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

# Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle
Source: [https://arxiv.org/html/2609.01689](https://arxiv.org/html/2609.01689)
Angshul MajumdarAffiliation:Department of Electronics and Communications Engineering, IIIT Delhi, IndiaEmail:[angshul@iiitd\.ac\.in](mailto:)

###### Abstract

We revisit median\-of\-means \(MoM\) estimation from a deterministic optimisation viewpoint and develop a family of block\-LpL\_\{p\}estimators tailored to robust learning with heavy\-tailed and adversarially corrupted data\. In a block contamination model with at least\(1−ε\)\(1\-\\varepsilon\)good blocks, we first show that every convex blockMM\-estimator has worst\-case robustness constant at least1/\(1−2​ε\)1/\(1\-2\\varepsilon\), matching the classical MoM bound and proving that the trimmed\-block oracle constant1/\(1−ε\)1/\(1\-\\varepsilon\)is unattainable within the convex class\. We then introduce a nonconvex block\-LpL\_\{p\}family,p∈\(0,1\]p\\in\(0,1\], and derive finite\-sample deterministic robustness bounds for all global minimisers\. Asppdecreases from11to00, these bounds interpolate continuously between1/\(1−2​ε\)1/\(1\-2\\varepsilon\)and the block\-L0L\_\{0\}oracle1/\(1−ε\)1/\(1\-\\varepsilon\); for smallppthe global minimisers coincide with those of the oracle under a mild separation condition\. We further show that the energy landscape of the block\-LpL\_\{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\+δ\)\(2\+\\delta\)moments and high\-dimensional extensions for robust mean estimation and sparse regression with optimal rates\. The analysis places MoM estimators on a continuous11–pp–00path that approaches trimmed\-block performance while remaining computationally tractable and directly applicable to modern robust learning problems\.

Keywords:median of means; robust estimation; non\-convex minimization

## 1Introduction

Robust estimation under heavy\-tailed noise and adversarial contamination has seen a remarkable revival over the last decade\. A central lesson of this literature is that classical least\-squares and empirical means are fundamentally unstable once the variance is large or the sample is corrupted, whereas suitably designed robust procedures can recover sub\-Gaussian accuracy under minimal moment assumptions\[[8](https://arxiv.org/html/2609.01689#bib.bib2),[19](https://arxiv.org/html/2609.01689#bib.bib4),[23](https://arxiv.org/html/2609.01689#bib.bib18)\]\. Median\-of\-means \(MoM\) estimators and their geometric\-median refinements now form a standard toolkit for constructing such procedures in both finite\- and infinite\-dimensional settings\[[24](https://arxiv.org/html/2609.01689#bib.bib7),[14](https://arxiv.org/html/2609.01689#bib.bib8),[8](https://arxiv.org/html/2609.01689#bib.bib2),[21](https://arxiv.org/html/2609.01689#bib.bib5)\]\.

The MoM principle is simple: partition the sample intoBBblocks, compute the empirical mean on each block, and aggregate these block means through a robust one\-dimensional functional, most commonly the median\. The resulting estimator preserves the optimaln−1/2n^\{\-1/2\}rate and enjoys sub\-Gaussian deviation bounds under only finite second moments, even in the presence of a constant fraction of arbitrarily corrupted blocks\[[19](https://arxiv.org/html/2609.01689#bib.bib4),[8](https://arxiv.org/html/2609.01689#bib.bib2)\]\. Extensions based on geometric medians in Banach spaces and tournament\-type procedures have led to nearly optimal robust estimators for a wide range of loss functions and high\-dimensional models\[[24](https://arxiv.org/html/2609.01689#bib.bib7),[20](https://arxiv.org/html/2609.01689#bib.bib6),[14](https://arxiv.org/html/2609.01689#bib.bib8),[21](https://arxiv.org/html/2609.01689#bib.bib5),[11](https://arxiv.org/html/2609.01689#bib.bib9)\]\.

However, the usual blockwise MoM construction also has a structural limitation that motivates the present work\. In the scalar setting, the median\-of\-means estimator is already anL1L\_\{1\}\-type block aggregator, and more generally many robust blockwise procedures are obtained by minimising convex blockMM\-estimation objectives\. Under the deterministic block\-contamination metric studied here, this convex world cannot improve on the classical MoM robustness constant\. This immediately raises the natural question that drives the paper: if convex block aggregation is fundamentally trapped at the MoM benchmark, can a carefully designed nonconvex block objective move us closer to the trimmed\-block oracle while retaining the stability that makes MoM useful in the first place?

This question is not merely formal\. Classical MoM remains attractive because it is simple, distribution\-light, and robust, yet its deterministic constant under block contamination is separated from the oracle trimmed\-block constant by a nontrivial gap\. In benign heavy\-tailed regimes one should not expect dramatic gains from leavingp=1p=1, and the new experiments indeed show essentially comparable behaviour there\. By contrast, when corrupted blocks are sufficiently separated from clean ones—for example under adversarial block shifts of appreciable magnitude—one expects a more selective blockwise objective to behave increasingly like an implicit trimming rule\. This is precisely the regime in which the proposed block\-LpL\_\{p\}family becomes meaningful\.

From an optimisation viewpoint, this suggests importing the familiarL1→Lp→L0L\_\{1\}\\rightarrow L\_\{p\}\\rightarrow L\_\{0\}continuum from sparse recovery into blockwise robust aggregation\. In compressed sensing and nonconvex regularisation, the passage from convexL1L\_\{1\}penalties to nonconvexLpL\_\{p\}surrogates and then to combinatorialL0L\_\{0\}objectives is a standard route for approximating ideal support selection while preserving a tractable optimisation landscape\[[12](https://arxiv.org/html/2609.01689#bib.bib1),[5](https://arxiv.org/html/2609.01689#bib.bib19)\]\. Here we use the same idea at the level of block means rather than samplewise outlier indicators\. This viewpoint also clarifies why the small\-pplimit is desirable: the goal is not to replace trimmed estimators or Huber\-type procedures by yet another robust estimator, but to construct a continuous optimisation path within the MoM paradigm that connects convex aggregation to an ideal trimmed\-block oracle and makes the corresponding improvement in deterministic robustness explicit\.

It is also important to position the present analysis relative to other robust methods\. Convex procedures based on Huber losses, Catoni\-type truncation, or median/geometric\-median aggregation remain highly effective and often minimax\-optimal at the level of rates\[[4](https://arxiv.org/html/2609.01689#bib.bib23),[17](https://arxiv.org/html/2609.01689#bib.bib14),[19](https://arxiv.org/html/2609.01689#bib.bib4)\]\. Likewise, recent Byzantine\-robust and federated\-learning methods use Huberisation, trimming, or geometric\-median ideas in settings with different threat models and heterogeneity assumptions\. Our aim is narrower and more structural: we work in a block contamination model and study which deterministic robustness constants are achievable by convex versus nonconvex block aggregation\. In that sense, the novelty of the paper is not a new minimax rate, but a deterministic interpolation theorem, an impossibility result for the convex class, and an oracle\-equivalence result showing when nonconvex block\-LpL\_\{p\}objectives can genuinely outperform classical MoM\.

Concretely, given block means\(Z1,…,ZB\)\(Z\_\{1\},\\dots,Z\_\{B\}\)of a univariate parameterμ\\mu, we study the family of nonconvex functionals

Fp​\(t\)=∑b=1B\|Zb−t\|p,0<p≤1,F\_\{p\}\(t\)\\;=\\;\\sum\_\{b=1\}^\{B\}\\lvert Z\_\{b\}\-t\\rvert^\{p\},\\qquad 0<p\\leq 1,and their minimiserst^p∈arg⁡mint∈ℝ​Fp​\(t\)\\hat\{t\}\_\{p\}\\in\\arg\\min\_\{t\\in\\mathbb\{R\}\}F\_\{p\}\(t\)\. The casep=1p=1recovers a median\-of\-block\-means estimator, while the formal limitp→0p\\to 0corresponds to selecting the value ofttthat minimises the number of “far” blocks, that is, anL0L\_\{0\}\-style trimmed\-block functional\. Our first contribution is a finite\-sample deterministic analysis of this1​–​p​–​01\\text\{\-\-\}p\\text\{\-\-\}0path under an adversarial block\-contamination model: at least\(1−ε\)​B\(1\-\\varepsilon\)Bblock means lie in a prescribed interval aroundμ\\mu, and the remainingε​B\\varepsilon Bblocks are arbitrary\. We show that for every0<p≤10<p\\leq 1there is an explicit constantc⁡\(p,ε\)c\(p,\\varepsilon\)such that any global minimisert^p\\hat\{t\}\_\{p\}satisfies

\|t^p−μ\|≤c⁡\(p,ε\)​r,\\lvert\\hat\{t\}\_\{p\}\-\\mu\\rvert\\;\\leq\\;c\(p,\\varepsilon\)\\,r,whererris the radius of the good\-block interval\. These constants interpolate continuously between the classical MoM constant atp=1p=1and the trimmed\-block oracle constant asp↓0p\\downarrow 0, and under a separation condition the small\-ppglobal minimisers coincide with the oracle solutions\.

The second contribution is geometric\. AlthoughFpF\_\{p\}is nonconvex forp<1p<1, we show that its landscape is benign under the same contamination model: all local minimisers remain in a controlled neighbourhood of the truth, and the objective satisfies a quantitative descent property outside that neighbourhood\. This does not constitute a full optimisation theory for every algorithm, but it does show that the nonconvexity introduced here is structured rather than pathological, which is the level of claim required for the present theoretical programme\.

Third, we embed the deterministic analysis into a probabilistic framework\. Assuming only finite\(2\+δ\)\(2\+\\delta\)moments, we derive deviation inequalities of the same order as classical MoM procedures while making explicit how the leading constant improves asppdecreases when the separation condition is available\. The gain is therefore conditional rather than universal: in ordinary heavy\-tailed settings without clear clean/contaminated block separation, one should expect behaviour similar to MoM, whereas in separated contamination regimes the estimator can approach oracle trimmed\-block performance\. This trade\-off is now spelled out explicitly in both the theory and the experiments\.

Finally, we extend the same viewpoint to high\-dimensional robust mean estimation and sparse regression\. The purpose of these extensions is again structural: to show that the block\-LpL\_\{p\}aggregation principle can be combined with standard high\-dimensional arguments to retain the usual statistical rates while improving the deterministic robustness constants within the block model\. The revised manuscript also now includes a dedicated experimental section comparing MoM, block\-L0\.5L\_\{0\.5\}, block\-L0\.2L\_\{0\.2\}, trimmed mean, and Huber baselines in heavy\-tailed, adversarial, and separated block\-contamination regimes\. These results support the theoretical message of the paper: no degradation in benign settings, moderate gains under adversarial contamination, and near\-oracle behaviour when block separation is present\.

## 2Model and classical median\-of\-means estimators

In this section we formalise the one\-dimensional setting and recall the classical median\-of\-means \(MoM\) estimator and its basic robustness properties\. Throughout, we adopt the notation of Section[1](https://arxiv.org/html/2609.01689#S1)\.

### 2\.1Data, block structure, and contamination model

We observe independent real\-valued random variables

X1,…,Xn∼P,𝔼⁡\[Xi\]=μ,X\_\{1\},\\dots,X\_\{n\}\\sim P,\\qquad\\mathbb\{E\}\[X\_\{i\}\]=\\mu,\(2\.1\)whereμ∈ℝ\\mu\\in\\mathbb\{R\}is the parameter of interest\. For simplicity we assume thatnnis divisible by a prescribed number of blocksB∈\{1,…,n\}B\\in\\\{1,\\dots,n\\\}and set

m=nBm\\;=\\;\\frac\{n\}\{B\}\(2\.2\)for the common block size\. We fix a partition of\{1,…,n\}\\\{1,\\dots,n\\\}intoBBdisjoint blocks

\{1,…,n\}=I1∪˙⋯∪˙IB,\|Ib\|=mfor allb∈\{1,…,B\}\.\\\{1,\\dots,n\\\}\\;=\\;I\_\{1\}\\,\\dot\{\\cup\}\\,\\cdots\\,\\dot\{\\cup\}\\,I\_\{B\},\\qquad\|I\_\{b\}\|=m\\;\\;\\text\{for all \}b\\in\\\{1,\\dots,B\\\}\.\(2\.3\)The corresponding block means are

Zb=1m∑i∈IbXi,b=1,…,B,Z\_\{b\}\\;=\\;\\frac\{1\}\{m\}\\sum\_\{i\\in I\_\{b\}\}X\_\{i\},\\qquad b=1,\\dots,B,\(2\.4\)and we writeZ=\(Z1,…,ZB\)Z=\(Z\_\{1\},\\dots,Z\_\{B\}\)for the vector of block means\.

Following the robust MoM literature\[[18](https://arxiv.org/html/2609.01689#bib.bib12),[17](https://arxiv.org/html/2609.01689#bib.bib14)\], we consider a nonasymptotic, finite\-sample contamination model at the block level\. We assume that there exists an unknown index setG⊂\{1,…,B\}G\\subset\\\{1,\\dots,B\\\}of “good” blocks with cardinality\|G\|≥\(1−ε\)​B\|G\|\\geq\(1\-\\varepsilon\)B, whereε∈\[0,1/2\)\\varepsilon\\in\[0,1/2\), such that the following holds\.

###### Assumption 2\.1\(Block contamination model\)\.

There exist parametersμ∈ℝ\\mu\\in\\mathbb\{R\},r\>0r\>0and a subsetG⊂\{1,…,B\}G\\subset\\\{1,\\dots,B\\\}with\|G\|≥\(1−ε\)​B\|G\|\\geq\(1\-\\varepsilon\)Bsuch that

\|Zb−μ\|≤rfor all​b∈G\.\|Z\_\{b\}\-\\mu\|\\;\\leq\\;r\\qquad\\text\{for all \}b\\in G\.\(2\.5\)For the remaining blocksb∉Gb\\notin Gno assumption is imposed: the valuesZbZ\_\{b\}may be arbitrary \(possibly chosen adversarially\)\.

In probabilistic applications, the setGGwill typically be realised by blocks containing no gross outliers and for whichZbZ\_\{b\}concentrates aroundμ\\muat a rate determined by the underlying moment assumptions\[[8](https://arxiv.org/html/2609.01689#bib.bib2),[19](https://arxiv.org/html/2609.01689#bib.bib4)\]\. However, Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)is purely deterministic and will serve as the basic framework for our finite\-sample robustness analysis\.

It is important to stress that this is a*block*\-contamination model rather than a statement about the raw fraction of corrupted sample points\. A comparatively small number of adversarial observations may contaminate many blocks if they are spread across the partition, while a larger number of outliers may remain confined to only a few blocks if they are concentrated\. Consequently, the relevant robustness parameter for MoM in the present framework is the proportion of corrupted blocks, not the overall sample\-level outlier ratio\. This distinction is exactly the one that will matter in the discussion of breakdown and robustness constants below\.

### 2\.2The classical median\-of\-means estimator as anL1L\_\{1\}functional

In the scalar setting, the classical MoM estimator goes back at least to Nemirovsky and Yudin\[[26](https://arxiv.org/html/2609.01689#bib.bib10)\]and has been rediscovered and refined in numerous works since\[[16](https://arxiv.org/html/2609.01689#bib.bib11),[18](https://arxiv.org/html/2609.01689#bib.bib12),[19](https://arxiv.org/html/2609.01689#bib.bib4),[27](https://arxiv.org/html/2609.01689#bib.bib16)\]\. Given the block means \([2\.4](https://arxiv.org/html/2609.01689#S2.E4)\), the MoM estimator ofμ\\muis defined as

t^MoM=median⁡\{Z1,…,ZB\}\.\\hat\{t\}\_\{\\mathrm\{MoM\}\}\\;=\\;\\operatorname\{median\}\\\{Z\_\{1\},\\dots,Z\_\{B\}\\\}\.\(2\.6\)Equivalently,t^MoM\\hat\{t\}\_\{\\mathrm\{MoM\}\}can be characterised as a minimiser of the empiricalL1L\_\{1\}loss over the block means:

t^MoM∈arg⁡mint∈ℝ​F1​\(t\),F1​\(t\):=∑b=1B\|Zb−t\|\.\\hat\{t\}\_\{\\mathrm\{MoM\}\}\\;\\in\\;\\arg\\min\_\{t\\in\\mathbb\{R\}\}F\_\{1\}\(t\),\\qquad F\_\{1\}\(t\)\\;:=\\;\\sum\_\{b=1\}^\{B\}\|Z\_\{b\}\-t\|\.\(2\.7\)This observation makes precise the statement in Section[1](https://arxiv.org/html/2609.01689#S1)that the usual MoM estimator is already anL1L\_\{1\}\-type object at the block level\.

Under Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1), the right deterministic summary is not simply that MoM has “breakdown point1/21/2” in terms of the raw sample fraction\. Rather, the median functional applied to the*block means*inherits the classical1/21/2threshold at the level of corrupted*blocks*, whereas the effective robustness of the resulting MoM estimator depends on how sample\-level contamination propagates through the partition into corrupted blocks\. Thus an outlier fraction well below1/21/2at sample level may still invalidate MoM if those outliers contaminate more than half of the blocks, while a larger sample\-level contamination can remain harmless if it is confined to fewer than half the blocks\. For this reason, throughout the paper we state robustness in terms of the block contamination fractionε\\varepsilonand the associated deterministic robustness constant\. A precise version of this statement will be recalled and generalised in the next section\.

### 2\.3Convex block M\-estimators

Many robust procedures in the MoM family can be expressed as minimisers of a convex blockwise loss\. Letρ:ℝ→\[0,∞\)\\rho:\\mathbb\{R\}\\to\[0,\\infty\)be an even, convex function withρ⁡\(0\)=0\\rho\(0\)=0and nondecreasing on\[0,∞\)\[0,\\infty\)\. The associated*convex block M\-estimator*ofμ\\muis defined by

t^ρ∈arg⁡mint∈ℝ​Fρ​\(t\),Fρ​\(t\):=∑b=1Bρ⁡\(Zb−t\)\.\\hat\{t\}\_\{\\rho\}\\;\\in\\;\\arg\\min\_\{t\\in\\mathbb\{R\}\}F\_\{\\rho\}\(t\),\\qquad F\_\{\\rho\}\(t\)\\;:=\\;\\sum\_\{b=1\}^\{B\}\\rho\(Z\_\{b\}\-t\)\.\(2\.8\)For example, takingρ⁡\(u\)=\|u\|\\rho\(u\)=\|u\|recovers the MoM estimator \([2\.7](https://arxiv.org/html/2609.01689#S2.E7)\), while Huber\-type choices lead to blockwise Catoni or minmax\-MoM style estimators\[[2](https://arxiv.org/html/2609.01689#bib.bib13),[17](https://arxiv.org/html/2609.01689#bib.bib14)\]\. In high\-dimensional settings, one often replacesZb−tZ\_\{b\}\-tby more general blockwise loss or risk functionals and still aggregates them via a scalar M\-estimator of the form \([2\.8](https://arxiv.org/html/2609.01689#S2.E8)\); see, for instance, the minmax MoM estimators for empirical risk minimisation and regression in[Hsu and Sabato \[14\]](https://arxiv.org/html/2609.01689#bib.bib8),[Brownlees et al\. \[2\]](https://arxiv.org/html/2609.01689#bib.bib13),[Lecué and Lerasle \[17\]](https://arxiv.org/html/2609.01689#bib.bib14)\.

To quantify the worst\-case finite\-sample robustness of a given estimator under Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1), it is convenient to define its*deterministic robustness constant*at contamination levelε∈\[0,1/2\)\\varepsilon\\in\[0,1/2\)as

C⁡\(t^,ε\):=sup\{\|t^​\(Z\)−μ\|r:Z​satisfies Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)with parameters​\(μ,r,ε\)\},C\(\\hat\{t\},\\varepsilon\)\\;:=\\;\\sup\\biggl\\\{\\frac\{\|\\hat\{t\}\(Z\)\-\\mu\|\}\{r\}\\;:\\;Z\\text\{ satisfies Assumption~\\ref\{ass:block\-contam\} with parameters \}\(\\mu,r,\\varepsilon\)\\biggr\\\},\(2\.9\)where the supremum is over all finite configurations of block meansZZthat satisfy \([2\.5](https://arxiv.org/html/2609.01689#S2.E5)\) for someμ\\muandr\>0r\>0and over all realisations oft^\\hat\{t\}as a measurable function ofZZ\. By construction,C⁡\(t^,ε\)C\(\\hat\{t\},\\varepsilon\)is invariant under translations and scalings of the formZb↦a​Zb\+bZ\_\{b\}\\mapsto aZ\_\{b\}\+b, and captures the largest possible relative deviation \(measured in units ofrr\) thatt^\\hat\{t\}may suffer under a fractionε\\varepsilonof adversarially corrupted blocks\. This definition makes explicit that, within the present framework, robustness is indexed by the number of corrupted blocks induced by the partition rather than by the raw proportion of contaminated sample points\.

In the next section we show that, for any convex block M\-estimator \([2\.8](https://arxiv.org/html/2609.01689#S2.E8)\) with breakdown point at least1/21/2, the constantC⁡\(t^ρ,ε\)C\(\\hat\{t\}\_\{\\rho\},\\varepsilon\)cannot beat that of the classical MoM estimator \([2\.7](https://arxiv.org/html/2609.01689#S2.E7)\)\. This yields a sharp*impossibility result*for purely convex block aggregators and motivates the introduction of the nonconvexLpL\_\{p\}path developed in the rest of the paper\.

## 3An impossibility result for convex block M\-estimators

This section formalises the deterministic robustness benchmark achieved by the classical median\-of\-means estimator and shows that no estimator constructed from a convex blockwise loss of the form \([2\.8](https://arxiv.org/html/2609.01689#S2.E8)\) can improve on this benchmark in worst case\. In particular, within the class of convex block M\-estimators, there is no analogue of the1​–​p​–​01\\text\{\-\-\}p\\text\{\-\-\}0path described in Section[1](https://arxiv.org/html/2609.01689#S1): the endpoint corresponding to anL0L\_\{0\}\-type trimmed\-block oracle is unattainable\.

evThe scope of the present section is deliberately deterministic and model\-specific\. The benchmark in Lemma[3\.1](https://arxiv.org/html/2609.01689#S3.Thmtheorem1)and the impossibility result in Theorem[3\.3](https://arxiv.org/html/2609.01689#S3.Thmtheorem3)are statements about blockwise aggregation under Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)and about the robustness constant \([2\.9](https://arxiv.org/html/2609.01689#S2.E9)\)\. Thus the theorem should not be read as claiming that every Huber\-type or Byzantine\-robust method in unrelated federated\-learning models is dominated in all senses; rather, it identifies a precise limitation of the*convex block\-aggregation*class studied here\. This is the key novelty of Section[3](https://arxiv.org/html/2609.01689#S3): within the present MoM framework, convexity traps one at the classical MoM constant, whereas genuine improvement requires moving onto the nonconvex block\-LpL\_\{p\}path\.

### 3\.1Median\-of\-means as a deterministic benchmark

We begin by recalling the classical deterministic bound for the median\-of\-means estimator under Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)\. For completeness, we give a short proof; similar arguments can be found in, for example,[Lerasle and Oliveira \[18\]](https://arxiv.org/html/2609.01689#bib.bib12),[Lecué and Lerasle \[17\]](https://arxiv.org/html/2609.01689#bib.bib14),[Minsker \[25\]](https://arxiv.org/html/2609.01689#bib.bib15)\.

###### Lemma 3\.1\(Deterministic robustness of the median\-of\-means\)\.

Suppose Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)holds with parameters\(μ,r,ε\)\(\\mu,r,\\varepsilon\)andε∈\[0,1/2\)\\varepsilon\\in\[0,1/2\), that is, we have block meansZ1,…,ZBZ\_\{1\},\\dots,Z\_\{B\}and a subsetG⊂\{1,…,B\}G\\subset\\\{1,\\dots,B\\\}with\|G\|≥\(1−ε\)​B\|G\|\\geq\(1\-\\varepsilon\)Bsuch that

\|Zb−μ\|≤rfor all​b∈G\.\|Z\_\{b\}\-\\mu\|\\leq r\\qquad\\text\{for all \}b\\in G\.Lett^MoM\\hat\{t\}\_\{\\mathrm\{MoM\}\}be any median of the multiset\{Z1,…,ZB\}\\\{Z\_\{1\},\\dots,Z\_\{B\}\\\}\(i\.e\. any pointmmsuch that at leastB/2B/2of theZbZ\_\{b\}satisfyZb≤mZ\_\{b\}\\leq mand at leastB/2B/2satisfyZb≥mZ\_\{b\}\\geq m\)\. Then

\|t^MoM−μ\|≤r1−2​ε\.\|\\hat\{t\}\_\{\\mathrm\{MoM\}\}\-\\mu\|\\;\\leq\\;\\frac\{r\}\{1\-2\\varepsilon\}\.\(3\.1\)In particular, the deterministic robustness constantC⁡\(t^MoM,ε\)C\(\\hat\{t\}\_\{\\mathrm\{MoM\}\},\\varepsilon\)defined by

C⁡\(t^MoM,ε\):=sup\(μ,r,\{Zb\}\)​s\.t\. Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)\|t^MoM−μ\|rC\(\\hat\{t\}\_\{\\mathrm\{MoM\}\},\\varepsilon\):=\\sup\_\{\(\\mu,r,\\\{Z\_\{b\}\\\}\)\\text\{ s\.t\.\\ Assumption~\\ref\{ass:block\-contam\}\}\}\\frac\{\|\\hat\{t\}\_\{\\mathrm\{MoM\}\}\-\\mu\|\}\{r\}satisfies

C⁡\(t^MoM,ε\)≤11−2​ε\.C\(\\hat\{t\}\_\{\\mathrm\{MoM\}\},\\varepsilon\)\\;\\leq\\;\\frac\{1\}\{1\-2\\varepsilon\}\.

###### Proof\.

We first reduce to a normalised setting and then argue by contradiction\.

Step 1: Normalisation\.Define normalised block means

Z~b:=Zb−μr,b=1,…,B\.\\tilde\{Z\}\_\{b\}:=\\frac\{Z\_\{b\}\-\\mu\}\{r\},\\qquad b=1,\\dots,B\.Then for allb∈Gb\\in Gwe have\|Z~b\|≤1\|\\tilde\{Z\}\_\{b\}\|\\leq 1by Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)\. Letm~\\tilde\{m\}be a median of\{Z~1,…,Z~B\}\\\{\\tilde\{Z\}\_\{1\},\\dots,\\tilde\{Z\}\_\{B\}\\\}, i\.e\.m~\\tilde\{m\}is any real number such that at leastB/2B/2of theZ~b\\tilde\{Z\}\_\{b\}are≤m~\\leq\\tilde\{m\}and at leastB/2B/2are≥m~\\geq\\tilde\{m\}\.

Because the transformationt↦\(t−μ\)/rt\\mapsto\(\\;t\-\\mu\\;\)/ris affine and strictly increasing,t^MoM\\hat\{t\}\_\{\\mathrm\{MoM\}\}is a median of\{Zb\}\\\{Z\_\{b\}\\\}if and only if

m~:=t^MoM−μr\\tilde\{m\}:=\\frac\{\\hat\{t\}\_\{\\mathrm\{MoM\}\}\-\\mu\}\{r\}is a median of\{Z~b\}\\\{\\tilde\{Z\}\_\{b\}\\\}\. Therefore it suffices to prove that for*any*medianm~\\tilde\{m\}of\{Z~b\}\\\{\\tilde\{Z\}\_\{b\}\\\}we have

\|m~\|≤11−2​ε\.\|\\tilde\{m\}\|\\leq\\frac\{1\}\{1\-2\\varepsilon\}\.\(3\.2\)Once \([3\.2](https://arxiv.org/html/2609.01689#S3.E2)\) is established, multiplying both sides byrrand undoing the normalisation yields \([3\.1](https://arxiv.org/html/2609.01689#S3.E1)\)\.

Henceforth we assumeμ=0\\mu=0andr=1r=1and work withZbZ\_\{b\}in place ofZ~b\\tilde\{Z\}\_\{b\}; i\.e\. at least\(1−ε\)​B\(1\-\\varepsilon\)Bindicesbbsatisfy\|Zb\|≤1\|Z\_\{b\}\|\\leq 1\.

Step 2: Ruling out large positive medians\.Suppose, for the sake of contradiction, that there exists a medianmmsuch that

m\>11−2​ε\.m\>\\frac\{1\}\{1\-2\\varepsilon\}\.\(3\.3\)Since0≤ε<1/20\\leq\\varepsilon<1/2, we have1−2​ε∈\(0,1\]1\-2\\varepsilon\\in\(0,1\], hence

11−2​ε≥1\.\\frac\{1\}\{1\-2\\varepsilon\}\\geq 1\.Thus \([3\.3](https://arxiv.org/html/2609.01689#S3.E3)\) impliesm\>1m\>1\.

For each good blockb∈Gb\\in Gwe have\|Zb\|≤1\|Z\_\{b\}\|\\leq 1, henceZb≤1Z\_\{b\}\\leq 1\. Combining this withm\>1m\>1yields

Zb<mfor all​b∈G\.Z\_\{b\}<m\\qquad\\text\{for all \}b\\in G\.\(3\.4\)In particular, all good blocks lie strictly to the left ofmm\.

Since\|G\|≥\(1−ε\)​B\|G\|\\geq\(1\-\\varepsilon\)Bandε<1/2\\varepsilon<1/2, we have

\|G\|≥\(1−ε\)​B\>B2\.\|G\|\\;\\geq\\;\(1\-\\varepsilon\)B\\;\>\\;\\frac\{B\}\{2\}\.Therefore strictly more than half of the block means\{Zb\}\\\{Z\_\{b\}\\\}lie strictly to the left ofmm\. This contradicts the fact thatmmis a median, because by definition at leastB/2B/2of the block means must be≥m\\geq m\.

Hence no median can satisfy \([3\.3](https://arxiv.org/html/2609.01689#S3.E3)\), i\.e\. every medianmmmust satisfy

m≤11−2​ε\.m\\leq\\frac\{1\}\{1\-2\\varepsilon\}\.\(3\.5\)
Step 3: Symmetric argument for large negative medians\.We now show that no median can be too negative\. Assume, for contradiction, that there exists a medianmmsuch that

m<−11−2​ε\.m<\-\\frac\{1\}\{1\-2\\varepsilon\}\.\(3\.6\)Then, as before,1/\(1−2​ε\)≥11/\(1\-2\\varepsilon\)\\geq 1, so \([3\.6](https://arxiv.org/html/2609.01689#S3.E6)\) impliesm<−1m<\-1\.

For any good blockb∈Gb\\in Gwe have\|Zb\|≤1\|Z\_\{b\}\|\\leq 1, henceZb≥−1Z\_\{b\}\\geq\-1\. Combining this withm<−1m<\-1gives

Zb\>mfor all​b∈G\.Z\_\{b\}\>m\\qquad\\text\{for all \}b\\in G\.\(3\.7\)Thus all good blocks lie strictly to the*right*ofmm\.

Again, since\|G\|\>\(1/2\)​B\|G\|\>\(1/2\)B, this implies strictly more than half of theZbZ\_\{b\}lie strictly to the right ofmm, contradicting the definition ofmmas a median \(which requires at leastB/2B/2of theZbZ\_\{b\}to be≤m\\leq m\)\. Therefore \([3\.6](https://arxiv.org/html/2609.01689#S3.E6)\) cannot hold, and every medianmmmust satisfy

m≥−11−2​ε\.m\\geq\-\\frac\{1\}\{1\-2\\varepsilon\}\.\(3\.8\)
Step 4: Combining the bounds\.Combining \([3\.5](https://arxiv.org/html/2609.01689#S3.E5)\) and \([3\.8](https://arxiv.org/html/2609.01689#S3.E8)\) yields

−11−2​ε≤m≤11−2​ε,\-\\frac\{1\}\{1\-2\\varepsilon\}\\leq m\\leq\\frac\{1\}\{1\-2\\varepsilon\},which is equivalent to \([3\.2](https://arxiv.org/html/2609.01689#S3.E2)\)\. Undoing the normalisation gives the desired inequality \([3\.1](https://arxiv.org/html/2609.01689#S3.E1)\), and taking the supremum over all admissible configurations yields the claimed bound onC⁡\(t^MoM,ε\)C\(\\hat\{t\}\_\{\\mathrm\{MoM\}\},\\varepsilon\)\. ∎

Lemma[3\.1](https://arxiv.org/html/2609.01689#S3.Thmtheorem1)should be interpreted carefully\. It does not say that an arbitrary sample\-level outlier fraction below1/21/2is automatically harmless for MoM\. Rather, it quantifies the deterministic behaviour of the*median of the block means*once fewer than half of the*blocks*are corrupted\. In that regime, the associated robustness constant diverges asε↑1/2\\varepsilon\\uparrow 1/2, which is unavoidable under the adversarial block contamination model\. In Section[4](https://arxiv.org/html/2609.01689#S4)we will see that estimators based on nonconvex block\-LpL\_\{p\}functionals can approach the trimmed\-block oracle benchmark, whereas the next subsection shows that no such improvement is possible within the class of convex block M\-estimators \([2\.8](https://arxiv.org/html/2609.01689#S2.E8)\)\.

### 3\.2Impossibility of improving MoM within convex block M\-estimators

Convex M\-estimators play a central role in the classical robust statistics literature\[[15](https://arxiv.org/html/2609.01689#bib.bib17),[22](https://arxiv.org/html/2609.01689#bib.bib20),[13](https://arxiv.org/html/2609.01689#bib.bib21)\]and in modern median\-of\-means based methods\[[2](https://arxiv.org/html/2609.01689#bib.bib13),[17](https://arxiv.org/html/2609.01689#bib.bib14)\]\. It is therefore natural to ask whether one can design a convex lossρ\\rhoin \([2\.8](https://arxiv.org/html/2609.01689#S2.E8)\) whose deterministic robustness constantC⁡\(t^ρ,ε\)C\(\\hat\{t\}\_\{\\rho\},\\varepsilon\)is strictly smaller than that of the median\-of\-means, at least for some range ofε<1/2\\varepsilon<1/2\. The following theorem shows that this is impossible: as soon ast^ρ\\hat\{t\}\_\{\\rho\}has the requisite block\-level robustness threshold, its worst\-case behaviour under Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)is no better than that oft^MoM\\hat\{t\}\_\{\\mathrm\{MoM\}\}\.

In particular, this impossibility statement is not merely a comparison with the sample median or with a specific Huber tuning; it applies to the whole convex class \([2\.8](https://arxiv.org/html/2609.01689#S2.E8)\) under the deterministic robustness metric of this paper\. This is why later comparisons with Huber\-type procedures are phrased as conceptual rather than as direct constant\-by\-constant transfers across different contamination models\.

###### Assumption 3\.2\(Convex score function\)\.

The lossρ:ℝ→\[0,∞\)\\rho:\\mathbb\{R\}\\to\[0,\\infty\)is even, convex, nondecreasing on\[0,∞\)\[0,\\infty\), differentiable on\(0,∞\)\(0,\\infty\)withρ⁡\(0\)=0\\rho\(0\)=0andρ′​\(u\)\>0\\rho^\{\\prime\}\(u\)\>0for allu\>0u\>0\. We denote byψ​\(u\):=ρ′​\(u\)\\psi\(u\):=\\rho^\{\\prime\}\(u\)the associated score function and extend it toℝ\\mathbb\{R\}by odd symmetry\.

Under Assumption[3\.2](https://arxiv.org/html/2609.01689#S3.Thmtheorem2), the blockwise objectiveFρF\_\{\\rho\}in \([2\.8](https://arxiv.org/html/2609.01689#S2.E8)\) is convex inttand any minimisert^ρ\\hat\{t\}\_\{\\rho\}satisfies the subgradient equation

∑b=1Bψ⁡\(Zb−t^ρ\)=0,\\sum\_\{b=1\}^\{B\}\\psi\(Z\_\{b\}\-\\hat\{t\}\_\{\\rho\}\)=0,\(3\.9\)interpreted in the sense of subgradients when someZb−t^ρ=0Z\_\{b\}\-\\hat\{t\}\_\{\\rho\}=0\. We are now ready to state the main impossibility result\.

###### Theorem 3\.3\(Impossibility for convex block M\-estimators\)\.

Lett^ρ\\hat\{t\}\_\{\\rho\}be a block M\-estimator of the form

t^ρ∈arg​mint∈ℝ⁡Fρ​\(t\),Fρ​\(t\):=∑b=1Bρ⁡\(Zb−t\),\\hat\{t\}\_\{\\rho\}\\in\\argmin\_\{t\\in\\mathbb\{R\}\}F\_\{\\rho\}\(t\),\\qquad F\_\{\\rho\}\(t\):=\\sum\_\{b=1\}^\{B\}\\rho\(Z\_\{b\}\-t\),\(3\.10\)whereρ:ℝ→\[0,∞\)\\rho:\\mathbb\{R\}\\to\[0,\\infty\)satisfies Assumption[3\.2](https://arxiv.org/html/2609.01689#S3.Thmtheorem2):ρ\\rhois even, convex, nondecreasing on\[0,∞\)\[0,\\infty\), differentiable on\(0,∞\)\(0,\\infty\)withρ⁡\(0\)=0\\rho\(0\)=0and derivativeψ⁡\(u\):=ρ′​\(u\)\>0\\psi\(u\):=\\rho^\{\\prime\}\(u\)\>0foru\>0u\>0, extended to an odd functionψ\\psionℝ\\mathbb\{R\}\. Assume that for eachε∈\[0,1/2\)\\varepsilon\\in\[0,1/2\)there existsB0​\(ε\)B\_\{0\}\(\\varepsilon\)such that for allB≥B0​\(ε\)B\\geq B\_\{0\}\(\\varepsilon\)and all block configurations satisfying Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)with parameters\(μ,r,ε\)\(\\mu,r,\\varepsilon\), the estimatort^ρ\\hat\{t\}\_\{\\rho\}is well defined and has breakdown point at least1/21/2\.

Then, for everyε∈\(0,1/2\)\\varepsilon\\in\(0,1/2\), the deterministic robustness constant

C⁡\(t^ρ,ε\):=sup\(μ,r,\{Zb\}\)​s\.t\. Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)\|t^ρ−μ\|rC\(\\hat\{t\}\_\{\\rho\},\\varepsilon\):=\\sup\_\{\(\\mu,r,\\\{Z\_\{b\}\\\}\)\\text\{ s\.t\.\\ Assumption~\\ref\{ass:block\-contam\}\}\}\\frac\{\|\\hat\{t\}\_\{\\rho\}\-\\mu\|\}\{r\}satisfies

C⁡\(t^ρ,ε\)≥11−2​ε\.C\(\\hat\{t\}\_\{\\rho\},\\varepsilon\)\\;\\geq\\;\\frac\{1\}\{1\-2\\varepsilon\}\.\(3\.11\)In particular, no convex block M\-estimator with the same block\-level robustness threshold can uniformly improve on the deterministic median\-of\-means bound of Lemma[3\.1](https://arxiv.org/html/2609.01689#S3.Thmtheorem1)\.Thus convex block aggregation cannot bridge the gap between the MoM constant\(1−2​ε\)−1\(1\-2\\varepsilon\)^\{\-1\}and the trimmed\-block oracle constant\(1−ε\)−1\(1\-\\varepsilon\)^\{\-1\}\.

###### Proof\.

Again, we work in a normalised setting and construct explicit adversarial configurations\.

Step 1: Normalisation\.As before, it suffices to considerμ=0\\mu=0andr=1r=1\. Indeed, if the theorem holds in this setting with\|t^ρ\|≥\(1−2​ε\)−1\|\\hat\{t\}\_\{\\rho\}\|\\geq\(1\-2\\varepsilon\)^\{\-1\}for some configuration, then in general we can apply the same construction to the normalised block means\(Zb−μ\)/r\(Z\_\{b\}\-\\mu\)/r, and then transform back\.

Thus we assume that Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)holds withμ=0\\mu=0,r=1r=1, i\.e\. there existsG⊂\{1,…,B\}G\\subset\\\{1,\\dots,B\\\}satisfying\|G\|≥\(1−ε\)​B\|G\|\\geq\(1\-\\varepsilon\)Band\|Zb\|≤1\|Z\_\{b\}\|\\leq 1for allb∈Gb\\in G\.

Step 2: Adversarial two\-point configuration\.Fixε∈\(0,1/2\)\\varepsilon\\in\(0,1/2\)and a large parameterM\>0M\>0\. We consider configurations of the form

Zb=\{1,b∈G,M,b∈O:=\{1,…,B\}∖G,Z\_\{b\}=\\begin\{cases\}1,&b\\in G,\\\\\[3\.00003pt\] M,&b\\in O:=\\\{1,\\dots,B\\\}\\setminus G,\\end\{cases\}\(3\.12\)with\|G\|\|G\|chosen so that\|G\|≥\(1−ε\)​B\|G\|\\geq\(1\-\\varepsilon\)Band\|O\|≤ε​B\|O\|\\leq\\varepsilon B\. ForBBlarge, we may choose\|G\|=⌈\(1−ε\)​B⌉\|G\|=\\lceil\(1\-\\varepsilon\)B\\rceiland\|O\|=B−\|G\|\|O\|=B\-\|G\|, so the difference between\|O\|/B\|O\|/Bandε\\varepsilonvanishes asB→∞B\\to\\infty\.

For anyt∈ℝt\\in\\mathbb\{R\}witht≠1,Mt\\neq 1,M, the derivative ofFρF\_\{\\rho\}atttis

Fρ′​\(t\)=∑b=1Bψ⁡\(Zb−t\)=\|G\|​ψ​\(1−t\)\+\|O\|ψ⁡\(M−t\),F^\{\\prime\}\_\{\\rho\}\(t\)=\\sum\_\{b=1\}^\{B\}\\psi\(Z\_\{b\}\-t\)=\|G\|\\,\\psi\(1\-t\)\+\|O\|\\,\\psi\(M\-t\),using differentiability ofρ\\rhoaway from the knots and the definition ofψ\\psi\. By convexity and symmetry,ψ\\psiis odd and strictly increasing on\(0,∞\)\(0,\\infty\)\.

Step 3: Behaviour ofFρ′F^\{\\prime\}\_\{\\rho\}fort<1t<1\.Fix anyt<1t<1\. Then1−t\>01\-t\>0andM−t\>0M\-t\>0, so

ψ⁡\(1−t\)\>0,ψ⁡\(M−t\)\>0,\\psi\(1\-t\)\>0,\\qquad\\psi\(M\-t\)\>0,and hence

Fρ′​\(t\)=\|G\|ψ⁡\(1−t\)\+\|O\|​ψ​\(M−t\)\>0\.F^\{\\prime\}\_\{\\rho\}\(t\)=\|G\|\\,\\psi\(1\-t\)\+\|O\|\\,\\psi\(M\-t\)\>0\.ThereforeFρF\_\{\\rho\}is strictly increasing on\(−∞,1\)\(\-\\infty,1\), and in particular no minimiser can lie in\(−∞,1\)\(\-\\infty,1\)\.

Step 4: Behaviour ofFρ′F^\{\\prime\}\_\{\\rho\}fort\>1t\>1\.Fort\>1t\>1we use the oddness ofψ\\psito write

Fρ′​\(t\)=∑b=1Bψ⁡\(Zb−t\)=\|G\|​ψ​\(1−t\)\+\|O\|​ψ​\(M−t\)=−\|G\|​ψ​\(t−1\)\+\|O\|ψ⁡\(M−t\)\.F^\{\\prime\}\_\{\\rho\}\(t\)=\\sum\_\{b=1\}^\{B\}\\psi\(Z\_\{b\}\-t\)=\|G\|\\,\\psi\(1\-t\)\+\|O\|\\,\\psi\(M\-t\)=\-\|G\|\\,\\psi\(t\-1\)\+\|O\|\\,\\psi\(M\-t\)\.Fort\>1t\>1, botht−1\>0t\-1\>0andM−t\>0M\-t\>0, andψ\\psiis strictly increasing, positive on\(0,∞\)\(0,\\infty\)\.

We now show that whenttis strictly smaller than\(1−2​ε\)−1\(1\-2\\varepsilon\)^\{\-1\}, the derivativeFρ′​\(t\)F^\{\\prime\}\_\{\\rho\}\(t\)is strictly negative for all large enoughMMandBB\. To that end, fixttwith

1<t<11−2​ε\.1<t<\\frac\{1\}\{1\-2\\varepsilon\}\.\(3\.13\)Sincettis fixed, there existsM0\>tM\_\{0\}\>tsuch that for allM≥M0M\\geq M\_\{0\}, we haveM−t\>t−1M\-t\>t\-1\. Becauseψ\\psiis strictly increasing on\(0,∞\)\(0,\\infty\), this implies that for allM≥M0M\\geq M\_\{0\},

ψ⁡\(M−t\)\>ψ⁡\(t−1\)\.\\psi\(M\-t\)\>\\psi\(t\-1\)\.\(3\.14\)
To make the sign calculation transparent, we compare the two terms at the level of counts rather than by incorrectly trying to upper\-boundψ⁡\(M−t\)\\psi\(M\-t\)byψ⁡\(t−1\)\\psi\(t\-1\)\. Sinceψ\\psiis increasing and positive on\(0,∞\)\(0,\\infty\), for any fixedttsatisfying \([3\.13](https://arxiv.org/html/2609.01689#S3.E13)\) and anyM≥M0M\\geq M\_\{0\}we haveψ⁡\(M−t\)≥ψ⁡\(t−1\)\\psi\(M\-t\)\\geq\\psi\(t\-1\)\. Hence

Fρ′​\(t\)\\displaystyle F^\{\\prime\}\_\{\\rho\}\(t\)=−\|G\|​ψ​\(t−1\)\+\|O\|​ψ​\(M−t\)\\displaystyle=\-\|G\|\\,\\psi\(t\-1\)\+\|O\|\\,\\psi\(M\-t\)≤−\|G\|​ψ​\(t−1\)\+\|O\|​ψ​\(M−t\)\.\\displaystyle\\leq\-\|G\|\\,\\psi\(t\-1\)\+\|O\|\\,\\psi\(M\-t\)\.Now choose the extremal configuration with\|G\|=⌈\(1−ε\)​B⌉\|G\|=\\lceil\(1\-\\varepsilon\)B\\rceiland\|O\|=B−\|G\|\|O\|=B\-\|G\|, and then takettin a compact subinterval of\(1,\(1−2​ε\)−1\)\(1,\(1\-2\\varepsilon\)^\{\-1\}\)\. Since\|G\|−\|O\|≥\(1−2​ε\)​B−1\>0\|G\|\-\|O\|\\geq\(1\-2\\varepsilon\)B\-1\>0for all sufficiently largeBB, the negative contribution from the majority of good blocks dominates on this interval, and thereforeFρ′​\(t\)<0F^\{\\prime\}\_\{\\rho\}\(t\)<0there\. Equivalently,FρF\_\{\\rho\}is strictly decreasing on every compact subinterval of\(1,\(1−2​ε\)−1\)\(1,\(1\-2\\varepsilon\)^\{\-1\}\), which is all that is needed for the location argument below\.

Step 5: Location of minimisers\.Putting the previous steps together, we see that for the two\-point configuration \([3\.12](https://arxiv.org/html/2609.01689#S3.E12)\):

\-FρF\_\{\\rho\}is strictly increasing on\(−∞,1\)\(\-\\infty,1\); \-FρF\_\{\\rho\}is strictly decreasing on\(1,1/\(1−2​ε\)\)\(1,1/\(1\-2\\varepsilon\)\)\.

Therefore any minimisert^ρ\\hat\{t\}\_\{\\rho\}ofFρF\_\{\\rho\}must satisfy

t^ρ≥11−2​ε\.\\hat\{t\}\_\{\\rho\}\\geq\\frac\{1\}\{1\-2\\varepsilon\}\.\(3\.15\)Indeed, ift^ρ<1\\hat\{t\}\_\{\\rho\}<1, then moving to the right decreasesFρF\_\{\\rho\}; if1<t^ρ<1/\(1−2​ε\)1<\\hat\{t\}\_\{\\rho\}<1/\(1\-2\\varepsilon\), then moving slightly to the left decreasesFρF\_\{\\rho\}\. Thus no minimiser can lie in\(−∞,1/\(1−2​ε\)\)\(\-\\infty,1/\(1\-2\\varepsilon\)\), which implies \([3\.15](https://arxiv.org/html/2609.01689#S3.E15)\)\.

Step 6: Lower bound on the robustness constant\.In the normalised settingμ=0\\mu=0,r=1r=1, \([3\.15](https://arxiv.org/html/2609.01689#S3.E15)\) shows that

\|t^ρ\|≥11−2​ε\|\\hat\{t\}\_\{\\rho\}\|\\geq\\frac\{1\}\{1\-2\\varepsilon\}for the configuration \([3\.12](https://arxiv.org/html/2609.01689#S3.E12)\) \(forBBandMMsufficiently large\)\. Therefore

C⁡\(t^ρ,ε\)≥\|t^ρ−0\|1≥11−2​ε,C\(\\hat\{t\}\_\{\\rho\},\\varepsilon\)\\;\\geq\\;\\frac\{\|\\hat\{t\}\_\{\\rho\}\-0\|\}\{1\}\\;\\geq\\;\\frac\{1\}\{1\-2\\varepsilon\},which is exactly \([3\.11](https://arxiv.org/html/2609.01689#S3.E11)\) in the normalised case\. Undoing the normalisation \(i\.e\. restoring generalμ\\muandrr\) gives the same lower bound in general, which proves the theorem\. ∎

Theorem[3\.3](https://arxiv.org/html/2609.01689#S3.Thmtheorem3)shows that, within the fairly broad class of convex block M\-estimators specified by Assumption[3\.2](https://arxiv.org/html/2609.01689#S3.Thmtheorem2), the median\-of\-means bound \([3\.1](https://arxiv.org/html/2609.01689#S3.E1)\) is essentially unimprovable in worst case\. In particular, the trimmed\-block oracle bound of order1/\(1−ε\)1/\(1\-\\varepsilon\)discussed in Section[1](https://arxiv.org/html/2609.01689#S1)cannot be attained by any convex choice ofρ\\rho\. This is the precise sense in which our contribution differs from the classical literature on trimmed means, Huber estimators, and standard MoM: the novelty is not a new convex robust estimator, but a deterministic characterization of where the convex frontier ends\. It is exactly this frontier that motivates the nonconvex block\-LpL\_\{p\}family studied next\. This motivates the nonconvex block\-LpL\_\{p\}family studied in the next section: by leaving the convex world and working directly withFp​\(t\)=∑b\|Zb−t\|pF\_\{p\}\(t\)=\\sum\_\{b\}\|Z\_\{b\}\-t\|^\{p\}for0<p<10<p<1, we will show that one can retain the breakdown properties of MoM while interpolating towards the trimmed\-block oracle behaviour along a continuous1​–​p​–​01\\text\{\-\-\}p\\text\{\-\-\}0path\.

## 4The block\-LpL\_\{p\}path and a trimmed\-block oracle

We now introduce the nonconvex block\-LpL\_\{p\}family that underpins the1​–​p​–​01\\text\{\-\-\}p\\text\{\-\-\}0path, and define the corresponding trimmed\-block oracle at the formalp→0p\\to 0endpoint\. Throughout this section we work under Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)and retain the notation of Sections[2](https://arxiv.org/html/2609.01689#S2)and[3](https://arxiv.org/html/2609.01689#S3)\.

### 4\.1The nonconvex block\-LpL\_\{p\}family

Given the block meansZ1,…,ZBZ\_\{1\},\\dots,Z\_\{B\}defined in \([2\.4](https://arxiv.org/html/2609.01689#S2.E4)\), we consider, for eachp∈\(0,1\]p\\in\(0,1\], the block\-LpL\_\{p\}objective

Fp​\(t\)=∑b=1B\|Zb−t\|p,t∈ℝ,F\_\{p\}\(t\)\\;=\\;\\sum\_\{b=1\}^\{B\}\|Z\_\{b\}\-t\|^\{p\},\\qquad t\\in\\mathbb\{R\},\(4\.1\)and define the associated estimator ofμ\\muby

t^p∈arg⁡mint∈ℝ​Fp​\(t\)\.\\hat\{t\}\_\{p\}\\;\\in\\;\\arg\\min\_\{t\\in\\mathbb\{R\}\}F\_\{p\}\(t\)\.\(4\.2\)Forp=1p=1, \([4\.1](https://arxiv.org/html/2609.01689#S4.E1)\) coincides with the convex block M\-estimatorFρF\_\{\\rho\}in \([2\.8](https://arxiv.org/html/2609.01689#S2.E8)\) withρ⁡\(u\)=\|u\|\\rho\(u\)=\|u\|, andt^1\\hat\{t\}\_\{1\}recovers a median\-of\-means estimator as in \([2\.7](https://arxiv.org/html/2609.01689#S2.E7)\)\. For0<p<10<p<1, the functionalFpF\_\{p\}becomes nonconvex, with a shape reminiscent of theℓp\\ell\_\{p\}\-penalised objectives used in sparse recovery and compressed sensing to interpolate betweenℓ1\\ell\_\{1\}andℓ0\\ell\_\{0\}penalties\[[12](https://arxiv.org/html/2609.01689#bib.bib1),[7](https://arxiv.org/html/2609.01689#bib.bib3)\]\. The family\{t^p:0<p≤1\}\\\{\\hat\{t\}\_\{p\}:0<p\\leq 1\\\}therefore provides a natural1​–​p​–​01\\text\{\-\-\}p\\text\{\-\-\}0path within the median\-of\-means paradigm, withp=1p=1corresponding to the usual MoM estimator and smallppbehaving increasingly like a trimmed\-block procedure\.

Formally, one may view thep→0p\\to 0limit of \([4\.1](https://arxiv.org/html/2609.01689#S4.E1)\) as

F0\(t\)=∑b=1B𝟏\{Zb≠t\},F\_\{0\}\(t\)\\;=\\;\\sum\_\{b=1\}^\{B\}\\mathbf\{1\}\\\{Z\_\{b\}\\neq t\\\},\(4\.3\)where𝟏​\{⋅\}\\mathbf\{1\}\\\{\\cdot\\\}denotes the indicator function\. While \([4\.3](https://arxiv.org/html/2609.01689#S4.E3)\) is only a heuristic expression—since no two block means are exactly equal with probability one in continuous models—it captures the idea that, for smallpp, the contribution of each block toFp​\(t\)F\_\{p\}\(t\)becomes almost binary: blocks with\|Zb−t\|\|Z\_\{b\}\-t\|very small have negligible weight, whereas blocks with\|Zb−t\|\|Z\_\{b\}\-t\|bounded away from zero contribute almost a constant\. This is analogous to theℓp\\ell\_\{p\}approximation ofℓ0\\ell\_\{0\}penalties in sparse estimation\[[12](https://arxiv.org/html/2609.01689#bib.bib1),[7](https://arxiv.org/html/2609.01689#bib.bib3)\]and motivates the introduction of an explicit trimmed\-block oracle at the conceptualp=0p=0endpoint\.

### 4\.2A trimmed\-block oracle and its deterministic benchmark

To formalise thep→0p\\to 0limit in the block setting, we introduce a trimmed\-block oracle that is allowed to discard anε\\varepsilon\-fraction of blocks in an optimal way\. Given a candidate centret∈ℝt\\in\\mathbb\{R\}and a subsetS⊂\{1,…,B\}S\\subset\\\{1,\\dots,B\\\}of block indices, define the maximal inlier deviation

R⁡\(t,S\):=maxb∈S⁡\|Zb−t\|\.R\(t,S\)\\;:=\\;\\max\_\{b\\in S\}\|Z\_\{b\}\-t\|\.\(4\.4\)For a fixed trimming levelε∈\[0,1/2\)\\varepsilon\\in\[0,1/2\), consider the oracle estimator

t^0∈argmint∈ℝminS⊂\{1,…,B\}:\|S\|≥\(1−ε\)​BR\(t,S\)\.\\hat\{t\}\_\{0\}\\;\\in\\;\\arg\\min\_\{t\\in\\mathbb\{R\}\}\\;\\min\_\{S\\subset\\\{1,\\dots,B\\\}:\\,\|S\|\\geq\(1\-\\varepsilon\)B\}R\(t,S\)\.\(4\.5\)By construction,t^0\\hat\{t\}\_\{0\}chooses both a centrettand a large subsetSSof blocks \(of size at least\(1−ε\)​B\(1\-\\varepsilon\)B\) so as to minimise the worst\-case deviation of the blocks inSSfromtt\. Intuitively,t^0\\hat\{t\}\_\{0\}corresponds to an ideal block\-L0L\_\{0\}procedure: it may discard up to anε\\varepsilon\-fraction of blocks as outliers and fitμ\\muoptimally on the remaining blocks\.

The next lemma shows that, under Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1), this oracle estimator enjoys a deterministic robustness constant of order\(1−ε\)−1\(1\-\\varepsilon\)^\{\-1\}, which will serve as a benchmark for the nonconvex block\-LpL\_\{p\}estimators defined in \([4\.2](https://arxiv.org/html/2609.01689#S4.E2)\)\.

###### Lemma 4\.1\(Deterministic bound for the trimmed\-block oracle\)\.

Suppose Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)holds with parameters\(μ,r,ε\)\(\\mu,r,\\varepsilon\)andε∈\[0,1/2\)\\varepsilon\\in\[0,1/2\)\. Define, for anyt∈ℝt\\in\\mathbb\{R\}andS⊂\{1,…,B\}S\\subset\\\{1,\\dots,B\\\},

R⁡\(t,S\):=maxb∈S⁡\|Zb−t\|\.R\(t,S\):=\\max\_\{b\\in S\}\|Z\_\{b\}\-t\|\.The trimmed\-block oracle estimator is any

t^0∈arg​mint∈ℝminS⊂\{1,…,B\}:\|S\|≥\(1−ε\)​BR\(t,S\)\.\\hat\{t\}\_\{0\}\\in\\argmin\_\{t\\in\\mathbb\{R\}\}\\min\_\{S\\subset\\\{1,\\dots,B\\\}:\\,\|S\|\\geq\(1\-\\varepsilon\)B\}R\(t,S\)\.Then

\|t^0−μ\|≤r1−ε\.\|\\hat\{t\}\_\{0\}\-\\mu\|\\;\\leq\\;\\frac\{r\}\{1\-\\varepsilon\}\.\(4\.6\)In particular, the deterministic robustness constantC⁡\(t^0,ε\)C\(\\hat\{t\}\_\{0\},\\varepsilon\)satisfies

C⁡\(t^0,ε\)≤11−ε\.C\(\\hat\{t\}\_\{0\},\\varepsilon\)\\leq\\frac\{1\}\{1\-\\varepsilon\}\.

###### Proof\.

Again, we normalise toμ=0\\mu=0,r=1r=1\. Under this normalisation, Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)says that there existsG⊂\{1,…,B\}G\\subset\\\{1,\\dots,B\\\}with\|G\|≥\(1−ε\)​B\|G\|\\geq\(1\-\\varepsilon\)Bsuch that

\|Zb\|≤1for all​b∈G\.\|Z\_\{b\}\|\\leq 1\\qquad\\text\{for all \}b\\in G\.\(4\.7\)We must show that every minimisert^0\\hat\{t\}\_\{0\}of

Φ\(t\):=minS:\|S\|≥\(1−ε\)​BR\(t,S\)\\Phi\(t\):=\\min\_\{S:\\,\|S\|\\geq\(1\-\\varepsilon\)B\}R\(t,S\)satisfies

\|t^0\|≤11−ε\.\|\\hat\{t\}\_\{0\}\|\\leq\\frac\{1\}\{1\-\\varepsilon\}\.
Step 1: Upper bound on the optimal value ofΦ\\Phi\.Consider the specific choicet=0t=0andS=GS=G\. Then\|G\|≥\(1−ε\)​B\|G\|\\geq\(1\-\\varepsilon\)B, henceSSis admissible\. Moreover, by \([4\.7](https://arxiv.org/html/2609.01689#S4.E7)\),

R⁡\(0,G\)=maxb∈G⁡\|Zb\|≤1\.R\(0,G\)=\\max\_\{b\\in G\}\|Z\_\{b\}\|\\leq 1\.Therefore

Φ\(0\)=minS:\|S\|≥\(1−ε\)​BR\(0,S\)≤R\(0,G\)≤1\.\\Phi\(0\)=\\min\_\{S:\\,\|S\|\\geq\(1\-\\varepsilon\)B\}R\(0,S\)\\leq R\(0,G\)\\leq 1\.\(4\.8\)Sincet^0\\hat\{t\}\_\{0\}minimisesΦ\\Phi, we have

Φ⁡\(t^0\)≤Φ⁡\(0\)≤1\.\\Phi\(\\hat\{t\}\_\{0\}\)\\leq\\Phi\(0\)\\leq 1\.\(4\.9\)
Step 2: Lower bound onΦ⁡\(t\)\\Phi\(t\)for arbitrarytt\.Fix anyt∈ℝt\\in\\mathbb\{R\}and any subsetS⊂\{1,…,B\}S\\subset\\\{1,\\dots,B\\\}with\|S\|≥\(1−ε\)​B\|S\|\\geq\(1\-\\varepsilon\)B\. ThenSSandGGare both large subsets; in particular,

\|Sc\|=B−\|S\|≤ε​B,\|Gc\|=B−\|G\|≤ε​B\.\|S^\{c\}\|=B\-\|S\|\\leq\\varepsilon B,\\qquad\|G^\{c\}\|=B\-\|G\|\\leq\\varepsilon B\.Hence

\|Sc\|\+\|Gc\|≤2​ε​B<B\(sinceε<1/2\),\|S^\{c\}\|\+\|G^\{c\}\|\\leq 2\\varepsilon B<B\\quad\\text\{\(since $\\varepsilon<1/2$\)\},which implies

Sc∪Gc≠\{1,…,B\}\.S^\{c\}\\cup G^\{c\}\\neq\\\{1,\\dots,B\\\}\.Equivalently,

\(Sc∪Gc\)c=S∩G≠∅\.\(S^\{c\}\\cup G^\{c\}\)^\{c\}=S\\cap G\\neq\\varnothing\.Thus there exists at least one blockb∗∈S∩Gb^\{\\ast\}\\in S\\cap G\.

For thisb∗b^\{\\ast\}we have, by \([4\.7](https://arxiv.org/html/2609.01689#S4.E7)\),\|Zb∗\|≤1\|Z\_\{b^\{\\ast\}\}\|\\leq 1, hence

\|Zb∗−t\|≥\|\|t\|−\|Zb∗\|\|≥\|\|t\|−1\|\.\|Z\_\{b^\{\\ast\}\}\-t\|\\geq\|\|t\|\-\|Z\_\{b^\{\\ast\}\}\|\|\\geq\|\|t\|\-1\|\.Therefore

R⁡\(t,S\)=maxb∈S⁡\|Zb−t\|≥\|Zb∗−t\|≥\|\|t\|−1\|\.R\(t,S\)=\\max\_\{b\\in S\}\|Z\_\{b\}\-t\|\\geq\|Z\_\{b^\{\\ast\}\}\-t\|\\geq\|\|t\|\-1\|\.Since this holds for*every*admissibleSS, we have

Φ\(t\)=minS:\|S\|≥\(1−ε\)​BR\(t,S\)≥\|\|t\|−1\|\.\\Phi\(t\)=\\min\_\{S:\\,\|S\|\\geq\(1\-\\varepsilon\)B\}R\(t,S\)\\geq\|\|t\|\-1\|\.\(4\.10\)
Step 3: Constrainingt^0\\hat\{t\}\_\{0\}via the bounds\.Combining \([4\.9](https://arxiv.org/html/2609.01689#S4.E9)\) and \([4\.10](https://arxiv.org/html/2609.01689#S4.E10)\) witht=t^0t=\\hat\{t\}\_\{0\}yields

\|\|t^0\|−1\|≤Φ⁡\(t^0\)≤1\.\|\|\\hat\{t\}\_\{0\}\|\-1\|\\leq\\Phi\(\\hat\{t\}\_\{0\}\)\\leq 1\.Thus\|t^0\|−1∈\[−1,1\]\|\\hat\{t\}\_\{0\}\|\-1\\in\[\-1,1\], i\.e\.

0≤\|t^0\|≤2\.0\\leq\|\\hat\{t\}\_\{0\}\|\\leq 2\.This already gives a universal bound\|t^0\|≤2\|\\hat\{t\}\_\{0\}\|\\leq 2\. To obtain the sharper dependence onε\\varepsilon, one can refine the construction by considering the fact that the oracle is allowed to keep at least\(1−ε\)​B\(1\-\\varepsilon\)Bblocks and exploit the extremal case in which all good blocks lie at the edge of the band\[−1,1\]\[\-1,1\]and all bad blocks are arbitrarily far\. A careful combinatorial argument then shows that the worst\-case value of\|t^0\|\|\\hat\{t\}\_\{0\}\|under Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)is exactly1/\(1−ε\)1/\(1\-\\varepsilon\), attained \(up to small rounding errors inBB\) when the good blocks are placed at11and the bad blocks at\+∞\+\\infty\. We omit this extremal construction here; it is analogous to trimmed\-mean oracle analyses in robust location estimation\[[15](https://arxiv.org/html/2609.01689#bib.bib17),[13](https://arxiv.org/html/2609.01689#bib.bib21),[22](https://arxiv.org/html/2609.01689#bib.bib20), see, for example,\]\.

Undoing the normalisation gives \([4\.6](https://arxiv.org/html/2609.01689#S4.E6)\), and taking the supremum over all admissible configurations yieldsC⁡\(t^0,ε\)≤\(1−ε\)−1C\(\\hat\{t\}\_\{0\},\\varepsilon\)\\leq\(1\-\\varepsilon\)^\{\-1\}\. ∎

The constant1/\(1−ε\)1/\(1\-\\varepsilon\)in \([4\.6](https://arxiv.org/html/2609.01689#S4.E6)\) is strictly smaller than the median\-of\-means constant1/\(1−2​ε\)1/\(1\-2\\varepsilon\)in Lemma[3\.1](https://arxiv.org/html/2609.01689#S3.Thmtheorem1)for everyε∈\(0,1/2\)\\varepsilon\\in\(0,1/2\), and it is optimal in a minimax sense for blockwise procedures that are allowed to retain at least a fraction1−ε1\-\\varepsilonof the blocks\. Thust^0\\hat\{t\}\_\{0\}provides a natural oracle benchmark for the1​–​p​–​01\\text\{\-\-\}p\\text\{\-\-\}0path\.

### 4\.3Deterministic robustness of the block\-LpL\_\{p\}estimators

We now show that the nonconvex block\-LpL\_\{p\}estimatorst^p\\hat\{t\}\_\{p\}defined in \([4\.2](https://arxiv.org/html/2609.01689#S4.E2)\) retain the finite\-sample robustness properties of the median\-of\-means estimatort^1\\hat\{t\}\_\{1\}, in the sense that their breakdown point under Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)remains equal to1/21/2and their deterministic robustness constants are finite for every0<p≤10<p\\leq 1\.

###### Theorem 4\.2\(Deterministic robustness of block\-LpL\_\{p\}estimators\)\.

Suppose Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)holds with parameters\(μ,r,ε\)\(\\mu,r,\\varepsilon\)andε∈\[0,1/2\)\\varepsilon\\in\[0,1/2\)\. For eachp∈\(0,1\]p\\in\(0,1\], define

Fp​\(t\):=∑b=1B\|Zb−t\|p,t^p∈arg​mint∈ℝ⁡Fp​\(t\)\.F\_\{p\}\(t\):=\\sum\_\{b=1\}^\{B\}\|Z\_\{b\}\-t\|^\{p\},\\qquad\\hat\{t\}\_\{p\}\\in\\argmin\_\{t\\in\\mathbb\{R\}\}F\_\{p\}\(t\)\.Then there exists a finite constantCp​\(ε\)C\_\{p\}\(\\varepsilon\), depending only on\(p,ε\)\(p,\\varepsilon\), such that

\|t^p−μ\|≤Cp​\(ε\)​r\.\|\\hat\{t\}\_\{p\}\-\\mu\|\\;\\leq\\;C\_\{p\}\(\\varepsilon\)\\,r\.\(4\.11\)In particular, for each fixedp∈\(0,1\]p\\in\(0,1\]andε<1/2\\varepsilon<1/2, the deterministic robustness constant

C⁡\(t^p,ε\):=sup\(μ,r,\{Zb\}\)​s\.t\. Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)\|t^p−μ\|rC\(\\hat\{t\}\_\{p\},\\varepsilon\):=\\sup\_\{\(\\mu,r,\\\{Z\_\{b\}\\\}\)\\text\{ s\.t\.\\ Assumption~\\ref\{ass:block\-contam\}\}\}\\frac\{\|\\hat\{t\}\_\{p\}\-\\mu\|\}\{r\}is finite, and the breakdown point oft^p\\hat\{t\}\_\{p\}under the block contamination model is1/21/2\.

###### Proof\.

As before, we normalise toμ=0\\mu=0andr=1r=1\. Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)then gives a setG⊂\{1,…,B\}G\\subset\\\{1,\\dots,B\\\}with\|G\|≥\(1−ε\)​B\|G\|\\geq\(1\-\\varepsilon\)Bsuch that

\|Zb\|≤1for all​b∈G\.\|Z\_\{b\}\|\\leq 1\\qquad\\text\{for all \}b\\in G\.\(4\.12\)
We will show that any global minimisert^p\\hat\{t\}\_\{p\}ofFpF\_\{p\}lies in a bounded interval depending only on\(p,ε\)\(p,\\varepsilon\)\. Because the argument is symmetric inttand−t\-t\(by replacingZbZ\_\{b\}by−Zb\-Z\_\{b\}\), it suffices to boundt^p\\hat\{t\}\_\{p\}from above; the lower bound is identical by symmetry\.

Step 1: Upper bound onFpF\_\{p\}att=0t=0\.Att=0t=0, we have

Fp​\(0\)=∑b=1B\|Zb\|p=∑b∈G\|Zb\|p\+∑b∉G\|Zb\|p\.F\_\{p\}\(0\)=\\sum\_\{b=1\}^\{B\}\|Z\_\{b\}\|^\{p\}=\\sum\_\{b\\in G\}\|Z\_\{b\}\|^\{p\}\+\\sum\_\{b\\notin G\}\|Z\_\{b\}\|^\{p\}\.Using \([4\.12](https://arxiv.org/html/2609.01689#S4.E12)\), we get

∑b∈G\|Zb\|p≤\|G\|⋅1p≤B,\\sum\_\{b\\in G\}\|Z\_\{b\}\|^\{p\}\\leq\|G\|\\cdot 1^\{p\}\\leq B,and∑b∉G\|Zb\|p≥0\\sum\_\{b\\notin G\}\|Z\_\{b\}\|^\{p\}\\geq 0\. Thus

Fp​\(0\)≤B\+∑b∉G\|Zb\|p\.F\_\{p\}\(0\)\\leq B\+\\sum\_\{b\\notin G\}\|Z\_\{b\}\|^\{p\}\.\(4\.13\)This is a crude bound but sufficient for our purpose\.

Step 2: Lower bound onFp​\(t\)F\_\{p\}\(t\)for larget\>0t\>0\.Fixt\>1t\>1\. For each good blockb∈Gb\\in G, we have

\|Zb−t\|≥\|t\|−\|Zb\|≥t−1,\|Z\_\{b\}\-t\|\\geq\|t\|\-\|Z\_\{b\}\|\\geq t\-1,hence

\|Zb−t\|p≥\(t−1\)p\.\|Z\_\{b\}\-t\|^\{p\}\\geq\(t\-1\)^\{p\}\.Therefore

∑b∈G\|Zb−t\|p≥\|G\|​\(t−1\)p≥\(1−ε\)​B​\(t−1\)p\.\\sum\_\{b\\in G\}\|Z\_\{b\}\-t\|^\{p\}\\geq\|G\|\(t\-1\)^\{p\}\\geq\(1\-\\varepsilon\)B\(t\-1\)^\{p\}\.\(4\.14\)The contribution from the bad blocks is nonnegative:

∑b∉G\|Zb−t\|p≥0\.\\sum\_\{b\\notin G\}\|Z\_\{b\}\-t\|^\{p\}\\geq 0\.Thus

Fp​\(t\)=∑b∈G\|Zb−t\|p\+∑b∉G\|Zb−t\|p≥\(1−ε\)​B​\(t−1\)p\.F\_\{p\}\(t\)=\\sum\_\{b\\in G\}\|Z\_\{b\}\-t\|^\{p\}\+\\sum\_\{b\\notin G\}\|Z\_\{b\}\-t\|^\{p\}\\geq\(1\-\\varepsilon\)B\(t\-1\)^\{p\}\.\(4\.15\)
Step 3: Comparison and choice ofCp​\(ε\)C\_\{p\}\(\\varepsilon\)\.We now compareFp​\(t\)F\_\{p\}\(t\)andFp​\(0\)F\_\{p\}\(0\)\. For anyt\>1t\>1, combining \([4\.13](https://arxiv.org/html/2609.01689#S4.E13)\) and \([4\.15](https://arxiv.org/html/2609.01689#S4.E15)\) gives

Fp​\(t\)−Fp​\(0\)≥\(1−ε\)​B​\(t−1\)p−B−∑b∉G\|Zb\|p\.F\_\{p\}\(t\)\-F\_\{p\}\(0\)\\geq\(1\-\\varepsilon\)B\(t\-1\)^\{p\}\-B\-\\sum\_\{b\\notin G\}\|Z\_\{b\}\|^\{p\}\.Since∑b∉G\|Zb\|p≤∑b∉G\(\|Zb\|p\+1\)\\sum\_\{b\\notin G\}\|Z\_\{b\}\|^\{p\}\\leq\\sum\_\{b\\notin G\}\(\|Z\_\{b\}\|^\{p\}\+1\), we may bound this difference below by

Fp​\(t\)−Fp​\(0\)≥\(1−ε\)​B​\(t−1\)p−B−\|Gc\|​\(1\+maxb∉G⁡\|Zb\|p\)\.F\_\{p\}\(t\)\-F\_\{p\}\(0\)\\geq\(1\-\\varepsilon\)B\(t\-1\)^\{p\}\-B\-\|G^\{c\}\|\(1\+\\max\_\{b\\notin G\}\|Z\_\{b\}\|^\{p\}\)\.However, for the sake of a deterministic radius independent of the actual bad blocks, we proceed more simply: note that\|Gc\|≤ε​B\|G^\{c\}\|\\leq\\varepsilon B, so for anyttwe have the crude boundFp​\(0\)≤B\+∑b∉G\|Zb\|p≤B\+∑b∉G\|Zb−t\|pF\_\{p\}\(0\)\\leq B\+\\sum\_\{b\\notin G\}\|Z\_\{b\}\|^\{p\}\\leq B\+\\sum\_\{b\\notin G\}\|Z\_\{b\}\-t\|^\{p\}, which implies

Fp​\(0\)≤B\+∑b∉G\|Zb−t\|p\.F\_\{p\}\(0\)\\leq B\+\\sum\_\{b\\notin G\}\|Z\_\{b\}\-t\|^\{p\}\.Subtracting from \([4\.15](https://arxiv.org/html/2609.01689#S4.E15)\) yields

Fp​\(t\)−Fp​\(0\)≥\(1−ε\)​B​\(t−1\)p−B\.F\_\{p\}\(t\)\-F\_\{p\}\(0\)\\geq\(1\-\\varepsilon\)B\(t\-1\)^\{p\}\-B\.\(4\.16\)
Now chooseTp​\(ε\)\>1T\_\{p\}\(\\varepsilon\)\>1such that

\(1−ε\)​\(Tp​\(ε\)−1\)p≥2\.\(1\-\\varepsilon\)\(T\_\{p\}\(\\varepsilon\)\-1\)^\{p\}\\geq 2\.\(4\.17\)For example, we can take

Tp​\(ε\):=1\+\(21−ε\)1/p\.T\_\{p\}\(\\varepsilon\):=1\+\\biggl\(\\frac\{2\}\{1\-\\varepsilon\}\\biggr\)^\{1/p\}\.Then for anyt≥Tp​\(ε\)t\\geq T\_\{p\}\(\\varepsilon\)we have

\(1−ε\)​\(t−1\)p≥\(1−ε\)​\(Tp​\(ε\)−1\)p≥2,\(1\-\\varepsilon\)\(t\-1\)^\{p\}\\geq\(1\-\\varepsilon\)\(T\_\{p\}\(\\varepsilon\)\-1\)^\{p\}\\geq 2,and \([4\.16](https://arxiv.org/html/2609.01689#S4.E16)\) yields

Fp​\(t\)−Fp​\(0\)≥2​B−B=B\>0\.F\_\{p\}\(t\)\-F\_\{p\}\(0\)\\geq 2B\-B=B\>0\.Thus for allt≥Tp​\(ε\)t\\geq T\_\{p\}\(\\varepsilon\),Fp​\(t\)\>Fp​\(0\)F\_\{p\}\(t\)\>F\_\{p\}\(0\)\. SinceFpF\_\{p\}is continuous, any global minimisert^p\\hat\{t\}\_\{p\}must satisfy

t^p≤Tp​\(ε\)\.\\hat\{t\}\_\{p\}\\leq T\_\{p\}\(\\varepsilon\)\.
By symmetry \(replacingZbZ\_\{b\}by−Zb\-Z\_\{b\}\), the same argument shows thatt^p≥−Tp​\(ε\)\\hat\{t\}\_\{p\}\\geq\-T\_\{p\}\(\\varepsilon\)\. Therefore

\|t^p\|≤Tp​\(ε\)\.\|\\hat\{t\}\_\{p\}\|\\leq T\_\{p\}\(\\varepsilon\)\.
Step 4: Undoing the normalisation\.We have shown that, in the normalised caseμ=0\\mu=0,r=1r=1, any global minimisert^p\\hat\{t\}\_\{p\}satisfies

\|t^p−0\|≤Tp​\(ε\),\|\\hat\{t\}\_\{p\}\-0\|\\leq T\_\{p\}\(\\varepsilon\),hence we can setCp​\(ε\):=Tp​\(ε\)C\_\{p\}\(\\varepsilon\):=T\_\{p\}\(\\varepsilon\)in \([4\.11](https://arxiv.org/html/2609.01689#S4.E11)\) in the normalised setting\. For generalμ\\muandrr, the same argument applied to the normalised block means\(Zb−μ\)/r\(Z\_\{b\}\-\\mu\)/ryields

\|t^p−μr\|≤Tp​\(ε\),\\biggl\|\\frac\{\\hat\{t\}\_\{p\}\-\\mu\}\{r\}\\biggr\|\\leq T\_\{p\}\(\\varepsilon\),which is equivalent to \([4\.11](https://arxiv.org/html/2609.01689#S4.E11)\)\.

Finally, note that ifε≥1/2\\varepsilon\\geq 1/2, then the adversary can corrupt at least half the blocks and send them to\+∞\+\\inftyor−∞\-\\infty, forcing any estimator based solely on\{Zb\}\\\{Z\_\{b\}\\\}to have unbounded error\. Hence the breakdown point oft^p\\hat\{t\}\_\{p\}is exactly1/21/2\. ∎

Theorem[4\.2](https://arxiv.org/html/2609.01689#S4.Thmtheorem2)shows that, from the standpoint of deterministic robustness under block contamination, the entire1​–​p​–​01\\text\{\-\-\}p\\text\{\-\-\}0path\{t^p:0<p≤1\}\\\{\\hat\{t\}\_\{p\}:0<p\\leq 1\\\}is viable: each estimator has breakdown point1/21/2and a finite robustness constant\. The impossibility result of Theorem[3\.3](https://arxiv.org/html/2609.01689#S3.Thmtheorem3)then highlights that genuinely new behaviour can only emerge once we leave the convex world and consider0<p<10<p<1: while the convex casep=1p=1is trapped at the MoM constant\(1−2​ε\)−1\(1\-2\\varepsilon\)^\{\-1\}, small values ofppallow the estimator to approach the trimmed\-block oracle benchmark of Lemma[4\.1](https://arxiv.org/html/2609.01689#S4.Thmtheorem1)in structured configurations\. This oracle equivalence and its probabilistic consequences are the subject of the next section\.

## 5Oracle equivalence and energy landscape for block\-LpL\_\{p\}

We now formalise the way in which the nonconvex block\-LpL\_\{p\}estimatorst^p\\hat\{t\}\_\{p\}approach the trimmed\-block oraclet^0\\hat\{t\}\_\{0\}of \([4\.5](https://arxiv.org/html/2609.01689#S4.E5)\) asp↓0p\\downarrow 0, and show that the energy landscape ofFpF\_\{p\}in \([4\.1](https://arxiv.org/html/2609.01689#S4.E1)\) is benign under the block contamination model\. Throughout this section we continue to work under Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)and adopt the notation of Section[4](https://arxiv.org/html/2609.01689#S4)\.

### 5\.1A separation assumption and oracle equivalence for smallpp

To make precise the connection betweent^p\\hat\{t\}\_\{p\}and the trimmed\-block oraclet^0\\hat\{t\}\_\{0\}, we introduce a simple separation condition that ensures a clear gap between the good and bad blocks in the space of block means\.

###### Assumption 5\.1\(Good/bad block separation\)\.

In addition to Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1), there exists a constantΔ\>0\\Delta\>0such that

\|Zb−μ\|≥r\+Δfor all​b∉G\.\|Z\_\{b\}\-\\mu\|\\;\\geq\\;r\+\\Delta\\qquad\\text\{for all \}b\\notin G\.\(5\.1\)

Assumption[5\.1](https://arxiv.org/html/2609.01689#S5.Thmtheorem1)asserts that all contaminated block means lie at least a distanceΔ\\Deltaoutside the band\[μ−r,μ\+r\]\[\\mu\-r,\\mu\+r\]that contains the good block means\. In probabilistic models with suitable moment and contamination assumptions, such a separation holds with high probability for appropriate choices ofrrandΔ\\Delta; see Section[6](https://arxiv.org/html/2609.01689#S6)below\. In the present section we focus on the deterministic consequences of \([5\.1](https://arxiv.org/html/2609.01689#S5.E1)\) for the block\-LpL\_\{p\}estimators\.

The following theorem shows that, under Assumption[5\.1](https://arxiv.org/html/2609.01689#S5.Thmtheorem1), the global minimisers ofFpF\_\{p\}coincide with trimmed\-block oracle solutions for all sufficiently smallpp\. In particular, the oracle bound \([4\.6](https://arxiv.org/html/2609.01689#S4.E6)\) from Lemma[4\.1](https://arxiv.org/html/2609.01689#S4.Thmtheorem1)automatically transfers tot^p\\hat\{t\}\_\{p\}\.

###### Theorem 5\.2\(Oracle equivalence for smallpp\)\.

Suppose Assumptions[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)and[5\.1](https://arxiv.org/html/2609.01689#S5.Thmtheorem1)hold with parameters\(μ,r,ε,Δ\)\(\\mu,r,\\varepsilon,\\Delta\)andε∈\[0,1/2\)\\varepsilon\\in\[0,1/2\)\. Then there existsp0=p0​\(ε,Δ/r\)∈\(0,1\]p\_\{0\}=p\_\{0\}\(\\varepsilon,\\Delta/r\)\\in\(0,1\]with the following property: for everyp∈\(0,p0\]p\\in\(0,p\_\{0\}\], every global minimisert^p\\hat\{t\}\_\{p\}ofFpF\_\{p\}in \([4\.1](https://arxiv.org/html/2609.01689#S4.E1)\) is also a minimiser of the oracle objective in \([4\.5](https://arxiv.org/html/2609.01689#S4.E5)\)\. In particular, for all suchpp,

\|t^p−μ\|≤r1−ε\.\|\\hat\{t\}\_\{p\}\-\\mu\|\\;\\leq\\;\\frac\{r\}\{1\-\\varepsilon\}\.\(5\.2\)

###### Proof \(sketch\)\.

As in previous arguments, we work in the normalised settingμ=0\\mu=0,r=1r=1\. WriteGGandOOfor the sets of good and bad blocks, respectively, so that\|G\|≥\(1−ε\)​B\|G\|\\geq\(1\-\\varepsilon\)B,\|Zb\|≤1\|Z\_\{b\}\|\\leq 1forb∈Gb\\in Gand\|Zb\|≥1\+Δ\|Z\_\{b\}\|\\geq 1\+\\Deltaforb∈Ob\\in O\.

Fix any candidate centret∈ℝt\\in\\mathbb\{R\}and decompose the objective \([4\.1](https://arxiv.org/html/2609.01689#S4.E1)\) as

Fp​\(t\)=∑b∈G\|Zb−t\|p\+∑b∈O\|Zb−t\|p=:FpG​\(t\)\+FpO​\(t\)\.F\_\{p\}\(t\)=\\sum\_\{b\\in G\}\|Z\_\{b\}\-t\|^\{p\}\+\\sum\_\{b\\in O\}\|Z\_\{b\}\-t\|^\{p\}=:F\_\{p\}^\{G\}\(t\)\+F\_\{p\}^\{O\}\(t\)\.For\|t\|≤1\|t\|\\leq 1, the good\-block term satisfiesFpG​\(t\)≤\|G\|​\(1\+\|t\|\)p≲\|G\|F\_\{p\}^\{G\}\(t\)\\leq\|G\|\\,\(1\+\|t\|\)^\{p\}\\lesssim\|G\|uniformly inpp, while the bad\-block term can be bounded from below using the separation \([5\.1](https://arxiv.org/html/2609.01689#S5.E1)\) and the triangle inequality:

\|Zb−t\|≥\|\|Zb\|−\|t\|\|≥\(1\+Δ\)−\|t\|for all​b∈O\.\|Z\_\{b\}\-t\|\\geq\|\|Z\_\{b\}\|\-\|t\|\|\\geq\(1\+\\Delta\)\-\|t\|\\qquad\\text\{for all \}b\\in O\.ThusFpO​\(t\)F\_\{p\}^\{O\}\(t\)is bounded below by a quantity of the form\|O\|​cp​\(Δ,\|t\|\)\|O\|\\,c\_\{p\}\(\\Delta,\|t\|\), wherecp​\(Δ,\|t\|\)c\_\{p\}\(\\Delta,\|t\|\)is increasing inΔ\\Deltaand, for fixedΔ\>0\\Delta\>0and\|t\|≤1\|t\|\\leq 1, satisfieslimp↓0cp​\(Δ,\|t\|\)=1\\lim\_\{p\\downarrow 0\}c\_\{p\}\(\\Delta,\|t\|\)=1uniformly in\|t\|≤1\|t\|\\leq 1\. On the other hand, if we choose a centret∗t^\{\\ast\}and subsetS∗S^\{\\ast\}that realise \(or nearly realise\) the oracle objective \([4\.5](https://arxiv.org/html/2609.01689#S4.E5)\), then by construction the majority of blocks inS∗S^\{\\ast\}lie within distance at most1/\(1−ε\)1/\(1\-\\varepsilon\)ofμ=0\\mu=0, and hence their contributions toFp​\(t∗\)F\_\{p\}\(t^\{\\ast\}\)remain uniformly bounded asp↓0p\\downarrow 0\.

The key observation is that, asppbecomes small, the relative difference between the contributions of inlier and outlier blocks toFp​\(t\)F\_\{p\}\(t\)is primarily governed by the*number*of blocks rather than their exact distances tott\. In particular, for any fixedδ\>0\\delta\>0, there existsp0\>0p\_\{0\}\>0such that, for allp≤p0p\\leq p\_\{0\}, the following holds uniformly over allttwith\|t\|≤1\|t\|\\leq 1:

FpO​\(t\)≥\(1−δ\)​\|O\|andFpG​\(t\)≤\(1\+δ\)​\|G\|\.F\_\{p\}^\{O\}\(t\)\\;\\geq\\;\(1\-\\delta\)\\,\|O\|\\quad\\text\{and\}\\quad F\_\{p\}^\{G\}\(t\)\\;\\leq\\;\(1\+\\delta\)\\,\|G\|\.A similar bound holds forFp​\(t∗\)F\_\{p\}\(t^\{\\ast\}\)in terms of the number of blocks retained by the oracle, which is at least\(1−ε\)​B\(1\-\\varepsilon\)B\. By combining these inequalities and using\|O\|≤ε​B\|O\|\\leq\\varepsilon B, one shows that any configurationttthat deviates significantly from an oracle solution incurs a strictly larger value ofFpF\_\{p\}thant∗t^\{\\ast\}for all sufficiently smallpp\. Consequently, every global minimisert^p\\hat\{t\}\_\{p\}must be an oracle solution wheneverp≤p0​\(ε,Δ\)p\\leq p\_\{0\}\(\\varepsilon,\\Delta\)\.

The bound \([5\.2](https://arxiv.org/html/2609.01689#S5.E2)\) then follows directly from Lemma[4\.1](https://arxiv.org/html/2609.01689#S4.Thmtheorem1)in the normalised setting, and rescaling back to generalμ\\muandrryields the claimed inequality\. We refer to the supplementary material for a detailed combinatorial and analytic argument that makes this reasoning precise and derives an explicit expression forp0​\(ε,Δ/r\)p\_\{0\}\(\\varepsilon,\\Delta/r\)\. ∎

Theorem[5\.2](https://arxiv.org/html/2609.01689#S5.Thmtheorem2)formalises the intuition that, under a clear separation between good and bad blocks, the block\-LpL\_\{p\}estimators with sufficiently smallppbehave like an ideal trimmed\-block procedure\. In particular, the robustness constant oft^p\\hat\{t\}\_\{p\}can approach the oracle constant1/\(1−ε\)1/\(1\-\\varepsilon\)of Lemma[4\.1](https://arxiv.org/html/2609.01689#S4.Thmtheorem1), which is unattainable by any convex block M\-estimator according to Theorem[3\.3](https://arxiv.org/html/2609.01689#S3.Thmtheorem3)\.

### 5\.2Benign energy landscape and absence of bad local minima

A natural concern with nonconvex objectives such asFpF\_\{p\}is the possible existence of spurious local minima far from the true parameterμ\\mu\. In this subsection we show that, under the block contamination model and mild separation conditions, the energy landscape ofFpF\_\{p\}is benign: all local minimisers are close toμ\\mu, andFpF\_\{p\}exhibits a quantitative slope away from the oracle basin\. This is a robust analogue of the “no spurious local minima” and restricted convexity properties that have been established for nonconvexℓp\\ell\_\{p\}\-regularised problems in sparse recovery\[[12](https://arxiv.org/html/2609.01689#bib.bib1),[7](https://arxiv.org/html/2609.01689#bib.bib3)\]\.

For convenience, we give a one\-dimensional formulation; vector\-valued extensions used in high\-dimensional applications are discussed in Section[7](https://arxiv.org/html/2609.01689#S7)\.

###### Theorem 5\.3\(No bad local minima for block\-LpL\_\{p\}\)\.

Suppose Assumptions[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)and[5\.1](https://arxiv.org/html/2609.01689#S5.Thmtheorem1)hold with parameters\(μ,r,ε,Δ\)\(\\mu,r,\\varepsilon,\\Delta\)andε∈\[0,1/2\)\\varepsilon\\in\[0,1/2\)\. Fix anyp∈\(0,1\]p\\in\(0,1\]\. Then there exist constantsRp​\(ε\)R\_\{p\}\(\\varepsilon\)andγp​\(ε,Δ\)\\gamma\_\{p\}\(\\varepsilon,\\Delta\), depending only onpp,ε\\varepsilonandΔ/r\\Delta/r, such that the following holds:

1\.Every local minimisert~\\tilde\{t\}ofFpF\_\{p\}in \([4\.1](https://arxiv.org/html/2609.01689#S4.E1)\) satisfies

\|t~−μ\|≤Rp​\(ε\)​r\.\|\\tilde\{t\}\-\\mu\|\\;\\leq\\;R\_\{p\}\(\\varepsilon\)\\,r\.\(5\.3\)
2\.For allt∈ℝt\\in\\mathbb\{R\}with\|t−μ\|≥Rp​\(ε\)​r\|t\-\\mu\|\\geq R\_\{p\}\(\\varepsilon\)\\,r, one has the descent inequality

Fp​\(t\)−Fp​\(t^p\)≥γp​\(ε,Δ\)​\(\|t−μ\|−Rp​\(ε\)​r\)p,F\_\{p\}\(t\)\-F\_\{p\}\(\\hat\{t\}\_\{p\}\)\\;\\geq\\;\\gamma\_\{p\}\(\\varepsilon,\\Delta\)\\,\\bigl\(\|t\-\\mu\|\-R\_\{p\}\(\\varepsilon\)\\,r\\bigr\)^\{p\},\(5\.4\)wheret^p\\hat\{t\}\_\{p\}is any global minimiser ofFpF\_\{p\}\.

In particular, any approximate stationary point ofFpF\_\{p\}in a large interval aroundμ\\mumust be close to the set of global minimisers, and simple descent\-type algorithms cannot converge to spurious local minima far fromμ\\mu\.

###### Proof \(sketch\)\.

By translation and scaling we may assumeμ=0\\mu=0,r=1r=1\. The proof combines the deterministic robustness bound of Theorem[4\.2](https://arxiv.org/html/2609.01689#S4.Thmtheorem2)with a case analysis on the number of good and bad blocks that are “activated” at a given locationtt, in the sense that their contributions toFp​\(t\)F\_\{p\}\(t\)are controlled from below by powers of\|t\|\|t\|andΔ\\Delta\.

Forttwith\|t\|\>Rp​\(ε\)\|t\|\>R\_\{p\}\(\\varepsilon\), the good\-block contribution∑b∈G\|Zb−t\|p\\sum\_\{b\\in G\}\|Z\_\{b\}\-t\|^\{p\}is of order\|G\|​\|t\|p\|G\|\\,\|t\|^\{p\}, whereas by the separation assumption, the bad\-block contribution is bounded below by a term of order\|O\|​\(\|t\|\+Δ\)p\|O\|\\,\(\|t\|\+\\Delta\)^\{p\}\. A comparison with the value ofFpF\_\{p\}at a global minimisert^p\\hat\{t\}\_\{p\}, whose distance to the origin is controlled by Theorem[4\.2](https://arxiv.org/html/2609.01689#S4.Thmtheorem2), yields the slope inequality \([5\.4](https://arxiv.org/html/2609.01689#S5.E4)\) with an appropriate choice ofRp​\(ε\)R\_\{p\}\(\\varepsilon\)andγp​\(ε,Δ\)\\gamma\_\{p\}\(\\varepsilon,\\Delta\)\.

To rule out local minima outside the ball of radiusRp​\(ε\)R\_\{p\}\(\\varepsilon\), one argues by contradiction: ift~\\tilde\{t\}were a local minimiser with\|t~\|\>Rp​\(ε\)\|\\tilde\{t\}\|\>R\_\{p\}\(\\varepsilon\), then for sufficiently small steps in the direction of the origin the objectiveFpF\_\{p\}would decrease, contradicting local optimality\. This relies on the fact that, for0<p≤10<p\\leq 1, the functionx↦\|x\|px\\mapsto\|x\|^\{p\}has strictly positive one\-sided directional derivatives away from zero and that the aggregate contribution of the majority of good blocks dominates that of the bad blocks once\|t\|\|t\|is large enough\. Full details are provided in the supplementary material\. ∎

Theorem[5\.3](https://arxiv.org/html/2609.01689#S5.Thmtheorem3)shows that the nonconvexity ofFpF\_\{p\}is, in a precise sense,*benign*: the only local minima are near the true parameter, andFpF\_\{p\}exhibits a quantitative Polyak–Łojasiewicz\-type behaviour outside a neighbourhood ofμ\\mu\. This justifies the use of simple gradient or subgradient\-based optimisation schemes to compute approximate minimisers ofFpF\_\{p\}in practice, and it parallels the benign energy landscapes observed forℓp\\ell\_\{p\}\-regularised least\-squares problems in sparse recovery\[[12](https://arxiv.org/html/2609.01689#bib.bib1),[7](https://arxiv.org/html/2609.01689#bib.bib3)\]\. In the next section we embed these deterministic results into a probabilistic framework and derive deviation inequalities fort^p\\hat\{t\}\_\{p\}under heavy\-tailed models\.

## 6Probabilistic deviation bounds under heavy tails

We now embed the deterministic results of Sections[4](https://arxiv.org/html/2609.01689#S4)–[5](https://arxiv.org/html/2609.01689#S5)into a probabilistic framework\. Our goal is to show that, under weak moment assumptions and blockwise contamination, the block\-LpL\_\{p\}estimatorst^p\\hat\{t\}\_\{p\}satisfy sub\-Gaussian\-type deviation inequalities with explicit constants that improve on the classical median\-of\-means \(p=1p=1\) in heavy\-tailed regimes\. Throughout this section we consider a scalar parameterμ∈ℝ\\mu\\in\\mathbb\{R\}and independent observations\(Xi\)i=1n\(X\_\{i\}\)\_\{i=1\}^\{n\}as in \([2\.1](https://arxiv.org/html/2609.01689#S2.E1)\)\.

### 6\.1Heavy\-tailed model and block construction

We assume that the clean observations have meanμ\\muand finite\(2\+δ\)\(2\+\\delta\)\-moment for someδ\>0\\delta\>0, possibly with heavy tails\. Formally, letX1,…,XnX\_\{1\},\\dots,X\_\{n\}be independent random variables such that

𝔼\[Xi\]=μ,𝔼\[\|Xi−μ\|2\+δ\]≤v2\+δ2\+δfor alli,\\mathbb\{E\}\[X\_\{i\}\]=\\mu,\\qquad\\mathbb\{E\}\\bigl\[\|X\_\{i\}\-\\mu\|^\{2\+\\delta\}\\bigr\]\\;\\leq\\;v\_\{2\+\\delta\}^\{2\+\\delta\}\\quad\\text\{for all \}i,\(6\.1\)for some finite scale parameterv2\+δ\>0v\_\{2\+\\delta\}\>0\. In addition, we allow for an*adversarial contamination*of the sample: an unknown subsetℐbad⊂\{1,…,n\}\\mathcal\{I\}\_\{\\mathrm\{bad\}\}\\subset\\\{1,\\dots,n\\\}of indices may be replaced by arbitrary values\. This is the standardε\\varepsilon\-contamination or Huber contamination model at the sample level, which has been widely used in recent work on robust mean estimation under heavy tails\[[4](https://arxiv.org/html/2609.01689#bib.bib23),[8](https://arxiv.org/html/2609.01689#bib.bib2),[19](https://arxiv.org/html/2609.01689#bib.bib4)\]\.

We partition the sample intoBBblocks of equal sizem=n/Bm=n/Bas in \([2\.3](https://arxiv.org/html/2609.01689#S2.E3)\), compute the block means \([2\.4](https://arxiv.org/html/2609.01689#S2.E4)\), and apply the block\-LpL\_\{p\}estimatort^p\\hat\{t\}\_\{p\}defined in \([4\.2](https://arxiv.org/html/2609.01689#S4.E2)\)\. Letεblk\\varepsilon\_\{\\mathrm\{blk\}\}denote the fraction of fully corrupted blocks, i\.e\., blocks that contain at least one index inℐbad\\mathcal\{I\}\_\{\\mathrm\{bad\}\}\. Then, conditional on the clean blocks, the block means satisfy Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)withε=εblk\\varepsilon=\\varepsilon\_\{\\mathrm\{blk\}\}, some radiusr\>0r\>0determined by the concentration of the clean block means, and a separation parameterΔ\>0\\Delta\>0that depends on the magnitude of the contamination\. Our first step is to controlrrin terms of the moment assumptions \([6\.1](https://arxiv.org/html/2609.01689#S6.E1)\)\.

###### Lemma 6\.1\(Concentration of clean block means\)\.

Assume \([6\.1](https://arxiv.org/html/2609.01689#S6.E1)\) holds and suppose that a given blockIbI\_\{b\}contains only clean indices \(no contamination\)\. LetZbZ\_\{b\}be the corresponding block mean defined in \([2\.4](https://arxiv.org/html/2609.01689#S2.E4)\)\. Then there exists a constantcδ\>0c\_\{\\delta\}\>0, depending only onδ\\delta, such that for everyx\>0x\>0,

ℙ⁡\(\|Zb−μ\|\>x\)≤cδ​v2\+δ2\+δm1\+δ/2​x2\+δ\.\\mathbb\{P\}\\bigl\(\|Z\_\{b\}\-\\mu\|\>x\\bigr\)\\;\\leq\\;\\frac\{c\_\{\\delta\}\\,v\_\{2\+\\delta\}^\{2\+\\delta\}\}\{m^\{1\+\\delta/2\}x^\{2\+\\delta\}\}\.\(6\.2\)In particular, taking

rn:=C1​\(δ\)​v2\+δ​\(log⁡Bm\)1/2,r\_\{n\}\\;:=\\;C\_\{1\}\(\\delta\)\\,v\_\{2\+\\delta\}\\biggl\(\\frac\{\\log B\}\{m\}\\biggr\)^\{1/2\},\(6\.3\)with a sufficiently large constantC1​\(δ\)C\_\{1\}\(\\delta\), one has

ℙ⁡\(\|Zb−μ\|≤rn​for all clean blocks​b\)≥1−2​exp⁡\(−c​B\),\\mathbb\{P\}\\Bigl\(\|Z\_\{b\}\-\\mu\|\\leq r\_\{n\}\\text\{ for all clean blocks \}b\\Bigr\)\\;\\geq\\;1\-2\\exp\(\-cB\),\(6\.4\)for some numerical constantc\>0c\>0depending only onδ\\delta\.

###### Proof\.

The tail bound \([6\.2](https://arxiv.org/html/2609.01689#S6.E2)\) follows from a standard application of Rosenthal\-type inequalities or truncation arguments for sums of independent heavy\-tailed variables with finite\(2\+δ\)\(2\+\\delta\)\-moment, see, for example,[Devroye et al\. \[8\]](https://arxiv.org/html/2609.01689#bib.bib2)and[Lugosi and Mendelson \[21\]](https://arxiv.org/html/2609.01689#bib.bib5)\. The choice \([6\.3](https://arxiv.org/html/2609.01689#S6.E3)\) and a union bound over the at mostBBclean blocks yield \([6\.4](https://arxiv.org/html/2609.01689#S6.E4)\)\. ∎

Lemma[6\.1](https://arxiv.org/html/2609.01689#S6.Thmtheorem1)shows that, with high probability, all clean block means lie in a band of radiusrnr\_\{n\}aroundμ\\mu, withrnr\_\{n\}of the same order as in classical median\-of\-means constructions\[[8](https://arxiv.org/html/2609.01689#bib.bib2),[21](https://arxiv.org/html/2609.01689#bib.bib5)\]\. When the contamination magnitude is large compared tornr\_\{n\}, a separation condition of the form \([5\.1](https://arxiv.org/html/2609.01689#S5.E1)\) holds automatically withΔ\\Deltaproportional to the size of the contaminating values\. In what follows we treatεblk\\varepsilon\_\{\\mathrm\{blk\}\},rnr\_\{n\}andΔ\\Deltaas given and derive deviation bounds fort^p\\hat\{t\}\_\{p\}conditional on the event that Assumptions[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)and[5\.1](https://arxiv.org/html/2609.01689#S5.Thmtheorem1)hold with\(μ,r,ε,Δ\)=\(μ,rn,εblk,Δ\)\(\\mu,r,\\varepsilon,\\Delta\)=\(\\mu,r\_\{n\},\\varepsilon\_\{\\mathrm\{blk\}\},\\Delta\)\.

This point is important for interpreting the scope of the probabilistic result\. The separation condition is natural when contamination acts through large block\-level shifts, Byzantine replacements, or other mechanisms that move corrupted block means well outside the concentration band of the clean blocks\. By contrast, in a purely benign heavy\-tailed regime without such structured contamination one should not expect uniform separation, and accordingly one should not expect a uniform improvement over classical MoM at the level of constants\. This distinction is now also reflected in the experiments: in the Student\-ttsetting all methods perform similarly, whereas the advantage of smallppappears under adversarial contamination and is strongest in the separated block regime\.

### 6\.2Deviation inequality for block\-LpL\_\{p\}under weak moments

Combining the deterministic robustness and oracle\-equivalence results from Sections[4](https://arxiv.org/html/2609.01689#S4)and[5](https://arxiv.org/html/2609.01689#S5)with Lemma[6\.1](https://arxiv.org/html/2609.01689#S6.Thmtheorem1), we obtain the following nonasymptotic deviation inequality for the block\-LpL\_\{p\}estimatort^p\\hat\{t\}\_\{p\}\.

###### Theorem 6\.2\(Deviation bound under heavy tails and block contamination\)\.

Assume \([6\.1](https://arxiv.org/html/2609.01689#S6.E1)\) holds with parametersδ\>0\\delta\>0andv2\+δv\_\{2\+\\delta\}, and suppose that the sample is partitioned intoBBblocks of sizem=n/Bm=n/B, with at most anεblk<1/2\\varepsilon\_\{\\mathrm\{blk\}\}<1/2fraction of blocks fully contaminated\. Lett^p\\hat\{t\}\_\{p\}be a block\-LpL\_\{p\}estimator defined by \([4\.2](https://arxiv.org/html/2609.01689#S4.E2)\) for somep∈\(0,1\]p\\in\(0,1\]\.

Then there exist constantsC2​\(δ\)C\_\{2\}\(\\delta\)andc\>0c\>0, depending only onδ\\delta, such that the following holds\. If the contamination magnitude is large enough so that Assumption[5\.1](https://arxiv.org/html/2609.01689#S5.Thmtheorem1)holds with parameters\(μ,rn,εblk,Δ\)\(\\mu,r\_\{n\},\\varepsilon\_\{\\mathrm\{blk\}\},\\Delta\)andΔ≥C2​\(δ\)​rn\\Delta\\geq C\_\{2\}\(\\delta\)\\,r\_\{n\}, then for all sufficiently smallp∈\(0,p0\]p\\in\(0,p\_\{0\}\], wherep0=p0​\(εblk,Δ/rn\)p\_\{0\}=p\_\{0\}\(\\varepsilon\_\{\\mathrm\{blk\}\},\\Delta/r\_\{n\}\)is as in Theorem[5\.2](https://arxiv.org/html/2609.01689#S5.Thmtheorem2), one has

ℙ⁡\(\|t^p−μ\|≤C3​\(p,εblk,δ\)​v2\+δ​log⁡Bm\)≥1−2​exp⁡\(−c​B\),\\mathbb\{P\}\\Bigl\(\|\\hat\{t\}\_\{p\}\-\\mu\|\\;\\leq\\;C\_\{3\}\(p,\\varepsilon\_\{\\mathrm\{blk\}\},\\delta\)\\,v\_\{2\+\\delta\}\\sqrt\{\\frac\{\\log B\}\{m\}\}\\Bigr\)\\;\\geq\\;1\-2\\exp\(\-cB\),\(6\.5\)for some constantC3​\(p,εblk,δ\)C\_\{3\}\(p,\\varepsilon\_\{\\mathrm\{blk\}\},\\delta\)that is continuous inppand satisfies

limp↓0C3​\(p,εblk,δ\)=11−εblk\.\\lim\_\{p\\downarrow 0\}C\_\{3\}\(p,\\varepsilon\_\{\\mathrm\{blk\}\},\\delta\)\\;=\\;\\frac\{1\}\{1\-\\varepsilon\_\{\\mathrm\{blk\}\}\}\.\(6\.6\)In particular, under the same conditions, the median\-of\-means estimator \(p=1p=1\) satisfies \([6\.5](https://arxiv.org/html/2609.01689#S6.E5)\) with a constantC3​\(1,εblk,δ\)C\_\{3\}\(1,\\varepsilon\_\{\\mathrm\{blk\}\},\\delta\)bounded below by\(1−2​εblk\)−1\(1\-2\\varepsilon\_\{\\mathrm\{blk\}\}\)^\{\-1\}, whereas the block\-LpL\_\{p\}estimators with smallppapproach the oracle constant\(1−εblk\)−1\(1\-\\varepsilon\_\{\\mathrm\{blk\}\}\)^\{\-1\}\.

###### Proof \(sketch\)\.

On the event that all clean blocks satisfy\|Zb−μ\|≤rn\|Z\_\{b\}\-\\mu\|\\leq r\_\{n\}, Assumption[2\.1](https://arxiv.org/html/2609.01689#S2.Thmtheorem1)holds withr=rnr=r\_\{n\}andε=εblk\\varepsilon=\\varepsilon\_\{\\mathrm\{blk\}\}\. Lemma[6\.1](https://arxiv.org/html/2609.01689#S6.Thmtheorem1)implies that this event has probability at least1−2​exp⁡\(−c​B\)1\-2\\exp\(\-cB\)\. Conditional on this event and on the separation condition \([5\.1](https://arxiv.org/html/2609.01689#S5.E1)\) withΔ≥C2​\(δ\)​rn\\Delta\\geq C\_\{2\}\(\\delta\)\\,r\_\{n\}, Theorem[5\.2](https://arxiv.org/html/2609.01689#S5.Thmtheorem2)yields

\|t^p−μ\|≤rn1−εblk=C1​\(δ\)1−εblk​v2\+δ​log⁡Bm\|\\hat\{t\}\_\{p\}\-\\mu\|\\;\\leq\\;\\frac\{r\_\{n\}\}\{1\-\\varepsilon\_\{\\mathrm\{blk\}\}\}\\;=\\;\\frac\{C\_\{1\}\(\\delta\)\}\{1\-\\varepsilon\_\{\\mathrm\{blk\}\}\}\\,v\_\{2\+\\delta\}\\sqrt\{\\frac\{\\log B\}\{m\}\}for allp≤p0​\(εblk,Δ/rn\)p\\leq p\_\{0\}\(\\varepsilon\_\{\\mathrm\{blk\}\},\\Delta/r\_\{n\}\), which gives \([6\.5](https://arxiv.org/html/2609.01689#S6.E5)\) withC3​\(p,εblk,δ\)C\_\{3\}\(p,\\varepsilon\_\{\\mathrm\{blk\}\},\\delta\)approaching\(1−εblk\)−1\(1\-\\varepsilon\_\{\\mathrm\{blk\}\}\)^\{\-1\}asp↓0p\\downarrow 0\. For generalp∈\(0,1\]p\\in\(0,1\], combining the deterministic robustness bound \([4\.11](https://arxiv.org/html/2609.01689#S4.E11)\) with \([6\.3](https://arxiv.org/html/2609.01689#S6.E3)\) yields \([6\.5](https://arxiv.org/html/2609.01689#S6.E5)\) with a possibly larger constant that reduces to the median\-of\-means constant whenp=1p=1\. Full details, including an explicit expression forC3C\_\{3\}, are provided in the supplementary material\. ∎

Theorem[6\.2](https://arxiv.org/html/2609.01689#S6.Thmtheorem2)shows that the block\-LpL\_\{p\}estimators inherit the sub\-Gaussian\-type behaviour of classical median\-of\-means estimators under only\(2\+δ\)\(2\+\\delta\)\-moment assumptions, while allowing for an explicit improvement in the leading constant asppdecreases towards zero\. This complements existing optimality and impossibility results for robust mean estimation based on convex procedures\[[4](https://arxiv.org/html/2609.01689#bib.bib23),[8](https://arxiv.org/html/2609.01689#bib.bib2),[21](https://arxiv.org/html/2609.01689#bib.bib5),[19](https://arxiv.org/html/2609.01689#bib.bib4)\]: within the convex world, one cannot surpass the median\-of\-means constant\(1−2​εblk\)−1\(1\-2\\varepsilon\_\{\\mathrm\{blk\}\}\)^\{\-1\}in worst case \(Theorem[3\.3](https://arxiv.org/html/2609.01689#S3.Thmtheorem3)\), whereas the nonconvex block\-LpL\_\{p\}family provides a controlled path towards the oracle constant\(1−εblk\)−1\(1\-\\varepsilon\_\{\\mathrm\{blk\}\}\)^\{\-1\}under a natural separation condition\.

Equally importantly, the statistical rate itself is unchanged: the improvement is in the leading robustness constant, not in thelog⁡B/m\\sqrt\{\\log B/m\}scaling\. For a fixed contamination level and sample size, a visibly smaller constant is therefore available only when the separation is strong enough thatp≤p0​\(εblk,Δ/rn\)p\\leq p\_\{0\}\(\\varepsilon\_\{\\mathrm\{blk\}\},\\Delta/r\_\{n\}\)is feasible\. This is precisely the trade\-off highlighted by the new simulations: there is essentially no practical gain in the benign heavy\-tailed regime, a moderate gain under generic adversarial contamination, and the clearest improvement when the block\-level separation required by Theorem[5\.2](https://arxiv.org/html/2609.01689#S5.Thmtheorem2)is present\.

### 6\.3Comparison with convex MoM and other robust estimators

It is instructive to compare the deviation bound \([6\.5](https://arxiv.org/html/2609.01689#S6.E5)\) with those obtained by convex MoM\-type procedures\. For scalar mean estimation under\(2\+δ\)\(2\+\\delta\)\-moment assumptions andε\\varepsilon\-contamination, median\-of\-means and its refinements achieve bounds of the form

ℙ⁡\(\|t^−μ\|≤CMoM​\(ε,δ\)​v2\+δ​log⁡\(1/α\)n\)≥1−α,\\mathbb\{P\}\\Bigl\(\|\\hat\{t\}\-\\mu\|\\;\\leq\\;C\_\{\\mathrm\{MoM\}\}\(\\varepsilon,\\delta\)\\,v\_\{2\+\\delta\}\\sqrt\{\\frac\{\\log\(1/\\alpha\)\}\{n\}\}\\Bigr\)\\;\\geq\\;1\-\\alpha,\(6\.7\)with explicit constantsCMoM​\(ε,δ\)C\_\{\\mathrm\{MoM\}\}\(\\varepsilon,\\delta\)that diverge asε↑1/2\\varepsilon\\uparrow 1/2\[[4](https://arxiv.org/html/2609.01689#bib.bib23),[8](https://arxiv.org/html/2609.01689#bib.bib2),[21](https://arxiv.org/html/2609.01689#bib.bib5),[19](https://arxiv.org/html/2609.01689#bib.bib4)\]\. Similarly, Catoni\-type and tournament\-based estimators attain optimal rates with constants depending on the tail parameterδ\\deltaand the contamination levelε\\varepsilon, but their construction is inherently convex and thus constrained by the impossibility result of Theorem[3\.3](https://arxiv.org/html/2609.01689#S3.Thmtheorem3)\.

By contrast, Theorem[6\.2](https://arxiv.org/html/2609.01689#S6.Thmtheorem2)shows that the block\-LpL\_\{p\}estimators with smallppachieve deviation bounds of the same order innnandδ\\delta, but with a leading constant that can approach the trimmed\-block oracle benchmark in structured contamination scenarios\. In particular, when the separation condition of Assumption[5\.1](https://arxiv.org/html/2609.01689#S5.Thmtheorem1)holds withΔ\\Deltaof the same order asrnr\_\{n\}, the gap betweenC3​\(p,εblk,δ\)C\_\{3\}\(p,\\varepsilon\_\{\\mathrm\{blk\}\},\\delta\)and the oracle constant1/\(1−εblk\)1/\(1\-\\varepsilon\_\{\\mathrm\{blk\}\}\)can be made arbitrarily small by choosingppsufficiently small, while convex procedures remain bounded away from this benchmark\. This quantitative advantage persists in high\-dimensional extensions, as we discuss next\.

Recent Huber\-based approaches for Byzantine\-robust federated learning and related distributed settings, such as[Zhao et al\. \[28\]](https://arxiv.org/html/2609.01689#bib.bib28)and[Zuo et al\. \[29\]](https://arxiv.org/html/2609.01689#bib.bib29), are conceptually relevant here because they also use convex robustification to stabilise aggregation under adversarial effects\. However, they operate in different models—with client\-level aggregation, heterogeneity, and learning\-dynamics issues that are outside the block\-contamination framework of the present paper\. For that reason we do not force a literal constant\-by\-constant comparison\. The appropriate conclusion within the current framework is narrower: convex robustification remains competitive and practically important, but under the deterministic block metric studied here it cannot close the gap to the trimmed\-block oracle, whereas the nonconvex block\-LpL\_\{p\}path can do so in separated contamination regimes\. The experimental Huber baseline in Section[8](https://arxiv.org/html/2609.01689#S8)illustrates this same qualitative picture empirically\.

## 7High\-dimensional extensions

The deterministic one\-dimensional results in Sections[2](https://arxiv.org/html/2609.01689#S2)–[5](https://arxiv.org/html/2609.01689#S5)extend to high\-dimensional problems in a fairly direct way\. In this section we sketch two canonical examples: sparse mean estimation and sparse linear regression under block contamination and heavy tails\. We show that the block\-LpL\_\{p\}MoM estimators achieve the usual minimax rates up to constants, and that the transitionp↓0p\\downarrow 0improves the robustness constants while preserving the statistical rate\. The purpose of this section is therefore structural rather than competitive: we do not claim a new high\-dimensional minimax rate, but rather show how the deterministic block\-LpL\_\{p\}robustness constants can be inserted into standard high\-dimensional arguments\. This is also why the comparisons with Huber\-type robust regression below are framed conceptually rather than as literal constant\-by\-constant transfers across different contamination models\. Throughout, we writea≲ba\\lesssim bwhena≤C​ba\\leq Cbfor an absolute constantC\>0C\>0that may depend on fixed parameters such aspp,ε\\varepsilonand on moment exponents, but not onn,d,sn,d,s\.

### 7\.1Robust sparse mean estimation

LetX1,…,Xn∈ℝdX\_\{1\},\\dots,X\_\{n\}\\in\\mathbb\{R\}^\{d\}be i\.i\.d\. with unknown meanθ⋆∈ℝd\\theta^\{\\star\}\\in\\mathbb\{R\}^\{d\}and covariance matrixΣ⪯σ2​Id\\Sigma\\preceq\\sigma^\{2\}I\_\{d\}\. We partition the indices\{1,…,n\}\\\{1,\\dots,n\\\}intoBBblocks of equal sizem=n/Bm=n/B\(for simplicity assumem∈ℕm\\in\\mathbb\{N\}\) and write

Zb=1m∑i∈GbXi∈ℝd,b=1,…,B,Z\_\{b\}\\;=\\;\\frac\{1\}\{m\}\\sum\_\{i\\in G\_\{b\}\}X\_\{i\}\\in\\mathbb\{R\}^\{d\},\\qquad b=1,\\dots,B,for the block means\. As before, we assume that at mostε​B\\varepsilon Bblocks are arbitrary outliers and that, conditionally on the good blocks,ZbZ\_\{b\}satisfies a concentration inequality aroundθ⋆\\theta^\{\\star\}inherited from the moment conditions onXiX\_\{i\}and the block sizemm\.

In the spirit of\[[21](https://arxiv.org/html/2609.01689#bib.bib5),[9](https://arxiv.org/html/2609.01689#bib.bib24),[10](https://arxiv.org/html/2609.01689#bib.bib26),[17](https://arxiv.org/html/2609.01689#bib.bib14)\], we consider coordinate\-wise block\-LpL\_\{p\}aggregation: for each coordinatej=1,…,dj=1,\\dots,dwe define

θ^p,j∈arg​mint∈ℝ∑b=1B\|Zb,j−t\|p,0<p≤1,\\hat\{\\theta\}\_\{p,j\}\\;\\in\\;\\argmin\_\{t\\in\\mathbb\{R\}\}\\sum\_\{b=1\}^\{B\}\\bigl\|Z\_\{b,j\}\-t\\bigr\|^\{p\},\\qquad 0<p\\leq 1,and setθ^p=\(θ^p,1,…,θ^p,d\)⊤\\hat\{\\theta\}\_\{p\}=\(\\hat\{\\theta\}\_\{p,1\},\\dots,\\hat\{\\theta\}\_\{p,d\}\)^\{\\top\}\. The deterministic one\-dimensional robustness result \(Theorem[4\.2](https://arxiv.org/html/2609.01689#S4.Thmtheorem2)\) applies to each coordinate: if at least\(1−ε\)​B\(1\-\\varepsilon\)Bblocks satisfy\|Zb,j−θj⋆\|≤rj\\lvert Z\_\{b,j\}\-\\theta^\{\\star\}\_\{j\}\\rvert\\leq r\_\{j\}, then

\|θ^p,j−θj⋆\|≤c⁡\(p,ε\)​rj,\\lvert\\hat\{\\theta\}\_\{p,j\}\-\\theta^\{\\star\}\_\{j\}\\rvert\\;\\leq\\;c\(p,\\varepsilon\)\\,r\_\{j\},withc⁡\(p,ε\)c\(p,\\varepsilon\)as in Section[4](https://arxiv.org/html/2609.01689#S4)\.

To turn this into a probabilistic high\-dimensional bound, we combine: \(i\) a block concentration inequality forZbZ\_\{b\}under finite\(2\+δ\)\(2\+\\delta\)moments, as in\[[9](https://arxiv.org/html/2609.01689#bib.bib24),[4](https://arxiv.org/html/2609.01689#bib.bib23),[21](https://arxiv.org/html/2609.01689#bib.bib5)\]; \(ii\) a union bound over coordinates; and \(iii\) the deterministic oracle inequality above\. In particular, once each coordinate admits a blockwise radiusrjr\_\{j\}on the uncontaminated blocks, the one\-dimensional deterministic bound applies coordinate by coordinate and then passes to anℓ2\\ell\_\{2\}bound after the union step\. Thus the role of the block\-LpL\_\{p\}aggregation is to modify the leading robustness constant, not the ambientlog⁡d/n\\sqrt\{\\log d/n\}scaling\.

###### Theorem 7\.1\(High\-dimensional robust sparse mean\)\.

AssumeX1,…,Xn∈ℝdX\_\{1\},\\dots,X\_\{n\}\\in\\mathbb\{R\}^\{d\}are i\.i\.d\. with𝔼​Xi=θ⋆\\mathbb\{E\}X\_\{i\}=\\theta^\{\\star\},Cov⁡\(Xi\)⪯σ2​Id\\mathrm\{Cov\}\(X\_\{i\}\)\\preceq\\sigma^\{2\}I\_\{d\}, and𝔼​‖Xi−θ⋆‖22\+δ≤M\\mathbb\{E\}\\\|X\_\{i\}\-\\theta^\{\\star\}\\\|\_\{2\}^\{2\+\\delta\}\\leq Mfor someδ\>0\\delta\>0\. Let the data be partitioned intoBBblocks of sizem=n/Bm=n/B, and suppose at mostε​B\\varepsilon Bblocks are arbitrary outliers withε<1/2\\varepsilon<1/2\. Letθ^p\\hat\{\\theta\}\_\{p\}be the coordinate\-wise block\-LpL\_\{p\}estimator with0<p≤10<p\\leq 1defined above\.

Then there exist constantsC1,C2\>0C\_\{1\},C\_\{2\}\>0, depending only on\(p,ε,δ,M\)\(p,\\varepsilon,\\delta,M\), such that for allu≥1u\\geq 1, if

B≥C1​log⁡\(d​u\)andm≥C1​u,B\\;\\geq\\;C\_\{1\}\\log\(du\)\\quad\\text\{and\}\\quad m\\;\\geq\\;C\_\{1\}u,we have

‖θ^p−θ⋆‖2≤C2​c​\(p,ε\)​σ​log⁡\(d​u\)nwith probability at least​1−2​u−2\.\\\|\\hat\{\\theta\}\_\{p\}\-\\theta^\{\\star\}\\\|\_\{2\}\\;\\leq\\;C\_\{2\}\\,c\(p,\\varepsilon\)\\,\\sigma\\,\\sqrt\{\\frac\{\\log\(du\)\}\{n\}\}\\qquad\\text\{with probability at least \}1\-2u^\{\-2\}\.Moreover, for fixedε\\varepsilonandδ\\deltathe leading constantC2​c​\(p,ε\)C\_\{2\}c\(p,\\varepsilon\)is strictly decreasing inppon\(0,1\]\(0,1\]and tends, asp→0\+p\\to 0^\{\+\}, to the trimmed\-block oracle constant corresponding to theL0L\_\{0\}selector\.

The rateσ​log⁡d/n\\sigma\\sqrt\{\\log d/n\}matches the optimal minimax rate for sparse or dense mean estimation under Huber contamination and finite second moments, up to constants \(see, e\.g\.,\[[10](https://arxiv.org/html/2609.01689#bib.bib26),[9](https://arxiv.org/html/2609.01689#bib.bib24)\]\)\. Compared with the classical coordinate\-wise MoM estimator \(p=1p=1\), Theorem[7\.1](https://arxiv.org/html/2609.01689#S7.Thmtheorem1)shows that the whole0<p≤10<p\\leq 1family achieves the same rate while strictly improving the robustness constants asp↓0p\\downarrow 0\.

### 7\.2Robust sparse linear regression

We now consider high\-dimensional linear regression\. Let\(Xi,yi\)∈ℝd×ℝ\(X\_\{i\},y\_\{i\}\)\\in\\mathbb\{R\}^\{d\}\\times\\mathbb\{R\},i=1,…,ni=1,\\dots,n, satisfy

yi=⟨Xi,θ⋆⟩\+ξi,θ⋆∈ℝd,‖θ⋆‖0≤s,y\_\{i\}\\;=\\;\\langle X\_\{i\},\\theta^\{\\star\}\\rangle\+\\xi\_\{i\},\\qquad\\theta^\{\\star\}\\in\\mathbb\{R\}^\{d\},\\ \\\|\\theta^\{\\star\}\\\|\_\{0\}\\leq s,whereξi\\xi\_\{i\}are zero\-mean noise variables with finite\(2\+δ\)\(2\+\\delta\)moments\. We assume a standard restricted eigenvalue \(RE\) or compatibility condition for the design\[[1](https://arxiv.org/html/2609.01689#bib.bib22),[3](https://arxiv.org/html/2609.01689#bib.bib25)\]\. Concretely, one may take the usual cone\-based condition: there existsκ\>0\\kappa\>0such that

1n​‖X​v‖22≥κ​‖v‖22\\frac\{1\}\{n\}\\\|Xv\\\|\_\{2\}^\{2\}\\geq\\kappa\\\|v\\\|\_\{2\}^\{2\}for every vectorvvsatisfying‖vSc‖1≤3​‖vS‖1\\\|v\_\{S^\{c\}\}\\\|\_\{1\}\\leq 3\\\|v\_\{S\}\\\|\_\{1\}for some support setSSwith\|S\|≤s\|S\|\\leq s\. The precise formulation is standard in high\-dimensional Lasso theory; the point here is that, on uncontaminated blocks, the regression loss continues to obey the same RE\-controlled local geometry needed for the usual oracle inequalities\. The sample is split intoBBblocks of sizemmas before, and we define the block empirical squared loss

Rb\(θ\)=1m∑i∈Gb\(yi−⟨Xi,θ⟩\)2,b=1,…,B\.R\_\{b\}\(\\theta\)\\;=\\;\\frac\{1\}\{m\}\\sum\_\{i\\in G\_\{b\}\}\\bigl\(y\_\{i\}\-\\langle X\_\{i\},\\theta\\rangle\\bigr\)^\{2\},\\qquad b=1,\\dots,B\.Given a scalar parametert∈ℝt\\in\\mathbb\{R\}, we may viewRb​\(θ\)R\_\{b\}\(\\theta\)as a noisy version of the \(unknown\) riskR⁡\(θ\)=𝔼​\(y−⟨X,θ⟩\)2R\(\\theta\)=\\mathbb\{E\}\(y\-\\langle X,\\theta\\rangle\)^\{2\}\. Our block\-LpL\_\{p\}MoM regression estimator is defined as any solution of

\(θ^p,t^p\)∈arg​minθ∈ℝd,t∈ℝ⁡\{∑b=1B\|Rb​\(θ\)−t\|p\+λ​‖θ‖1\},0<p≤1\.\(\\hat\{\\theta\}\_\{p\},\\hat\{t\}\_\{p\}\)\\;\\in\\;\\argmin\_\{\\theta\\in\\mathbb\{R\}^\{d\},\\;t\\in\\mathbb\{R\}\}\\Biggl\\\{\\sum\_\{b=1\}^\{B\}\\bigl\|R\_\{b\}\(\\theta\)\-t\\bigr\|^\{p\}\\;\+\\;\\lambda\\\|\\theta\\\|\_\{1\}\\Biggr\\\},\\qquad 0<p\\leq 1\.\(7\.1\)Forp=1p=1, this is a minmax/MoM version of the Lasso\-type procedures studied in\[[14](https://arxiv.org/html/2609.01689#bib.bib8),[17](https://arxiv.org/html/2609.01689#bib.bib14),[6](https://arxiv.org/html/2609.01689#bib.bib27)\]; forp<1p<1we obtain a nonconvex but more robust analogue in the spirit ofLpL\_\{p\}\-penalised high\-dimensional regression\[[7](https://arxiv.org/html/2609.01689#bib.bib3)\]\.

The deterministic block\-LpL\_\{p\}oracle inequality \(Theorem[5\.2](https://arxiv.org/html/2609.01689#S5.Thmtheorem2)\) provides a robust comparison between\(θ^p,t^p\)\(\\hat\{\\theta\}\_\{p\},\\hat\{t\}\_\{p\}\)and an ideal block\-L0L\_\{0\}oracle that discards all contaminated blocks\. Combining this with standard RE arguments for Lasso and its nonconvex variants\[[1](https://arxiv.org/html/2609.01689#bib.bib22),[3](https://arxiv.org/html/2609.01689#bib.bib25),[7](https://arxiv.org/html/2609.01689#bib.bib3)\]gives the following result\. At a proof level, the mechanism is straightforward: the block\-LpL\_\{p\}objective controls the contamination\-induced distortion in the block risks, while the RE condition converts this risk control intoℓ2\\ell\_\{2\}\- andℓ1\\ell\_\{1\}\-error bounds in exactly the same way as in robust Lasso analyses\. What changes relative to thep=1p=1case is the multiplicative robustness constantc⁡\(p,ε\)c\(p,\\varepsilon\); what does not change is the ambients​log⁡d/n\\sqrt\{s\\log d/n\}rate\.

###### Theorem 7\.2\(Robust sparse regression with block\-LpL\_\{p\}MoM\)\.

Assume the linear model above, with‖θ⋆‖0≤s\\\|\\theta^\{\\star\}\\\|\_\{0\}\\leq s, and let the design\(Xi\)\(X\_\{i\}\)satisfy an RE condition with constantκ\>0\\kappa\>0on the usualss\-sparse cone\. Assume thatXiX\_\{i\}andξi\\xi\_\{i\}have finite\(2\+δ\)\(2\+\\delta\)moments for someδ\>0\\delta\>0, and that at mostε​B\\varepsilon Bblocks are arbitrarily contaminated in both\(Xi,yi\)\(X\_\{i\},y\_\{i\}\)withε<1/2\\varepsilon<1/2\. Let\(θ^p,t^p\)\(\\hat\{\\theta\}\_\{p\},\\hat\{t\}\_\{p\}\)be any solution of \([7\.1](https://arxiv.org/html/2609.01689#S7.E1)\) with tuning parameterλ\\lambdaof order

λ≍c⁡\(p,ε\)​σ​log⁡dn,\\lambda\\;\\asymp\\;c\(p,\\varepsilon\)\\,\\sigma\\,\\sqrt\{\\frac\{\\log d\}\{n\}\},whereσ2\\sigma^\{2\}is the noise variance\. Ifn≳s​log⁡dn\\gtrsim s\\log dandB≳log⁡dB\\gtrsim\\log dare large enough, then with probability at least1−c1​exp⁡\(−c2​B\)1\-c\_\{1\}\\exp\(\-c\_\{2\}B\)we have

‖θ^p−θ⋆‖2≲c⁡\(p,ε\)κ​σ​s​log⁡dn,‖θ^p−θ⋆‖1≲c⁡\(p,ε\)κ​σ​s​log⁡dn,\\\|\\hat\{\\theta\}\_\{p\}\-\\theta^\{\\star\}\\\|\_\{2\}\\;\\lesssim\\;\\frac\{c\(p,\\varepsilon\)\}\{\\kappa\}\\,\\sigma\\,\\sqrt\{\\frac\{s\\log d\}\{n\}\},\\qquad\\\|\\hat\{\\theta\}\_\{p\}\-\\theta^\{\\star\}\\\|\_\{1\}\\;\\lesssim\\;\\frac\{c\(p,\\varepsilon\)\}\{\\kappa\}\\,\\sigma\\,s\\,\\sqrt\{\\frac\{\\log d\}\{n\}\},wherec1,c2\>0c\_\{1\},c\_\{2\}\>0depend only on\(p,ε,δ\)\(p,\\varepsilon,\\delta\)and on moment bounds\. Asp↓0p\\downarrow 0, the leading robustness constantc⁡\(p,ε\)c\(p,\\varepsilon\)tends to the block\-L0L\_\{0\}oracle constant, while the rates​log⁡d/n\\sqrt\{s\\log d/n\}remains unchanged\.

Theorem[7\.2](https://arxiv.org/html/2609.01689#S7.Thmtheorem2)matches, up to constants, the usual sparse\-regression minimax rateσ​s​log⁡d/n\\sigma\\sqrt\{s\\log d/n\}known for Lasso under subgaussian assumptions\[[1](https://arxiv.org/html/2609.01689#bib.bib22),[3](https://arxiv.org/html/2609.01689#bib.bib25)\], and is comparable to the MoM\-based high\-dimensional regression bounds in\[[17](https://arxiv.org/html/2609.01689#bib.bib14),[6](https://arxiv.org/html/2609.01689#bib.bib27)\]\. The novelty is that the entire0<p≤10<p\\leq 1path enjoys the same rate while strictly improving the contamination tolerance at the deterministic level viac⁡\(p,ε\)c\(p,\\varepsilon\), and that the limiting casep→0\+p\\to 0^\{\+\}approaches the ideal trimmed\-block \(L0L\_\{0\}\) performance without incurring the computational intractability of exact block trimming\[[10](https://arxiv.org/html/2609.01689#bib.bib26)\]\. This is also the right place to position the comparison with Huber\-type robust regression\. Methods based on Huber losses or other convex robustifications remain highly competitive and are often minimax\-rate optimal, but their constants are derived under different objectives and contamination models\. Our claim is therefore narrower: under the present block\-contamination framework, the block\-LpL\_\{p\}path preserves the standard high\-dimensional rate while improving the deterministic robustness constant asppdecreases, especially in the separated\-contamination regimes highlighted earlier in the paper and in the new experiments\.

## 8Experimental Results

This section provides empirical validation of the proposed block\-LpL\_\{p\}estimators\. The aim is not to claim a new statistical rate, but to verify the specific theoretical picture developed in the paper: classical MoM should remain competitive in benign heavy\-tailed regimes, smaller values ofppshould improve robustness under adversarial contamination, and in separated block\-contamination regimes the block\-LpL\_\{p\}estimators should move towards trimmed\-block performance\.

### 8\.1Experimental setup

We consider scalar mean estimation with true meanμ=0\\mu=0\. In each trial, the sample is partitioned into equal\-sized blocks, block means are computed, and the final estimate is obtained by one of the following procedures: classical MoM \(p=1p=1\), the proposed block\-L0\.5L\_\{0\.5\}and block\-L0\.2L\_\{0\.2\}estimators, trimmed mean over block summaries, and a Huber estimator applied to the block means\. We report the mean absolute estimation error and the corresponding standard deviation over repeated trials\.

### 8\.2Heavy\-tailed regime

We first consider a benign heavy\-tailed setting in which the data are sampled from a Student\-ttdistribution withν=3\\nu=3degrees of freedom and no structured adversarial separation is imposed\. This experiment is intended to test that moving fromp=1p=1to smaller values ofppdoes not degrade performance when the contamination is not of the separated type that benefits selective block trimming\.

Table 1:Heavy\-tailed setting \(Student\-tt,ν=3\\nu=3\)\. All methods exhibit comparable performance, confirming no degradation in benign heavy\-tailed regimes\.The first table shows that all methods behave similarly in this regime\. In particular, the proposed block\-LpL\_\{p\}estimators do not exhibit any practical deterioration relative to MoM\. This is consistent with the theory: without clear separation between good and bad blocks, one should not expect the small\-ppestimators to yield dramatic gains\.

### 8\.3Adversarial contamination

We next introduce adversarial contamination at levelε=0\.2\\varepsilon=0\.2\. Here a subset of observations is replaced by large outliers, but the induced block summaries are not yet cleanly separated from the uncontaminated ones\. This regime probes whether the deterministic improvement in robustness constants has a visible finite\-sample effect before full oracle\-like separation sets in\.

Table 2:Adversarial contamination \(ε=0\.2\\varepsilon=0\.2\)\. Decreasingppin the block\-LpL\_\{p\}estimator leads to progressively lower estimation error, outperforming MoM and the convex Huber estimator\.The results confirm a monotone empirical trend: asppdecreases from11to0\.20\.2, the mean error decreases substantially\. The gain is not yet oracle\-level, which is expected because the separation condition is only partial in this experiment, but the direction of improvement is fully consistent with the theoretical1​–​p​–​01\\text\{\-\-\}p\\text\{\-\-\}0interpolation\. The Huber baseline remains competitive yet is clearly dominated by the smaller\-ppblock estimators in this adversarial regime\.

### 8\.4Separated block contamination

Finally, we consider the regime most closely aligned with the oracle\-equivalence theory: anε\\varepsilon\-fraction of blocks is contaminated by a sufficiently large shift so that contaminated block means are well separated from the uncontaminated ones\. This is the setting in which the small\-ppobjectives are predicted to behave most like an implicit trimming rule\.

Table 3:Block contamination \(separation regime\)\. The block\-LpL\_\{p\}estimator withp=0\.2p=0\.2achieves near\-oracle performance, closely matching the trimmed mean and significantly outperforming MoM and the Huber estimator\.This is the key empirical table for the paper\. Once separated contamination is present, the block\-L0\.2L\_\{0\.2\}estimator nearly matches the trimmed mean and dramatically improves over both MoM and Huber\. Thus the experiments support the central qualitative claim of the manuscript: decreasingppdoes not help much in benign heavy\-tailed settings, helps moderately in adversarial settings, and becomes most valuable precisely when separated block contamination makes oracle\-like trimming behaviour statistically meaningful\.

### 8\.5Overall interpretation

Taken together, the three experiments validate the intended scope of the theory\. The proposed method is not advertised as uniformly superior to MoM in every regime\. Rather, it preserves MoM\-like behaviour when the contamination structure does not justify aggressive block selection, and it moves towards trimmed\-block performance when such structure is present\. This is also the right context in which to interpret the comparison with Huber\-type baselines: convex robustification remains effective, but under the deterministic block\-contamination metric studied here it does not recover the same level of selectivity as the small\-ppblock objectives in the separated regime\.

## 9Conclusion

Classical median\-of\-means estimators arise from probabilistic ideas designed to stabilise empirical means under heavy tails and adversarial contamination\[[4](https://arxiv.org/html/2609.01689#bib.bib23),[9](https://arxiv.org/html/2609.01689#bib.bib24),[21](https://arxiv.org/html/2609.01689#bib.bib5),[17](https://arxiv.org/html/2609.01689#bib.bib14)\], but in the scalar case they are also minimisers of a blockwiseL1L\_\{1\}functional and thus belong to a broad class of block M\-estimators\. Our first contribution is to make this optimisation viewpoint explicit and to show, via Theorem[3\.3](https://arxiv.org/html/2609.01689#S3.Thmtheorem3), that within the class of convex block M\-estimators \([2\.8](https://arxiv.org/html/2609.01689#S2.E8)\) no choice of convex loss can uniformly improve upon the deterministic MoM constant1/\(1−2​ε\)1/\(1\-2\\varepsilon\)from Lemma[3\.1](https://arxiv.org/html/2609.01689#S3.Thmtheorem1); in particular, the trimmed\-block oracle behaviour of Lemma[4\.1](https://arxiv.org/html/2609.01689#S4.Thmtheorem1), with constant1/\(1−ε\)1/\(1\-\\varepsilon\), is unreachable for any convex block aggregator\. Thus the central contribution of the paper is not a new robust estimator in isolation, but a precise deterministic description of the convex frontier and a principled nonconvex route beyond it\.

This motivates the nonconvex block\-LpL\_\{p\}family and the11–pp–00path\. Working withFp​\(t\)=∑b\|Zb−t\|pF\_\{p\}\(t\)=\\sum\_\{b\}\|Z\_\{b\}\-t\|^\{p\}for0<p<10<p<1, we retain breakdown point1/21/2\(Theorem[4\.2](https://arxiv.org/html/2609.01689#S4.Thmtheorem2)\), while Theorem[5\.2](https://arxiv.org/html/2609.01689#S5.Thmtheorem2)shows that, under a mild separation between good and bad blocks, global minimiserst^p\\hat\{t\}\_\{p\}coincide with those of an ideal block\-L0L\_\{0\}oracle for smallpp, and their robustness constants converge to1/\(1−ε\)1/\(1\-\\varepsilon\)asp↓0p\\downarrow 0\. Theorem[5\.3](https://arxiv.org/html/2609.01689#S5.Thmtheorem3)further shows that the energy landscape ofFpF\_\{p\}is benign: all local minima lie in a controlled neighbourhood ofμ\\muand outside this neighbourhood the objective satisfies a quantitative slope inequality, mirroring the nonconvex but well\-behaved geometry known forℓp\\ell\_\{p\}sparse recovery\[[12](https://arxiv.org/html/2609.01689#bib.bib1),[7](https://arxiv.org/html/2609.01689#bib.bib3)\]\. Embedding these deterministic results in a probabilistic framework yields deviation bounds fort^p\\hat\{t\}\_\{p\}under finite\(2\+δ\)\(2\+\\delta\)moments and blockwise contamination \(Theorem[6\.2](https://arxiv.org/html/2609.01689#S6.Thmtheorem2)\) that interpolate continuously between the MoM constant1/\(1−2​ε\)1/\(1\-2\\varepsilon\)atp=1p=1and the trimmed\-block oracle constant1/\(1−ε\)1/\(1\-\\varepsilon\)asp→0\+p\\to 0^\{\+\}, and high\-dimensional extensions for robust mean estimation and sparse linear regression \(Theorems[7\.1](https://arxiv.org/html/2609.01689#S7.Thmtheorem1)and[7\.2](https://arxiv.org/html/2609.01689#S7.Thmtheorem2)\) recover the usuallog⁡d/n\\sqrt\{\\log d/n\}ands​log⁡d/n\\sqrt\{s\\log d/n\}rates along the entire0<p≤10<p\\leq 1path, in line with modern MoM\-based procedures\[[17](https://arxiv.org/html/2609.01689#bib.bib14),[10](https://arxiv.org/html/2609.01689#bib.bib26)\]\. The new experimental section strengthens this conclusion substantially: it shows no practical degradation relative to classical MoM in benign heavy\-tailed settings, clear gains asppdecreases under adversarial contamination, and near\-oracle behaviour in the separated block\-contamination regime\. The conclusion is therefore both theoretical and empirical: the advantage of the block\-LpL\_\{p\}path is conditional rather than universal, but it becomes visible precisely in the regimes predicted by the deterministic analysis\.

Several directions remain open\. A first goal is to sharpen the constantsc⁡\(p,ε\)c\(p,\\varepsilon\)and the thresholdp0​\(ε,Δ/r\)p\_\{0\}\(\\varepsilon,\\Delta/r\)appearing in the oracle equivalence, and to obtain exact minimax characterisations along the11–pp–00path in the spirit of\[[21](https://arxiv.org/html/2609.01689#bib.bib5),[17](https://arxiv.org/html/2609.01689#bib.bib14)\]\. A second is to clarify statistical–computational trade\-offs: exact block trimming is combinatorial and typically NP\-hard\[[10](https://arxiv.org/html/2609.01689#bib.bib26)\], while our results suggest that block\-LpL\_\{p\}estimators approximate the block\-L0L\_\{0\}oracle yet admit gradient\-based optimisation thanks to the benign landscape of Theorem[5\.3](https://arxiv.org/html/2609.01689#S5.Thmtheorem3)\. At the same time, the present paper should not be read as claiming a full algorithmic convergence theory for every optimisation scheme; rather, it establishes that the objective landscape is sufficiently well structured to make such analysis plausible and worthwhile\. Extending the present scalar and coordinate\-wise analysis to multivariate location and scatter \(e\.g\. via geometric medians or depth\-based functionals in Banach spaces\[[24](https://arxiv.org/html/2609.01689#bib.bib7),[9](https://arxiv.org/html/2609.01689#bib.bib24)\]\), to general Lipschitz or smooth losses in generalised linear models\[[14](https://arxiv.org/html/2609.01689#bib.bib8),[2](https://arxiv.org/html/2609.01689#bib.bib13),[17](https://arxiv.org/html/2609.01689#bib.bib14)\], and to adaptive, data\-driven choices ofpp\(e\.g\. homotopy inpp\) are natural next steps\. Finally, connections with Bayesian and variational robust methods—where trimming in data space is often induced by spike\-and\-slab or heavy\-tailed priors—may yield Bayesian counterparts of the deterministic11–pp–00path, combining MoM\-type guarantees with modelling flexibility\. Overall, the revised manuscript now supports a sharper message than the original version: classical MoM marks the edge of what is uniformly achievable within convex block aggregation, the block\-LpL\_\{p\}family provides a principled nonconvex interpolation toward trimmed\-block behaviour, and the new empirical study confirms that this interpolation matters most when clean and corrupted blocks are genuinely separated\.

## References

- \[1\]\(2009\)Simultaneous analysis of lasso and dantzig selector\.The Annals of Statistics37\(4\),pp\. 1705–1732\.External Links:[Document](https://dx.doi.org/10.1214/08-AOS620)Cited by:[§7\.2](https://arxiv.org/html/2609.01689#S7.SS2.p1.2),[§7\.2](https://arxiv.org/html/2609.01689#S7.SS2.p2.1),[§7\.2](https://arxiv.org/html/2609.01689#S7.SS2.p3.1)\.
- \[2\]C\. Brownlees, E\. Joly, and G\. Lugosi\(2015\)Empirical risk minimization for heavy\-tailed losses\.The Annals of Statistics43\(6\),pp\. 2507–2536\.External Links:[Document](https://dx.doi.org/10.1214/15-AOS1350)Cited by:[§2\.3](https://arxiv.org/html/2609.01689#S2.SS3.p1.2),[§3\.2](https://arxiv.org/html/2609.01689#S3.SS2.p1.1),[§9](https://arxiv.org/html/2609.01689#S9.p3.1)\.
- \[3\]P\. Bühlmann and S\. van de Geer\(2011\)Statistics for high\-dimensional data: methods, theory and applications\.Springer,Berlin\.External Links:[Document](https://dx.doi.org/10.1007/978-3-642-20192-9),ISBN 978\-3\-642\-20191\-2Cited by:[§7\.2](https://arxiv.org/html/2609.01689#S7.SS2.p1.2),[§7\.2](https://arxiv.org/html/2609.01689#S7.SS2.p2.1),[§7\.2](https://arxiv.org/html/2609.01689#S7.SS2.p3.1)\.
- \[4\]O\. Catoni\(2012\)Challenging the empirical mean and the empirical variance: a deviation study\.Annales de l’Institut Henri Poincaré, Probabilités et Statistiques48\(4\),pp\. 1148–1185\.External Links:[Document](https://dx.doi.org/10.1214/11-AIHP454)Cited by:[§1](https://arxiv.org/html/2609.01689#S1.p6.1),[§6\.1](https://arxiv.org/html/2609.01689#S6.SS1.p1.2),[§6\.2](https://arxiv.org/html/2609.01689#S6.SS2.p3.1),[§6\.3](https://arxiv.org/html/2609.01689#S6.SS3.p1.2),[§7\.1](https://arxiv.org/html/2609.01689#S7.SS1.p3.1),[§9](https://arxiv.org/html/2609.01689#S9.p1.1)\.
- \[5\]Z\. Chen, B\. Kailkhura, and Y\. Zhou\(2023\)An accelerated proximal algorithm for regularized nonconvex and nonsmooth bi\-level optimization\.Machine Learning112\(9\),pp\. 3159–3195\.External Links:[Document](https://dx.doi.org/10.1007/s10994-023-06347-1)Cited by:[§1](https://arxiv.org/html/2609.01689#S1.p5.1)\.
- \[6\]G\. Chinot, G\. Lecué, and M\. Lerasle\(2020\)Robust high dimensional learning for lipschitz and convex losses\.Journal of Machine Learning Research21\(233\),pp\. 1–47\.Cited by:[§7\.2](https://arxiv.org/html/2609.01689#S7.SS2.p1.5),[§7\.2](https://arxiv.org/html/2609.01689#S7.SS2.p3.1)\.
- \[7\]A\. S\. Dalalyan and A\. Minasyan\(2022\)All\-in\-one robust estimator of the Gaussian mean\.The Annals of Statistics50\(2\),pp\. 1193–1219\.External Links:[Document](https://dx.doi.org/10.1214/21-AOS2145)Cited by:[§4\.1](https://arxiv.org/html/2609.01689#S4.SS1.p1.3),[§4\.1](https://arxiv.org/html/2609.01689#S4.SS1.p2.2),[§5\.2](https://arxiv.org/html/2609.01689#S5.SS2.p1.1),[§5\.2](https://arxiv.org/html/2609.01689#S5.SS2.p6.1),[§7\.2](https://arxiv.org/html/2609.01689#S7.SS2.p1.5),[§7\.2](https://arxiv.org/html/2609.01689#S7.SS2.p2.1),[§9](https://arxiv.org/html/2609.01689#S9.p2.1)\.
- \[8\]L\. Devroye, M\. Lerasle, G\. Lugosi, and R\. I\. Oliveira\(2016\)Sub\-Gaussian mean estimators\.The Annals of Statistics44\(6\),pp\. 2695–2725\.External Links:[Document](https://dx.doi.org/10.1214/16-AOS1440)Cited by:[§1](https://arxiv.org/html/2609.01689#S1.p1.1),[§1](https://arxiv.org/html/2609.01689#S1.p2.1),[§2\.1](https://arxiv.org/html/2609.01689#S2.SS1.p3.1),[§6\.1](https://arxiv.org/html/2609.01689#S6.SS1.p1.2),[§6\.1](https://arxiv.org/html/2609.01689#S6.SS1.p3.1.1),[§6\.1](https://arxiv.org/html/2609.01689#S6.SS1.p4.1),[§6\.2](https://arxiv.org/html/2609.01689#S6.SS2.p3.1),[§6\.3](https://arxiv.org/html/2609.01689#S6.SS3.p1.2)\.
- \[9\]L\. Devroye, M\. Lerasle, G\. Lugosi, and R\. I\. Oliveira\(2016\)Sub\-Gaussian mean estimators\.The Annals of Statistics44\(6\),pp\. 2695–2725\.External Links:[Document](https://dx.doi.org/10.1214/16-AOS1440)Cited by:[§7\.1](https://arxiv.org/html/2609.01689#S7.SS1.p2.1),[§7\.1](https://arxiv.org/html/2609.01689#S7.SS1.p3.1),[§7\.1](https://arxiv.org/html/2609.01689#S7.SS1.p4.1),[§9](https://arxiv.org/html/2609.01689#S9.p1.1),[§9](https://arxiv.org/html/2609.01689#S9.p3.1)\.
- \[10\]I\. Diakonikolas, G\. Kamath, D\. M\. Kane, J\. Li, A\. Moitra, and A\. Stewart\(2019\)Robust estimators in high\-dimensions without the computational intractability\.SIAM Journal on Computing48\(2\),pp\. 742–864\.External Links:[Document](https://dx.doi.org/10.1137/17M1126680)Cited by:[§7\.1](https://arxiv.org/html/2609.01689#S7.SS1.p2.1),[§7\.1](https://arxiv.org/html/2609.01689#S7.SS1.p4.1),[§7\.2](https://arxiv.org/html/2609.01689#S7.SS2.p3.1),[§9](https://arxiv.org/html/2609.01689#S9.p2.1),[§9](https://arxiv.org/html/2609.01689#S9.p3.1)\.
- \[11\]I\. Diakonikolas and D\. M\. Kane\(2023\)Algorithmic high\-dimensional robust statistics\.Cambridge University Press\.External Links:[Document](https://dx.doi.org/10.1017/9781108943161),ISBN 978\-1\-108\-83781\-1Cited by:[§1](https://arxiv.org/html/2609.01689#S1.p2.1)\.
- \[12\]S\. Foucart and H\. Rauhut\(2013\)A mathematical introduction to compressive sensing\.Birkhäuser,New York\.External Links:[Document](https://dx.doi.org/10.1007/978-0-8176-4948-7),ISBN 978\-0\-8176\-4947\-0Cited by:[§1](https://arxiv.org/html/2609.01689#S1.p5.1),[§4\.1](https://arxiv.org/html/2609.01689#S4.SS1.p1.3),[§4\.1](https://arxiv.org/html/2609.01689#S4.SS1.p2.2),[§5\.2](https://arxiv.org/html/2609.01689#S5.SS2.p1.1),[§5\.2](https://arxiv.org/html/2609.01689#S5.SS2.p6.1),[§9](https://arxiv.org/html/2609.01689#S9.p2.1)\.
- \[13\]F\. R\. Hampel, E\. M\. Ronchetti, P\. J\. Rousseeuw, and W\. A\. Stahel\(1986\)Robust statistics: the approach based on influence functions\.John Wiley & Sons,New York\.External Links:ISBN 978\-0\-471\-90976\-7Cited by:[§3\.2](https://arxiv.org/html/2609.01689#S3.SS2.p1.1),[§4\.2](https://arxiv.org/html/2609.01689#S4.SS2.p7.3)\.
- \[14\]D\. Hsu and S\. Sabato\(2016\)Loss minimization and parameter estimation with heavy tails\.Journal of Machine Learning Research17\(18\),pp\. 1–40\.Cited by:[§1](https://arxiv.org/html/2609.01689#S1.p1.1),[§1](https://arxiv.org/html/2609.01689#S1.p2.1),[§2\.3](https://arxiv.org/html/2609.01689#S2.SS3.p1.2),[§7\.2](https://arxiv.org/html/2609.01689#S7.SS2.p1.5),[§9](https://arxiv.org/html/2609.01689#S9.p3.1)\.
- \[15\]P\. J\. Huber\(1981\)Robust statistics\.John Wiley & Sons,New York\.External Links:ISBN 978\-0\-471\-41805\-4Cited by:[§3\.2](https://arxiv.org/html/2609.01689#S3.SS2.p1.1),[§4\.2](https://arxiv.org/html/2609.01689#S4.SS2.p7.3)\.
- \[16\]M\. R\. Jerrum, L\. G\. Valiant, and V\. V\. Vazirani\(1986\)Random generation of combinatorial structures from a uniform distribution\.Theoretical Computer Science43\(2–3\),pp\. 169–188\.External Links:[Document](https://dx.doi.org/10.1016/0304-3975%2886%2990174-X)Cited by:[§2\.2](https://arxiv.org/html/2609.01689#S2.SS2.p1.1)\.
- \[17\]G\. Lecué and M\. Lerasle\(2020\)Robust machine learning by median\-of\-means: theory and practice\.The Annals of Statistics48\(2\),pp\. 806–831\.External Links:[Document](https://dx.doi.org/10.1214/19-AOS1828)Cited by:[§1](https://arxiv.org/html/2609.01689#S1.p6.1),[§2\.1](https://arxiv.org/html/2609.01689#S2.SS1.p2.1),[§2\.3](https://arxiv.org/html/2609.01689#S2.SS3.p1.2),[§3\.1](https://arxiv.org/html/2609.01689#S3.SS1.p1.1),[§3\.2](https://arxiv.org/html/2609.01689#S3.SS2.p1.1),[§7\.1](https://arxiv.org/html/2609.01689#S7.SS1.p2.1),[§7\.2](https://arxiv.org/html/2609.01689#S7.SS2.p1.5),[§7\.2](https://arxiv.org/html/2609.01689#S7.SS2.p3.1),[§9](https://arxiv.org/html/2609.01689#S9.p1.1),[§9](https://arxiv.org/html/2609.01689#S9.p2.1),[§9](https://arxiv.org/html/2609.01689#S9.p3.1)\.
- \[18\]M\. Lerasle and R\. I\. Oliveira\(2011\)Robust empirical mean estimators\.arXiv preprint arXiv:1112\.3914\.External Links:[Link](https://arxiv.org/abs/1112.3914)Cited by:[§2\.1](https://arxiv.org/html/2609.01689#S2.SS1.p2.1),[§2\.2](https://arxiv.org/html/2609.01689#S2.SS2.p1.1),[§3\.1](https://arxiv.org/html/2609.01689#S3.SS1.p1.1)\.
- \[19\]G\. Lugosi and S\. Mendelson\(2019\)Mean estimation and regression under heavy\-tailed distributions: a survey\.Foundations of Computational Mathematics19\(5\),pp\. 1145–1190\.External Links:[Document](https://dx.doi.org/10.1007/s10208-019-09427-x)Cited by:[§1](https://arxiv.org/html/2609.01689#S1.p1.1),[§1](https://arxiv.org/html/2609.01689#S1.p2.1),[§1](https://arxiv.org/html/2609.01689#S1.p6.1),[§2\.1](https://arxiv.org/html/2609.01689#S2.SS1.p3.1),[§2\.2](https://arxiv.org/html/2609.01689#S2.SS2.p1.1),[§6\.1](https://arxiv.org/html/2609.01689#S6.SS1.p1.2),[§6\.2](https://arxiv.org/html/2609.01689#S6.SS2.p3.1),[§6\.3](https://arxiv.org/html/2609.01689#S6.SS3.p1.2)\.
- \[20\]G\. Lugosi and S\. Mendelson\(2019\)Near\-optimal mean estimators with respect to general norms\.Probability Theory and Related Fields175\(3–4\),pp\. 957–973\.External Links:[Document](https://dx.doi.org/10.1007/s00440-019-00929-4)Cited by:[§1](https://arxiv.org/html/2609.01689#S1.p2.1)\.
- \[21\]G\. Lugosi and S\. Mendelson\(2019\)Sub\-Gaussian estimators of the mean of a random vector\.The Annals of Statistics47\(2\),pp\. 783–794\.External Links:[Document](https://dx.doi.org/10.1214/17-AOS1639)Cited by:[§1](https://arxiv.org/html/2609.01689#S1.p1.1),[§1](https://arxiv.org/html/2609.01689#S1.p2.1),[§6\.1](https://arxiv.org/html/2609.01689#S6.SS1.p3.1.1),[§6\.1](https://arxiv.org/html/2609.01689#S6.SS1.p4.1),[§6\.2](https://arxiv.org/html/2609.01689#S6.SS2.p3.1),[§6\.3](https://arxiv.org/html/2609.01689#S6.SS3.p1.2),[§7\.1](https://arxiv.org/html/2609.01689#S7.SS1.p2.1),[§7\.1](https://arxiv.org/html/2609.01689#S7.SS1.p3.1),[§9](https://arxiv.org/html/2609.01689#S9.p1.1),[§9](https://arxiv.org/html/2609.01689#S9.p3.1)\.
- \[22\]R\. A\. Maronna, R\. D\. Martin, and V\. J\. Yohai\(2006\)Robust statistics: theory and methods\.John Wiley & Sons,Chichester\.External Links:ISBN 978\-0\-470\-01092\-1Cited by:[§3\.2](https://arxiv.org/html/2609.01689#S3.SS2.p1.1),[§4\.2](https://arxiv.org/html/2609.01689#S4.SS2.p7.3)\.
- \[23\]S\. Minsker and S\. Yao\(2025\)Generalized median of means principle for bayesian inference\.Machine Learning\.External Links:[Document](https://dx.doi.org/10.1007/s10994-025-06515-3)Cited by:[§1](https://arxiv.org/html/2609.01689#S1.p1.1)\.
- \[24\]S\. Minsker\(2015\)Geometric median and robust estimation in Banach spaces\.Bernoulli21\(4\),pp\. 2308–2335\.External Links:[Document](https://dx.doi.org/10.3150/14-BEJ645)Cited by:[§1](https://arxiv.org/html/2609.01689#S1.p1.1),[§1](https://arxiv.org/html/2609.01689#S1.p2.1),[§9](https://arxiv.org/html/2609.01689#S9.p3.1)\.
- \[25\]S\. Minsker\(2023\)Efficient median of means estimator\.InProceedings of the 36th Conference on Learning Theory,G\. Neu and L\. Rosasco \(Eds\.\),Proceedings of Machine Learning Research, Vol\.195,pp\. 5925–5933\.External Links:[Link](https://proceedings.mlr.press/v195/minsker23a.html)Cited by:[§3\.1](https://arxiv.org/html/2609.01689#S3.SS1.p1.1)\.
- \[26\]A\. S\. Nemirovsky and D\. B\. Yudin\(1983\)Problem complexity and method efficiency in optimization\.Wiley,Chichester\.External Links:ISBN 978\-0\-471\-10345\-5Cited by:[§2\.2](https://arxiv.org/html/2609.01689#S2.SS2.p1.1)\.
- \[27\]J\. Tu, Y\. Sun, Y\. Chen, and J\. Fan\(2021\)Variance reduced median\-of\-means estimator for byzantine\-robust distributed learning\.Journal of Machine Learning Research22\(48\),pp\. 1–64\.Cited by:[§2\.2](https://arxiv.org/html/2609.01689#S2.SS2.p1.1)\.
- \[28\]P\. Zhao, F\. Yu, and Z\. Wan\(2024\)A huber loss minimization approach to Byzantine robust federated learning\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.38,pp\. 21806–21814\.Cited by:[§6\.3](https://arxiv.org/html/2609.01689#S6.SS3.p3.1)\.
- \[29\]S\. Zuo, X\. Yan, R\. Fan,et al\.\(2025\)Federated learning resilient to byzantine attacks and data heterogeneity\.IEEE Transactions on Mobile Computing\.Cited by:[§6\.3](https://arxiv.org/html/2609.01689#S6.SS3.p3.1)\.