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
arXiv:2609.01689 (cs)
[Submitted on 1 Sep 2026]
Title:Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle
Authors:Angshul Majumdar
View a PDF of the paper titled Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle, by Angshul Majumdar
View PDF
HTML (experimental)
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)
Full-text links:
Access Paper:
- View PDF
- HTML (experimental)
- TeX Source
View a PDF of the paper titled Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle, by Angshul Majumdar
References & Citations
Loading...
Bookmark
Bibliographic Tools
Code, Data, Media
Demos
Related Papers
About arXivLabs
Bibliographic and Citation Tools
Bibliographic Explorer Toggle
Bibliographic Explorer (What is the Explorer?)
Connected Papers Toggle
Connected Papers (What is Connected Papers?)
Litmaps Toggle
Litmaps (What is Litmaps?)
scite.ai Toggle
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
alphaXiv Toggle
alphaXiv (What is alphaXiv?)
Links to Code Toggle
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub Toggle
DagsHub (What is DagsHub?)
GotitPub Toggle
Gotit.pub (What is GotitPub?)
Huggingface Toggle
Hugging Face (What is Huggingface?)
ScienceCast Toggle
ScienceCast (What is ScienceCast?)
Demos
Replicate Toggle
Replicate (What is Replicate?)
Spaces Toggle
Hugging Face Spaces (What is Spaces?)
Spaces Toggle
TXYZ.AI (What is TXYZ.AI?)
Recommenders and Search Tools
Link to Influence Flower
Influence Flower (What are Influence Flowers?)
Core recommender toggle
CORE Recommender (What is CORE?)
IArxiv recommender toggle
IArxiv Recommender
(What is IArxiv?)
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
-
Federating Quantum and Classical Computing: A Privacy-Preserving Hybrid Approach
Sep 23
-
Entropy Can Flow, or It Can Guide. Be Entropy. LEDFlow: Introducing Entropy-guided Generation Order into Uniform Discrete Flow
Sep 23
-
The Probabilistic Structure of Large Language Models
Sep 23
-
Stable Unsupervised Continual Chunking with Sheaf SyncMap
Sep 23
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.