Introduction
Robust statistics under contamination is a central topic in modern statistics, and is drawing increasing attention from both the statistics and computer science communities [5 , 13 ] . A fundamental model in this field is the location model with adversarial corruption, where k k k N \mathbb{N} N [5 ] . Call the contamination fraction ε : = k / N \varepsilon:= k/N ε := k / N ε = 1 / 2 \varepsilon= 1/2 ε = 1/2 [13 ] treats the contamination level ε ≤ 1 / 2 − κ \varepsilon\le1/2 - \kappa ε ≤ 1/2 − κ κ > 0 \kappa> 0 κ > 0 ε ↑ 1 / 2 \varepsilon\uparrow1/2 ε ↑ 1/2 ε ∈ [ 0 , 1 / 2 ) \varepsilon\in[0,1/2) ε ∈ [ 0 , 1/2 )
Problem Setup
We start by introducing the adversarial corruption model as follows, as in [5 ] [Definition 2.5].
Definition 1.1 (Gaussian Location Model under Adversarial Corruption). Let clean data
X ~ 1 , … , X ~ N ∼ i . i . d . N ( μ , σ 2 I n ) , μ ∈ K ⊆ R n . \widetilde{X}_1,\ldots,\widetilde{X}_N \overset{\mathrm{i.i.d.}}{\sim} \mathcal{N}(\mu,\sigma^2 I_n), \quad\mu\in K \subseteq\mathbb{R}^n. X 1 , … , X N ∼ i.i.d. N ( μ , σ 2 I n ) , μ ∈ K ⊆ R n . Then an oracle adversarial algorithm C \mathcal{C} C k k k 0 ≤ k < N 2 0 \le k < \frac{N}{2} 0 ≤ k < 2 N ε : = k / N \varepsilon:= k/N ε := k / N
estimator, using auxiliary randomness if needed. The resulting corrupted data is denoted as X 1 : N : = ( X 1 , … , X N ) = C ( X ~ 1 : N ) X_{1:N} := (X_1,\ldots,X_N) = C(\widetilde{X}_{1:N}) X 1 : N := ( X 1 , … , X N ) = C ( X 1 : N )
Our goal is to characterize the minimax risk of estimating μ \mu μ ℓ 2 \ell_2 ℓ 2
M = M ( K , N , k , σ ) : = inf μ ^ sup μ ∈ K sup C E μ , C [ ∥ μ ^ ( X 1 : N ) − μ ∥ 2 ] (1) \mathcal{M} = \mathcal{M}(K,N,k,\sigma) := \inf_{\hat{\mu}} \sup_{\mu\in K} \sup_C \mathbb{E}_{\mu,C}\left[\left\|\hat{\mu}(X_{1:N})-\mu\right\|^2\right] \tag*{(1)} M = M ( K , N , k , σ ) := μ ^ inf μ ∈ K sup C sup E μ , C [ ∥ μ ^ ( X 1 : N ) − μ ∥ 2 ] (1) where the risk is defined for given K , N , k , σ K,N,k,\sigma K , N , k , σ μ ^ \hat{\mu} μ ^ C C C
Notation
Throughout the paper, we use n n n N N N k k k ε : = k / N \varepsilon:= k/N ε := k / N σ 2 I n \sigma^2 I_n σ 2 I n K ⊆ R n K \subseteq\mathbb{R}^n K ⊆ R n K K K d : = diam ( K ) : = sup x , y ∈ K ∥ x − y ∥ d := \operatorname{diam}(K) := \sup_{x,y\in K}\|x-y\| d := diam ( K ) := sup x , y ∈ K ∥ x − y ∥
For any two real numbers a , b a,b a , b a ∨ b : = max { a , b } a \vee b := \max\{a,b\} a ∨ b := max { a , b } a ∧ b : = min { a , b } a \wedge b := \min\{a,b\} a ∧ b := min { a , b } N N N [ N ] : = { 1 , 2 , … , N } [N] := \{1,2,\ldots,N\} [ N ] := { 1 , 2 , … , N } x ∈ R n x \in\mathbb{R}^n x ∈ R n ℓ 2 \ell_2 ℓ 2 ∥ x ∥ : = ∑ i = 1 n x i 2 \|x\| := \sqrt{\sum_{i=1}^n x_i^2} ∥ x ∥ := ∑ i = 1 n x i 2 A A A A T A^\mathsf{T} A T B ( x , r ) : = { y ∈ R n : ∥ y − x ∥ ≤ r } B(x,r) := \{y \in\mathbb{R}^n : \|y-x\| \le r\} B ( x , r ) := { y ∈ R n : ∥ y − x ∥ ≤ r } x x x r r r B q ( R ) : = { x ∈ R n : ∥ x ∥ q ≤ R } B_q(R) := \{x \in\mathbb{R}^n : \|x\|_q \le R\} B q ( R ) := { x ∈ R n : ∥ x ∥ q ≤ R } ℓ q \ell_q ℓ q R R R a , b a,b a , b n , N , k , σ , K n,N,k,\sigma,K n , N , k , σ , K a ≲ b a \lesssim b a ≲ b a ≤ C b a \le Cb a ≤ C b C > 0 C>0 C > 0 n , N , k , σ , K n,N,k,\sigma,K n , N , k , σ , K a ≳ b a \gtrsim b a ≳ b a ≥ C b a \ge Cb a ≥ C b a ≍ b a \asymp b a ≍ b a ≲ b a \lesssim b a ≲ b a ≳ b a \gtrsim b a ≳ b A A A 1 A ( x ) = 1 \mathbf{1}_A(x) = 1 1 A ( x ) = 1 x ∈ A x \in A x ∈ A 0 0 0 μ \mu μ Σ \Sigma Σ N ( μ , Σ ) \mathcal{N}(\mu,\Sigma) N ( μ , Σ ) m , p m,p m , p Binomial ( m , p ) \operatorname{Binomial}(m,p) Binomial ( m , p ) P , Q P,Q P , Q d T V ( P , Q ) : = sup A ∣ P ( A ) − Q ( A ) ∣ d_{\mathrm{TV}}(P,Q) := \sup_A |P(A)-Q(A)| d TV ( P , Q ) := sup A ∣ P ( A ) − Q ( A ) ∣
Also, we formalize the definition of two key concepts in this work: star-shaped set and local metric entropy.
Definition 1.2 (Star-Shaped Set). A set K ⊆ R n K \subseteq\mathbb{R}^n K ⊆ R n x ∗ ∈ K x^* \in K x ∗ ∈ K x ∈ K x \in K x ∈ K x ∗ x^* x ∗ x x x K K K t ∈ [ 0 , 1 ] t \in[0,1] t ∈ [ 0 , 1 ] t x ∗ + ( 1 − t ) x ∈ K t x^* + (1-t)x \in K t x ∗ + ( 1 − t ) x ∈ K x ∗ x^* x ∗ K K K
Remark 1.1. Star-shaped sets are a generalization of convex sets. Every convex set is star-shaped, with every point in the set being a center. However, not every star-shaped set is convex, making the star-shaped set a substantially richer class of sets. An important instance of a star-shaped set is the sparse vector set, which is non-convex but star-shaped with the origin being a center.
Definition 1.3 (Local Metric Entropy). Given a set K ⊆ R n K \subseteq\mathbb{R}^n K ⊆ R n r > 0 r>0 r > 0 r r r K K K M = M ( r , K ) M=M(r,K) M = M ( r , K )
such that ∥ ν i − ν j ∥ ≥ r \lVert\nu_i-\nu_j\rVert\ge r ∥ ν i − ν j ∥ ≥ r i ≠ j i\ne j i = j c > 1 c>1 c > 1 K K K
M K l o c ( r , c ) : = sup ν ∈ K M ( r / c , K ∩ B ( ν , r ) ) , M^{\mathrm{loc}}_{K}(r,c):=\sup_{\nu\in K} M(r/c,K\cap B(\nu,r)), M K loc ( r , c ) := ν ∈ K sup M ( r / c , K ∩ B ( ν , r )) , where we may drop the subscript K K K K K K log M K l o c ( r , c ) \log M^{\mathrm{loc}}_{K}(r,c) log M K loc ( r , c ) log M K l o c ( 0 , c ) : = 0 \log M^{\mathrm{loc}}_{K}(0,c):=0 log M K loc ( 0 , c ) := 0
Related Work
The theoretical study of robust statistics has a long history, dating back to Huber’s seminal work [8 ] . Later, [7 ] formalized the notion of breakdown point, and [1 ] identified 1 / 2 1/2 1/2 [4 , 5 , 10 , 9 , 13 ] . We outline several closely related works in the following.
Robust mean estimation near the breakdown point has been studied in prior work. [4 ] developed the minimax theoretic framework for Huber’s contamination model, and showed how robust testing yields optimal rates across various estimation models. [9 ] studied the Gaussian mean-shift model and established the minimax rate for the whole range of contamination levels. Their result found a phase transition governed by N − 2 k N-2k N − 2 k [3 ] focused on adversarial corruption model similar to ours through an overlap-based analysis and considered robust sparse mean estimation. However, their results do not provide a general characterization of the minimax rate under general parameter constraints. Our work further connects the corruption component with the information-theoretic component induced by local geometry, capturing the interaction between the constraint geometry and adversarial corruption.
For mean estimation with constraints under adversarial corruption, we utilize a tournament-on-the-tree framework first developed in [11 ] and later extended to adversarial corruption in [13 ] . Crucially, [13 ] extended the framework to adversarial corruption with star-shaped constraints, and established the minimax rate for ε \varepsilon ε 1 / 2 1/2 1/2
Going beyond the breakdown point of 1 / 2 1/2 1/2 [2 , 6 ] .
Contributions and Organization
Our main contribution is a sharp characterization of the minimax squared ℓ 2 \ell_2 ℓ 2 ε ∈ [ 0 , 1 / 2 ) \varepsilon\in[0,1/2) ε ∈ [ 0 , 1/2 ) [13 ] and show that the proximity to the breakdown point affects the minimax rate in two ways: (i) the information-theoretic component is governed by a fixed point equation involving the local metric entropy and the effective sample size N − 2 k = N ( 1 − 2 ε ) N-2k=N(1-2\varepsilon) N − 2 k = N ( 1 − 2 ε ) σ 2 ε 2 log e 1 − 2 ε \sigma^2\varepsilon^2\log\frac{e}{1-2\varepsilon} σ 2 ε 2 log 1 − 2 ε e ε \varepsilon ε 1 / 2 1/2 1/2
Our proof establishes matching upper and lower bounds through several key arguments. The upper bound is based on the tournament-on-the-tree framework in [13 ] , with careful calibration of constants in the tail probabilities and stopping conditions when ε \varepsilon ε 1 / 2 1/2 1/2 N N N N − 2 k N-2k N − 2 k ε \varepsilon ε ε ∈ [ 0 , 1 / 2 ) \varepsilon\in[0,1/2) ε ∈ [ 0 , 1/2 )
The remainder of the paper is organized as follows. § 2 presents the main results, including the minimax rate and several examples, and outlines the lower- and upper-bound arguments. § 3 discusses possible extensions and future directions. The appendices provide technical details: Appendix § 5 provides a brief review of the tournament-on-the-tree framework and several useful properties involved in the analysis; Appendix § 6 derives the rates for the examples in § 2.1 ; Appendix § 7 proves the lower bound and Appendix § 8 -§ 10 prove the upper bound.
Main Results
Theorem 2.1 (Minimax Rate). Let K ⊆ R n K \subseteq\mathbb{R}^n K ⊆ R n be a star-shaped set with diameter d d d (in the case of unbounded K K K , we set d = ∞ d=\infty d = ∞ ). Set 0 ≤ k < N / 2 0 \leq k < N/2 0 ≤ k < N /2 ε : = k / N \varepsilon:= k/N ε := k / N Definition 1.1 . Then
M ≍ ( δ ε ∗ 2 ∨ σ 2 ε 2 log e 1 − 2 ε ) ∧ d 2 . (2) \mathfrak{M} \asymp\left(\delta_\varepsilon^{*2} \vee\sigma^2\varepsilon^2 \log\frac{e}{1-2\varepsilon}\right) \wedge d^2. \tag*{(2)} M ≍ ( δ ε ∗ 2 ∨ σ 2 ε 2 log 1 − 2 ε e ) ∧ d 2 . (2) Here δ ε ∗ \delta_\varepsilon^* δ ε ∗ is defined as
δ ε ∗ : = sup { r ≥ 0 : ( 1 − 2 ε ) N r 2 σ 2 ≤ log M l o c ( r , c ) } , (3) \delta_\varepsilon^* := \sup\left\{r \geq0 : (1-2\varepsilon)\frac{Nr^2}{\sigma^2} \leq\log\mathcal{M}^{\mathrm{loc}}(r,c)\right\}, \tag*{(3)} δ ε ∗ := sup { r ≥ 0 : ( 1 − 2 ε ) σ 2 N r 2 ≤ log M loc ( r , c ) } , (3) in which c c c is a sufficiently large constant.
Theorem 2.1 reveals two mechanisms behind the minimax rate, together with their dependence on the corruption level ε \varepsilon ε δ ε ∗ 2 \delta_\varepsilon^{*2} δ ε ∗ 2 log M l o c ( r , c ) \log M^{\mathrm{loc}}(r,c) log M loc ( r , c ) N − 2 k = N ( 1 − 2 ε ) N-2k=N(1-2\varepsilon) N − 2 k = N ( 1 − 2 ε ) σ 2 ε 2 log e 1 − 2 ε \sigma^2\varepsilon^2\log\frac{e}{1-2\varepsilon} σ 2 ε 2 log 1 − 2 ε e ε \varepsilon ε 1 / 2 1/2 1/2 [9 ] [Appendix E], but differs from the sharper rate for Gaussian mean-shift model.
Our work is a direct continuation of [13 ] . Our result recovers their Gaussian rate when ε ∈ [ 0 , 1 / 2 − κ ] \varepsilon\in[0,1/2-\kappa] ε ∈ [ 0 , 1/2 − κ ] 1 / 2 1/2 1/2 ε ∈ [ 0 , 1 / 2 ) \varepsilon\in[0,1/2) ε ∈ [ 0 , 1/2 )
Proposition 2.1. Fix an absolute constant 0 < κ < 1 / 2 0<\kappa<1/2 0 < κ < 1/2 κ = 1 / 8 \kappa=1/8 κ = 1/8 0 ≤ ε ≤ 1 / 2 − κ 0\le\varepsilon\le1/2-\kappa 0 ≤ ε ≤ 1/2 − κ c c c [13 ] [Theorem 3.10]. Let the critical local packing radius η ∗ \eta^* η ∗
η ∗ : = sup { r ≥ 0 : N r 2 σ 2 ≤ log M l o c ( r , c ) } . \eta^*:=\sup\left\{r\ge0:\frac{Nr^2}{\sigma^2}\le\log M^{\mathrm{loc}}(r,c)\right\}. η ∗ := sup { r ≥ 0 : σ 2 N r 2 ≤ log M loc ( r , c ) } . Then we have η ∗ ≤ δ ε ∗ ≤ η ∗ 2 κ \eta^*\le\delta_\varepsilon^*\le\frac{\eta^*}{\sqrt{2\kappa}} η ∗ ≤ δ ε ∗ ≤ 2 κ η ∗
M ≍ ( η ∗ 2 ∨ σ 2 ε 2 ) ∧ d 2 ≲ ( δ ε ∗ 2 ∨ σ 2 ε 2 log e 1 − 2 ε ) ∧ d 2 , \mathfrak{M}\asymp\left(\eta^{*2}\vee\sigma^2\varepsilon^2\right)\wedge d^2\lesssim\left(\delta_\varepsilon^{*2}\vee\sigma^2\varepsilon^2\log\frac{e}{1-2\varepsilon}\right)\wedge d^2, M ≍ ( η ∗ 2 ∨ σ 2 ε 2 ) ∧ d 2 ≲ ( δ ε ∗ 2 ∨ σ 2 ε 2 log 1 − 2 ε e ) ∧ d 2 , and similarly for the unbounded case d = ∞ d=\infty d = ∞ [13 ] .
Examples
We illustrate the minimax rate in Theorem 2.1 with several examples of constraint sets K K K ℓ 2 \ell_2 ℓ 2 ℓ 1 \ell_1 ℓ 1 R : = d / 2 R:=d/2 R := d /2
Unconstrained Case For K = R n K=\mathbb{R}^n K = R n log M K l o c ( r , c ) ≳ n \log M_K^{\mathrm{loc}}(r,c)\gtrsim n log M K loc ( r , c ) ≳ n r > 0 r>0 r > 0
M ( R n ) ≳ σ 2 n N ( 1 − 2 ε ) ∨ σ 2 ε 2 log e 1 − 2 ε . \mathfrak{M}(\mathbb{R}^n)\gtrsim\frac{\sigma^2n}{N(1-2\varepsilon)}\vee\sigma^2\varepsilon^2\log\frac{e}{1-2\varepsilon}. M ( R n ) ≳ N ( 1 − 2 ε ) σ 2 n ∨ σ 2 ε 2 log 1 − 2 ε e . Euclidean Ball For K = B 2 ( R ) : = { x ∈ R n : ∥ x ∥ ≤ R } K=B_2(R):=\{x\in\mathbb{R}^n:\lVert x\rVert\le R\} K = B 2 ( R ) := { x ∈ R n : ∥ x ∥ ≤ R } 0 < r ≲ R 0<r\lesssim R 0 < r ≲ R
M ( B 2 ( R ) ) ≳ ( σ 2 n N ( 1 − 2 ε ) ∨ σ 2 ε 2 log e 1 − 2 ε ) ∧ R 2 . \mathfrak{M}(B_2(R))\gtrsim\left(\frac{\sigma^2n}{N(1-2\varepsilon)}\vee\sigma^2\varepsilon^2\log\frac{e}{1-2\varepsilon}\right)\wedge R^2. M ( B 2 ( R )) ≳ ( N ( 1 − 2 ε ) σ 2 n ∨ σ 2 ε 2 log 1 − 2 ε e ) ∧ R 2 . ℓ 1 \ell_1 ℓ 1 K = B 1 ( R ) : = { x ∈ R n : ∥ x ∥ 1 ≤ R } K = B_1(R) := \{x \in\mathbb{R}^n : \lVert x \rVert_1 \le R\} K = B 1 ( R ) := { x ∈ R n : ∥ x ∥ 1 ≤ R } n ≥ 2 n \ge2 n ≥ 2 0 < r ≤ R 0 < r \le R 0 < r ≤ R
log M B 1 ( R ) l o c ( r , c ) ≲ { n , r ≤ R / n R 2 r 2 log e n r 2 R 2 , R / n < r ≤ R . \log M^{\mathrm{loc}}_{B_1(R)}(r,c) \lesssim\begin{cases} n, & r \le R/\sqrt{n} \\ \frac{R^2}{r^2} \log\frac{enr^2}{R^2}, & R/\sqrt{n} < r \le R. \end{cases} log M B 1 ( R ) loc ( r , c ) ≲ { n , r 2 R 2 log R 2 e n r 2 , r ≤ R / n R / n < r ≤ R . The resulting minimax rate is
M ( B 1 ( R ) ) ≳ { ( R 2 log ( e n / λ ) λ ∨ σ 2 ε 2 log e 1 − 2 ε ) ∧ R 2 , λ ≤ n 2 ( R 2 n λ ∨ σ 2 ε 2 log e 1 − 2 ε ) ∧ R 2 , λ > n 2 , \mathfrak{M}(B_1(R)) \gtrsim\begin{cases} \left(R^2\sqrt{\frac{\log(en/\sqrt{\lambda})}{\lambda}} \vee\sigma^2\varepsilon^2\log\frac{e}{1-2\varepsilon}\right) \wedge R^2, & \lambda\le n^2 \\ \left(R^2\frac{n}{\lambda} \vee\sigma^2\varepsilon^2\log\frac{e}{1-2\varepsilon}\right) \wedge R^2, & \lambda> n^2, \end{cases} M ( B 1 ( R )) ≳ ⎩ ⎨ ⎧ ( R 2 λ l o g ( e n / λ ) ∨ σ 2 ε 2 log 1 − 2 ε e ) ∧ R 2 , ( R 2 λ n ∨ σ 2 ε 2 log 1 − 2 ε e ) ∧ R 2 , λ ≤ n 2 λ > n 2 , where we denote λ : = N ( 1 − 2 ε ) R 2 σ 2 \lambda:= \frac{N(1-2\varepsilon)R^2}{\sigma^2} λ := σ 2 N ( 1 − 2 ε ) R 2 § 6 .
Sparse Vector Set Let 1 ≤ s ≤ n / 8 1 \le s \le n/8 1 ≤ s ≤ n /8 K K K K : = { x ∈ R n : ∥ x ∥ 0 ≤ s } K := \{x \in\mathbb{R}^n : \lVert x \rVert_0 \le s\} K := { x ∈ R n : ∥ x ∥ 0 ≤ s } log M K l o c ( r , c ) ≲ s log e n s \log M^{\mathrm{loc}}_K(r,c) \lesssim s \log\frac{en}{s} log M K loc ( r , c ) ≲ s log s e n r > 0 r > 0 r > 0
M ( { x ∈ R n : ∥ x ∥ 0 ≤ s } ) ≳ σ 2 s log e n s N ( 1 − 2 ε ) ∨ σ 2 ε 2 log e 1 − 2 ε . \mathfrak{M}(\{x \in\mathbb{R}^n : \lVert x \rVert_0 \le s\}) \gtrsim\frac{\sigma^2 s \log\frac{en}{s}}{N(1-2\varepsilon)} \vee\sigma^2\varepsilon^2\log\frac{e}{1-2\varepsilon}. M ({ x ∈ R n : ∥ x ∥ 0 ≤ s }) ≳ N ( 1 − 2 ε ) σ 2 s log s e n ∨ σ 2 ε 2 log 1 − 2 ε e . In the case of an extra radius constraint R > 0 R > 0 R > 0 K : = { x ∈ R n : ∥ x ∥ 0 ≤ s , ∥ x ∥ 2 ≤ R } K := \{x \in\mathbb{R}^n : \lVert x \rVert_0 \le s, \lVert x \rVert_2 \le R\} K := { x ∈ R n : ∥ x ∥ 0 ≤ s , ∥ x ∥ 2 ≤ R }
M ( { x ∈ R n : ∥ x ∥ 0 ≤ s , ∥ x ∥ 2 ≤ R } ) ≳ ( σ 2 s log e n s N ( 1 − 2 ε ) ∨ σ 2 ε 2 log e 1 − 2 ε ) ∧ R 2 . \mathfrak{M}(\{x \in\mathbb{R}^n : \lVert x \rVert_0 \le s, \lVert x \rVert_2 \le R\}) \gtrsim\left(\frac{\sigma^2 s \log\frac{en}{s}}{N(1-2\varepsilon)} \vee\sigma^2\varepsilon^2\log\frac{e}{1-2\varepsilon}\right) \wedge R^2. M ({ x ∈ R n : ∥ x ∥ 0 ≤ s , ∥ x ∥ 2 ≤ R }) ≳ ( N ( 1 − 2 ε ) σ 2 s log s e n ∨ σ 2 ε 2 log 1 − 2 ε e ) ∧ R 2 . Lower Bound
We split the lower bound into the regimes of ε ≤ 3 / 8 \varepsilon\le3/8 ε ≤ 3/8 ε > 3 / 8 \varepsilon> 3/8 ε > 3/8 [13 ] ; the latter is the main contribution of this work. The lower bound consists of two components: the information theoretic component and the contamination component. We present the key steps to establish each of them when ε \varepsilon ε 1 / 2 1/2 1/2 § 7 .
Information Theoretic Component We first look at the information-theoretic component of the minimax rate. The key observation is that, with a proper adversary, an adversarial corruption problem with k k k N N N N − 2 k N-2k N − 2 k
Lemma 2.1 (Effective Sample Size Reduction). Let Θ : = { μ 1 , … , μ M } ⊂ K \Theta:= \{\mu_1,\ldots,\mu_M\} \subset K Θ := { μ 1 , … , μ M } ⊂ K V ∼ π V \sim\pi V ∼ π [ M ] [M] [ M ] μ V \mu_V μ V
X ~ 1 , … , X ~ N ∼ i . i . d . N ( μ V , σ 2 I n ) , μ V ∈ Θ . \widetilde{X}_1,\ldots,\widetilde{X}_N \overset{\mathrm{i.i.d.}}{\sim} \mathcal{N}(\mu_V,\sigma^2 I_n), \qquad\mu_V \in\Theta. X 1 , … , X N ∼ i.i.d. N ( μ V , σ 2 I n ) , μ V ∈ Θ. Given an adversarial corruption algorithm C C C X ~ 1 : N \widetilde{X}_{1:N} X 1 : N X 1 : N X_{1:N} X 1 : N k = ε N < N / 2 k=\varepsilon N<N/2 k = εN < N /2
R c o r r u p t ( μ ^ , C , π ) : = E μ V ∼ π [ E μ V , C [ ∥ μ ^ ( X 1 : N ) − μ V ∥ 2 ] ] . R_{\mathrm{corrupt}}(\widehat{\mu},C,\pi):=\mathbb{E}_{\mu_V\sim\pi}\left[\mathbb{E}_{\mu_V,C}\left[\left\|\widehat{\mu}(X_{1:N})-\mu_V\right\|^2\right]\right]. R corrupt ( μ , C , π ) := E μ V ∼ π [ E μ V , C [ ∥ μ ( X 1 : N ) − μ V ∥ 2 ] ] . Let the Bayesian risk for clean data of size m m m
R c l e a n ( m , π ) : = inf μ ^ E μ V ∼ π [ E μ V [ ∥ μ ^ ( X ~ 1 : m ) − μ V ∥ 2 ] ] . R_{\mathrm{clean}}(m,\pi):=\inf_{\widehat{\mu}}\mathbb{E}_{\mu_V\sim\pi}\left[\mathbb{E}_{\mu_V}\left[\left\|\widehat{\mu}(\widetilde{X}_{1:m})-\mu_V\right\|^2\right]\right]. R clean ( m , π ) := μ inf E μ V ∼ π [ E μ V [ μ ( X 1 : m ) − μ V 2 ] ] . Then for any prior π \pi π C π C_\pi C π μ ^ \widehat{\mu} μ
R c o r r u p t ( μ ^ , C π , π ) ≥ 1 2 R c l e a n ( N − 2 k , π ) . R_{\mathrm{corrupt}}(\widehat{\mu},C_\pi,\pi)\geq\frac{1}{2}R_{\mathrm{clean}}(N-2k,\pi). R corrupt ( μ , C π , π ) ≥ 2 1 R clean ( N − 2 k , π ) . Then applying Lemma 2.1 to a local packing set and using Fano’s method, we can establish the information theoretic component lower bound.
Remark 2.1. Lemma 2.1 provides a useful connection between the estimation under adversarial corruption and the clean-sample estimation, illustrating the effective sample size reduction from N N N N − 2 k N-2k N − 2 k ℓ 2 \ell_2 ℓ 2
Contamination Component We now turn to the contamination component of the minimax rate. This can be done by carefully assessing the total variation distance between two Gaussian distributions to show that these two distributions are indistinguishable under a suitable adversary.
Lemma 2.2. Let a a a N N N ε − : = ε − a N > 1 / 4 \varepsilon_-:=\varepsilon-\frac{a}{\sqrt{N}}>1/4 ε − := ε − N a > 1/4 μ 0 , μ 1 ∈ K \mu_0,\mu_1\in K μ 0 , μ 1 ∈ K
d T V ( N ( μ 0 , σ 2 I n ) , N ( μ 1 , σ 2 I n ) ) ≤ 2 ε − . d_{\mathrm{TV}}\left(\mathcal{N}(\mu_0,\sigma^2 I_n),\mathcal{N}(\mu_1,\sigma^2 I_n)\right)\leq2\varepsilon_-. d TV ( N ( μ 0 , σ 2 I n ) , N ( μ 1 , σ 2 I n ) ) ≤ 2 ε − . Then there exist two adversaries C 0 , C 1 C_0,C_1 C 0 , C 1 μ 0 \mu_0 μ 0 μ 1 \mu_1 μ 1
P ~ b ( N ) : = L ( C b ( X ~ 1 : N ) ) , b = 0 , 1 , \widetilde{P}^{(N)}_b:=\mathcal{L}\left(C_b(\widetilde{X}_{1:N})\right),\qquad b=0,1, P b ( N ) := L ( C b ( X 1 : N ) ) , b = 0 , 1 , be the distribution of the corrupted data, we have d T V ( P ~ 0 ( N ) , P ~ 1 ( N ) ) < 1 2 d_{\mathrm{TV}}(\widetilde{P}^{(N)}_0,\widetilde{P}^{(N)}_1)<\frac{1}{2} d TV ( P 0 ( N ) , P 1 ( N ) ) < 2 1
M ≥ inf μ ^ sup b ∈ { 0 , 1 } E P ~ b ( N ) [ ∥ μ ^ − μ b ∥ 2 ] ≳ ∥ μ 0 − μ 1 ∥ 2 . \mathfrak{M}\geq\inf_{\widehat{\mu}}\sup_{b\in\{0,1\}}\mathbb{E}_{\widetilde{P}^{(N)}_b}\left[\left\|\widehat{\mu}-\mu_b\right\|^2\right]\gtrsim\left\|\mu_0-\mu_1\right\|^2. M ≥ μ inf b ∈ { 0 , 1 } sup E P b ( N ) [ ∥ μ − μ b ∥ 2 ] ≳ ∥ μ 0 − μ 1 ∥ 2 . Remark 2.2. Here the constant a a a N N N N ≥ N a N \ge N_a N ≥ N a a a a ε \varepsilon ε ε \varepsilon ε
The characterization of the total variation distance between two Gaussian distributions was given in previous work, say [9 ] [Appendix § 9 ]. This allows us to establish the contamination component of the minimax lower bound, as formalized in the following lemma.
Lemma 2.3 (Contamination Lower Bound). Let M \mathcal{M} M ε = k N ∈ ( 3 / 8 , 1 / 2 ) \varepsilon= \frac{k}{N} \in(3/8,1/2) ε = N k ∈ ( 3/8 , 1/2 )
M ≳ σ 2 ε 2 log 1 1 − 2 ε ∧ d 2 , \mathcal{M} \gtrsim\sigma^2\varepsilon^2 \log\frac{1}{1-2\varepsilon} \wedge d^2, M ≳ σ 2 ε 2 log 1 − 2 ε 1 ∧ d 2 , and set d = ∞ d = \infty d = ∞ K K K
The above two components characterize the minimax lower bound when ε \varepsilon ε 1 / 2 1/2 1/2 ε ∈ [ 0 , 3 / 8 ] \varepsilon\in[0,3/8] ε ∈ [ 0 , 3/8 ] ε ∈ [ 0 , 1 / 2 ) \varepsilon\in[0,1/2) ε ∈ [ 0 , 1/2 )
Theorem 2.2 (Minimax Lower Bound). Let ε = k N ∈ [ 0 , 1 / 2 ) \varepsilon= \frac{k}{N} \in[0,1/2) ε = N k ∈ [ 0 , 1/2 ) M \mathcal{M} M d d d K K K
M ≳ max { δ ε ∗ 2 , σ 2 ε 2 log ( e / ( 1 − 2 ε ) ) } ∧ d 2 , \mathcal{M} \gtrsim\max\{\delta_\varepsilon^{*2},\sigma^2\varepsilon^2\log(e/(1-2\varepsilon))\}\wedge d^2, M ≳ max { δ ε ∗ 2 , σ 2 ε 2 log ( e / ( 1 − 2 ε ))} ∧ d 2 , and set d = ∞ d = \infty d = ∞ K K K δ ε ∗ \delta_\varepsilon^* δ ε ∗ (3) .
Upper Bound
For the upper bound, we apply the tournament-on-the-tree framework as in [13 ] [§ 3 ]. The tree structure and estimator construction remain unchanged up to a rescaling, while the main difference is that we need to calibrate the constants in the tail probability bound when ε \varepsilon ε 1 / 2 1/2 1/2 ε \varepsilon ε K K K ε \varepsilon ε
In the following we present the main results for the upper bound. We refer the readers to Section A.2 for a review of the tournament-on-the-tree framework and Appendix § 8 -§ 10 for the technical details of the upper bound proof.
Theorem 2.3 (Minimax Upper Bound for Bounded K K K K K K d d d Definition 1.1 where ε = k N ∈ [ 0 , 1 / 2 ) \varepsilon= \frac{k}{N} \in[0,1/2) ε = N k ∈ [ 0 , 1/2 )
M ≲ max { δ ε ∗ 2 , σ 2 ε 2 log ( e / ( 1 − 2 ε ) ) } ∧ d 2 (4) \mathcal{M} \lesssim\max\{\delta_\varepsilon^{*2},\sigma^2\varepsilon^2\log(e/(1-2\varepsilon))\}\wedge d^2 \tag*{(4)} M ≲ max { δ ε ∗ 2 , σ 2 ε 2 log ( e / ( 1 − 2 ε ))} ∧ d 2 (4) where we define δ ε ∗ \delta_\varepsilon^* δ ε ∗ (3) .
For unbounded K K K [13 ] [Section 5].
Theorem 2.4 (Minimax Upper Bound for Unbounded K K K Let K K K Definition 1.1 where ε = k N ∈ [ 0 , 1 / 2 ) \varepsilon= \frac{k}{N} \in[0,1/2) ε = N k ∈ [ 0 , 1/2 )
M ≲ max { δ ε ∗ 2 , σ 2 ε 2 log ( e 1 − 2 ε ) } , \mathcal{M} \lesssim\max\left\{\delta_{\varepsilon}^{*2}, \sigma^{2}\varepsilon^{2}\log\left(\frac{e}{1-2\varepsilon}\right)\right\}, M ≲ max { δ ε ∗ 2 , σ 2 ε 2 log ( 1 − 2 ε e ) } , where δ ε ∗ \delta_{\varepsilon}^{*} δ ε ∗
Discussion
We established the minimax rate for constraint Gaussian mean estimation under adversarial corruption, with a focus on the regime when the corruption level ε \varepsilon ε 1 / 2 1/2 1/2 N ( 1 − 2 ε ) N(1-2\varepsilon) N ( 1 − 2 ε ) δ ε ∗ \delta_{\varepsilon}^{*} δ ε ∗ ε 2 log e 1 − 2 ε \varepsilon^{2}\log\frac{e}{1-2\varepsilon} ε 2 log 1 − 2 ε e ε \varepsilon ε 1 / 2 1/2 1/2 [13 ] .
Our result utilizes the tournament-on-the-tree framework in [13 ] to establish the minimax upper bound. They also presented the application of the framework to sub-Gaussian model, and the subsequent work [12 ] extended to even heavier tailed distributions of finite moments. It is of interest to characterize the full near-breakdown behavior under these broader noise settings. Another interesting direction is Gaussian noise with known covariance Σ \Sigma Σ σ 2 \sigma^{2} σ 2 σ 2 \sigma^{2} σ 2
Declaration of AI Use
During the preparation of this manuscript, the authors used the generative AI tools from OpenAI to assist with literature review, grammar and language polishing, and refinement of mathematical arguments. Generative AI was also used in the verification of the constants in certain proofs. All AI-assisted suggestions were evaluated by the authors, who take full responsibility for the mathematical results, proofs, and other content of this paper.
Tournament-on-the-Tree Framework
The tournament-on-the-tree framework provides a systematic approach to establish the upper bounds of robust estimation problems. The core idea was first introduced in [11 ] and later extended in [13 ] to handle more general settings. We briefly summarize the key steps of this framework below and refer the readers to [12 ] Section 3 for a more systematic introduction. Throughout the upper bound arguments, we use an ε \varepsilon ε
We retain the large enough constant C > 2 C > 2 C > 2 c : = 4 ( C + 1 ) c := 4(C + 1) c := 4 ( C + 1 ) [13 ] Remark 3.9. For bounded K K K d d d
r J : = d 2 J − 1 ( C + 1 ) , J ≥ 1. (5) r_J := \frac{d}{2^{J-1}(C+1)}, \qquad J \ge1. \tag*{(5)} r J := 2 J − 1 ( C + 1 ) d , J ≥ 1. (5) Useful Properties
We first collect several useful properties of the local packing number and star-shaped sets.
Lemma A.1 (Useful Properties). Let K ⊆ R n K \subseteq\mathbb{R}^n K ⊆ R n be a star-shaped set and let c > 1 c > 1 c > 1 be some constant. Then the following properties hold:
(i) The mapping r \mapsto M_K^{\mathrm{loc}}(r,c)\) *is non-increasing in* r > 0$;
(ii) For any r > 0 r > 0 r > 0 we have M K l o c ( r , c ) ≤ ( 1 + 2 c ) n M_K^{\mathrm{loc}}(r,c) \le(1+2c)^n M K loc ( r , c ) ≤ ( 1 + 2 c ) n
(iii) If K K K is bounded with diameter d d d then K K K must contain a line segment of length ≥ d / 3 \ge d/3 ≥ d /3 If K K K is unbounded, then it must contain line segments of any length.
Proof. The proofs of (i) and (iii) were given in [13 ] Lemma 1.4, Lemma 1.3. (ii) is a direct consequence of the volume argument, see [12 ] Remark 4.2 for details.
We also give the following proof of Proposition 2.1 to show that our result is consistent with [13 ] when ε \varepsilon ε 1 / 2 1/2 1/2
Proof of Proposition 2.1. We prove for the bounded K K K K K K
By Lemma A.1(i), for any r < δ ε ∗ r < \delta_\varepsilon^* r < δ ε ∗
log M l o c ( 1 − 2 ε r , c ) ≥ log M l o c ( r , c ) ≥ ( 1 − 2 ε ) N r 2 / σ 2 = N ( 1 − 2 ε r ) 2 / σ 2 , \log M^{\mathrm{loc}}\left(\sqrt{1-2\varepsilon r},c\right) \ge\log M^{\mathrm{loc}}(r,c) \ge(1-2\varepsilon)Nr^2/\sigma^2 = N\left(\sqrt{1-2\varepsilon r}\right)^2/\sigma^2, log M loc ( 1 − 2 ε r , c ) ≥ log M loc ( r , c ) ≥ ( 1 − 2 ε ) N r 2 / σ 2 = N ( 1 − 2 ε r ) 2 / σ 2 , meaning that 1 − 2 ε r ≤ η ∗ \sqrt{1-2\varepsilon r} \le\eta^* 1 − 2 ε r ≤ η ∗ r < δ ε ∗ r < \delta_\varepsilon^* r < δ ε ∗
1 ≤ log e 1 − 2 ε ≤ 1 + log 1 2 κ , 1 \le\log\frac{e}{1-2\varepsilon} \le1+\log\frac{1}{2\kappa}, 1 ≤ log 1 − 2 ε e ≤ 1 + log 2 κ 1 , so the two minimax rates are equivalent up to a constant factor depending on κ \kappa κ
Pruned Directed Tree Construction and the Estimator
Fix a sufficiently large universal separation constant C > 2 C>2 C > 2 c : = 4 ( C + 1 ) c:=4(C+1) c := 4 ( C + 1 ) c c c [13 ] Remark 3.9 to rescale c c c c o r i g = 2 ( C + 1 ) c_{\mathrm{orig}}=2(C+1) c orig = 2 ( C + 1 ) K K K d d d
r J = d 2 J − 1 ( C + 1 ) , J ≥ 1. r_J=\frac{d}{2^{J-1}(C+1)},\qquad J\ge1. r J = 2 J − 1 ( C + 1 ) d , J ≥ 1. Starting from an arbitrary root in K K K [13 ] Section 3.1. Let L ( J ) \mathcal{L}(J) L ( J ) J J J O ( u ) \mathcal{O}(u) O ( u ) u u u [13 ] Lemma 3.1 – 3.3 in Lemma A.2. The constants in the construction are slightly different from the original [13 ] Section 3.1 due to the rescaling of c c c
Algorithm 1 Directed Tree Construction
Input: Set K K K s ∈ K s\in K s ∈ K d > 0 d>0 d > 0 c = 4 ( C + 1 ) c=4(C+1) c = 4 ( C + 1 )
Output: A directed tree structure G \mathcal{G} G J J J L ( J ) \mathcal{L}(J) L ( J )
L ( 1 ) ← { s } \mathcal{L}(1)\leftarrow\{s\} L ( 1 ) ← { s }
Form a maximal ( 2 d / c ) (2d/c) ( 2 d / c ) B ( s , d ) ∩ K B(s,d)\cap K B ( s , d ) ∩ K s s s s s s O ( s ) \mathcal{O}(s) O ( s )
L ( 2 ) ← O ( s ) \mathcal{L}(2)\leftarrow\mathcal{O}(s) L ( 2 ) ← O ( s )
for J = 3 , 4 , … J=3,4,\ldots J = 3 , 4 , … do
for all u ∈ L ( J − 1 ) u\in\mathcal{L}(J-1) u ∈ L ( J − 1 ) do
Form a maximal ( d / 2 J − 2 c ) (d/2^{J-2}c) ( d / 2 J − 2 c ) B ( u , d / 2 J − 2 ) ∩ K B(u,d/2^{J-2})\cap K B ( u , d / 2 J − 2 ) ∩ K u u u O ( u ) \mathcal{O}(u) O ( u )
end for
8: U J ← U_J \leftarrow U J ← O ( u ) \mathcal{O}(u) O ( u ) u ∈ L ( J − 1 ) u \in\mathcal{L}(J-1) u ∈ L ( J − 1 )
9: while U J ≠ ∅ U_J \ne\varnothing U J = ∅
10: Pick first element, say u l J u_l^J u l J U J U_J U J
11: T J ( u l J ) ← { u k J ∈ U J : ∥ u k J − u l J ∥ ≤ d 2 J − 2 c , k ≠ l } ; \mathcal{T}_J(u_l^J) \leftarrow\{u_k^J \in U_J : \lVert u_k^J-u_l^J\rVert\le\frac{d}{2^{J-2}c},\ k \ne l\}; T J ( u l J ) ← { u k J ∈ U J : ∥ u k J − u l J ∥ ≤ 2 J − 2 c d , k = l } ;
12: For each u k J ∈ T J ( u l J ) u_k^J \in\mathcal{T}_J(u_l^J) u k J ∈ T J ( u l J ) P ( u k J ) → u k J \mathcal{P}(u_k^J) \to u_k^J P ( u k J ) → u k J u k J u_k^J u k J G G G P ( u k J ) → u l J \mathcal{P}(u_k^J) \to u_l^J P ( u k J ) → u l J
13: Remove { u l J } ∪ T J ( u l J ) \{u_l^J\} \cup\mathcal{T}_J(u_l^J) { u l J } ∪ T J ( u l J ) U J U_J U J
14: end while
15: L ( J ) ← ⋃ u ∈ L ( J − 1 ) O ( u ) ; \mathcal{L}(J) \leftarrow\bigcup_{u\in\mathcal{L}(J-1)}\mathcal{O}(u); L ( J ) ← ⋃ u ∈ L ( J − 1 ) O ( u ) ;
16: end for
17: return G G G
Lemma A.2 (Pruned Directed Tree Properties). For the above described pruned directed tree, we have the following properties:
(i) For any J ≥ 3 J \ge3 J ≥ 3 L ( J ) \mathcal{L}(J) L ( J ) r J r_J r J ( r J / 2 ) (r_J/2) ( r J /2 ) K K K
(ii) For any J ≥ 2 J \ge2 J ≥ 2 u ∈ L ( J − 1 ) u \in\mathcal{L}(J-1) u ∈ L ( J − 1 ) O ( u ) \mathcal{O}(u) O ( u ) r J r_J r J K ∩ B ( u , ( c / 2 ) r J ) K \cap B(u,(c/2)r_J) K ∩ B ( u , ( c /2 ) r J ) ∣ O ( u ) ∣ ≤ M K loc ( ( c / 2 ) r J , c ) |\mathcal{O}(u)| \le M_K^{\operatorname{loc}}((c/2)r_J,c) ∣ O ( u ) ∣ ≤ M K loc (( c /2 ) r J , c )
(iii) For any J ≥ 2 J \ge2 J ≥ 2 μ ∈ K \mu\in K μ ∈ K
∣ L ( J − 1 ) ∩ B ( μ , ( c / 2 ) r J ) ∣ ≤ M K loc ( ( c / 2 ) r J , c ) ; |\mathcal{L}(J-1) \cap B(\mu,(c/2)r_J)| \le M_K^{\operatorname{loc}}((c/2)r_J,c); ∣ L ( J − 1 ) ∩ B ( μ , ( c /2 ) r J ) ∣ ≤ M K loc (( c /2 ) r J , c ) ; (iv) Every infinite path Y = [ Y 1 , Y 2 , … ] \mathcal{Y}=[\mathcal{Y}_1,\mathcal{Y}_2,\ldots] Y = [ Y 1 , Y 2 , … ] Y J + 1 ∈ O ( Y J ) \mathcal{Y}_{J+1}\in\mathcal{O}(\mathcal{Y}_J) Y J + 1 ∈ O ( Y J ) 1 ≤ J ′ ≤ J 1 \le J' \le J 1 ≤ J ′ ≤ J
∥ Y J − Y J ′ ∥ ≤ 4 C + 5 2 r J . \lVert\mathcal{Y}_J-\mathcal{Y}_{J'}\rVert\le\frac{4C+5}{2}r_J. ∥ Y J − Y J ′ ∥ ≤ 2 4 C + 5 r J . Tournament Based on Robust Comparison Another key ingredient of the tournament-on-the-tree framework is a tournament procedure based on the robust pairwise comparison over the local packing set at each layer. We remind the readers that the tree is constructed such that for any node, its offspring form a local packing set of the appropriate ball around the parent node. The objective of the tournament is to select a winner which can best represent the true mean parameter μ \mu μ
The fundamental building block of the tournament is the robust pairwise comparison between two candidates. Given an ordered pair of candidates ( ν 1 , ν 2 ) (\nu_1,\nu_2) ( ν 1 , ν 2 ) ν 1 , ν 2 ∈ K \nu_1,\nu_2 \in K ν 1 , ν 2 ∈ K ∥ ν 1 − ν 2 ∥ ≥ C r \lVert\nu_1-\nu_2\rVert\ge Cr ∥ ν 1 − ν 2 ∥ ≥ C r μ \mu μ X ~ \widetilde{X} X B ( ν 1 , r ) B(\nu_1,r) B ( ν 1 , r ) B ( ν 2 , r ) B(\nu_2,r) B ( ν 2 , r )
ψ = ψ ( ν 1 , ν 2 ) = { 0 , if deciding μ ∈ B ( ν 1 , r ) , 1 , if deciding μ ∈ B ( ν 2 , r ) . \psi=\psi_{(\nu_1,\nu_2)}=
\begin{cases}
0, & \text{if deciding } \mu\in B(\nu_1,r),\\
1, & \text{if deciding } \mu\in B(\nu_2,r).
\end{cases} ψ = ψ ( ν 1 , ν 2 ) = { 0 , 1 , if deciding μ ∈ B ( ν 1 , r ) , if deciding μ ∈ B ( ν 2 , r ) . Assume ν 1 , ν 2 \nu_1,\nu_2 ν 1 , ν 2 R n \mathbb{R}^n R n ψ ( ν 1 , ν 2 ) = 0 \psi_{(\nu_1,\nu_2)}=0 ψ ( ν 1 , ν 2 ) = 0 ν 1 ≻ ν 2 \nu_1 \succ\nu_2 ν 1 ≻ ν 2 ν 2 ≻ ν 1 \nu_2 \succ\nu_1 ν 2 ≻ ν 1 [13 ] Definition 3.4:
Definition A.1. Given any ordered pair of candidates ( ν 1 , ν 2 ) (\nu_1,\nu_2) ( ν 1 , ν 2 ) Definition 1.1 , the testing function is defined by
ψ ( ν 1 , ν 2 ) ( X 1 : N ) = 1 ( card { i ∈ [ N ] : ∥ X i − ν 1 ∥ ≥ ∥ X i − ν 2 ∥ } ≥ N 2 ) . \psi_{(\nu_1,\nu_2)}(X_{1:N})=\mathbb{1}\left(\operatorname{card}\left\{i\in[N]:\lVert X_i-\nu_1\rVert\geq\lVert X_i-\nu_2\rVert\right\}\geq\frac{N}{2}\right). ψ ( ν 1 , ν 2 ) ( X 1 : N ) = 1 ( card { i ∈ [ N ] : ∥ X i − ν 1 ∥ ≥ ∥ X i − ν 2 ∥ } ≥ 2 N ) . For simplicity, we write ψ \psi ψ
The robust pairwise comparison leads to a robust tournament among the offspring of each node in the pruned directed tree. Based on the directed tree constructed, a robust tournament series can be performed. We record one step here for clarity. On each level J ≥ 2 J\geq2 J ≥ 2 Y J − 1 \mathcal{Y}_{J-1} Y J − 1 O ( Y J − 1 ) \mathcal{O}(\mathcal{Y}_{J-1}) O ( Y J − 1 ) S = O ( Y J − 1 ) S=\mathcal{O}(\mathcal{Y}_{J-1}) S = O ( Y J − 1 ) ν ∈ S \nu\in S ν ∈ S
T ( r , ν , S ) = { max ν ′ ∈ S ′ ∥ ν − ν ′ ∥ , if S ′ ≠ ∅ , 0 , if S ′ = ∅ , T(r,\nu,S)=
\begin{cases}
\max_{\nu'\in S'}\lVert\nu-\nu'\rVert, & \text{if }S'\ne\varnothing,\\
0, & \text{if }S'=\varnothing,
\end{cases} T ( r , ν , S ) = { max ν ′ ∈ S ′ ∥ ν − ν ′ ∥ , 0 , if S ′ = ∅ , if S ′ = ∅ , where we define S ′ = { ν ′ ∈ S : ν ′ ≻ ν and ∥ ν − ν ′ ∥ ≥ C r } S'=\{\nu'\in S:\nu'\succ\nu\text{ and }\lVert\nu-\nu'\rVert\geq Cr\} S ′ = { ν ′ ∈ S : ν ′ ≻ ν and ∥ ν − ν ′ ∥ ≥ C r } ν ^ \hat{\nu} ν ^ T ( r , ν , S ) T(r,\nu,S) T ( r , ν , S ) S S S J J J p ( r ) p(r) p ( r ) [13 ] Lemma 3.7.
Lemma A.3 (Tournament Error Bound). Let S ⊆ K S\subseteq K S ⊆ K r r r K ′ ⊆ K K'\subseteq K K ′ ⊆ K μ ∈ K ′ \mu\in K' μ ∈ K ′ ν 1 , ν 2 ∈ S \nu_1,\nu_2\in S ν 1 , ν 2 ∈ S ∥ ν 1 − ν 2 ∥ ≥ C r \lVert\nu_1-\nu_2\rVert\geq Cr ∥ ν 1 − ν 2 ∥ ≥ C r p ( r ) p(r) p ( r ) ν ^ \hat{\nu} ν ^
P μ ( ∥ ν ^ − μ ∥ ≥ ( C + 1 ) r ) ≤ ∣ S ∣ ⋅ p ( r ) . \mathbb{P}_{\mu}\left(\lVert\hat{\nu}-\mu\rVert\geq(C+1)r\right)\leq|S|\cdot p(r). P μ ( ∥ ν ^ − μ ∥ ≥ ( C + 1 ) r ) ≤ ∣ S ∣ ⋅ p ( r ) . Bounded K K K In the case of bounded K K K Y = [ Y 1 , Y 2 , … ] \mathcal{Y}=[\mathcal{Y}_1,\mathcal{Y}_2,\ldots] Y = [ Y 1 , Y 2 , … ]
Algorithm 2 Robust Tournament Algorithm for an Upper Bound.
Input: Directed tree G \mathcal{G} G
Output: A winner chain Y = [ Y 1 , Y 2 , … ] \mathcal{Y}=[\mathcal{Y}_1,\mathcal{Y}_2,\ldots] Y = [ Y 1 , Y 2 , … ] G \mathcal{G} G
Initialize J = 1 J=1 J = 1 Y 1 = s \mathcal{Y}_1=s Y 1 = s Y = [ Y 1 ] \mathcal{Y}=[\mathcal{Y}_1] Y = [ Y 1 ]
for J = 1 , 2 , … J=1,2,\ldots J = 1 , 2 , … do
Y J + 1 ← arg min ν ∈ O ( Y J ) T ( d 2 J ( C + 1 ) , ν , O ( Y J ) ) \mathcal{Y}_{J+1}\leftarrow\underset{\nu\in\mathcal{O}(\mathcal{Y}_J)}{\arg\min}\ T\left(\frac{d}{2^{J}(C+1)},\nu,\mathcal{O}(\mathcal{Y}_J)\right) Y J + 1 ← ν ∈ O ( Y J ) arg min T ( 2 J ( C + 1 ) d , ν , O ( Y J ) )
Y . append ( Y J + 1 ) \mathcal{Y}.\operatorname{append}(\mathcal{Y}_{J+1}) Y . append ( Y J + 1 )
5: end for
6: return Y = [ Y 1 , Y 2 , … ] \mathcal{Y} = [Y_1,Y_2,\ldots] Y = [ Y 1 , Y 2 , … ]
As we will see later in the proof of the upper bound, traversing enough steps along the winner chain Y \mathcal{Y} Y μ \mu μ
Unbounded K K K In the case of unbounded K K K R ε R_{\varepsilon} R ε μ \mu μ n n n σ \sigma σ ε \varepsilon ε C C C S ( R ) S(R) S ( R ) μ \mu μ K K K K K K
The localization set S ( R ) S(R) S ( R ) K K K
Definition A.2 (Localization Set). For each fixed ν \nu ν and i ∈ [ N ] i \in[N] i ∈ [ N ] let event E ν , i ( R ) : = { ∥ X i − ν ∥ > R } E_{\nu,i}(R) := \{\lVert X_i-\nu\rVert> R\} E ν , i ( R ) := {∥ X i − ν ∥ > R } and define
S ( R ) : = { ν ∈ K : ∑ i = 1 N 1 ( E ν , i ( R ) ) < N / 2 } . S(R) := \left\{\nu\in K : \sum_{i=1}^{N} \mathbf{1}(E_{\nu,i}(R)) < N/2\right\}. S ( R ) := { ν ∈ K : i = 1 ∑ N 1 ( E ν , i ( R )) < N /2 } . Thus, S ( R ) S(R) S ( R ) R R R
Unlike [13 ] , where they used the threshold ≤ N / 2 − 1 \le N/2-1 ≤ N /2 − 1 < N / 2 < N/2 < N /2 N N N
The set S ( R ) S(R) S ( R ) [13 ] [Lemmas 5.2 and 5.4]:
S ( R ) S(R) S ( R ) R R R S ( R 1 ) ⊆ S ( R 2 ) S(R_1) \subseteq S(R_2) S ( R 1 ) ⊆ S ( R 2 ) R 1 < R 2 R_1 < R_2 R 1 < R 2
diam ( S ( R ) ) ≤ 2 R \operatorname{diam}(S(R)) \le2R diam ( S ( R )) ≤ 2 R
The countable packing of K K K K K K K K K [13 ] [Remark 5.13] that the minimax rate remains unchanged with the closure replacement. The constant adjustment in the argument is also universal and do not involve ε \varepsilon ε m : = R ε c / 2 − 1 m := \frac{R_{\varepsilon}}{c/2-1} m := c /2 − 1 R ε c c c m m m 2 m 2m 2 m S m S_m S m K K K K K K s s s d = d m = 2 m + 2 R ε d=d_m=2m+2R_{\varepsilon} d = d m = 2 m + 2 R ε B ( s , d m ) ∩ K B(s,d_m)\cap K B ( s , d m ) ∩ K G s \mathcal{G}^s G s L s ( J ) \mathcal{L}^s(\mathcal{J}) L s ( J ) s s s s s s { G s : s ∈ S m } \{G^s:s\in S_m\} { G s : s ∈ S m } G s G^s G s
The output for the unbounded K K K
If S ( R ε ) = ∅ S(R_\varepsilon)=\varnothing S ( R ε ) = ∅ S ( R ^ ) S(\widehat{R}) S ( R ) R ^ = inf { R ≥ 0 : S ( R ) ≠ ∅ } \widehat{R}=\inf\{R\ge0:S(R)\ne\varnothing\} R = inf { R ≥ 0 : S ( R ) = ∅ }
If S ( R ε ) ≠ ∅ S(R_\varepsilon)\ne\varnothing S ( R ε ) = ∅ s ∈ S m s\in S_m s ∈ S m s s s S ( R ε ) S(R_\varepsilon) S ( R ε ) G s G^s G s Y s = [ Y 1 s , Y 2 s , … ] \mathcal{Y}^s=[Y^s_1,Y^s_2,\ldots] Y s = [ Y 1 s , Y 2 s , … ]
Proof of Examples
The computation for unconstrained K K K K K K δ ε ∗ \delta_\varepsilon^* δ ε ∗ ℓ 1 \ell_1 ℓ 1
Proof of ℓ 1 \ell_1 ℓ 1 It suffices to compute the critical local metric entropy radius δ ε ∗ \delta_\varepsilon^* δ ε ∗ ℓ 1 \ell_1 ℓ 1
log M B 1 ( R ) loc ( r , c ) ≍ { case 1: n , if r ≤ R / n , case 2: R 2 r 2 log e n r 2 R 2 , if R / n < r ≤ R . \log M_{B_1(R)}^{\operatorname{loc}}(r,c)\asymp
\begin{cases}
\text{case 1: } n, & \text{if } r\le R/\sqrt{n},\\
\text{case 2: } \dfrac{R^2}{r^2}\log\dfrac{enr^2}{R^2}, & \text{if } R/\sqrt{n}<r\le R.
\end{cases} log M B 1 ( R ) loc ( r , c ) ≍ ⎩ ⎨ ⎧ case 1: n , case 2: r 2 R 2 log R 2 e n r 2 , if r ≤ R / n , if R / n < r ≤ R . which corresponds to the following regimes of the critical local metric entropy radius δ ε ∗ \delta_\varepsilon^* δ ε ∗
{ case 1: δ ε ∗ 2 ≲ n N ( 1 − 2 ε ) σ 2 , if δ ε ∗ ≤ R n , case 2: log ( e n δ ε ∗ 2 / R 2 ) ( e n δ ε ∗ 2 / R 2 ) ≲ N ( 1 − 2 ε ) R 2 σ 2 1 n 2 , if R n < δ ε ∗ < R . \begin{cases}
\text{case 1: } \delta_\varepsilon^{*2}\lesssim\dfrac{n}{N(1-2\varepsilon)}\sigma^2, & \text{if } \delta_\varepsilon^*\le\dfrac{R}{\sqrt{n}},\\
\text{case 2: } \dfrac{\log(en\delta_\varepsilon^{*2}/R^2)}{(en\delta_\varepsilon^{*2}/R^2)}\lesssim\dfrac{N(1-2\varepsilon)R^2}{\sigma^2}\dfrac{1}{n^2}, & \text{if } \dfrac{R}{\sqrt{n}}<\delta_\varepsilon^*<R.
\end{cases} ⎩ ⎨ ⎧ case 1: δ ε ∗ 2 ≲ N ( 1 − 2 ε ) n σ 2 , case 2: ( e n δ ε ∗ 2 / R 2 ) log ( e n δ ε ∗ 2 / R 2 ) ≲ σ 2 N ( 1 − 2 ε ) R 2 n 2 1 , if δ ε ∗ ≤ n R , if n R < δ ε ∗ < R . Solving the above equations gives
δ ε ∗ 2 ∧ R 2 ≍ { R 2 log ( e n / λ ) λ , log e n < λ < n 2 , R 2 n λ , λ ≥ n 2 . \delta_\varepsilon^{*2}\wedge R^2\asymp
\begin{cases}
R^2\sqrt{\dfrac{\log(en/\sqrt{\lambda})}{\lambda}}, & \log en<\lambda<n^2,\\
R^2\dfrac{n}{\lambda}, & \lambda\ge n^2.
\end{cases} δ ε ∗ 2 ∧ R 2 ≍ ⎩ ⎨ ⎧ R 2 λ log ( e n / λ ) , R 2 λ n , log e n < λ < n 2 , λ ≥ n 2 . where λ : = N ( 1 − 2 ε ) R 2 σ 2 \lambda:=\dfrac{N(1-2\varepsilon)R^2}{\sigma^2} λ := σ 2 N ( 1 − 2 ε ) R 2 λ ≤ log e n \lambda\le\log en λ ≤ log e n
log ( 2 n ) ≥ log ( e n ) / 4 ≥ λ / 4 = N ( 1 − 2 ε ) ( R / 2 ) 2 σ 2 . \log(2n)\ge\log(en)/4\ge\lambda/4=\dfrac{N(1-2\varepsilon)(R/2)^2}{\sigma^2}. log ( 2 n ) ≥ log ( e n ) /4 ≥ λ /4 = σ 2 N ( 1 − 2 ε ) ( R /2 ) 2 . On the other hand, since { ± ( R / 2 ) e ^ i : i ∈ [ n ] } ⊂ B 1 ( R ) ∩ B ( 0 , R / 2 ) \{\pm(R/2)\hat{e}_i:i\in[n]\}\subset B_1(R)\cap B(0,R/2) { ± ( R /2 ) e ^ i : i ∈ [ n ]} ⊂ B 1 ( R ) ∩ B ( 0 , R /2 ) log M B 1 ( R ) loc ( R / 2 , c ) ≥ log 2 n \log M_{B_1(R)}^{\operatorname{loc}}(R/2,c)\ge\log2n log M B 1 ( R ) loc ( R /2 , c ) ≥ log 2 n c c c δ ε ∗ ≥ R / 2 \delta_\varepsilon^*\ge R/2 δ ε ∗ ≥ R /2 δ ε ∗ 2 ∧ R 2 ≍ R 2 \delta_\varepsilon^{*2}\wedge R^2\asymp R^2 δ ε ∗ 2 ∧ R 2 ≍ R 2
Proof of Lower Bound
Proof of Lemma 2.1. Let N 0 : = N − 2 k N_0 := N - 2k N 0 := N − 2 k C π \mathcal{C}_{\pi} C π
The corruption algorithm does the following: First we keep N 0 N_0 N 0 Z : = X ~ 1 : N 0 Z := \widetilde{X}_{1:N_0} Z := X 1 : N 0 V V V X ~ 1 : N 0 \widetilde{X}_{1:N_0} X 1 : N 0
π Z ( v ) : = P ( V = v ∣ Z ) = π ( v ) ∏ i = 1 N 0 f μ v ( X ~ i ) ∑ v ′ ∈ [ M ] π ( v ′ ) ∏ i = 1 N 0 f μ v ′ ( X ~ i ) , v ∈ [ M ] , \pi_Z(v) := \mathbb{P}(V = v \mid Z) = \frac{\pi(v)\prod_{i=1}^{N_0} f_{\mu_v}(\widetilde{X}_i)}{\sum_{v'\in[M]} \pi(v')\prod_{i=1}^{N_0} f_{\mu_{v'}}(\widetilde{X}_i)}, \qquad v \in[M], π Z ( v ) := P ( V = v ∣ Z ) = ∑ v ′ ∈ [ M ] π ( v ′ ) ∏ i = 1 N 0 f μ v ′ ( X i ) π ( v ) ∏ i = 1 N 0 f μ v ( X i ) , v ∈ [ M ] , where f μ v = ϕ ( ⋅ , μ v , σ 2 I n ) f_{\mu_v} = \phi(\cdot,\mu_v,\sigma^2 I_n) f μ v = ϕ ( ⋅ , μ v , σ 2 I n ) N ( μ v , σ 2 I n ) \mathcal{N}(\mu_v,\sigma^2 I_n) N ( μ v , σ 2 I n ) V ′ ∼ π Z V' \sim\pi_Z V ′ ∼ π Z
V , V ′ ∣ Z ∼ i . i . d . π Z . V,V'\mid Z \overset{\mathrm{i.i.d.}}{\sim} \pi_Z. V , V ′ ∣ Z ∼ i.i.d. π Z . On the remaining 2 k 2k 2 k k k k ( X ~ j , X ~ j + 1 ) (\widetilde{X}_j,\widetilde{X}_{j+1}) ( X j , X j + 1 ) P μ V ⊗ P μ V P_{\mu_V}\otimes P_{\mu_V} P μ V ⊗ P μ V V V V j = N 0 + 1 , N 0 + 3 , … , N − 1 j=N_0+1,N_0+3,\ldots,N-1 j = N 0 + 1 , N 0 + 3 , … , N − 1 P μ V ′ P_{\mu_{V'}} P μ V ′
( X j , X j + 1 ) ∣ V , V ′ ∼ 1 2 ( P μ V ⊗ P μ V ′ + P μ V ′ ⊗ P μ V ) : = S V , V ′ . (X_j,X_{j+1})\mid V,V' \sim\frac{1}{2}\left(P_{\mu_V}\otimes P_{\mu_{V'}}+P_{\mu_{V'}}\otimes P_{\mu_V}\right) := S_{V,V'}. ( X j , X j + 1 ) ∣ V , V ′ ∼ 2 1 ( P μ V ⊗ P μ V ′ + P μ V ′ ⊗ P μ V ) := S V , V ′ . As a result, within the 2 k 2k 2 k k k k k k k Y ∈ R 2 k × n Y\in\mathbb{R}^{2k\times n} Y ∈ R 2 k × n X 1 : N = ( Z , Y ) X_{1:N}=(Z,Y) X 1 : N = ( Z , Y ) V , V ′ V,V' V , V ′ Z Z Z Y Y Y V V V V ′ V' V ′ S v , v ′ = S v ′ , v S_{v,v'}=S_{v',v} S v , v ′ = S v ′ , v v , v ′ ∈ [ M ] v,v'\in[M] v , v ′ ∈ [ M ]
( V , V ′ , Y ) ∣ Z = d ( V ′ , V , Y ) ∣ Z . (6) (V,V',Y)\mid Z \overset{\mathrm{d}}{=} (V',V,Y)\mid Z. \tag*{(6)} ( V , V ′ , Y ) ∣ Z = d ( V ′ , V , Y ) ∣ Z . (6) Putting the above together we have for any estimator μ ^ : R N × n → R n \widehat{\mu}:\mathbb{R}^{N\times n}\to\mathbb{R}^n μ : R N × n → R n
E X ~ , C [ ∥ μ ^ ( X 1 : N ) − μ V ∥ 2 ] = E Z [ E V , V ′ , Y ∣ Z [ ∥ μ ^ ( Z , Y ) − μ V ∥ 2 ∣ Z ] ] = ( i ) E Z [ E V , V ′ , Y ∣ Z [ ∥ μ ^ ( Z , Y ) − μ V ′ ∥ 2 ∣ Z ] ] , \mathbb{E}_{\widetilde{X},\mathcal{C}}\left[\left\|\widehat{\mu}(X_{1:N})-\mu_V\right\|^2\right]
=\mathbb{E}_Z\left[\mathbb{E}_{V,V',Y\mid Z}\left[\left\|\widehat{\mu}(Z,Y)-\mu_V\right\|^2\mid Z\right]\right]
\overset{(i)}{=}\mathbb{E}_Z\left[\mathbb{E}_{V,V',Y\mid Z}\left[\left\|\widehat{\mu}(Z,Y)-\mu_{V'}\right\|^2\mid Z\right]\right], E X , C [ ∥ μ ( X 1 : N ) − μ V ∥ 2 ] = E Z [ E V , V ′ , Y ∣ Z [ ∥ μ ( Z , Y ) − μ V ∥ 2 ∣ Z ] ] = ( i ) E Z [ E V , V ′ , Y ∣ Z [ ∥ μ ( Z , Y ) − μ V ′ ∥ 2 ∣ Z ] ] , where (i) by Equation C.1. Rearranging and using the parallelogram identity we have
E X ~ , C [ ∥ μ ^ ( X 1 : N ) − μ V ∥ 2 ] = 1 2 E X ~ , C [ ∥ μ ^ ( X 1 : N ) − μ V ∥ 2 + ∥ μ ^ ( X 1 : N ) − μ V ′ ∥ 2 ] ≥ 1 4 E X ~ , C [ ∥ μ V − μ V ′ ∥ 2 ] . \mathbb{E}_{\widetilde{X},\mathcal{C}}\left[\left\|\widehat{\mu}(X_{1:N})-\mu_V\right\|^2\right]
=\frac{1}{2}\mathbb{E}_{\widetilde{X},\mathcal{C}}\left[\left\|\widehat{\mu}(X_{1:N})-\mu_V\right\|^2+\left\|\widehat{\mu}(X_{1:N})-\mu_{V'}\right\|^2\right]
\geq\frac{1}{4}\mathbb{E}_{\widetilde{X},\mathcal{C}}\left[\left\|\mu_V-\mu_{V'}\right\|^2\right]. E X , C [ ∥ μ ( X 1 : N ) − μ V ∥ 2 ] = 2 1 E X , C [ ∥ μ ( X 1 : N ) − μ V ∥ 2 + ∥ μ ( X 1 : N ) − μ V ′ ∥ 2 ] ≥ 4 1 E X , C [ ∥ μ V − μ V ′ ∥ 2 ] . For the right-hand side we have
E V , V ′ ∣ Z [ ∥ μ V − μ V ′ ∥ 2 ∣ Z ] = E V , V ′ ∣ Z [ ∥ μ V − E V ∣ Z [ μ V ∣ Z ] + E V ∣ Z [ μ V ∣ Z ] − μ V ′ ∥ 2 ∣ Z ] \mathbb{E}_{V,V'\mid Z}\left[\left\|\mu_V-\mu_{V'}\right\|^2\mid Z\right]
=\mathbb{E}_{V,V'\mid Z}\left[\left\|\mu_V-\mathbb{E}_{V\mid Z}[\mu_V\mid Z]+\mathbb{E}_{V\mid Z}[\mu_V\mid Z]-\mu_{V'}\right\|^2\mid Z\right] E V , V ′ ∣ Z [ ∥ μ V − μ V ′ ∥ 2 ∣ Z ] = E V , V ′ ∣ Z [ μ V − E V ∣ Z [ μ V ∣ Z ] + E V ∣ Z [ μ V ∣ Z ] − μ V ′ 2 ∣ Z ] = ( i ) 2 E V ∣ Z [ ∥ μ V − E V ∣ Z [ μ V ∣ Z ] ∥ 2 ∣ Z ] + 2 E V , V ′ ∣ Z [ ⟨ μ V − E V ∣ Z [ μ V ∣ Z ] , E V ∣ Z [ μ V ∣ Z ] − μ V ′ ⟩ ∣ Z ] , \overset{(i)}{=}2\mathbb{E}_{V\mid Z}\left[\left\|\mu_V-\mathbb{E}_{V\mid Z}[\mu_V\mid Z]\right\|^2\mid Z\right]
+2\mathbb{E}_{V,V'\mid Z}\left[\left\langle\mu_V-\mathbb{E}_{V\mid Z}[\mu_V\mid Z],\mathbb{E}_{V\mid Z}[\mu_V\mid Z]-\mu_{V'}\right\rangle\mid Z\right], = ( i ) 2 E V ∣ Z [ μ V − E V ∣ Z [ μ V ∣ Z ] 2 ∣ Z ] + 2 E V , V ′ ∣ Z [ ⟨ μ V − E V ∣ Z [ μ V ∣ Z ] , E V ∣ Z [ μ V ∣ Z ] − μ V ′ ⟩ ∣ Z ] , where the second term equals 0 0 0 ( i ) (i) ( i ) V , V ′ V,V' V , V ′ Z Z Z Z Z Z
E X ~ , C [ ∥ μ ^ ( X 1 : N ) − μ V ∥ 2 ] ≥ 1 2 E Z E V ∣ Z [ ∥ μ V − E V ∣ Z [ μ V ∣ Z ] ∥ 2 ∣ Z ] . (7) \mathbb{E}_{\widetilde{X},C}\left[\lVert\hat{\mu}(X_{1:N})-\mu_V\rVert^2\right]\ge\frac{1}{2}\mathbb{E}_Z\mathbb{E}_{V\mid Z}\left[\lVert\mu_V-\mathbb{E}_{V\mid Z}[\mu_V\mid Z]\rVert^2\mid Z\right]. \tag*{(7)} E X , C [ ∥ μ ^ ( X 1 : N ) − μ V ∥ 2 ] ≥ 2 1 E Z E V ∣ Z [ ∥ μ V − E V ∣ Z [ μ V ∣ Z ] ∥ 2 ∣ Z ] . (7) For the Bayesian risk of clean data of size N 0 N_0 N 0 R c l e a n ( N 0 , π ) R_{\mathrm{clean}}(N_0,\pi) R clean ( N 0 , π ) E V ∣ Z [ μ V ∣ Z ] \mathbb{E}_{V\mid Z}[\mu_V\mid Z] E V ∣ Z [ μ V ∣ Z ]
R c l e a n ( N 0 , π ) = E Z E V ∣ Z [ ∥ μ V − E V ∣ Z [ μ V ∣ Z ] ∥ 2 ∣ Z ] , R_{\mathrm{clean}}(N_0,\pi)=\mathbb{E}_Z\mathbb{E}_{V\mid Z}\left[\lVert\mu_V-\mathbb{E}_{V\mid Z}[\mu_V\mid Z]\rVert^2\mid Z\right], R clean ( N 0 , π ) = E Z E V ∣ Z [ ∥ μ V − E V ∣ Z [ μ V ∣ Z ] ∥ 2 ∣ Z ] , where the first argument N 0 = N − 2 k N_0=N-2k N 0 = N − 2 k Z Z Z
Lemma C.1 (Local Packing Lower Bound). Let c c c Appendix § 5 . Then for any η \eta η log M l o c ( η , c ) > 4 ( N − 2 k 2 σ 2 η 2 ∨ log 2 ) \log M^{\mathrm{loc}}(\eta,c)>4\left(\frac{N-2k}{2\sigma^2}\eta^2\vee\log2\right) log M loc ( η , c ) > 4 ( 2 σ 2 N − 2 k η 2 ∨ log 2 )
M ≥ η 2 16 c 2 . \mathfrak{M}\ge\frac{\eta^2}{16c^2}. M ≥ 16 c 2 η 2 . Proof. The proof follows from Fano’s method and then using Lemma 2.1.
Let notations be as in Lemma 2.1. Set μ 1 , … , μ M \mu_1,\ldots,\mu_M μ 1 , … , μ M M = M l o c ( η , c ) M=M^{\mathrm{loc}}(\eta,c) M = M loc ( η , c ) π \pi π [ M ] [M] [ M ] [14 ] [Proposition 15.1, Equation 15.31], we have
R c l e a n ( N 0 , π ) ≥ η 2 4 c 2 { 1 − I ( X ~ 1 : N 0 ; V ) + log 2 log M } , R_{\mathrm{clean}}(N_0,\pi)\ge\frac{\eta^2}{4c^2}\left\{1-\frac{I(\widetilde{X}_{1:N_0};V)+\log2}{\log M}\right\}, R clean ( N 0 , π ) ≥ 4 c 2 η 2 { 1 − log M I ( X 1 : N 0 ; V ) + log 2 } , where I ( X ~ 1 : N 0 ; V ) I(\widetilde{X}_{1:N_0};V) I ( X 1 : N 0 ; V ) X ~ 1 : N 0 \widetilde{X}_{1:N_0} X 1 : N 0 V V V N ( μ v , σ 2 I n ) \mathcal{N}(\mu_v,\sigma^2 I_n) N ( μ v , σ 2 I n )
I ( X ~ 1 : N 0 ; V ) ≤ 1 M ∑ v = 1 M D K L ( P μ v ⊗ N 0 ∥ Q ⊗ N 0 ) = N 0 2 σ 2 M ∑ v = 1 M ∥ μ v − μ ˉ ∥ 2 ≤ N 0 2 σ 2 η 2 . \begin{aligned}
I(\widetilde{X}_{1:N_0};V)&\le\frac{1}{M}\sum_{v=1}^{M}D_{\mathrm{KL}}\left(P_{\mu_v}^{\otimes N_0}\middle\|Q^{\otimes N_0}\right)\\
&=\frac{N_0}{2\sigma^2M}\sum_{v=1}^{M}\lVert\mu_v-\bar{\mu}\rVert^2\\
&\le\frac{N_0}{2\sigma^2}\eta^2.
\end{aligned} I ( X 1 : N 0 ; V ) ≤ M 1 v = 1 ∑ M D KL ( P μ v ⊗ N 0 Q ⊗ N 0 ) = 2 σ 2 M N 0 v = 1 ∑ M ∥ μ v − μ ˉ ∥ 2 ≤ 2 σ 2 N 0 η 2 . using [13 ] [Lemma A.2], where Q = N ( μ ˉ , σ 2 I n ) Q=\mathcal{N}(\bar{\mu},\sigma^2 I_n) Q = N ( μ ˉ , σ 2 I n ) μ ˉ = 1 M ∑ v = 1 M μ v \bar{\mu}=\frac{1}{M}\sum_{v=1}^{M}\mu_v μ ˉ = M 1 ∑ v = 1 M μ v
Putting the above together, we have
log M > 4 ( N − 2 k 2 σ 2 η 2 ∨ log 2 ) ≥ 2 ( N − 2 k 2 σ 2 η 2 + log 2 ) ≥ 2 ( I ( X ~ 1 : N 0 ; V ) + log 2 ) . \log M>4\left(\frac{N-2k}{2\sigma^2}\eta^2\vee\log2\right)\ge2\left(\frac{N-2k}{2\sigma^2}\eta^2+\log2\right)\ge2\left(I(\widetilde{X}_{1:N_0};V)+\log2\right). log M > 4 ( 2 σ 2 N − 2 k η 2 ∨ log 2 ) ≥ 2 ( 2 σ 2 N − 2 k η 2 + log 2 ) ≥ 2 ( I ( X 1 : N 0 ; V ) + log 2 ) . Then substituting this into the lower bound of R c l e a n ( N 0 , π ) R_{\mathrm{clean}}(N_0,\pi) R clean ( N 0 , π )
M ≥ inf μ ^ R c o r r u p t ( μ ^ , C , π ) ≥ 1 2 R c l e a n ( N − 2 k , π ) ≥ η 2 16 c 2 . \mathfrak{M}\ge\inf_{\hat{\mu}}R_{\mathrm{corrupt}}(\hat{\mu},\mathcal{C},\pi)\ge\frac{1}{2}R_{\mathrm{clean}}(N-2k,\pi)\ge\frac{\eta^2}{16c^2}. M ≥ μ ^ inf R corrupt ( μ ^ , C , π ) ≥ 2 1 R clean ( N − 2 k , π ) ≥ 16 c 2 η 2 . :::
The following characterizes the maximum separation of two Gaussian distributions given a total variation distance constraint. It is a direct result from [9 ] [Appendix E, Proposition 8], with a proper renotation adjustment.
Lemma C.2 (Maximum Separation of Two Gaussians). Let η ∈ ( 1 / 4 , 1 / 2 ) \eta\in(1/4,1/2) η ∈ ( 1/4 , 1/2 ) σ > 0 \sigma> 0 σ > 0
ω ( η ) : = sup { ∣ θ 1 − θ 2 ∣ σ : d T V ( N ( θ 1 , σ 2 ) , N ( θ 2 , σ 2 ) ) ≤ 2 η } . \omega(\eta) := \sup\left\{\frac{\lvert\theta_1-\theta_2\rvert}{\sigma} : d_{\mathrm{TV}}\left(\mathcal{N}(\theta_1,\sigma^2),\mathcal{N}(\theta_2,\sigma^2)\right) \le2\eta\right\}. ω ( η ) := sup { σ ∣ θ 1 − θ 2 ∣ : d TV ( N ( θ 1 , σ 2 ) , N ( θ 2 , σ 2 ) ) ≤ 2 η } . Then we have
ω ( η ) ≥ 2 log ( 1 2 ( 1 − 2 η ) ) . \omega(\eta) \ge\sqrt{2\log\left(\frac{1}{2(1-2\eta)}\right)}. ω ( η ) ≥ 2 log ( 2 ( 1 − 2 η ) 1 ) . Corollary C.1. Let η ∈ ( 1 / 4 , 1 / 2 ) \eta\in(1/4,1/2) η ∈ ( 1/4 , 1/2 ) σ > 0 \sigma> 0 σ > 0 θ 1 , θ 2 ∈ R n \theta_1,\theta_2 \in\mathbb{R}^n θ 1 , θ 2 ∈ R n ∥ θ 1 − θ 2 ∥ 2 ≤ σ 2 ∨ 2 σ 2 log ( 1 2 ( 1 − 2 η ) ) \lVert\theta_1-\theta_2\rVert^2 \le\sigma^2 \vee2\sigma^2\log\left(\frac{1}{2(1-2\eta)}\right) ∥ θ 1 − θ 2 ∥ 2 ≤ σ 2 ∨ 2 σ 2 log ( 2 ( 1 − 2 η ) 1 )
d T V ( N ( θ 1 , σ 2 I n ) , N ( θ 2 , σ 2 I n ) ) ≤ 2 η . d_{\mathrm{TV}}\left(\mathcal{N}(\theta_1,\sigma^2 I_n),\mathcal{N}(\theta_2,\sigma^2 I_n)\right) \le2\eta. d TV ( N ( θ 1 , σ 2 I n ) , N ( θ 2 , σ 2 I n ) ) ≤ 2 η . We also note that σ 2 ∨ 2 σ 2 log ( 1 2 ( 1 − 2 η ) ) ≲ σ 2 log ( 1 1 − 2 η ) \sigma^2 \vee2\sigma^2\log\left(\frac{1}{2(1-2\eta)}\right) \lesssim\sigma^2\log\left(\frac{1}{1-2\eta}\right) σ 2 ∨ 2 σ 2 log ( 2 ( 1 − 2 η ) 1 ) ≲ σ 2 log ( 1 − 2 η 1 ) η ∈ ( 1 / 4 , 1 / 2 ) \eta\in(1/4,1/2) η ∈ ( 1/4 , 1/2 )
Proof. By the rotational invariance of the total variation distance and the tensorization property that
d T V ( P × S , Q × S ) = d T V ( P , Q ) , d_{\mathrm{TV}}(P \times S,Q \times S) = d_{\mathrm{TV}}(P,Q), d TV ( P × S , Q × S ) = d TV ( P , Q ) , the preceding lemma can be extended to the multivariate case:
∥ θ 1 − θ 2 ∥ 2 ≤ 2 σ 2 log ( 1 2 ( 1 − 2 η ) ) . \lVert\theta_1-\theta_2\rVert^2 \le2\sigma^2\log\left(\frac{1}{2(1-2\eta)}\right). ∥ θ 1 − θ 2 ∥ 2 ≤ 2 σ 2 log ( 2 ( 1 − 2 η ) 1 ) . On the other hand, by Pinsker’s inequality and the KL divergence formula for Gaussian distributions, we have
d T V ( N ( θ 1 , σ 2 I n ) , N ( θ 2 , σ 2 I n ) ) ≤ 1 2 D K L ( N ( θ 1 , σ 2 I n ) ∥ N ( θ 2 , σ 2 I n ) ) = ∥ θ 1 − θ 2 ∥ 2 σ . d_{\mathrm{TV}}\left(\mathcal{N}(\theta_1,\sigma^2 I_n),\mathcal{N}(\theta_2,\sigma^2 I_n)\right)
\le\sqrt{\frac{1}{2}D_{\mathrm{KL}}\left(\mathcal{N}(\theta_1,\sigma^2 I_n)\mathbin{\|}\mathcal{N}(\theta_2,\sigma^2 I_n)\right)}
= \frac{\lVert\theta_1-\theta_2\rVert}{2\sigma}. d TV ( N ( θ 1 , σ 2 I n ) , N ( θ 2 , σ 2 I n ) ) ≤ 2 1 D KL ( N ( θ 1 , σ 2 I n ) ∥ N ( θ 2 , σ 2 I n ) ) = 2 σ ∥ θ 1 − θ 2 ∥ . meaning that if ∥ θ 1 − θ 2 ∥ 2 ≤ σ 2 \lVert\theta_1-\theta_2\rVert^2 \le\sigma^2 ∥ θ 1 − θ 2 ∥ 2 ≤ σ 2 d T V ( N ( θ 1 , σ 2 I n ) , N ( θ 2 , σ 2 I n ) ) ≤ 1 / 2 < 2 η d_{\mathrm{TV}}\left(\mathcal{N}(\theta_1,\sigma^2 I_n),\mathcal{N}(\theta_2,\sigma^2 I_n)\right) \le1/2 < 2\eta d TV ( N ( θ 1 , σ 2 I n ) , N ( θ 2 , σ 2 I n ) ) ≤ 1/2 < 2 η η ∈ ( 1 / 4 , 1 / 2 ) \eta\in(1/4,1/2) η ∈ ( 1/4 , 1/2 ) □ \square □
Proof of Lemma 2.2. For the two hypotheses b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } μ 0 \mu_0 μ 0 μ 1 \mu_1 μ 1 P b P_b P b P ‾ = 1 2 ( P 0 + P 1 ) \overline{P} = \frac{1}{2}(P_0+P_1) P = 2 1 ( P 0 + P 1 )
d T V ( P 0 , P ‾ ) = d T V ( P 1 , P ‾ ) = 1 2 d T V ( P 0 , P 1 ) ≤ ϵ − . d_{\mathrm{TV}}(P_0,\overline{P}) = d_{\mathrm{TV}}(P_1,\overline{P}) = \frac{1}{2}d_{\mathrm{TV}}(P_0,P_1) \le\epsilon_-. d TV ( P 0 , P ) = d TV ( P 1 , P ) = 2 1 d TV ( P 0 , P 1 ) ≤ ϵ − . The adversarial algorithm C b C_b C b X ~ i ∼ P b \widetilde{X}_i \sim P_b X i ∼ P b ( X ~ i , Y i ) (\widetilde{X}_i,Y_i) ( X i , Y i ) P ‾ \overline{P} P
X ~ i ∼ P b , Y i ∼ P ‾ , P ( X ~ i ≠ Y i ) = d T V ( P b , P ‾ ) ≤ ε − . \widetilde{X}_i \sim P_b,\quad Y_i \sim\overline{P},\quad\mathbb{P}\left(\widetilde{X}_i \ne Y_i\right)=d_{\mathrm{TV}}(P_b,\overline{P})\leq\varepsilon_-. X i ∼ P b , Y i ∼ P , P ( X i = Y i ) = d TV ( P b , P ) ≤ ε − . This can be done by accept-reject sampling. Then we count the number of disagreements between X ~ i \widetilde{X}_i X i Y i Y_i Y i
B i : = 1 ( X ~ i ≠ Y i ) ∼ Bernoulli ( d T V ( P b , P ‾ ) ) , B_i := \mathbb{1}(\widetilde{X}_i \ne Y_i)\sim\operatorname{Bernoulli}\left(d_{\mathrm{TV}}(P_b,\overline{P})\right), B i := 1 ( X i = Y i ) ∼ Bernoulli ( d TV ( P b , P ) ) , and let B = ∑ i = 1 N B i B=\sum_{i=1}^{N}B_i B = ∑ i = 1 N B i i ∈ [ N ] i\in[N] i ∈ [ N ] B ∼ Binom ( N , d T V ( P b , P ‾ ) ) B\sim\operatorname{Binom}(N,d_{\mathrm{TV}}(P_b,\overline{P})) B ∼ Binom ( N , d TV ( P b , P ))
The adversarial algorithm C b C_b C b
If B ≤ k B\leq k B ≤ k X ~ i \widetilde{X}_i X i Y i Y_i Y i
If B > k B>k B > k
We remark that in the first case, only at most k k k X 1 : N X_{1:N} X 1 : N P ~ b ( N ) \widetilde{P}_b^{(N)} P b ( N ) B B B
P ( B > k ) ≤ ( i ) P ( Binom ( N , ε − ) > k ) = P ( Binom ( N , ε − ) > N ε − + a N ) \begin{aligned}
\mathbb{P}(B>k)\mathrel{\mathop{\leq}^{(i)}}\mathbb{P}\left(\operatorname{Binom}(N,\varepsilon_-)>k\right) \\
&=\mathbb{P}\left(\operatorname{Binom}(N,\varepsilon_-)>N\varepsilon_-+a\sqrt{N}\right)
\end{aligned} P ( B > k ) ≤ ( i ) P ( Binom ( N , ε − ) > k ) = P ( Binom ( N , ε − ) > N ε − + a N ) ≤ ( i i ) exp [ − 2 a 2 ] \mathrel{\mathop{\leq}^{(ii)}}\exp\left[-2a^2\right] ≤ ( ii ) exp [ − 2 a 2 ] < ( i i i ) 1 / 8 , \mathrel{\mathop{<}^{(iii)}}1/8, < ( iii ) 1/8 , where (i) by the stochastic dominance B ∼ Binom ( N , d T V ( P b , P ‾ ) ) ≤ s t Binom ( N , ε − ) B\sim\operatorname{Binom}(N,d_{\mathrm{TV}}(P_b,\overline{P}))\leq_{\mathrm{st}}\operatorname{Binom}(N,\varepsilon_-) B ∼ Binom ( N , d TV ( P b , P )) ≤ st Binom ( N , ε − ) a a a
d T V ( P ~ b ( N ) , P ‾ ⊗ N ) ≤ P ( X 1 : N ≠ Y 1 : N ) = P ( B > k ) < 1 / 4. d_{\mathrm{TV}}\left(\widetilde{P}_b^{(N)},\overline{P}^{\otimes N}\right)\leq\mathbb{P}(X_{1:N}\ne Y_{1:N})=\mathbb{P}(B>k)<1/4. d TV ( P b ( N ) , P ⊗ N ) ≤ P ( X 1 : N = Y 1 : N ) = P ( B > k ) < 1/4. Then by triangle inequality we have
d T V ( P ~ 0 ( N ) , P ~ 1 ( N ) ) ≤ d T V ( P ~ 0 ( N ) , P ‾ ⊗ N ) + d T V ( P ~ 1 ( N ) , P ‾ ⊗ N ) < 1 / 2 < 1. d_{\mathrm{TV}}\left(\widetilde{P}_0^{(N)},\widetilde{P}_1^{(N)}\right)\leq d_{\mathrm{TV}}\left(\widetilde{P}_0^{(N)},\overline{P}^{\otimes N}\right)+d_{\mathrm{TV}}\left(\widetilde{P}_1^{(N)},\overline{P}^{\otimes N}\right)<1/2<1. d TV ( P 0 ( N ) , P 1 ( N ) ) ≤ d TV ( P 0 ( N ) , P ⊗ N ) + d TV ( P 1 ( N ) , P ⊗ N ) < 1/2 < 1. Then using Le Cam’s two point method [14 ] [Equation 15.14], we have the desired result.
Proof of Lemma 2.3. Let a a a ε − = ε − a / N ≤ 1 / 4 \varepsilon_-=\varepsilon-a/\sqrt{N}\leq1/4 ε − = ε − a / N ≤ 1/4 N N N N ≤ 64 a 2 N\leq64a^2 N ≤ 64 a 2 ε > 3 / 8 \varepsilon>3/8 ε > 3/8 1 − 2 ε ≥ 1 N > 1 64 a 2 1-2\varepsilon\geq\frac{1}{N}>\frac{1}{64a^2} 1 − 2 ε ≥ N 1 > 64 a 2 1 ε \varepsilon ε 1 / 2 1/2 1/2 κ = 1 / ( 128 a 2 ) \kappa=1/(128a^2) κ = 1/ ( 128 a 2 ) ε − > 1 / 4 \varepsilon_->1/4 ε − > 1/4 K K K ε − \varepsilon_{-} ε − Lemma 2.2 . By Lemma A.1[(iii)] and Corollary C.1, there exists μ 0 , μ 1 ∈ K \mu_0,\mu_1 \in K μ 0 , μ 1 ∈ K
∥ μ 0 − μ 1 ∥ 2 = ( σ 2 ∨ 2 σ 2 log 1 2 ( 1 − 2 ε − ) ) ∧ ( d / 3 ) 2 . (8) \lVert\mu_0-\mu_1\rVert^2=\left(\sigma^2\vee2\sigma^2\log\frac{1}{2(1-2\varepsilon_{-})}\right)\wedge(d/3)^2. \tag*{(8)} ∥ μ 0 − μ 1 ∥ 2 = ( σ 2 ∨ 2 σ 2 log 2 ( 1 − 2 ε − ) 1 ) ∧ ( d /3 ) 2 . (8) Consequently, we have d T V ( N ( μ 0 , σ 2 I n ) , N ( μ 1 , σ 2 I n ) ) ≤ 2 ε − d_{\mathrm{TV}}(\mathcal{N}(\mu_0,\sigma^2I_n),\mathcal{N}(\mu_1,\sigma^2I_n))\leq2\varepsilon_{-} d TV ( N ( μ 0 , σ 2 I n ) , N ( μ 1 , σ 2 I n )) ≤ 2 ε −
∥ μ 0 − μ 1 ∥ 2 ≲ σ 2 log 1 1 − 2 ε − ∧ d 2 . \lVert\mu_0-\mu_1\rVert^2\lesssim\sigma^2\log\frac{1}{1-2\varepsilon_{-}}\wedge d^2. ∥ μ 0 − μ 1 ∥ 2 ≲ σ 2 log 1 − 2 ε − 1 ∧ d 2 . Then by applying Lemma 2.2 , we have
M ≳ ∥ μ 0 − μ 1 ∥ 2 ≲ σ 2 log 1 1 − 2 ε − ∧ d 2 . \mathfrak{M}\gtrsim\lVert\mu_0-\mu_1\rVert^2\lesssim\sigma^2\log\frac{1}{1-2\varepsilon_{-}}\wedge d^2. M ≳ ∥ μ 0 − μ 1 ∥ 2 ≲ σ 2 log 1 − 2 ε − 1 ∧ d 2 . It suffices to prove that log 1 1 − 2 ε − ≍ log 1 1 − 2 ε \log\frac{1}{1-2\varepsilon_{-}}\asymp\log\frac{1}{1-2\varepsilon} log 1 − 2 ε − 1 ≍ log 1 − 2 ε 1
Notice that by construction we have ε = k N \varepsilon=\frac{k}{N} ε = N k k < N 2 k<\frac{N}{2} k < 2 N
1 − 2 ε = N − 2 k N ≥ 1 N . 1-2\varepsilon=\frac{N-2k}{N}\geq\frac{1}{N}. 1 − 2 ε = N N − 2 k ≥ N 1 . Now discuss two cases:
1 − 2 ε < 1 − 2 ε − = ( 1 − 2 ε ) + 2 a N ≤ 2 ( 1 − 2 ε ) 1-2\varepsilon<1-2\varepsilon_{-}=(1-2\varepsilon)+\frac{2a}{\sqrt{N}}\leq2(1-2\varepsilon) 1 − 2 ε < 1 − 2 ε − = ( 1 − 2 ε ) + N 2 a ≤ 2 ( 1 − 2 ε ) as a result we have log 1 1 − 2 ε − ≍ log 1 1 − 2 ε \log\frac{1}{1-2\varepsilon_{-}}\asymp\log\frac{1}{1-2\varepsilon} log 1 − 2 ε − 1 ≍ log 1 − 2 ε 1 ε > 3 / 8 \varepsilon>3/8 ε > 3/8
log 1 1 − 2 ε − ≍ log N ≍ log 1 1 − 2 ε . \log\frac{1}{1-2\varepsilon_{-}}\asymp\log N\asymp\log\frac{1}{1-2\varepsilon}. log 1 − 2 ε − 1 ≍ log N ≍ log 1 − 2 ε 1 . Then noticing that ε 2 ≳ 1 \varepsilon^2\gtrsim1 ε 2 ≳ 1 K K K ∥ μ 0 − μ 1 ∥ 2 ≲ σ 2 log 1 1 − 2 ε − \lVert\mu_0-\mu_1\rVert^2\lesssim\sigma^2\log\frac{1}{1-2\varepsilon_{-}} ∥ μ 0 − μ 1 ∥ 2 ≲ σ 2 log 1 − 2 ε − 1
Proof of Theorem 2.2. We prove for the bounded K K K K K K 0 < κ < 1 / 2 0<\kappa<1/2 0 < κ < 1/2 ε ≤ 1 / 2 − κ \varepsilon\leq1/2-\kappa ε ≤ 1/2 − κ
M ≳ max { δ ε ∗ 2 , σ 2 ε 2 log ( e / ( 1 − 2 ε ) ) } ∧ d 2 . \mathfrak{M}\gtrsim\max\{\delta_{\varepsilon}^{*2},\sigma^2\varepsilon^2\log(e/(1-2\varepsilon))\}\wedge d^2. M ≳ max { δ ε ∗ 2 , σ 2 ε 2 log ( e / ( 1 − 2 ε ))} ∧ d 2 . Then it suffices to consider the case when 1 / 2 − κ < ε < 1 / 2 1/2-\kappa<\varepsilon<1/2 1/2 − κ < ε < 1/2 κ = 1 / 8 \kappa=1/8 κ = 1/8 3 / 8 < ε < 1 / 2 3/8<\varepsilon<1/2 3/8 < ε < 1/2
The discussion is split depending on the value of δ ε ∗ \delta_{\varepsilon}^{*} δ ε ∗
If δ ε ∗ = 0 \delta_{\varepsilon}^{*}=0 δ ε ∗ = 0 K K K r r r M l o c ( r , c ) ≥ 2 M^{\mathrm{loc}}(r,c)\geq2 M loc ( r , c ) ≥ 2 c c c ( 1 − 2 ε ) N r 2 / σ 2 → r → 0 0 (1-2\varepsilon)N^{r^2/\sigma^2}\xrightarrow{r\to0}0 ( 1 − 2 ε ) N r 2 / σ 2 r → 0 0 r > 0 r>0 r > 0
( 1 − 2 ε ) N r 2 / σ 2 < log 2 ≤ log M l o c ( r , c ) . (1-2\varepsilon)N^{r^2/\sigma^2}<\log2\leq\log M^{\mathrm{loc}}(r,c). ( 1 − 2 ε ) N r 2 / σ 2 < log 2 ≤ log M loc ( r , c ) . As a result, δ ε ∗ ≥ r > 0 \delta_{\varepsilon}^{*}\geq r>0 δ ε ∗ ≥ r > 0 K K K
If N − 2 k σ 2 δ ε ∗ 2 > 8 log 2 \frac{N-2k}{\sigma^2}\delta_\varepsilon^{*2}>8\log2 σ 2 N − 2 k δ ε ∗ 2 > 8 log 2 δ ε ∗ \delta_\varepsilon^* δ ε ∗ We argue that δ ε ∗ 4 \frac{\delta_\varepsilon^*}{4} 4 δ ε ∗ 0 < r < δ ε ∗ 0<r<\delta_\varepsilon^* 0 < r < δ ε ∗ log M l o c ( r , c ) > ( 1 − 2 ε ) N r 2 σ 2 \log M^{\mathrm{loc}}(r,c)>(1-2\varepsilon)\frac{N r^2}{\sigma^2} log M loc ( r , c ) > ( 1 − 2 ε ) σ 2 N r 2
log M l o c ( δ ε ∗ 4 , c ) ≥ log lim s ↑ δ ε ∗ M l o c ( s , c ) ≥ lim s ↑ δ ε ∗ N − 2 k 2 σ 2 s 2 = N − 2 k 2 σ 2 δ ε ∗ 2 > 4 [ N − 2 k 2 σ 2 ( δ ε ∗ 4 ) 2 ∨ log 2 ] . \log M^{\mathrm{loc}}\left(\frac{\delta_\varepsilon^*}{4},c\right)\ge\log\lim_{s\uparrow\delta_\varepsilon^*}M^{\mathrm{loc}}(s,c)\ge\lim_{s\uparrow\delta_\varepsilon^*}\frac{N-2k}{2\sigma^2}s^2
= \frac{N-2k}{2\sigma^2}\delta_\varepsilon^{*2}>4\left[\frac{N-2k}{2\sigma^2}\left(\frac{\delta_\varepsilon^*}{4}\right)^2\vee\log2\right]. log M loc ( 4 δ ε ∗ , c ) ≥ log s ↑ δ ε ∗ lim M loc ( s , c ) ≥ s ↑ δ ε ∗ lim 2 σ 2 N − 2 k s 2 = 2 σ 2 N − 2 k δ ε ∗ 2 > 4 [ 2 σ 2 N − 2 k ( 4 δ ε ∗ ) 2 ∨ log 2 ] . Then applying Lemma C.1 we have
M ≳ ( δ ε ∗ / 4 ) 2 16 c 2 ≳ δ ε ∗ 2 ≳ δ ε ∗ 2 ∧ d 2 . \mathfrak{M}\gtrsim\frac{(\delta_\varepsilon^*/4)^2}{16c^2}\gtrsim\delta_\varepsilon^{*2}\gtrsim\delta_\varepsilon^{*2}\wedge d^2. M ≳ 16 c 2 ( δ ε ∗ /4 ) 2 ≳ δ ε ∗ 2 ≳ δ ε ∗ 2 ∧ d 2 . Together with Lemma 2.3 we have
M ≳ ( δ ε ∗ 2 ∨ σ 2 ε 2 log ( 1 / ( 1 − 2 ε ) ) ) ∧ d 2 . \mathfrak{M}\gtrsim\left(\delta_\varepsilon^{*2}\vee\sigma^2\varepsilon^2\log(1/(1-2\varepsilon))\right)\wedge d^2. M ≳ ( δ ε ∗ 2 ∨ σ 2 ε 2 log ( 1/ ( 1 − 2 ε )) ) ∧ d 2 . If N − 2 k σ 2 δ ε ∗ 2 ≤ 8 log 2 \frac{N-2k}{\sigma^2}\delta_\varepsilon^{*2}\le8\log2 σ 2 N − 2 k δ ε ∗ 2 ≤ 8 log 2 δ ε ∗ \delta_\varepsilon^* δ ε ∗ By the same argument as in [13 ][proof of Theorem 3.10, case 3] , we have d ≤ 12 δ ε ∗ d\le12\delta_\varepsilon^* d ≤ 12 δ ε ∗ d / 6 d/6 d /6
Choosing c c c
log M l o c ( d 6 , c ) > 64 log 2 ≥ 4 ( 2 N − 2 k σ 2 ( δ ε ∗ ) 2 ∨ 4 log 2 ) ≥ 4 ( N − 2 k 2 σ 2 ( d / 6 ) 2 ∨ log 2 ) . \log M^{\mathrm{loc}}\left(\frac{d}{6},c\right)>64\log2\ge4\left(2\frac{N-2k}{\sigma^2}\left(\delta_\varepsilon^*\right)^2\vee4\log2\right)\ge4\left(\frac{N-2k}{2\sigma^2}(d/6)^2\vee\log2\right). log M loc ( 6 d , c ) > 64 log 2 ≥ 4 ( 2 σ 2 N − 2 k ( δ ε ∗ ) 2 ∨ 4 log 2 ) ≥ 4 ( 2 σ 2 N − 2 k ( d /6 ) 2 ∨ log 2 ) . Thus we can apply Lemma C.1 to get
M ≳ d 2 ≳ δ ε ∗ 2 ∧ d 2 . \mathfrak{M}\gtrsim d^2\gtrsim\delta_\varepsilon^{*2}\wedge d^2. M ≳ d 2 ≳ δ ε ∗ 2 ∧ d 2 . Together with Lemma 2.3 we have
M ≳ ( δ ε ∗ 2 ∨ σ 2 ε 2 log ( 1 / ( 1 − 2 ε ) ) ) ∧ d 2 . \mathfrak{M}\gtrsim\left(\delta_\varepsilon^{*2}\vee\sigma^2\varepsilon^2\log(1/(1-2\varepsilon))\right)\wedge d^2. M ≳ ( δ ε ∗ 2 ∨ σ 2 ε 2 log ( 1/ ( 1 − 2 ε )) ) ∧ d 2 . Constant Calibration Near the Breakdown Point
In [13 ] , their constant setting was done in the regime when ε \varepsilon ε 1 / 2 1/2 1/2 ε \varepsilon ε 1 / 2 1/2 1/2 [13 ][Theorem 3.6] in the near-breakdown regime ε ∈ [ 1 / 4 , 1 / 2 ) \varepsilon\in[1/4,1/2) ε ∈ [ 1/4 , 1/2 ) ε \varepsilon ε § 5 .
We begin by introducing some notations and how they compare to the original definitions in [13 ][Appendix B] . Throughout the proof necessary constants from the original proof are added subscript ε \varepsilon ε ε \varepsilon ε C C C C ′ C' C ′ ρ \rho ρ α ε \alpha_\varepsilon α ε β ε \beta_\varepsilon β ε L ε L_\varepsilon L ε
a ε : = 1 − 2 ε , z ε : = log e a ε = log e 1 − 2 ε , a_\varepsilon:= 1 - 2\varepsilon,\qquad z_\varepsilon:= \log\frac{e}{a_\varepsilon} = \log\frac{e}{1 - 2\varepsilon}, a ε := 1 − 2 ε , z ε := log a ε e = log 1 − 2 ε e , for notational convenience. Additionally, we recall the definitions g : [ 0 , 1 / 2 ) ↦ R g : [0,1/2) \mapsto\mathbb{R} g : [ 0 , 1/2 ) ↦ R h : [ 0 , 1 / 2 ) ↦ R h : [0,1/2) \mapsto\mathbb{R} h : [ 0 , 1/2 ) ↦ R
g ( t ) : = ( 1 2 + t ) log ( 1 2 + t ) + ( 1 2 − t ) log ( 1 − 2 t ) , g(t) := \left(\frac{1}{2} + t\right)\log\left(\frac{1}{2} + t\right) + \left(\frac{1}{2} - t\right)\log(1 - 2t), g ( t ) := ( 2 1 + t ) log ( 2 1 + t ) + ( 2 1 − t ) log ( 1 − 2 t ) , h ( t ) : = t ( 1 − exp [ 4 g ( t ) 1 − 2 t ] ) . h(t) := t\left(1 - \exp\left[\frac{4g(t)}{1 - 2t}\right]\right). h ( t ) := t ( 1 − exp [ 1 − 2 t 4 g ( t ) ] ) . Now we first assess the endpoint behavior of g g g h h h t → 1 / 2 t \to1/2 t → 1/2
Lemma D.1. There exist universal constants Q 1 , Q 2 Q_1,Q_2 Q 1 , Q 2 t ∈ [ 1 / 4 , 1 / 2 ) t \in[1/4,1/2) t ∈ [ 1/4 , 1/2 )
Q 1 log e 1 − 2 t ≤ − 4 g ( t ) 1 − 2 t ≤ Q 2 log e 1 − 2 t , (9) Q_1\log\frac{e}{1-2t}\leq\frac{-4g(t)}{1-2t}\leq Q_2\log\frac{e}{1-2t}, \tag*{(9)} Q 1 log 1 − 2 t e ≤ 1 − 2 t − 4 g ( t ) ≤ Q 2 log 1 − 2 t e , (9) and
Q 1 ( 1 − 2 t ) ≤ 1 − 2 h ( t ) ≤ Q 2 ( 1 − 2 t ) . (10) Q_1(1-2t)\leq1-2h(t)\leq Q_2(1-2t). \tag*{(10)} Q 1 ( 1 − 2 t ) ≤ 1 − 2 h ( t ) ≤ Q 2 ( 1 − 2 t ) . (10) Proof. Set s = 1 − 2 t ∈ ( 0 , 1 / 2 ] s = 1 - 2t \in(0,1/2] s = 1 − 2 t ∈ ( 0 , 1/2 ]
− 4 g ( t ) 1 − 2 t = − 4 ( ( 1 − s / 2 ) log ( 1 − s / 2 ) + ( s / 2 ) log ( s ) ) s = 2 log ( 1 / s ) − 4 1 − s / 2 s log ( 1 − s / 2 ) ⏟ O ( 1 ) on s ∈ ( 0 , 1 / 2 ] \begin{aligned}
\frac{-4g(t)}{1-2t}
= -\frac{4\left((1-s/2)\log(1-s/2)+(s/2)\log(s)\right)}{s} \\
&=2\log(1/s)-4\frac{1-s/2}{s}\log(1-s/2)
\underset{O(1)\ \text{on }s\in(0,1/2]}{\underbrace{\hspace{4cm}}}
\end{aligned} 1 − 2 t − 4 g ( t ) = − s 4 ( ( 1 − s /2 ) log ( 1 − s /2 ) + ( s /2 ) log ( s ) ) = 2 log ( 1/ s ) − 4 s 1 − s /2 log ( 1 − s /2 ) O ( 1 ) on s ∈ ( 0 , 1/2 ] ≍ log ( e / s ) , \asymp\log(e/s), ≍ log ( e / s ) , proving the first inequality. Also, it gives exp ( 4 g ( t ) / ( 1 − 2 t ) ) ≍ s 2 \exp(4g(t)/(1-2t))\asymp s^2 exp ( 4 g ( t ) / ( 1 − 2 t )) ≍ s 2
1 − 2 h ( t ) = s + ( 1 − s ) exp ( 4 g ( t ) / ( 1 − 2 t ) ) ≍ s , 1-2h(t)=s+(1-s)\exp(4g(t)/(1-2t))\asymp s, 1 − 2 h ( t ) = s + ( 1 − s ) exp ( 4 g ( t ) / ( 1 − 2 t )) ≍ s , proving the second inequality. □ \square □
Lemma D.2 (Robust Pairwise Testing Near Breakdown Point). Fix a sufficiently large constant C > 2 C > 2 C > 2 D 1 , Q 0 > 0 D_1,Q_0 > 0 D 1 , Q 0 > 0 ε \varepsilon ε ε = k N ∈ [ 1 / 4 , 1 / 2 ) \varepsilon= \frac{k}{N} \in[1/4,1/2) ε = N k ∈ [ 1/4 , 1/2 ) H 0 : μ ∈ B ( ν 1 , r ) H_0 : \mu\in B(\nu_1,r) H 0 : μ ∈ B ( ν 1 , r ) H 1 : μ ∈ B ( ν 2 , r ) H_1 : \mu\in B(\nu_2,r) H 1 : μ ∈ B ( ν 2 , r ) ∥ ν 1 − ν 2 ∥ ≥ C r \|\nu_1-\nu_2\| \geq Cr ∥ ν 1 − ν 2 ∥ ≥ C r ν 1 , ν 2 ∈ K \nu_1,\nu_2 \in K ν 1 , ν 2 ∈ K r ≥ D 1 ε σ z ε r \geq D_1\varepsilon\sigma\sqrt{z_\varepsilon} r ≥ D 1 ε σ z ε ψ \psi ψ [13 ] [Theorem 3.6] satisfies
sup ∥ μ − ν 1 ∥ ≤ r P μ , C ( ψ = 1 ) ∨ sup ∥ μ − ν 2 ∥ ≤ r P μ , C ( ψ = 0 ) ≤ exp [ − Q 0 a ε N r 2 σ 2 ] , \sup_{\|\mu-\nu_1\|\leq r}\mathbb{P}_{\mu,C}(\psi=1)\vee\sup_{\|\mu-\nu_2\|\leq r}\mathbb{P}_{\mu,C}(\psi=0)\leq\exp\left[-Q_0a_\varepsilon N\frac{r^2}{\sigma^2}\right], ∥ μ − ν 1 ∥ ≤ r sup P μ , C ( ψ = 1 ) ∨ ∥ μ − ν 2 ∥ ≤ r sup P μ , C ( ψ = 0 ) ≤ exp [ − Q 0 a ε N σ 2 r 2 ] , for any admissible adversary C C C k k k
Proof. Let Q 1 , Q 2 Q_1,Q_2 Q 1 , Q 2
C ′ : = C − 2 2 2 π , ϱ : = exp [ − ( C ′ ) 2 r 2 / σ 2 ] , α ε : = 1 2 − Q 3 a ε , C' := \frac{C-2}{2\sqrt{2\pi}}, \qquad\varrho:= \exp\left[-(C')^2r^2/\sigma^2\right], \qquad\alpha_\varepsilon:= \frac{1}{2}-Q_3a_\varepsilon, C ′ := 2 2 π C − 2 , ϱ := exp [ − ( C ′ ) 2 r 2 / σ 2 ] , α ε := 2 1 − Q 3 a ε , where Q 3 ∈ ( 0 , 1 / ( 4 Q 2 ) ) Q_3 \in(0,1/(4Q_2)) Q 3 ∈ ( 0 , 1/ ( 4 Q 2 )) α ε ∈ [ 1 / 4 , 1 / 2 ) \alpha_\varepsilon\in[1/4,1/2) α ε ∈ [ 1/4 , 1/2 ) ε ∈ [ 1 / 4 , 1 / 2 ) \varepsilon\in[1/4,1/2) ε ∈ [ 1/4 , 1/2 )
h ( α ε ) − ε ≥ ( i ) a ε 2 − ( 1 2 − h ( α ε ) ) ≥ ( i i ) a ε ( 1 2 − Q 2 Q 3 ) > 0 , (11) h(\alpha_\varepsilon)-\varepsilon\mathrel{\overset{(i)}{\geq}} \frac{a_\varepsilon}{2}-\left(\frac{1}{2}-h(\alpha_\varepsilon)\right) \mathrel{\overset{(ii)}{\geq}} a_\varepsilon\left(\frac{1}{2}-Q_2Q_3\right)>0, \tag*{(11)} h ( α ε ) − ε ≥ ( i ) 2 a ε − ( 2 1 − h ( α ε ) ) ≥ ( ii ) a ε ( 2 1 − Q 2 Q 3 ) > 0 , (11) where ( i ) (i) ( i ) a ε a_\varepsilon a ε ( i i ) (ii) ( ii ) [13 ] [Appendix B, Equation (B.1)]. Then we set
L ε : = 3 2 − 4 g ( α ε ) 1 − 2 α ε , β ε : = C ′ ( Φ ( L ε ) − 1 2 ) , L_\varepsilon:= \frac{3}{2}\sqrt{-\frac{4g(\alpha_\varepsilon)}{1-2\alpha_\varepsilon}}, \qquad\beta_\varepsilon:= C'\left(\Phi(L_\varepsilon)-\frac{1}{2}\right), L ε := 2 3 − 1 − 2 α ε 4 g ( α ε ) , β ε := C ′ ( Φ ( L ε ) − 2 1 ) , then directly we have
Φ − 1 ( 1 2 + β ε C ′ ) = L ε > − 4 g ( α ε ) 1 − 2 α ε , (12) \Phi^{-1}\left(\frac{1}{2}+\frac{\beta_\varepsilon}{C'}\right)=L_\varepsilon>\sqrt{-\frac{4g(\alpha_\varepsilon)}{1-2\alpha_\varepsilon}}, \tag*{(12)} Φ − 1 ( 2 1 + C ′ β ε ) = L ε > − 1 − 2 α ε 4 g ( α ε ) , (12) which is a counterpart of their Equation (B.2). We further set
C 1 , ε : = 2 L ε β ε , C 2 , ε : = β ε L ε , C_{1,\varepsilon}:=\frac{2L_\varepsilon}{\beta_\varepsilon}, \qquad C_{2,\varepsilon}:=\frac{\beta_\varepsilon}{L_\varepsilon}, C 1 , ε := β ε 2 L ε , C 2 , ε := L ε β ε , which follow the settings of their (B.3) and (B.4), and satisfy C 1 , ε C 2 , ε = 2 C_{1,\varepsilon}C_{2,\varepsilon}=2 C 1 , ε C 2 , ε = 2 β ε ≲ 1 \beta_\varepsilon\lesssim1 β ε ≲ 1 Lemma D.1 gives − 4 g ( α ε ) / ( 1 − 2 α ε ) -4g(\alpha_\varepsilon)/(1-2\alpha_\varepsilon) − 4 g ( α ε ) / ( 1 − 2 α ε ) C 1 , ε 2 ≲ z ε C_{1,\varepsilon}^2\lesssim z_\varepsilon C 1 , ε 2 ≲ z ε
C 3 , ε : = C 2 , ε 2 2 ∧ ( 1 / 2 − α ε ) ( C ′ ) 2 2 ≲ a ε , C_{3,\varepsilon}:=\frac{C_{2,\varepsilon}^2}{2}\wedge\frac{(1/2-\alpha_\varepsilon)(C')^2}{2}\lesssim a_\varepsilon, C 3 , ε := 2 C 2 , ε 2 ∧ 2 ( 1/2 − α ε ) ( C ′ ) 2 ≲ a ε , where the final comparison follows since a ε z ε ≲ 1 a_\varepsilon z_\varepsilon\lesssim1 a ε z ε ≲ 1 [13 ] [Appendix B].
Then we verify that they satisfy the two constant conditions (i)-(ii) from their proof. Choose D 1 D_1 D 1
D 1 > max { sup ε C 1 , ε z ε , sup ε 4 C ′ L ε z ε } < ∞ . D_1>\max\left\{\sup_\varepsilon\frac{C_{1,\varepsilon}}{\sqrt{z_\varepsilon}},\sup_\varepsilon\frac{4}{C'}\frac{L_\varepsilon}{\sqrt{z_\varepsilon}}\right\}<\infty. D 1 > max { ε sup z ε C 1 , ε , ε sup C ′ 4 z ε L ε } < ∞. Here both suprema are finite by the previous discussion. As a result, if r / σ ≥ D 1 ε z ε r/\sigma\geq D_1\varepsilon\sqrt{z_\varepsilon} r / σ ≥ D 1 ε z ε
r σ ≥ C 1 , ε ε . (13) \frac{r}{\sigma}\geq C_{1,\varepsilon}\varepsilon. \tag*{(13)} σ r ≥ C 1 , ε ε . (13) Also, since ε ≥ 1 / 4 \varepsilon\geq1/4 ε ≥ 1/4
C ′ r σ ≥ C ′ D 1 ε z ε ≥ C ′ D 1 4 z ε > L ε . (14) \frac{C'r}{\sigma}\geq C'D_1\varepsilon\sqrt{z_\varepsilon}\geq\frac{C'D_1}{4}\sqrt{z_\varepsilon}>L_\varepsilon. \tag*{(14)} σ C ′ r ≥ C ′ D 1 ε z ε ≥ 4 C ′ D 1 z ε > L ε . (14) This verifies the two constant conditions (i)-(ii) in [13 ] [Appendix B]: (i) Verify that ε < α ε ( 1 − ϱ ) \varepsilon< \alpha_{\varepsilon}(1-\varrho) ε < α ε ( 1 − ϱ )
α ε ( 1 − ϱ ) = α ε ( 1 − exp [ − ( C ′ ) 2 r 2 / σ 2 ] ) > ( i ) α ε ( 1 − exp [ − L ε 2 ] ) ≥ ( i i ) α ε ( 1 − exp [ 4 g ( α ε ) / ( 1 − 2 α ε ) ] ) = h ( α ε ) > ( i i i ) ε , \alpha_{\varepsilon}(1-\varrho)=\alpha_{\varepsilon}\left(1-\exp\left[-(C')^{2}r^{2}/\sigma^{2}\right]\right)
\underset{(i)}{>}\alpha_{\varepsilon}\left(1-\exp\left[-L_{\varepsilon}^{2}\right]\right)
\underset{(ii)}{\ge}\alpha_{\varepsilon}\left(1-\exp\left[4g(\alpha_{\varepsilon})/(1-2\alpha_{\varepsilon})\right]\right)
=h(\alpha_{\varepsilon})
\underset{(iii)}{>}\varepsilon, α ε ( 1 − ϱ ) = α ε ( 1 − exp [ − ( C ′ ) 2 r 2 / σ 2 ] ) ( i ) > α ε ( 1 − exp [ − L ε 2 ] ) ( ii ) ≥ α ε ( 1 − exp [ 4 g ( α ε ) / ( 1 − 2 α ε ) ] ) = h ( α ε ) ( iii ) > ε , where (i) from Equation D.6; (ii) from Equation D.4; (iii) from Equation D.3.
(ii) Verify that ( 1 / 2 − α ε ) log ( 1 / ϱ ) ≥ − 2 g ( α ε ) (1/2-\alpha_{\varepsilon})\log(1/\varrho)\ge-2g(\alpha_{\varepsilon}) ( 1/2 − α ε ) log ( 1/ ϱ ) ≥ − 2 g ( α ε )
( 1 / 2 − α ε ) log ( 1 / ϱ ) > ( 1 / 2 − α ε ) L ε 2 > − 2 g ( α ε ) , (1/2-\alpha_{\varepsilon})\log(1/\varrho)>(1/2-\alpha_{\varepsilon})L_{\varepsilon}^{2}>-2g(\alpha_{\varepsilon}), ( 1/2 − α ε ) log ( 1/ ϱ ) > ( 1/2 − α ε ) L ε 2 > − 2 g ( α ε ) , where (i) from Equation D.4.
As a result, condition (i) and (ii) place the argument in the large-r / σ r/\sigma r / σ ε ∈ [ 1 / 4 , 1 / 2 ) \varepsilon\in[1/4,1/2) ε ∈ [ 1/4 , 1/2 ) r / σ r/\sigma r / σ ε \varepsilon ε r ≳ C 1 ( κ ) ε σ r\gtrsim C_1(\kappa)\varepsilon\sigma r ≳ C 1 ( κ ) ε σ C ′ r / σ > L C'r/\sigma>L C ′ r / σ > L
Applying their Lemma B.3 and inequality (B.7), then following their procedure to compare the clean and corrupted voting results gives
sup μ ∈ B ( ν 1 , r ) P μ , C ( ψ = 1 ) ≤ exp [ − 1 2 ( 1 / 2 − α ε ) ( C ′ ) 2 N r 2 σ 2 ] . \sup_{\mu\in B(\nu_1,r)}\mathbb{P}_{\mu,C}(\psi=1)\le\exp\left[-\frac{1}{2}(1/2-\alpha_{\varepsilon})(C')^{2}N\frac{r^{2}}{\sigma^{2}}\right]. μ ∈ B ( ν 1 , r ) sup P μ , C ( ψ = 1 ) ≤ exp [ − 2 1 ( 1/2 − α ε ) ( C ′ ) 2 N σ 2 r 2 ] . Noticing that the definition of α ε \alpha_{\varepsilon} α ε a ε = 1 − 2 α ε 2 Q 3 a_{\varepsilon}=\frac{1-2\alpha_{\varepsilon}}{2Q_3} a ε = 2 Q 3 1 − 2 α ε Q 0 ≤ Q 3 ( C ′ ) 2 / 2 Q_0\le Q_3(C')^2/2 Q 0 ≤ Q 3 ( C ′ ) 2 /2 P μ ∈ B ( ν 2 , r ) ( ψ = 0 ) \mathbb{P}_{\mu\in B(\nu_2,r)}(\psi=0) P μ ∈ B ( ν 2 , r ) ( ψ = 0 )
Minimax Upper Bound for Bounded Case
We now apply the robust testing procedure Lemma D.2 to the tournament-on-a-tree procedure introduced in Appendix § 5 . In the following, our focus is on the near-breakdown regime ε ∈ [ 1 / 4 , 1 / 2 ) \varepsilon\in[1/4,1/2) ε ∈ [ 1/4 , 1/2 ) ε ∈ [ 0 , 1 / 4 ) \varepsilon\in[0,1/4) ε ∈ [ 0 , 1/4 ) [13 ] Theorem 3.10.
Applying the robust pairwise testing to the tournament-on-the-tree procedure, we obtain a path along the tree Y = [ Y 1 , Y 2 , … ] \mathcal{Y}=[\mathcal{Y}_1,\mathcal{Y}_2,\ldots] Y = [ Y 1 , Y 2 , … ] Y J + 1 ∈ O ( Y J ) \mathcal{Y}_{J+1}\in\mathcal{O}(\mathcal{Y}_J) Y J + 1 ∈ O ( Y J ) J J J § 5 . Now we prove that by choosing a proper stopping step J J J
A
Q 0 a ε N r J 2 / σ 2 ≥ 4 log M loc ( ξ 2 r J , c ) ∨ log 2 ; Q_0a_{\varepsilon}Nr_J^2/\sigma^2\ge4\log M^{\operatorname{loc}}\left(\frac{\xi}{2}r_J,c\right)\vee\log2; Q 0 a ε N r J 2 / σ 2 ≥ 4 log M loc ( 2 ξ r J , c ) ∨ log 2 ; B r J ≥ D 1 ε σ z ε B\quad r_J \ge D_1\varepsilon\sigma\sqrt{z_\varepsilon} B r J ≥ D 1 ε σ z ε
Here Q 0 , D 1 Q_0,D_1 Q 0 , D 1 Lemma D.2 and r J = d / ( 2 J − 1 ( C + 1 ) ) r_J=d/(2^{J-1}(C+1)) r J = d / ( 2 J − 1 ( C + 1 )) J A J^A J A J B J^B J B K K K J ∗ : = J A ∧ J B J^*:=J^A\wedge J^B J ∗ := J A ∧ J B μ ^ b o u n d e d : = Y J ∗ \hat{\mu}_{\mathrm{bounded}}:=\mathcal{Y}_{J^*} μ ^ bounded := Y J ∗
The following lemma shows the error bound induced by the stopping conditions using Lemma D.2 .
Lemma E.1. Let K K K d d d μ ∈ K \mu\in K μ ∈ K ε ∈ [ 1 / 4 , 1 / 2 ) \varepsilon\in[1/4,1/2) ε ∈ [ 1/4 , 1/2 ) r J r_J r J J J J
E [ ∥ Y J − μ ∥ 2 ] ≲ r J 2 + σ 2 a ε N exp [ − Q 0 a ε N r J 2 2 σ 2 ] ≲ r J 2 . \mathbb{E}\left[\left\|\mathcal{Y}_J-\mu\right\|^2\right]\lesssim r_J^2+\frac{\sigma^2}{a_\varepsilon N}\exp\left[-Q_0a_\varepsilon N\frac{r_J^2}{2\sigma^2}\right]\lesssim r_J^2. E [ ∥ Y J − μ ∥ 2 ] ≲ r J 2 + a ε N σ 2 exp [ − Q 0 a ε N 2 σ 2 r J 2 ] ≲ r J 2 . Proof. By the monotonicity of the local metric entropy as in Lemma A.1[(i)], for any 1 ≤ j ≤ J 1\le j\le J 1 ≤ j ≤ J
r j ≥ D 1 ε σ z ε , Q 0 a ε N r j 2 σ 2 ≥ 4 log M l o c ( C 2 r j , c ) ∨ log 2. r_j\ge D_1\varepsilon\sigma\sqrt{z_\varepsilon},\qquad Q_0\frac{a_\varepsilon Nr_j^2}{\sigma^2}\ge4\log M^{\mathrm{loc}}\left(\frac{C}{2}r_j,c\right)\vee\log2. r j ≥ D 1 ε σ z ε , Q 0 σ 2 a ε N r j 2 ≥ 4 log M loc ( 2 C r j , c ) ∨ log 2. As a result, Lemma D.2 applies to every comparison before the stopping iteration j ≤ J j\le J j ≤ J
Now following the tree-tail calculation of [13 ] [Lemma B.5, Lemma B.6] but with a different tail probability from Lemma D.2 , we account for the two local packing factors in the union bound. We remark that the only differences are the error tail exponent Q 0 a ε N r j 2 / σ 2 Q_0a_\varepsilon Nr_j^2/\sigma^2 Q 0 a ε N r j 2 / σ 2 D 1 ε σ z ε D_1\varepsilon\sigma\sqrt{z_\varepsilon} D 1 ε σ z ε
M l o c ( C 2 r j , c ) 2 exp [ − Q 0 a ε N r j 2 / σ 2 ] ≤ exp [ − Q 0 a ε N r j 2 / ( 2 σ 2 ) ] . M^{\mathrm{loc}}\left(\frac{C}{2}r_j,c\right)^2\exp\left[-Q_0a_\varepsilon Nr_j^2/\sigma^2\right]\le\exp\left[-Q_0a_\varepsilon Nr_j^2/(2\sigma^2)\right]. M loc ( 2 C r j , c ) 2 exp [ − Q 0 a ε N r j 2 / σ 2 ] ≤ exp [ − Q 0 a ε N r j 2 / ( 2 σ 2 ) ] . The subsequent tail integration, as in their Lemma B.6, gives the error bound
E [ ∥ Y J − μ ∥ 2 ] ≲ r J 2 + σ 2 a ε N exp [ − Q 0 a ε N r J 2 2 σ 2 ] . \mathbb{E}\left[\left\|\mathcal{Y}_J-\mu\right\|^2\right]\lesssim r_J^2+\frac{\sigma^2}{a_\varepsilon N}\exp\left[-Q_0a_\varepsilon N\frac{r_J^2}{2\sigma^2}\right]. E [ ∥ Y J − μ ∥ 2 ] ≲ r J 2 + a ε N σ 2 exp [ − Q 0 a ε N 2 σ 2 r J 2 ] . Finally, the condition Q 0 a ε N r J 2 σ 2 ≥ log 2 \frac{Q_0a_\varepsilon Nr_J^2}{\sigma^2}\ge\log2 σ 2 Q 0 a ε N r J 2 ≥ log 2
Lemma E.2. For ε ∈ [ 1 / 4 , 1 / 2 ) \varepsilon\in[1/4,1/2) ε ∈ [ 1/4 , 1/2 ) μ ^ b o u n d e d \hat{\mu}_{\mathrm{bounded}} μ ^ bounded
sup μ ∈ K sup E μ , C [ ∥ μ ^ b o u n d e d − μ ∥ 2 ] ≲ ( r J A 2 ∨ σ 2 ε 2 log ( 1 / ( 1 − 2 ε ) ) ) ∧ d 2 . \sup_{\mu\in K}\sup\mathbb{E}_{\mu,\mathcal{C}}\left[\left\|\hat{\mu}_{\mathrm{bounded}}-\mu\right\|^2\right]\lesssim\left(r_{J^A}^2\vee\sigma^2\varepsilon^2\log(1/(1-2\varepsilon))\right)\wedge d^2. μ ∈ K sup sup E μ , C [ ∥ μ ^ bounded − μ ∥ 2 ] ≲ ( r J A 2 ∨ σ 2 ε 2 log ( 1/ ( 1 − 2 ε )) ) ∧ d 2 . Proof. We first deal with the case when at least one of the two conditions fails at J = 1 J=1 J = 1 μ ^ b o u n d e d = Y 1 \hat{\mu}_{\mathrm{bounded}}=\mathcal{Y}_1 μ ^ bounded = Y 1 μ , Y 1 ∈ K \mu,\mathcal{Y}_1\in K μ , Y 1 ∈ K ∥ Y 1 − μ ∥ 2 ≤ d 2 \left\|\mathcal{Y}_1-\mu\right\|^2\le d^2 ∥ Y 1 − μ ∥ 2 ≤ d 2 r 1 = d / ( C + 1 ) ≲ d r_1=d/(C+1)\lesssim d r 1 = d / ( C + 1 ) ≲ d
E [ ∥ μ ^ b o u n d e d − μ ∥ 2 ] ≤ d 2 ≲ r J A 2 ∧ d 2 ≤ ( r J A 2 ∨ σ 2 ε 2 log ( 1 / ( 1 − 2 ε ) ) ) ∧ d 2 . \mathbb{E}\left[\left\|\hat{\mu}_{\mathrm{bounded}}-\mu\right\|^2\right]\le d^2\lesssim r_{J_A}^2\wedge d^2\le\left(r_{J_A}^2\vee\sigma^2\varepsilon^2\log(1/(1-2\varepsilon))\right)\wedge d^2. E [ ∥ μ ^ bounded − μ ∥ 2 ] ≤ d 2 ≲ r J A 2 ∧ d 2 ≤ ( r J A 2 ∨ σ 2 ε 2 log ( 1/ ( 1 − 2 ε )) ) ∧ d 2 . E [ ∥ μ ^ b o u n d e d − μ ∥ 2 ] ≤ d 2 ≲ ε 2 σ 2 log ( 1 / ( 1 − 2 ε ) ) ∧ d 2 ≤ ( r J A 2 ∨ σ 2 ε 2 log ( 1 / ( 1 − 2 ε ) ) ) ∧ d 2 . \mathbb{E}\left[\left\|\hat{\mu}_{\mathrm{bounded}}-\mu\right\|^2\right]\le d^2\lesssim\varepsilon^2\sigma^2\log(1/(1-2\varepsilon))\wedge d^2\le\left(r_{J_A}^2\vee\sigma^2\varepsilon^2\log(1/(1-2\varepsilon))\right)\wedge d^2. E [ ∥ μ ^ bounded − μ ∥ 2 ] ≤ d 2 ≲ ε 2 σ 2 log ( 1/ ( 1 − 2 ε )) ∧ d 2 ≤ ( r J A 2 ∨ σ 2 ε 2 log ( 1/ ( 1 − 2 ε )) ) ∧ d 2 . It remains to consider the case when both conditions are satisfied at the root J = 1 J=1 J = 1
sup μ ∈ K sup C E μ , C [ ∥ μ ^ b o u n d e d − μ ∥ 2 ] ≲ r J ∗ 2 . \sup_{\mu\in K}\sup_C\mathbb{E}_{\mu,C}\left[\left\|\hat{\mu}_{\mathrm{bounded}}-\mu\right\|^2\right]\lesssim r_{J^*}^2. μ ∈ K sup C sup E μ , C [ ∥ μ ^ bounded − μ ∥ 2 ] ≲ r J ∗ 2 . At the level when condition (B) fails, we have r J B < 2 D 1 ε σ z ε r_{J_B}<2D_1\varepsilon\sigma\sqrt{z_\varepsilon} r J B < 2 D 1 ε σ z ε J ↦ r J J\mapsto r_J J ↦ r J
r J ∗ 2 = r J A 2 ∨ r J B 2 ≲ r J A 2 ∨ σ 2 ε 2 log ( 1 / ( 1 − 2 ε ) ) . r_{J^*}^2=r_{J_A}^2\vee r_{J_B}^2\lesssim r_{J_A}^2\vee\sigma^2\varepsilon^2\log(1/(1-2\varepsilon)). r J ∗ 2 = r J A 2 ∨ r J B 2 ≲ r J A 2 ∨ σ 2 ε 2 log ( 1/ ( 1 − 2 ε )) . Combining the two cases with the trivial bound d 2 d^2 d 2
Proof of Theorem 2.3. Recall that
δ ε ∗ = sup { r ≥ 0 : a ε N r 2 σ 2 ≤ log M l o c ( r , c ) } . \delta_\varepsilon^*=\sup\left\{r\ge0:a_\varepsilon N\frac{r^2}{\sigma^2}\le\log M^{\mathrm{loc}}(r,c)\right\}. δ ε ∗ = sup { r ≥ 0 : a ε N σ 2 r 2 ≤ log M loc ( r , c ) } . If K K K δ ε ∗ = 0 \delta_\varepsilon^*=0 δ ε ∗ = 0 κ ε : = a ε N δ ε ∗ 2 / σ 2 \kappa_\varepsilon:=a_\varepsilon N\delta_\varepsilon^{*2}/\sigma^2 κ ε := a ε N δ ε ∗ 2 / σ 2
8 log 2 ≥ κ ε = 1 4 a ε N ( 2 δ ε ∗ ) 2 σ 2 ≥ 1 4 log M l o c ( 2 δ ε ∗ , c ) . 8\log2\ge\kappa_\varepsilon=\frac{1}{4}a_\varepsilon N\frac{(2\delta_\varepsilon^*)^2}{\sigma^2}\ge\frac{1}{4}\log M^{\mathrm{loc}}(2\delta_\varepsilon^*,c). 8 log 2 ≥ κ ε = 4 1 a ε N σ 2 ( 2 δ ε ∗ ) 2 ≥ 4 1 log M loc ( 2 δ ε ∗ , c ) . By the same argument as in [13 ] [proof of Theorem 3.10, Case 3], which utilizes the fact that there must be line segments in K K K d / 3 d/3 d /3 d ≤ 12 δ ε ∗ d\le12\delta_\varepsilon^* d ≤ 12 δ ε ∗
E [ ∥ μ ^ b o u n d e d − μ ∥ 2 ] ≲ d 2 ≲ ( δ ε ∗ 2 ∨ σ 2 ε 2 log ( 1 / ( 1 − 2 ε ) ) ) ∧ d 2 . \mathbb{E}\left[\left\|\hat{\mu}_{\mathrm{bounded}}-\mu\right\|^2\right]\lesssim d^2\lesssim\left(\delta_\varepsilon^{*2}\vee\sigma^2\varepsilon^2\log(1/(1-2\varepsilon))\right)\wedge d^2. E [ ∥ μ ^ bounded − μ ∥ 2 ] ≲ d 2 ≲ ( δ ε ∗ 2 ∨ σ 2 ε 2 log ( 1/ ( 1 − 2 ε )) ) ∧ d 2 . Case 2: If κ ε > 8 log 2 \kappa_\varepsilon>8\log2 κ ε > 8 log 2 δ ε ∗ ≳ r J A \delta_\varepsilon^*\gtrsim r_{J_A} δ ε ∗ ≳ r J A r ~ : = D 4 δ ε ∗ \tilde r:=D_4\delta_\varepsilon^* r ~ := D 4 δ ε ∗ r ~ ≳ r J A \tilde r\gtrsim r_{J_A} r ~ ≳ r J A
D 3 : = c 4 ∧ Q 0 4 , D 4 : = 2 / D 3 . D_3:=\frac{c}{4}\wedge\frac{\sqrt{Q_0}}{4},\qquad D_4:=2/D_3. D 3 := 4 c ∧ 4 Q 0 , D 4 := 2/ D 3 . Consequently, we have D 3 ≤ c / 2 D_3 \le c/2 D 3 ≤ c /2 4 D 3 2 < Q 0 4D_3^2 < Q_0 4 D 3 2 < Q 0 D 3 D 4 = 2 D_3D_4 = 2 D 3 D 4 = 2 Q 0 D 4 2 ≥ 64 Q_0D_4^2 \ge64 Q 0 D 4 2 ≥ 64 r ~ \tilde r r ~
Q 0 a ε N ( D 4 δ ε ∗ ) 2 σ 2 = Q 0 D 3 2 a ε N ( 2 δ ε ∗ ) 2 σ 2 > Q 0 D 3 2 log M loc ( 2 δ ε ∗ , c ) ≥ ( i ) Q 0 D 3 2 log M loc ( c D 4 2 δ ε ∗ , c ) = Q 0 D 3 2 log M loc ( c 2 r ~ , c ) \begin{aligned}
\frac{Q_0a_\varepsilon N(D_4\delta_\varepsilon^*)^2}{\sigma^2}
= \frac{Q_0}{D_3^2}\frac{a_\varepsilon N(2\delta_\varepsilon^*)^2}{\sigma^2} \\
&> \frac{Q_0}{D_3^2}\log M^{\operatorname{loc}}(2\delta_\varepsilon^*,c) \\
&\geq^{(i)} \frac{Q_0}{D_3^2}\log M^{\operatorname{loc}}\left(\frac{cD_4}{2}\delta_\varepsilon^*,c\right) \\
&= \frac{Q_0}{D_3^2}\log M^{\operatorname{loc}}\left(\frac{c}{2}\tilde r,c\right)
\end{aligned} σ 2 Q 0 a ε N ( D 4 δ ε ∗ ) 2 = D 3 2 Q 0 σ 2 a ε N ( 2 δ ε ∗ ) 2 > D 3 2 Q 0 log M loc ( 2 δ ε ∗ , c ) ≥ ( i ) D 3 2 Q 0 log M loc ( 2 c D 4 δ ε ∗ , c ) = D 3 2 Q 0 log M loc ( 2 c r ~ , c ) ≥ 4 log M loc ( c 2 r ~ , c ) . \geq4\log M^{\operatorname{loc}}\left(\frac{c}{2}\tilde r,c\right). ≥ 4 log M loc ( 2 c r ~ , c ) . where (i) from the monotonicity of the local metric entropy Lemma A.1[(i)] and the fact that D 3 ≤ c / 2 D_3 \le c/2 D 3 ≤ c /2
Q 0 a ε N ( D 4 δ ε ∗ ) 2 σ 2 = Q 0 D 4 2 κ ε > 64 log 2 > log 2. \frac{Q_0a_\varepsilon N(D_4\delta_\varepsilon^*)^2}{\sigma^2}
= Q_0D_4^2\kappa_\varepsilon> 64\log2 > \log2. σ 2 Q 0 a ε N ( D 4 δ ε ∗ ) 2 = Q 0 D 4 2 κ ε > 64 log 2 > log 2. Now if r 1 < r ~ r_1 < \tilde r r 1 < r ~ r J A ≤ r 1 < r ~ r_{JA} \le r_1 < \tilde r r J A ≤ r 1 < r ~ J J J r ~ ≤ r J < 2 r ~ \tilde r \le r_J < 2\tilde r r ~ ≤ r J < 2 r ~ r ↦ Q 0 a ε N r 2 / σ 2 − ( 4 log M loc ( c 2 r , c ) ∨ log 2 ) r \mapsto Q_0a_\varepsilon Nr^2/\sigma^2 - (4\log M^{\operatorname{loc}}(\frac{c}{2}r,c) \vee\log2) r ↦ Q 0 a ε N r 2 / σ 2 − ( 4 log M loc ( 2 c r , c ) ∨ log 2 ) r J A ≤ r J < 2 r ~ r_{JA} \le r_J < 2\tilde r r J A ≤ r J < 2 r ~ r J A ≲ r ~ r_{JA} \lesssim\tilde r r J A ≲ r ~
sup μ ∈ K sup C E [ ∥ μ ^ b o u n d e d − μ ∥ 2 ] ≲ ( r J A 2 ∨ σ 2 ε 2 log ( 1 / ( 1 − 2 ε ) ) ) ∧ d 2 \sup_{\mu\in K}\sup_{\mathcal C}\mathbb{E}\left[\|\hat\mu_{\mathrm{bounded}}-\mu\|^2\right]
\lesssim\left(r_{JA}^2 \vee\sigma^2\varepsilon^2\log\left(1/(1-2\varepsilon)\right)\right)\wedge d^2 μ ∈ K sup C sup E [ ∥ μ ^ bounded − μ ∥ 2 ] ≲ ( r J A 2 ∨ σ 2 ε 2 log ( 1/ ( 1 − 2 ε ) ) ) ∧ d 2 ≲ ( δ ε ∗ 2 ∨ σ 2 ε 2 log ( 1 / ( 1 − 2 ε ) ) ) ∧ d 2 . \lesssim\left(\delta_\varepsilon^{*2}\vee\sigma^2\varepsilon^2\log\left(1/(1-2\varepsilon)\right)\right)\wedge d^2. ≲ ( δ ε ∗ 2 ∨ σ 2 ε 2 log ( 1/ ( 1 − 2 ε ) ) ) ∧ d 2 . When ε ≥ 1 / 4 \varepsilon\ge1/4 ε ≥ 1/4 log ( 1 / ( 1 − 2 ε ) ) \log(1/(1-2\varepsilon)) log ( 1/ ( 1 − 2 ε )) log ( e / ( 1 − 2 ε ) ) \log(e/(1-2\varepsilon)) log ( e / ( 1 − 2 ε )) ε ∈ [ 0 , 1 / 4 ) \varepsilon\in[0,1/4) ε ∈ [ 0 , 1/4 )
Minimax Upper Bound for Unbounded Case
For the unbounded case, the tree is preceded by a localization step, as described in Appendix § 5 . The localization and tree construction remain unchanged up to constant rescaling, and it suffices to analyze the constant calibration in these steps. The objective is to restore the dependence on ε \varepsilon ε [13 ] where ε \varepsilon ε 1 / 2 1/2 1/2 ε ∈ [ 1 / 4 , 1 / 2 ) \varepsilon\in[1/4,1/2) ε ∈ [ 1/4 , 1/2 ) ε ∈ [ 0 , 1 / 4 ) \varepsilon\in[0,1/4) ε ∈ [ 0 , 1/4 )
Localization Step
The two requirements on γ ε \gamma_\varepsilon γ ε [13 ] [Section 5.2] are
γ ε > max ( 1 − C 3 , ε 6 ( C + 1 ) 2 log 2 , 1 − 4 ( C + 1 ) 2 C 1 , ε 2 ) , \gamma_\varepsilon> \max\left(1-\frac{C_{3,\varepsilon}}{6(C+1)^2\log2},1-\frac{4}{(C+1)^2C_{1,\varepsilon}^2}\right), γ ε > max ( 1 − 6 ( C + 1 ) 2 log 2 C 3 , ε , 1 − ( C + 1 ) 2 C 1 , ε 2 4 ) , where we note that C 1 , ε 2 ≍ z ε = log ( e / ( 1 − 2 ε ) ) C_{1,\varepsilon}^{2} \asymp z_{\varepsilon} = \log(e/(1-2\varepsilon)) C 1 , ε 2 ≍ z ε = log ( e / ( 1 − 2 ε )) C 3 , ε ≍ a ε = 1 − 2 ε C_{3,\varepsilon} \asymp a_{\varepsilon} = 1-2\varepsilon C 3 , ε ≍ a ε = 1 − 2 ε
γ ε : = 1 − Q 4 a ε (15) \gamma_{\varepsilon} := 1-Q_{4}a_{\varepsilon} \tag*{(15)} γ ε := 1 − Q 4 a ε (15) where Q 4 > 0 Q_{4}>0 Q 4 > 0 a ε z ε ≲ 1 a_{\varepsilon}z_{\varepsilon}\lesssim1 a ε z ε ≲ 1 γ ε ≲ 1 \gamma_{\varepsilon}\lesssim1 γ ε ≲ 1 1 − γ ε ≲ a ε 1-\gamma_{\varepsilon}\lesssim a_{\varepsilon} 1 − γ ε ≲ a ε Q 4 ≤ 1 Q_{4}\leq1 Q 4 ≤ 1 γ ε ∈ [ 1 / 2 , 1 ) \gamma_{\varepsilon}\in[1/2,1) γ ε ∈ [ 1/2 , 1 ) ε ∈ [ 1 / 4 , 1 / 2 ) \varepsilon\in[1/4,1/2) ε ∈ [ 1/4 , 1/2 )
Now we proceed to the localization radius R ε R_{\varepsilon} R ε [13 ] [Equation (5.1)], we require that
R ε 2 > max ( 8 n σ 2 log 5 1 − γ ε , − 64 σ 2 g ( ε ) γ ε a ε , 1024 σ 2 log 2 γ ε a ε , 4 ( C + 1 ) 2 ) . (16) R_{\varepsilon}^{2}>\max\left(\frac{8n\sigma^{2}\log5}{1-\gamma_{\varepsilon}},\frac{-64\sigma^{2}g(\varepsilon)}{\gamma_{\varepsilon}a_{\varepsilon}},\frac{1024\sigma^{2}\log2}{\gamma_{\varepsilon}a_{\varepsilon}},4(C+1)^{2}\right). \tag*{(16)} R ε 2 > max ( 1 − γ ε 8 n σ 2 log 5 , γ ε a ε − 64 σ 2 g ( ε ) , γ ε a ε 1024 σ 2 log 2 , 4 ( C + 1 ) 2 ) . (16) By Lemma D.1 , we have − g ( ε ) / a ε ≲ z ε -g(\varepsilon)/a_{\varepsilon}\lesssim z_{\varepsilon} − g ( ε ) / a ε ≲ z ε n ≥ 1 n\geq1 n ≥ 1 a ε z ε ≲ 1 a_{\varepsilon}z_{\varepsilon}\lesssim1 a ε z ε ≲ 1
R ε 2 : = Q 5 n σ 2 a ε ∨ 8 ( C + 1 ) 2 , (17) R_{\varepsilon}^{2}:=Q_{5}\frac{n\sigma^{2}}{a_{\varepsilon}}\vee8(C+1)^{2}, \tag*{(17)} R ε 2 := Q 5 a ε n σ 2 ∨ 8 ( C + 1 ) 2 , (17) where Q 5 > 0 Q_{5}>0 Q 5 > 0
For every t ≥ R ε t\geq R_{\varepsilon} t ≥ R ε R ε R_{\varepsilon} R ε t t t R ε R_{\varepsilon} R ε [13 ] [Lemma 5.3] gives
P ( μ ∉ S ( t ) ) ≤ exp ( − N a ε γ ε t 2 64 σ 2 ) , t ≥ R ε . (18) \mathbb{P}\left(\mu\notin S(t)\right)\leq\exp\left(-\frac{Na_{\varepsilon}\gamma_{\varepsilon}t^{2}}{64\sigma^{2}}\right),\qquad t\geq R_{\varepsilon}. \tag*{(18)} P ( μ ∈ / S ( t ) ) ≤ exp ( − 64 σ 2 N a ε γ ε t 2 ) , t ≥ R ε . (18) It follows from Equation F.3 that the right-hand side is bounded by exp [ − Q 5 N n / 128 ] \exp[-Q_{5}Nn/128] exp [ − Q 5 N n /128 ]
In Appendix § 5 , we have described the construction of the estimator for the unbounded case depending on whether S ( R ε ) S(R_{\varepsilon}) S ( R ε )
Risk Upper Bound Analysis
Recall that the final estimator is defined as
If S ( R ε ) ≠ ∅ S(R_{\varepsilon})\neq\varnothing S ( R ε ) = ∅ Y s = [ Y 1 s , Y 2 s , … ] \mathcal{Y}^{s}=[Y^{s}_{1},Y^{s}_{2},\ldots] Y s = [ Y 1 s , Y 2 s , … ] S ( R ε ) S(R_{\varepsilon}) S ( R ε ) J ∗ J^{*} J ∗ Y J ∗ s Y^{s}_{J^{*}} Y J ∗ s
If S ( R ε ) = ∅ S(R_{\varepsilon})=\varnothing S ( R ε ) = ∅ R ^ : = inf { R ≥ 0 : S ( R ) ≠ ∅ } \widehat{R}:=\inf\{R\geq0:S(R)\neq\varnothing\} R := inf { R ≥ 0 : S ( R ) = ∅ } \minlex S(\widehat{R}) .
We denote the final estimator as μ ^ u n b o u n d e d \widehat{\mu}_{\mathrm{unbounded}} μ unbounded
We now state the stopping conditions for the first case. Here we slightly overload the notation r J r_{J} r J d d d d m d_{m} d m
r J : = d m 2 J − 1 ( C + 1 ) , d m : = 2 m + 2 R ε = 2 c c − 2 R ε . r_{J}:=\frac{d_{m}}{2^{J-1}(C+1)},\qquad d_{m}:=2m+2R_{\varepsilon}=\frac{2c}{c-2}R_{\varepsilon}. r J := 2 J − 1 ( C + 1 ) d m , d m := 2 m + 2 R ε = c − 2 2 c R ε . The stopping conditions are
A Q 0 a ε N r J 2 / σ 2 ≥ 6 log M l o c ( ε 2 r J , c ) ∨ log 2 Q_{0}a_{\varepsilon}Nr_{J}^{2}/\sigma^{2}\geq6\log M^{\mathrm{loc}}(\frac{\varepsilon}{2}r_{J},c)\vee\log2 Q 0 a ε N r J 2 / σ 2 ≥ 6 log M loc ( 2 ε r J , c ) ∨ log 2 B r J ≥ D 1 ε σ z ε r_J \ge D_1\varepsilon\sigma\sqrt{z_\varepsilon} r J ≥ D 1 ε σ z ε
Let J A J^A J A J B J^B J B A and B are satisfied, respectively; if the corresponding condition is never satisfied, we set the index to be 1. Then we let the stopping step be J ∗ : = J A ∧ J B J^* := J^A \wedge J^B J ∗ := J A ∧ J B
μ ^ u n b o u n d e d = { Y J ∗ , S ( R ε ) ≠ ∅ , min l e x S ( R ^ ) , S ( R ε ) = ∅ . \widehat{\mu}_{\mathrm{unbounded}} =
\begin{cases}
\mathcal{Y}_{J^*}, & S(R_\varepsilon) \ne\varnothing,\\
\min_{\mathrm{lex}} S(\widehat{R}), & S(R_\varepsilon) = \varnothing.
\end{cases} μ unbounded = { Y J ∗ , min lex S ( R ) , S ( R ε ) = ∅ , S ( R ε ) = ∅ . Lemma F.1. If ε ∈ [ 1 / 4 , 1 / 2 ) \varepsilon\in[1/4,1/2) ε ∈ [ 1/4 , 1/2 ) J J J A and B are satisfied, we have
E [ ∥ μ ^ u n b o u n d e d − μ ∥ 2 ] ≲ r J 2 . \mathbb{E}\left[\left\|\widehat{\mu}_{\mathrm{unbounded}}-\mu\right\|^2\right] \lesssim r_J^2. E [ ∥ μ unbounded − μ ∥ 2 ] ≲ r J 2 . Proof. The proof is divided into two parts according to whether S ( R ε ) S(R_\varepsilon) S ( R ε ) [13 ] [Lemma D.1, Lemma D.2]. In their proof of Lemma D.2, Parts I-IV correspond to the case S ( R ε ) ≠ ∅ S(R_\varepsilon) \ne\varnothing S ( R ε ) = ∅ S ( R ε ) = ∅ S(R_\varepsilon) = \varnothing S ( R ε ) = ∅ ε \varepsilon ε
We begin with a counterpart of their Lemma D.1 that gives the tail probability of the tree traversal with constants uniform over ε ∈ [ 1 / 4 , 1 / 2 ) \varepsilon\in[1/4,1/2) ε ∈ [ 1/4 , 1/2 ) s s s
P ( ∥ Y J s − μ ∥ > ( C + 1 ) r J ∣ S ( R ε ) ≠ ∅ ) ≤ 2 exp [ − N a ε γ ε R ε 2 64 σ 2 ] + 4 exp [ − Q 0 a ε N r J 2 2 σ 2 ] ≲ exp [ − Q 6 a ε N r J 2 σ 2 ] . \mathbb{P}\left(\left\|\mathcal{Y}^{s}_{J}-\mu\right\|>(C+1)r_J\mid S(R_\varepsilon)\ne\varnothing\right)
\le2\exp\left[-\frac{Na_\varepsilon\gamma_\varepsilon R_\varepsilon^2}{64\sigma^2}\right]
+4\exp\left[-\frac{Q_0a_\varepsilon Nr_J^2}{2\sigma^2}\right]
\lesssim\exp\left[-\frac{Q_6a_\varepsilon Nr_J^2}{\sigma^2}\right]. P ( ∥ Y J s − μ ∥ > ( C + 1 ) r J ∣ S ( R ε ) = ∅ ) ≤ 2 exp [ − 64 σ 2 N a ε γ ε R ε 2 ] + 4 exp [ − 2 σ 2 Q 0 a ε N r J 2 ] ≲ exp [ − σ 2 Q 6 a ε N r J 2 ] . where Q 6 Q_6 Q 6 Q 6 = Q 0 2 ∧ ( 2 C + 1 ) 2 2048 Q_6 = \frac{Q_0}{2}\wedge\frac{(2C+1)^2}{2048} Q 6 = 2 Q 0 ∧ 2048 ( 2 C + 1 ) 2 r J ≤ r 1 = 4 R ε 2 C + 1 r_J\le r_1=\frac{4R_\varepsilon}{2C+1} r J ≤ r 1 = 2 C + 1 4 R ε γ ε ≥ 1 / 2 \gamma_\varepsilon\ge1/2 γ ε ≥ 1/2 ε ∈ [ 1 / 4 , 1 / 2 ) \varepsilon\in[1/4,1/2) ε ∈ [ 1/4 , 1/2 )
The S ( R ε ) ≠ ∅ S(R_\varepsilon)\ne\varnothing S ( R ε ) = ∅ Y J ∗ \mathcal{Y}_{J^*} Y J ∗ Lemma E.1 by assessing the tail probability of the tree traversal and then integrating the tail. To obtain the conditional expected risk, we apply the preceding tail bound at every level j ≤ J j\le J j ≤ J [13 ] [Lemma D.2]. Specifically, there are two scales involved in the integration (say, the integration index is t t t r J ≲ t ≲ R ε r_J\lesssim t\lesssim R_\varepsilon r J ≲ t ≲ R ε t ≳ R ε t\gtrsim R_\varepsilon t ≳ R ε J J J A and B are satisfied, we have
E [ ∥ Y J s − μ ∥ 2 ∣ S ( R ε ) ≠ ∅ ] ≲ r J 2 + σ 2 a ε N exp [ − Q 6 a ε N r J 2 σ 2 ] ≲ r J 2 , (19) \mathbb{E}\left[\left\|\mathcal{Y}^{s}_{J}-\mu\right\|^2\mid S(R_\varepsilon)\ne\varnothing\right]
\lesssim r_J^2+\frac{\sigma^2}{a_\varepsilon N}\exp\left[-Q_6a_\varepsilon N\frac{r_J^2}{\sigma^2}\right]
\lesssim r_J^2, \tag*{(19)} E [ ∥ Y J s − μ ∥ 2 ∣ S ( R ε ) = ∅ ] ≲ r J 2 + a ε N σ 2 exp [ − Q 6 a ε N σ 2 r J 2 ] ≲ r J 2 , (19) where the last inequality follows from condition A . Since both stopping conditions hold at J J J J ≤ J ∗ J \le J^* J ≤ J ∗ ∥ Y J ∗ s − Y J s ∥ ≤ 4 C + 5 2 r J \lVert\mathcal{Y}_{J^*}^s-\mathcal{Y}_J^s\rVert\le\frac{4C+5}{2}r_J ∥ Y J ∗ s − Y J s ∥ ≤ 2 4 C + 5 r J J ≤ J ∗ J \le J^* J ≤ J ∗
E [ ∥ Y J ∗ s − μ ∥ 2 1 { S ( R ε ) ≠ ∅ } ] ≲ r J 2 . \mathbb{E}\left[\lVert\mathcal{Y}_{J^*}^s-\mu\rVert^2\mathbb{1}\{S(R_\varepsilon)\ne\varnothing\}\right]\lesssim r_J^2. E [ ∥ Y J ∗ s − μ ∥ 2 1 { S ( R ε ) = ∅ } ] ≲ r J 2 . The S ( R ε ) = ∅ S(R_\varepsilon)=\varnothing S ( R ε ) = ∅ S ( R ε ) = ∅ S(R_\varepsilon)=\varnothing S ( R ε ) = ∅
{ S ( R ε ) = ∅ } = { R ^ > R ε } = ⋃ l = 1 ∞ { 2 l − 1 R ε < R ^ ≤ 2 l R ε } . \{S(R_\varepsilon)=\varnothing\}=\{\widehat{R}>R_\varepsilon\}=\mathop{\bigcup}_{l=1}^{\infty}\{2^{l-1}R_\varepsilon<\widehat{R}\le2^lR_\varepsilon\}. { S ( R ε ) = ∅ } = { R > R ε } = ⋃ l = 1 ∞ { 2 l − 1 R ε < R ≤ 2 l R ε } . Then we let p l : = P ( 2 l − 1 R ε < R ^ ≤ 2 l R ε ) p_l:=\mathbb{P}\left(2^{l-1}R_\varepsilon<\widehat{R}\le2^lR_\varepsilon\right) p l := P ( 2 l − 1 R ε < R ≤ 2 l R ε )
p l ≤ P ( R ^ > 2 l − 1 R ε ) ≤ P ( μ ∉ S ( 2 l − 1 R ε ) ) ≤ exp [ − N a ε γ ε 4 l − 1 R ε 2 64 σ 2 ] : = exp ( − t l ) , (20) \begin{aligned}
p_l &\le\mathbb{P}(\widehat{R}>2^{l-1}R_\varepsilon)\\
&\le\mathbb{P}(\mu\notin S(2^{l-1}R_\varepsilon))\\
&\le\exp\left[-\frac{Na_\varepsilon\gamma_\varepsilon4^{l-1}R_\varepsilon^2}{64\sigma^2}\right]:=\exp(-t_l), \tag*{(20)}
\end{aligned} p l ≤ P ( R > 2 l − 1 R ε ) ≤ P ( μ ∈ / S ( 2 l − 1 R ε )) ≤ exp [ − 64 σ 2 N a ε γ ε 4 l − 1 R ε 2 ] := exp ( − t l ) , (20) where we remind the readers that t l ≥ t 1 > 1 t_l\ge t_1>1 t l ≥ t 1 > 1 [13 ] [Equation (D.8)]:
E [ ∥ μ ^ u n b o u n d e d − μ ∥ 2 1 { 2 l − 1 R ε < R ^ ≤ 2 l R ε } ] ≲ 4 l − 1 R ε 2 σ 2 N a ε γ ε log 1 p l + σ 2 N a ε γ ε . \mathbb{E}\left[\lVert\widehat{\mu}_{\mathrm{unbounded}}-\mu\rVert^2\mathbb{1}\{2^{l-1}R_\varepsilon<\widehat{R}\le2^lR_\varepsilon\}\right]\lesssim4^{l-1}R_\varepsilon^2\sqrt{\frac{\sigma^2}{Na_\varepsilon\gamma_\varepsilon}\log\frac{1}{p_l}}+\frac{\sigma^2}{Na_\varepsilon\gamma_\varepsilon}. E [ ∥ μ unbounded − μ ∥ 2 1 { 2 l − 1 R ε < R ≤ 2 l R ε } ] ≲ 4 l − 1 R ε 2 N a ε γ ε σ 2 log p l 1 + N a ε γ ε σ 2 . Substituting the tail bound of p l p_l p l
E [ ∥ μ ^ u n b o u n d e d − μ ∥ 2 1 { S ( R ε ) = ∅ } ] = ∑ l = 1 ∞ p l E [ ∥ μ ^ u n b o u n d e d − μ ∥ 2 1 { 2 l − 1 R ε < R ^ ≤ 2 l R ε } ] ≲ ∑ l = 1 p l > 0 ∞ p l ( 4 l − 1 R ε 2 σ 2 N a ε γ ε log 1 p l + σ 2 N a ε γ ε ) ≲ ( i ) σ 2 N a ε γ ε ∑ l = 1 ∞ t l exp ( − t l ) + σ 2 N a ε γ ε ≲ ( i i ) σ 2 N a ε γ ε ≲ σ 2 N a ε . (21) \begin{aligned}
\mathbb{E}\left[\lVert\widehat{\mu}_{\mathrm{unbounded}}-\mu\rVert^2\mathbb{1}\{S(R_\varepsilon)=\varnothing\}\right]
&=\sum_{l=1}^{\infty}p_l\mathbb{E}\left[\lVert\widehat{\mu}_{\mathrm{unbounded}}-\mu\rVert^2\mathbb{1}\{2^{l-1}R_\varepsilon<\widehat{R}\le2^lR_\varepsilon\}\right]\\
&\lesssim\sum_{\substack{l=1\\p_l>0}}^{\infty}p_l\left(4^{l-1}R_\varepsilon^2\sqrt{\frac{\sigma^2}{Na_\varepsilon\gamma_\varepsilon}\log\frac{1}{p_l}}+\frac{\sigma^2}{Na_\varepsilon\gamma_\varepsilon}\right)\\
&\underset{(i)}{\lesssim}\frac{\sigma^2}{Na_\varepsilon\gamma_\varepsilon}\sum_{l=1}^{\infty}t_l\exp(-t_l)+\frac{\sigma^2}{Na_\varepsilon\gamma_\varepsilon}\\
&\underset{(ii)}{\lesssim}\frac{\sigma^2}{Na_\varepsilon\gamma_\varepsilon}\lesssim\frac{\sigma^2}{Na_\varepsilon}. \tag*{(21)}
\end{aligned} E [ ∥ μ unbounded − μ ∥ 2 1 { S ( R ε ) = ∅ } ] = l = 1 ∑ ∞ p l E [ ∥ μ unbounded − μ ∥ 2 1 { 2 l − 1 R ε < R ≤ 2 l R ε } ] ≲ l = 1 p l > 0 ∑ ∞ p l ( 4 l − 1 R ε 2 N a ε γ ε σ 2 log p l 1 + N a ε γ ε σ 2 ) ( i ) ≲ N a ε γ ε σ 2 l = 1 ∑ ∞ t l exp ( − t l ) + N a ε γ ε σ 2 ( ii ) ≲ N a ε γ ε σ 2 ≲ N a ε σ 2 . (21) where (i) by rearranging Equation F.6 to see that p l 4 l − 1 R ε 2 ≤ 64 σ 2 / ( N a ε γ ε ) t l exp ( − t l ) p_l4^{l-1}R_\varepsilon^2\le64\sigma^2/(Na_\varepsilon\gamma_\varepsilon)t_l\exp(-t_l) p l 4 l − 1 R ε 2 ≤ 64 σ 2 / ( N a ε γ ε ) t l exp ( − t l ) x ↦ x log ( 1 / x ) x\mapsto x\log(1/x) x ↦ x log ( 1/ x ) x ∈ ( 0 , 1 / e ) x\in(0,1/e) x ∈ ( 0 , 1/ e ) p l log ( 1 / p l ) ≤ t l exp ( − t l ) p_l\log(1/p_l)\le t_l\exp(-t_l) p l log ( 1/ p l ) ≤ t l exp ( − t l ) l ≥ 1 l\ge1 l ≥ 1 t l t_l t l
Finally, we combine the two cases Equation F.5 and Equation F.7. Note that condition (A) implies that r J 2 ≳ σ 2 N a ε r_J^2\gtrsim\frac{\sigma^2}{Na_\varepsilon} r J 2 ≳ N a ε σ 2
E [ ∥ μ ^ u n b o u n d e d − μ ∥ 2 ] ≲ r J 2 + σ 2 N a ε ≲ r J 2 . \mathbb{E}\left[\lVert\widehat{\mu}_{\mathrm{unbounded}}-\mu\rVert^2\right]\lesssim r_J^2+\frac{\sigma^2}{Na_\varepsilon}\lesssim r_J^2. E [ ∥ μ unbounded − μ ∥ 2 ] ≲ r J 2 + N a ε σ 2 ≲ r J 2 . Lemma F.2. If ε ∈ [ 1 / 4 , 1 / 2 ) \varepsilon\in[1/4,1/2) ε ∈ [ 1/4 , 1/2 ) μ ^ u n b o u n d e d \widehat{\mu}_{\mathrm{unbounded}} μ unbounded
sup μ ∈ K sup C E μ , C [ ∥ μ ^ u n b o u n d e d − μ ∥ 2 ] ≲ r J A 2 ∨ σ 2 ε 2 log ( 1 1 − 2 ε ) . \sup_{\mu\in K}\sup_C \mathbb{E}_{\mu,C}\left[\left\|\widehat{\mu}_{\mathrm{unbounded}}-\mu\right\|^2\right] \lesssim r_{J^A}^2 \vee\sigma^2\varepsilon^2\log\left(\frac{1}{1-2\varepsilon}\right). μ ∈ K sup C sup E μ , C [ ∥ μ unbounded − μ ∥ 2 ] ≲ r J A 2 ∨ σ 2 ε 2 log ( 1 − 2 ε 1 ) . Proof. We first check that both conditions A and B are satisfied at the root J = 1 J=1 J = 1 r 1 = d m C + 1 = 4 2 C + 1 R ε r_1 = \frac{d_m}{C+1} = \frac{4}{2^{C+1}}R_\varepsilon r 1 = C + 1 d m = 2 C + 1 4 R ε r 1 2 ≳ n σ 2 / a ε r_1^2 \gtrsim n\sigma^2/a_\varepsilon r 1 2 ≳ n σ 2 / a ε n ≳ log M l o c ( c 2 r 1 , c ) n \gtrsim\log M^{\mathrm{loc}}(c^2r_1,c) n ≳ log M loc ( c 2 r 1 , c ) a ε z ε ≲ 1 a_\varepsilon z_\varepsilon\lesssim1 a ε z ε ≲ 1 Q 5 Q_5 Q 5 J ∗ J^* J ∗
sup μ ∈ K sup C E μ , C [ ∥ μ ^ u n b o u n d e d − μ ∥ 2 ] ≲ r J ∗ 2 . \sup_{\mu\in K}\sup_C \mathbb{E}_{\mu,C}\left[\left\|\widehat{\mu}_{\mathrm{unbounded}}-\mu\right\|^2\right] \lesssim r_{J^*}^2. μ ∈ K sup C sup E μ , C [ ∥ μ unbounded − μ ∥ 2 ] ≲ r J ∗ 2 . At step J B + 1 J^B+1 J B + 1 B fails, which gives r J B / 2 = r J B + 1 < D 1 ε σ z ε r_{J^B}/2=r_{J^B+1}<D_1\varepsilon\sigma\sqrt{z_\varepsilon} r J B /2 = r J B + 1 < D 1 ε σ z ε J ∗ = J A ∧ J B J^*=J^A\wedge J^B J ∗ = J A ∧ J B r J ∗ 2 = r J A ∧ J B 2 = r J A 2 ∨ r J B 2 ≲ r J A ∨ σ 2 ε 2 log ( 1 / ( 1 − 2 ε ) ) r_{J^*}^2=r_{J^A\wedge J^B}^2=r_{J^A}^2\vee r_{J^B}^2\lesssim r_{J^A}\vee\sigma^2\varepsilon^2\log\left(1/(1-2\varepsilon)\right) r J ∗ 2 = r J A ∧ J B 2 = r J A 2 ∨ r J B 2 ≲ r J A ∨ σ 2 ε 2 log ( 1/ ( 1 − 2 ε ) )
Proof of Theorem 2.4 . The regime ε ∈ [ 0 , 1 / 4 ) \varepsilon\in[0,1/4) ε ∈ [ 0 , 1/4 ) [13 ] [Theorem 5.9] and the rate matching argument as in Proposition 2.1. For ε ∈ [ 1 / 4 , 1 / 2 ) \varepsilon\in[1/4,1/2) ε ∈ [ 1/4 , 1/2 ) K K K K K K κ ε : = a ε N δ ε ∗ 2 / σ 2 \kappa_\varepsilon:= a_\varepsilon N\delta_\varepsilon^{*2}/\sigma^2 κ ε := a ε N δ ε ∗ 2 / σ 2 r J A ≲ δ ε ∗ r_{J^A}\lesssim\delta_\varepsilon^* r J A ≲ δ ε ∗ ε ∈ [ 0 , 1 / 2 ) \varepsilon\in[0,1/2) ε ∈ [ 0 , 1/2 )
