We revisit median-of-means (MoM) estimation from a deterministic optimisation viewpoint and develop a family of block- \(L_p\) estimators tailored to robust learning with heavy-tailed and adversarially corrupted data. In a block contamination model with at least \((1-\varepsilon )\) good blocks, we first show that every convex block M-estimator has worst-case robustness constant at least \(1/(1-2\varepsilon )\) , matching the classical MoM bound and proving that the trimmed-block oracle constant \(1/(1-\varepsilon )\) is unattainable within the convex class. We then introduce a nonconvex block- \(L_p\) family, \(p\in (0,1]\) , and derive finite-sample deterministic robustness bounds for all global minimisers. As p decreases from 1 to 0, these bounds interpolate continuously between \(1/(1-2\varepsilon )\) and the block- \(L_0\) oracle \(1/(1-\varepsilon )\) ; for small p the global minimisers coincide with those of the oracle under a mild separation condition. We further show that the energy landscape of the block- \(L_p\) objectives is benign: all local minima lie near the truth and there are no bad basins. Combining these results with block-level concentration yields sub-Gaussian deviation bounds under finite \((2+\delta )\) moments and high-dimensional extensions for robust mean estimation and sparse regression with optimal rates. The analysis places MoM estimators on a continuous 1–p–0 path that approaches trimmed-block performance while remaining computationally tractable and directly applicable to modern robust learning problems.
