Research map / Learning theory and algorithms / Sample complexity

Variance estimation in compound decision theory under boundedness

NeurIPS 2024 · Learning theory and algorithms › Sample complexity · approach: Optimal mean estimation and subsampling · 0 citations (OpenAlex)

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.

Establishes the sharp minimax rate (log log n / log n)^2 for estimating the noise variance in the normal means model under bounded means, via a cumulant-based variational estimator and a moment-matching lower bound.

Problem

Variance estimation in the compound normal means model (one observation per mean) when only the means are assumed bounded, which is the mildest identifiability condition; the sharp minimax rate was unknown.

Approach

Identify the noise variance as the largest cumulant-based value such that all putative moments of the symmetrized empirical mean distribution stay in [-1,1]; estimate O(log n / log log n) cumulants from the data and plug them into a truncated variational estimator, with a Gaussian-quadrature moment-matching lower bound.

Key results

• Upper bound: the cumulant-based truncated estimator attains E|σ̂²−σ²|² ≲ (log log n / log n)² over the bounded-means class (Theorem 1).
• Lower bound: inf over estimators sup over the parameter space of P(|σ̂²−σ²|² ≥ C(log log n/log n)²) ≥ c (Theorem 2), via moment matching with Gaussian quadrature priors supported on [-1,1].
• Noise agnosticism: consistent variance estimation is impossible if only sub-Gaussianity of the noise is assumed (Proposition 5).

Measured effects reported in the paper

Surprising findings

• Consistent variance estimation is impossible when the noise is only assumed sub-Gaussian, so exploiting Gaussian noise structure is necessary.
• A rate faster than 1/log n is achievable under bounded means, despite the intuition from Gaussian mixture results that the rate should be logarithmic.

Limitations

• Lower and upper bounds are stated up to universal constants and the estimator uses tuning parameters r and epsilon that depend on n and constants from the proofs.
• The cumulant estimator relies on Gaussian noise structure; noise-agnostic estimation is impossible under sub-Gaussianity alone.
• Analysis is for the compound (sequence) model with a known Gaussian family and bounded means in [-1,1]; the authors note the unbounded case is infinite-risk.

Experimental setup

Metrics: minimax risk (squared error)

Baselines: Butucea and Matias Fourier estimator Matias empirical MGF estimator Wu and Yang Lindsay's algorithm max-order-statistic estimator

Builds on: Tweedie's formula Kong and Valiant polynomial approximation for regression variance estimation Butucea and Matias deconvolution variance estimation Wu and Yang Gaussian mixture moment estimation Matias moment generating function estimator

Closest papers by meaning

• Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond $1+\alpha$ Moments (NeurIPS 2023 · similarity 0.86)
• Robust Statistical Estimators with Bounded Empirical Sensitivity (NeurIPS 2026 · similarity 0.84)
• The Bias-Variance Tradeoff in Data-Driven Optimization: A Local Misspecification Perspective (NeurIPS 2025 · similarity 0.83)
• Sub-Gaussian Confidence Intervals for Heavy-Tailed Data: Characterizing the Limits of Inference (NeurIPS 2026 · similarity 0.82)
• The Empirical Mean is Minimax Optimal for Local Glivenko-Cantelli (ICML 2025 · similarity 0.82)
• Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability (NeurIPS 2024 · similarity 0.82)