Introduction
Mean estimation, or location estimation, is one of the foundational subroutines in machine learning and statistics. A modern line of work focuses on statistical estimators that are robust to heavy-tailed distributions. Starting with the systematic study pioneered by Catoni [6 ] , this line of work seeks to obtain non-asymptotic sub-Gaussian rates for estimating the means of random variables, usually using estimators such as the median of means, which appeared independently in [NY83, JVV86, AMS99], Catoni’s estimator [6 ] , or trimmed-mean estimators [16 ] . As we recall later, more involved versions of these estimators also work well in high-dimensional regimes, where the primary focus has traditionally been on the Euclidean norm.
However, the Euclidean norm is arguably the most benign norm to work with. Indeed, given n n n independent vectors X 1 , … , X n X_1,\ldots,X_n X 1 , … , X n in R d \mathbb{R}^d R d with common mean μ \mu μ and identity covariance I d I_d I d , the sample mean is essentially optimal, up to universal constant factors for all n n n and d d d :
E ∥ 1 n ∑ i = 1 n X i − μ ∥ 2 ≤ d n , (1) \mathbb{E}\left\|\frac{1}{n}\sum_{i=1}^{n}X_i-\mu\right\|_2\le\sqrt{\frac{d}{n}}, \tag*{(1)} E n 1 i = 1 ∑ n X i − μ 2 ≤ n d , (1)
which follows from Cauchy–Schwarz and does not require the existence of any moments above the second moment, while the lower bound follows from Anderson’s lemma [3 ] as discussed below. Assuming only the existence of the covariance, and no higher moments, the main focus has therefore been on obtaining sub-Gaussian estimators, namely estimators with optimal sub-Gaussian type tails, where the sample mean is clearly the wrong object [Min15, LM19b, CG17, LM21].
When going beyond the Euclidean norm, while still keeping only the bounded covariance assumption, even the in expectation story of (1) becomes more delicate especially in the high-dimensional regime where the dimension d d d is larger than the sample size n n n . In non-Hilbertian geometries, the vanilla sample mean is no longer necessarily a good estimator.6 Our key contribution is to show that the Euclidean picture is special even for the simple mean estimation problem in R d \mathbb{R}^d R d . For ℓ p \ell_p ℓ p norms with p > 2 p>2 p > 2 , robustification can be necessary even for in expectation bounds of the form (1) . This phenomenon does not appear in the regime 1 ≤ p ≤ 2 1\le p\le2 1 ≤ p ≤ 2 , where the sample mean remains optimal up to universal constants, but it becomes crucial once the geometry of the loss is sufficiently far from ℓ 2 \ell_2 ℓ 2 .
Theorem 1.1 (Phase transition for location estimation in ℓ p \ell_p ℓ p , informal). Under only the covariance assumption Cov P ( X ) = I d \operatorname{Cov}_P(X)=I_d Cov P ( X ) = I d , the optimal expected error for estimating the mean in ℓ p \ell_p ℓ p satisfies
inf μ ^ sup μ ∈ R d P : E P [ X ] = μ Cov P ( X ) = I d E ∥ μ ^ − μ ∥ p ≍ { d 1 2 ⌈ n / 2 ⌉ , p ˉ > 2 ⌈ n / 2 ⌉ , d 1 p ˉ p ˉ n , p ˉ ≤ 2 ⌈ n / 2 ⌉ , \inf_{\widehat{\mu}}\sup_{\substack{\mu\in\mathbb{R}^d\\P:\mathbb{E}_P[X]=\mu\\\operatorname{Cov}_P(X)=I_d}}\mathbb{E}\|\widehat{\mu}-\mu\|_p\asymp
\begin{cases}
d^{\frac{1}{2\lceil n/2\rceil}}, & \bar p>2\lceil n/2\rceil,\\
d^{\frac{1}{\bar p}}\sqrt{\frac{\bar p}{n}}, & \bar p\le2\lceil n/2\rceil,
\end{cases} μ inf μ ∈ R d P : E P [ X ] = μ Cov P ( X ) = I d sup E ∥ μ − μ ∥ p ≍ ⎩ ⎨ ⎧ d 2 ⌈ n /2 ⌉ 1 , d p ˉ 1 n p ˉ , p ˉ > 2 ⌈ n /2 ⌉ , p ˉ ≤ 2 ⌈ n /2 ⌉ , where μ ^ \widehat{\mu} μ ranges over all estimators based on the n n n samples and
p ˉ = min { p , max { log d , 1 } } . \bar p=\min\{p,\max\{\log d,1\}\}. p ˉ = min { p , max { log d , 1 }} .
Thus, the minimax risk undergoes a sharp phase transition. In the large sample regime, the rate has the familiar Gaussian form, corresponding to the Gaussian width of the dual ball inducing the norm, as we discuss below:
d 1 / p ˉ p ˉ n . d^{1/\bar p}\sqrt{\frac{\bar p}{n}}. d 1/ p ˉ n p ˉ .
In contrast, in the small sample or large p p p regime, the effective exponent is capped by the number of samples, and the optimal rate becomes
d 1 2 ⌈ n / 2 ⌉ . d^{\frac{1}{2\lceil n/2\rceil}}. d 2 ⌈ n /2 ⌉ 1 .
We show that a estimator achieving this rate is a simple coordinate-wise median of means estimator, with the choice of number of buckets depending on the geometry of the loss. Recall that median of means first splits the sample into nearly equal buckets, computes the average inside each bucket, and then takes a median of these bucket averages. In the coordinate-wise version used here, if X ˉ ( 1 ) , … , X ˉ ( t ) \bar{X}^{(1)}, \ldots, \bar{X}^{(t)} X ˉ ( 1 ) , … , X ˉ ( t ) denote the nonempty bucket averages, the estimator is defined by
μ ^ j = Median ( { X ˉ j ( 1 ) , … , X ˉ j ( t ) } ) , j = 1 , … , d . \widehat{\mu}_j = \operatorname{Median}\left(\left\{\bar{X}^{(1)}_j,\ldots,\bar{X}^{(t)}_j\right\}\right), \qquad j=1,\ldots,d. μ j = Median ( { X ˉ j ( 1 ) , … , X ˉ j ( t ) } ) , j = 1 , … , d .
The number of buckets is dictated by the geometry of the loss, namely by the effective exponent p ˉ \bar{p} p ˉ . More precisely, the estimator uses
t ( p ˉ ) = 2 ⌊ p ˉ 2 ⌋ − 1 t(\bar{p}) = 2\left\lfloor\frac{\bar{p}}{2}\right\rfloor- 1 t ( p ˉ ) = 2 ⌊ 2 p ˉ ⌋ − 1
buckets, with the median taken over the nonempty buckets. When 1 ≤ p < 2 1 \le p < 2 1 ≤ p < 2 , we have t ( p ˉ ) = 1 t(\bar{p}) = 1 t ( p ˉ ) = 1 , so the estimator is just the ordinary sample mean. The same happens at p = 2 p = 2 p = 2 , recovering exactly the Euclidean behavior in (1) . When p > 2 p > 2 p > 2 and p ˉ > 2 \bar{p} > 2 p ˉ > 2 , the estimator becomes a genuine coordinate-wise median of means estimator, with the number of buckets increasing with p ˉ \bar{p} p ˉ . Finally, in the extreme regime where t ( p ˉ ) > n t(\bar{p}) > n t ( p ˉ ) > n , every nonempty bucket contains a single observation, and the procedure reduces to the coordinate-wise median of the sample points. The technical difficulty is to show that these regimes match sharply and together give the precise minimax rate above.
Phase transition and the existing general norm results. Our in expectation analysis complements the existing high probability theory of robust mean estimation with respect to general norms. Sub-Gaussian mean estimators for general norms were studied, in different forms, in [14 Min25, 10 ] . The original benchmark in [14 ] is distribution dependent and is centered around robustly reproducing the performance of the empirical mean, together with the correct one dimensional sub-Gaussian deviation term. Informally, in our ℓ p \ell_p ℓ p setup this benchmark contains a term of the form
E ∥ 1 n ∑ i = 1 n ( X i − μ ) ∥ p , \mathbb{E}\left\|\frac{1}{n}\sum_{i=1}^{n}(X_i-\mu)\right\|_p, E n 1 i = 1 ∑ n ( X i − μ ) p ,
or its symmetrized analogue. This is the natural target if the goal is to obtain optimal high probability tails around the performance of the sample mean. However, for the problem considered in this paper, this benchmark can be too large: as follows from our results, for p > 2 p > 2 p > 2 , the sample mean itself is already suboptimal even in expectation.7
A related but different point is emphasized in [10 ] . If one takes Gaussian mean estimation as the benchmark, then the relevant complexity is the Gaussian width of the dual ball inducing the norm. In the case of the ℓ p \ell_p ℓ p norm and identity covariance, this gives
E ∥ G ∥ p n ≍ d 1 / p ˉ p ˉ n , \frac{\mathbb{E}\|G\|_p}{\sqrt{n}} \asymp d^{1/\bar{p}}\sqrt{\frac{\bar{p}}{n}}, n E ∥ G ∥ p ≍ d 1/ p ˉ n p ˉ ,
where G ∼ N ( 0 , I d ) G \sim N(0,I_d) G ∼ N ( 0 , I d ) and p ˉ = min { p , max { log d , 1 } } \bar{p} = \min\{p,\max\{\log d,1\}\} p ˉ = min { p , max { log d , 1 }} . Thus, the second branch of our theorem,
d 1 / p ˉ p ˉ n , d^{1/\bar{p}}\sqrt{\frac{\bar{p}}{n}}, d 1/ p ˉ n p ˉ ,
coincides exactly with the Gaussian width benchmark. In this regime, our estimator achieves the same rate that the sample mean would have for Gaussian data; this may be called the sub-Gaussian regime. The genuinely new phenomenon provided by our analysis is the first branch,
d 2 1 / p ˉ . d^{2^{1/\bar{p}}}. d 2 1/ p ˉ .
This term does not appear in the Gaussian mean estimation setup. It reflects a finite sample heavy-tailed regime under only a covariance assumption. Morally, the Gaussian width rate is correct once the number of samples is large enough relative to the effective exponent p ˉ \bar{p} p ˉ . When this condition fails, the minimax risk enters a different phase.
Phase transition and the Gaussian location estimation problem. The Gaussian width branch of Theorem 1.1 is also closely connected to the classical minimax theory of Gaussian location estimation. In the Gaussian location model, Anderson’s lemma implies an exact minimax identity for every bowl-shaped loss; see the original inequality of Anderson [3 ] and the modern presentation in [PW25, Section 28.6]. In particular, for X 1 , … , X n ∼ N ( μ , I d ) X_1,\ldots,X_n \sim N(\mu,I_d) X 1 , … , X n ∼ N ( μ , I d ) , Anderson’s lemma implies
inf μ ^ sup μ ∈ R d E ∥ μ ^ − μ ∥ p = E ∥ G ∥ p n ≍ d 1 / p ˉ p ˉ n , G ∼ N ( 0 , I d ) , p ˉ = min { p , max { log d , 1 } } . \inf_{\widehat{\mu}}\sup_{\mu\in\mathbb{R}^d}\mathbb{E}\|\widehat{\mu}-\mu\|_p
= \frac{\mathbb{E}\|G\|_p}{\sqrt{n}}
\asymp d^{1/\bar{p}}\sqrt{\frac{\bar{p}}{n}},
\qquad G\sim N(0,I_d),\qquad\bar{p}=\min\{p,\max\{\log d,1\}\}. μ inf μ ∈ R d sup E ∥ μ − μ ∥ p = n E ∥ G ∥ p ≍ d 1/ p ˉ n p ˉ , G ∼ N ( 0 , I d ) , p ˉ = min { p , max { log d , 1 }} .
Thus, as discussed above, the second branch of our theorem is exactly the classical Gaussian location obstruction. Our result shows that this Gaussian answer is not the whole story under only a covariance assumption. For the much larger class of all distributions with covariance I d I_d I d , the Gaussian benchmark remains sharp only when
p ˉ ≤ 2 ⌊ n 2 ⌋ . \bar{p}\le2\left\lfloor\frac{n}{2}\right\rfloor. p ˉ ≤ 2 ⌊ 2 n ⌋ .
When this condition fails, heavy-tailed distributions create an additional obstruction, and the minimax risk becomes d 2 1 / p ˉ d^{2^{1/\bar{p}}} d 2 1/ p ˉ . In this sense, Theorem 1.1 may be viewed as a heavy-tailed, covariance-only analogue of the classical Gaussian location minimax identity.
High probability implications and limitations of projection-based estimators. As of now, the full high probability minimax picture for ℓ p \ell_p ℓ p norms remains unclear. In particular, the aforementioned general norm results do not directly provide the matching high probability behavior for ℓ p \ell_p ℓ p norms under only the covariance assumption. Our theorem in expectation already shows that the sample mean can be suboptimal. On the negative side, we further show that natural projection-based median of means estimators, of the type used in the general norm theory [14 Min25, 10 OR25] , can also fail to achieve the correct ℓ p \ell_p ℓ p behavior.
Informally, a projection-based median of means estimator works as follows. It searches for a point whose projection in every dual direction agrees with the median of the projected bucket means:
μ ^ p r o j ∈ arg min x sup ∥ v ∥ q ≤ 1 ∣ ⟨ v , x ⟩ − Median ( { ⟨ v , X ‾ ( 1 ) ⟩ , … , ⟨ v , X ‾ ( t ) ⟩ } ) ∣ , 1 p + 1 q = 1. \widehat{\mu}_{\mathrm{proj}}\in\arg\min_x\sup_{\|v\|_q\le1}\left|\langle v,x\rangle-\operatorname{Median}\left(\{\langle v,\overline{X}^{(1)}\rangle,\ldots,\langle v,\overline{X}^{(t)}\rangle\}\right)\right|,
\qquad\frac{1}{p}+\frac{1}{q}=1. μ proj ∈ arg x min ∥ v ∥ q ≤ 1 sup ⟨ v , x ⟩ − Median ( {⟨ v , X ( 1 ) ⟩ , … , ⟨ v , X ( t ) ⟩} ) , p 1 + q 1 = 1.
This construction is natural as a generic norm-agnostic procedure, but our result shows that it can be too crude even for the classical family of ℓ p \ell_p ℓ p norms once p > 2 p>2 p > 2 .
Theorem 1.2 (Suboptimality of Projection-based median-of-means). Let p > 2 p > 2 p > 2 . There exist absolute constants C , c > 0 C, c > 0 C , c > 0 such that the following hold. Let d , n ∈ N d, n \in\mathbb{N} d , n ∈ N be such that n ≤ c d n \le c\sqrt{d} n ≤ c d and d > C d > C d > C . Then, there exists a distribution D D D with mean 0 0 0 and covariance I d I_d I d such that the projection-based median-of-means estimator with any bucket size m m m satisfying n / m ≥ 3 n/m \ge3 n / m ≥ 3 , μ ^ P r o j \hat{\mu}_{\mathrm{Proj}} μ ^ Proj , satisfies:
P r X ∼ D ⊗ n [ ∥ μ ^ P r o j ( X ) ∥ p ≥ d 2 n 1 − 1 / p ] ≥ 0.9. \mathop{\mathrm{Pr}}_{X\sim D^{\otimes n}}\left[\left\|\hat{\mu}_{\mathrm{Proj}}(X)\right\|_p \ge\frac{\sqrt{d}}{2n^{1-1/p}}\right] \ge0.9. Pr X ∼ D ⊗ n [ ∥ μ ^ Proj ( X ) ∥ p ≥ 2 n 1 − 1/ p d ] ≥ 0.9.
This should be compared with the coordinate-wise estimator analyzed above. In the Gaussian width regime, the latter achieves a much smaller rate. For example, for p = ∞ p = \infty p = ∞ and log d ≲ n ≪ d \log d \lesssim n \ll\sqrt{d} log d ≲ n ≪ d , the coordinate-wise estimator has error of order, with constant probability,
log d n , \sqrt{\frac{\log d}{n}}, n log d ,
while the projection-based median of means lower bound is of order, again with constant probability,
d n . \frac{\sqrt{d}}{n}. n d .
Thus, in this regime the projection-based estimator pays a polynomial price in the dimension, while the coordinate-wise estimator has only logarithmic dependence. This shows that, for structured norms such as ℓ p \ell_p ℓ p , one needs to go beyond projection-based estimators for general norms.
A high probability result for the ℓ ∞ \ell_\infty ℓ ∞ norm. Although our main focus is on the results in expectation, as a complementary result we give a sharp high probability analysis for the ℓ ∞ \ell_\infty ℓ ∞ norm. This result is the high probability analogue of the phase transition phenomenon above, and refines even the constant probability regimes implied by our analysis in expectation.
Theorem 1.3 (ℓ ∞ \ell_\infty ℓ ∞ high probability phase transition, informal). Under only the covariance assumption Cov P ( X ) = I d \operatorname{Cov}_P(X) = I_d Cov P ( X ) = I d , the optimal ℓ ∞ \ell_\infty ℓ ∞ error at confidence level 1 − δ 1-\delta 1 − δ is, up to universal constants,
{ ( d δ ) 1 2 ⌈ n / 2 ⌉ , n ≲ log ( d / δ ) , log ( d / δ ) n , n ≳ log ( d / δ ) . \begin{cases}
\left(\dfrac{d}{\delta}\right)^{\frac{1}{2\lceil n/2\rceil}}, & n \lesssim\log(d/\delta),\\
\sqrt{\dfrac{\log(d/\delta)}{n}}, & n \gtrsim\log(d/\delta).
\end{cases} ⎩ ⎨ ⎧ ( δ d ) 2 ⌈ n /2 ⌉ 1 , n log ( d / δ ) , n ≲ log ( d / δ ) , n ≳ log ( d / δ ) .
The upper bound is achieved by the coordinate-wise median of means estimator with t = 2 ⌈ log ( d / δ ) ⌉ t = 2\lceil\log(d/\delta)\rceil t = 2 ⌈ log ( d / δ )⌉ buckets, and the lower bound holds for every estimator.
As before, the first regime is genuinely non-Gaussian: the error is polynomial in d / δ d/\delta d / δ , although the exponent decreases with the sample size. Once n n n is of order log ( d / δ ) \log(d/\delta) log ( d / δ ) , the usual sub-Gaussian rate takes over. Thus, even for the classical ℓ ∞ \ell_\infty ℓ ∞ norm, the Gaussian width or sub-Gaussian benchmark captures only the large sample side of the theory, while under only a covariance assumption there is an additional finite sample heavy-tailed phase. This also highlights a limitation of projection-based estimators: in the regimes where the coordinate-wise estimator attains the sharp ℓ ∞ \ell_\infty ℓ ∞ rate, projection-based median of means estimators can be polynomially suboptimal, as shown by Theorem 1.2 .
On computation and coordinate-wise medians. A significant line of work on heavy tailed mean estimation in the Euclidean norm studies polynomial time estimators with sub-Gaussian guarantees under finite covariance assumptions; see, for example, [12 , 7 , 11 , 9 ] . In the main regimes in expectation studied here, computation is essentially trivial: the optimal estimator is coordinate-wise and reduces to bucket averages and one dimensional medians. At the same time, coordinate-wise median of means is not universally optimal. In the high probability Euclidean problem, no single distribution independent choice of the number of buckets is optimal for all distributions with identity covariance. We prove the following result.
Theorem 1.4 (Suboptimality of coordinate-wise median-of-means). There are universal constants c , C ≥ 0 c, C \ge0 c , C ≥ 0 such that the following holds. For any δ ∈ ( 0 , c ) \delta\in(0,c) δ ∈ ( 0 , c ) and n , d , t ∈ N n,d,t \in\mathbb{N} n , d , t ∈ N with t ≤ n t \le n t ≤ n , there exists a distribution P P P over R d \mathbb{R}^{d} R d with mean 0 0 0 and covariance I d I_d I d such that if Algorithm 1 is ran with t t t buckets and sample X 1 , … , X n ∼ P X_1,\ldots,X_n \sim P X 1 , … , X n ∼ P as input, it returns an estimate μ ^ \hat{\mu} μ ^ satisfying
Pr X 1 , … , X n ∼ P [ ∥ μ ^ ∥ 2 ≥ C d log ( 1 / δ ) n log log ( 1 / δ ) ] > δ . \Pr_{X_1,\ldots,X_n\sim P}\left[\|\hat{\mu}\|_2 \ge C\sqrt{\frac{d\log(1/\delta)}{n\log\log(1/\delta)}}\right] > \delta. X 1 , … , X n ∼ P Pr [ ∥ μ ^ ∥ 2 ≥ C n log log ( 1/ δ ) d log ( 1/ δ ) ] > δ .
This is expected, and probably folklore, but we include it for completeness in Section C. The complete high probability theory for general norms therefore remains substantially more delicate than the picture in expectation developed here.8
Notation and Organization
We begin with some notation. We use log \log log to denote the natural logarithm. For a real number a a a , we will use ⌊ a ⌋ \lfloor a\rfloor ⌊ a ⌋ and ⌈ a ⌉ \lceil a\rceil ⌈ a ⌉ to denote its floor and ceiling respectively. For a positive integer a a a , we will often use the fact that ⌊ a + 1 2 ⌋ \left\lfloor\frac{a+1}{2}\right\rfloor ⌊ 2 a + 1 ⌋ is a short form for a + 1 2 \frac{a+1}{2} 2 a + 1 when a a a is odd and a 2 \frac{a}{2} 2 a when a a a is even. For a multiset of real numbers, { a i } i = 1 n \{a_i\}_{i=1}^n { a i } i = 1 n , we use a ( 1 ) ≥ a ( 2 ) ⋯ ≥ a ( n ) a_{(1)} \ge a_{(2)} \cdots\ge a_{(n)} a ( 1 ) ≥ a ( 2 ) ⋯ ≥ a ( n ) to denote the decreasing rearrangement of its elements with the median being a ⌊ ( n + 1 ) / 2 ⌋ a_{\lfloor(n+1)/2\rfloor} a ⌊( n + 1 ) /2 ⌋ if n n n is odd or ( a ( n / 2 ) + a ( n / 2 + 1 ) ) / 2 (a_{(n/2)} + a_{(n/2+1)})/2 ( a ( n /2 ) + a ( n /2 + 1 ) ) /2 when n n n is even. For positive integer a a a we define [ a ] = { 1 , 2 , … , a } [a] = \{1,2,\ldots,a\} [ a ] = { 1 , 2 , … , a } . We use c , C c,C c , C for universal constants, and their value may change from line to line. For x ∈ R d x \in\mathbb{R}^d x ∈ R d and p ∈ [ 1 , ∞ ) p \in[1,\infty) p ∈ [ 1 , ∞ ) , we use ∥ x ∥ p \|x\|_p ∥ x ∥ p to denote the ℓ p \ell_p ℓ p norm of x x x , with q q q typically used to denote the dual norm exponent satisfying 1 p + 1 q = 1 \frac{1}{p}+\frac{1}{q}=1 p 1 + q 1 = 1 . We use e 1 , … , e d ∈ R d e_1,\ldots,e_d \in\mathbb{R}^d e 1 , … , e d ∈ R d to denote the standard basis vectors over R d \mathbb{R}^d R d . We use I d I_d I d for identity matrix whose dimension will be clear from context.
For a distribution P P P over X \mathcal{X} X , event A : X → { 0 , 1 } A:\mathcal{X}\to\{0,1\} A : X → { 0 , 1 } and function f : X → R f:\mathcal{X}\to\mathbb{R} f : X → R , we will use Pr X ∼ P [ A ( X ) ] \Pr_{X\sim P}[A(X)] Pr X ∼ P [ A ( X )] , and E X ∼ P [ f ( X ) ] \mathbb{E}_{X\sim P}[f(X)] E X ∼ P [ f ( X )] to be the probability of event A A A and the expectation of f f f when X X X is drawn from P P P respectively. When a random variable or its distribution is clear from context, we often drop the subscript and simply write Pr P ( E P ) \Pr_P(\mathbb{E}_P) Pr P ( E P ) or Pr ( E ) \Pr(\mathbb{E}) Pr ( E ) . Furthermore, for a natural number n n n , we use P ⊗ n P^{\otimes n} P ⊗ n to denote the product distribution over n n n i.i.d. samples from P P P . For a distribution P P P over R d \mathbb{R}^d R d with mean μ \mu μ , we define the covariance matrix as Cov P ( X ) = E X ∼ P [ X X T ] − μ μ T \operatorname{Cov}_P(X)=\mathbb{E}_{X\sim P}[XX^{\mathsf{T}}]-\mu\mu^{\mathsf{T}} Cov P ( X ) = E X ∼ P [ X X T ] − μ μ T .
For quantities a , b a,b a , b , we write a ≲ b a\lesssim b a ≲ b (a ≳ b a\gtrsim b a ≳ b ) if there exists a universal constant C > 0 C>0 C > 0 (c > 0 c>0 c > 0 ) such that a ≤ C b a\le Cb a ≤ C b (a ≥ c b a\ge cb a ≥ c b ) uniformly over the relevant parameter ranges which will be clear from context. We write a = O ( b ) a=O(b) a = O ( b ) (a = Ω ( b ) a=\Omega(b) a = Ω ( b ) ) if a ≲ b a\lesssim b a ≲ b (a ≳ b a\gtrsim b a ≳ b ) asymptotically in the relevant parameters and a = Θ ( b ) a=\Theta(b) a = Θ ( b ) if both hold. Finally, a = o ( b ) a=o(b) a = o ( b ) (a = ω ( b ) a=\omega(b) a = ω ( b ) ) if a b \frac{a}{b} b a (b a \frac{b}{a} a b ) goes to 0 0 0 asymptotically.
Organization: The remainder of the paper is organized as follows: Theorem 1.1 is formalized and proved in § 3 , Theorem 1.3 in Section 4, Theorem 1.2 in Section B, and Theorem 1.4 in Section C.
Optimal In-expectation Guarantees
In this section we prove sharp bounds for the mini-max risk of heavy-tailed isotropic mean estimation. The minimax risk of sample size n n n , dimension d d d and norm ∥ ⋅ ∥ : R d → R ≥ 0 \|\cdot\|:\mathbb{R}^{d}\to\mathbb{R}_{\ge0} ∥ ⋅ ∥ : R d → R ≥ 0 is defined as follows:
R ( n , d , ∥ ⋅ ∥ ) = inf A : ( R d ) n → R d sup μ ∈ R d P : E P [ X ] = μ , Cov P ( X ) = I d E X 1 , … , X n ∼ P [ ∥ A ( X 1 , … , X n ) − μ ∥ ] . (2) \mathfrak{R}(n,d,\|\cdot\|)=\inf_{A:(\mathbb{R}^{d})^{n}\to\mathbb{R}^{d}}\sup_{\substack{\mu\in\mathbb{R}^{d}\\ P:\mathbb{E}_{P}[X]=\mu,\ \operatorname{Cov}_{P}(X)=I_{d}}}\mathbb{E}_{X_{1},\ldots,X_{n}\sim P}\left[\|A(X_{1},\ldots,X_{n})-\mu\|\right]. \tag*{(2)} R ( n , d , ∥ ⋅ ∥ ) = A : ( R d ) n → R d inf μ ∈ R d P : E P [ X ] = μ , Cov P ( X ) = I d sup E X 1 , … , X n ∼ P [ ∥ A ( X 1 , … , X n ) − μ ∥ ] . (2)
In words, this is the smallest expected error when estimating the mean, measured in the norm ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ , that an estimator can guarantee based on n n n samples, uniformly over all d d d -dimensional distributions with identity covariance. For ℓ p \ell_{p} ℓ p norms, we will simply write R ( n , d , p ) = R ( n , d , ∥ ⋅ ∥ p ) \mathfrak{R}(n,d,p)=\mathfrak{R}(n,d,\|\cdot\|_{p}) R ( n , d , p ) = R ( n , d , ∥ ⋅ ∥ p ) .
To state our main result, it will be useful to setup some notation that will be used throughout this section. We will make frequent use of the truncated version of p ∈ [ 1 , ∞ ] p\in[1,\infty] p ∈ [ 1 , ∞ ] defined as
p ˉ = min { p , max { log d , 1 } } . (3) \bar{p}=\min\{p,\max\{\log d,1\}\}. \tag*{(3)} p ˉ = min { p , max { log d , 1 }} . (3)
The truncation at log d \log d log d is because for any p , q p,q p , q such that log d ≤ p ≤ q \log d\le p\le q log d ≤ p ≤ q , we have that e − 1 ∥ ⋅ ∥ p ≤ ∥ ⋅ ∥ q ≤ ∥ ⋅ ∥ p e^{-1}\|\cdot\|_{p}\le\|\cdot\|_{q}\le\|\cdot\|_{p} e − 1 ∥ ⋅ ∥ p ≤ ∥ ⋅ ∥ q ≤ ∥ ⋅ ∥ p , i.e. the norms are equivalent up to a constant factor. Thus, the minimax risk with respect to ℓ p \ell_{p} ℓ p and ℓ q \ell_{q} ℓ q are equivalent up to a constant factor so it suffices to consider the range p ∈ [ 1 , log d ] p\in[1,\log d] p ∈ [ 1 , log d ] .9
We can now state our main result.
Theorem 3.1. For any n , d ∈ N n,d\in\mathbb{N} n , d ∈ N and p ∈ [ 1 , ∞ ] p\in[1,\infty] p ∈ [ 1 , ∞ ] we have that
R ( n , p , d ) ≍ { d 1 2 ⌈ n / 2 ⌉ , p ˉ > 2 ⌈ n 2 ⌉ , d 1 p ˉ p ˉ n , p ˉ ≤ 2 ⌈ n 2 ⌉ . \mathfrak{R}(n,p,d)\asymp
\begin{cases}
d^{\frac{1}{2^{\lceil n/2\rceil}}}, & \bar{p}>2\left\lceil\frac{n}{2}\right\rceil,\\
d^{\frac{1}{\bar{p}}}\sqrt{\frac{\bar{p}}{n}}, & \bar{p}\le2\left\lceil\frac{n}{2}\right\rceil.
\end{cases} R ( n , p , d ) ≍ ⎩ ⎨ ⎧ d 2 ⌈ n /2 ⌉ 1 , d p ˉ 1 n p ˉ , p ˉ > 2 ⌈ 2 n ⌉ , p ˉ ≤ 2 ⌈ 2 n ⌉ . Equivalently, if we define s = min { p ˉ , 2 ⌈ n 2 ⌉ } s=\min\{\bar{p},2\left\lceil\frac{n}{2}\right\rceil\} s = min { p ˉ , 2 ⌈ 2 n ⌉ } , then
R ( n , p , d ) ≍ d 1 s s n . \mathfrak{R}(n,p,d)\asymp d^{\frac{1}{s}}\sqrt{\frac{s}{n}}. R ( n , p , d ) ≍ d s 1 n s . Moreover, this rate is achieved by the coordinate-wise median-of-means estimator.
Remark 3.2. Observe that a phase transition occurs exactly at p ˉ = 2 ⌈ n 2 ⌉ \bar{p}=2\left\lceil\frac{n}{2}\right\rceil p ˉ = 2 ⌈ 2 n ⌉ , where the small sample size regime 2 ⌈ n 2 ⌉ < p ˉ 2\left\lceil\frac{n}{2}\right\rceil<\bar{p} 2 ⌈ 2 n ⌉ < p ˉ rate d 1 2 ⌈ n / 2 ⌉ d^{\frac{1}{2^{\lceil n/2\rceil}}} d 2 ⌈ n /2 ⌉ 1 changes to the large sample size regime p ˉ ≤ 2 ⌈ n 2 ⌉ \bar{p}\le2\left\lceil\frac{n}{2}\right\rceil p ˉ ≤ 2 ⌈ 2 n ⌉ rate d 1 p ˉ p ˉ n d^{\frac{1}{\bar{p}}}\sqrt{\frac{\bar{p}}{n}} d p ˉ 1 n p ˉ .
Upper bound
In this section we prove upper bounds on the expected error of the coordinate-wise median-of-means estimator (Algorithm 1) when used to estimate the mean with respect to ℓ p \ell_{p} ℓ p norms for p ∈ [ 1 , ∞ ] p\in[1,\infty] p ∈ [ 1 , ∞ ] . We will make frequent use of the function t ( p ˉ ) t(\bar{p}) t ( p ˉ ) :
t ( p ˉ ) = 2 ⌈ p ˉ 2 ⌉ − 1. (4) t(\bar{p})=2\left\lceil\frac{\bar{p}}{2}\right\rceil-1. \tag*{(4)} t ( p ˉ ) = 2 ⌈ 2 p ˉ ⌉ − 1. (4)
Algorithm 1 Coordinate-wise Median-of-Means
Require: Number of buckets t ≤ n t \le n t ≤ n , samples X 1 , … , X n ∈ R d X_1,\ldots,X_n \in\mathbb{R}^d X 1 , … , X n ∈ R d
1: Partition [ n ] [n] [ n ] into t t t size-balanced buckets B 1 , … , B t B_1,\ldots,B_t B 1 , … , B t by setting B i = { m ∈ [ n ] : m ≡ i ( m o d t ) } B_i=\{m\in[n]:m\equiv i\pmod{t}\} B i = { m ∈ [ n ] : m ≡ i ( mod t )} 2: for i = 1 i=1 i = 1 to t t t do 3: μ ^ ( i ) ← 1 ∣ B i ∣ ∑ m ∈ B i X m \hat{\mu}^{(i)}\leftarrow\frac{1}{\lvert B_i\rvert}\sum_{m\in B_i}X_m μ ^ ( i ) ← ∣ B i ∣ 1 ∑ m ∈ B i X m 4: end for 5: return μ ^ ← Median ( μ ^ ( 1 ) , … , μ ^ ( t ) ) \hat{\mu}\leftarrow\operatorname{Median}(\hat{\mu}^{(1)},\ldots,\hat{\mu}^{(t)}) μ ^ ← Median ( μ ^ ( 1 ) , … , μ ^ ( t ) ) ▷ coordinate-wise median
We will use t ( p ˉ ) t(\bar{p}) t ( p ˉ ) as the number of buckets in coordinate-wise median-of-means estimator Algorithm 1 when estimating the mean with respect to the ℓ p \ell_p ℓ p norm. Notice that in the case that p ∈ [ 1 , 2 ] p\in[1,2] p ∈ [ 1 , 2 ] , the number of buckets is just 1 and Algorithm 1 reduces to the usual sample mean that is optimal in-expectation for p ∈ [ 1 , 2 ] p\in[1,2] p ∈ [ 1 , 2 ] .
We now state our upper bound on the performance of Algorithm 1 for estimating the mean of a random vector in R d \mathbb{R}^d R d under ℓ p \ell_p ℓ p norm for any p ≥ 1 p\ge1 p ≥ 1 .
Theorem 3.3. Let X 1 , … , X n ∈ R d X_1,\ldots,X_n\in\mathbb{R}^d X 1 , … , X n ∈ R d be i.i.d. random vectors with finite mean μ \mu μ and covariance Σ \Sigma Σ . Fix p ≥ 1 p\ge1 p ≥ 1 . Given the number of buckets t ( p ˉ ) t(\bar{p}) t ( p ˉ ) and the sample X 1 , … , X n X_1,\ldots,X_n X 1 , … , X n as input, Algorithm 1 returns an estimate μ ^ \hat{\mu} μ ^ satisfying
E [ ∥ μ ^ − μ ∥ p ] ≤ { 2 ( ∑ j = 1 d Σ j j p ˉ / 2 ) 1 / p ˉ , p ˉ > 2 ⌈ n 2 ⌉ , 2 ( ∑ j = 1 d Σ j j p ˉ / 2 ) 1 / p ˉ ⌊ n / t ( p ˉ ) ⌋ , p ˉ ≤ 2 ⌈ n 2 ⌉ . \mathbb{E}\left[\lVert\hat{\mu}-\mu\rVert_p\right]\le
\begin{cases}
2\left(\sum_{j=1}^{d}\Sigma_{jj}^{\bar{p}/2}\right)^{1/\bar{p}}\!, & \bar{p}>2\left\lceil\frac{n}{2}\right\rceil,\\[6pt]
2\frac{\left(\sum_{j=1}^{d}\Sigma_{jj}^{\bar{p}/2}\right)^{1/\bar{p}}}{\sqrt{\lfloor n/t(\bar{p})\rfloor}}, & \bar{p}\le2\left\lceil\frac{n}{2}\right\rceil.
\end{cases} E [ ∥ μ ^ − μ ∥ p ] ≤ ⎩ ⎨ ⎧ 2 ( ∑ j = 1 d Σ j j p ˉ /2 ) 1/ p ˉ , 2 ⌊ n / t ( p ˉ )⌋ ( ∑ j = 1 d Σ j j p ˉ /2 ) 1/ p ˉ , p ˉ > 2 ⌈ 2 n ⌉ , p ˉ ≤ 2 ⌈ 2 n ⌉ . Moreover, if we define s = min { p ˉ , 2 ⌈ n 2 ⌉ } s=\min\{\bar{p},2\left\lceil\frac{n}{2}\right\rceil\} s = min { p ˉ , 2 ⌈ 2 n ⌉ } then
E [ ∥ μ ^ − μ ∥ p ] ≤ 4 ( ∑ j = 1 d Σ j j s / 2 ) 1 / s s n . \mathbb{E}\left[\lVert\hat{\mu}-\mu\rVert_p\right]\le4\left(\sum_{j=1}^{d}\Sigma_{jj}^{s/2}\right)^{1/s}\sqrt{\frac{s}{n}}. E [ ∥ μ ^ − μ ∥ p ] ≤ 4 ( j = 1 ∑ d Σ j j s /2 ) 1/ s n s .
To prove Theorem 3.3 , we will need the following moment bound on the deviation of the empirical median from the population mean which is a slight generalization of a result due to [17 ] . For completeness, we include a proof in Section A.
Theorem 3.4. Let X 1 , … , X t X_1,\ldots,X_t X 1 , … , X t be t t t independent random variables with a common mean μ \mu μ and let M = M ( X 1 , … , X t ) M=M(X_1,\ldots,X_t) M = M ( X 1 , … , X t ) denote their median. For all q ≥ 0 q\ge0 q ≥ 0 it holds that
E [ ∣ M − μ ∣ q ⌈ t 2 ⌉ ] ≤ ( t ⌈ t 2 ⌉ ) max i ∈ [ t ] E [ ∣ X i − μ ∣ q ⌈ t 2 ⌉ ] . \mathbb{E}\left[\lvert M-\mu\rvert^{q\left\lceil\frac{t}{2}\right\rceil}\right]\le\binom{t}{\left\lceil\frac{t}{2}\right\rceil}\max_{i\in[t]}\mathbb{E}\left[\lvert X_i-\mu\rvert^{q\left\lceil\frac{t}{2}\right\rceil}\right]. E [ ∣ M − μ ∣ q ⌈ 2 t ⌉ ] ≤ ( ⌈ 2 t ⌉ t ) i ∈ [ t ] max E [ ∣ X i − μ ∣ q ⌈ 2 t ⌉ ] .
Proof of Theorem 3.3 . We consider two cases. First, let us consider the case that p ˉ ≤ 2 ⌈ n 2 ⌉ \bar{p}\le2\left\lceil\frac{n}{2}\right\rceil p ˉ ≤ 2 ⌈ 2 n ⌉ . Notice that this condition is equivalent to the condition that n ≥ t ( p ˉ ) n\ge t(\bar{p}) n ≥ t ( p ˉ ) , which will be more convenient to use in what follows. Indeed, we have that
t ( p ˉ ) ≤ n ⟺ ⌈ p ˉ 2 ⌉ ≤ ⌊ n + 1 2 ⌋ ⟺ ⌈ p ˉ 2 ⌉ ≤ ⌊ n 2 ⌋ ⟺ p ˉ 2 ≤ ⌊ n 2 ⌋ ⟺ p ˉ ≤ 2 ⌊ n 2 ⌋ . (5) t(\bar{p})\le n\Longleftrightarrow\left\lceil\frac{\bar{p}}{2}\right\rceil\le\left\lfloor\frac{n+1}{2}\right\rfloor\Longleftrightarrow\left\lceil\frac{\bar{p}}{2}\right\rceil\le\left\lfloor\frac{n}{2}\right\rfloor\Longleftrightarrow\frac{\bar{p}}{2}\le\left\lfloor\frac{n}{2}\right\rfloor\Longleftrightarrow\bar{p}\le2\left\lfloor\frac{n}{2}\right\rfloor. \tag*{(5)} t ( p ˉ ) ≤ n ⟺ ⌈ 2 p ˉ ⌉ ≤ ⌊ 2 n + 1 ⌋ ⟺ ⌈ 2 p ˉ ⌉ ≤ ⌊ 2 n ⌋ ⟺ 2 p ˉ ≤ ⌊ 2 n ⌋ ⟺ p ˉ ≤ 2 ⌊ 2 n ⌋ . (5)
Now, using the fact that ∥ ⋅ ∥ p ≤ ∥ ⋅ ∥ p ˉ \lVert\cdot\rVert_p \le\lVert\cdot\rVert_{\bar p} ∥ ⋅ ∥ p ≤ ∥ ⋅ ∥ p ˉ together with Jensen’s inequality yields
E [ ∥ μ ^ − μ ∥ p ] ≤ E [ ∥ μ ^ − μ ∥ p ˉ ] ≤ E [ ∥ μ ^ − μ ∥ p ˉ p ˉ ] 1 p ˉ = ( ∑ j = 1 d E [ ∣ μ ^ j − μ j ∣ p ˉ ] ) 1 p ˉ . (6) \mathbb{E}\left[\lVert\hat{\mu}-\mu\rVert_p\right] \le\mathbb{E}\left[\lVert\hat{\mu}-\mu\rVert_{\bar p}\right] \le\mathbb{E}\left[\lVert\hat{\mu}-\mu\rVert_{\bar p}^{\bar p}\right]^{\frac{1}{\bar p}} = \left(\sum_{j=1}^{d}\mathbb{E}\left[|\hat{\mu}_j-\mu_j|^{\bar p}\right]\right)^{\frac{1}{\bar p}}. \tag*{(6)} E [ ∥ μ ^ − μ ∥ p ] ≤ E [ ∥ μ ^ − μ ∥ p ˉ ] ≤ E [ ∥ μ ^ − μ ∥ p ˉ p ˉ ] p ˉ 1 = ( j = 1 ∑ d E [ ∣ μ ^ j − μ j ∣ p ˉ ] ) p ˉ 1 . (6)
It now suffices to bound the terms E [ ∣ μ ^ j − μ j ∣ p ˉ ] \mathbb{E}\left[|\hat{\mu}_j-\mu_j|^{\bar p}\right] E [ ∣ μ ^ j − μ j ∣ p ˉ ] . Notice that ⌈ t ( p ˉ ) 2 ⌉ = ⌊ t ( p ˉ ) + 1 2 ⌋ = ⌈ p ˉ 2 ⌉ ≥ 1 \left\lceil\frac{t(\bar p)}{2}\right\rceil=\left\lfloor\frac{t(\bar p)+1}{2}\right\rfloor=\left\lceil\frac{\bar p}{2}\right\rceil\ge1 ⌈ 2 t ( p ˉ ) ⌉ = ⌊ 2 t ( p ˉ ) + 1 ⌋ = ⌈ 2 p ˉ ⌉ ≥ 1 , so there is some q ∈ [ 1 , 2 ] q\in[1,2] q ∈ [ 1 , 2 ] such that q ⌈ t ( p ˉ ) 2 ⌉ = p ˉ q\left\lceil\frac{t(\bar p)}{2}\right\rceil=\bar p q ⌈ 2 t ( p ˉ ) ⌉ = p ˉ . Thus, we can invoke the moment bound of Theorem 3.4 with t = t ( p ˉ ) t=t(\bar p) t = t ( p ˉ ) and q ∈ [ 1 , 2 ] q\in[1,2] q ∈ [ 1 , 2 ] as above together with Jensen’s inequality to get
E [ ∣ μ ^ j − μ j ∣ p ˉ ] ≤ ( t ( p ˉ ) ⌈ t ( p ˉ ) 2 ⌉ ) max i ∈ [ t ( p ˉ ) ] E [ ∣ μ ^ j ( i ) − μ j ∣ q ] ⌈ t ( p ˉ ) 2 ⌉ ≤ ( t ( p ˉ ) ⌈ t ( p ˉ ) 2 ⌉ ) max i ∈ [ t ( p ˉ ) ] E [ ∣ μ ^ j ( i ) − μ j ∣ 2 ] q 2 ⌈ t ( p ˉ ) 2 ⌉ ≤ ( t ( p ˉ ) ⌈ t ( p ˉ ) 2 ⌉ ) ( Σ j j ⌊ n / t ( p ˉ ) ⌋ ) q 2 ⌈ t ( p ˉ ) 2 ⌉ = ( t ( p ˉ ) ⌈ t ( p ˉ ) 2 ⌉ ) ( Σ j j ⌊ n / t ( p ˉ ) ⌋ ) p ˉ 2 , \begin{aligned}
\mathbb{E}\left[|\hat{\mu}_j-\mu_j|^{\bar p}\right]\le\binom{t(\bar p)}{\left\lceil\frac{t(\bar p)}{2}\right\rceil}\max_{i\in[t(\bar p)]}\mathbb{E}\left[|\hat{\mu}_j^{(i)}-\mu_j|^q\right]^{\left\lceil\frac{t(\bar p)}{2}\right\rceil} \\
&\le\binom{t(\bar p)}{\left\lceil\frac{t(\bar p)}{2}\right\rceil}\max_{i\in[t(\bar p)]}\mathbb{E}\left[|\hat{\mu}_j^{(i)}-\mu_j|^2\right]^{\frac{q}{2}\left\lceil\frac{t(\bar p)}{2}\right\rceil} \\
&\le\binom{t(\bar p)}{\left\lceil\frac{t(\bar p)}{2}\right\rceil}\left(\frac{\Sigma_{jj}}{\left\lfloor n/t(\bar p)\right\rfloor}\right)^{\frac{q}{2}\left\lceil\frac{t(\bar p)}{2}\right\rceil}
= \binom{t(\bar p)}{\left\lceil\frac{t(\bar p)}{2}\right\rceil}\left(\frac{\Sigma_{jj}}{\left\lfloor n/t(\bar p)\right\rfloor}\right)^{\frac{\bar p}{2}},
\end{aligned} E [ ∣ μ ^ j − μ j ∣ p ˉ ] ≤ ( ⌈ 2 t ( p ˉ ) ⌉ t ( p ˉ ) ) i ∈ [ t ( p ˉ )] max E [ ∣ μ ^ j ( i ) − μ j ∣ q ] ⌈ 2 t ( p ˉ ) ⌉ ≤ ( ⌈ 2 t ( p ˉ ) ⌉ t ( p ˉ ) ) i ∈ [ t ( p ˉ )] max E [ ∣ μ ^ j ( i ) − μ j ∣ 2 ] 2 q ⌈ 2 t ( p ˉ ) ⌉ ≤ ( ⌈ 2 t ( p ˉ ) ⌉ t ( p ˉ ) ) ( ⌊ n / t ( p ˉ ) ⌋ Σ j j ) 2 q ⌈ 2 t ( p ˉ ) ⌉ = ( ⌈ 2 t ( p ˉ ) ⌉ t ( p ˉ ) ) ( ⌊ n / t ( p ˉ ) ⌋ Σ j j ) 2 p ˉ ,
where the last inequality follows from the fact that each bucket gets at least ⌊ n / t ( p ˉ ) ⌋ \lfloor n/t(\bar p)\rfloor ⌊ n / t ( p ˉ )⌋ samples and that the variance of the j j j th coordinate is Σ j j \Sigma_{jj} Σ j j . Plugging the above back into (6) yields
E [ ∥ μ ^ − μ ∥ p ] ≤ ( t ( p ˉ ) ⌈ t ( p ˉ ) 2 ⌉ ) 1 p ˉ ( ∑ j = 1 d ( Σ j j ) p ˉ 2 ) 1 p ˉ ⌊ n / t ( p ˉ ) ⌋ ≤ 2 ( ∑ j = 1 d ( Σ j j ) p ˉ 2 ) 1 p ˉ ⌊ n / t ( p ˉ ) ⌋ , \mathbb{E}\left[\lVert\hat{\mu}-\mu\rVert_p\right]\le\binom{t(\bar p)}{\left\lceil\frac{t(\bar p)}{2}\right\rceil}^{\frac{1}{\bar p}}\frac{\left(\sum_{j=1}^{d}(\Sigma_{jj})^{\frac{\bar p}{2}}\right)^{\frac{1}{\bar p}}}{\sqrt{\lfloor n/t(\bar p)\rfloor}}\le2\frac{\left(\sum_{j=1}^{d}(\Sigma_{jj})^{\frac{\bar p}{2}}\right)^{\frac{1}{\bar p}}}{\sqrt{\lfloor n/t(\bar p)\rfloor}}, E [ ∥ μ ^ − μ ∥ p ] ≤ ( ⌈ 2 t ( p ˉ ) ⌉ t ( p ˉ ) ) p ˉ 1 ⌊ n / t ( p ˉ )⌋ ( ∑ j = 1 d ( Σ j j ) 2 p ˉ ) p ˉ 1 ≤ 2 ⌊ n / t ( p ˉ )⌋ ( ∑ j = 1 d ( Σ j j ) 2 p ˉ ) p ˉ 1 ,
where the final inequality follows from the simple bound
( t ( p ˉ ) ⌈ t ( p ˉ ) 2 ⌉ ) = ( 2 ⌈ p ˉ 2 ⌉ − 1 ⌈ p ˉ 2 ⌉ ) = ( 2 ⌈ p ˉ 2 ⌉ − 1 ⌈ p ˉ 2 ⌉ − 1 ) ≤ ∑ k = 0 ⌈ p ˉ 2 ⌉ − 1 ( 2 ⌈ p ˉ 2 ⌉ − 1 k ) = 2 2 ⌈ p ˉ 2 ⌉ − 2 ≤ 2 p ˉ . \binom{t(\bar p)}{\left\lceil\frac{t(\bar p)}{2}\right\rceil}=\binom{2\left\lceil\frac{\bar p}{2}\right\rceil-1}{\left\lceil\frac{\bar p}{2}\right\rceil}=\binom{2\left\lceil\frac{\bar p}{2}\right\rceil-1}{\left\lceil\frac{\bar p}{2}\right\rceil-1}\le\sum_{k=0}^{\left\lceil\frac{\bar p}{2}\right\rceil-1}\binom{2\left\lceil\frac{\bar p}{2}\right\rceil-1}{k}=2^{2\left\lceil\frac{\bar p}{2}\right\rceil-2}\le2^{\bar p}. ( ⌈ 2 t ( p ˉ ) ⌉ t ( p ˉ ) ) = ( ⌈ 2 p ˉ ⌉ 2 ⌈ 2 p ˉ ⌉ − 1 ) = ( ⌈ 2 p ˉ ⌉ − 1 2 ⌈ 2 p ˉ ⌉ − 1 ) ≤ k = 0 ∑ ⌈ 2 p ˉ ⌉ − 1 ( k 2 ⌈ 2 p ˉ ⌉ − 1 ) = 2 2 ⌈ 2 p ˉ ⌉ − 2 ≤ 2 p ˉ .
Now consider the case that p ˉ > 2 ⌈ n 2 ⌉ \bar p>2\left\lceil\frac{n}{2}\right\rceil p ˉ > 2 ⌈ 2 n ⌉ , which is equivalent to n < t ( p ˉ ) n<t(\bar p) n < t ( p ˉ ) by (5) . In this case, every non-empty bucket has a single sample and the estimator is the coordinate-wise median. Since n < t ( p ˉ ) = 2 ⌈ p ˉ / 2 ⌉ − 1 n<t(\bar p)=2\lceil\bar p/2\rceil-1 n < t ( p ˉ ) = 2 ⌈ p ˉ /2 ⌉ − 1 , a simple case analysis on the parity of n n n shows that p > 2 ⌈ n / 2 ⌉ = : r ( n ) p>2\lceil n/2\rceil=:r(n) p > 2 ⌈ n /2 ⌉ =: r ( n ) . Thus, using the fact that ∥ ⋅ ∥ p ≤ ∥ ⋅ ∥ 2 ⌈ n / 2 ⌉ \lVert\cdot\rVert_p\le\lVert\cdot\rVert_{2\lceil n/2\rceil} ∥ ⋅ ∥ p ≤ ∥ ⋅ ∥ 2 ⌈ n /2 ⌉ and Jensen’s inequality yields
E [ ∥ μ ^ − μ ∥ p ] ≤ E [ ∥ μ ^ − μ ∥ 2 ⌈ n / 2 ⌉ ] ≤ E [ ∥ μ ^ − μ ∥ r ( n ) r ( n ) r ( n ) ] = ( ∑ j = 1 d E [ ∣ μ ^ j − μ j ∣ r ( n ) ] ) 1 r ( n ) . (7) \mathbb{E}\left[\lVert\hat{\mu}-\mu\rVert_p\right]\le\mathbb{E}\left[\lVert\hat{\mu}-\mu\rVert_{2\lceil n/2\rceil}\right]\le\mathbb{E}\left[\lVert\hat{\mu}-\mu\rVert_{r(n)}^{\frac{r(n)}{r(n)}}\right]=\left(\sum_{j=1}^{d}\mathbb{E}\left[|\hat{\mu}_j-\mu_j|^{r(n)}\right]\right)^{\frac{1}{r(n)}}. \tag*{(7)} E [ ∥ μ ^ − μ ∥ p ] ≤ E [ ∥ μ ^ − μ ∥ 2 ⌈ n /2 ⌉ ] ≤ E [ ∥ μ ^ − μ ∥ r ( n ) r ( n ) r ( n ) ] = ( j = 1 ∑ d E [ ∣ μ ^ j − μ j ∣ r ( n ) ] ) r ( n ) 1 . (7)
So, it suffices to bound the terms E [ ∣ μ ^ j − μ j ∣ r ( n ) ] \mathbb{E}\left[|\hat{\mu}_j-\mu_j|^{r(n)}\right] E [ ∣ μ ^ j − μ j ∣ r ( n ) ] . As in the previous case, we can invoke Theorem 3.4 with q = 2 q=2 q = 2 and t = n t=n t = n to get the bound
E [ ∣ μ ^ j − μ j ∣ r ( n ) ] = E [ ∣ μ ^ j − μ j ∣ 2 ⌈ n / 2 ⌉ ] ≤ ( n ⌈ n / 2 ⌉ ) Σ j j ⌈ n / 2 ⌉ . \mathbb{E}\left[|\hat{\mu}_j-\mu_j|^{r(n)}\right]=\mathbb{E}\left[|\hat{\mu}_j-\mu_j|^{2\lceil n/2\rceil}\right]\le\binom{n}{\lceil n/2\rceil}\Sigma_{jj}^{\lceil n/2\rceil}. E [ ∣ μ ^ j − μ j ∣ r ( n ) ] = E [ ∣ μ ^ j − μ j ∣ 2 ⌈ n /2 ⌉ ] ≤ ( ⌈ n /2 ⌉ n ) Σ j j ⌈ n /2 ⌉ .
Plugging this into the bound (7) and using a similar approximation for the binomial term as before yields the final bound
E [ ∥ μ ^ − μ ∥ p ] ≤ 2 ( ∑ j = 1 d ( Σ j j ) ⌊ n / 2 ⌋ ) 1 2 ⌊ n / 2 ⌋ . \mathbb{E}[\|\hat{\mu}-\mu\|_p]\leq2\left(\sum_{j=1}^{d}(\Sigma_{jj})^{\left\lfloor n/2\right\rfloor}\right)^{\frac{1}{2\left\lfloor n/2\right\rfloor}}. E [ ∥ μ ^ − μ ∥ p ] ≤ 2 ( j = 1 ∑ d ( Σ j j ) ⌊ n /2 ⌋ ) 2 ⌊ n /2 ⌋ 1 .
as desired. We now derive the uniform bound based on s = min { p ˉ , 2 ⌊ n 2 ⌋ } s=\min\{\bar{p},2\left\lfloor\frac{n}{2}\right\rfloor\} s = min { p ˉ , 2 ⌊ 2 n ⌋ } . Notice that in the case that n ≥ t ( p ˉ ) n\geq t(\bar{p}) n ≥ t ( p ˉ ) we have s = p ˉ s=\bar{p} s = p ˉ and we have the simple bound
E [ ∥ μ ^ − μ ∥ p ] ≤ 2 ( ∑ j = 1 d ( Σ j j ) p ˉ / 2 ) 1 / p ˉ ⌊ n / t ( p ˉ ) ⌋ = 2 ( ∑ j = 1 d ( Σ j j ) s / 2 ) 1 / s ⌊ n / t ( p ˉ ) ⌋ ≤ 4 ( ∑ j = 1 d ( Σ j j ) s / 2 ) 1 / s s n , \mathbb{E}[\|\hat{\mu}-\mu\|_p]\leq2\frac{\left(\sum_{j=1}^{d}(\Sigma_{jj})^{\bar{p}/2}\right)^{1/\bar{p}}}{\sqrt{\lfloor n/t(\bar{p})\rfloor}}=2\frac{\left(\sum_{j=1}^{d}(\Sigma_{jj})^{s/2}\right)^{1/s}}{\sqrt{\lfloor n/t(\bar{p})\rfloor}}\leq4\left(\sum_{j=1}^{d}(\Sigma_{jj})^{s/2}\right)^{1/s}\sqrt{\frac{s}{n}}, E [ ∥ μ ^ − μ ∥ p ] ≤ 2 ⌊ n / t ( p ˉ )⌋ ( ∑ j = 1 d ( Σ j j ) p ˉ /2 ) 1/ p ˉ = 2 ⌊ n / t ( p ˉ )⌋ ( ∑ j = 1 d ( Σ j j ) s /2 ) 1/ s ≤ 4 ( j = 1 ∑ d ( Σ j j ) s /2 ) 1/ s n s ,
where the final inequality follows from the facts that n ≥ t ( p ˉ ) n\geq t(\bar{p}) n ≥ t ( p ˉ ) implies ⌊ n t ( p ˉ ) ⌋ ≥ n 2 t ( p ˉ ) \left\lfloor\frac{n}{t(\bar{p})}\right\rfloor\geq\frac{n}{2t(\bar{p})} ⌊ t ( p ˉ ) n ⌋ ≥ 2 t ( p ˉ ) n and t ( p ˉ ) = 2 ⌈ p ˉ 2 ⌉ − 1 ≤ 2 p ˉ = 2 s t(\bar{p})=2\left\lceil\frac{\bar{p}}{2}\right\rceil-1\leq2\bar{p}=2s t ( p ˉ ) = 2 ⌈ 2 p ˉ ⌉ − 1 ≤ 2 p ˉ = 2 s and so 1 ⌊ n / t ( p ˉ ) ⌋ ≤ 2 t ( p ˉ ) n ≤ 2 s n \frac{1}{\sqrt{\lfloor n/t(\bar{p})\rfloor}}\leq\sqrt{\frac{2t(\bar{p})}{n}}\leq2\sqrt{\frac{s}{n}} ⌊ n / t ( p ˉ )⌋ 1 ≤ n 2 t ( p ˉ ) ≤ 2 n s . Now in the case that n < t ( p ˉ ) n<t(\bar{p}) n < t ( p ˉ ) we have s = 2 ⌊ n 2 ⌋ = r ( n ) s=2\left\lfloor\frac{n}{2}\right\rfloor=r(n) s = 2 ⌊ 2 n ⌋ = r ( n ) and hence
E [ ∥ μ ^ − μ ∥ p ] ≤ 2 ( ∑ j = 1 d ( Σ j j ) ⌊ n / 2 ⌋ ) 1 2 ⌊ n / 2 ⌋ = 2 ( ∑ j = 1 d ( Σ j j ) s / 2 ) 1 / s ≤ 2 ( ∑ j = 1 d ( Σ j j ) s / 2 ) 1 / s s n , \mathbb{E}[\|\hat{\mu}-\mu\|_p]\leq2\left(\sum_{j=1}^{d}(\Sigma_{jj})^{\left\lfloor n/2\right\rfloor}\right)^{\frac{1}{2\left\lfloor n/2\right\rfloor}}=2\left(\sum_{j=1}^{d}(\Sigma_{jj})^{s/2}\right)^{1/s}\leq2\left(\sum_{j=1}^{d}(\Sigma_{jj})^{s/2}\right)^{1/s}\sqrt{\frac{s}{n}}, E [ ∥ μ ^ − μ ∥ p ] ≤ 2 ( j = 1 ∑ d ( Σ j j ) ⌊ n /2 ⌋ ) 2 ⌊ n /2 ⌋ 1 = 2 ( j = 1 ∑ d ( Σ j j ) s /2 ) 1/ s ≤ 2 ( j = 1 ∑ d ( Σ j j ) s /2 ) 1/ s n s ,
where the final inequality uses the fact that s = 2 ⌊ n 2 ⌋ ≥ n s=2\left\lfloor\frac{n}{2}\right\rfloor\geq n s = 2 ⌊ 2 n ⌋ ≥ n . This completes the proof.
Lower bounds
In this section we prove that the rate achieved in Theorem 3.3 is optimal. The lower bound has two components, proved as two separate lemmas, corresponding to the two regimes discussed in the introduction. The first obstruction is already present in the Gaussian location model and gives the Gaussian-width branch. The second obstruction is genuinely non-Gaussian and is witnessed by heavy-tailed distributions. We begin with the Gaussian lower bound. It matches Theorem 3.3 up to constants in the regime p ˉ ≤ 2 ⌊ n 2 ⌋ \bar{p}\leq2\left\lfloor\frac{n}{2}\right\rfloor p ˉ ≤ 2 ⌊ 2 n ⌋ .
Lemma 3.5 (Gaussian-width lower bound). There exists a universal constant c > 0 c>0 c > 0 such that for any d , n ∈ N d,n\in\mathbb{N} d , n ∈ N , any p ∈ [ 1 , ∞ ] p\in[1,\infty] p ∈ [ 1 , ∞ ] , and any estimator A : ( R d ) n → R d A:(\mathbb{R}^{d})^{n}\to\mathbb{R}^{d} A : ( R d ) n → R d ,
sup μ ∈ R d E X 1 , … , X n ∼ N ( μ , I d ) [ ∥ A ( X 1 , … , X n ) − μ ∥ p ] ≥ c d 1 / p ˉ p ˉ n . \sup_{\mu\in\mathbb{R}^{d}}\mathbb{E}_{X_{1},\ldots,X_{n}\sim\mathcal{N}(\mu,I_{d})}\left[\|A(X_{1},\ldots,X_{n})-\mu\|_{p}\right]\geq c d^{1/\bar{p}}\sqrt{\frac{\bar{p}}{n}}. μ ∈ R d sup E X 1 , … , X n ∼ N ( μ , I d ) [ ∥ A ( X 1 , … , X n ) − μ ∥ p ] ≥ c d 1/ p ˉ n p ˉ . Consequently, the same lower bound holds for the minimax risk R ( n , d , p ) \mathfrak{R}(n,d,p) R ( n , d , p ) .
Proof. Let P μ = N ( μ , I d ) P_{\mu}=\mathcal{N}(\mu,I_{d}) P μ = N ( μ , I d ) and let G ∼ N ( 0 , I d ) G\sim\mathcal{N}(0,I_{d}) G ∼ N ( 0 , I d ) . Since the Gaussian family { P μ : μ ∈ R d } \{P_{\mu}:\mu\in\mathbb{R}^{d}\} { P μ : μ ∈ R d } is contained in the class of distributions with covariance I d I_{d} I d , it suffices to prove the lower bound over this subfamily. By [PW25, Theorem 28.7], which is a consequence of Anderson’s lemma [3 ] , applied with ρ ( x ) = ∥ x ∥ p \rho(x)=\|x\|_{p} ρ ( x ) = ∥ x ∥ p , the minimax risk in the Gaussian location model is
inf μ ^ sup μ ∈ R d E X 1 , … , X n ∼ P μ [ ∥ μ ^ ( X 1 , … , X n ) − μ ∥ p ] = E ∥ G n ∥ p = E ∥ G ∥ p n . (8) \inf_{\hat{\mu}}\sup_{\mu\in\mathbb{R}^{d}}\mathbb{E}_{X_{1},\ldots,X_{n}\sim P_{\mu}}\left[\|\hat{\mu}(X_{1},\ldots,X_{n})-\mu\|_{p}\right]=\mathbb{E}\left\|\frac{G}{\sqrt{n}}\right\|_{p}=\frac{\mathbb{E}\|G\|_{p}}{\sqrt{n}}. \tag*{(8)} μ ^ inf μ ∈ R d sup E X 1 , … , X n ∼ P μ [ ∥ μ ^ ( X 1 , … , X n ) − μ ∥ p ] = E n G p = n E ∥ G ∥ p . (8)
Indeed, the function ρ ( x ) = ∥ x ∥ p \rho(x)=\lVert x\rVert_p ρ ( x ) = ∥ x ∥ p is lower-semicontinuous and bowl-shaped (its sublevel sets are symmetric and convex). Therefore every estimator A \mathcal{A} A satisfies
sup μ ∈ R d E X 1 , … , X n ∼ P μ [ ∥ A ( X 1 , … , X n ) − μ ∥ p ] ≥ E ∥ G ∥ p n . (9) \sup_{\mu\in\mathbb{R}^{d}}\mathop{\mathbb{E}}_{X_1,\ldots,X_n\sim P_\mu}\left[\lVert\mathcal{A}(X_1,\ldots,X_n)-\mu\rVert_p\right]\ge\frac{\mathbb{E}\lVert G\rVert_p}{\sqrt{n}}. \tag*{(9)} μ ∈ R d sup E X 1 , … , X n ∼ P μ [ ∥ A ( X 1 , … , X n ) − μ ∥ p ] ≥ n E ∥ G ∥ p . (9)
It remains to lower bound the Gaussian width term. The standard Gaussian norm estimate gives
E ∥ G ∥ p ≍ d 1 p ˉ p ˉ , p ˉ = min { p , max { log d , 1 } } . \mathbb{E}\lVert G\rVert_p\asymp d^{\frac{1}{\bar p}}\sqrt{\bar p},\qquad\bar p=\min\{p,\max\{\log d,1\}\}. E ∥ G ∥ p ≍ d p ˉ 1 p ˉ , p ˉ = min { p , max { log d , 1 }} .
Plugging this estimate into (9) yields the claim.
We now prove the second lower bound. Unlike Lemma 3.5 , this obstruction is not present in the Gaussian location model. It is a genuinely heavy-tailed obstruction and gives the small-sample branch of the minimax rate. Since ∥ x ∥ p ≥ ∥ x ∥ ∞ \lVert x\rVert_p\ge\lVert x\rVert_\infty ∥ x ∥ p ≥ ∥ x ∥ ∞ for all x ∈ R d x\in\mathbb{R}^d x ∈ R d and all p ≥ 1 p\ge1 p ≥ 1 , it suffices to prove a lower bound in the ℓ ∞ \ell_\infty ℓ ∞ norm.
Lemma 3.6 (Heavy-tailed small-sample lower bound). There exists a universal constant c > 0 c>0 c > 0 satisfying the following. For any d , n ∈ N d,n\in\mathbb{N} d , n ∈ N with log d ≥ 2 ⌈ n 2 ⌉ \log d\ge2\left\lceil\frac{n}{2}\right\rceil log d ≥ 2 ⌈ 2 n ⌉ and any estimator A : ( R d ) n → R d \mathcal{A}:(\mathbb{R}^{d})^n\to\mathbb{R}^d A : ( R d ) n → R d , there exists a distribution P P P with mean μ ∈ R d \mu\in\mathbb{R}^d μ ∈ R d and covariance I d I_d I d such that
E X 1 , … , X n ∼ P [ ∥ A ( X 1 , … , X n ) − μ ∥ ∞ ] ≥ c d 1 ⌈ n / 2 ⌉ . \mathop{\mathbb{E}}_{X_1,\ldots,X_n\sim P}\left[\lVert\mathcal{A}(X_1,\ldots,X_n)-\mu\rVert_\infty\right]\ge c d^{\frac{1}{\left\lceil n/2\right\rceil}}. E X 1 , … , X n ∼ P [ ∥ A ( X 1 , … , X n ) − μ ∥ ∞ ] ≥ c d ⌈ n /2 ⌉ 1 . Consequently, in the regime log d ≥ 2 ⌈ n 2 ⌉ \log d\ge2\left\lceil\frac{n}{2}\right\rceil log d ≥ 2 ⌈ 2 n ⌉ , the same lower bound holds for the minimax risk R ( n , d , p ) \mathfrak{R}(n,d,p) R ( n , d , p ) for every p ∈ [ 1 , ∞ ] p\in[1,\infty] p ∈ [ 1 , ∞ ] .
Proof. We use the high-probability ℓ ∞ \ell_\infty ℓ ∞ lower bound proven in Theorem 4.4 . Apply Theorem 4.4 with σ = 1 \sigma=1 σ = 1 and δ 0 = 1 / 4 \delta_0=1/4 δ 0 = 1/4 . Then for any estimator A \mathcal{A} A , there exists a distribution P P P on R d \mathbb{R}^d R d with mean μ \mu μ and covariance I d I_d I d such that
P r X 1 , … , X n ∼ P [ ∥ A ( X 1 , … , X n ) − μ ∥ ∞ ≥ 1 4 ( 1 − 2 d − 1 ⌈ n / 2 ⌉ ) ( 4 d ) 1 ⌈ n / 2 ⌉ ] > 1 4 . \mathop{\mathbf{Pr}}_{X_1,\ldots,X_n\sim P}\left[\lVert\mathcal{A}(X_1,\ldots,X_n)-\mu\rVert_\infty\ge\frac{1}{4}\left(1-2d^{-\frac{1}{\left\lceil n/2\right\rceil}}\right)(4d)^{\frac{1}{\left\lceil n/2\right\rceil}}\right]>\frac{1}{4}. Pr X 1 , … , X n ∼ P [ ∥ A ( X 1 , … , X n ) − μ ∥ ∞ ≥ 4 1 ( 1 − 2 d − ⌈ n /2 ⌉ 1 ) ( 4 d ) ⌈ n /2 ⌉ 1 ] > 4 1 .
Here we used that, for δ 0 = 1 / 4 \delta_0=1/4 δ 0 = 1/4 , the auxiliary parameter appearing in Theorem 4.4 is ( 4 δ 0 d ) 1 ⌈ n / 2 ⌉ = d − 1 ⌈ n / 2 ⌉ \left(\frac{4\delta_0}{d}\right)^{\frac{1}{\left\lceil n/2\right\rceil}}=d^{-\frac{1}{\left\lceil n/2\right\rceil}} ( d 4 δ 0 ) ⌈ n /2 ⌉ 1 = d − ⌈ n /2 ⌉ 1 . By the assumption log d ≥ 2 ⌈ n 2 ⌉ \log d\ge2\left\lceil\frac{n}{2}\right\rceil log d ≥ 2 ⌈ 2 n ⌉ , we have d − 1 ⌈ n / 2 ⌉ ≤ e − 2 d^{-\frac{1}{\left\lceil n/2\right\rceil}}\le e^{-2} d − ⌈ n /2 ⌉ 1 ≤ e − 2 . Therefore,
1 4 ( 1 − 2 d − 1 ⌈ n / 2 ⌉ ) ( 4 d ) 1 ⌈ n / 2 ⌉ ≥ 1 − 2 e − 2 4 d 1 ⌈ n / 2 ⌉ . \frac{1}{4}\left(1-2d^{-\frac{1}{\left\lceil n/2\right\rceil}}\right)(4d)^{\frac{1}{\left\lceil n/2\right\rceil}}\ge\frac{1-2e^{-2}}{4}d^{\frac{1}{\left\lceil n/2\right\rceil}}. 4 1 ( 1 − 2 d − ⌈ n /2 ⌉ 1 ) ( 4 d ) ⌈ n /2 ⌉ 1 ≥ 4 1 − 2 e − 2 d ⌈ n /2 ⌉ 1 .
Using the elementary inequality E Z ≥ a Pr [ Z ≥ a ] \mathbb{E}Z\ge a\Pr[Z\ge a] E Z ≥ a Pr [ Z ≥ a ] for nonnegative random variables Z Z Z , we conclude that
E X 1 , … , X n ∼ P [ ∥ A ( X 1 , … , X n ) − μ ∥ ∞ ] ≥ 1 − 2 e − 2 16 d 1 ⌈ n / 2 ⌉ . \mathop{\mathbb{E}}_{X_1,\ldots,X_n\sim P}\left[\lVert\mathcal{A}(X_1,\ldots,X_n)-\mu\rVert_\infty\right]\ge\frac{1-2e^{-2}}{16}d^{\frac{1}{\left\lceil n/2\right\rceil}}. E X 1 , … , X n ∼ P [ ∥ A ( X 1 , … , X n ) − μ ∥ ∞ ] ≥ 16 1 − 2 e − 2 d ⌈ n /2 ⌉ 1 .
This proves the lemma with c = 1 − 2 e − 2 16 c=\frac{1-2e^{-2}}{16} c = 16 1 − 2 e − 2 .
Proof of thm:expectedminimaxrisk
We begin by showing that guarantee of Algorithm 1 provided in Theorem 3.3 achieves the claimed minimax risk in the isotropic case. First, notice that in the isotropic case Σ = I d \Sigma=I_d Σ = I d , so the guarantee reduces to
R ( n , d , p ) ≤ { 2 d 1 p ˉ , p ˉ > 2 ⌊ n 2 ⌋ , 2 d 1 p ˉ ⌊ n / t ( p ˉ ) ⌋ , p ˉ ≤ 2 ⌊ n 2 ⌋ . \mathfrak{R}(n,d,p) \le\begin{cases} 2d^{\frac{1}{\bar{p}}}, & \bar{p}>2\left\lfloor\frac{n}{2}\right\rfloor, \\ 2\frac{d^{\frac{1}{\bar{p}}}}{\sqrt{\left\lfloor n/t(\bar{p})\right\rfloor}}, & \bar{p}\le2\left\lfloor\frac{n}{2}\right\rfloor. \end{cases} R ( n , d , p ) ≤ ⎩ ⎨ ⎧ 2 d p ˉ 1 , 2 ⌊ n / t ( p ˉ ) ⌋ d p ˉ 1 , p ˉ > 2 ⌊ 2 n ⌋ , p ˉ ≤ 2 ⌊ 2 n ⌋ .
Notice that guarantee of Theorem 3.3 based on s = min { p ˉ , 2 ⌊ n 2 ⌋ } s=\min\{\bar{p},2\left\lfloor\frac{n}{2}\right\rfloor\} s = min { p ˉ , 2 ⌊ 2 n ⌋ } implies the upper bound
R ( n , p , d ) ≤ 4 d 1 s s n . \mathfrak{R}(n,p,d) \le4d^{\frac{1}{s}}\sqrt{\frac{s}{n}}. R ( n , p , d ) ≤ 4 d s 1 n s .
We now combine the lower bounds from Lemmas 3.5 and 3.6 . Consider the regime where p ˉ > 2 ⌊ n 2 ⌋ \bar{p}>2\left\lfloor\frac{n}{2}\right\rfloor p ˉ > 2 ⌊ 2 n ⌋ . In this case, we certainly have that log d ≥ 2 ⌊ n 2 ⌋ \log d\ge2\left\lfloor\frac{n}{2}\right\rfloor log d ≥ 2 ⌊ 2 n ⌋ , so Lemma 3.6 implies that
R ( n , p , d ) ≳ d 1 2 ⌊ n / 2 ⌋ . \mathfrak{R}(n,p,d)\gtrsim d^{\frac{1}{2\left\lfloor n/2\right\rfloor}}. R ( n , p , d ) ≳ d 2 ⌊ n /2 ⌋ 1 .
We also have the lower bound on the risk implied by Lemma 3.5 that tells us that
R ( n , p , d ) ≳ d 1 p ˉ p ˉ n . \mathfrak{R}(n,p,d)\gtrsim d^{\frac{1}{\bar{p}}}\sqrt{\frac{\bar{p}}{n}}. R ( n , p , d ) ≳ d p ˉ 1 n p ˉ .
Thus, all together we conclude the lower bound
R ( n , p , d ) ≳ { d 1 2 ⌊ n / 2 ⌋ , p ˉ > 2 ⌊ n 2 ⌋ , d 1 p ˉ p ˉ n , p ˉ ≤ 2 ⌊ n 2 ⌋ , \mathfrak{R}(n,p,d)\gtrsim\begin{cases} d^{\frac{1}{2\left\lfloor n/2\right\rfloor}}, & \bar{p}>2\left\lfloor\frac{n}{2}\right\rfloor, \\ d^{\frac{1}{\bar{p}}}\sqrt{\frac{\bar{p}}{n}}, & \bar{p}\le2\left\lfloor\frac{n}{2}\right\rfloor, \end{cases} R ( n , p , d ) ≳ ⎩ ⎨ ⎧ d 2 ⌊ n /2 ⌋ 1 , d p ˉ 1 n p ˉ , p ˉ > 2 ⌊ 2 n ⌋ , p ˉ ≤ 2 ⌊ 2 n ⌋ ,
which is equivalent to the following lower bound based on s s s :
R ( n , p , d ) ≳ d 1 s s n . \mathfrak{R}(n,p,d)\gtrsim d^{\frac{1}{s}}\sqrt{\frac{s}{n}}. R ( n , p , d ) ≳ d s 1 n s .
This concludes the proof.
Optimal High-probability Guarantees for ℓ ∞ \ell_\infty ℓ ∞
In this section, we formalize and prove Theorem 1.3 which characterizes the optimal high-probability estimation guarantees under the ℓ ∞ \ell_\infty ℓ ∞ norm. First, define the following minimax risk:
r ( n , d , δ ) = inf A : ( R d ) n → R d { r > 0 : sup μ ∈ R d P : E P [ X ] = μ Cov P ( X ) = I d Pr X 1 , … , X n ∼ P [ ∥ A ( X 1 , … , X n ) − μ ∥ ∞ ≥ r ] ≤ δ } . (10) r(n,d,\delta)=\inf_{\mathcal{A}:(\mathbb{R}^{d})^{n}\to\mathbb{R}^{d}}\left\{r>0:\sup_{\substack{\mu\in\mathbb{R}^{d}\\ P:\mathbb{E}_{P}[X]=\mu\\ \operatorname{Cov}_{P}(X)=I_{d}}}\Pr_{X_{1},\ldots,X_{n}\sim P}\left[\lVert\mathcal{A}(X_{1},\ldots,X_{n})-\mu\rVert_{\infty}\ge r\right]\le\delta\right\}. \tag*{(10)} r ( n , d , δ ) = A : ( R d ) n → R d inf ⎩ ⎨ ⎧ r > 0 : μ ∈ R d P : E P [ X ] = μ Cov P ( X ) = I d sup X 1 , … , X n ∼ P Pr [ ∥ A ( X 1 , … , X n ) − μ ∥ ∞ ≥ r ] ≤ δ ⎭ ⎬ ⎫ . (10)
The formalization of Theorem 1.3 is given below.
Theorem 4.1. There is a universal constant c > 0 c > 0 c > 0 such that for any n , d ∈ N n,d \in\mathbb{N} n , d ∈ N , and δ ∈ ( 0 , c ) \delta\in(0,c) δ ∈ ( 0 , c ) , we have that:
r ( n , d , δ ) ≍ { ( d δ ) 1 2 ⌊ n 2 ⌋ , n ≲ log ( d / δ ) , log ( d / δ ) n , n ≳ log ( d / δ ) . r(n,d,\delta) \asymp
\begin{cases}
\left(\frac{d}{\delta}\right)^{\frac{1}{2\lfloor\frac{n}{2} \rfloor}}, & n \lesssim\log(d/\delta),\\
\sqrt{\frac{\log(d/\delta)}{n}}, & n \gtrsim\log(d/\delta).
\end{cases} r ( n , d , δ ) ≍ ⎩ ⎨ ⎧ ( δ d ) 2 ⌊ 2 n ⌋ 1 , n l o g ( d / δ ) , n ≲ log ( d / δ ) , n ≳ log ( d / δ ) . Moreover, this rate is achieved by the coordinate-wise median-of-means estimator.
Note that the rates in the two cases coincide when n = Θ ( log ( d / δ ) ) n = \Theta(\log(d/\delta)) n = Θ ( log ( d / δ )) . The proof is presented in two parts with the upper bound established in Subsection 4.1 and the lower bound in Subsection 4.2.
High-probability Upper Bound in ℓ ∞ \ell_\infty ℓ ∞
In this section we prove high probability bounds for the performance of the coordinate wise median of means estimator for estimating the mean of a random vector in R d \mathbb{R}^d R d under the ℓ ∞ \ell_\infty ℓ ∞ norm. Towards this end, we begin with the one dimensional case.
Theorem 4.2. Let X 1 , … , X n ∈ R X_1,\ldots,X_n \in\mathbb{R} X 1 , … , X n ∈ R be i.i.d. random variables with finite mean μ \mu μ and variance σ 2 \sigma^2 σ 2 . Fix a confidence parameter δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) . Given the number of buckets t = 2 ⌈ log ( 1 / δ ) ⌉ t = 2\lceil\log(1/\delta)\rceil t = 2 ⌈ log ( 1/ δ )⌉ and the sample X 1 , … , X n X_1,\ldots,X_n X 1 , … , X n as input, Algorithm 1 returns an estimate μ ^ \hat{\mu} μ ^ satisfying
∣ μ ^ − μ ∣ ≤ { 2 σ ( 1 δ ) 1 2 ⌊ n / 2 ⌋ , n < 2 ⌈ log ( 1 / δ ) ⌉ , 4 σ e n log ( 1 δ ) , n ≥ 2 ⌈ log ( 1 / δ ) ⌉ , (11) \lvert\hat{\mu}-\mu\rvert\le
\begin{cases}
2\sigma\left(\frac{1}{\delta}\right)^{\frac{1}{2\lfloor n/2\rfloor}}, & n < 2\lceil\log(1/\delta)\rceil,\\
4\sigma\sqrt{\frac{e}{n}\log\left(\frac{1}{\delta}\right)}, & n \ge2\lceil\log(1/\delta)\rceil,
\end{cases} \tag*{(11)} ∣ μ ^ − μ ∣ ≤ ⎩ ⎨ ⎧ 2 σ ( δ 1 ) 2 ⌊ n /2 ⌋ 1 , 4 σ n e log ( δ 1 ) , n < 2 ⌈ log ( 1/ δ )⌉ , n ≥ 2 ⌈ log ( 1/ δ )⌉ , (11) with probability at least 1 − δ 1-\delta 1 − δ over the randomness of X 1 , … , X n X_1,\ldots,X_n X 1 , … , X n .
Proof. We split the analysis into two very different cases. First, let us consider the case that the sample size n n n is smaller than the number of buckets t t t . In this case, Algorithm 1 returns the median of the n n n sample points. Using Markov’s inequality together with the moment bound of Theorem 3.4 with q = 2 q=2 q = 2 and t = n t=n t = n implies that our output μ ^ \hat{\mu} μ ^ satisfies
Pr [ ∣ μ ^ − μ ∣ > 2 σ ( 1 δ ) 1 2 ⌊ n / 2 ⌋ ] ≤ δ E [ ∣ μ ^ − μ ∣ 2 ⌊ n / 2 ⌋ ] ( 2 σ ) 2 ⌊ n / 2 ⌋ ≤ δ ( n ⌈ n / 2 ⌉ ) 2 2 ⌊ n / 2 ⌋ ≤ δ 2 n 2 2 ⌊ n / 2 ⌋ ≤ δ , \Pr\left[\lvert\hat{\mu}-\mu\rvert> 2\sigma\left(\frac{1}{\delta}\right)^{\frac{1}{2\lfloor n/2\rfloor}}\right]
\le\frac{\delta\,\mathbb{E}\left[\lvert\hat{\mu}-\mu\rvert^{2\lfloor n/2\rfloor}\right]}{(2\sigma)^{2\lfloor n/2\rfloor}}
\le\frac{\delta\binom{n}{\lceil n/2\rceil}}{2^{2\lfloor n/2\rfloor}}
\le\frac{\delta2^n}{2^{2\lfloor n/2\rfloor}}
\le\delta, Pr [ ∣ μ ^ − μ ∣ > 2 σ ( δ 1 ) 2 ⌊ n /2 ⌋ 1 ] ≤ ( 2 σ ) 2 ⌊ n /2 ⌋ δ E [ ∣ μ ^ − μ ∣ 2 ⌊ n /2 ⌋ ] ≤ 2 2 ⌊ n /2 ⌋ δ ( ⌈ n /2 ⌉ n ) ≤ 2 2 ⌊ n /2 ⌋ δ 2 n ≤ δ ,
where the second-to-last inequality uses a simple upper bound on centered binomial coefficients.
Now consider the (well studied) case that n n n is at least t t t . In this case, Algorithm 1 returns the median of the t t t bucket means. Each bucket contains at least ⌊ n / t ⌋ \lfloor n/t\rfloor ⌊ n / t ⌋ samples, so the variance of each bucket mean is at most σ 2 ⌊ n / t ⌋ \frac{\sigma^2}{\lfloor n/t\rfloor} ⌊ n / t ⌋ σ 2 . Thus, Markov’s inequality applied together with moment bound of Theorem 3.4 tells us that our output μ ^ = Median ( μ ^ ( 1 ) , … , μ ^ ( t ) ) \hat{\mu} = \operatorname{Median}(\hat{\mu}^{(1)},\ldots,\hat{\mu}^{(t)}) μ ^ = Median ( μ ^ ( 1 ) , … , μ ^ ( t ) ) satisfies
Pr [ ∣ μ ^ − μ ∣ > 2 σ e ( 1 ⌊ n / t ⌋ ) ] ≤ ( ⌊ n / t ⌋ 4 e σ 2 ) ⌊ t / 2 ⌋ ( t ⌈ t / 2 ⌉ ) max i ∈ [ t ] E [ ( μ ^ ( i ) − μ ) 2 ] ⌊ t / 2 ⌋ ≤ e − ⌈ t / 2 ⌉ ≤ δ . \Pr\left[\lvert\hat{\mu}-\mu\rvert> 2\sigma\sqrt{e\left(\frac{1}{\lfloor n/t\rfloor}\right)}\right]
\le\left(\frac{\lfloor n/t\rfloor}{4e\sigma^2}\right)^{\lfloor t/2\rfloor}
\binom{t}{\lceil t/2\rceil}
\max_{i\in[t]}\mathbb{E}\left[(\hat{\mu}^{(i)}-\mu)^2\right]^{\lfloor t/2\rfloor}
\le e^{-\lceil t/2\rceil}
\le\delta. Pr [ ∣ μ ^ − μ ∣ > 2 σ e ( ⌊ n / t ⌋ 1 ) ] ≤ ( 4 e σ 2 ⌊ n / t ⌋ ) ⌊ t /2 ⌋ ( ⌈ t /2 ⌉ t ) i ∈ [ t ] max E [ ( μ ^ ( i ) − μ ) 2 ] ⌊ t /2 ⌋ ≤ e − ⌈ t /2 ⌉ ≤ δ .
The above implies the second bound in (11) since ⌊ n / t ⌋ ≥ n 4 log ( 1 / δ ) \lfloor n/t\rfloor\ge\frac{n}{4\log(1/\delta)} ⌊ n / t ⌋ ≥ 4 l o g ( 1/ δ ) n . This completes the proof. □
Applying the above median-of-means estimator to each coordinate with failure parameter δ / d \delta/d δ / d together with a union bound gives us the following corollary for estimation under the ℓ ∞ \ell_\infty ℓ ∞ norm.
Corollary 4.3. Let X 1 , … , X n ∈ R d X_1,\ldots,X_n \in\mathbb{R}^d X 1 , … , X n ∈ R d be i.i.d. random vectors with finite mean μ \mu μ and covariance σ 2 I d \sigma^2 I_d σ 2 I d . Fix a confidence parameter δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) . Given the number of buckets t = 2 ⌈ log ( d / δ ) ⌉ t=2\lceil\log(d/\delta)\rceil t = 2 ⌈ log ( d / δ )⌉ and the sample X 1 , … , X n X_1,\ldots,X_n X 1 , … , X n as input, Algorithm 1 returns an estimate μ ^ \widehat{\mu} μ satisfying
∥ μ ^ − μ ∥ ∞ ≤ { 2 σ ( d δ ) 1 2 ⌈ n / 2 ⌉ , n < 2 ⌈ log ( d / δ ) ⌉ , 4 σ e n log ( d δ ) , n ≥ 2 ⌈ log ( d / δ ) ⌉ , (12) \|\widehat{\mu}-\mu\|_\infty\le
\begin{cases}
2\sigma\left(\frac{d}{\delta}\right)^{\frac{1}{2\lceil n/2\rceil}}, & n<2\lceil\log(d/\delta)\rceil,\\
4\sigma\sqrt{\frac{e}{n}\log\left(\frac{d}{\delta}\right)}, & n\ge2\lceil\log(d/\delta)\rceil,
\end{cases} \tag*{(12)} ∥ μ − μ ∥ ∞ ≤ ⎩ ⎨ ⎧ 2 σ ( δ d ) 2 ⌈ n /2 ⌉ 1 , 4 σ n e log ( δ d ) , n < 2 ⌈ log ( d / δ )⌉ , n ≥ 2 ⌈ log ( d / δ )⌉ , (12)
with probability at least 1 − δ 1-\delta 1 − δ over the randomness of X 1 , … , X n X_1,\ldots,X_n X 1 , … , X n .
High-probability Lower Bound in ℓ ∞ \ell_\infty ℓ ∞
In this sub-section we show a high-probability lower bound for any estimator in ℓ ∞ \ell_\infty ℓ ∞ . We prove our lower bound in two regimes: the small sample regime (n ≤ log ( d / δ ) n\le\log(d/\delta) n ≤ log ( d / δ ) ) in Theorem 4.4 and the large sample regime (n ≥ log ( d / δ ) n\ge\log(d/\delta) n ≥ log ( d / δ ) ) in Lemma 4.5 .
Theorem 4.4. For any δ ∈ ( 0 , 1 / 2 ) \delta\in(0,1/2) δ ∈ ( 0 , 1/2 ) , any σ > 0 \sigma>0 σ > 0 , any n , d ∈ N n,d\in\mathbb{N} n , d ∈ N and any deterministic estimator A : ( R d ) n → R d \mathcal{A}:(\mathbb{R}^d)^n\to\mathbb{R}^d A : ( R d ) n → R d , there exists a distribution P P P on R d \mathbb{R}^d R d with mean μ \mu μ and covariance matrix σ 2 I d \sigma^2 I_d σ 2 I d such that
Pr X 1 , … , X n ∼ P [ ∥ A ( X 1 , … , X n ) − μ ∥ ∞ ≥ σ ( 1 − 2 p ) 4 ( d δ ) 1 2 ⌈ n / 2 ⌉ ] > δ , \Pr_{X_1,\ldots,X_n\sim P}\left[\|\mathcal{A}(X_1,\ldots,X_n)-\mu\|_\infty\ge\frac{\sigma(1-2p)}{4}\left(\frac{d}{\delta}\right)^{\frac{1}{2\lceil n/2\rceil}}\right]>\delta, X 1 , … , X n ∼ P Pr [ ∥ A ( X 1 , … , X n ) − μ ∥ ∞ ≥ 4 σ ( 1 − 2 p ) ( δ d ) 2 ⌈ n /2 ⌉ 1 ] > δ , where p = ( 4 δ d ) 1 2 ⌈ n / 2 ⌉ p=\left(\frac{4\delta}{d}\right)^{\frac{1}{2\lceil n/2\rceil}} p = ( d 4 δ ) 2 ⌈ n /2 ⌉ 1 .
Proof. If p ≥ 1 / 2 p\ge1/2 p ≥ 1/2 , then 1 − 2 p ≤ 0 1-2p\le0 1 − 2 p ≤ 0 , so the lower bound in the theorem is non-positive. In this case the claim is trivial since the norm is always non-negative and the claim follows for any distribution P P P with covariance σ 2 I d \sigma^2 I_d σ 2 I d . Thus, we assume that p < 1 / 2 p<1/2 p < 1/2 throughout. Define
ℓ = σ p ( 1 − p ) . \ell=\frac{\sigma}{\sqrt{p(1-p)}}. ℓ = p ( 1 − p ) σ .
We consider two distributions P 0 P_0 P 0 and P 1 P_1 P 1 on { 0 , ℓ } \{0,\ell\} { 0 , ℓ } given by
Pr Y ∼ P 0 [ Y = ℓ ] = p , Pr Y ∼ P 1 [ Y = ℓ ] = 1 − p . \Pr_{Y\sim P_0}[Y=\ell]=p,\qquad\Pr_{Y\sim P_1}[Y=\ell]=1-p. Y ∼ P 0 Pr [ Y = ℓ ] = p , Y ∼ P 1 Pr [ Y = ℓ ] = 1 − p .
Equivalently, under P 0 P_0 P 0 the point ℓ \ell ℓ occurs with probability p p p , while under P 1 P_1 P 1 it occurs with probability 1 − p 1-p 1 − p . Write μ 0 = E Y ∼ P 0 [ Y ] = p ℓ \mu_0=\mathbb{E}_{Y\sim P_0}[Y]=p\ell μ 0 = E Y ∼ P 0 [ Y ] = p ℓ and μ 1 = E Y ∼ P 1 [ Y ] = ( 1 − p ) ℓ \mu_1=\mathbb{E}_{Y\sim P_1}[Y]=(1-p)\ell μ 1 = E Y ∼ P 1 [ Y ] = ( 1 − p ) ℓ for the mean of P 0 P_0 P 0 and P 1 P_1 P 1 respectively. It is immediate that both distributions have variance p ( 1 − p ) ℓ 2 = σ 2 p(1-p)\ell^2=\sigma^2 p ( 1 − p ) ℓ 2 = σ 2 . Moreover, we define the separation of the means to be
Δ = μ 1 − μ 0 = ( 1 − 2 p ) ℓ , \Delta=\mu_1-\mu_0=(1-2p)\ell, Δ = μ 1 − μ 0 = ( 1 − 2 p ) ℓ ,
and since p < 1 / 2 p<1/2 p < 1/2 , we have Δ > 0 \Delta>0 Δ > 0 . We now construct the hard distribution. For each b = ( b 1 , … , b d ) ∈ { 0 , 1 } d b=(b_1,\ldots,b_d)\in\{0,1\}^d b = ( b 1 , … , b d ) ∈ { 0 , 1 } d , let P b P_b P b be the product distribution on R d \mathbb{R}^d R d whose j j j th coordinate has distribution P b j P_{b_j} P b j , independently over j = 1 , … , d j=1,\ldots,d j = 1 , … , d . Notice that P b P_b P b has mean μ b \mu_b μ b and covariance matrix σ 2 I d \sigma^2 I_d σ 2 I d where μ b = ( μ b 1 , … , μ b d ) \mu_b=(\mu_{b_1},\ldots,\mu_{b_d}) μ b = ( μ b 1 , … , μ b d ) . We will show that for any deterministic estimator A \mathcal{A} A , there exists some choice of b ∈ { 0 , 1 } d b\in\{0,1\}^d b ∈ { 0 , 1 } d witnessing the lower bound. Given samples X 1 , … , X n ∈ R d X_1,\ldots,X_n\in\mathbb{R}^d X 1 , … , X n ∈ R d , define a decoder b ^ = b ^ ( X 1 , … , X n ) ∈ { 0 , 1 } d \widehat{b}=\widehat{b}(X_1,\ldots,X_n)\in\{0,1\}^d b = b ( X 1 , … , X n ) ∈ { 0 , 1 } d coordinate-wise by
b ^ j ∈ arg min u ∈ { 0 , 1 } ∣ A ( X 1 , … , X n ) j − μ u ∣ , \widehat{b}_j\in\arg\min_{u\in\{0,1\}}\left|\mathcal{A}(X_1,\ldots,X_n)_j-\mu_u\right|, b j ∈ arg u ∈ { 0 , 1 } min ∣ A ( X 1 , … , X n ) j − μ u ∣ ,
with ties broken arbitrarily. Now, if ∥ A ( X 1 , … , X n ) − μ b ∥ ∞ < Δ 2 \lVert\mathcal{A}(X_1,\ldots,X_n)-\mu_b\rVert_\infty< \frac{\Delta}{2} ∥ A ( X 1 , … , X n ) − μ b ∥ ∞ < 2 Δ , then every coordinate of A ( X 1 , … , X n ) \mathcal{A}(X_1,\ldots,X_n) A ( X 1 , … , X n ) is strictly closer to the correct mean than to the incorrect mean, hence
∥ A ( X 1 , … , X n ) − μ b ∥ ∞ < Δ 2 ⟹ b ^ = b . (13) \lVert\mathcal{A}(X_1,\ldots,X_n)-\mu_b\rVert_\infty< \frac{\Delta}{2} \quad\Longrightarrow\quad\widehat{b}=b. \tag*{(13)} ∥ A ( X 1 , … , X n ) − μ b ∥ ∞ < 2 Δ ⟹ b = b . (13)
Let U U U be the uniform distribution over { 0 , 1 } d \{0,1\}^d { 0 , 1 } d and let B = ( B 1 , … , B d ) ∼ U B=(B_1,\ldots,B_d)\sim U B = ( B 1 , … , B d ) ∼ U . Conditioned on B = b B=b B = b , let X 1 , … , X n X_1,\ldots,X_n X 1 , … , X n be i.i.d. samples from P b P_b P b . For each coordinate j j j , define the coordinate samples
Z j = ( X 1 , j , X 2 , j , … , X n , j ) ∈ Z , Z_j=(X_{1,j},X_{2,j},\ldots,X_{n,j})\in\mathcal{Z}, Z j = ( X 1 , j , X 2 , j , … , X n , j ) ∈ Z ,
where Z : = { 0 , ℓ } n \mathcal{Z}:=\{0,\ell\}^n Z := { 0 , ℓ } n . Conditioned on B = b B=b B = b , the random vectors Z 1 , … , Z d Z_1,\ldots,Z_d Z 1 , … , Z d are independent and Z j Z_j Z j follows P b j n P_{b_j}^n P b j n . Finally define η = 1 2 ∑ z ∈ { 0 , ℓ } n min { P 0 n ( z ) , P 1 n ( z ) } \eta=\frac{1}{2}\sum_{z\in\{0,\ell\}^n}\min\{P_0^n(z),P_1^n(z)\} η = 2 1 ∑ z ∈ { 0 , ℓ } n min { P 0 n ( z ) , P 1 n ( z )} , which, by restricting the sum to those z z z satisfying ∣ { i : z i = ℓ } ∣ = ⌊ n / 2 ⌋ |\{i:z_i=\ell\}|=\left\lfloor n/2\right\rfloor ∣ { i : z i = ℓ } ∣ = ⌊ n /2 ⌋ , can be lower bounded as follows:
η ≥ 1 2 ( n ⌊ n / 2 ⌋ ) min { p ⌈ n / 2 ⌉ ( 1 − p ) ⌊ n / 2 ⌋ , ( 1 − p ) ⌈ n / 2 ⌉ p ⌊ n / 2 ⌋ } ≥ 1 2 ( n ⌊ n / 2 ⌋ ) p ⌈ n / 2 ⌉ 2 − ⌊ n / 2 ⌋ ≥ 1 2 p ⌈ n / 2 ⌉ = 2 δ d , (14) \eta\geq\frac{1}{2}\binom{n}{\lfloor n/2\rfloor}\min\left\{p^{\lceil n/2\rceil}(1-p)^{\lfloor n/2\rfloor},(1-p)^{\lceil n/2\rceil}p^{\lfloor n/2\rfloor}\right\}\geq\frac{1}{2}\binom{n}{\lfloor n/2\rfloor}p^{\lceil n/2\rceil}2^{-\lfloor n/2\rfloor}\geq\frac{1}{2}p^{\lceil n/2\rceil}=\frac{2\delta}{d}, \tag*{(14)} η ≥ 2 1 ( ⌊ n /2 ⌋ n ) min { p ⌈ n /2 ⌉ ( 1 − p ) ⌊ n /2 ⌋ , ( 1 − p ) ⌈ n /2 ⌉ p ⌊ n /2 ⌋ } ≥ 2 1 ( ⌊ n /2 ⌋ n ) p ⌈ n /2 ⌉ 2 − ⌊ n /2 ⌋ ≥ 2 1 p ⌈ n /2 ⌉ = d 2 δ , (14)
where the second inequality uses the fact that p < 1 / 2 p<1/2 p < 1/2 twice, first to say the first term in the minimum is no larger than the second and then lower bound 1 − p 1-p 1 − p by 1 / 2 1/2 1/2 , the final inequality uses the well known inequality ( n r ) ≥ ( n r ) r \binom{n}{r}\geq\left(\frac{n}{r}\right)^r ( r n ) ≥ ( r n ) r for n ≥ r ≥ 1 n\geq r\geq1 n ≥ r ≥ 1 to conclude that 2 − ⌊ n / 2 ⌋ ( n ⌊ n / 2 ⌋ ) ≥ 2 − ⌈ n / 2 ⌉ ( n ⌊ n / 2 ⌋ ) ⌊ n / 2 ⌋ ≥ 1 2^{-\lfloor n/2\rfloor}\binom{n}{\lfloor n/2\rfloor}\geq2^{-\lceil n/2\rceil}\left(\frac{n}{\lfloor n/2\rfloor}\right)^{\lfloor n/2\rfloor}\geq1 2 − ⌊ n /2 ⌋ ( ⌊ n /2 ⌋ n ) ≥ 2 − ⌈ n /2 ⌉ ( ⌊ n /2 ⌋ n ) ⌊ n /2 ⌋ ≥ 1 ,10 and the equality follows from the definition of p p p . We now claim that every decoder ϕ : { 0 , ℓ } n d → { 0 , 1 } d \phi:\{0,\ell\}^{n d}\to\{0,1\}^d ϕ : { 0 , ℓ } n d → { 0 , 1 } d satisfies
Pr B ∼ U , X 1 , … , X n ∼ P B [ ϕ ( Z ) = B ] ≤ ( 1 − η ) d . \mathop{\Pr}_{B\sim U,\,X_1,\ldots,X_n\sim P_B}[\phi(Z)=B]\leq(1-\eta)^d. Pr B ∼ U , X 1 , … , X n ∼ P B [ ϕ ( Z ) = B ] ≤ ( 1 − η ) d .
Indeed, writing Z = ( Z 1 , … , Z d ) Z=(Z_1,\ldots,Z_d) Z = ( Z 1 , … , Z d ) and summing over the sample space we have that
Pr B ∼ U , X 1 , … , X n ∼ P B [ ϕ ( Z ) = B ] = 2 − d ∑ b ∈ { 0 , 1 } d ∑ z ∈ Z d 1 { ϕ ( z ) = b } ∏ j = 1 d P b j n ( z j ) = 2 − d ∑ z ∈ Z d ∏ j = 1 d P ϕ ( z ) j n ( z j ) \begin{aligned}
\mathop{\Pr}_{B\sim U,\,X_1,\ldots,X_n\sim P_B}[\phi(Z)=B]
=2^{-d}\sum_{b\in\{0,1\}^d}\sum_{z\in\mathcal{Z}^d}1\{\phi(z)=b\}\prod_{j=1}^dP_{b_j}^n(z_j) \\
&=2^{-d}\sum_{z\in\mathcal{Z}^d}\prod_{j=1}^dP_{\phi(z)_j}^n(z_j)
\end{aligned} Pr B ∼ U , X 1 , … , X n ∼ P B [ ϕ ( Z ) = B ] = 2 − d b ∈ { 0 , 1 } d ∑ z ∈ Z d ∑ 1 { ϕ ( z ) = b } j = 1 ∏ d P b j n ( z j ) = 2 − d z ∈ Z d ∑ j = 1 ∏ d P ϕ ( z ) j n ( z j )
≤ 2 − d ∑ z ∈ Z d ∏ j = 1 d max u ∈ { 0 , 1 } P u n ( z j ) = 2 − d ∑ z 1 ∈ Z ⋯ ∑ z d ∈ Z ∏ j = 1 d max u ∈ { 0 , 1 } P u n ( z j ) = ( 1 2 ∑ w ∈ Z max u ∈ { 0 , 1 } P u n ( w ) ) d . \begin{aligned}
\leq2^{-d}\sum_{z\in\mathcal{Z}^d}\prod_{j=1}^d\max_{u\in\{0,1\}}P_u^n(z_j) \\
&=2^{-d}\sum_{z_1\in\mathcal{Z}}\cdots\sum_{z_d\in\mathcal{Z}}\prod_{j=1}^d\max_{u\in\{0,1\}}P_u^n(z_j) \\
&=\left(\frac{1}{2}\sum_{w\in\mathcal{Z}}\max_{u\in\{0,1\}}P_u^n(w)\right)^d.
\end{aligned} ≤ 2 − d z ∈ Z d ∑ j = 1 ∏ d u ∈ { 0 , 1 } max P u n ( z j ) = 2 − d z 1 ∈ Z ∑ ⋯ z d ∈ Z ∑ j = 1 ∏ d u ∈ { 0 , 1 } max P u n ( z j ) = ( 2 1 w ∈ Z ∑ u ∈ { 0 , 1 } max P u n ( w ) ) d .
Now notice that
1 2 ∑ w ∈ Z max { P 0 n ( w ) , P 1 n ( w ) } = 1 2 ∑ w ∈ Z ( P 0 n ( w ) + P 1 n ( w ) − min { P 0 n ( w ) , P 1 n ( w ) } ) = 1 − η , \frac{1}{2}\sum_{w\in\mathcal{Z}}\max\{P_0^n(w),P_1^n(w)\}
=\frac{1}{2}\sum_{w\in\mathcal{Z}}\left(P_0^n(w)+P_1^n(w)-\min\{P_0^n(w),P_1^n(w)\}\right)
=1-\eta, 2 1 w ∈ Z ∑ max { P 0 n ( w ) , P 1 n ( w )} = 2 1 w ∈ Z ∑ ( P 0 n ( w ) + P 1 n ( w ) − min { P 0 n ( w ) , P 1 n ( w )} ) = 1 − η ,
so,
Pr B ∼ U , X 1 , … , X n ∼ P B [ ϕ ( Z ) = B ] ≤ ( 1 − η ) d . \Pr_{B\sim U, X_1,\ldots,X_n\sim P_B}[\phi(Z)=B]\leq(1-\eta)^d. B ∼ U , X 1 , … , X n ∼ P B Pr [ ϕ ( Z ) = B ] ≤ ( 1 − η ) d .
The above upper bound certainly holds for our decoder b ^ \hat{b} b ^ , so an averaging argument implies the existence of some b ⋆ ∈ { 0 , 1 } d b^\star\in\{0,1\}^d b ⋆ ∈ { 0 , 1 } d such that
Pr X 1 , … , X n ∼ P b ⋆ [ b ^ ( Z ) = b ⋆ ] ≤ ( 1 − η ) d ≤ ( 1 − 2 δ d ) d ≤ e − 2 δ < 1 − δ , \Pr_{X_1,\ldots,X_n\sim P_{b^\star}}\left[\hat{b}(Z)=b^\star\right]\leq(1-\eta)^d\leq\left(1-\frac{2\delta}{d}\right)^d\leq e^{-2\delta}<1-\delta, X 1 , … , X n ∼ P b ⋆ Pr [ b ^ ( Z ) = b ⋆ ] ≤ ( 1 − η ) d ≤ ( 1 − d 2 δ ) d ≤ e − 2 δ < 1 − δ ,
where we used the lower bound on η \eta η from (14) and the inequality e − 2 δ ≤ 1 − δ e^{-2\delta}\leq1-\delta e − 2 δ ≤ 1 − δ that holds for δ ∈ ( 0 , 1 2 ) \delta\in(0,\frac{1}{2}) δ ∈ ( 0 , 2 1 ) . Now, using the above with (13) , we conclude that
Pr X 1 , … , X n ∼ P b ⋆ [ ∥ A ( X 1 , … , X n ) − μ b ⋆ ∥ ∞ ≥ Δ 2 ] > Pr X 1 , … , X n ∼ P b ⋆ [ b ^ ( Z ) ≠ b ⋆ ] > δ . \Pr_{X_1,\ldots,X_n\sim P_{b^\star}}\left[\left\|\mathcal{A}(X_1,\ldots,X_n)-\mu_{b^\star}\right\|_\infty\geq\frac{\Delta}{2}\right]>\Pr_{X_1,\ldots,X_n\sim P_{b^\star}}\left[\hat{b}(Z)\neq b^\star\right]>\delta. X 1 , … , X n ∼ P b ⋆ Pr [ ∥ A ( X 1 , … , X n ) − μ b ⋆ ∥ ∞ ≥ 2 Δ ] > X 1 , … , X n ∼ P b ⋆ Pr [ b ^ ( Z ) = b ⋆ ] > δ .
All that remains is to lower bound Δ / 2 \Delta/2 Δ/2 . We have
Δ 2 = σ ( 1 − 2 p ) 2 p ( 1 − p ) ≥ σ ( 1 − 2 p ) 2 ( d 4 δ ) 1 2 1 n ≥ σ ( 1 − 2 p ) 4 ( d δ ) 1 2 1 n . \begin{aligned}
\frac{\Delta}{2}=\frac{\sigma(1-2p)}{2\sqrt{p(1-p)}} \\
&\geq\frac{\sigma(1-2p)}{2}\left(\frac{d}{4\delta}\right)^{\frac{1}{2^{\frac{1}{n}}}} \\
&\geq\frac{\sigma(1-2p)}{4}\left(\frac{d}{\delta}\right)^{\frac{1}{2^{\frac{1}{n}}}}.
\end{aligned} 2 Δ = 2 p ( 1 − p ) σ ( 1 − 2 p ) ≥ 2 σ ( 1 − 2 p ) ( 4 δ d ) 2 n 1 1 ≥ 4 σ ( 1 − 2 p ) ( δ d ) 2 n 1 1 .
where we used the facts p = ( 4 δ d ) 1 2 1 n p=\left(\frac{4\delta}{d}\right)^{\frac{1}{2^{\frac{1}{n}}}} p = ( d 4 δ ) 2 n 1 1 , 1 1 − p ≥ 1 \sqrt{\frac{1}{1-p}}\geq1 1 − p 1 ≥ 1 and 4 − 1 2 1 n ≥ 1 2 4^{-\frac{1}{2^{\frac{1}{n}}}}\geq\frac{1}{2} 4 − 2 n 1 1 ≥ 2 1 . This completes the proof. □ \square □
Lemma 4.5 (Gaussian lower bound for the large-sample regime). There exists a universal constant c > 0 c>0 c > 0 such that for every n , d ∈ N n,d\in\mathbb{N} n , d ∈ N , every σ > 0 \sigma>0 σ > 0 , and every δ ∈ ( 0 , 1 / 4 ) \delta\in(0,1/4) δ ∈ ( 0 , 1/4 ) ,
r ( n , d , σ , δ ) ≥ c σ log ( d / δ ) n . r(n,d,\sigma,\delta)\geq c\sigma\sqrt{\frac{\log(d/\delta)}{n}}. r ( n , d , σ , δ ) ≥ c σ n log ( d / δ ) .
Proof. Note that it suffices to prove the lower bound on the Gaussian distribution:
X 1 , … , X n ∣ μ ∼ N ( μ , σ 2 I d ) ⊗ n , μ ∈ R d . X_1,\ldots,X_n\mid\mu\sim\mathcal{N}(\mu,\sigma^2 I_d)^{\otimes n},\qquad\mu\in\mathbb{R}^d. X 1 , … , X n ∣ μ ∼ N ( μ , σ 2 I d ) ⊗ n , μ ∈ R d .
Fix an arbitrary estimator
A : ( R d ) n → R d . \mathcal{A}:(\mathbb{R}^d)^n\to\mathbb{R}^d. A : ( R d ) n → R d .
Let
X ‾ = 1 n ∑ i = 1 n X i . \overline{X}=\frac{1}{n}\sum_{i=1}^n X_i. X = n 1 i = 1 ∑ n X i .
For a parameter s > 0 s>0 s > 0 and assume the Gaussian prior on μ \mu μ :
μ ∼ N ( 0 , s 2 I d ) . \mu\sim\mathcal{N}(0,s^2I_d). μ ∼ N ( 0 , s 2 I d ) .
Under this prior and the Gaussian observation model above, X ‾ \overline{X} X is a sufficient statistic for μ \mu μ . Concretely, the posterior distribution of μ \mu μ given the full sample X = ( X 1 , … , X n ) X=(X_1,\ldots,X_n) X = ( X 1 , … , X n ) is
μ ∣ X ∼ N ( α s X ‾ , τ s 2 I d ) , \mu\mid X\sim\mathcal{N}(\alpha_s\overline{X},\tau_s^2I_d), μ ∣ X ∼ N ( α s X , τ s 2 I d ) ,
where
α s = s 2 s 2 + σ 2 / n , τ s 2 = ( 1 s 2 + n σ 2 ) − 1 = s 2 σ 2 σ 2 + n s 2 . \alpha_s = \frac{s^2}{s^2+\sigma^2/n}, \qquad\tau_s^2 = \left(\frac{1}{s^2}+\frac{n}{\sigma^2}\right)^{-1} = \frac{s^2\sigma^2}{\sigma^2+ns^2}. α s = s 2 + σ 2 / n s 2 , τ s 2 = ( s 2 1 + σ 2 n ) − 1 = σ 2 + n s 2 s 2 σ 2 .
Note, in particular, that:
τ s ⟶ σ n as s → ∞ . \tau_s \longrightarrow\frac{\sigma}{\sqrt{n}} \qquad\text{as } s\to\infty. τ s ⟶ n σ as s → ∞.
Fix r > 0 r>0 r > 0 , and define the cube
K r : = { z ∈ R d : ∥ z ∥ ∞ < r } . K_r := \{z\in\mathbb{R}^d : \|z\|_\infty<r\}. K r := { z ∈ R d : ∥ z ∥ ∞ < r } .
Observe that K r K_r K r is convex and centrally symmetric.
Now condition on the realized sample X \mathbf{X} X . The conditional success probability of the estimator is
Pr [ ∥ A ( X ) − μ ∥ ∞ < r ∣ X ] = Pr [ μ ∈ A ( X ) + K r ∣ X ] . \Pr[\|\mathcal{A}(\mathbf{X})-\mu\|_\infty<r\mid\mathbf{X}]
=
\Pr[\mu\in\mathcal{A}(\mathbf{X})+K_r\mid\mathbf{X}]. Pr [ ∥ A ( X ) − μ ∥ ∞ < r ∣ X ] = Pr [ μ ∈ A ( X ) + K r ∣ X ] .
Since
μ ∣ X ∼ N ( α s X ˉ , τ s 2 I d ) , \mu\mid\mathbf{X}\sim\mathcal{N}(\alpha_s\bar{X},\tau_s^2I_d), μ ∣ X ∼ N ( α s X ˉ , τ s 2 I d ) ,
this conditional success probability of the estimator is
Pr [ α s X ˉ + τ s G ∈ A ( X ) + K r ∣ X ] = Pr [ τ s G ∈ A ( X ) − α s X ˉ + K r ∣ X ] , \Pr[\alpha_s\bar{X}+\tau_sG\in\mathcal{A}(\mathbf{X})+K_r\mid\mathbf{X}]
=
\Pr[\tau_sG\in\mathcal{A}(\mathbf{X})-\alpha_s\bar{X}+K_r\mid\mathbf{X}], Pr [ α s X ˉ + τ s G ∈ A ( X ) + K r ∣ X ] = Pr [ τ s G ∈ A ( X ) − α s X ˉ + K r ∣ X ] ,
where G ∼ N ( 0 , I d ) G\sim\mathcal{N}(0,I_d) G ∼ N ( 0 , I d ) . By Anderson’s inequality, for a centered Gaussian vector and a convex centrally symmetric set K r K_r K r , the Gaussian measure of a translate of K r K_r K r is maximized at the centered translate [3 ] . Hence
Pr [ τ s G ∈ A ( X ) − α s X ˉ + K r ∣ X ] ≤ Pr [ τ s G ∈ K r ∣ X ] . \Pr[\tau_sG\in\mathcal{A}(\mathbf{X})-\alpha_s\bar{X}+K_r\mid\mathbf{X}]
\le
\Pr[\tau_sG\in K_r\mid\mathbf{X}]. Pr [ τ s G ∈ A ( X ) − α s X ˉ + K r ∣ X ] ≤ Pr [ τ s G ∈ K r ∣ X ] .
Averaging over X X X under the joint prior-predictive distribution gives
Pr [ ∥ A ( X ) − μ ∥ ∞ < r ] ≤ Pr [ τ s ∥ G ∥ ∞ < r ] . \Pr[\|\mathcal{A}(\mathbf{X})-\mu\|_\infty<r]
\le
\Pr[\tau_s\|G\|_\infty<r]. Pr [ ∥ A ( X ) − μ ∥ ∞ < r ] ≤ Pr [ τ s ∥ G ∥ ∞ < r ] .
And consequently,
Pr [ ∥ A ( X ) − μ ∥ ∞ ≥ r ] ≥ Pr [ τ s ∥ G ∥ ∞ ≥ r ] . \Pr[\|\mathcal{A}(\mathbf{X})-\mu\|_\infty\ge r]
\ge
\Pr[\tau_s\|G\|_\infty\ge r]. Pr [ ∥ A ( X ) − μ ∥ ∞ ≥ r ] ≥ Pr [ τ s ∥ G ∥ ∞ ≥ r ] .
Letting s → ∞ s\to\infty s → ∞ , and using continuity of the distribution of ∥ G ∥ ∞ \|G\|_\infty ∥ G ∥ ∞ , yields
sup μ ∈ R d X 1 , … , X n ∼ N ( μ , σ 2 I d ) Pr [ ∥ A ( X 1 , … , X n ) − μ ∥ ∞ ≥ r ] ≥ Pr [ σ n ∥ G ∥ ∞ ≥ r ] . (15) \sup_{\substack{\mu\in\mathbb{R}^d\\X_1,\ldots,X_n\sim\mathcal{N}(\mu,\sigma^2I_d)}}
\Pr[\|\mathcal{A}(X_1,\ldots,X_n)-\mu\|_\infty\ge r]
\ge
\Pr\left[\frac{\sigma}{\sqrt{n}}\|G\|_\infty\ge r\right]. \tag*{(15)} μ ∈ R d X 1 , … , X n ∼ N ( μ , σ 2 I d ) sup Pr [ ∥ A ( X 1 , … , X n ) − μ ∥ ∞ ≥ r ] ≥ Pr [ n σ ∥ G ∥ ∞ ≥ r ] . (15)
It remains to choose r r r . We use the following standard Gaussian maximum lower bound:
Claim 4.6. There exists a universal constant c 0 > 0 c_0>0 c 0 > 0 such that for every d ∈ N d\in\mathbb{N} d ∈ N and every δ ∈ ( 0 , 1 / 4 ) \delta\in(0,1/4) δ ∈ ( 0 , 1/4 ) ,
Pr [ ∥ G ∥ ∞ ≥ c 0 log ( d / δ ) ] ≥ δ . \Pr\left[\|G\|_\infty\ge c_0\sqrt{\log(d/\delta)}\right]\ge\delta. Pr [ ∥ G ∥ ∞ ≥ c 0 log ( d / δ ) ] ≥ δ . Proof. Let
L = log ( d / δ ) , t = c 0 L , p t = Pr ( ∣ g ∣ ≥ t ) , L=\log(d/\delta),\qquad t=c_0\sqrt{L},\qquad p_t=\Pr(|g|\ge t), L = log ( d / δ ) , t = c 0 L , p t = Pr ( ∣ g ∣ ≥ t ) , where g ∼ N ( 0 , 1 ) g\sim\mathcal{N}(0,1) g ∼ N ( 0 , 1 ) . If t ≤ 1 t\le1 t ≤ 1 , then
Pr [ ∥ G ∥ ∞ ≥ t ] ≥ Pr [ ∣ g ∣ ≥ 1 ] > δ , \Pr[\|G\|_\infty\ge t]\ge\Pr[|g|\ge1]>\delta, Pr [ ∥ G ∥ ∞ ≥ t ] ≥ Pr [ ∣ g ∣ ≥ 1 ] > δ , as Pr [ ∣ g ∣ ≥ 1 ] ≥ 1 / 4 \Pr[|g|\ge1]\ge1/4 Pr [ ∣ g ∣ ≥ 1 ] ≥ 1/4 and δ < 1 / 4 \delta<1/4 δ < 1/4 .
If t > 1 t > 1 t > 1 , the Gaussian tail lower bound gives
p t ≥ c 1 t − 1 e − t 2 / 2 p_t \ge c_1 t^{-1}e^{-t^2/2} p t ≥ c 1 t − 1 e − t 2 /2
for a universal constant c 1 > 0 c_1 > 0 c 1 > 0 . Thus
d p t ≥ c 1 d c 0 L exp ( − c 0 2 2 L ) = c 1 δ c 0 L ( d δ ) 1 − c 0 2 / 2 . d p_t \ge\frac{c_1d}{c_0\sqrt{L}}\exp\left(-\frac{c_0^2}{2}L\right)=\frac{c_1\delta}{c_0\sqrt{L}}\left(\frac{d}{\delta}\right)^{1-c_0^2/2}. d p t ≥ c 0 L c 1 d exp ( − 2 c 0 2 L ) = c 0 L c 1 δ ( δ d ) 1 − c 0 2 /2 .
Choosing c 0 > 0 c_0 > 0 c 0 > 0 sufficiently small ensures that d p t ≥ 2 δ d p_t \ge2\delta d p t ≥ 2 δ for all d ≥ 1 d \ge1 d ≥ 1 and δ ∈ ( 0 , 1 / 4 ) \delta\in(0,1/4) δ ∈ ( 0 , 1/4 ) . Using the independence of the coordinates yields,
Pr [ ∥ G ∥ ∞ ≥ t ] = 1 − ( 1 − p t ) d ≥ 1 − e − d p t ≥ 1 − e − 2 δ ≥ δ . \Pr[\lVert G\rVert_\infty\ge t] = 1-(1-p_t)^d \ge1-e^{-dp_t} \ge1-e^{-2\delta} \ge\delta. Pr [∥ G ∥ ∞ ≥ t ] = 1 − ( 1 − p t ) d ≥ 1 − e − d p t ≥ 1 − e − 2 δ ≥ δ .
This proves the Gaussian maximum lower bound.
Now setting
r = c 0 σ log ( d / δ ) n . r=c_0\sigma\sqrt{\frac{\log(d/\delta)}{n}}. r = c 0 σ n log ( d / δ ) .
with Claim 4.6 and Equation (15) concludes the proof.
Proof of Theorem 4.1
Write L = log ( d / δ ) L=\log(d/\delta) L = log ( d / δ ) . We first prove the upper bound. In the isotropic case, Theorem 4.3 gives, for the coordinate-wise median-of-means estimator with t = 2 ⌈ L ⌉ t=2\lceil L\rceil t = 2 ⌈ L ⌉ buckets
r ( n , d , δ ) ≲ { ( d δ ) 1 2 ⌈ n / 2 ⌉ , n < 2 ⌈ L ⌉ , L n , n ≥ 2 ⌈ L ⌉ . r(n,d,\delta)\lesssim
\begin{cases}
\left(\dfrac{d}{\delta}\right)^{\frac{1}{2\lceil n/2\rceil}}, & n<2\lceil L\rceil,\\
\sqrt{\dfrac{L}{n}}, & n\ge2\lceil L\rceil.
\end{cases} r ( n , d , δ ) ≲ ⎩ ⎨ ⎧ ( δ d ) 2 ⌈ n /2 ⌉ 1 , n L , n < 2 ⌈ L ⌉ , n ≥ 2 ⌈ L ⌉ .
This implies the claimed upper bound in both regimes. If n ≲ L n\lesssim L n ≲ L , then the first line is exactly the desired bound when it applies, while if the second line applies then L / n ≤ 1 ≤ ( d / δ ) 1 / ( 2 ⌈ n / 2 ⌉ ) \sqrt{L/n}\le1\le(d/\delta)^{1/(2\lceil n/2\rceil)} L / n ≤ 1 ≤ ( d / δ ) 1/ ( 2 ⌈ n /2 ⌉) . If n ≳ L n\gtrsim L n ≳ L , then the second line is exactly the desired bound when it applies, while if the first line applies then n = Θ ( L ) n=\Theta(L) n = Θ ( L ) , and the two rates are comparable up to universal constants.
We now prove the lower bound. First, consider the large sample regime n ≳ L n\gtrsim L n ≳ L . We can invoke the Gaussian lower bound (Lemma 4.5 ) in the isotropic to get
r ( n , d , δ ) ≳ L n , r(n,d,\delta)\gtrsim\sqrt{\frac{L}{n}}, r ( n , d , δ ) ≳ n L ,
as claimed.
It remains to prove the lower bound in the small sample regime. Assume that n ≲ L n\lesssim L n ≲ L . By taking the universal constant small in the theorem statement to be small enough, we may assume that δ < 1 / 4 \delta<1/4 δ < 1/4 and that L ≥ 2 log 4 L\ge2\log4 L ≥ 2 log 4 . Set
a = ( 4 δ d ) 1 / ⌈ n / 2 ⌉ . (16) a=\left(\frac{4\delta}{d}\right)^{1/\lceil n/2\rceil}. \tag*{(16)} a = ( d 4 δ ) 1/ ⌈ n /2 ⌉ . (16)
If a ≤ 1 / 4 a \le1/4 a ≤ 1/4 , then 1 − 2 a ≥ 1 / 2 1-2a \ge1/2 1 − 2 a ≥ 1/2 , and Theorem 4.4 implies that for every estimator there is a distribution with mean μ \mu μ and covariance I d I_d I d such that
Pr [ ∥ A ( X 1 , … , X n ) − μ ∥ ∞ ≥ 1 8 ( d δ ) 1 2 ⌈ n 2 ⌉ ] > δ . \Pr\left[\left\|\mathcal{A}(X_1,\ldots,X_n)-\mu\right\|_{\infty}\ge\frac{1}{8}\left(\frac{d}{\delta}\right)^{\frac{1}{2\left\lceil\frac{n}{2}\right\rceil}}\right]>\delta. Pr [ ∥ A ( X 1 , … , X n ) − μ ∥ ∞ ≥ 8 1 ( δ d ) 2 ⌈ 2 n ⌉ 1 ] > δ .
Hence, by the definition of the minimax risk, we have
r ( n , d , δ ) ≳ ( d δ ) 1 2 ⌈ n 2 ⌉ . r(n,d,\delta)\gtrsim\left(\frac{d}{\delta}\right)^{\frac{1}{2\left\lceil\frac{n}{2}\right\rceil}}. r ( n , d , δ ) ≳ ( δ d ) 2 ⌈ 2 n ⌉ 1 .
On the other hand if a > 1 / 4 a>1/4 a > 1/4 , then
( d δ ) 1 2 ⌈ n 2 ⌉ ≲ 1 , \left(\frac{d}{\delta}\right)^{\frac{1}{2\left\lceil\frac{n}{2}\right\rceil}}\lesssim1, ( δ d ) 2 ⌈ 2 n ⌉ 1 ≲ 1 ,
which we can combine with Lemma 4.5 and our assumption that n ≲ L n\lesssim L n ≲ L to conclude that
r ( n , d , δ ) ≳ L n ≳ 1 ≲ ( d δ ) 1 2 ⌈ n 2 ⌉ . r(n,d,\delta)\gtrsim\sqrt{\frac{L}{n}}\gtrsim1\lesssim\left(\frac{d}{\delta}\right)^{\frac{1}{2\left\lceil\frac{n}{2}\right\rceil}}. r ( n , d , δ ) ≳ n L ≳ 1 ≲ ( δ d ) 2 ⌈ 2 n ⌉ 1 .
Combining the upper and lower bounds completes the proof.
Funding. Mikael was while carrying out this work, supported by an Internationalisation Fellowship from the Carlsberg Foundation, Independent Research Fund Denmark (DFF) Sapere Aude Research Leader grant No. 9064-00068B, and the European Union (ERC, TUCLA, 101125203). Kasper was supported by the European Union (ERC, TUCLA, 101125203). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. Yeshwanth Cherapanamjeri is supported by an NTU-NAP Start-up Grant (025661-00016).
AI assistance disclosure. The theorem statements, proofs, and hard constructions in this work were developed by the authors. Most of the results were obtained in summer 2025 without material AI assistance. During the preparation of the manuscript in April 2026, OpenAI GPT-5.5 assisted with formalizing and drafting parts of the proof of the lower bound for projection based median of means estimators, as well as with checking and polishing the manuscript.
Omitted Proofs
Lemma A.1. Let f 1 , … , f t : R + → R + f_1,\ldots,f_t:\mathbb{R}_{+}\to\mathbb{R}_{+} f 1 , … , f t : R + → R + be t t t , measurable, non-increasing and integrable functions. Then
∫ 0 ∞ ∏ i = 1 t f i ( x 1 / t ) d x ≤ ∏ i = 1 t ∫ 0 ∞ f i ( x ) d x \int_{0}^{\infty}\prod_{i=1}^{t}f_i(x^{1/t})\,\mathrm{d}x\leq\prod_{i=1}^{t}\int_{0}^{\infty}f_i(x)\,\mathrm{d}x ∫ 0 ∞ i = 1 ∏ t f i ( x 1/ t ) d x ≤ i = 1 ∏ t ∫ 0 ∞ f i ( x ) d x
Proof. We have that
∏ i = 1 t ∫ 0 ∞ f i ( x ) d x = ∏ i = 1 t ∫ 0 ∞ f i ( x i ) d x i = ∫ 0 ∞ ⋯ ∫ 0 ∞ ∏ i = 1 t f i ( x i ) d x 1 … d x t = ∑ x i 1 < ⋯ < x i t { i 1 , … , i t } = [ t ] ∫ 0 ∞ ∫ 0 x i t ⋯ ∫ 0 x i 2 ∏ i = 1 t f i ( x i ) d x i 1 … d x i t − 1 d x i t ≥ ∑ x i 1 < ⋯ < x i t { i 1 , … , i t } = [ t ] ∫ 0 ∞ ∏ i = 1 t f i ( x i t ) ∫ 0 x i t ⋯ ∫ 0 x i 2 1 d x i 1 … d x i t − 1 d x i t = t ! ∫ 0 ∞ ∏ i = 1 t f i ( x ) x t − 1 ( t − 1 ) ! d x = ∫ 0 ∞ ∏ i = 1 t f i ( x 1 / t ) d x , \begin{aligned}
\prod_{i=1}^{t}\int_{0}^{\infty}f_i(x)\,\mathrm{d}x
&=\prod_{i=1}^{t}\int_{0}^{\infty}f_i(x_i)\,\mathrm{d}x_i\\
&=\int_{0}^{\infty}\cdots\int_{0}^{\infty}\prod_{i=1}^{t}f_i(x_i)\,\mathrm{d}x_1\ldots\mathrm{d}x_t\\
&=\sum_{\substack{x_{i_1}<\cdots<x_{i_t}\\\{i_1,\ldots,i_t\}=[t]}}\int_{0}^{\infty}\int_{0}^{x_{i_t}}\cdots\int_{0}^{x_{i_2}}\prod_{i=1}^{t}f_i(x_i)\,\mathrm{d}x_{i_1}\ldots\mathrm{d}x_{i_{t-1}}\mathrm{d}x_{i_t}\\
&\geq\sum_{\substack{x_{i_1}<\cdots<x_{i_t}\\\{i_1,\ldots,i_t\}=[t]}}\int_{0}^{\infty}\prod_{i=1}^{t}f_i(x_{i_t})\int_{0}^{x_{i_t}}\cdots\int_{0}^{x_{i_2}}1\mathrm{d}x_{i_1}\ldots\mathrm{d}x_{i_{t-1}}\mathrm{d}x_{i_t}\\
&=t!\int_{0}^{\infty}\prod_{i=1}^{t}f_i(x)\frac{x^{t-1}}{(t-1)!}\,\mathrm{d}x\\
&=\int_{0}^{\infty}\prod_{i=1}^{t}f_i(x^{1/t})\,\mathrm{d}x,
\end{aligned} i = 1 ∏ t ∫ 0 ∞ f i ( x ) d x = i = 1 ∏ t ∫ 0 ∞ f i ( x i ) d x i = ∫ 0 ∞ ⋯ ∫ 0 ∞ i = 1 ∏ t f i ( x i ) d x 1 … d x t = x i 1 < ⋯ < x i t { i 1 , … , i t } = [ t ] ∑ ∫ 0 ∞ ∫ 0 x i t ⋯ ∫ 0 x i 2 i = 1 ∏ t f i ( x i ) d x i 1 … d x i t − 1 d x i t ≥ x i 1 < ⋯ < x i t { i 1 , … , i t } = [ t ] ∑ ∫ 0 ∞ i = 1 ∏ t f i ( x i t ) ∫ 0 x i t ⋯ ∫ 0 x i 2 1 d x i 1 … d x i t − 1 d x i t = t ! ∫ 0 ∞ i = 1 ∏ t f i ( x ) ( t − 1 )! x t − 1 d x = ∫ 0 ∞ i = 1 ∏ t f i ( x 1/ t ) d x ,
where the third equality follows from decomposing the integration domain R + t \mathbb{R}_{+}^{t} R + t into the t ! t! t ! disjoint regions corresponding to the possible orderings x i 1 < ⋯ < x i t x_{i_1}<\cdots<x_{i_t} x i 1 < ⋯ < x i t of the coordinates. The inequality follows from the fact that each f i f_i f i is non-increasing, so on any region where x i 1 < ⋯ < x i t x_{i_1}<\cdots<x_{i_t} x i 1 < ⋯ < x i t we have f i ( x i ) ≥ f i ( x i t ) f_i(x_i)\geq f_i(x_{i_t}) f i ( x i ) ≥ f i ( x i t ) for every i ∈ [ t ] i\in[t] i ∈ [ t ] . The second last equality follows from the fact that there are t ! t! t ! such orderings, together with an explicit evaluation of the inner integrals. The final equality follows from a change of variables.
Theorem 3.4. Let X 1 , … , X t X_1,\ldots,X_t X 1 , … , X t be t t t independent random variables with a common mean μ \mu μ and let M = M ( X 1 , … , X t ) M=M(X_1,\ldots,X_t) M = M ( X 1 , … , X t ) denote their median. For all q ≥ 0 q\ge0 q ≥ 0 it holds that
E [ ∣ M − μ ∣ q ⌊ t / 2 ⌋ ] ≤ ( t ⌊ t / 2 ⌋ ) max i ∈ [ t ] E [ ∣ X i − μ ∣ q ⌊ t / 2 ⌋ ] . \mathbb{E}\left[|M-\mu|^{q\lfloor t/2\rfloor}\right]\le\binom{t}{\lfloor t/2\rfloor}\max_{i\in[t]}\mathbb{E}\left[|X_i-\mu|^{q\lfloor t/2\rfloor}\right]. E [ ∣ M − μ ∣ q ⌊ t /2 ⌋ ] ≤ ( ⌊ t /2 ⌋ t ) i ∈ [ t ] max E [ ∣ X i − μ ∣ q ⌊ t /2 ⌋ ] .
Proof. The case q = 0 q=0 q = 0 follows from the left hand side of the inequality to be less than or equal to the right hand side of the inequality. Furthermore, if the right hand side is infinite then the inequality also holds. Thus, we can assume that q > 0 q>0 q > 0 and that the right hand side is finite, meaning all the expectations E [ ∣ X i − μ ∣ q ] \mathbb{E}[|X_i-\mu|^q] E [ ∣ X i − μ ∣ q ] are finite. By calculations we have that
E [ ∣ M − μ ∣ q ⌊ t / 2 ⌋ ] = ∫ 0 ∞ Pr [ ∣ M − μ ∣ q ⌊ t / 2 ⌋ ≥ x ] d x = ∫ 0 ∞ Pr [ ∣ M − μ ∣ q ≥ x 1 ⌊ t / 2 ⌋ ] d x . \mathbb{E}\left[|M-\mu|^{q\lfloor t/2\rfloor}\right]=\int_0^\infty\Pr\left[|M-\mu|^{q\lfloor t/2\rfloor}\ge x\right]\,dx=\int_0^\infty\Pr\left[|M-\mu|^q\ge x^{\frac{1}{\lfloor t/2\rfloor}}\right]\,dx. E [ ∣ M − μ ∣ q ⌊ t /2 ⌋ ] = ∫ 0 ∞ Pr [ ∣ M − μ ∣ q ⌊ t /2 ⌋ ≥ x ] d x = ∫ 0 ∞ Pr [ ∣ M − μ ∣ q ≥ x ⌊ t /2 ⌋ 1 ] d x .
where we have used that the expectation of a positive random variable is the integral of its right tail. Now for the median M M M of X 1 , … , X t X_1,\ldots,X_t X 1 , … , X t to be x x x away from the mean μ \mu μ it must be the case that there are ⌊ t / 2 ⌋ \lfloor t/2\rfloor ⌊ t /2 ⌋ X i X_i X i ’s such that ∣ X i − μ ∣ ≥ x |X_i-\mu|\ge x ∣ X i − μ ∣ ≥ x . By this, a union bound and independence of X i X_i X i ’s we then get that:
E [ ∣ M − μ ∣ q ⌊ t / 2 ⌋ ] ≤ ∫ 0 ∞ Pr [ ∃ I ∈ ( [ t ] ⌊ t / 2 ⌋ ) : ∀ i ∈ I such that ∣ X i − μ ∣ q ≥ x 1 ⌊ t / 2 ⌋ ] d x ≤ ∑ I ∈ ( [ t ] ⌊ t / 2 ⌋ ) ∫ 0 ∞ Pr [ ∀ i ∈ I : ∣ X i − μ ∣ q ≥ x 1 ⌊ t / 2 ⌋ ] d x = ∑ I ∈ ( [ t ] ⌊ t / 2 ⌋ ) ∫ 0 ∞ ∏ i ∈ I Pr [ ∣ X i − μ ∣ q ≥ x 1 ⌊ t / 2 ⌋ ] d x . \begin{aligned}
\mathbb{E}\left[|M-\mu|^{q\lfloor t/2\rfloor}\right]\le\int_0^\infty\Pr\left[\exists I\in\binom{[t]}{\lfloor t/2\rfloor}:\forall i\in I\text{ such that }|X_i-\mu|^q\ge x^{\frac{1}{\lfloor t/2\rfloor}}\right]\,dx \\
&\le\sum_{I\in\binom{[t]}{\lfloor t/2\rfloor}}\int_0^\infty\Pr\left[\forall i\in I:|X_i-\mu|^q\ge x^{\frac{1}{\lfloor t/2\rfloor}}\right]\,dx \\
&=\sum_{I\in\binom{[t]}{\lfloor t/2\rfloor}}\int_0^\infty\prod_{i\in I}\Pr\left[|X_i-\mu|^q\ge x^{\frac{1}{\lfloor t/2\rfloor}}\right]\,dx.
\end{aligned} E [ ∣ M − μ ∣ q ⌊ t /2 ⌋ ] ≤ ∫ 0 ∞ Pr [ ∃ I ∈ ( ⌊ t /2 ⌋ [ t ] ) : ∀ i ∈ I such that ∣ X i − μ ∣ q ≥ x ⌊ t /2 ⌋ 1 ] d x ≤ I ∈ ( ⌊ t /2 ⌋ [ t ] ) ∑ ∫ 0 ∞ Pr [ ∀ i ∈ I : ∣ X i − μ ∣ q ≥ x ⌊ t /2 ⌋ 1 ] d x = I ∈ ( ⌊ t /2 ⌋ [ t ] ) ∑ ∫ 0 ∞ i ∈ I ∏ Pr [ ∣ X i − μ ∣ q ≥ x ⌊ t /2 ⌋ 1 ] d x .
Now using that for each i i i , the function Pr [ ∣ X i − μ ∣ q ≥ x ] \Pr[|X_i-\mu|^q\ge x] Pr [ ∣ X i − μ ∣ q ≥ x ] is non-increasing in x x x , integrable by considering the case where the expectation is finite for all X i X_i X i , and measureable by X i X_i X i being a random variable, we can use Lemma A.1 to get that
E [ ∣ M − μ ∣ q ⌊ t / 2 ⌋ ] ≤ ∑ I ∈ ( [ t ] ⌊ t / 2 ⌋ ) ∏ i ∈ I ∫ 0 ∞ Pr [ ∣ X i − μ ∣ q ≥ x ] d x = ∑ I ∈ ( [ t ] ⌊ t / 2 ⌋ ) ∏ i ∈ I E [ ∣ X i − μ ∣ q ] ≤ ( t ⌊ t / 2 ⌋ ) max i ∈ [ t ] E [ ∣ X i − μ ∣ q ] ⌊ t / 2 ⌋ . \begin{aligned}
\mathbb{E}\left[|M-\mu|^{q\lfloor t/2\rfloor}\right]\le\sum_{I\in\binom{[t]}{\lfloor t/2\rfloor}}\prod_{i\in I}\int_0^\infty\Pr\left[|X_i-\mu|^q\ge x\right]\,dx \\
&=\sum_{I\in\binom{[t]}{\lfloor t/2\rfloor}}\prod_{i\in I}\mathbb{E}\left[|X_i-\mu|^q\right] \\
&\le\binom{t}{\lfloor t/2\rfloor}\max_{i\in[t]}\mathbb{E}\left[|X_i-\mu|^q\right]^{\lfloor t/2\rfloor}.
\end{aligned} E [ ∣ M − μ ∣ q ⌊ t /2 ⌋ ] ≤ I ∈ ( ⌊ t /2 ⌋ [ t ] ) ∑ i ∈ I ∏ ∫ 0 ∞ Pr [ ∣ X i − μ ∣ q ≥ x ] d x = I ∈ ( ⌊ t /2 ⌋ [ t ] ) ∑ i ∈ I ∏ E [ ∣ X i − μ ∣ q ] ≤ ( ⌊ t /2 ⌋ t ) i ∈ [ t ] max E [ ∣ X i − μ ∣ q ] ⌊ t /2 ⌋ .
where the first inequality follows from Lemma A.1, the first equality follows from the fact that the expectation of a positive random variable is the integral of its right tail, and the last inequality follows from taking max under the product.
Proof of thm:projsuboptimal
In this section, we establish that projection-based Median-of-Means estimators are provably suboptimal for ℓ p \ell_p ℓ p norms when p > 2 p > 2 p > 2 . Let p > 2 p > 2 p > 2 and q < 2 q < 2 q < 2 denote the order of the corresponding dual ball. The projection-based median is now defined as follows for a pointset Y = { y i } i = 1 n Y = \{y_i\}_{i=1}^n Y = { y i } i = 1 n with y i ∈ R d y_i \in\mathbb{R}^d y i ∈ R d :
Med p r o j ( Y ) = arg min x max v : ∥ v ∥ q = 1 ∣ ⟨ v , x ⟩ − Med ( { ⟨ v , y i ⟩ } i = 1 n ) ∣ . \operatorname{Med}_{\mathrm{proj}}(Y) = \arg\min_{x} \max_{v:\|v\|_q=1} \left|\langle v,x\rangle- \operatorname{Med}\left(\{\langle v,y_i\rangle\}_{i=1}^n\right)\right|. Med proj ( Y ) = arg x min v : ∥ v ∥ q = 1 max ∣ ⟨ v , x ⟩ − Med ( {⟨ v , y i ⟩ } i = 1 n ) ∣ .
Theorem 1.2 (Suboptimality of Projection-based median-of-means). Let p > 2 p > 2 p > 2 . There exist absolute constants C , c > 0 C,c > 0 C , c > 0 such that the following hold. Let d , n ∈ N d,n \in\mathbb{N} d , n ∈ N be such that n ≤ c d n \le c\sqrt{d} n ≤ c d and d > C d > C d > C . Then, there exists a distribution D D D with mean 0 0 0 and covariance I d I_d I d such that the projection-based median-of-means estimator with any bucket size m m m satisfying n / m ≥ 3 n/m \ge3 n / m ≥ 3 , μ ^ P r o j \widehat{\mu}_{\mathrm{Proj}} μ Proj , satisfies:
Pr X ∼ D ⊗ n [ ∥ μ ^ P r o j ( X ) ∥ p ≥ d 2 n 1 − 1 / p ] ≥ 0.9. \Pr_{X\sim D^{\otimes n}}\left[\|\widehat{\mu}_{\mathrm{Proj}}(X)\|_p \ge\frac{\sqrt{d}}{2n^{1-1/p}}\right] \ge0.9. X ∼ D ⊗ n Pr [ ∥ μ Proj ( X ) ∥ p ≥ 2 n 1 − 1/ p d ] ≥ 0.9.
:::
We will show that the median-of-means estimator with the projection-based median defined above is sub-optimal for any choice of number of buckets, t t t , equivalently bucket size m = n / t m = n/t m = n / t , for the distribution D D D , corresponding to the uniform distribution over the signed and scaled basis vectors. Formally:
∀ i ∈ [ d ] , s ∈ { ± 1 } : Pr X ∼ D ( X = s d e i ) = 1 2 d . \forall i \in[d], s \in\{\pm1\}: \Pr_{X\sim D}(X = s\sqrt{d}e_i) = \frac{1}{2d}. ∀ i ∈ [ d ] , s ∈ { ± 1 } : X ∼ D Pr ( X = s d e i ) = 2 d 1 .
where e i e_i e i denote the standard basis vectors in R d \mathbb{R}^d R d . Note that D D D has mean 0 0 0 and covariance I d I_d I d .
Now, let X = { X i } i = 1 n X = \{X_i\}_{i=1}^n X = { X i } i = 1 n be n n n iid samples from from D D D . Furthermore, from our definition of D D D , X i = s i d e c ( i ) X_i = s_i\sqrt{d}e_{c(i)} X i = s i d e c ( i ) with s i = ± 1 s_i = \pm1 s i = ± 1 and c ( i ) ∈ [ d ] c(i) \in[d] c ( i ) ∈ [ d ] . We first prove a simple lemma establishing that the c ( i ) c(i) c ( i ) are unique with high-probability:
Lemma B.2. Under the preconditions of Theorem 1.2 , we have:
∀ i , j ∈ [ n ] , i ≠ j : c ( i ) ≠ c ( j ) \forall i,j \in[n], i \ne j : c(i) \ne c(j) ∀ i , j ∈ [ n ] , i = j : c ( i ) = c ( j ) with probability at least $0.9.
Proof. We have:
Pr ( ∀ i , j ∈ [ n ] , i ≠ j : c ( i ) ≠ c ( j ) ) = ∏ i = 1 n ( 1 − i − 1 d ) ≥ ∏ i = 1 n ( 1 − n d ) = ( 1 − n d ) n ≥ exp ( − 2 n d ⋅ n ) ≥ 0.9 (17) \begin{aligned}
\Pr\left(\forall i,j \in[n], i \ne j : c(i) \ne c(j)\right) = \prod_{i=1}^{n}\left(1-\frac{i-1}{d}\right) \ge\prod_{i=1}^{n}\left(1-\frac{n}{d}\right) \\
&= \left(1-\frac{n}{d}\right)^n \ge\exp\left(-\frac{2n}{d}\cdot n\right) \ge0.9 \tag*{(17)}
\end{aligned} Pr ( ∀ i , j ∈ [ n ] , i = j : c ( i ) = c ( j ) ) = i = 1 ∏ n ( 1 − d i − 1 ) ≥ i = 1 ∏ n ( 1 − d n ) = ( 1 − d n ) n ≥ exp ( − d 2 n ⋅ n ) ≥ 0.9 (17)
as n ≤ c d n \le c\sqrt{d} n ≤ c d .
Now, we condition on the uniqueness of c ( i ) c(i) c ( i ) . Define the bucketed means Z i Z_i Z i as follows for i ∈ [ t ] i \in[t] i ∈ [ t ] with m : = n / t m := n/t m := n / t :
Z i = 1 m ∑ j = ( i − 1 ) m + 1 i m X j Z_i = \frac{1}{m}\sum_{j=(i-1)m+1}^{im} X_j Z i = m 1 j = ( i − 1 ) m + 1 ∑ im X j
with the collection denoted by Z Z Z . From PROJ-MED, the projection-based median-of-means estimate is the minimizer of the following function:
F ( x ) : = max v : ∥ v ∥ q = 1 ∣ ⟨ v , x ⟩ − Med ( { ⟨ v , Z i ⟩ } i = 1 t ) ∣ F(x) := \max_{v:\lVert v\rVert_q=1}\left|\langle v,x\rangle-\operatorname{Med}\left(\{\langle v,Z_i\rangle\}_{i=1}^{t}\right)\right| F ( x ) := v : ∥ v ∥ q = 1 max ⟨ v , x ⟩ − Med ( {⟨ v , Z i ⟩ } i = 1 t )
We now make some observations:
Observation B.3. F F F is a convex function of x x x .
Proof. This follows from F F F being defined as the maximum of a set of convex functions. □
Next, F F F satisfies the following symmetries:
Observation B.4. Defining:
X ~ i = d e c ( i ) , S ∈ R d × d : S i , j : = { 0 if i ≠ j 1 if i = j , ∀ ℓ , c ( ℓ ) ≠ i 1 if i = j , ∃ ℓ , c ( ℓ ) = i and s ℓ = 1 − 1 otherwise , and Z ~ i = 1 m ∑ j = ( i − 1 ) m + 1 i m X ~ j . \widetilde{X}_i=\sqrt{d}e_{c(i)},\ S\in\mathbb{R}^{d\times d}: S_{i,j}:=
\begin{cases}
0 & \text{if }i\ne j\\
1 & \text{if }i=j,\ \forall\ell,\ c(\ell)\ne i\\
1 & \text{if }i=j,\ \exists\ell,\ c(\ell)=i\text{ and }s_\ell=1\\
-1 & \text{otherwise}
\end{cases}
,\quad\text{and}\quad
\widetilde{Z}_i=\frac{1}{m}\sum_{j=(i-1)m+1}^{im}\widetilde{X}_j. X i = d e c ( i ) , S ∈ R d × d : S i , j := ⎩ ⎨ ⎧ 0 1 1 − 1 if i = j if i = j , ∀ ℓ , c ( ℓ ) = i if i = j , ∃ ℓ , c ( ℓ ) = i and s ℓ = 1 otherwise , and Z i = m 1 j = ( i − 1 ) m + 1 ∑ im X j . where uniqueness of c ( i ) c(i) c ( i ) from Lemma B.2 ensures that S S S is well-defined. Finally, defining F ~ \widetilde{F} F analogously to F F F , we observe the following:
∀ x : F ( x ) = F ~ ( S x ) . \forall x:\ F(x)=\widetilde{F}(Sx). ∀ x : F ( x ) = F ( S x ) . Consequently,
arg min x F ( x ) = S arg min x F ~ ( x ) . \underset{x}{\arg\min}\ F(x)=S\underset{x}{\arg\min}\ \widetilde{F}(x). x arg min F ( x ) = S x arg min F ( x ) .
Proof. From the definition of S S S we have
S X ~ i = S d e c ( i ) = S c ( i ) , c ( i ) d e c ( i ) = s i d e c ( i ) = X i S\widetilde{X}_i=S\sqrt{d}e_{c(i)}=S_{c(i),c(i)}\sqrt{d}e_{c(i)}=s_i\sqrt{d}e_{c(i)}=X_i S X i = S d e c ( i ) = S c ( i ) , c ( i ) d e c ( i ) = s i d e c ( i ) = X i
which implies
∀ v , ∥ v ∥ q = 1 , i ∈ [ t ] : ⟨ v , Z i ⟩ = ⟨ S v , Z ~ i ⟩ . \forall v,\ \lVert v\rVert_q=1,\ i\in[t]:\ \langle v,Z_i\rangle=\langle Sv,\widetilde{Z}_i\rangle. ∀ v , ∥ v ∥ q = 1 , i ∈ [ t ] : ⟨ v , Z i ⟩ = ⟨ S v , Z i ⟩ .
and hence
F ( x ) = max v : ∥ v ∥ q = 1 ∣ ⟨ v , x ⟩ − Med ( { ⟨ v , Z i ⟩ } i = 1 t ) ∣ = max v : ∥ v ∥ q = 1 ∣ ⟨ S v , S x ⟩ − Med ( { ⟨ S v , Z ~ i ⟩ } i = 1 t ) ∣ = F ~ ( S x ) F(x)=\max_{v:\lVert v\rVert_q=1}\left|\langle v,x\rangle-\operatorname{Med}\left(\{\langle v,Z_i\rangle\}_{i=1}^{t}\right)\right|
=\max_{v:\lVert v\rVert_q=1}\left|\langle Sv,Sx\rangle-\operatorname{Med}\left(\{\langle Sv,\widetilde{Z}_i\rangle\}_{i=1}^{t}\right)\right|
=\widetilde{F}(Sx) F ( x ) = v : ∥ v ∥ q = 1 max ⟨ v , x ⟩ − Med ( {⟨ v , Z i ⟩ } i = 1 t ) = v : ∥ v ∥ q = 1 max ⟨ S v , S x ⟩ − Med ( {⟨ S v , Z i ⟩ } i = 1 t ) = F ( S x )
where the last equality follows from the fact that S S S is a diagonal matrix with entries in { ± 1 } \{\pm1\} { ± 1 } , so S v Sv S v ranges over all vectors with ℓ q \ell_q ℓ q norm at most 1 as v v v does. □
On the event of Lemma B.2 , define the bucket supports
C r : = { c ( ( r − 1 ) m + 1 ) , … , c ( r m ) } , r ∈ [ t ] . C_r := \{c((r-1)m+1),\ldots,c(rm)\}, \qquad r \in[t]. C r := { c (( r − 1 ) m + 1 ) , … , c ( r m )} , r ∈ [ t ] .
Then the sets C 1 , … , C t C_1,\ldots,C_t C 1 , … , C t are disjoint, ∣ C r ∣ = m |C_r|=m ∣ C r ∣ = m for all r ∈ [ t ] r \in[t] r ∈ [ t ] , and
Z ~ r = d m ∑ j ∈ C r e j . \widetilde{Z}_r = \frac{\sqrt{d}}{m}\sum_{j\in C_r}e_j. Z r = m d j ∈ C r ∑ e j .
Hence,
F ~ ( x ) = max v : ∥ v ∥ q = 1 ∣ ⟨ v , x ⟩ − Med ( { d m ∑ j ∈ C r v j } r = 1 t ) ∣ . \widetilde{F}(x)=\max_{v:\lVert v\rVert_q=1}\left|\langle v,x\rangle-\operatorname{Med}\left(\left\{\frac{\sqrt{d}}{m}\sum_{j\in C_r}v_j\right\}_{r=1}^{t}\right)\right|. F ( x ) = v : ∥ v ∥ q = 1 max ⟨ v , x ⟩ − Med ⎩ ⎨ ⎧ m d j ∈ C r ∑ v j ⎭ ⎬ ⎫ r = 1 t .
Lemma B.5. Fix r ∈ [ t ] r \in[t] r ∈ [ t ] , and let P P P be any permutation matrix that permutes the coordinates in C r C_r C r and fixes all coordinates outside C r C_r C r . Then
∀ x ∈ R d : F ~ ( P x ) = F ~ ( x ) . \forall x\in\mathbb{R}^d:\widetilde{F}(Px)=\widetilde{F}(x). ∀ x ∈ R d : F ( P x ) = F ( x ) . Proof. Since
Z ~ ℓ = d m ∑ j ∈ C ℓ e j \widetilde{Z}_\ell=\frac{\sqrt{d}}{m}\sum_{j\in C_\ell}e_j Z ℓ = m d j ∈ C ℓ ∑ e j for every ℓ ∈ [ t ] \ell\in[t] ℓ ∈ [ t ] , permuting coordinates inside C r C_r C r leaves every Z ~ ℓ \widetilde{Z}_\ell Z ℓ unchanged:
∀ ℓ ∈ [ t ] : P Z ~ ℓ = Z ~ ℓ . \forall\ell\in[t]:P\widetilde{Z}_\ell=\widetilde{Z}_\ell. ∀ ℓ ∈ [ t ] : P Z ℓ = Z ℓ . Therefore,
F ~ ( P x ) = max v : ∥ v ∥ q = 1 ∣ ⟨ v , P x ⟩ − Med ( { ⟨ v , Z ~ ℓ ⟩ } ℓ = 1 t ) ∣ \widetilde{F}(Px)=\max_{v:\lVert v\rVert_q=1}\left|\langle v,Px\rangle-\operatorname{Med}\left(\left\{\langle v,\widetilde{Z}_\ell\rangle\right\}_{\ell=1}^{t}\right)\right| F ( P x ) = v : ∥ v ∥ q = 1 max ⟨ v , P x ⟩ − Med ( { ⟨ v , Z ℓ ⟩ } ℓ = 1 t ) = max v : ∥ v ∥ q = 1 ∣ ⟨ P T v , x ⟩ − Med ( { ⟨ P T v , Z ~ ℓ ⟩ } ℓ = 1 t ) ∣ . =\max_{v:\lVert v\rVert_q=1}\left|\langle P^{\mathsf T}v,x\rangle-\operatorname{Med}\left(\left\{\langle P^{\mathsf T}v,\widetilde{Z}_\ell\rangle\right\}_{\ell=1}^{t}\right)\right|. = v : ∥ v ∥ q = 1 max ⟨ P T v , x ⟩ − Med ( { ⟨ P T v , Z ℓ ⟩ } ℓ = 1 t ) . Since P P P is a permutation matrix, ∥ P T v ∥ q = ∥ v ∥ q \lVert P^{\mathsf T}v\rVert_q=\lVert v\rVert_q ∥ P T v ∥ q = ∥ v ∥ q . Hence, after the change of variables u = P T v u=P^{\mathsf T}v u = P T v ,
F ~ ( P x ) = max u : ∥ u ∥ q = 1 ∣ ⟨ u , x ⟩ − Med ( { ⟨ u , Z ~ ℓ ⟩ } ℓ = 1 t ) ∣ = F ~ ( x ) . \widetilde{F}(Px)=\max_{u:\lVert u\rVert_q=1}\left|\langle u,x\rangle-\operatorname{Med}\left(\left\{\langle u,\widetilde{Z}_\ell\rangle\right\}_{\ell=1}^{t}\right)\right|=\widetilde{F}(x). F ( P x ) = u : ∥ u ∥ q = 1 max ⟨ u , x ⟩ − Med ( { ⟨ u , Z ℓ ⟩ } ℓ = 1 t ) = F ( x ) .
Corollary B.6. There exists a minimizer x ⋆ x^\star x ⋆ of F ~ \widetilde{F} F such that for every r ∈ [ t ] r\in[t] r ∈ [ t ] , all coordinates of x ⋆ x^\star x ⋆ in C r C_r C r are equal.
Proof. Let G i n \mathcal{G}_{\mathrm{in}} G in denote the finite group of permutation matrices that permute coordinates inside each C r C_r C r and fix all coordinates outside ⋃ r = 1 t C r \bigcup_{r=1}^t C_r ⋃ r = 1 t C r . For any minimizer x x x of F ~ \widetilde{F} F , define its symmetrization
x ˉ : = 1 ∣ G i n ∣ ∑ P ∈ G i n P x \bar{x}:=\frac{1}{|\mathcal{G}_{\mathrm{in}}|}\sum_{P\in\mathcal{G}_{\mathrm{in}}}Px x ˉ := ∣ G in ∣ 1 P ∈ G in ∑ P x
By convexity of F ~ \widetilde{F} F from Observation B.3 and Lemma B.5 ,
F ~ ( x ˉ ) ≤ 1 ∣ G i n ∣ ∑ P ∈ G i n F ~ ( P x ) = 1 ∣ G i n ∣ ∑ P ∈ G i n F ~ ( x ) = F ~ ( x ) . \widetilde{F}(\bar{x}) \le\frac{1}{|\mathcal{G}_{\mathrm{in}}|}\sum_{P\in\mathcal{G}_{\mathrm{in}}}\widetilde{F}(P x)=\frac{1}{|\mathcal{G}_{\mathrm{in}}|}\sum_{P\in\mathcal{G}_{\mathrm{in}}}\widetilde{F}(x)=\widetilde{F}(x). F ( x ˉ ) ≤ ∣ G in ∣ 1 P ∈ G in ∑ F ( P x ) = ∣ G in ∣ 1 P ∈ G in ∑ F ( x ) = F ( x ) .
Since x x x is already a minimizer, x ˉ \bar{x} x ˉ is also a minimizer.
By construction, x ˉ \bar{x} x ˉ is invariant under every permutation inside each C r C_r C r . Hence,
∀ r ∈ [ t ] , ∀ i , j ∈ C r : x ˉ i = x ˉ j . \forall r\in[t],\ \forall i,j\in C_r:\bar{x}_i=\bar{x}_j. ∀ r ∈ [ t ] , ∀ i , j ∈ C r : x ˉ i = x ˉ j .
Lemma B.7. Let σ \sigma σ be any permutation of [ t ] [t] [ t ] . For each r ∈ [ t ] r\in[t] r ∈ [ t ] , choose any bijection
ϕ r : C r → C σ ( r ) . \phi_r:C_r\to C_{\sigma(r)}. ϕ r : C r → C σ ( r ) . Let P σ , ϕ P_{\sigma,\phi} P σ , ϕ be the permutation matrix that sends each coordinate j ∈ C r j\in C_r j ∈ C r to ϕ r ( j ) \phi_r(j) ϕ r ( j ) , and fixes all coordinates outside ⋃ r = 1 t C r \bigcup_{r=1}^t C_r ⋃ r = 1 t C r . Then
∀ x ∈ R d : F ~ ( P σ , ϕ x ) = F ~ ( x ) . \forall x\in\mathbb{R}^d:\widetilde{F}(P_{\sigma,\phi}x)=\widetilde{F}(x). ∀ x ∈ R d : F ( P σ , ϕ x ) = F ( x ) .
Proof. By construction,
P σ , ϕ Z ~ r = d m ∑ j ∈ C r P σ , ϕ e j = d m ∑ k ∈ C σ ( r ) e k = Z ~ σ ( r ) . P_{\sigma,\phi}\widetilde{Z}_r=\frac{\sqrt{d}}{m}\sum_{j\in C_r}P_{\sigma,\phi}e_j=\frac{\sqrt{d}}{m}\sum_{k\in C_{\sigma(r)}}e_k=\widetilde{Z}_{\sigma(r)}. P σ , ϕ Z r = m d j ∈ C r ∑ P σ , ϕ e j = m d k ∈ C σ ( r ) ∑ e k = Z σ ( r ) .
Therefore,
F ~ ( P σ , ϕ x ) = max v : ∥ v ∥ q = 1 ∣ ⟨ v , P σ , ϕ x ⟩ − Med ( { ⟨ v , Z ~ r ⟩ } r = 1 t ) ∣ = max v : ∥ v ∥ q = 1 ∣ ⟨ P σ , ϕ T v , x ⟩ − Med ( { ⟨ P σ , ϕ T v , Z ~ σ ( r ) ⟩ } r = 1 t ) ∣ . \begin{aligned}
\widetilde{F}(P_{\sigma,\phi}x)=\max_{v:\lVert v\rVert_q=1}\left|\langle v,P_{\sigma,\phi}x\rangle-\operatorname{Med}\left(\left\{\langle v,\widetilde{Z}_r\rangle\right\}_{r=1}^t\right)\right| \\
&=\max_{v:\lVert v\rVert_q=1}\left|\langle P_{\sigma,\phi}^{\mathsf{T}}v,x\rangle-\operatorname{Med}\left(\left\{\langle P_{\sigma,\phi}^{\mathsf{T}}v,\widetilde{Z}_{\sigma(r)}\rangle\right\}_{r=1}^t\right)\right|.
\end{aligned} F ( P σ , ϕ x ) = v : ∥ v ∥ q = 1 max ⟨ v , P σ , ϕ x ⟩ − Med ( { ⟨ v , Z r ⟩ } r = 1 t ) = v : ∥ v ∥ q = 1 max ⟨ P σ , ϕ T v , x ⟩ − Med ( { ⟨ P σ , ϕ T v , Z σ ( r ) ⟩ } r = 1 t ) .
Since σ \sigma σ only reorders the multiset of bucket projections, the median is unchanged:
Med ( { ⟨ P σ , ϕ T v , Z ~ σ ( r ) ⟩ } r = 1 t ) = Med ( { ⟨ P σ , ϕ T v , Z ~ r ⟩ } r = 1 t ) . \operatorname{Med}\left(\left\{\langle P_{\sigma,\phi}^{\mathsf{T}}v,\widetilde{Z}_{\sigma(r)}\rangle\right\}_{r=1}^t\right)=\operatorname{Med}\left(\left\{\langle P_{\sigma,\phi}^{\mathsf{T}}v,\widetilde{Z}_r\rangle\right\}_{r=1}^t\right). Med ( { ⟨ P σ , ϕ T v , Z σ ( r ) ⟩ } r = 1 t ) = Med ( { ⟨ P σ , ϕ T v , Z r ⟩ } r = 1 t ) .
Since P σ , ϕ P_{\sigma,\phi} P σ , ϕ is a permutation matrix ∥ P σ , ϕ T v ∥ q = ∥ v ∥ q \lVert P_{\sigma,\phi}^{\mathsf{T}}v\rVert_q=\lVert v\rVert_q ∥ P σ , ϕ T v ∥ q = ∥ v ∥ q . Hence, after the change of variables u = P σ , ϕ T v u=P_{\sigma,\phi}^{\mathsf{T}}v u = P σ , ϕ T v ,
F ~ ( P σ , ϕ x ) = max u : ∥ u ∥ q = 1 ∣ ⟨ u , x ⟩ − Med ( { ⟨ u , Z ~ r ⟩ } r = 1 t ) ∣ = F ~ ( x ) . \widetilde{F}(P_{\sigma,\phi}x)=\max_{u:\lVert u\rVert_q=1}\left|\langle u,x\rangle-\operatorname{Med}\left(\left\{\langle u,\widetilde{Z}_r\rangle\right\}_{r=1}^t\right)\right|=\widetilde{F}(x). F ( P σ , ϕ x ) = u : ∥ u ∥ q = 1 max ⟨ u , x ⟩ − Med ( { ⟨ u , Z r ⟩ } r = 1 t ) = F ( x ) .
Corollary B.8. There exists a minimizer x ⋆ x^\star x ⋆ of F ~ \widetilde{F} F and a scalar a ∈ R a\in\mathbb{R} a ∈ R such that
∀ j ∈ ⋃ r = 1 t C r : x j ⋆ = a . \forall j\in\bigcup_{r=1}^t C_r:x^\star_j=a. ∀ j ∈ r = 1 ⋃ t C r : x j ⋆ = a .
Proof. Start from the minimizer given by Theorem B.6, so that
∀ r ∈ [ t ] , ∀ j ∈ C r : x j = a r \forall r \in[t],\ \forall j \in C_r : x_j = a_r ∀ r ∈ [ t ] , ∀ j ∈ C r : x j = a r
for some scalars a 1 , … , a t a_1,\ldots,a_t a 1 , … , a t .
Let G b u c k \mathcal{G}_{\mathrm{buck}} G buck denote the finite set of all permutations P σ , ϕ P_{\sigma,\phi} P σ , ϕ from Lemma B.7 . Define
x ˉ : = 1 ∣ G b u c k ∣ ∑ P ∈ G b u c k P x . \bar{x} := \frac{1}{|\mathcal{G}_{\mathrm{buck}}|}\sum_{P \in\mathcal{G}_{\mathrm{buck}}} Px. x ˉ := ∣ G buck ∣ 1 P ∈ G buck ∑ P x .
By convexity of F ~ \widetilde{F} F from Observation B.3 and Lemma B.7 ,
F ~ ( x ˉ ) ≤ 1 ∣ G b u c k ∣ ∑ P ∈ G b u c k F ~ ( P x ) = F ~ ( x ) . \widetilde{F}(\bar{x}) \leq\frac{1}{|\mathcal{G}_{\mathrm{buck}}|}\sum_{P \in\mathcal{G}_{\mathrm{buck}}}\widetilde{F}(Px) = \widetilde{F}(x). F ( x ˉ ) ≤ ∣ G buck ∣ 1 P ∈ G buck ∑ F ( P x ) = F ( x ) .
Hence x ˉ \bar{x} x ˉ is also a minimizer.
The group G b u c k \mathcal{G}_{\mathrm{buck}} G buck acts transitively on the active coordinates ⋃ r = 1 t C r \bigcup_{r=1}^{t} C_r ⋃ r = 1 t C r : any active coordinate can be mapped to any other active coordinate by first permuting buckets and then using a bijection inside the target bucket. Therefore, x ˉ \bar{x} x ˉ must take the same value on all active coordinates, i.e.,
∃ a ∈ R such that ∀ j ∈ ⋃ r = 1 t C r : x ˉ j = a . \exists a \in\mathbb{R}\ \text{such that}\ \forall j \in\bigcup_{r=1}^{t} C_r : \bar{x}_j = a. ∃ a ∈ R such that ∀ j ∈ r = 1 ⋃ t C r : x ˉ j = a .
Lemma B.9. There exists a minimizer x ⋆ x^\star x ⋆ of F ~ \widetilde{F} F such that
∀ j ∉ ⋃ r = 1 t C r : x j ⋆ = 0. \forall j \notin\bigcup_{r=1}^{t} C_r : x_j^\star= 0. ∀ j ∈ / r = 1 ⋃ t C r : x j ⋆ = 0.
Consequently, there exists a minimizer of the form
x ⋆ = a ∑ r = 1 t ∑ j ∈ C r e j x^\star= a \sum_{r=1}^{t}\sum_{j \in C_r} e_j x ⋆ = a r = 1 ∑ t j ∈ C r ∑ e j
for some scalar a ∈ R a \in\mathbb{R} a ∈ R .
Proof. Fix j ∉ ⋃ r = 1 t C r j \notin\bigcup_{r=1}^{t} C_r j ∈ / ⋃ r = 1 t C r , and let D j D_j D j be the diagonal matrix defined by
( D j ) k , k = { − 1 if k = j , 1 otherwise . (D_j)_{k,k} =
\begin{cases}
-1 & \text{if } k=j,\\
1 & \text{otherwise}.
\end{cases} ( D j ) k , k = { − 1 1 if k = j , otherwise .
Since every Z ~ r \widetilde{Z}_r Z r is supported on C r C_r C r , we have
∀ r ∈ [ t ] : D j Z ~ r = Z ~ r . \forall r \in[t] : D_j\widetilde{Z}_r = \widetilde{Z}_r. ∀ r ∈ [ t ] : D j Z r = Z r .
Hence, arguing exactly as in Lemma B.5 ,
∀ x ∈ R d : F ~ ( D j x ) = F ~ ( x ) . \forall x \in\mathbb{R}^d : \widetilde{F}(D_jx) = \widetilde{F}(x). ∀ x ∈ R d : F ( D j x ) = F ( x ) .
Let x x x be any minimizer of F ~ \widetilde{F} F , and define
x ˉ : = x + D j x 2 . \bar{x} := \frac{x + D_jx}{2}. x ˉ := 2 x + D j x .
By convexity of F ~ \widetilde{F} F from Observation B.3,
F ~ ( x ˉ ) ≤ F ~ ( x ) + F ~ ( D j x ) 2 = F ~ ( x ) . \widetilde{F}(\bar{x}) \le\frac{\widetilde{F}(x) + \widetilde{F}(D_jx)}{2} = \widetilde{F}(x). F ( x ˉ ) ≤ 2 F ( x ) + F ( D j x ) = F ( x ) .
Thus x ˉ \bar{x} x ˉ is also a minimizer. Moreover, x ˉ \bar{x} x ˉ agrees with x x x on every coordinate except j j j , and
x ˉ j = 0. \bar{x}_j = 0. x ˉ j = 0.
Repeating this argument for every j ∉ ⋃ r = 1 t C r j \notin\bigcup_{r=1}^{t} C_r j ∈ / ⋃ r = 1 t C r yields a minimizer supported on ⋃ r = 1 t C r \bigcup_{r=1}^{t} C_r ⋃ r = 1 t C r . Combining this with Theorem B.8 proves that there exists a minimizer of the form
x ∗ = a ∑ r = 1 t ∑ j ∈ C r e j = a ∑ i = 1 n e c ( i ) . x^* = a \sum_{r=1}^{t} \sum_{j \in C_r} e_j = a \sum_{i=1}^{n} e_{c(i)}. x ∗ = a r = 1 ∑ t j ∈ C r ∑ e j = a i = 1 ∑ n e c ( i ) .
At this point, by Lemma B.9, it remains only to optimize over the scalar multiplying the active coordinates. Define
ρ : = ⌊ t 2 ⌋ + 1 , η : = t − ρ . \rho:= \left\lfloor\frac{t}{2} \right\rfloor+ 1,\qquad\eta:= t-\rho. ρ := ⌊ 2 t ⌋ + 1 , η := t − ρ .
Let y ( 1 ) ≥ ⋯ ≥ y ( t ) y_{(1)} \ge\cdots\ge y_{(t)} y ( 1 ) ≥ ⋯ ≥ y ( t ) denote the non-increasing rearrangement of a multiset of scalars Y = { y i } i = 1 t \mathbf{Y} = \{y_i\}_{i=1}^{t} Y = { y i } i = 1 t . We use the convention
Med ( Y ) = { y ( k ) if t = 2 k − 1 , y ( k ) + y ( k + 1 ) 2 if t = 2 k . \operatorname{Med}(\mathbf{Y}) =
\begin{cases}
y_{(k)} & \text{if } t=2k-1,\\
\frac{y_{(k)}+y_{(k+1)}}{2} & \text{if } t=2k.
\end{cases} Med ( Y ) = { y ( k ) 2 y ( k ) + y ( k + 1 ) if t = 2 k − 1 , if t = 2 k .
For a ∈ R a \in\mathbb{R} a ∈ R , define
x ( a ) : = a ∑ i = 1 n e c ( i ) = a ∑ r = 1 t ∑ j ∈ C r e j . x^{(a)} := a \sum_{i=1}^{n} e_{c(i)} = a \sum_{r=1}^{t} \sum_{j \in C_r} e_j. x ( a ) := a i = 1 ∑ n e c ( i ) = a r = 1 ∑ t j ∈ C r ∑ e j .
Lemma B.10. For every a ∈ R a \in\mathbb{R} a ∈ R ,
F ~ ( x ( a ) ) = m 1 / p max u ∈ R t : ∥ u ∥ q ≤ 1 ∣ a ∑ r = 1 t u r − d m Med ( { u r } r = 1 t ) ∣ . \widetilde{F}(x^{(a)}) = m^{1/p} \max_{u \in\mathbb{R}^{t}:\lVert u\rVert_q \le1} \left| a \sum_{r=1}^{t} u_r - \frac{\sqrt{d}}{m}\operatorname{Med}\left(\{u_r\}_{r=1}^{t}\right) \right|. F ( x ( a ) ) = m 1/ p u ∈ R t : ∥ u ∥ q ≤ 1 max a r = 1 ∑ t u r − m d Med ( { u r } r = 1 t ) .
Proof. For v ∈ R d v \in\mathbb{R}^{d} v ∈ R d , define
u r : = m − 1 / p ∑ j ∈ C r v j , r ∈ [ t ] . u_r := m^{-1/p} \sum_{j \in C_r} v_j,\qquad r \in[t]. u r := m − 1/ p j ∈ C r ∑ v j , r ∈ [ t ] .
By Hölder,
∣ u r ∣ = m − 1 / p ∣ ∑ j ∈ C r v j ∣ ≤ ∥ v C r ∥ q . |u_r| = m^{-1/p}\left|\sum_{j \in C_r} v_j\right| \le\lVert v_{C_r}\rVert_q. ∣ u r ∣ = m − 1/ p j ∈ C r ∑ v j ≤ ∥ v C r ∥ q .
Hence,
∑ r = 1 t ∣ u r ∣ q ≤ ∑ r = 1 t ∥ v C r ∥ q q ≤ ∥ v ∥ q q . \sum_{r=1}^{t} |u_r|^q \le\sum_{r=1}^{t} \|v_{C_r}\|_q^q \le\|v\|_q^q. r = 1 ∑ t ∣ u r ∣ q ≤ r = 1 ∑ t ∥ v C r ∥ q q ≤ ∥ v ∥ q q .
In particular, every v v v with ∥ v ∥ q ≤ 1 \|v\|_q \le1 ∥ v ∥ q ≤ 1 produces a vector u u u with ∥ u ∥ q ≤ 1 \|u\|_q \le1 ∥ u ∥ q ≤ 1 . Moreover,
∑ j ∈ C r v j = m 1 / p u r for all r ∈ [ t ] . \sum_{j\in C_r} v_j = m^{1/p}u_r \qquad\text{for all } r\in[t]. j ∈ C r ∑ v j = m 1/ p u r for all r ∈ [ t ] .
Therefore,
F ~ ( x ( a ) ) = max v : ∥ v ∥ q = 1 ∣ a ∑ r = 1 t ∑ j ∈ C r v j − d m Med ( { ∑ j ∈ C r v j } r = 1 t ) ∣ = m 1 / p max v : ∥ v ∥ q = 1 ∣ a ∑ r = 1 t u r − d m Med ( { u r } r = 1 t ) ∣ ≤ m 1 / p max u : ∥ u ∥ q ≤ 1 ∣ a ∑ r = 1 t u r − d m Med ( { u r } r = 1 t ) ∣ . \begin{aligned}
\widetilde{F}(x^{(a)}) &= \max_{v:\|v\|_q=1}\left|a\sum_{r=1}^{t}\sum_{j\in C_r}v_j-\frac{\sqrt{d}}{m}\operatorname{Med}\left(\left\{\sum_{j\in C_r}v_j\right\}_{r=1}^{t}\right)\right| \\
&=m^{1/p}\max_{v:\|v\|_q=1}\left|a\sum_{r=1}^{t}u_r-\frac{\sqrt{d}}{m}\operatorname{Med}\left(\{u_r\}_{r=1}^{t}\right)\right| \\
&\le m^{1/p}\max_{u:\|u\|_q\le1}\left|a\sum_{r=1}^{t}u_r-\frac{\sqrt{d}}{m}\operatorname{Med}\left(\{u_r\}_{r=1}^{t}\right)\right|.
\end{aligned} F ( x ( a ) ) = v : ∥ v ∥ q = 1 max a r = 1 ∑ t j ∈ C r ∑ v j − m d Med ⎩ ⎨ ⎧ j ∈ C r ∑ v j ⎭ ⎬ ⎫ r = 1 t = m 1/ p v : ∥ v ∥ q = 1 max a r = 1 ∑ t u r − m d Med ( { u r } r = 1 t ) ≤ m 1/ p u : ∥ u ∥ q ≤ 1 max a r = 1 ∑ t u r − m d Med ( { u r } r = 1 t ) .
For the reverse inequality, fix any u ∈ R t u\in\mathbb{R}^t u ∈ R t with ∥ u ∥ q ≤ 1 \|u\|_q\le1 ∥ u ∥ q ≤ 1 , and define v ∈ R d v\in\mathbb{R}^d v ∈ R d by setting
∀ r ∈ [ t ] , ∀ j ∈ C r : v j : = m − 1 + 1 / p u r , \forall r\in[t],\ \forall j\in C_r : v_j:=m^{-1+1/p}u_r, ∀ r ∈ [ t ] , ∀ j ∈ C r : v j := m − 1 + 1/ p u r ,
and v j : = 0 v_j:=0 v j := 0 outside ⋃ r = 1 t C r \bigcup_{r=1}^{t}C_r ⋃ r = 1 t C r . Then
∑ j ∈ C r v j = m 1 / p u r for all r ∈ [ t ] , \sum_{j\in C_r}v_j=m^{1/p}u_r \qquad\text{for all } r\in[t], j ∈ C r ∑ v j = m 1/ p u r for all r ∈ [ t ] ,
and
∥ v ∥ q q = ∑ r = 1 t ∑ j ∈ C r m − q + q / p ∣ u r ∣ q = ∑ r = 1 t m ( 1 − q ) + q / p ∣ u r ∣ q = ∑ r = 1 t ∣ u r ∣ q = ∥ u ∥ q q ≤ 1 , \|v\|_q^q=\sum_{r=1}^{t}\sum_{j\in C_r}m^{-q+q/p}|u_r|^q=\sum_{r=1}^{t}m^{(1-q)+q/p}|u_r|^q=\sum_{r=1}^{t}|u_r|^q=\|u\|_q^q\le1, ∥ v ∥ q q = r = 1 ∑ t j ∈ C r ∑ m − q + q / p ∣ u r ∣ q = r = 1 ∑ t m ( 1 − q ) + q / p ∣ u r ∣ q = r = 1 ∑ t ∣ u r ∣ q = ∥ u ∥ q q ≤ 1 ,
since ( 1 − q ) = − q / p (1-q)=-q/p ( 1 − q ) = − q / p as 1 / p + 1 / q = 1 1/p+1/q=1 1/ p + 1/ q = 1 . Plugging v v v into the definition of F ~ \widetilde{F} F now yields the reverse inequality, concluding the proof of the lemma. □ \square □
Lemma B.11. For every a ∈ R a\in\mathbb{R} a ∈ R ,
F ~ ( x ( a ) ) = m 1 / p ( ρ ∣ d ρ m − a ∣ p + η ∣ a ∣ p ) 1 / p . \widetilde{F}(x^{(a)})=m^{1/p}\left(\rho\left|\frac{\sqrt{d}}{\rho m}-a\right|^p+\eta|a|^p\right)^{1/p}. F ( x ( a ) ) = m 1/ p ( ρ ρ m d − a p + η ∣ a ∣ p ) 1/ p .
Proof. Let
λ : = d m . \lambda:=\frac{\sqrt{d}}{m}. λ := m d .
By Lemma B.10 , it suffices to compute
max ∥ u ∥ q ≤ 1 ∣ a ∑ r = 1 t u r − λ Med ( { u r } r = 1 t ) ∣ . \max_{\|u\|_q\le1}\left|a\sum_{r=1}^{t}u_r-\lambda\operatorname{Med}\left(\{u_r\}_{r=1}^{t}\right)\right|. ∥ u ∥ q ≤ 1 max a r = 1 ∑ t u r − λ Med ( { u r } r = 1 t ) .
Since Med ( − u ) = − Med ( u ) \operatorname{Med}(-u)=-\operatorname{Med}(u) Med ( − u ) = − Med ( u ) , this maximum equals
max ∥ u ∥ q ≤ 1 { λ Med ( { u r } r = 1 t ) − a ∑ r = 1 t u r } . \max_{\lVert u\rVert_q\le1}\left\{\lambda\operatorname{Med}\left(\{u_r\}_{r=1}^{t}\right)-a\sum_{r=1}^{t}u_r\right\}. ∥ u ∥ q ≤ 1 max { λ Med ( { u r } r = 1 t ) − a r = 1 ∑ t u r } .
Let
u ( 1 ) ≥ u ( 2 ) ≥ ⋯ ≥ u ( t ) u_{(1)}\ge u_{(2)}\ge\cdots\ge u_{(t)} u ( 1 ) ≥ u ( 2 ) ≥ ⋯ ≥ u ( t )
be the non-increasing rearrangement of u u u . Now, observe that:
Med ( u ) ≤ 1 ρ ∑ r = 1 ρ u ( r ) . \operatorname{Med}(u)\le\frac{1}{\rho}\sum_{r=1}^{\rho}u_{(r)}. Med ( u ) ≤ ρ 1 r = 1 ∑ ρ u ( r ) .
Therefore,
λ Med ( u ) − a ∑ r = 1 t u r ≤ λ ρ ∑ r = 1 ρ u ( r ) − a ∑ r = 1 t u ( r ) = ( λ ρ − a ) ∑ r = 1 ρ u ( r ) − a ∑ r = ρ + 1 t u ( r ) . \lambda\operatorname{Med}(u)-a\sum_{r=1}^{t}u_r\le\frac{\lambda}{\rho}\sum_{r=1}^{\rho}u_{(r)}-a\sum_{r=1}^{t}u_{(r)}=\left(\frac{\lambda}{\rho}-a\right)\sum_{r=1}^{\rho}u_{(r)}-a\sum_{r=\rho+1}^{t}u_{(r)}. λ Med ( u ) − a r = 1 ∑ t u r ≤ ρ λ r = 1 ∑ ρ u ( r ) − a r = 1 ∑ t u ( r ) = ( ρ λ − a ) r = 1 ∑ ρ u ( r ) − a r = ρ + 1 ∑ t u ( r ) .
By Hölder,
λ Med ( u ) − a ∑ r = 1 t u r ≤ ( ρ ∣ λ ρ − a ∣ p + η ∣ a ∣ p ) 1 / p ∥ u ∥ q . \lambda\operatorname{Med}(u)-a\sum_{r=1}^{t}u_r\le\left(\rho\left|\frac{\lambda}{\rho}-a\right|^p+\eta|a|^p\right)^{1/p}\lVert u\rVert_q. λ Med ( u ) − a r = 1 ∑ t u r ≤ ( ρ ρ λ − a p + η ∣ a ∣ p ) 1/ p ∥ u ∥ q .
Since ∥ u ∥ q ≤ 1 \lVert u\rVert_q\le1 ∥ u ∥ q ≤ 1 , this establishes an upper bound.
For the lower bound, set
A : = λ ρ − a , B : = − a , α : = ( ρ ∣ A ∣ p + η ∣ B ∣ p ) − 1 / q , A:=\frac{\lambda}{\rho}-a,\qquad B:=-a,\qquad\alpha:=\left(\rho|A|^p+\eta|B|^p\right)^{-1/q}, A := ρ λ − a , B := − a , α := ( ρ ∣ A ∣ p + η ∣ B ∣ p ) − 1/ q ,
and J ( z ) : = sgn ( z ) ∣ z ∣ p − 1 J(z):=\operatorname{sgn}(z)|z|^{p-1} J ( z ) := sgn ( z ) ∣ z ∣ p − 1 .
Now, define u ∈ R t u\in\mathbb{R}^t u ∈ R t by
u 1 = ⋯ = u ρ = α J ( A ) , u ρ + 1 = ⋯ = u t = α J ( B ) . u_1=\cdots=u_\rho=\alpha J(A),\qquad u_{\rho+1}=\cdots=u_t=\alpha J(B). u 1 = ⋯ = u ρ = α J ( A ) , u ρ + 1 = ⋯ = u t = α J ( B ) .
Since A − B > 0 A-B>0 A − B > 0 , and J J J is increasing, this vector is non-increasing. Also, observe
∥ u ∥ q q = α q ( ρ ∣ A ∣ p + η ∣ B ∣ p ) = 1 and Med ( u ) = α J ( A ) . \lVert u\rVert_q^q=\alpha^q\left(\rho|A|^p+\eta|B|^p\right)=1\quad\text{and}\quad\operatorname{Med}(u)=\alpha J(A). ∥ u ∥ q q = α q ( ρ ∣ A ∣ p + η ∣ B ∣ p ) = 1 and Med ( u ) = α J ( A ) .
Hence
λ Med ( u ) − a ∑ r = 1 t u r = λ α J ( A ) − a ( ρ α J ( A ) + η α J ( B ) ) = α ( ρ A J ( A ) + η B J ( B ) ) = α ( ρ ∣ A ∣ p + η ∣ B ∣ p ) = ( ρ ∣ A ∣ p + η ∣ B ∣ p ) 1 / p . \begin{aligned}
\lambda\operatorname{Med}(u)-a\sum_{r=1}^{t}u_r=\lambda\alpha J(A)-a\left(\rho\alpha J(A)+\eta\alpha J(B)\right)=\alpha\left(\rho AJ(A)+\eta BJ(B)\right) \\
&=\alpha\left(\rho|A|^p+\eta|B|^p\right)=\left(\rho|A|^p+\eta|B|^p\right)^{1/p}.
\end{aligned} λ Med ( u ) − a r = 1 ∑ t u r = λ α J ( A ) − a ( ρ α J ( A ) + η α J ( B ) ) = α ( ρ A J ( A ) + η B J ( B ) ) = α ( ρ ∣ A ∣ p + η ∣ B ∣ p ) = ( ρ ∣ A ∣ p + η ∣ B ∣ p ) 1/ p .
matching the upper bound and proving the lemma.
Corollary B.12. The optimal scalar is
a ⋆ = d ρ m 1 1 + ( η / ρ ) 1 / ( p − 1 ) . a^\star=\frac{\sqrt{d}}{\rho m}\frac{1}{1+(\eta/\rho)^{1/(p-1)}}. a ⋆ = ρ m d 1 + ( η / ρ ) 1/ ( p − 1 ) 1 . Consequently, a minimizer of F ~ \widetilde{F} F is
x ⋆ = a ⋆ ∑ i = 1 n e c ( i ) , x^\star=a^\star\sum_{i=1}^{n}e_{c(i)}, x ⋆ = a ⋆ i = 1 ∑ n e c ( i ) ,
and hence, by Observation B.4, a minimizer of F F F is
μ ^ p r o j ( X ) = S x ⋆ = a ⋆ ∑ i = 1 n s i ϵ c ( i ) . \widehat{\mu}_{\mathrm{proj}}(\mathbf{X})=Sx^\star=a^\star\sum_{i=1}^{n}s_i\epsilon_{c(i)}. μ proj ( X ) = S x ⋆ = a ⋆ i = 1 ∑ n s i ϵ c ( i ) .
Proof. Observing that F ~ ( x ( a ) ) \widetilde{F}(x^{(a)}) F ( x ( a ) ) is convex in a a a and computing its derivative, the corollary follows. □
Corollary B.13. The resulting estimator has
∥ μ ^ p r o j ( X ) ∥ p = ∥ x ⋆ ∥ p = a ⋆ n 1 / p ≥ d 2 n 1 − 1 / p . \lVert\widehat{\mu}_{\mathrm{proj}}(\mathbf{X})\rVert_p=\lVert x^\star\rVert_p=a^\star n^{1/p}\geq\frac{\sqrt{d}}{2n^{1-1/p}}. ∥ μ proj ( X ) ∥ p = ∥ x ⋆ ∥ p = a ⋆ n 1/ p ≥ 2 n 1 − 1/ p d .
Proof. Since x ⋆ x^\star x ⋆ has exactly n n n nonzero coordinates, each of magnitude a ⋆ a^\star a ⋆ ,
∥ x ⋆ ∥ p = a ⋆ n 1 / p . \lVert x^\star\rVert_p=a^\star n^{1/p}. ∥ x ⋆ ∥ p = a ⋆ n 1/ p .
The corollary follows from Theorem B.12. □
Proof of Theorem 1.2 . The theorem follows from Theorem B.13 and Lemma B.2 . □
Proof of thm:moml2lbmain
Proof of Theorem 1.4
In this section, we show that Algorithm 1 cannot be optimal for the ℓ 2 \ell_2 ℓ 2 norm. The optimal rate for heavy-tailed mean estimation for isotropic data in this setting is known to be of order
d n + 1 n log ( 1 δ ) . (18) \sqrt{\frac{d}{n}}+\sqrt{\frac{1}{n}\log\left(\frac{1}{\delta}\right)}. \tag*{(18)} n d + n 1 log ( δ 1 ) . (18)
We prove the following lower bound which demonstrates that the coordinate-wise median-of-means strategy is sub-optimal when the failure probability is small.
Theorem 1.4 (Suboptimality of coordinate-wise median-of-means). There are universal constants c , C ≥ 0 c,C\geq0 c , C ≥ 0 such that the following holds. For any δ ∈ ( 0 , c ) \delta\in(0,c) δ ∈ ( 0 , c ) and n , d , t ∈ N n,d,t\in\mathbb{N} n , d , t ∈ N with t ≤ n t\leq n t ≤ n , there exists a distribution P P P over R d \mathbb{R}^d R d with mean 0 0 0 and covariance I d I_d I d such that if Algorithm 1 is ran with t t t buckets and sample X 1 , … , X n ∼ P X_1,\ldots,X_n\sim P X 1 , … , X n ∼ P as input, it returns an estimate μ ^ \widehat{\mu} μ satisfying
Pr X 1 , … , X n ∼ P [ ∥ μ ^ ∥ 2 ≥ C d log ( 1 / δ ) n log log ( 1 / δ ) ] > δ . \underset{X_1,\ldots,X_n\sim P}{\operatorname{Pr}}\left[\lVert\widehat{\mu}\rVert_2\geq C\sqrt{\frac{d\log(1/\delta)}{n\log\log(1/\delta)}}\right]>\delta. X 1 , … , X n ∼ P Pr [ ∥ μ ∥ 2 ≥ C n log log ( 1/ δ ) d log ( 1/ δ ) ] > δ .
This result follows from combining two different lower bounds: the first demonstrates a large error when Algorithm 1 is run with many buckets, while the second shows a large error when it is run with few buckets.
Lemma C.1. There is a universal constants C > 0 C>0 C > 0 such that the following holds. For any δ ∈ ( 0 , 1 / 3 ) \delta\in(0,1/3) δ ∈ ( 0 , 1/3 ) and n , d , t ∈ N n,d,t\in\mathbb{N} n , d , t ∈ N with t ≤ n t\leq n t ≤ n , there exists a distribution P 1 P_1 P 1 over R d \mathbb{R}^d R d with mean 0 0 0 and covariance I d I_d I d such that if Algorithm 1 is given the number of buckets t t t and the sample X 1 , … , X n ∼ P 1 X_1,\ldots,X_n\sim P_1 X 1 , … , X n ∼ P 1 as input, it returns an estimate μ ^ \widehat{\mu} μ satisfying
Pr X 1 , … , X n ∼ P 1 [ ∥ μ ^ ∥ 2 ≥ C d t n ] > δ . \underset{X_1,\ldots,X_n\sim P_1}{\operatorname{Pr}}\left[\lVert\widehat{\mu}\rVert_2\geq C\sqrt{\frac{dt}{n}}\right]>\delta. X 1 , … , X n ∼ P 1 Pr [ ∥ μ ∥ 2 ≥ C n d t ] > δ .
Proof. Set p = 1 − t 8 n p = 1 - \frac{t}{8n} p = 1 − 8 n t and ℓ = 1 p ( 1 − p ) \ell= \frac{1}{\sqrt{p(1-p)}} ℓ = p ( 1 − p ) 1 and define random variable Z ∼ Q Z \sim Q Z ∼ Q by
Pr Z ∼ Q [ Z = ( 1 − p ) ℓ ] = p , Pr Z ∼ Q [ Z = − p ℓ ] = 1 − p . \Pr_{Z\sim Q}[Z = (1-p)\ell] = p,\qquad\Pr_{Z\sim Q}[Z = -p\ell] = 1-p. Z ∼ Q Pr [ Z = ( 1 − p ) ℓ ] = p , Z ∼ Q Pr [ Z = − p ℓ ] = 1 − p .
Notice that E Z ∼ Q [ Z ] = 0 \mathbb{E}_{Z\sim Q}[Z] = 0 E Z ∼ Q [ Z ] = 0 and Z Z Z has variance 1 1 1 . Let P 1 P_1 P 1 be the product distribution on R d \mathbb{R}^d R d whose coordinates are independent copies of Z Z Z . Clearly P 1 P_1 P 1 has mean 0 0 0 and covariance I d I_d I d .
Let X 1 , … , X n X_1,\ldots,X_n X 1 , … , X n be an i.i.d. sample from P 1 P_1 P 1 and run Algorithm 1 using t t t buckets. Denote the bucket sizes by m 1 , … , m t m_1,\ldots,m_t m 1 , … , m t , so that
m j ≤ ⌈ n t ⌉ ≤ n t + 1. m_j \le\left\lceil\frac{n}{t}\right\rceil\le\frac{n}{t}+1. m j ≤ ⌈ t n ⌉ ≤ t n + 1.
Fix a coordinate k ∈ [ d ] k \in[d] k ∈ [ d ] and a bucket j ∈ [ t ] j \in[t] j ∈ [ t ] . The empirical mean of the k k k th coordinate in bucket j j j equals ( 1 − p ) ℓ (1-p)\ell ( 1 − p ) ℓ whenever all samples in that bucket have k k k th coordinate equal to ( 1 − p ) ℓ (1-p)\ell ( 1 − p ) ℓ . This event has probability
p m j = ( 1 − t 8 n ) m j ≥ 1 − m j t 8 n ≥ 1 − ( n t + 1 ) t 8 n ≥ 3 4 , p^{m_j}=\left(1-\frac{t}{8n}\right)^{m_j}\ge1-\frac{m_jt}{8n}\ge1-\left(\frac{n}{t}+1\right)\frac{t}{8n}\ge\frac{3}{4}, p m j = ( 1 − 8 n t ) m j ≥ 1 − 8 n m j t ≥ 1 − ( t n + 1 ) 8 n t ≥ 4 3 ,
where we used the inequality ( 1 + x ) y ≥ 1 + y x (1+x)^y \ge1+yx ( 1 + x ) y ≥ 1 + y x which holds for x ≥ − 1 x \ge-1 x ≥ − 1 and y ≥ 1 y \ge1 y ≥ 1 , and the fact that t ≤ n t \le n t ≤ n . For the fixed coordinate k ∈ [ d ] k \in[d] k ∈ [ d ] , let Y k Y_k Y k be the number of buckets whose coordinate-k k k empirical mean is equal to ( 1 − p ) ℓ (1-p)\ell ( 1 − p ) ℓ . Then Y k Y_k Y k is a sum of independent Bernoulli random variables with
E Y k ≥ 3 t 4 . \mathbb{E}Y_k \ge\frac{3t}{4}. E Y k ≥ 4 3 t .
We can apply Markov’s inequality to the random variable t − Y k t-Y_k t − Y k to get
Pr X 1 , … , X n ∼ P 1 [ Y k > t 2 ] = 1 − Pr X 1 , … , X n ∼ P 1 [ t − Y k ≥ t 2 ] ≥ 1 − t 4 2 t = 1 2 . \Pr_{X_1,\ldots,X_n\sim P_1}\left[Y_k>\frac{t}{2}\right]
=1-\Pr_{X_1,\ldots,X_n\sim P_1}\left[t-Y_k\ge\frac{t}{2}\right]
\ge1-\frac{t}{4}\frac{2}{t}
=\frac{1}{2}. X 1 , … , X n ∼ P 1 Pr [ Y k > 2 t ] = 1 − X 1 , … , X n ∼ P 1 Pr [ t − Y k ≥ 2 t ] ≥ 1 − 4 t t 2 = 2 1 .
On the event { Y k > t / 2 } \{Y_k>t/2\} { Y k > t /2 } , strictly more than half of the bucket means in coordinate k k k are equal to ( 1 − p ) ℓ (1-p)\ell ( 1 − p ) ℓ , and therefore the coordinate-wise median M k M_k M k is ( 1 − p ) ℓ (1-p)\ell ( 1 − p ) ℓ . Now define
W = ∑ k = 1 d 1 { M k = ( 1 − p ) ℓ } . W=\sum_{k=1}^{d}\mathbf{1}\{M_k=(1-p)\ell\}. W = k = 1 ∑ d 1 { M k = ( 1 − p ) ℓ } .
Since the coordinates of P 1 P_1 P 1 are independent, the events { M k = ( 1 − p ) ℓ } \{M_k=(1-p)\ell\} { M k = ( 1 − p ) ℓ } are independent over k ∈ [ d ] k \in[d] k ∈ [ d ] . Moreover since,
E W ≥ d 2 , \mathbb{E}W\ge\frac{d}{2}, E W ≥ 2 d ,
we can invoke Markov’s inequality on the random variable d − W d-W d − W to conclude that
Pr X 1 , … , X n ∼ P 1 [ W ≥ d 4 ] = 1 − Pr X 1 , … , X n ∼ P 1 [ d − W ≥ 3 d 4 ] ≥ 1 − d / 2 3 d / 4 = 1 3 . \Pr_{X_1,\ldots,X_n\sim P_1}\left[W\ge\frac{d}{4}\right]
=1-\Pr_{X_1,\ldots,X_n\sim P_1}\left[d-W\ge\frac{3d}{4}\right]
\ge1-\frac{d/2}{3d/4}
=\frac{1}{3}. X 1 , … , X n ∼ P 1 Pr [ W ≥ 4 d ] = 1 − X 1 , … , X n ∼ P 1 Pr [ d − W ≥ 4 3 d ] ≥ 1 − 3 d /4 d /2 = 3 1 .
On this event, we have that
∥ μ ^ ∥ 2 ≥ d 4 ( 1 − p ) ℓ = d t 4 ( 8 n − t ) ≥ C d t n . \|\hat{\mu}\|_2\ge\sqrt{\frac{d}{4}}(1-p)\ell
=\sqrt{\frac{dt}{4(8n-t)}}\ge C\sqrt{\frac{dt}{n}}. ∥ μ ^ ∥ 2 ≥ 4 d ( 1 − p ) ℓ = 4 ( 8 n − t ) d t ≥ C n d t .
for some universal constant C > 0 C>0 C > 0 , where we have used the assumption t ≤ n t\le n t ≤ n . By setting c = 1 3 c=\frac{1}{3} c = 3 1 it holds for every δ ∈ ( 0 , c ) \delta\in(0,c) δ ∈ ( 0 , c ) that
Pr X 1 , … , X n ∼ P 1 [ ∥ μ ^ ∥ 2 ≥ C d t n ] > δ . \Pr_{X_1,\ldots,X_n\sim P_1}\left[\lVert\hat{\mu}\rVert_2\ge C\sqrt{\frac{dt}{n}}\right]>\delta. X 1 , … , X n ∼ P 1 Pr [ ∥ μ ^ ∥ 2 ≥ C n d t ] > δ .
as claimed. This completes the proof.
Lemma C.2. There exist universal constants c 1 , c 2 c_1,c_2 c 1 , c 2 such that the following holds. Let n , d , t ∈ N n,d,t\in\mathbb{N} n , d , t ∈ N with t ≤ n t\le n t ≤ n , and δ ∈ ( 0 , c 1 ) \delta\in(0,c_1) δ ∈ ( 0 , c 1 ) satisfying
t ≤ log ( 1 / δ ) log log ( 1 / δ ) . t\le\frac{\log(1/\delta)}{\log\log(1/\delta)}. t ≤ log log ( 1/ δ ) log ( 1/ δ ) . There exists a distribution P P P over R d \mathbb{R}^d R d satisfying E P X = 0 \mathbb{E}_P X=0 E P X = 0 and Cov P ( X ) = I d \operatorname{Cov}_P(X)=I_d Cov P ( X ) = I d , such that the following holds. If Algorithm 1 is run with t t t buckets on X 1 , … , X n ∼ P X_1,\ldots,X_n\sim P X 1 , … , X n ∼ P , its output μ ^ \hat{\mu} μ ^ satisfies
Pr X 1 , … , X n ∼ P [ ∥ μ ^ ∥ 2 ≥ c 2 t d log ( 1 / δ ) n ] > δ . \Pr_{X_1,\ldots,X_n\sim P}\left[\lVert\hat{\mu}\rVert_2\ge c_2\sqrt{\frac{td\log(1/\delta)}{n}}\right]>\delta. X 1 , … , X n ∼ P Pr [ ∥ μ ^ ∥ 2 ≥ c 2 n t d log ( 1/ δ ) ] > δ .
Proof. Our hard distribution will be of the form
X = R ε , ε = ( ε 1 , … , ε d ) , X=R\varepsilon,\qquad\varepsilon=(\varepsilon_1,\ldots,\varepsilon_d), X = R ε , ε = ( ε 1 , … , ε d ) ,
where ε 1 , … , ε d \varepsilon_1,\ldots,\varepsilon_d ε 1 , … , ε d are independent Rademacher random variables and R R R is an independent scalar random variable to be specified subsequently. Now, let
L = log ( 1 / δ ) , m = ⌈ n t ⌉ , a = L 8 ε 2 . L=\log(1/\delta),\qquad m=\left\lceil\frac{n}{t}\right\rceil,\qquad a=\frac{L}{8\varepsilon^2}. L = log ( 1/ δ ) , m = ⌈ t n ⌉ , a = 8 ε 2 L .
Note that a ≥ 2 a\ge2 a ≥ 2 for sufficiently small c 1 c_1 c 1 . Now, define R R R as follows
Pr [ R = m a ] = 1 m a , Pr [ R = 0 ] = 1 − 1 m a , \Pr[R=\sqrt{ma}]=\frac{1}{ma},\qquad\Pr[R=0]=1-\frac{1}{ma}, Pr [ R = ma ] = ma 1 , Pr [ R = 0 ] = 1 − ma 1 ,
and let X = R ε X=R\varepsilon X = R ε . Then, observe that
E X = 0 , Cov ( X ) = E [ R 2 ] E [ ε ε ⊤ ] = m a ⋅ 1 m a I d = I d . \mathbb{E}X=0,\qquad\operatorname{Cov}(X)=\mathbb{E}[R^2]\mathbb{E}[\varepsilon\varepsilon^\top]=ma\cdot\frac{1}{ma}I_d=I_d. E X = 0 , Cov ( X ) = E [ R 2 ] E [ ε ε ⊤ ] = ma ⋅ ma 1 I d = I d .
Let m 1 , … , m t m_1,\ldots,m_t m 1 , … , m t be the bucket sizes produced by Algorithm 1. Since t ≤ n t\le n t ≤ n ,
m i ∈ { ⌊ n t ⌋ , ⌈ n t ⌉ } , m i ≥ m 2 . m_i\in\left\{\left\lfloor\frac{n}{t}\right\rfloor,\left\lceil\frac{n}{t}\right\rceil\right\},\qquad m_i\ge\frac{m}{2}. m i ∈ { ⌊ t n ⌋ , ⌈ t n ⌉ } , m i ≥ 2 m .
For bucket i i i , let E i E_i E i be the event that exactly one sample in the bucket has nonzero multiplier R R R . Then
Pr [ E i ] = m i ⋅ 1 m a ⋅ ( 1 − 1 m a ) m i − 1 ≥ 1 8 a . \Pr[E_i]=m_i\cdot\frac{1}{ma}\cdot\left(1-\frac{1}{ma}\right)^{m_i-1}\ge\frac{1}{8a}. Pr [ E i ] = m i ⋅ ma 1 ⋅ ( 1 − ma 1 ) m i − 1 ≥ 8 a 1 .
Observing that E 1 , … , E t E_1,\ldots,E_t E 1 , … , E t are independent, we get for E = ⋂ i = 1 t E i E=\bigcap_{i=1}^{t}E_i E = ⋂ i = 1 t E i ,
Pr [ E ] ≥ ( 1 8 a ) t . (19) \Pr[E]\ge\left(\frac{1}{8a}\right)^t. \tag*{(19)} Pr [ E ] ≥ ( 8 a 1 ) t . (19)
We condition on E E E for the remainder of the proof. Note that each bucket contains exactly one nonzero sample, and the corresponding Rademacher vectors remain independent. Hence the i i i th bucket mean is distributed as
μ ^ ( i ) = m a m i ϵ ( i ) = s i ϵ ( i ) , i = 1 , … , t , \widehat{\mu}^{(i)} = \frac{\sqrt{ma}}{m_i}\epsilon^{(i)} = s_i\epsilon^{(i)}, \qquad i=1,\ldots,t, μ ( i ) = m i ma ϵ ( i ) = s i ϵ ( i ) , i = 1 , … , t ,
where ϵ ( 1 ) , … , ϵ ( t ) \epsilon^{(1)},\ldots,\epsilon^{(t)} ϵ ( 1 ) , … , ϵ ( t ) are independent copies of ϵ \epsilon ϵ and
s i ≥ s 0 : = a m . s_i \ge s_0 := \sqrt{\frac{a}{m}}. s i ≥ s 0 := m a .
Thus, conditioned on E E E ,
μ ^ j = Median ( s 1 ϵ j ( 1 ) , … , s t ϵ j ( t ) ) , j ∈ [ d ] . \widehat{\mu}_j = \operatorname{Median}\left(s_1\epsilon_j^{(1)},\ldots,s_t\epsilon_j^{(t)}\right), \qquad j \in[d]. μ j = Median ( s 1 ϵ j ( 1 ) , … , s t ϵ j ( t ) ) , j ∈ [ d ] .
We use the following elementary fact.
Claim C.3. For every s i ≥ s 0 s_i \ge s_0 s i ≥ s 0 ,
Pr [ ∣ Median ( s 1 ϵ 1 , … , s t ϵ t ) ∣ ≥ s 0 ] ≥ 1 / 2 , \Pr\left[\left|\operatorname{Median}(s_1\epsilon_1,\ldots,s_t\epsilon_t)\right| \ge s_0\right] \ge1/2, Pr [ ∣ Median ( s 1 ϵ 1 , … , s t ϵ t ) ∣ ≥ s 0 ] ≥ 1/2 , where ϵ 1 , … , ϵ t \epsilon_1,\ldots,\epsilon_t ϵ 1 , … , ϵ t are independent Rademacher random variables.
Proof. If t t t is odd, one of the two signs appears strictly more than t / 2 t/2 t /2 times. The median then has that sign and absolute value at least s 0 s_0 s 0 . If t t t is even, the same conclusion holds unless exactly half of the signs are positive and half are negative. Therefore if B ∼ Binom ( t , 1 / 2 ) B \sim\operatorname{Binom}(t,1/2) B ∼ Binom ( t , 1/2 ) , then
Pr [ ∣ Median ( s 1 ϵ 1 , … , s t ϵ t ) ∣ ≥ s 0 ] ≥ 1 − I { t even } Pr [ B = t 2 ] ≥ 1 2 . \Pr\left[\left|\operatorname{Median}(s_1\epsilon_1,\ldots,s_t\epsilon_t)\right| \ge s_0\right] \ge1-\mathbb{I}\{t\ \text{even}\}\Pr\left[B=\frac{t}{2}\right] \ge\frac{1}{2}. Pr [ ∣ Median ( s 1 ϵ 1 , … , s t ϵ t ) ∣ ≥ s 0 ] ≥ 1 − I { t even } Pr [ B = 2 t ] ≥ 2 1 .
Let Z = ∑ j = 1 d I { ∣ μ ^ j ∣ ≥ s 0 } Z=\sum_{j=1}^{d}\mathbb{I}\{|\widehat{\mu}_j|\ge s_0\} Z = ∑ j = 1 d I { ∣ μ j ∣ ≥ s 0 } . Conditioned on E E E , the summands defining Z Z Z are independent and have expectations at least 1 / 2 1/2 1/2 by Claim C.3. Hence a Chernoff bound gives
Pr [ Z ≥ d 4 | E ] ≥ c . \Pr\left[Z\ge\frac{d}{4}\,\middle|\,E\right]\ge c. Pr [ Z ≥ 4 d E ] ≥ c .
On this event, ∥ μ ^ ∥ 2 ≥ s 0 d / 2 \|\widehat{\mu}\|_2\ge s_0\sqrt{d}/2 ∥ μ ∥ 2 ≥ s 0 d /2 . Therefore
Pr [ ∥ μ ^ ∥ 2 ≥ c s 0 d | E ] ≥ c . \Pr\left[\|\widehat{\mu}\|_2\ge c s_0\sqrt{d}\,\middle|\,E\right]\ge c. Pr [ ∥ μ ∥ 2 ≥ c s 0 d E ] ≥ c .
Since m ≤ 2 n / t m\le2n/t m ≤ 2 n / t ,
s 0 d = a m d ≥ c a t d n . s_0\sqrt{d}=\sqrt{\frac{a}{m}}\sqrt{d}\ge c\sqrt{\frac{atd}{n}}. s 0 d = m a d ≥ c n a t d .
Therefore, using (19) ,
Pr [ ∥ μ ^ ∥ 2 ≥ c a t d n ] ≥ c ( 1 8 a ) t = c ( e 2 L ) t . \Pr\left[\|\widehat{\mu}\|_2\ge c\sqrt{\frac{atd}{n}}\right]\ge c\left(\frac{1}{8a}\right)^t=c\left(\frac{e^2}{L}\right)^t. Pr [ ∥ μ ∥ 2 ≥ c n a t d ] ≥ c ( 8 a 1 ) t = c ( L e 2 ) t .
By taking c 1 c_{1} c 1 sufficiently small such that log L − 2 ≥ 0 \log L - 2 \ge0 log L − 2 ≥ 0 and since t ≤ L / log L t \le L/\log L t ≤ L / log L ,
log [ c ( e 2 L ) t ] ≥ log c − L log L ( log L − 2 ) = − L + 2 L log L + log c . \log\left[c\left(\frac{e^{2}}{L}\right)^{t}\right] \ge\log c - \frac{L}{\log L}(\log L - 2) = -L + \frac{2L}{\log L} + \log c. log [ c ( L e 2 ) t ] ≥ log c − log L L ( log L − 2 ) = − L + log L 2 L + log c .
Taking c 1 c_{1} c 1 sufficiently small makes the last quantity larger than − L -L − L . Hence
c ( e 2 L ) t > e − L = δ . c\left(\frac{e^{2}}{L}\right)^{t} > e^{-L} = \delta. c ( L e 2 ) t > e − L = δ .
Finally, because a = L / ( 8 e 2 ) a = L/(8e^{2}) a = L / ( 8 e 2 ) ,
c a t d n = c ′ t d L n = c ′ t d log ( 1 / δ ) n , c\sqrt{\frac{atd}{n}} = c'\sqrt{\frac{tdL}{n}} = c'\sqrt{\frac{td\log(1/\delta)}{n}}, c n a t d = c ′ n t d L = c ′ n t d log ( 1/ δ ) ,
for another universal constant c ′ > 0 c' > 0 c ′ > 0 . Renaming constants establishes the lemma.
Proof of Theorem 1.4 . The result follows from Lemmas C.1 and C.2 for the regimes:
t ≥ log ( 1 / δ ) log log ( 1 / δ ) and t ≤ log ( 1 / δ ) log log ( 1 / δ ) t \ge\frac{\log(1/\delta)}{\log\log(1/\delta)}
\quad\text{and}\quad
t \le\frac{\log(1/\delta)}{\log\log(1/\delta)} t ≥ log log ( 1/ δ ) log ( 1/ δ ) and t ≤ log log ( 1/ δ ) log ( 1/ δ )
respectively.