Lune

ICML2025Top-tier venue

The Empirical Mean is Minimax Optimal for Local Glivenko-Cantelli

Doron Cohen, Aryeh Kontorovich, Roi Weiss

Abstract

We revisit the recently introduced Local Glivenko-Cantelli setting, which studies distributiondependent 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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Improved Distribution Estimation in ℓ∞\ell_\inftyDoron Cohen, Aryeh Kontorovich, Yonatan LivshitzICML 2026

Builds on1

  1. Outlier Robust Mean Estimation with Subgaussian Rates via StabilityIlias Diakonikolas, Daniel M. Kane, Ankit PensiaNeurIPS 2020 · 76 citations

Related papers

  1. Towards Problem-dependent Optimal Learning RatesYunbei Xu, Assaf ZeeviNeurIPS 2020 · 4 citations
  2. Supervised Learning with General Risk FunctionalsLiu Leqi, Audrey Huang, Zachary C. Lipton, Kamyar AzizzadenesheliICML 2022 · 7 citations
  3. Quantifying the Empirical Wasserstein Distance to a Set of Measures: Beating the Curse of DimensionalityNian Si, Jose H. Blanchet, Soumyadip Ghosh, Mark S. SquillanteNeurIPS 2020 · 16 citations
  4. Nonparametric Density Estimation under Distribution DriftAlessio Mazzetto, Eli UpfalICML 2023 · 5 citations
  5. Marginal-Nonuniform PAC LearnabilitySteve Hanneke, Shay Moran, Maximilian ThiessenNeurIPS 2025
Dusk over the sea between two cliffs drawn in fine vertical lines