Robust Estimation Under Heterogeneous Corruption Rates
This work addresses the problem of robust estimation for applications like distributed learning and sensor networks, where corruption rates vary, and it is incremental by extending existing uniform corruption models to heterogeneous settings.
The paper tackles robust estimation under heterogeneous corruption rates, where each sample has a known but non-identical corruption probability, and establishes tight minimax rates for mean estimation in multivariate bounded and univariate Gaussian distributions, as well as rates up to a factor of √d for multivariate Gaussian mean estimation and linear regression.
We study the problem of robust estimation under heterogeneous corruption rates, where each sample may be independently corrupted with a known but non-identical probability. This setting arises naturally in distributed and federated learning, crowdsourcing, and sensor networks, yet existing robust estimators typically assume uniform or worst-case corruption, ignoring structural heterogeneity. For mean estimation for multivariate bounded distributions and univariate gaussian distributions, we give tight minimax rates for all heterogeneous corruption patterns. For multivariate gaussian mean estimation and linear regression, we establish the minimax rate for squared error up to a factor of $\sqrt{d}$, where $d$ is the dimension. Roughly, our findings suggest that samples beyond a certain corruption threshold may be discarded by the optimal estimators -- this threshold is determined by the empirical distribution of the corruption rates given.