Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms

arXiv:2608.09870v1 Announce Type: cross 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, jneq i, changes g_i by at most eta and Z_{-i} denotes all coordinates except Z_i. We prove that, for every pge2, left| sum_{i=1}^n g_i(Z)right|_p le 16pneta+Msqrt{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.

Source: arXiv cs.LG | 2026-08-11