EUVIMEDEUVIMED entdecken
Crossref

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

Angshul Majumdar

Machine Learning · 2026-07 · 115 (7)

DOI: 10.1007/s10994-026-07101-2 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Machine Learning, online erschienen am 07.07.2026. Verfasst von Angshul Majumdar. Die Arbeit nennt 28 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We revisit median-of-means (MoM) estimation from a deterministic optimisation viewpoint and develop a family of block-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_p$$\end{document} estimators tailored to robust learning with heavy-tailed and adversarially corrupted data. In a block contamination model with at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1-\varepsilon )$$\end{document} good blocks, we first show that every convex block M-estimator has worst-case robustness constant at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/(1-2\varepsilon )$$\end{document}, matching the classical MoM bound and proving that the trimmed-block oracle constant \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/(1-\varepsilon )$$\end{document} is unattainable within the convex class. We then introduce a nonconvex block-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_p$$\end{document} family, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p\in (0,1]$$\end{document}, and derive finite-sample deterministic robustness bounds for all global minimisers. As p decreases from 1 to 0, these bounds interpolate continuously between \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/(1-2\varepsilon )$$\end{document} and the block-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_0$$\end{document} oracle \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/(1-\varepsilon )$$\end{document}; 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-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_p$$\end{document} 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(2+\delta )$$\end{document} 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.

Zitieren

APA

Majumdar, A. (2026). Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle. Machine Learning, 115(7). https://doi.org/10.1007/s10994-026-07101-2

Vancouver

Majumdar A. Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle. Machine Learning. 2026;115(7). doi:10.1007/s10994-026-07101-2

BibTeX
@article{Majumdar2026,
  author = {Majumdar, Angshul},
  title = {Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle},
  journal = {Machine Learning},
  year = {2026},
  volume = {115},
  number = {7},
  doi = {10.1007/s10994-026-07101-2}
}
Kostenlos starten →