stat.MLAug 10, 2026

Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms

Authors: Thanh Nguyen-Cung, Binh T. Nguyen

Organizations: VinUniversity

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\log n, and they asked whether this factor can be removed. We answer this upper-bound question affirmatively. More specifically, let Z=(Z1,…,Zn)Z=(Z_1,\ldots,Z_n) have independent coordinates and let gi(Z)g_i(Z) satisfy E[gi(Z)∣Z−i]=0, ∣E[gi(Z)∣Zi]∣≤M, for every i=1,…,n,\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−iZ_{-i} denotes all coordinates except ZiZ_i. Assume additionally that changing any coordinate ZjZ_j, j≠ij\neq i, changes gig_i by at most ββ, we prove that, for every p≥2p\ge2, for every p≥2p\ge2, ∥∑i=1ngi(Z)∥p≤16pnβ+M2pn.\left\| \sum_{i=1}^n g_i(Z)\right\|_p \le 16pnβ+M\sqrt{2pn}. This removes the log⁡n\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.

Explore similar work

CardsList
Jun 5, 2026stat.ML

Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite L_p Moments

While algorithmic stability is a central tool for understanding generalization of learning algorithms, existing high-probability guarantees typically rely on uniform boundedness or sub-Gaussian/sub-Weibull tail assumptions, which can be overly restrictive for modern settings with heavy-tailed or unbounded losses. We develop a stability-based framework that requires only a finite LpL_p moment condition. Our first contribution is sharp concentration inequalities for functions of independent random variables under LpL_p constraints, extending McDiarmid's bounded-differences techniques beyond the classical regime. Leveraging these results, we derive sharp high-probability generalization bounds across a range of learning paradigms, including empirical risk minimization, transductive regression, and meta-learning. These guarantees show that LpL_p stability suffices for robust generalization even when boundedness fails, substantially weakening the standard assumptions in the stability literature.
Qianqian Lei, Soham Bonnerjee, Yuefeng Han +1
Generalization BoundsEmpirical Risk MinimizationFiniteConcentration
AskPDF
May 22, 2025stat.ML

Improved generalization bounds for binary linear classification via isoperimetry

We examine the concentration of uniform generalization errors around their expectation in binary linear classification problems via an isoperimetric argument. In particular, we establish Poincaré and log-Sobolev inequalities for the joint distribution of the output labels and the label-weighted input vectors, which we apply to derive concentration bounds. The derived results improve upon existing bounds obtained from general unbounded empirical processes, as well as that tailored specifically to logistic regression. In asymptotic analysis, we also show that almost sure convergence of uniform generalization errors to their expectation occurs in very broad settings, such as proportionally high-dimensional regimes. Using this convergence, we establish uniform laws of large numbers under dimension-free conditions.
Shogo Nakakita
Generalization BoundsConcentration InequalitiesEmpirical Risk MinimizationMulticlass Classification
AskPDF
Jun 5, 2026cs.LG

Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters

We analyze generalization error, uniform stability, and uniform argument stability of gradient descent (GD) and stochastic gradient descent (SGD) over discrete parameter spaces, where each update involves deterministic or stochastic rounding. We show that deterministic rounding degrades the generalization error of GD on convex, Lipschitz, and smooth loss functions, increasing the rate from O(T/n)O(T/n) to O(T/n)O(T/\sqrt{n}), and establish matching lower bounds. We further prove that uniform stability of GD becomes Ω(T)Ω(T), showing that stability-based generalization bounds are vacuous in this setting. In contrast, for the same losses, stochastic gradient descent with deterministic rounding admits nontrivial uniform stability guarantees, which differ qualitatively from the real-valued case and exhibit distinct dependencies on the number of iterations and the dimension: we prove tight bounds O(T/n)O(T/n) for one dimension and O(T2/n)O(T^2/n) for higher dimensions. We also show that stochastic rounding can introduce generalization error that increases with the dimension; such a phenomenon is absent in standard real-valued optimization and in the deterministic rounding case. Finally, we provide upper bounds on uniform argument stability for stochastic rounding schemes and show that these bounds are tight when the loss can be represented as a sum of coordinate-wise functions.
Jonghyun Shin, Sejun Park
Stochastic Gradient DescentGeneralization BoundsGradient DescentFixed-Point Iteration
AskPDF