Empirical bounds for functions with weak interactions

Andreas Maurer, Massimiliano Pontil
Proceedings of the 31st Conference On Learning Theory, PMLR 75:987-1010, 2018.

Abstract

We provide sharp empirical estimates of expectation, variance and normal approximation for a class of statistics whose variation in any argument does not change too much when another argument is modified. Examples of such weak interactions are furnished by U- and V-statistics, Lipschitz L-statistics and various error functionals of $\ell_2$-regularized algorithms and Gibbs algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v75-maurer18a, title = {Empirical bounds for functions with weak interactions}, author = {Maurer, Andreas and Pontil, Massimiliano}, booktitle = {Proceedings of the 31st Conference On Learning Theory}, pages = {987--1010}, year = {2018}, editor = {Bubeck, Sébastien and Perchet, Vianney and Rigollet, Philippe}, volume = {75}, series = {Proceedings of Machine Learning Research}, month = {06--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v75/maurer18a/maurer18a.pdf}, url = {https://proceedings.mlr.press/v75/maurer18a.html}, abstract = {We provide sharp empirical estimates of expectation, variance and normal approximation for a class of statistics whose variation in any argument does not change too much when another argument is modified. Examples of such weak interactions are furnished by U- and V-statistics, Lipschitz L-statistics and various error functionals of $\ell_2$-regularized algorithms and Gibbs algorithms.} }
Endnote
%0 Conference Paper %T Empirical bounds for functions with weak interactions %A Andreas Maurer %A Massimiliano Pontil %B Proceedings of the 31st Conference On Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Sébastien Bubeck %E Vianney Perchet %E Philippe Rigollet %F pmlr-v75-maurer18a %I PMLR %P 987--1010 %U https://proceedings.mlr.press/v75/maurer18a.html %V 75 %X We provide sharp empirical estimates of expectation, variance and normal approximation for a class of statistics whose variation in any argument does not change too much when another argument is modified. Examples of such weak interactions are furnished by U- and V-statistics, Lipschitz L-statistics and various error functionals of $\ell_2$-regularized algorithms and Gibbs algorithms.
APA
Maurer, A. & Pontil, M.. (2018). Empirical bounds for functions with weak interactions. Proceedings of the 31st Conference On Learning Theory, in Proceedings of Machine Learning Research 75:987-1010 Available from https://proceedings.mlr.press/v75/maurer18a.html.

Related Material