Cyrus Cousins

Sharp uniform convergence bounds through empirical centralization

Sharp uniform convergence bounds through empirical centralization

Cyrus Cousins and Matteo Riondato

Abstract

We introduce the use of empirical centralization to derive novel practical, probabilistic, sample-dependent bounds to the Supremum Deviation (SD) of empirical means of functions in a family from their expectations. Our bounds have optimal dependence on the maximum (i.e., wimpy) variance and the function ranges, and the same dependence on the number of samples as existing SD bounds. To compute the bounds in practice, we develop novel tightly-concentrated Monte-Carlo estimators of the empirical Rademacher average of the empirically-centralized family, and we show novel concentration results for the empirical wimpy variance. Our experimental evaluation shows that our bounds greatly outperform non-centralized bounds and are extremely practical even at small sample sizes.

Keywords

Concentration of Measure ♦ Empirical Process Theory ♣ Uniform Convergence ♥ Rademacher Averages ♠ Statistical Learning Theory


Read the full paper

Get the code and supplement.



See the Poster