Sharp uniform convergence bounds through empirical centralization
Cyrus Cousins,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) varianceand the function ranges, and the same dependence on the number of samples as existing SD bounds.To compute the SD bounds in practice, we develop tightly-concentratedMonte 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 practicaleven at small sample sizes.
