Concentration in unbounded metric spaces and algorithmic stability. arXiv:1309.1007

We prove an extension of McDiarmid’s inequal-ity for metric spaces with unbounded diame-ter. To this end, we introduce the notion of the 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 non-trivial, dimension-free results in some interest-ing cases where the former does not. As an ap-plication, we give apparently the first generaliza-tion bound in the algorithmic stability setting that holds for unbounded loss functions. This yields a novel risk bound for some regularized metric re-gression algorithms. We give two extensions of the basic concentration result. The first enables one to replace the independence assumption by appropriate strong mixing. The second gener-alizes the subgaussian technique to other Orlicz norms. 1