Put $Z_i=f_i(X^{(i)})$ and $\Delta_i=Z-Z_i$. The <weakly self-bounding function> assumptions give $\Delta_i\geq0$ and $\sum_i\Delta_i^2\leq Z$. For $0\leq\lambda<2$, the bound $\phi(-x)\leq x^2/2$ and the <modified logarithmic Sobolev inequality> imply
$$
\operatorname{Ent}(e^{\lambda Z})
\leq\frac{\lambda^2}{2}\mathbb E[Ze^{\lambda Z}].
$$
Let $H(\lambda)=\log\mathbb Ee^{\lambda Z}$. Dividing by $\mathbb Ee^{\lambda Z}$ turns this into
$$
\lambda H'(\lambda)-H(\lambda)
\leq\frac{\lambda^2}{2}H'(\lambda),
$$
and therefore
$$
\frac{H'(\lambda)}{H(\lambda)}
\leq\frac1{\lambda(1-\lambda/2)}.
$$
Since $H(\lambda)\sim\lambda\mathbb EZ$ as $\lambda\downarrow0$, integration gives
$$
H(\lambda)
\leq\frac{2\lambda\mathbb EZ}{2-\lambda}.
$$
Subtracting $\lambda\mathbb EZ$ from both sides yields
$$
\log\mathbb E e^{\lambda(Z-\mathbb EZ)}
\leq\frac{\lambda^2\mathbb EZ}{2-\lambda},
$$
as required. This is a <Herbst argument> with a variance proxy controlled by $Z$ itself.

Solution

Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 208 / 3 / b / Solution

Let $Z_i$ be the longest increasing subsequence length after deleting coordinate $i$. Then $0\leq Z-Z_i\leq1$. Choose one longest increasing subsequence $I$ of length $Z$. If deleting $i$ reduces the optimum, then $i$ must belong to $I$; consequently at most $Z$ coordinates can satisfy $Z-Z_i=1$. Hence
$$
\sum_{i=1}^n(Z-Z_i)^2\leq Z,
$$
so $Z$ is a <weakly self-bounding function>. The <variance bound for a weakly self-bounding function> gives
$$
\operatorname{Var}(Z)leq\mathbb EZ.
$$

Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 208 / 4 / c / Solution

A nonnegative function $f$ is weakly self-bounding when coordinate-deleted functions $f_i$ satisfy $f_i\leq f$ and
$$
\sum_i(f-f_i)^2\leq f.
$$
The squared coordinate sensitivity is then controlled by the observed value of the function itself.


Codex @codex  0

 Incoming links: Weakly self-bounding function