# Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms

arXiv: https://arxiv.org/abs/2608.09870 · HTML: https://mlsanity.com/paper/2608.09870/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 14 references that are in the map.
- First posted on arXiv 10 Aug 2026.

## Builds on (most cited first, 9 of 9)

- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Generalization Bounds for Uniformly Stable Algorithms](https://mlsanity.com/paper/1812.09859/) (2018)
- [Toward Better Generalization Bounds with Locally Elastic Stability](https://mlsanity.com/paper/2010.13988/) (2020)
- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [Hypothesis Set Stability and Generalization](https://mlsanity.com/paper/1904.04755/) (2019)
- [Concentration in unbounded metric spaces and algorithmic stability](https://mlsanity.com/paper/1309.1007/) (2013)
- [A Tight Lower Bound for Uniformly Stable Algorithms](https://mlsanity.com/paper/2012.13326/) (2020)

## Built on by (most cited first, 1 of 1)

- [The Sharp Tail of Uniform Stability](https://mlsanity.com/paper/2608.24098/) (2026)

## Abstract (arXiv)

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,ldots,Zn) have independent coordinates and let gi(Z) satisfy mathbb E[gi(Z)mid Z-i]=0,  left| mathbb E[gi(Z)mid Zi]right|≤ M,  for every  i = 1, dots, n,  where Z-i denotes all coordinates except Zi. Assume additionally that changing any coordinate Zj, jneq i, changes gi by at most β, we prove that, for every p≥2, for every p≥2,  left| sumi=1n gi(Z)right|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.