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

Summary

The paper recasts median-of-means (MoM) estimation as minimization of an L1 objective over block means and asks whether nonconvex block aggregation can outperform convex procedures under deterministic block contamination. It first claims an impossibility: every convex block M-estimator with breakdown point 1/2 has worst-case robustness constant at least 1/(1−2ε) (Theorem 3.3), so the trimmed-block oracle constant 1/(1−ε) is unreachable within the convex class. It then studies F_p(t)=Σ|Z_b−t|^p for p∈(0,1], proving finite robustness constants and breakdown point 1/2 for global minimizers (Theorem 4.2). Under a good/bad block separation it further asserts that for small p the global minimizers coincide with the trimmed-block oracle (Theorem 5.2), that the landscape has no bad local minima (Theorem 5.3), and that sub-Gaussian deviations under (2+δ) moments follow (Theorem 6.2), with extensions to high-dimensional mean estimation and sparse regression (Theorems 7.1–7.2). All results after Theorem 4.2 are proof sketches deferring to a supplementary material that is absent from the paper. More seriously, the central impossibility theorem appears false: the median itself (ρ=|u|) belongs to the allowed convex class, yet its true worst-case constant under the paper's model is 1, below 1/(1−2ε) for every ε>0, and the proof contains a sign error in the objective's derivative; spurious local minima at outlier locations also contradict Theorem 5.3. The experiments (Tables 1–3) lack parameters and code, and the trimmed-mean baseline beats the proposed block-L0.2 in all three settings.