arXiv:2602.20698v2 cs.LG

High-Dimensional Robust Mean Estimation from Doubly Corrupted and Heterogeneous Batches

Maryam Aliakbarpour, Vladimir Braverman, Yuhan Liu, Junze Yin

제출 2026-11-05

원문 초록

Modern data systems often require aggregating information from multiple sources: some might be entirely untrustworthy, while the remaining presumably reliable sources may still suffer from a small amount of corruption. We study robust mean estimation under this practical scenario, which is formulated through the double corruption model: samples are divided among $N$ users, each with $n$ samples. $\varepsilon$ fraction of the users could be arbitrarily corrupted, while each of the remaining ``good'' users still have $\alpha$-fraction ($\alpha>0$) of corrupted samples. The goal is to estimate the unknown mean $\mu$ with small $\ell_2$ error. This is a challenging scenario because we must handle two types of adversarial corruption: user-level corruption and sample-level corruption. When the unknown distribution has covariance matrix bounded by the identity matrix, we design a sum-of-squares (SoS) algorithm that achieves an $\ell_2$ error of $\sqrt{\alpha}$ with probability at least $2/3$ as long as the total number of samples $nN=\widetilde{\Omega}(d/\alpha)$. The estimation error and sample complexity are min-max optimal under the mild condition. For comparison, treating all $nN$ samples as $(\varepsilon+\alpha)$-corrupted and applying standard robust mean estimation only achieves an error of $\sqrt{\varepsilon+\alpha}$. Thus, our new algorithm removes the adverse effect of untrustworthy users and achieves the optimal error as if only sample-level corruption is present. Also, our SoS algorithm extends to the heterogeneous setting where each user's local mean could be additionally shifted by $\sqrt{\beta}$ in $\ell_2$ distance. We show that an error of $O(\sqrt{\alpha+\beta})$ can be achieved with probability at least $2/3$ when $nN=\widetilde{\Omega}(d/(\alpha+\beta))$.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2602.20698v2제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.