Concentration in unbounded metric spaces and algorithmic stability
arXiv:1309.1007
Abstract
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.
References in corpus (3)
Cited by in corpus (15)
- Convergence and Concentration of Empirical Measures under Wasserstein Distance in Unbounded Functional Spaces
- Some Theoretical Insights into Wasserstein GANs
- Non-Stationary Bandits with Habituation and Recovery Dynamics
- Comparing a Large Number of Multivariate Distributions
- Estimating covariance and precision matrices along subspaces
- Convergence Analysis of Gradient EM for Multi-component Gaussian Mixture
- A Mathematical Framework for Learning Probability Distributions
- Convex and Non-convex Approaches for Statistical Inference with Class-Conditional Noisy Labels
- Topologically penalized regression on manifolds
- Sharper convergence bounds of Monte Carlo Rademacher Averages through Self-Bounding functions
- Chernoff bounds for branching random walks
- A Rademacher Complexity Based Method fo rControlling Power and Confidence Level in Adaptive Statistical Analysis
- Some Hoeffding- and Bernstein-type Concentration Inequalities
- Deviation bound for non-causal machine learning
- Distribution-dependent concentration inequalities for tighter generalization bounds