Cyrus Cousins

Sharp uniform convergence bounds through empirical centralization

Sharp uniform convergence bounds through empirical centralization

Cyrus Cousins and Matteo Riondato


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.


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