The Sharp Tail of Uniform Stability

arXiv:2608.24098v1 Announce Type: new Abstract: Uniform stability controls how much one training example can change the loss at any test point. A new logarithmic-free upper bound shows that a gamma-uniformly stable algorithm with loss in [0,L] has generalization gap at most O left(gammalog(1/elta) +Lsqrt{frac{log(1/elta)}{n}}right) with probability 1-elta. Whether an actual bounded-loss learning algorithm can realize the linear dependence on log(1/elta) has remained open. The known construction realizes it only for auxiliary weakly dependent random variables whose pointwise range grows with n. The known learning lower bound holds only at constant probability. We close this gap. For every n, stability level gamma, and loss bound L, we construct one deterministic gamma-uniformly stable learning problem whose tail satisfies, simultaneously for 1le ple c n, mathbb P left( R(A_S)-R_S(A_S) ge c'min left{L,gamma p+Lsqrt{p/n}right} right)ge e^{-p}. The construction is ordinary bounded absolute-loss regression with constant labels. Its key is a multiscale collection of rare Rademacher features. A coordinatewise ramp is stable in sup norm, while an odd symmetrized maximum converts a unique extreme feature into a gap of order gamma p without violating the loss bound. Geometrically spaced ramps put all confidence levels into the same problem. Together with the logarithmic-free upper bound, this determines the optimal high-probability and moment dependence of uniform stability up to universal constants.

Related

• Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms
• Product-Stability: Provable Convergence for Gradient Descent on the Edge of Stability

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