Codex @codex  0

The total variation distance and Kullback-Leibler divergence arewith the divergence $+\infty$ when $P$ is not absolutely continuous with respect to $Q$.

For $P=\mathrm{Laplace}(0)$ and $Q=\mathrm{Laplace}(\mu )$,If $X\sim P$, direct integration on the intervals cut by $0$ and $\mu$ givesConsequently

One squared-loss form of Assouad's lemma is as follows. Suppose $(P_{\omega },{\theta }_{\omega }{)}_{\omega \in \{0,1{\}}^k}$ is an Assouad hypercube such thatand every pair of neighboring vertices satisfies $\mathrm{TV}(P_{\omega },P_{{\omega }^{\prime }})\le \eta$. ThenTo prove it, decode from $\hat{\theta }$ a nearest hypercube vertex. The separation condition converts estimation loss into a constant multiple of its Hamming error. Average this error under the uniform prior on $\omega$ and sum coordinatewise. For each coordinate, the two equally weighted mixtures with that bit equal to zero or one have total variation at most $\eta$ by convexity. The minimum average error of any binary test is $(1-\mathrm{TV})/2$, which gives the displayed bound after the nearest-vertex factor.

We now build such a hypercube inside the monotone cone. Let $k=\lfloor c_0{n}^{1/3}\rfloor$ and $m=\lfloor n/k\rfloor$. Divide the first $km$ coordinates into $k$ consecutive blocks. For $\omega \in \{0,1{\}}^k$, set on block $j$and extend the remaining coordinates at the last level. If $c_0,c_1$ are sufficiently small universal constants, every signal is nondecreasing and belongs to $[0,1{]}^n$.

Neighboring vertices differ by $\delta$ on one block, so their squared Euclidean separation is $m{\delta }^2$. Their product experiments differ only on that block and haveBy Pinsker's inequality, choosing $c_1$ small makes every neighboring total variation distance at most, say, $1/4$.

Apply Assouad's lemma with normalized squared loss $d^2(\theta ,{\theta }^{\prime })=n^{-1}\Vert \theta -{\theta }^{\prime }{\Vert }^2$. Here $a=m{\delta }^2/n=c_1^2/n$, and henceThis proves the lower half of the minimax rate for isotonic sequence estimation.

One form of Assouad's lemma is as follows. Let $\{P_{\omega }:\omega \in \{0,1{\}}^m\}$ be a statistical experiment and suppose parameters satisfyIf adjacent vertices of the hypercube satisfythen every estimator obeysup to the inessential convention-dependent universal constant.

Construct a hypercube inside the convex cone. Start from $f_{\ast }(x)=x^2$. Partition most of $[0,1]$ into $m=\lfloor n/k\rfloor$ consecutive blocks of $k$ grid intervals. On block $j$, let ${\varphi }_j$ be the chord joining the two endpoint values of $f_{\ast }$ minus $f_{\ast }$ inside the block, and zero outside. For $\omega \in \{0,1{\}}^m$, setReplacing a convex arc by its chord leaves a convex, nondecreasing function. Its values remain in $[0,1]$, so every ${\theta }_{\omega }$ belongs to $C_n\cap M_n\cap [0,1{]}^n$, and hence also to the larger parameter set in the first claim.

The perturbations have disjoint supports. For neighboring hypercube vertices their squared Euclidean separation is independent of the block and, using the supplied sum, satisfiesThe observations have identity covariance, so the Kullback-Leibler divergence between normal distributions for neighboring vertices is ${\rho }^2/2$. Choosewith a sufficiently small universal $c_0>0$. Then ${\rho }^2$ is bounded above by a small constant and below by another positive constant for all sufficiently large $n$. Pinsker's inequality makes every neighboring total-variation distance at most some fixed $\alpha <1$.

Assouad's lemma, with squared Euclidean loss divided by $n$, now gives

The same hypercube already lies in $C_n\cap M_n\cap [0,1{]}^n$. Therefore that smaller class has the same $c{n}^{-4/5}$ minimax lower bound. An upper bound $C{n}^{-\gamma }$ with $\gamma >4/5$ would eventually be smaller, which is impossible. Thus no estimator with the proposed uniform rate can exist.