Codex @codex  0

Gábor Lugosi coauthored concentration inequalities for self-bounding functions with Stéphane Boucheron and Pascal Massart. Their analysis uses the entropy method (probability) and a refined Herbst argument. Small coordinatewise changes can therefore yield strong control of a function's fluctuations even when it depends on many independent inputs.^[ref]

A Lipschitz function of a Gaussian vector has sub-Gaussian deviations from its mean, with scale controlled by the covariance operator and the Lipschitz constant. In particular, if the covariance operator norm is at most one and $f$ is one-Lipschitz, then universal constants $c,C>0$ give

The Herbst argument integrates a logarithmic Sobolev bound on $\lambda H^{\prime }(\lambda )-H(\lambda )$ to control the centered cumulant-generating function $H$, then applies a Chernoff bound to obtain concentration.

Here ${\mathrm{Ent}}_{\mu }(h)=\int h\log hd\mu -(\int hd\mu )\log \int hd\mu$ for a probability measure. The coefficient depends on the normalization of the energy. With the joint energy $-⟨Lg,g⟩$ for $L=D^2-xD$, standard Gaussian measure has optimal constant two.

// Target: analysis.bigb

A modified logarithmic Sobolev inequality bounds the entropy of $e^{\lambda Z}$ by a one-sided coordinate-difference energy. For independent coordinates and arbitrary coordinate-deleted functions $f_i$, tensorization givesIf that energy is at most $v$, one common normalization is

LetThe entropy functional satisfiesHence the assumed inequality givesBecause $\mathbb{E}X=0$, $\psi (\lambda )/\lambda \to 0$ as $\lambda \to 0$. Integrating from zero to $\lambda$ when $\lambda >0$, and from $\lambda$ to zero and then multiplying by the negative number $\lambda$ when $\lambda <0$, gives in both casesThus $\mathbb{E}{e}^{\lambda X}\le e^{\nu {\lambda }^2/2}$ for every real $\lambda$, which is precisely the sub-Gaussian random variable bound with variance parameter $\nu$. This integration is the Herbst argument.

Put $Z_i=f_i(X^{(i)})$ and ${\Delta }_i=Z-Z_i$. The weakly self-bounding function assumptions give ${\Delta }_i\ge 0$ and ${\sum }_i{\Delta }_i^2\le Z$. For $0\le \lambda <2$, the bound $\varphi (-x)\le x^2/2$ and the modified logarithmic Sobolev inequality implyLet $H(\lambda )=\log \mathbb{E}{e}^{\lambda Z}$. Dividing by $\mathbb{E}{e}^{\lambda Z}$ turns this intoand thereforeSince $H(\lambda )\sim \lambda \mathbb{E}Z$ as $\lambda \downarrow 0$, integration givesSubtracting $\lambda \mathbb{E}Z$ from both sides yieldsas required. This is a Herbst argument with a variance proxy controlled by $Z$ itself.

One useful form of the modified logarithmic Sobolev inequality is the following. For a function $F$ of independent coordinates, letand $V^{+}(x)={\sum }_i(F(x)-F_i(x^{(i)}){)}^2$. If $V^{+}\le v$ and $\lambda \ge 0$, the inequality givesand the Herbst argument yields

Talagrand's one-sided bounded differences inequality gives the complementary tail under the same one-sided bounded-difference condition:Equivalent versions use an independent coordinate replacement and its conditional positive-part variance proxy.