Median-of-Means Re-examined for Robust Learning

This research delves into the median-of-means estimation technique, re-evaluating it through the lens of deterministic optimization. The study focuses on developing robust learning methods capable of handling heavy-tailed and adversarially corrupted data, a common challenge in real-world datasets. The authors introduce a new family of block-Lp estimators, where 'p' ranges between 0 and 1, designed to enhance robustness. A key finding is that within a block contamination model, any convex block M-estimator is inherently limited in its worst-case robustness, achieving a constant of at least 1 divided by (1 - 2*epsilon). This matches the known median-of-means bound and demonstrates that the ideal trimmed-block oracle constant of 1 divided by (1 - epsilon) cannot be reached using purely convex methods. To overcome this limitation, the paper proposes the nonconvex block-Lp family. As the parameter 'p' decreases towards 0, the robustness bounds of these nonconvex estimators continuously approach the trimmed-block oracle constant. For sufficiently small 'p', the global minimizers of these objectives align with those of the oracle under specific conditions. Furthermore, the study shows that these nonconvex block-Lp objectives possess a "benign landscape," meaning all local minima remain close to the true solution, avoiding problematic basins. These theoretical results, combined with block-level concentration, lead to sub-Gaussian deviation bounds and high-dimensional extensions for robust mean estimation and sparse regression.