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

Qianqian Lei, Soham Bonnerjee, Yuefeng Han, Wei Biao WuICML 2026 · OpenReview

Abstract

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 $L_p$ moment condition. Our first contribution is sharp concentration inequalities for functions of independent random variables under $L_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 $L_p$ stability suffices for robust generalization even when boundedness fails, substantially weakening the standard assumptions in the stability literature.
BibTeX
@inproceedings{lei2026stability,
  author = {Qianqian Lei and Soham Bonnerjee and Yuefeng Han and Wei Biao Wu},
  title = {{Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite $L\_p$ Moments}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=SGTLVjx3MN},
}

Loading related content...

Figure