The Empirical Mean is Minimax Optimal for Local Glivenko-Cantelli

Doron Cohen, Aryeh Kontorovich, Roi Weiss
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:11173-11184, 2025.

Abstract

We revisit the recently introduced Local Glivenko-Cantelli setting, which studies distribution-dependent uniform convergence rates of the Empirical Mean Estimator (EME). In this work, we investigate generalizations of this setting where arbitrary estimators are allowed rather than just the EME. Can a strictly larger class of measures be learned? Can better risk decay rates be obtained? We provide exhaustive answers to these questions—which are both negative, provided the learner is barred from exploiting some infinite-dimensional pathologies. On the other hand, allowing such exploits does lead to a strictly larger class of learnable measures.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-cohen25b, title = {The Empirical Mean is Minimax Optimal for Local Glivenko-Cantelli}, author = {Cohen, Doron and Kontorovich, Aryeh and Weiss, Roi}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {11173--11184}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/cohen25b/cohen25b.pdf}, url = {https://proceedings.mlr.press/v267/cohen25b.html}, abstract = {We revisit the recently introduced Local Glivenko-Cantelli setting, which studies distribution-dependent uniform convergence rates of the Empirical Mean Estimator (EME). In this work, we investigate generalizations of this setting where arbitrary estimators are allowed rather than just the EME. Can a strictly larger class of measures be learned? Can better risk decay rates be obtained? We provide exhaustive answers to these questions—which are both negative, provided the learner is barred from exploiting some infinite-dimensional pathologies. On the other hand, allowing such exploits does lead to a strictly larger class of learnable measures.} }
Endnote
%0 Conference Paper %T The Empirical Mean is Minimax Optimal for Local Glivenko-Cantelli %A Doron Cohen %A Aryeh Kontorovich %A Roi Weiss %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-cohen25b %I PMLR %P 11173--11184 %U https://proceedings.mlr.press/v267/cohen25b.html %V 267 %X We revisit the recently introduced Local Glivenko-Cantelli setting, which studies distribution-dependent uniform convergence rates of the Empirical Mean Estimator (EME). In this work, we investigate generalizations of this setting where arbitrary estimators are allowed rather than just the EME. Can a strictly larger class of measures be learned? Can better risk decay rates be obtained? We provide exhaustive answers to these questions—which are both negative, provided the learner is barred from exploiting some infinite-dimensional pathologies. On the other hand, allowing such exploits does lead to a strictly larger class of learnable measures.
APA
Cohen, D., Kontorovich, A. & Weiss, R.. (2025). The Empirical Mean is Minimax Optimal for Local Glivenko-Cantelli. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:11173-11184 Available from https://proceedings.mlr.press/v267/cohen25b.html.

Related Material