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 under our general conditions with computationally efficient estimators. 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

Standard statistical estimation typically relies on the assumption of independent and identically distributed (i.e.d.) data. However, many modern applications involve heterogeneous data sources where each observation may come from a different distribution. For instance, a network of sensors might have varying levels of reliability, or a dataset might be composed of samples from diverse environments.

This paper addresses the problem of entangled single-sample distributions. In this setting, we have $n$ data points, each drawn from a distinct distribution. These distributions share a common parameter of interest (e.g., a mean vector or regression coefficients) but possess different, unknown noise levels. The objective is to recover the shared signal despite the presence of highly noisy or even adversarial samples.

Methodology: Iterative Trimming

The authors propose a computationally efficient framework based on iterative trimming. Unlike traditional trimmed estimators that require exhaustive searches over subsets, the iterative approach alternates between identifying "good" points and updating the parameter estimate.

Iterative Trimmed Mean (ITM)

For mean estimation, the algorithm follows these steps:

  1. Trim: Given the current mean estimate, select the $\alpha n$ samples closest to it.
  2. Update: Compute the new mean as the average of these selected samples.
  3. Iterate: Repeat until convergence (typically logarithmic in the initial error).

Iterative Trimmed Squares Minimization (ITSM)

For linear regression, the process is analogous:

  1. Trim: Identify the $\alpha n$ samples with the smallest squared residuals relative to the current coefficient estimate.
  2. Update: Perform standard least squares on this subset.
  3. Iterate: Repeat until the estimate stabilizes.

Experimental Results

The proposed methods were evaluated using synthetic datasets designed to simulate heterogeneous noise environments.

Mean Estimation

In mean estimation tasks, the ITM algorithm was compared against an "Oracle Mean" (OM) estimator—an imaginary baseline that knows the true variances and uses only the least noisy samples.

ITM performance compared to the Oracle Mean (OM) for mean estimation.

As shown in the figure above, the ITM estimator's error curve closely tracks that of the Oracle. This demonstrates the algorithm's ability to automatically identify and prioritize high-quality data points without prior knowledge of their noise levels.

Linear Regression

For high-dimensional regression ($d=100$), the ITSM algorithm was tested against standard Ordinary Least Squares (OLS).

Comparison of ITSM and OLS performance under heterogeneous noise.

The results indicate that ITSM significantly outperforms OLS in the presence of a constant fraction of high-noise points. While OLS is heavily influenced by outliers, ITSM effectively ignores them, resulting in a much lower average error that decreases as the total sample size $n$ increases.

Key Insights

  • Robustness to High Noise: The final estimation error is determined by the noise level of the $\alpha n$-th noisiest point. The algorithm is essentially immune to the specific noise levels of the remaining $(1-\alpha)n$ points.
  • Convergence Guarantees: Theory suggests convergence for $\alpha \ge 4/5$, though empirical results show success with $\alpha$ as low as $2/3$.
  • Computational Efficiency: The algorithms run in nearly linear time, providing a practical solution for large-scale heterogeneous datasets.

Conclusion

Iterative trimming provides a robust and efficient means of learning from entangled single-sample distributions. By bridging the gap between theoretical guarantees and practical performance, this work validates the use of iterative methods in heterogeneous environments and opens new avenues for robust statistical estimation.

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 under our general conditions with computationally efficient estimators. 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