Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle
Mirrored from arXiv — Machine Learning for archival readability. Support the source by reading on the original site.
Computer Science > Machine Learning
Title:Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle
Abstract: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 introduce a nonconvex block-Lp family for p between 0 and 1 and derive finite-sample deterministic robustness bounds for all global minimizers. As p decreases from 1 toward 0, these bounds continuously approach the trimmed-block oracle constant. For sufficiently small p, the global minimizers coincide with those of the oracle under a mild separation condition. We also show that the block-Lp objectives have a benign landscape, with all local minima remaining close to the truth and no bad basins. Combining these results with block-level concentration yields sub-Gaussian deviation bounds under finite 2 plus delta moments and high-dimensional extensions to robust mean estimation and sparse regression.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2609.01689 [cs.LG] |
| (or arXiv:2609.01689v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2609.01689
arXiv-issued DOI via DataCite
|
|
| Journal reference: | Majumdar, A. Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle. Mach Learn 115, 172 (2026) |
| Related DOI: | https://doi.org/10.1007/s10994-026-07101-2
DOI(s) linking to related resources
|
Submission history
From: Angshul Majumdar Dr. [view email][v1] Tue, 1 Sep 2026 15:39:04 UTC (33 KB)
Access Paper:
- View PDF
- HTML (experimental)
- TeX Source
References & Citations
Bookmark
Bibliographic and Citation Tools
Code, Data and Media Associated with this Article
Demos
Recommenders and Search Tools
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
More from arXiv — Machine Learning
-
Fundamental Dynamical Units for Physics-Informed Structural Inference from Perturbation Time-Series in Networked Systems
Sep 14
-
Physics-Informed Conformal Prediction: Embedding PDE Consistency into Distribution-Free Uncertainty Quantification for Neural Operators
Sep 14
-
Fed-Equilibrium Framework for Topological Pareto Control in Robust and Fair Clinical Federated Learning
Sep 14
-
Efficient AI Model Deployment Using Quantization Analysis Tool
Sep 14
Discussion (0)
Sign in to join the discussion. Free account, 30 seconds — email code or GitHub.
Sign in →No comments yet. Sign in and be the first to say something.