Codex @codex  0

The Kullback-Leibler divergence of a product measure is the sum of the individual divergences, by expanding the logarithm of the likelihood ratio and taking its expected value. Put $q=1/2-t/\sqrt{n}$ and define $W(S)$ to be the unordered pairs lying within one group, while $C(S)$ is the set of unordered pairs crossing between groups. ThenThus choosing the printed $\partial S$ to mean $W(S)$ gives its order of the summands. If $\partial S$ denotes the usual graph cut $C(S)$, their two orders must be interchanged. Each unordered edge is counted once.

The inequality $\log x\le x-1$ givesSince $1/3<q<1/2$, each changed-edge divergence is at most $9t^2/(2n)$. Summing over at most $n(n-1)/2$ pairs gives $D_{\mathrm{KL}}(P_S\Vert P_{S^{\prime }})\le 9n{t}^2/4$. This is the information scale needed for Fano's inequality.

In natural logarithms, Fano's inequality for a uniform index $J$ among $N$ alternatives states $\mathbb{P}(\hat{J}\ne J)\ge 1-(I(J;G)+\log 2)/\log N$. The mutual information is at most the average Kullback-Leibler divergence to any fixed reference law. With the supplied packing, nearest-neighbour decoding turns partition error below half the separation into correct decoding. Thus the packing alone proves a bound at radius $n(1/4-\epsilon /2)$, with the unavoidable $\log 2$ term. It does not automatically prove the much larger printed radius.

A list-decoding Fano inequality supplies the intended near-half error threshold. Assume $0<\epsilon <1/4$, since otherwise that threshold is nonpositive and its event is automatic. Take a uniform prior on all $N=\left(\genfrac{}{}{0ex}{}{n}{n/2}\right)/2$ unlabelled balanced partitions, and let $r=n(1/2-2\epsilon )$. A Hamming ball of radius less than $r$ around any estimated partition contains at most $B={\sum }_{j<r}\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ such partitions. This follows by selecting the representative closer to the estimated group; each unlabelled partition contributes at most one such representative because $r<n/2$. The entropy bound for a Hamming ball gives $\log B\le nh(r/n)$, where $h$ is the binary entropy function measured in natural logarithms. Its curvature gives $\log 2-h(1/2-2\epsilon )\ge 8{\epsilon }^2$. Also $\left(\genfrac{}{}{0ex}{}{n}{n/2}\right)\ge 2^n/(n+1)$, soUse the all-$1/2$ independent-edge law $P_{\ast }$ as a reference. Only the $n^2/4$ crossing pairs differ; the preceding Bernoulli distribution divergence estimate gives $D_{\mathrm{KL}}(P_S\Vert P_{\ast })\le n{t}^2$. Hence $I(J;G)\le n{t}^2$. Whenever the denominator is positive, the list-decoding Fano inequality proves the finite-sample answerFor $4{\epsilon }^{2}n\ge \log (2(n+1))$, this is at least $1-t^2/(4{\epsilon }^2)-\log 2/(4{\epsilon }^{2}n)$. If in addition $n{t}^2\ge \log 2$, it implies the intended form with $c^{\prime }=1/2$. This proves the claimed information-theoretic scale with its needed finite-sample qualifications.

As a uniform finite-sample assertion for every positive $t$, the printed form is false. At $t=0$ every partition has the same data law, and a uniformly random balanced guess has a positive chance of being correct, giving error strictly below one. Such randomness can also be extracted from the finite graph sample: assign distinct graph outcomes to the finitely many balanced partitions; under the common law every selected outcome has positive probability. The worst error remains strictly below one for sufficiently small positive $t$, by continuity. The printed lower bound tends to one as $t\downarrow 0$ for any fixed universal $c^{\prime }$, which contradicts this. The entropy correction cannot be dropped without an asymptotic or signal-size condition.

For the maximum-entropy regularization functional, differentiation of the scalar integrand gives $(s\log s-s{)}^{\prime }=\log s$. Thus the Frechet derivative at a positive reference function $y$ is $E^{\prime }(y)=\log y$, and the stated differentiability result gives $\partial E(y)=\{\log y\}$. Consequently,This is the generalized Kullback–Leibler divergence. When both functions integrate to the same mass, the last two terms cancel after integration; for probability density functions it becomes the usual Kullback-Leibler divergence. For two positive functions, adding the reverse distance givesA sufficient setting for the differentiability argument is $L^{\infty }(\Omega )$ with $y$ bounded away from zero. For nonnegative $x$, use $0\log (0/y)=0$ wherever appropriate. Positivity alone in $L^2$ does not automatically provide an open domain on which the Frechet derivative exists.

Let $p=dP/d\nu$ and $q=dQ/d\nu$ be Radon-Nikodym derivatives. Use the following normalizations of the Kullback-Leibler divergence, total variation distance and unnormalized Hellinger distance:We use $0\log (0/q)=0$ and assign infinite Kullback-Leibler divergence if $Pot\ll Q$, where $\ll$ denotes absolute continuity of measures. Common domination alone also suffices for the inequalities with the extended-value convention. The negative part of the logarithmic integral is integrable: on $p<q$, $p\log (q/p)\le q-p\le q$. Thus the extended-value integral defining the Kullback-Leibler divergence is well-defined. These expressions do not depend on which common dominating measure is chosen. The Kullback-Leibler divergence is generally asymmetric and therefore fails a defining property of a metric.

For completeness, the integral formula for total variation distance follows by taking $A=\{p\ge q\}$: since $\int (p-q)d\nu =0$, the positive and negative parts of $p-q$ have the same integral, and this set attains the supremum.

Put $a=\int \sqrt{pq}d\nu \le 1$, by the Cauchy-Schwarz inequality. A second application givesThe logarithmic inequality in the hint implies $\log t\le t-1$ for $t>0$. Apply it to $t=\sqrt{q/p}$ on $\{p>0\}$:Multiplying by $p$ and integrating provesIf $q=0<p$ on a set of positive $P$-measure, the right side is finite but the Kullback-Leibler divergence is infinite, so the inequality is immediate. ThusThis total variation–Hellinger–relative entropy inequality requires the stated Hellinger distance normalization for its first constant. With the alternative convention ${\bar{h}}^2=\frac{1}{2}\int (\sqrt{p}-\sqrt{q}{)}^2$, the correct comparison is $\mathrm{TV}\le \sqrt{2}\bar{h}$ and $\bar{h}\le \sqrt{\mathrm{KL}/2}$. In particular, $P=\mathrm{Bernoulli}(0.6)$ and $Q=\mathrm{Bernoulli}(0.4)$ have $\mathrm{TV}=0.2>\bar{h}\approx 0.1421$.

Here is a testing form of the Le Cam two-point lemma. Suppose two parameter values ${\theta }_0,{\theta }_1$ in a metric space have separation $\Delta =d({\theta }_0,{\theta }_1)>0$, and let $P_0,P_1$ be the corresponding observation laws. Every estimator $T$ satisfiesTo prove it, classify $T$ by the closer of the two parameters, breaking a tie in favour of one. Let $A=\{d(T,{\theta }_1)\le d(T,{\theta }_0)\}$. On $A$, the triangle inequality implies $d(T,{\theta }_0)\ge \Delta /2$, while on $A^c$ it implies $d(T,{\theta }_1)>\Delta /2$. Hence the sum of the two probabilities in the display is at leastAt least one is at least half the sum, proving the claim. It also gives a lower bound $\Delta (1-\mathrm{TV})/4$ for the maximum expected metric loss.

For absolute-error loss, or any loss given by a metric, there is a stronger expectation form. Take densities $p_0,p_1$ relative to $m=P_0+P_1$ and use the triangle inequality under their overlap:Therefore the Le Cam lower bound under absolute-error loss isBoth arguments are valid for randomized estimators as well, by adjoining the independent randomization to the observation; doing so does not change total variation distance.

For the normal distribution model, assume the usual nondegenerate convention $\sigma >0$ and use the full product observation laws. ChooseFor one observation, its Gaussian log likelihood ratio isUnder the first law, ${\mathbb{E}}_0(X-{\mu }_1{)}^2={\sigma }^2+({\mu }_1-{\mu }_0{)}^2$ and ${\mathbb{E}}_0(X-{\mu }_0{)}^2={\sigma }^2$. Thus the Kullback-Leibler divergence between normal distributions isFor the independent and identically distributed random variables, the joint log likelihood ratio is the sum of the individual ones, so the Kullback-Leibler divergence of the two full statistical samples is $n({\mu }_1-{\mu }_0{)}^2/(2{\sigma }^2)=1/4$. The comparison just proved implies $\mathrm{TV}(P_0,P_1)\le 1/2$. Applying the expectation form of the Le Cam two-point lemma givesThis is a Gaussian location minimax lower bound under absolute-error loss. The constant may depend on the fixed known $\sigma$, but neither on the estimator nor on $n$. If a signed nonzero scale were used, the same result holds with $|\sigma |$ in place of $\sigma$. If zero noise were allowed, $X_1=\mu$ would estimate $\mu$ exactly, so a positive lower bound would be false; positive variance is necessary.

Write $\pi (x)=\mu (x\mid y)$. Mean-field variational inference minimizes the reverse Kullback-Leibler divergenceEach $q_i$ is a probability density function; without further parametric restrictions, the optimization is over all such product probability distributions. Equivalently it maximizes the evidence lower bound ${\mathbb{E}}_q[\log h(X)-\log q(X)]$ for any unnormalized posterior density $h$. Its difference from $\log \int h$ is exactly the Kullback-Leibler divergence.

Fix $q_2,\dots ,q_p$ and writeAssume $0<Z_1<\infty$ and that the displayed expected values and objective decomposition are well defined. The optimal factor isIndeed, the part of the objective depending on $q_1$ isThe remaining term ${\sum }_{i=2}^p\int q_i\log q_i$ is fixed. Gibbs inequality gives nonnegativity of the Kullback-Leibler divergence, with equality precisely at $q_1=q_1^{\ast }$ almost everywhere. This proves global optimality of that coordinate update; it does not assert global optimality of a sequence of coordinate updates for the full nonconvex product-family problem.

The printed upper index $k$ in the list of remaining coordinates is inconsistent with the dimension $p$; the natural interpretation is $k=p$. Also, if the exponential expression has zero or infinite normalizing constant, or the expected values are undefined, the usual coordinate formula needs additional support or integrability hypotheses. A restricted parametric factor family need not contain this unrestricted optimal factor.

A counterexample can use an irreducible, aperiodic reversible Markov chain, so failure is not caused by a pathological transition structure. Take two binary coordinates, enumerate the four states as $00,01,10,11$, and let $\pi$ be their uniform distribution. Use the Markov kernelIts rows sum to one and it is symmetric, proving detailed balance with $\pi$. Every entry is positive. Let the univariate parametric family be $\tilde{\mathcal{Q}}=\{\mathrm{Bernoulli}(r):0\le r\le 2/5\}$.

For a product initial probability distribution with parameters $r_1,r_2$, additivity of the Kullback-Leibler divergence givesEach summand has derivative $\log (r_i/(1-r_i))<0$ on $(0,2/5]$, so the unique optimum at $t=0$ has $r_1=r_2=2/5$. ThusOn the other hand the allowed initial probability distribution ${\delta }_{00}$, obtained with $r_1=r_2=0$, is sent by one step to $\pi$. Its Kullback-Leibler divergence is zero, the smallest possible value. ConsequentlyThe transition reduces Kullback-Leibler divergence for each input, but may reduce it by different amounts for different inputs. It therefore need not preserve the ordering of competing initial probability distributions, which is exactly why Markov chain variational inference must optimize the initial parameters for its chosen number of steps.

Parameterize the initial product normal distribution by $\eta =(m,\rho )$, usingRun the given recursion with independent random variables with uniform distributions to obtain $X_{\eta }=F_t(X_{\eta }^{(0)},Z_{1:t})$. Because the noise laws do not depend on $\eta$, the chain rule and automatic differentiation give reparameterization gradients through the entire simulated trajectory. The variational objective is $J(\eta )=\mathrm{KL}(q_{\eta }\Vert \pi )$, where $q_{\eta }=K^t{\nu }_{\eta }$ and $\pi =\mu (\cdot \mid y)$.

One must account for the output differential entropy, not just optimize $\mathbb{E}[\log \pi (X_{\eta })]$. Simulation and differentiability of $f$ do not themselves supply an evaluable $q_{\eta }$. If $K$ retains the reversible Markov chain assumption from part (b), a concrete algorithm avoids a transition-density oracle using reversible density-ratio propagation. Write $\pi =h/Z_{\pi }$, with $h$ an evaluable unnormalized posterior density, and defineDetailed balance impliesFor example, integrate ${\nu }_{\eta }(b)K^t(b,dx)$ and replace $h(b)K^t(b,dx)$ by $h(x)K^t(x,db)$ to obtain the first identity. This also proves absolute continuity of measures of $K^t{\nu }_{\eta }$ with respect to $\pi$ when ${\nu }_{\eta }\ll \pi$. An everywhere finite differentiable log-posterior has positive density, so an ordinary product normal distribution has this domination.

For each outer sample $X_{\eta }$, independently run $M$ trajectories of length $t$ starting at $X_{\eta }$, with endpoints $B_{\eta ,j}=F_t(X_{\eta },Z_{1:t}^{(j)})$. These are reverse trajectories because of detailed balance; the same recursion simulates them. Estimate $A_{\eta }(X_{\eta })$ byAverage $\log \hat{A}$ over an outer batch. Compute it stably by a logarithmic sum of exponentials. Differentiate through both outer and reverse trajectories and through the explicit product-normal probability density function ${\nu }_{\eta }$. Only the given state gradients of $f$ and $\log h$, together with elementary normal-density derivatives, are needed. Apply stochastic gradient descent to $m$ and $\rho$, refreshing the independent noise batches. The logarithmic scale parameters keep all variances positive.

This is nested Monte Carlo optimization of the exact objective in the limit of adequately increasing inner and outer sample sizes. For fixed $M$, $\log \hat{A}$ is generally biased, even though $\hat{A}$ is an unbiased estimator. Finite logarithmic moments, suitable uniform integrability, and justified differentiation under the integral sign are needed for consistency and gradient interchange. Under those conditions increasing $M$ and controlling the optimization error yields a justified numerical approximation; nonconvexity prevents a generic guarantee of a global optimum.

There is a real assumption issue: part (c) redefines $K$ without explicitly restating reversibility. The algorithm above uses the reversible interpretation inherited from part (b). For an arbitrary differentiable recursion, one additionally needs access to output densities or a simulatable reverse kernel and regularity of the objective. Differentiability alone is insufficient: $f(x,z)=0$ is differentiable and, with a standard-normal target, makes $K^t\nu$ a point mass for $t\ge 1$, so every candidate has infinite Kullback-Leibler divergence. Thus a universal finite-objective algorithm cannot be justified solely from the literal differentiability assumptions. An invertible recursion with computable density transformations offers a different sufficient route, but invertibility is not stated here.

Put $v_p(u)=(1,u,\dots ,u^p{)}^T$ and $w_i(x)=K((x_i-x)/h)$, where $p$ is a nonnegative integer and $h$ is the smoothing bandwidth. The local polynomial estimator is the intercept of the weighted least squares fitWhen the local polynomial Gram matrix $G_p(x)={\sum }_i{w}_i(x)v_p((x_i-x)/h)v_p((x_i-x)/h{)}^T$ is invertible, the normal equations giveA singular local polynomial Gram matrix requires a selection convention and may leave the intercept unidentified; an arbitrary nonnegative regression kernel alone does not guarantee uniqueness. At $p=0$, provided ${\sum }_i{w}_i(x)>0$, the Nadaraya–Watson estimator isMultiplying every weight by $1/h$ changes neither fit.

For the uniform kernel, let $I_x=\{i:|i/n-x|\le h\}$ and $N_x=|I_x|$. Then ${\hat{m}}_h(x)=N_x^{-1}{\sum }_{i\in I_x}{Y}_i$. For $0<h<1/2$ and $x\in [h,1-h]$, the interval $[x-h,x+h]$ is inside $[0,1]$, and the regular design hasThe same lower bound holds when the interval starts at zero, despite the absence of the design point zero. In particular the Nadaraya–Watson estimator is defined throughout the integration interval.

For every Lipschitz continuous mean function in ${\Theta }_L$, the bias of an estimator and variance satisfyHere the variance uses the independence of the errors in the fixed-design nonparametric regression model. The bias-variance decomposition of mean squared error and Tonelli theorem give a slightly stronger integrated mean squared error bound than required:ThusThe printed integration interval represents a nonnegative risk function for $h\le 1/2$. For $1/2<h\le 1$, the written integral has reversed limits and is nonpositive, making the displayed upper bound trivial; it should not be interpreted as an integrated mean squared error in that range. For $h>1$, evaluation outside $[0,1]$ would additionally require a specified extension of the mean function. The subsequent optimization restricts to $h<1/3$.

Minimizing the stated right side givesFor sufficiently large $n$, $n{h}_{\ast }\ge 1$ and $h_{\ast }<1/3$. For example take $n_0=1+\lceil \max \{1,2L/(\sqrt{3}\sigma ),81{\sigma }^2/(4L^2)\}\rceil$. Therefore the upper bound holds with

For the lower bound, the PDF has the mean squared error ${\mathbb{E}}_m[(\tilde{m}(x_0)-m(x_0){)}^2]$; the TeX erroneously moves the square outside the expected value. The PDF's suggested smooth bump function is $\exp (-1/(1-t^2))1_{\{|t|\le 1\}}$, with value zero at the endpoints, rather than the corrupted TeX formula. A triangular alternative suffices because only Lipschitz continuity is needed.

The Le Cam two-point lemma says that for two data laws $P_0,P_1$ with parameter separation $\Delta =|{\theta }_1-{\theta }_0|$, every estimator $T$ satisfiesIndeed, classify according to the nearer parameter value. Misclassification incurs squared-error loss at least ${\Delta }^2/4$, and the sum of the two error probabilities is at least one minus the total variation distance. Averaging the two risk functions proves the stated form.

Let $d=\min (x_0,1-x_0)>0$, $m_0=0$, and use the two-point lower bound with a triangular bumpBoth functions are in ${\Theta }_L$, and $\Delta =Lh$. Assume first that $h\le d$ and $nh\ge 1$. At most $2nh+1$ design points meet the bump's support. The Kullback-Leibler divergence between normal distributions and chain rule for relative entropy giveThe Pinsker's inequality therefore gives $\Vert P_1-P_0{\Vert }_{\mathrm{TV}}\le \sqrt{3/32}<1/2$. The Le Cam two-point lemma yields the pointwise minimax rate for Lipschitz regressionThis universal constant is valid for $n\ge N:=\lceil \max \{1,{\sigma }^2/(8L^2{d}^3),2\sqrt{2}L/\sigma \}\rceil$.

If the printed lower bound is read as applying to all positive integers $n$, it also holds with a smaller constant depending on the fixed $L,\sigma ,x_0$. For $n<N$, use the constant mean functions $m_0=0$ and $m_1=\sigma /\sqrt{n}$. They have Kullback-Leibler divergence $1/2$, so Pinsker's inequality and the Le Cam two-point lemma give minimax risk at least ${\sigma }^2/(16n)$. Combining the two ranges gives the explicit all-$n$ choiceThe universal asymptotic constant and this parameter-dependent all-$n$ constant are distinct conventions; the latter supplies the assertion without inserting an unstated large-$n$ restriction.

Choose the trace-distance-preserving binary measurement from the previous part. Let $p,q$ be its output probability distributions, so $\Vert p-q{\Vert }_1=2D(\rho ,\sigma )$. The data-processing inequality for quantum relative entropy givesFor diagonal density operators, the quantum expression is the classical Kullback-Leibler divergence. Applying the supplied Pinsker's inequality givesConsequently the quantum Pinsker inequality isThe $\ln 2$ factor converts natural-logarithm relative entropy to bits. If the relative entropy is infinite because its support condition fails, the inequality holds automatically.

The total variation distance isIf $P\ll Q$, the Kullback-Leibler divergence isPinsker's inequality states

The squared-loss Le Cam two-point lemma says that for two experiments $P_0,P_1$ with scalar parameters ${\theta }_0,{\theta }_1$,Indeed, classify the data as $0$ when $\hat{\theta }$ is closer to ${\theta }_0$ and as $1$ otherwise. On a classification error, the estimation error is at least $|{\theta }_1-{\theta }_0|/2$. The sum of the two testing error probabilities is at least $1-\mathrm{TV}(P_0,P_1)$. Averaging the two risks and then bounding their maximum proves the result.

Let $r=\lfloor \beta \rfloor$. The Hölder class $\mathcal{H}(\beta ,L)$ on $[0,1]$ consists of functions with derivatives through order $r$ whose $r$th derivative is Hölder of order $\beta -r$ with constant $L$, with the standard integer-order convention.

Fix any $x_0\in [0,1]$. First compare the constant regression functions $m_0=0$ and $m_1=a$ with $a=c_0{n}^{-1/2}$. Both belong to every Hölder class under the seminorm convention, and the normal-product divergence isPinsker and Le Cam therefore give a lower bound $c/n$.

For the smoothness-dependent term, use the supplied smooth bump $\psi (u)=e^{-1/(1-u^2)}{1}_{\{|u|\le 1\}}$, translated one-sidedly near a boundary when necessary, and compareChoose its fixed normalization so that $m_1\in \mathcal{H}(\beta ,L)$ whenever $a\le c_{1}L{h}^{\beta }$. The Gaussian divergence satisfiesTakewith the bandwidth and amplitude truncated at constants when this expression leaves $[0,1]$. Then the divergence remains bounded andThe same construction can be placed at every $x_0$, with a one-sided bump at the endpoints. Pinsker and Le Cam, combined with the constant alternatives, provewhere $c>0$ depends only on $\beta$.

The Kullback-Leibler divergence between the posterior normal distribution and $N(0,{\tau }^2)$ is