Abstract
We consider the problem of estimating the common mean of independently sampled data, where samples are drawn in a possibly non-identical manner from symmetric, unimodal distributions with a common mean. This generalizes the setting of Gaussian mixture modeling, as the number of distinct mixture components may diverge with the number of observations. We propose an estimator that adapts to the level of heterogeneity in the data, achieving near-optimality in both the i.i.d. setting and heterogeneous settings where the fraction of "low-noise" points is as small as $\frac{\log n}{n}$. Our estimator is a hybrid of the modal interval, shorth, and median estimators from classical statistics; however, the key technical contributions rely on novel empirical process theory results derived for independent but non-i.i.d. data. In the multivariate setting, we generalize our theory to mean estimation for mixtures of radially symmetric distributions and derive minimax lower bounds on the expected error of any estimator agnostic to individual data scales. Finally, we describe an extension of our estimators applicable to linear regression and present computationally feasible versions that run in polynomial time.
Introduction
Most classical statistical frameworks rely on the assumption that data is Independent and Identically Distributed (i.i.d.). However, in modern applications such as crowdsourcing, sensor networks, or multi-center clinical trials, this assumption frequently fails. For instance, a network of 100 sensors may measure the same physical constant, but while one sensor is high-precision, others may be cheap, poorly calibrated, or malfunctioning. This creates a scenario of "entangled single-sample distributions": each data point $X_i$ comes from a different distribution $P_i$, yet they all share a common parameter of interest, $\mu^*$.
The challenge lies in the fact that the observer does not know which samples are reliable and which are noise. Standard tools like the sample mean are highly sensitive to high-variance outliers, while the sample median, though robust, often fails to achieve optimal convergence rates when the noise has specific structures. This paper introduces a robust hybrid estimator designed to navigate these heterogeneous environments.
The Hybrid Estimator Approach
The proposed solution bridges the gap between "local" and "global" statistical methods by combining three classical tools into a single robust framework:
- The Modal Interval and Shorth: These are local estimators. The $r$-modal interval identifies the center of the interval of length $r$ containing the most data points, while the "shorth" identifies the center of the shortest interval containing a specific number of points ($k$). These methods excel at ignoring heavy-tailed noise but can be unstable in isolation.
- The $k$-median: This serves as a global screening step. It identifies a "safe zone" where the true mean is statistically likely to reside.
- The Hybrid Mechanism: The algorithm calculates a shorth estimate and then projects it onto the median-based safe zone. This allows the estimator to utilize the precision of the shorth while using the median as a safeguard to prevent the estimate from being pulled toward random clusters of noise.
To support this approach, the authors developed new empirical process theory specifically for independent but non-identical data, providing rigorous guarantees that were previously only available for i.i.d. settings.
Performance in Heterogeneous Regimes
The researchers evaluated the estimator using synthetic datasets designed to simulate various levels of heterogeneity:
- i.i.d. Gaussian: The baseline clean scenario.
- Quadratic Variance: Where the variance of the $i$-th sample grows as $i^2$.
- $\alpha$-mixture distributions: A challenging regime where only a tiny fraction of points (roughly $\log n$) are low-noise, while the rest have variances that grow as a power of $n$ ($n^{2\alpha}$).
A key insight from these tests is the "phase transition" in the modal estimator. When noise in the "bad" samples grows sufficiently fast ($\alpha \geq 1$), the modal estimator actually performs better. The noise becomes so spread out that it effectively disappears into the background, allowing the few "clean" points to emerge as a distinct, sharp peak. The hybrid estimator adapts to these levels of heterogeneity without requiring prior knowledge of the noise scales.
Multivariate and Regression Extensions
The theory extends beyond simple mean estimation into higher dimensions and regression analysis:
- High-Dimensional Geometry: In multivariate settings ($d > 1$), the authors demonstrate that estimators agnostic to individual variances are limited by a rate of $n^{-1/d}$. Their hybrid estimator is shown to hit this minimax lower bound. To ensure practical utility, they provide a version that runs in $O(n^2 d)$ time, avoiding the NP-hardness usually associated with finding the "shortest gap" in high dimensions.
- Linear Regression: The methodology is adapted into a "modal interval regression estimator." This allows for the recovery of the true parameter $\beta^*$ even when error terms are non-i.i.d. and heavy-tailed, provided the design matrix meets certain properties.
Conclusion and Future Directions
This work provides a robust framework for finding signal in highly inconsistent data, proving that near-optimality is possible even when the vast majority of data is noise. However, some limitations remain. The current theory relies on the assumption that distributions are symmetric and unimodal. Future work may explore relaxations of these conditions, such as log-concavity or general asymmetry. Additionally, in the regression context, selecting the optimal interval radius $r$ remains a challenge; the authors suggest that adapting Lepski’s method could provide a path forward for automated calibration.
Summary updated