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

• URL: http://arxiv.org/abs/2609.01689v1
• Date: Tue, 01 Sep 2026 15:39:04 GMT
• Title: Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle
• Abstract summary: We develop a family block-Lp estimators for robust learning with heavy-tailed and adversarially corrupted data.<n>We show that the block-Lp objectives have a benign landscape, with all local minima remaining close to the truth and no bad basins.
• Score: 11.62669179647184
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• Resolving Multi-Modal Regression by Difference-Quotient-Based Clustering:Fast Coarse Conditional-Label Assignment [0.0]
  Difference-Quotient Clustering (DQC) partitions data to minimize intra-cluster output-vs-input discrepancy.<n>We observe two empirical regularities: larger intra-cluster contradictions require deeper networks, and oracle labels generalize from fewer samples than cluster-derived equivalents.
  arXiv  Detail & Related papers  (2026-08-26T07:34:23Z)
• Global Minimax Readout of a Qubit Direction [5.246986428523558]
  We determine the exact worst-direction Fisher-information cost of using a parameter-independent readout to estimate an unknown qubit direction at known Bloch-vector length $$.<n>Every fixed-local architecture, including recorded classical randomization, reduces exactly to a zero-barycenter probability measure on the Bloch ball.<n>For every full-rank qubit and every trace-balanced spectral Fisher loss, the resulting minimax problem is rigid.
  arXiv  Detail & Related papers  (2026-08-17T17:26:32Z)
• HOMER: Huber-of-Means for Efficient and Robust Estimation in Hilbert Spaces [0.26856688022781555]
  We propose emphHOMER, or Huber-of-Means for Robust Estimation.<n>Its canonical and pseudo-Huber forms bound each block score and interpolate between median-like robustness and the empirical mean.<n>We show that HOMER remains stable when a minority of block summaries is displaced.
  arXiv  Detail & Related papers  (2026-07-29T23:51:17Z)
• Local LMO: Constrained Gradient Optimization via a Local Linear Minimization Oracle [51.714334316332476]
  Local L is a new projection-free type for constrained optimization.<n>Local LMO is perhaps best viewed as an oracle of Gradient Descent (GD)
  arXiv  Detail & Related papers  (2026-05-09T10:03:24Z)
• From Tail Universality to Bernstein-von Mises: A Unified Statistical Theory of Semi-Implicit Variational Inference [0.12183405753834557]
  Semi-implicit variational inference (SIVI) constructs approximate posteriors of the form $q() = int k(| z) r(dz)$<n>This paper develops a unified "approximation-optimization-statistics'' theory for such families.
  arXiv  Detail & Related papers  (2025-12-05T19:26:25Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  We study the problem of clustering $T$ trajectories of length $H$, each generated by one of $K$ unknown ergodic Markov chains over a finite state space of size $S$.<n>We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the weighted KL divergence between the transition kernels of the chains.<n>We then present a novel two-stage clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-02T05:10:40Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  We analyze $f$-divergence-regularized offline policy learning.<n>For reverse Kullback-Leibler (KL) divergence, we give the first $tildeO(epsilon-1)$ sample complexity under single-policy concentrability.<n>We extend our analysis to dueling bandits, and we believe these results take a significant step toward a comprehensive understanding of $f$-divergence-regularized policy learning.
  arXiv  Detail & Related papers  (2025-02-09T22:14:45Z)
• Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogates [0.0]
  We show that the first optimality gap of the proposed algorithm decays at the rate of the expected loss for various methods under nontens dependent data setting. We obtain first convergence point for various methods under nontens dependent data setting.
  arXiv  Detail & Related papers  (2022-01-05T15:17:35Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Federated Functional Gradient Boosting [75.06942944563572]
  We study functional minimization in Federated Learning. For both FFGB.C and FFGB.L, the radii of convergence shrink to zero as the feature distributions become more homogeneous.
  arXiv  Detail & Related papers  (2021-03-11T21:49:19Z)
• Computationally efficient sparse clustering [67.95910835079825]
  We provide a finite sample analysis of a new clustering algorithm based on PCA. We show that it achieves the minimax optimal misclustering rate in the regime $|theta infty$.
  arXiv  Detail & Related papers  (2020-05-21T17:51:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.