Efficient median of means estimator

Stanislav Minsker
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5925-5933, 2023.

Abstract

The goal of this note is to present a modification of the popular median of means estimator that achieves sub-Gaussian deviation bounds with nearly optimal constants under minimal assumptions on the underlying distribution. We build on a recent work on the topic and prove that desired guarantees can be attained under weaker requirements.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-minsker23a, title = {Efficient median of means estimator}, author = {Minsker, Stanislav}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {5925--5933}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/minsker23a/minsker23a.pdf}, url = {https://proceedings.mlr.press/v195/minsker23a.html}, abstract = {The goal of this note is to present a modification of the popular median of means estimator that achieves sub-Gaussian deviation bounds with nearly optimal constants under minimal assumptions on the underlying distribution. We build on a recent work on the topic and prove that desired guarantees can be attained under weaker requirements.} }
Endnote
%0 Conference Paper %T Efficient median of means estimator %A Stanislav Minsker %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-minsker23a %I PMLR %P 5925--5933 %U https://proceedings.mlr.press/v195/minsker23a.html %V 195 %X The goal of this note is to present a modification of the popular median of means estimator that achieves sub-Gaussian deviation bounds with nearly optimal constants under minimal assumptions on the underlying distribution. We build on a recent work on the topic and prove that desired guarantees can be attained under weaker requirements.
APA
Minsker, S.. (2023). Efficient median of means estimator. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:5925-5933 Available from https://proceedings.mlr.press/v195/minsker23a.html.

Related Material