Search papers, labs, and topics across Lattice.
This paper establishes a new logarithmic-free upper bound for the generalization gap of $\gamma$-uniformly stable algorithms, showing that it can be expressed as $O(\gamma\log(1/\delta) + L\sqrt{\frac{\log(1/\delta)}{n}})$ with high probability. The authors construct a deterministic learning problem that achieves this bound, addressing the previously open question of whether a bounded-loss learning algorithm can realize the linear dependence on $\log(1/\delta)$. By utilizing a multiscale collection of rare Rademacher features, the authors demonstrate that their method maintains stability while effectively managing the generalization gap.
Achieving a logarithmic-free upper bound for generalization gaps in $\gamma$-uniformly stable algorithms could redefine our understanding of stability in machine learning.
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(\gamma\log(1/\delta) +L\sqrt{\frac{\log(1/\delta)}{n}}\right)$ with probability $1-\delta$. Whether an actual bounded-loss learning algorithm can realize the linear dependence on $\log(1/\delta)$ 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 $1\le p\le c n$, $\mathbb P \left( R(A_S)-R_S(A_S) \ge c'\min \left\{L,\gamma p+L\sqrt{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.
