Research map / Learning theory and algorithms / Sample complexity
The Empirical Mean is Minimax Optimal for Local Glivenko-Cantelli
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that, for product Bernoulli distributions, the Local Glivenko-Cantelli class LGC is essentially the largest learnable family under decay and strong-symmetry restrictions, that the empirical mean estimator is near-minimax optimal, and that relaxing these restrictions allows a strictly larger learnable class.
Problem
Whether arbitrary estimators (beyond the empirical mean estimator) can learn a strictly larger class of product Bernoulli distributions under the local Glivenko-Cantelli setting, and whether they can achieve faster l-infinity risk decay than the EME.
Approach
Extends the local Glivenko-Cantelli analysis from the EME to arbitrary estimators: uses a sign-reflection (Rademacher) randomized construction and Borel-Cantelli arguments to show LGC is maximal under decay and strong symmetry, derives a minimax lower bound matching EME rates, and shows a test-then-switch estimator learns LGC plus constant sequences when those restrictions are dropped.
Key results
- Under decay and strong symmetry, any learnable family is contained in LGC, so the EME's LGC class is essentially maximal among learnable families.
- Minimax lower bound of the form 1 ∧ (c·sqrt(s/n) ∨ Q(t,s)·t/n) over P_{s,t}, matching the EME's rate up to log factors.
- Learnable family without decay/symmetry: LGC ∪ constant sequences is learnable via a sign-test-then-average estimator.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| allow arbitrary estimators instead of restricting to the empirical mean | decaying, strongly symmetric product-distribution families · Local Glivenko-Cantelli | expected sup-norm risk decay rate | No clear effect |
| add constant sequences to the EME-learnable family | dot-LGC · dot-LGC union constant sequences | learnability | Helped |
| allow distributions within c/sqrt(j) of 1/2 | product-distribution learning · Q = {p: |p[j] - 1/2| <= c/sqrt(j)} | learnability | Helped |
| use the simple average estimator instead of the EME | structured distributions · uniform, triangular, Beta(2,2), exponential, 1/n-scaled, and Gaussian | error | Helped |
Surprising findings
- Dropping decay and strong symmetry allows a strictly larger learnable class, including constant sequences (c,c,...) and sequences like those with |p_j - 1/2| <= c/sqrt(j).
Experimental setup
Metrics: expected sup-norm estimation error minimax risk
Baselines: Empirical Mean Estimator
Builds on: Local Glivenko-Cantelli (Cohen et al.) Fano method
Closest papers by meaning
- Learning discrete distributions with infinite support (NeurIPS 2020 · similarity 0.88)
- On the Variance, Admissibility, and Stability of Empirical Risk Minimization (NeurIPS 2023 · similarity 0.87)
- On the Asymptotic Distribution of the Minimum Empirical Risk (ICML 2024 · similarity 0.86)
- Robust Statistical Estimators with Bounded Empirical Sensitivity (NeurIPS 2026 · similarity 0.84)
- On the Consistency of Kernel Methods with Dependent Observations (ICML 2024 · similarity 0.84)
- Stability and Sharper Risk Bounds with Convergence Rate $\tilde{O}(1/n^2)$ (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.