Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms
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=(Z1,…,Zn) have independent coordinates and let gi(Z) satisfy $\mathbb E[g_i(Z)\mid Z_{-i}]=0, \ \left| \mathbb E[g_i(Z)\mid Z_i]\right|\le M, \ \text{for every } i = 1, \dots, n, $ where Z−i denotes all coordinates except Zi. Assume additionally that changing any coordinate Zj, j≠ i, changes gi by at most β, we prove that, for every p≥2, for every p≥2, | ∑i=1n gi(Z)|p ≤ 16pnβ+M√(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.
Related
- From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms
- Logarithmic Hessian estimates for non-uniformly elliptic equations in non-divergence form
- Corrections to ``The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithms
- Generalization Analysis of Distributed Kernel-based Robust Gradient Descent Algorithms
- Mirror descent algorithms with logarithmic barriers
BibTeX
@misc{nguyencung2026logarithmicfree,
title = {{Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms}},
author = {Thanh Nguyen-Cung and Binh T. Nguyen},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.09870},
eprint = {2608.09870},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.09870},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms
AU - Thanh Nguyen-Cung
AU - Binh T. Nguyen
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2608.09870
UR - https://arxiv.org/abs/2608.09870
AB - 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,…,Z_n) have independent coordinates and let g_i(Z) satisfy $\mathbb E[g_i(Z)\mid Z_{-i}]=0, \ \left| \mathbb E[g_i(Z)\mid Z_i]\right|\le M, \ \text{for every } i = 1, \dots, n, $ where Z_−i denotes all coordinates except Z_i. Assume additionally that changing any coordinate Z_j, j≠ i, changes g_i by at most β, we prove that, for every p≥2, for every p≥2, | ∑_i=1^n g_i(Z)|_p ≤ 16pnβ+M√(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.
ER -