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

Özetle: 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.

Özet

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 $α$-fraction ($α>0$) of corrupted samples. The goal is to estimate the unknown mean $μ$ 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α$ with probability at least $2/3$ as long as the total number of samples $nN=widetildeΩ(d/α)$. The estimation error and sample complexity are min-max optimal under the mild condition. For comparison, treating all $nN$ samples as $(varepsilon+α)$-corrupted and applying standard robust mean estimation only achieves an error of $sqrt{varepsilon+α}$. 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β$ in $ell_2$ distance. We show that an error of $O(sqrt{α+β})$ can be achieved with probability at least $2/3$ when $nN=widetildeΩ(d/(α+β))$.

Orijinal Özet (İngilizce)

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 $α$-fraction ($α>0$) of corrupted samples. The goal is to estimate the unknown mean $μ$ 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α$ with probability at least $2/3$ as long as the total number of samples $nN=widetildeΩ(d/α)$. The estimation error and sample complexity are min-max optimal under the mild condition. For comparison, treating all $nN$ samples as $(varepsilon+α)$-corrupted and applying standard robust mean estimation only achieves an error of $sqrt{varepsilon+α}$. 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β$ in $ell_2$ distance. We show that an error of $O(sqrt{α+β})$ can be achieved with probability at least $2/3$ when $nN=widetildeΩ(d/(α+β))$.

Kaynak: arXiv:2602.20698 · PDF