Concentration in unbounded metric spaces and algorithmic stability
This work addresses the problem of concentration inequalities in unbounded settings for researchers in machine learning theory, providing a novel tool for analyzing algorithmic stability with unbounded losses, though it is incremental in extending existing concentration methods.
The authors extended McDiarmid's inequality to unbounded metric spaces by introducing the subgaussian diameter, a distribution-dependent refinement, and applied it to derive the first generalization bound for algorithmic stability with unbounded loss functions, achieving dimension-free results in certain cases.
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.