# Entangled Mean Estimation in High-Dimensions

arXiv: https://arxiv.org/abs/2501.05425 · HTML: https://mlsanity.com/paper/2501.05425/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 69 references that are in the map.
- First posted on arXiv 9 Jan 2025.

## Builds on (most cited first, 19 of 19)

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [Challenges of Big Data Analysis](https://mlsanity.com/paper/1308.1479/) (2013)
- [Meta-learning for mixed linear regression](https://mlsanity.com/paper/2002.08936/) (2020)
- [A Survey on Heterogeneous Federated Learning](https://mlsanity.com/paper/2210.04505/) (2022)
- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [List Decodable Mean Estimation in Nearly Linear Time](https://mlsanity.com/paper/2005.09796/) (2020)
- [List-Decodable Mean Estimation via Iterative Multi-Filtering](https://mlsanity.com/paper/2006.10715/) (2020)
- [Optimal estimation of the null distribution in large-scale inference](https://mlsanity.com/paper/2401.06350/) (2024)
- [Learning Entangled Single-Sample Distributions via Iterative Trimming](https://mlsanity.com/paper/2004.09563/) (2020)
- [On Mean Estimation for Heteroscedastic Random Variables](https://mlsanity.com/paper/2010.11537/) (2020)
- [Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances](https://mlsanity.com/paper/2312.02417/) (2023)
- [Non-asymptotic bounds for percentiles of independent non-identical random variables](https://mlsanity.com/paper/1808.07997/) (2018)
- [Estimating location parameters in entangled single-sample distributions](https://mlsanity.com/paper/1907.03087/) (2019)
- [Learning Entangled Single-Sample Gaussians in the Subset-of-Signals Model](https://mlsanity.com/paper/2007.05557/) (2020)

## Built on by (most cited first, 3 of 3)

- [Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination](https://mlsanity.com/paper/2502.14772/) (2025)
- [Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms](https://mlsanity.com/paper/2601.05157/) (2026)
- [High-Dimensional Gaussian Mean Estimation under Realizable Contamination](https://mlsanity.com/paper/2603.16798/) (2026)

## Abstract (arXiv)

We study the task of high-dimensional entangled mean estimation in the subset-of-signals model. Specifically, given N independent random points x1,ldots,xN in ℝD and a parameter α ∈ (0, 1) such that each xi is drawn from a Gaussian with mean μ and unknown covariance, and an unknown α-fraction of the points have identity-bounded covariances, the goal is to estimate the common mean μ. The one-dimensional version of this task has received significant attention in theoretical computer science and statistics over the past decades. Recent work [LY20; CV24] has given near-optimal upper and lower bounds for the one-dimensional setting. On the other hand, our understanding of even the information-theoretic aspects of the multivariate setting has remained limited. In this work, we design a computationally efficient algorithm achieving an information-theoretically near-optimal error. Specifically, we show that the optimal error (up to polylogarithmic factors) is f(α,N) + √D/(α N), where the term f(α,N) is the error of the one-dimensional problem and the second term is the sub-Gaussian error rate. Our algorithmic approach employs an iterative refinement strategy, whereby we progressively learn more accurate approximations hat μ to μ. This is achieved via a novel rejection sampling procedure that removes points significantly deviating from hat μ, as an attempt to filter out unusually noisy samples. A complication that arises is that rejection sampling introduces bias in the distribution of the remaining points. To address this issue, we perform a careful analysis of the bias, develop an iterative dimension-reduction strategy, and employ a novel subroutine inspired by list-decodable learning that leverages the one-dimensional result.