Learning Entangled Single-Sample Distributions via Iterative Trimming

Hui Yuan, Yingyu Liang

Abstract

In the setting of entangled single-sample distributions, the goal is to estimate some common parameter shared by a family of distributions, given one single sample from each distribution. We study mean estimation and linear regression under general conditions, and analyze a simple and computationally efficient method based on iteratively trimming samples and re-estimating the parameter on the trimmed sample set. We show that the method in logarithmic iterations outputs an estimation whose error only depends on the noise level of the $\lceil \alpha n \rceil$-th noisiest data point where $\alpha$ is a constant and $n$ is the sample size. This means it can tolerate a constant fraction of high-noise points. These are the first such results for the method under our general conditions. It also justifies the wide application and empirical success of iterative trimming in practice. Our theoretical results are complemented by experiments on synthetic data.

Introduction

Classical statistical learning often relies on the assumption that data is independent and identically distributed (i.i.d.). However, real-world scenarios frequently present heterogeneous data where each sample originates from a distinct environment or distribution. For instance, sensors in a network might share a common target parameter but operate under varying noise levels due to environmental factors. This paper addresses the "entangled single-sample distribution" setting, where $n$ data points are drawn from $n$ different distributions sharing a common mean ($\mu$) or regression coefficient ($\beta$), but possessing unknown and potentially disparate variances.

The primary challenge in this setting is twofold: preventing high-noise "outliers" from biasing the estimate and maintaining computational efficiency. While trimmed estimators are robust, they often involve NP-hard optimization problems. This work provides a theoretical foundation for Iterative Trimming, a computationally efficient heuristic widely used in practice.

Methodology: Iterative Trimming

The authors analyze two primary algorithms based on the principle of iterative refinement:

  1. Iterative Trimmed Mean (ITM): For mean estimation, the algorithm begins with an initial empirical mean. It iteratively identifies the $\alpha n$ points closest to the current estimate (where $\alpha$ is a predefined fraction, e.g., 0.8) and updates the estimate using only these points until convergence.
  2. Iterative Trimmed Squares Minimization (ITSM): Applied to linear regression, this method identifies points with the smallest squared residuals relative to the current model and re-estimates the regression coefficients using Least Squares on that subset.

The paper proves that these algorithms converge in a logarithmic number of steps and run in nearly linear time, providing the first rigorous guarantees under general conditions without requiring strict symmetry or Gaussianity.

Experimental Evaluation

The theoretical guarantees were validated using synthetic datasets simulating various noise environments, including univariate and multivariate ($d=10$) mean estimation, and high-dimensional linear regression ($d=100$).

Figure 1: Average error of ITM vs. Oracle Mean (OM) in a univariate setting as sample size $n$ increases.

A key finding is the "Oracle Performance" of the iterative trimming method. As shown in Figure 1 and Figure 3, the error of the ITM algorithm closely tracks that of an "Oracle" estimator (OM)—an ideal estimator that knows exactly which points are low-noise and uses only those. This demonstrates the algorithm's effectiveness in autonomously identifying and discarding high-noise samples.

Figure 3: Average error of ITM vs. OM in a multivariate or lower-noise setting, showing consistent tracking of the oracle performance.

Discussion and Key Insights

The most significant theoretical insight is the Threshold Property: the final estimation error depends only on the noise level of the $\alpha n$-th noisiest point. This implies that as long as a constant fraction of the data is "good," the magnitude of noise in the "bad" fraction does not affect the final error bound.

Furthermore, the research breaks the symmetry requirement prevalent in previous literature. Iterative trimming remains effective under general conditions, provided the data distribution satisfies certain regularity requirements. While a statistical gap remains between these results and the absolute theoretical optimum (which might average noise across all good points), the iterative approach offers a practical, polynomial-time solution to a traditionally difficult problem.

Conclusion

This work bridges the gap between the empirical success of iterative trimming and its theoretical understanding. Future research may explore the "vanishing error" phenomenon observed in experiments and validate these findings on real-world heterogeneous datasets, such as those found in sensor networks or cross-domain computer vision.

Summary updated

Abstract

In the setting of entangled single-sample distributions, the goal is to estimate some common parameter shared by a family of distributions, given one \emph{single} sample from each distribution. We study mean estimation and linear regression under general conditions, and analyze a simple and computationally efficient method based on iteratively trimming samples and re-estimating the parameter on the trimmed sample set. We show that the method in logarithmic iterations outputs an estimation whose error only depends on the noise level of the $\lceil \alpha n \rceil$-th noisiest data point where $\alpha$ is a constant and $n$ is the sample size. This means it can tolerate a constant fraction of high-noise points. These are the first such results for the method under our general conditions. It also justifies the wide application and empirical success of iterative trimming in practice. Our theoretical results are complemented by experiments on synthetic data.
BibTeX
@inproceedings{yuan2020learning,
  author = {Hui Yuan and Yingyu Liang},
  title = {{Learning Entangled Single-Sample Distributions via Iterative Trimming}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=Yk8JhmKMyG},
}
Figure