paper

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

arXiv:2602.20698

Abstract

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 users, each with samples. fraction of the users could be arbitrarily corrupted, while each of the remaining ``good'' users still have -fraction () of corrupted samples. The goal is to estimate the unknown mean with small 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 error of with probability at least as long as the total number of samples . The estimation error and sample complexity are min-max optimal under the mild condition. For comparison, treating all samples as -corrupted and applying standard robust mean estimation only achieves an error of . 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 in distance. We show that an error of can be achieved with probability at least when .