Research map / Learning theory and algorithms / Kernels and regression theory

Algorithmic Stability Unleashed: Generalization Bounds with Unbounded Losses

ICML 2024 · Learning theory and algorithms › Kernels and regression theory · approach: Information-theoretic generalization bounds

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Extends algorithmic stability generalization bounds from bounded losses to unbounded losses with subweibull diameter, via new concentration inequalities for subweibull variables, and gives sqrt(n)-faster bounds.

Problem

High-probability generalization bounds from algorithmic stability typically require bounded losses, which excludes many important unbounded-loss settings.

Approach

Defines a subweibull diameter of a metric probability space and proves moment and probabilistic concentration inequalities for functions of independent subweibull variables, yielding totally Lipschitz stability generalization bounds for unbounded losses; a moment-based argument further improves the dominant term by sqrt(n).

Key results

• Generalization bound for totally Lipschitz stable algorithms with unbounded losses under subweibull diameter, recovering subgaussian (alpha=2) and subexponential (alpha=1) results as special cases.
• Sharper bound with dominant term gamma*Delta_alpha(Z) instead of gamma*Delta_alpha(Z)*sqrt(n), up to sqrt(n) faster than prior results.
• For regularized 1-NN regression, the bound improves the rate from O(1/sqrt(n)) (Kontorovich 2014) to O(1/n).

Limitations

• Analysis is for totally Lipschitz stable algorithms; stochastic gradient descent and other common algorithms are not shown to satisfy this stability.
• Results rely on a stronger stability notion and assume bounded subweibull diameter of the metric probability space.

Experimental setup

Metrics: generalization bound order in n subweibull diameter dependence

Baselines: Bousquet & Elisseeff (2002) uniform stability bound Kontorovich (2014) subgaussian diameter bound Maurer & Pontil (2021) subexponential diameter bound

Builds on: Kontorovich (2014) totally Lipschitz stability Maurer & Pontil (2021) subexponential diameter bounds Bousquet et al. (2020) sharper stability bounds Bousquet & Elisseeff (2002) uniform stability

Closest papers by meaning

• Stability and Sharper Risk Bounds with Convergence Rate $\tilde{O}(1/n^2)$ (NeurIPS 2025 · similarity 0.91)
• Certification-Enhanced Generalization Bounds (NeurIPS 2026 · similarity 0.90)
• Exactly Tight Information-theoretic Generalization Bounds via Binary Jensen-Shannon Divergence (ICML 2025 · similarity 0.89)
• Fantastic Generalization Measures are Nowhere to be Found (ICLR 2024 · similarity 0.89)
• Which Algorithms Have Tight Generalization Bounds? (NeurIPS 2025 · similarity 0.89)
• Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Power (ICLR 2025 · similarity 0.89)