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

• URL: http://arxiv.org/abs/2606.06855v1
• Date: Fri, 05 Jun 2026 02:59:49 GMT
• Title: Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite $L_p$ Moments
• Abstract summary: We develop a stability-based framework that requires only a finite $L_p$ moment condition.<n>We derive sharp high-probability generalization bounds across a range of learning paradigms.
• Score: 3.5932002706017556
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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.

Related papers

• The Price of Robustness: Stable Classifiers Need Overparameterization [17.335490896384265]
  We establish a generalization bound for finite function classes that improves inversely with class stability.<n>We derive as a corollary a law of robustness for classification that extends the results of Bubeck and Sellke.<n>Experiments support our theory, while traditional norm-based measures remain largely uninformative.
  arXiv  Detail & Related papers  (2026-03-03T09:47:06Z)
• Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Margins [31.581870065866568]
  We study safe online reinforcement learning in Constrained Markov Decision Processes (CMDPs) under strong regret and violation metrics.<n>Existing primal-dual methods that achieve sublinear strong reward regret incur growing strong constraint violation or are restricted to average-iterate convergence due to inherent oscillations.<n>We propose the Flexible safety Domain Optimization via Margin-regularized Exploration (FlexDOME) algorithm, the first to provably achieve near-constant $tildeO(1)$ strong constraint violation alongside sublinear strong regret and non-asymptotic last-iterate convergence.
  arXiv  Detail & Related papers  (2026-02-11T14:54:26Z)
• A Robustness Analysis of Blind Source Separation [91.3755431537592]
  Blind source separation (BSS) aims to recover an unobserved signal from its mixture $X=f(S)$ under the condition that the transformation $f$ is invertible but unknown. We present a general framework for analysing such violations and quantifying their impact on the blind recovery of $S$ from $X$. We show that a generic BSS-solution in response to general deviations from its defining structural assumptions can be profitably analysed in the form of explicit continuity guarantees.
  arXiv  Detail & Related papers  (2023-03-17T16:30:51Z)
• Stability and Generalization for Markov Chain Stochastic Gradient Methods [49.981789906200035]
  We provide a comprehensive generalization analysis of MC-SGMs for both minimization and minimax problems. We establish the optimal excess population risk bounds for both smooth and non-smooth cases. We develop the first nearly optimal convergence rates for convex-concave problems both in expectation and with high probability.
  arXiv  Detail & Related papers  (2022-09-16T15:42:51Z)
• Boosting the Confidence of Generalization for $L_2$-Stable Randomized Learning Algorithms [41.082982732100696]
  We show that a properly designed subbagging process leads to near-tight exponential generalization bounds over both data and algorithm. We further derive generic results to improve high-probability generalization bounds for convex or non-tight problems with natural decaying learning rates.
  arXiv  Detail & Related papers  (2022-06-08T12:14:01Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  Policy gradient (PG) is one of the most popular reinforcement learning (RL) problems. "vanilla" theoretical understanding of PG trajectory is one of the most popular methods for solving RL problems.
  arXiv  Detail & Related papers  (2021-07-23T19:38:17Z)
• Toward Better Generalization Bounds with Locally Elastic Stability [41.7030651617752]
  We argue that locally elastic stability implies tighter generalization bounds than those derived based on uniform stability. We revisit the examples of bounded support vector machines, regularized least square regressions, and gradient descent.
  arXiv  Detail & Related papers  (2020-10-27T02:04:53Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
  arXiv  Detail & Related papers  (2020-08-20T03:48:14Z)
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent [55.85456985750134]
  We introduce a new stability measure called on-average model stability, for which we develop novel bounds controlled by the risks of SGD iterates. This yields generalization bounds depending on the behavior of the best model, and leads to the first-ever-known fast bounds in the low-noise setting. To our best knowledge, this gives the firstever-known stability and generalization for SGD with even non-differentiable loss functions.
  arXiv  Detail & Related papers  (2020-06-15T06:30:19Z)
• Distributional Robustness and Regularization in Reinforcement Learning [62.23012916708608]
  We introduce a new regularizer for empirical value functions and show that it lower bounds the Wasserstein distributionally robust value function. It suggests using regularization as a practical tool for dealing with $textitexternal uncertainty$ in reinforcement learning.
  arXiv  Detail & Related papers  (2020-03-05T19:56:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.