Sharp uniform convergence bounds through empirical centralization
Cyrus Cousins, 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 SD bounds in practice, we develop 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.
BibTeX
@inproceedings{NEURIPS2020_ac457ba9,
author = {Cousins, Cyrus and Riondato, Matteo},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {15123--15132},
publisher = {Curran Associates, Inc.},
title = {Sharp uniform convergence bounds through empirical centralization},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/ac457ba972fb63b7994befc83f774746-Paper.pdf},
volume = {33},
year = {2020}
}