SOURCE-LINKED INTELLIGENCE

Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle

arXiv · AI, language, vision and robotics · article · Sep 1, 2026 · UTC

We revisit median-of-means estimation from a deterministic optimization viewpoint and develop a family of block-Lp estimators for robust learning with heavy-tailed and adversarially corrupted data. In a block contamination model with at least a fraction 1 minus epsilon of good blocks, we first show that every convex block M-estimator has worst-case robustness constant at least 1 divided by 1 minus 2 epsilon. This matches the classical median-of-means bound and proves that the trimmed-block oracle constant 1 divided by 1 minus epsilon cannot be attained within the convex class. We then introduc

Read original source ↗ Open in workspace

recordType

paper

region

Global