The Sharp Tail of Uniform Stability

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 γ-uniformly stable algorithm with loss in [0,L] has generalization gap at most O (γ (1/δ) +L sqrt(1/δ) over n) with probability 1-δ. Whether an actual bounded-loss learning algorithm can realize the linear dependence on (1/δ) 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 γ, and loss bound L, we construct one deterministic γ-uniformly stable learning problem whose tail satisfies, simultaneously for 1 p c n, P (R(A S)-R S(A S) c' L,γp+L sqrt p/n) 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 γ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.