= Entropy method for certifiable functions
The <entropy method for certifiable functions> turns short certificates into bounds on coordinate sensitivity. Suppose a nonnegative integer-valued <certifiable function> $f$ changes by at most $L$ when one coordinate changes and has certificates of size at most $g(k)$ at value $k$. Define the coordinate-deleted <functions>
$$
f_i(x^{(i)})=\inf_{y_i} f(x_1,\ldots,x_{i-1},y_i,x_{i+1},\ldots,x_n),
$$
assuming these <functions> are <measurable>. At an input of value $k$, changing a coordinate outside a chosen certificate cannot reduce the value below $k$. Hence $f_i=f$ outside that certificate, while $0\leq f-f_i\leq L$ on it. Consequently
$$
\sum_i(f-f_i)^2\leq L^2g(f).
$$
For <independent random variables>, the <Efron–Stein inequality> already gives $\operatorname{Var}(f(X))\leq L^2\mathbb E g(f(X))$. When $L=1$ and $g(k)=k$, the stronger bound $\sum_i(f-f_i)\leq f$ makes $f$ a <self-bounding function>. <Tensorization of entropy> and a <modified logarithmic Sobolev inequality> control exponential rather than quadratic variation, producing <concentration inequalities>. The certificate size alone needs this coordinate-change bound; an arbitrarily large change in one coordinate is not controlled by a short certificate.
Back to article page
