# Concentration in unbounded metric spaces and algorithmic stability

arXiv: https://arxiv.org/abs/1309.1007 · HTML: https://mlsanity.com/paper/1309.1007/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Sep 2013.

## Built on by (most cited first, 22 of 22)

- [Transfer Learning under High-dimensional Generalized Linear Models](https://mlsanity.com/paper/2105.14328/) (2021)
- [Towards Theoretical Understandings of Self-Consuming Generative Models](https://mlsanity.com/paper/2402.11778/) (2024)
- [Scaling ResNets in the Large-depth Regime](https://mlsanity.com/paper/2206.06929/) (2022)
- [Lifting Weak Supervision To Structured Prediction](https://mlsanity.com/paper/2211.13375/) (2022)
- [The computational asymptotics of Gaussian variational inference and the Laplace approximation](https://mlsanity.com/paper/2104.05886/) (2021)
- [Shedding a PAC-Bayesian Light on Adaptive Sliced-Wasserstein Distances](https://mlsanity.com/paper/2206.03230/) (2022)
- [A Mathematical Framework for Learning Probability Distributions](https://mlsanity.com/paper/2212.11481/) (2022)
- [Matrix Completion with Model-free Weighting](https://mlsanity.com/paper/2106.05850/) (2021)
- [Regret Analysis of Learning-Based MPC with Partially-Unknown Cost Function](https://mlsanity.com/paper/2108.02307/) (2021)
- [Topologically penalized regression on manifolds](https://mlsanity.com/paper/2110.13749/) (2021)
- [Binary classification with corrupted labels](https://mlsanity.com/paper/2106.09136/) (2021)
- [Stability of Random Forests and Coverage of Random-Forest Prediction Intervals](https://mlsanity.com/paper/2310.18814/) (2023)
- [A Mathematical Framework for AI-Human Integration in Work](https://mlsanity.com/paper/2505.23432/) (2025)
- [Distribution-dependent Generalization Bounds for Tuning Linear Regression Across Tasks](https://mlsanity.com/paper/2507.05084/) (2025)
- [Some Hoeffding- and Bernstein-type Concentration Inequalities](https://mlsanity.com/paper/2102.06304/) (2021)
- [Tight Non-asymptotic Inference via Sub-Gaussian Intrinsic Moment Norm](https://mlsanity.com/paper/2303.07287/) (2023)
- [Generalization Guarantees on Data-Driven Tuning of Gradient Descent with Langevin Updates](https://mlsanity.com/paper/2604.13130/) (2026)
- [Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite Lp Moments](https://mlsanity.com/paper/2606.06855/) (2026)
- [Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms](https://mlsanity.com/paper/2608.09870/) (2026)
- [Making the most of your day: online learning for optimal allocation of time](https://mlsanity.com/paper/2102.08087/) (2021)
- [Concentration Inequalities for Stochastic Optimization of Unbounded Objective Functions with Application to Denoising Score Matching](https://mlsanity.com/paper/2502.08628/) (2025)
- [A Generalized McDiarmid Inequality: Sample Reuse and Non-Uniform Unbounded Differences](https://mlsanity.com/paper/2610.17159/) (2026)

## 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.