mlsanityData to 7 Oct 2026

Concentration in unbounded metric spaces and algorithmic stability

arXiv 1309.1007 ↗First posted 4 Sep 2013math.PR cs.LG math.FAcited by 21

Not on the map. Why?

Abstract (arXiv)

We prove an extension of McDiarmid's inequality for metric spaces with unbounded diameter. To this end, we introduce the notion of the em subgaussian diameter, which is a distribution-dependent refinement of the metric diameter. Our technique provides an alternative approach to that of Kutin and Niyogi's method of weakly difference-bounded functions, and yields nontrivial, dimension-free results in some interesting cases where the former does not. As an application, we give apparently the first generalization bound in the algorithmic stability setting that holds for unbounded loss functions. We furthermore extend our concentration inequality to strongly mixing processes.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). First posted on arXiv 4 Sep 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 4; 2023: 2; 2024: 1; 2025: 3; 2026: 3.

21 papers.

Sort:

  1. 2021Transfer Learning under High-dimensional Generalized Linear Modelscited by 69
  2. 2024Towards Theoretical Understandings of Self-Consuming Generative Modelscited by 28
  3. 2022Scaling ResNets in the Large-depth Regimecited by 18
  4. 2022Lifting Weak Supervision To Structured Predictioncited by 10
  5. 2021The computational asymptotics of Gaussian variational inference and the Laplace approximationcited by 8
  6. 2022Shedding a PAC-Bayesian Light on Adaptive Sliced-Wasserstein Distancescited by 7
  7. 2022A Mathematical Framework for Learning Probability Distributionscited by 7
  8. 2021Matrix Completion with Model-free Weightingcited by 6
  9. 2021Regret Analysis of Learning-Based MPC with Partially-Unknown Cost Functioncited by 5
  10. 2021Topologically penalized regression on manifoldscited by 5
  11. 2021Binary classification with corrupted labelscited by 4
  12. 2023Stability of Random Forests and Coverage of Random-Forest Prediction Intervalscited by 4
9 more
  1. 2025Distribution-dependent Generalization Bounds for Tuning Linear Regression Across Taskscited by 2
  2. 2021Some Hoeffding- and Bernstein-type Concentration Inequalitiescited by 1
  3. 2023Tight Non-asymptotic Inference via Sub-Gaussian Intrinsic Moment Normcited by 1
  4. 2025A Mathematical Framework for AI-Human Integration in Workcited by 1
  5. 2026Generalization Guarantees on Data-Driven Tuning of Gradient Descent with Langevin Updatescited by 1
  6. 2026Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite Lp Momentscited by 1
  7. 2026Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithmscited by 1
  8. 2021Making the most of your day: online learning for optimal allocation of timecited by 0
  9. 2025Concentration Inequalities for Stochastic Optimization of Unbounded Objective Functions with Application to Denoising Score Matchingcited by 0