Minimax Lower Bounds

Chapter Minimax Lower Bounds In the previous chapters, we have proved several upper bounds and the goal of this chapter is to assess their optimality. Specifically, our goal is to answer the following questions: 1. Can our analysis be improved? In other words: do the estimators that we have studied actually satisfy better bounds? 2. Can any estimator improve upon these bounds? Both questions ask about some form of optimality. The first one is about optimality of an estimator, whereas the second one is about optimality of a bound. The difficulty of these questions varies depending on whether we are looking for a positive or a negative answer. Indeed, a positive answer to these questions simply consists in finding a better proof for the estimator we have studied (question 1.) or simply finding a better estimator, together with a proof that it performs better (question 2.). A negative answer is much more arduous. For example, in question 2., it is a statement about all estimators. How can this be done? The answer lies in information theory (see [CT06] for a nice introduction). In this chapter, we will see how to give a negative answer to question 2. It will imply a negative answer to question 1. Θ φ(Θ) B1 σ2 d n r log d σ n B0 (k) σ2 k log(ed/k) n IRd Estimator Result θ̂ls Theorem 2.2 ls θ̂B 1 Theorem 2.4 ls θˆB 0 (k) Corollaries 2.8-2.9 Table 5.1. Rate φ(Θ) obtained for different choices of Θ. 5.1 OPTIMALITY IN A MINIMAX SENSE Consider the Gaussian Sequence Model (GSM) where we observe Y = (Y1 , . . . , Yd )⊤ , defined by Yi = θi∗ + εi , i = 1, . . . , d , (5.1) 2 where ε = (ε1 , . . . , εd )⊤ ∼ Nd (0, σn Id ), θ∗ = (θ1∗ , . . . , θd∗ )⊤ ∈ Θ is the parameter of interest and Θ ⊂ IRd is a given set of parameters. We will need a more precise notation for probabilities and expectations throughout this chapter. Denote by IPθ∗ and IEθ∗ the probability measure and corresponding expectation that are associated to the distribution of Y from the GSM (5.1). Recall that GSM is a special case of the linear regression model when the design matrix satisfies the ORT condition. In this case, we have proved several performance guarantees (upper bounds) for various choices of Θ that can be expressed either in the form   IE |θ̂n − θ∗ |22 ≤ Cφ(Θ) (5.2) or the form |θ̂n − θ∗ |22 ≤ Cφ(Θ) , with prob. 1 − d−2 (5.3) For some constant C. The rates φ(Θ) for different choices of Θ that we have obtained are gathered in Table 5.1 together with the estimator (and the corresponding result from Chapter 2) that was employed to obtain this rate. Can any of these results be improved? In other words, does there exists another estimator θ˜ such that supθ∗ ∈Θ IE|θ˜ − θ∗ |22 ≪ φ(Θ)? A first step in this direction is the Cramér-Rao lower bound [Sha03] that allows us to prove lower bounds in terms of the Fisher information. Nevertheless, this notion of optimality is too stringent and often leads to nonexistence of optimal estimators. Rather, we prefer here the notion of minimax optimality that characterizes how fast θ∗ can be estimated uniformly over Θ. Definition 5.1. We say that an estimator θˆn is minimax optimal over Θ if it satisfies (5.2) and there exists C ′ > 0 such that   (5.4) inf sup IEθ φ−1 (Θ)|θˆ − θ|22 ≥ C ′ θ̂ θ∈Θ where the infimum is taker over all estimators (i.e., measurable functions of Y). Moreover, φ(Θ) is called minimax rate of estimation over Θ. Note that minimax rates of convergence φ are defined up to multiplicative constants. We may then choose this constant such that the minimax rate has a simple form such as σ 2 d/n as opposed to 7σ 2 d/n for example. This definition can be adapted to rates that hold with high probability. As we saw in Chapter 2 (Cf. Table 5.1), the upper bounds in expectation and those with high probability are of the same order of magnitude. It is also the case for lower bounds. Indeed, observe that it follows from the Markov inequality that for any A > 0,     IEθ φ−1 (Θ)|θˆ − θ|22 ≥ AIPθ φ−1 (Θ)|θˆ − θ|22 > A (5.5) Therefore, (5.6) follows if we prove that   inf sup IPθ |θˆ − θ|22 > Aφ(Θ) ≥ C” θ̂ θ∈Θ for some positive constants A and C”. The above inequality also implies a lower bound with high probability. We can therefore employ the following alternate definition for minimax optimality. Definition 5.2. We say that an estimator θˆ is minimax optimal over Θ if it satisfies either (5.2) or (5.3) and there exists C ′ > 0 such that   inf sup IPθ |θˆ − θ|22 > φ(Θ) ≥ C ′ (5.6) θ̂ θ∈Θ where the infimum is taker over all estimators (i.e., measurable functions of Y). Moreover, φ(Θ) is called minimax rate of estimation over Θ. 5.2 REDUCTION TO FINITE HYPOTHESIS TESTING Minimax lower bounds rely on information theory and follow from a simple principle: if the number of observations is too small, it may be hard to distinguish between two probability distributions that are close to each other. For example, given n i.i.d. observations, it is impossible to reliably decide whether they are drawn from N (0, 1) or N ( n1 , 1). This simple argument can be made precise using the formalism of statistical hypothesis testing. To do so, we reduce our estimation problem to a testing problem. The reduction consists of two steps. 1. Reduction to a finite number of hypotheses. In this step the goal is to find the largest possible number of hypotheses θ1 , . . . , θM ∈ Θ under the constraint that |θj − θk |22 ≥ 4φ(Θ) . (5.7) This problem boils down to a packing of the set Θ. Then we can use the following trivial observations:     inf sup IPθ |θˆ − θ|22 > φ(Θ) ≥ inf max IPθj |θˆ − θj |22 > φ(Θ) . θˆ 1≤j≤M θ̂ θ∈Θ 2. Reduction to a testing problem. In this second step, the necessity of the constraint (5.7) becomes apparent. ˆ define the minimum distance test ψ(θ) ˆ that is assoFor any estimator θ, ciated to it by ˆ = argmin |θˆ − θj |2 , ψ(θ) 1≤j ≤M with ties broken arbitrarily. ˆ 6= j, then there exists Next observe that if, for some j = 1, . . . , M , ψ(θ) k 6= j such that |θˆ − θk |2 ≤ |θˆ − θj |2 . Together with the reverse triangle inequality it yields |θˆ − θj |2 ≥ |θj − θk |2 − |θˆ − θk |2 ≥ |θj − θk |2 − |θˆ − θj |2 so that 1 |θj − θk |2 2 Together with constraint (5.7), it yields |θ̂ − θj |2 ≥ |θ̂ − θj |22 ≥ φ(Θ) As a result,     ˆ = inf max IPθj |θ̂ − θj |22 > φ(Θ) ≥ inf max IPθj ψ (θ) 6 j θˆ 1≤j≤M θˆ 1≤j ≤M   ≥ inf max IPθj ψ = 6 j ψ 1≤j≤M where the infimum is taken over all tests based on Y and that take values in {1, . . . , M }. Conclusion: it is sufficient for proving lower bounds to find θ1 , . . . , θM ∈ Θ such that |θj − θk |22 ≥ 4φ(Θ) and   6 j ≥ C′ . inf max IPθj ψ = ψ 1≤j≤M The above quantity is called minimax probability of error. In the next sections, we show how it can be bounded from below using arguments from information theory. For the purpose of illustration, we begin with the simple case where M = 2 in the next section. 5.3 LOWER BOUNDS BASED ON TWO HYPOTHESES The Neyman-Pearson Lemma and the total variation distance Consider two probability measures IP0 and IP1 and observations X drawn from either IP0 or IP1 . We want to know which distribution X comes from. It corresponds to the following statistical hypothesis problem: H0 : H1 : Z ∼ IP0 Z ∼ IP1 A test ψ = ψ(Z) ∈ {0, 1} indicates which hypothesis should be true. Any test ψ can make two types of errors. It can commit either an error of type I (ψ = 1 whereas Z ∼ IP0 ) or an error of type II (ψ = 0 whereas Z ∼ IP1 ). Of course, the test may also be correct. The following fundamental result, called the Neyman Pearson Lemma indicates that any test ψ is bound to commit one of these two types of error with positive probability unless IP0 and IP1 have essentially disjoint support. Let ν be a sigma finite measure satisfying IP0 ≪ ν and IP1 ≪ ν. For example we can take ν = IP0 + IP1 . It follows from the Radon-Nikodym theorem [Bil95] that both IP0 and IP1 admit probability densities with respect to ν. We denote them by p0 and p1 respectively. For any function f , we write for simplicity Z Z f = f (x)ν(dx) Lemma 5.3 (Neyman-Pearson). Let IP0 and IP1 be two probability measures. Then for any test ψ, it holds Z IP0 (ψ = 1) + IP1 (ψ = 0) ≥ min(p0 , p1 ) Moreover, equality holds for the Likelihood Ratio test ψ ⋆ = 1I(p1 ≥ p0 ). Proof. Observe first that IP0 (ψ ⋆ = 1) + IP1 (ψ ⋆ = 0) = Z p0 + ψ ∗ =1 = Z Z p1 ≥p0 = Z p1 ψ ∗ =0 p0 + p1 ≥p0 = Z Z p1 Z min(p0 , p1 ) + p1 0 = −2 Z p q p log r q  p hr q i  = −2 p log −1 +1 p pq>0 Z hr q i ≥ −2 p −1 (by Jensen) p pq>0 Z √ =2−2 pq pq>0 Z Next, note that  Z √ 2  Z p 2 pq = max(p, q) min(p, q) Z Z ≤ max(p, q) min(p, q) (by Cauchy-Schwarz) Z Z   = 2 − min(p, q) min(p, q)

= 1 + TV(IP, Q) 1 − TV(IP, Q) = 1 − TV(IP, Q)2 The two displays yield p 1 − TV(IP, Q)2 ≥ TV(IP, Q)2 , √ where we used the fact that 0 ≤ TV(IP, Q) ≤ 1 and 1 − x ≤ 1 − x/2 for x ∈ [0, 1]. KL(IP, Q) ≥ 2 − 2 Pinsker’s inequality yields the following theorem for the GSM. Theorem 5.9. Assume that Θ contains two hypotheses θ0 and θ1 such that |θ0 − θ1 |22 = 8α2 σ 2 /n for some α ∈ (0, 1/2). Then inf sup IPθ (|θˆ − θ|22 ≥ θ̂ θ ∈Θ 2ασ 2 1 ) ≥ −α. n 2 Proof. Write for simplicity IPj = IPθj , j = 0, 1. Recall that it follows from the reduction to hypothesis testing that inf sup IPθ (|θˆ − θ|22 ≥ θ̂ θ ∈Θ 2ασ 2 ) ≥ inf max IPj (ψ = 6 j) ψ j=0,1 n   1 ≥ inf IP0 (ψ = 1) + IP1 (ψ = 0) 2 ψ i 1h = 1 − TV(IP0 , IP1 ) (Prop.-def. 5.4) 2 i p 1h ≥ 1 − KL(IP1 , IP0 ) (Lemma 5.8) 2 r 1h n|θ1 − θ0 |22 i = 1− (Example 5.7) 2 2σ 2 i 1h = 1 − 2α 2 Clearly the result of Theorem 5.9 matches the upper bound for Θ = IRd only for d = 1. How about larger d? A quick inspection of our proof shows that our technique, in its present state, cannot yield better results. Indeed, there are only two known candidates for the choice of θ∗ . With this knowledge, one can obtain upper bounds that do not depend on d by simply projecting Y onto the linear span of θ0 , θ1 and then solving the GSM in two dimensions. To obtain larger lower bounds, we need to use more than two hypotheses. In particular, in view of the above discussion, we need a set of hypotheses that spans a linear space of dimension proportional to d. In principle, we should need at least order d hypotheses but we will actually need much more. 5.4 LOWER BOUNDS BASED ON MANY HYPOTHESES The reduction to hypothesis testing from Section 5.2 allows us to use more than two hypotheses. Specifically, we should find θ1 , . . . , θM such that   6 j ≥ C′ , inf max IPθj ψ = ψ 1≤j≤M for some positive constant C ′ . Unfortunately, the Neyman-Pearson Lemma no longer exists for more than two hypotheses. Nevertheless, it is possible to relate the minimax probability of error directly to the Kullback-Leibler divergence, without involving the total variation distance. This is possible using a well known result from information theory called Fano’s inequality. We use it in a form that is tailored to our purposes and that is due to Lucien Birgé [Bir83] and builds upon an original result in [IH81]. Theorem 5.10 (Fano’s inequality). Let P1 , . . . , PM , M ≥ 2 be probability distributions such that Pj ≪ Pk , ∀ j, k. Then PM 1   j,k=1 KL(Pj , Pk ) + log 2 M2 inf max Pj ψ(X) = 6 j ≥1− ψ 1≤j≤M log(M − 1) where the infimum is taken over all tests with values in {1, . . . , M }. Proof. Let Z ∈ {1, . . . , M } be a random variable such that IP(Z = i) = 1/M and let X ∼ PZ . Note that PZ is a mixture distribution so that for any measure ν such that PZ ≪ ν, we have M dPZ 1 X dPj = . dν M j=1 dν For all test ψ, we have M X j =1 IP(Z = j|X) log[IP(Z = j |X)] = = IP(Z = ψ(X)|X) log[IP(Z = ψ(X)|X)] + X IP(Z = j|X) log[IP(Z = j|X)] j=ψ(X) 6 = (1 − IP(Z = 6 ψ(X)|X)) log[1 − IP(Z = 6 ψ(X)|X)] h IP(Z = j |X) i X IP(Z = j |X) + IP(Z = 6 ψ(X)|X ) log IP(Z = 6 ψ(X)|X) IP(Z = 6 ψ(X)|X) j=ψ(X) 6 + IP(Z = 6 ψ(X)|X) log[IP(Z = 6 ψ(X)|X)] 6 ψ(X)|X)) + IP(Z = 6 ψ(X)|X) = h(IP(Z = X qj log(qj ) , 6 ψ(X) j= where h(x) = x log(x) + (1 − x) log(1 − x) and qj = is such that qj ≥ 0 and X j=ψ(X) 6 qj log(qj ) = − P IP(Z = j |X) IP(Z = 6 ψ(X)|X) qj j=ψ(X) 6 X qj log j=ψ(X) 6 = 1. It implies by Jensen’s inequality that 1 qj ≥ − log  X 6 j=ψ(X) qj  = − log(M − 1) . qj By the same convexity argument, we get h(x) ≥ − log 2. It yields M X j=1 6 ψ(X)|X) log(M − 1) . IP(Z = j|X) log[IP(Z = j|X)] ≥ − log 2 − IP(Z = (5.8) Next, observe that since X ∼ PZ , the random variable IP(Z = j|X) satisfies IP(Z = j|X) = dPj (X) 1 dPj (X) = PM M dPZ k=1 dPk (X) It implies Z nX M j=1 o IP(Z = j|X = x) log[IP(Z = j|X = x)] dPZ (x) M Z n  1 dP o X 1 dPj j = (x) log (x) dPZ (x) M dPZ M dPZ j=1 M Z   1 X dPj (x) = log PM dPj (x) M j=1 k=1 dPk (x) ≤ = M Z  dP (x)  1 X j log dPj (x) − log M dPk (x) M2 (by Jensen) j,k=1 M 1 X KL(Pj , Pk ) − log M , M2 j,k=1 Together with (5.8), it yields M 1 X KL(Pj , Pk ) − log M ≥ − log 2 − IP(Z 6= ψ(X)) log(M − 1) M2 j,k=1 Since IP(Z 6= ψ(X)) = M 1 X Pj (ψ(X) 6= j) ≤ max Pj (ψ(X) = 6 j) , 1≤j ≤M M j=1 this implies the desired result. Fano’s inequality leads to the following useful theorem. Theorem 5.11. Assume that Θ contains M ≥ 5 hypotheses θ1 , . . . , θM such that for some constant 0 < α < 1/4, it holds (i) |θj − θk |22 ≥ 4φ (ii) |θj − θk |22 ≤ Then 2ασ 2 log(M ) n
1 inf sup IPθ |θˆ − θ|22 ≥ φ ≥ − 2α . 2 θ̂ θ ∈Θ Proof. in view of (i), it follows from the reduction to hypothesis testing that it is sufficient to prove that   1 inf max IPθj ψ 6= j ≥ − 2α ψ 1≤j≤M 2 If follows from (ii) and Example 5.7 that KL(IPj , IPk ) = n|θj − θk |22 ≤ α log(M ) . 2σ 2 Moreover, since M ≥ 5, 1 M2 PM j,k=1 KL(IPj , IPk ) + log 2 log(M − 1) ≤ α log(M ) + log 2 1 ≤ 2α + . log(M − 1) 2 The proof then follows from Fano’s inequality. 2 Theorem 5.11 indicates that we must take φ ≤ ασ 2n log(M ). Therefore, the larger the M , the larger the lower bound can be. However, M cannot be arbitrary larger because of the constraint (i). We are therefore facing a packing problem wp here the goal is to “pack” as many Euclidean balls of radius proportional to σ log(M )/n in Θ under the constraint that their centers remain close together (constraint (p ii)). If Θ = IRd , this the goal is to pack the Euclidean p ball of radius R = σ 2α log(M )/n with Euclidean balls of radius R 2α/γ. This can be done using a volume argument (see Problem 5.3). However, we will use the more versatile lemma below. It gives a a lower bound on the size of a packing of the discrete hypercube {0, 1}d with respect to the Hamming distance defined by ρ(ω, ω ′ ) = d X i=1 1I(ωi = 6 ωj′ ) , ∀ ω, ω ′ ∈ {0, 1}d Lemma 5.12 (Varshamov-Gilbert). For any γ ∈ (0, 1/2), there exist binary vectors ω1 , . . . ωM ∈ {0, 1}d such that (i) ρ(ωj , ωk ) ≥ 2
1 − γ d for all j 6= k , 2 (ii) M = ⌊eγ d ⌋ ≥ e γ2d 2 . Proof. Let ωj,i , 1 ≤ i ≤ d, 1 ≤ j ≤ M to be i.i.d Bernoulli random variables with parameter 1/2 and observe that d − ρ(ωj , ωk ) = X ∼ Bin(d, 1/2) . Therefore it follows from a union bound that

 M (M − 1) 1 d IP ∃j 6= k , ρ(ωj , ωk ) < −γ d ≤ IP X − > γd . 2 2 2 Hoeffding’s inequality then yields 
M (M − 1) d M (M − 1)
 IP X − > γd ≤ exp − 2γ 2 d + log <1 2 2 2 as soon as   M (M − 1) < 2 exp 2γ 2 d 2 A sufficient condition for the above inequality to hold is to take M = ⌊eγ d ⌋ ≥ e γ2d 2 . For this value of M , we have IP ∀j 6= k , ρ(ωj , ωk ) ≥

1 −γ d >0 2 and by virtue of the probabilistic method, there exist ω1 , . . . ωM ∈ {0, 1}d that satisfy (i) and (ii) 5.5 APPLICATION TO THE GAUSSIAN SEQUENCE MODEL We are now in a position to apply Theorem 5.11 by choosing θ1 , . . . , θM based on ω1 , . . . , ωM from the Varshamov-Gilbert Lemma. Lower bounds for estimation Take γ = 1/4 and apply the Varshamov-Gilbert Lemma to obtain ω1 , . . . , ωM with M = ⌊ed/16 ⌋ ≥ ed/32 and such that ρ(ωj , ωk ) ≥ d/4 for all j 6= k. Let θ1 , . . . , θM be such that βσ θj = ω j √ , n for some β > 0 to be chosen later. We can check the conditions of Theorem 5.11: (i) |θj − θk |22 = (ii) |θj − θk |22 = for β = √ α 4 . β 2 σ2 β 2 σ2 d ρ(ωj , ωk ) ≥ 4 n 16n β 2 σ2 β 2 σ2 d 32β 2 σ 2 2ασ 2 ρ(ωj , ωk ) ≤ ≤ log(M ) = log(M ) , n n n n Applying now Theorem 5.11 yields α σ2 d
1 inf sup IPθ |θˆ − θ|22 ≥ ≥ − 2α . 256 n 2 θ̂ θ ∈IRd It implies the following corollary. Corollary 5.13. The minimax rate of estimation of over IRd in the Gaussian sequence model is φ(IRd ) = σ 2 d/n. Moreover, it is attained by the least squares estimator θˆls = Y. Note that this rate is minimax over sets Θ that are strictly smaller than IRd (see Problem 5.4). Indeed, it is minimax over any subset of IRd that contains θ1 , . . . , θM . Lower bounds for sparse estimation It appears from Table 5.1 that when estimating sparse vectors, we have to pay for an extra logarithmic term log(ed/k) for not knowing the sparsity pattern of the unknown θ∗ . In this section, we show that this term is unavoidable as it appears in the minimax optimal rate of estimation of sparse vectors. Note that the vectors θ1 , . . . , θM employed in the previous subsection are not guaranteed to be sparse because the vectors ω1 , . . . , ωM obtained from the Varshamov-Gilbert Lemma may themselves not be sparse. To overcome this limitation, we need a sparse version of the Varhsamov-Gilbert lemma. Lemma 5.14 (Sparse Varshamov-Gilbert). There exist positive constants C1 and C2 such that the following holds for any two integers k and d such that 1 ≤ k ≤ d/8. There exist binary vectors ω1 , . . . ωM ∈ {0, 1}d such that (i) ρ(ωi , ωj ) ≥ (ii) log(M ) ≥ k for all i 6= j , 2 k d log(1 + ). 8 2k (iii) |ωj |0 = k for all j . Proof. Take ω1 , . . . , ωM independently and uniformly at random from the set C0 (k) = {ω ∈ {0, 1}d : |ω|0 = k} ,
of k-sparse binary random vectors. Note that C0 (k) has cardinality kd . To choose ωj uniformly from C0 (k), we proceed as follows. Let U1 , . . . , Uk ∈ {1, . . . , d} be k random variables such that U1 is drawn uniformly at random from {1, . . . , d} and for any i = 2, . . . , k, conditionally on U1 , . . . , Ui−1 , the random variable Ui is drawn uniformly at random from {1, . . . , d}\{U1, . . . , Ui−1 }. Then define  1 if i ∈ {U1 , . . . , Uk } ω= 0 otherwise . Clearly, all outcomes in C0 (k) are equally likely under this distribution and therefore, ω is uniformly distributed on C0 (k). Observe that
1 IP ∃ ωj 6= ωk : ρ(ωj , ωk ) < k = d
k ≤ 1
d k X IP ∃ ωj 6= x : ρ(ωj , x) < X M X x∈{0,1}d |x|0 =k x∈{0,1}d j=1 |x|0 =k k
2 IP ωj 6= x : ρ(ωj , x) < = M IP ω = 6 x0 : ρ(ω, x0 ) < k
2 k
2 where ω has the same distribution as ω1 and x0 is any k-sparse vector in {0, 1}d. The last equality holds by symmetry since (i) all the ωj s have the same distribution and (ii) all the outcomes of ωj are equally likely. Note that k X ρ(ω, x0 ) ≥ k − Zi , i=1 where Zi = 1I(Ui ∈ supp(x0 )). Indeed the left hand side is the number of coordinates on which the vectors ω, x0 disagree and the right hand side is the number of coordinates in supp(x0 ) on which the two vectors disagree. In particular, we have that, Z1 ∼ Ber(k/d) and for any i = 2, . . . , d, conditionally on Z1 , . . . , Zi−i , we have Zi ∼ Ber(Qi ), where P k − i−1 k 2k l=1 Zl Qi = ≤ ≤ p − (i − 1) d−k d since k ≤ d/2. Next we apply a Chernoff bound to get that for any s > 0, k k h X X
i sk k
k
≤ IP Zi > = IE exp s Zi e− 2 2 2 i=1 i=1 IP ω 6= x0 : ρ(ω, x0 ) < The above MGF can be controlled by induction on k as follows: k k−1 h h X X
i

i IE exp s Zi = IE exp s Zi IE exp sZk Z1 , . . . , Zk=1 i=1 i=1 h = IE exp s h ≤ IE exp s .. . ≤ k−1 X i=1 k −1 X i=1 i
Zi (Qk (es − 1) + 1) Zi
i 2k s
(e − 1) + 1 d
k 2k s (e − 1) + 1 d = 2k For s = log(1 + d 2k ). Putting everything together, we get 
IP ∃ ωj = 6 ωk : ρ(ωj , ωk ) < k ≤ exp log M  = exp log M  ≤ exp log M  ≤ exp log M < 1. sk  2 k + k log 2 − log(1 + 2 k + k log 2 − log(1 + 2 k d  − log(1 + ) 4 2k + k log 2 − d  ) 2k d  ) 2k (for d ≥ 8k) If we take M such that log M < k d log(1 + ) 4 2k Apply the sparse Varshamov-Gilbert lemma to obtain ω1 , . . . , ωM with d 6 k. Let log(M ) ≥ k8 log(1 + 2k ) and such that ρ(ωj , ωk ) ≥ k/2 for all j = θ1 , . . . , θM be such that r βσ d log(1 + ), θj = ω j √ n 2k for some β > 0 to be chosen later. We can check the conditions of Theorem 5.11: (i) |θj − θk |22 = (ii) |θj −θk |22 = for β = pα 8. β 2 σ2 d β 2 σ2 d ρ(ωj , ωk ) log(1 + )≥4 k log(1 + ) n 2k 8n 2k d 2ασ 2 β 2 σ2 d 2kβ 2 σ 2 ρ(ωj , ωk ) log(1+ ) ≤ log(1+ ) ≤ log(M ) , n 2k n 2k n Applying now Theorem 5.11 yields α2 σ 2 d
1 inf sup IPθ |θˆ − θ|22 ≥ k log(1 + ) ≥ − 2α . 64n 2k 2 θ̂ θ∈IRd |θ|0 ≤k It implies the following corollary. Corollary 5.15. Recall that B0 (k) ⊂ IRd denotes the set of all k-sparse vectors of IRd . The minimax rate of estimation over B0 (k) in the Gaussian sequence 2 model is φ(B0 (k)) = σnk log(ed/k). Moreover, it is attained by the constrained ls least squares estimator θˆB . 0 (k) Note that the modified BIC estimator of Problem 2.6 is also minimax opls timal over B0 (k) but unlike θˆB , it is also adaptive to k. For any ε > 0, 0 (k) the Lasso estimator and the BIC estimator are minimax optimal for sets of parameters such that k ≤ d1−ε . Lower bounds for estimating vectors in ℓ1 balls Recall that in Maurey’s argument, we q approximated a vector θ such that |θ|1 = n R by a vector θ′ such that |θ′ |0 = R σ log d . We can essentially do the same for the lower bound. √ Assume that d ≥ n and let β ∈ (0, 1) be a parameter to be chosen later and define k to be the smallest integer such that r R n √ . k≥ βσ log(ed/ n) Let ω1 , . . . , ωM be obtained from the sparse Varshamov-Gilbert Lemma 5.14 with this choice of k and define θj = ω j R . k Observe that |θj |1 = R for j = 1, . . . , M . We can check the conditions of Theorem 5.11: √ R2 R2 R 2 log(ed/ n)
(i) |θj − θk |22 = 2 ρ(ωj , ωk ) ≥ ≥ 4R min ,β σ . 8 8n k 2k r √ 2R2 log(ed/ n) 2ασ 2 2 (ii) |θj − θk |2 ≤ ≤ 4Rβσ ≤ log(M ) , k n n for β small enough if d ≥ Ck for some constant C > 0 chosen large enough. Applying now Theorem 5.11 yields √ R 2 2 log(ed/ n)

1 inf sup IPθ |θ̂ − θ|22 ≥ R min ,β σ ≥ − 2α . 8 8n 2 θ̂ θ∈IRd It implies the following corollary. Corollary 5.16. Recall that B1 (R) ⊂ IRd denotes the set vectors θ ∈ IRd such that |θ|1 ≤ R. Then there exist a constant C > 0 such that if d ≥ n1/2+ε , ε > 0, the minimax rate of estimation over B1 (R) in the Gaussian sequence model is log d φ(B0 (k)) = min(R2 , Rσ ). n Moreover, it is attained by the constrained least squares estimator θˆls if R ≥ σ logn d and by the trivial estimator θˆ = 0 otherwise. B1 (R) Proof. To complete the proof of the statement, we need to study risk of the trivial estimator equal to zero for small R. Note that if |θ∗ |1 ≤ R, we have |0 − θ∗ |22 = |θ∗ |22 ≤ |θ∗ |21 = R2 . Remark 5.17. Note that the inequality |θ∗ |22 ≤ |θ∗ |21 appears to be quite loose. Nevertheless, it is tight up to a multiplicative constant for the vectors of the log d form θj = ωj R k that are employed in the lower bound. Indeed, if R ≤ σ n , we have k ≤ 2/β R2 β |θj |22 = ≥ |θj |21 . k 2