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

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.

Machine-learning models often face data with rare but very large outliers, where standard theories can be too restrictive. We develop new mathematical tools showing that stable learning algorithms can still have meaningful performance guarantees under much weaker assumptions. These results help explain generalization in heavy-tailed settings across several learning problems, including standard, transductive, and meta learning.