Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms
2026-08-10 • Machine Learning
Machine Learning
AI summaryⓘ
The authors address a question posed by Bousquet, Klochkov, and Zhivotovskiy about improving a mathematical bound related to learning algorithms' stability. They study functions whose outputs change a little when one input changes and prove a new inequality that removes an extra logarithmic factor from the previous result. Their new bound better matches known limits and applies to sums of weakly dependent functions of independent random variables. To do this, they first prove the result on a simple binary space and then extend it to more general cases using a special randomization method.
uniform stabilitygeneralization errormoment inequalityindependent random variablesweakly interacting functionsRademacher cubeproduct distributionrandomization argumentlearning algorithmlogarithmic factor
Authors
Thanh Nguyen-Cung, Binh T. Nguyen
Abstract
Uniform stability is a classical tool for controlling the generalization error of a learning algorithm. Bousquet, Klochkov, and Zhivotovskiy (2020) showed that the problem can be reduced to a moment inequality for a sum of weakly interacting functions of independent random variables. Their bound contains an additional factor $\log n$, and they asked whether this factor can be removed. We answer this upper-bound question affirmatively. More specifically, let $Z=(Z_1,\ldots,Z_n)$ have independent coordinates and let $g_i(Z)$ satisfy $$ \mathbb E[g_i(Z)\mid Z_{-i}]=0, \qquad \left| \mathbb E[g_i(Z)\mid Z_i]\right|\le M, \qquad \forall i = \overline{1, n} $$ while changing any coordinate $Z_j$, $j\neq i$, changes $g_i$ by at most $β$ and $Z_{-i}$ denotes all coordinates except $Z_i$. We prove that, for every $p\ge2$, $$ \left\| \sum_{i=1}^n g_i(Z)\right\|_p \le 16pnβ+M\sqrt{2pn}. $$ This removes the $\log n$ factor from the previous bound and matches the lower bound of Bousquet, Klochkov, and Zhivotovskiy up to universal constants in the range covered by their construction. Our proof first establishes the required estimate on the Rademacher cube, then transfers it to arbitrary product distributions by a two-copy randomization argument.