Abstract
Estimating the common mean of Gaussian variables with unknown, heteroskedastic variances is a fundamental challenge in robust statistics. This paper introduces a "balance-finding" algorithm that achieves near-optimal error rates by requiring candidate means to satisfy a symmetry condition. This approach resolves an open problem in the "Subset-of-Signals" model, demonstrating that vanishing error is achievable even when the number of high-quality samples $m$ is as small as $n^{1/4}$, significantly improving upon the previous $n^{1/2}$ threshold.
Introduction
In standard statistical inference, data is often assumed to be independent and identically distributed (i.i.d.). However, many real-world applications involve data from heterogeneous sources—such as different sensors or clinical sites—where some sources are highly precise and others are extremely noisy. When the variances of these sources are unknown, traditional estimators struggle. The empirical mean is highly sensitive to high-variance outliers, while the median, though robust, fails to leverage small clusters of high-precision data.
This paper addresses the Subset-of-Signals model: given $n$ samples where an unknown subset of $m$ samples has variance $\le 1$ (and the remainder have arbitrary, unknown variances), the goal is to estimate the common mean with minimal error.
The Balanced Modal Estimator
The core innovation of this work is the Balanced Modal Estimator. While traditional modal estimators seek a window of fixed width containing the maximum number of points, they are known to be suboptimal. The authors introduce a "balance" condition: a candidate mean $\hat{\mu}$ is considered valid only if the number of points in the interval $[\hat{\mu}-w, \hat{\mu}]$ approximately equals the number in $[\hat{\mu}, \hat{\mu}+w]$.
By checking for symmetry (balance) rather than just density, the algorithm transforms a quadratic signal (the peak of the density) into a linear signal (the derivative of the density). This shift allows for much higher precision. Since the optimal window width $w$ is unknown, the algorithm employs a sweep-line approach to test for balance across multiple scales and shifts, intersecting valid intervals to produce a final estimate.
Theoretical Performance and the $n^{1/4}$ Barrier
The proposed algorithm achieves near-optimal error rates that match known lower bounds up to logarithmic factors. Specifically, it achieves an error of $\tilde{O}((n/m^4)^{1/6})$ for large $m$ and $\tilde{O}((n/m^4)^{1/2})$ for small $m$.
As shown in Figure 1, the "balance-finding" approach significantly outperforms previous state-of-the-art methods. While prior work by Pensia, Jog, and Loh (2019) required $m \approx \sqrt{n}$ to achieve a vanishing error (error $< 1$), this work demonstrates that vanishing error is possible even when $m$ is as small as $n^{1/4}$.
Key Insights
- Linear Signal Detection: Checking for balance provides a stronger signal than counting points, enabling the detection of the true mean with higher precision.
- Scale Invariance: The algorithm automatically identifies the correct scale $w$ by examining gaps between points, ensuring robustness without prior knowledge of the "good" samples' variances.
- Multi-dimensional Advantage: In two or more dimensions, the shared variance across dimensions allows one dimension to act as a proxy for filtering noise in another. This enables the algorithm to reach "known-variance" error rates even for $d=2$.
Conclusion
This work provides a near-optimal solution to the heteroskedastic mean estimation problem under the Subset-of-Signals model. While the current proofs rely on Gaussian assumptions and the parameter-free version of the algorithm has high computational complexity ($\tilde{O}(n^6)$), the underlying intuition of balance-finding offers a promising path for future research in heteroskedastic regression and covariance estimation.
Summary updated