Variance estimation in compound decision theory under boundedness

Subhodh Kotekal

Introduction

In high-dimensional data analysis, researchers frequently encounter scenarios where they have many parameters but only a single observation for each. In such settings, estimating the underlying noise variance is notoriously difficult. This paper investigates the fundamental limits of variance estimation within the normal means model, proving that if the underlying signals are bounded, the best possible error rate for estimating variance is $\left(\frac{\log \log n}{\log n}\right)^2$. To achieve this limit, the author introduces a novel estimator that leverages the mathematical properties of "cumulants."

The Challenge of the Normal Means Model

Consider analyzing gene expression data for thousands of genes ($n$), where each gene yields exactly one measurement. Statistically, this measurement is assumed to be the "true" expression level (the mean) plus some random Gaussian noise with an unknown variance $\sigma^2$.

In classical statistics, estimating noise level typically requires multiple measurements of the same parameter. However, in modern large-scale parallel experiments—such as microarrays—researchers often only get one shot per parameter. This setup is known as the normal means model in compound decision theory.

If no assumptions are made about the true expression levels, it is mathematically impossible to distinguish between a highly variable signal and high-volume noise. However, if we assume the signals are bounded (e.g., they fall within a known, finite range), the variance becomes identifiable. The central question this paper addresses is: What is the fundamental limit of how accurately we can estimate this variance, and how do we build an algorithm to reach it?

Methodology: Cumulants and Variational Representation

Because this is a purely theoretical paper, the results are established through rigorous mathematical proofs rather than empirical datasets. The author departs from standard "moment-based" estimators, which can be highly unstable, and instead utilizes cumulants.

  1. The Cumulant Advantage: Cumulants are closely related to statistical moments but possess a highly useful property: the cumulant of a sum of independent variables is simply the sum of their individual cumulants. Because Gaussian noise has only two non-zero cumulants (the mean and the variance), the higher-order cumulants of the observed data are identical to the higher-order cumulants of the underlying signal.
  2. Variational Representation: The paper introduces a "variational" framework for variance. It proves that the true signal variance can be expressed as the supremum (the highest possible value) of a specific function of the data's cumulants, provided the signal strictly adheres to its bounds.
  3. The Rate-Optimal Estimator: The proposed algorithm estimates $O\left(\frac{\log n}{\log \log n}\right)$ cumulants from the data and plugs them into this variational formula. It also incorporates a truncation step to handle cases where the noise is extremely small, preventing the estimator from being skewed by rare outliers.

Key Insights and Theoretical Results

  • Minimax Optimality and the "Slow" Reality: The paper establishes the sharp minimax rate for variance estimation under square error as $\Theta\left( \left( \frac{\log \log n}{\log n} \right)^2 \right)$. This logarithmic rate is remarkably slow compared to the $1/n$ rates typical in simpler parametric problems, confirming that variance estimation in this setting is inherently "hard" and requires massive amounts of data to achieve high precision.
  • Gaussianity is Essential: A surprising theoretical insight is that knowing the noise is strictly Gaussian is mandatory. If one only assumes the noise is "sub-Gaussian" (a broader category), consistent variance estimation becomes impossible. The specific "shape" of the Gaussian distribution is required to mathematically separate noise from the signal.
  • Moment Matching for Lower Bounds: To prove the theoretical speed limit (the lower bound), the author uses Le Cam’s two-point method and a moment-matching construction. The paper demonstrates how to construct two different signal distributions that share a large number of moments—making them almost indistinguishable—yet result from different noise variances.
  • Comparison to Regression: The paper highlights that this problem is strictly harder than variance estimation in high-dimensional linear regression. In regression, the randomness of the design matrix provides extra structural information that is entirely absent in the sequence model studied here.

Limitations and Future Directions

While the paper resolves a fundamental theoretical question, it leaves several avenues open for future research:

  • Noise Sensitivity: The proposed estimator is finely tuned for Gaussian noise. Extending this framework to other noise distributions (such as Poisson or Student's t-distributions) while maintaining minimax optimality remains an open challenge.
  • Computational Complexity: While the paper successfully establishes the statistical rate, calculating the high-order Bell polynomials required for cumulant estimation can become computationally intensive as $n$ grows large.
  • The NPMLE Connection: A major open question is whether the Nonparametric Maximum Likelihood Estimator (NPMLE)—a highly popular "black box" tool in empirical Bayes methods—automatically achieves this optimal rate without requiring the explicit cumulant mathematics developed in this work.

Summary updated

Abstract

The normal means model is often studied under the assumption of a known variance. However, ignorance of the variance is a frequent issue in applications and basic theoretical questions still remain open in this setting. This article establishes that the sharp minimax rate of variance estimation in square error is $(\frac{\log\log n}{\log n})^2$ under arguably the most mild assumption imposed for identifiability: bounded means. The rate-optimal estimator proposed in this article achieves the optimal rate by estimating $O\left(\frac{\log n}{\log\log n}\right)$ cumulants and leveraging a variational representation of the noise variance in terms of the cumulants of the data distribution. The minimax lower bound involves a moment matching construction.
BibTeX
@inproceedings{kotekal2024variance,
  author = {Subhodh Kotekal},
  title = {{Variance estimation in compound decision theory under boundedness}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=HvCppnDykt},
}
Figure