Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite $L_p$ Moments
For machine learning theorists, this work significantly weakens the standard assumptions required for stability-based generalization guarantees, making them applicable to heavy-tailed or unbounded loss settings.
This paper develops sharp high-probability generalization bounds for learning algorithms under only finite $L_p$ moment conditions, extending stability-based analysis beyond boundedness or sub-Gaussian assumptions. The results cover empirical risk minimization, transductive regression, and meta-learning.
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.