Misspecified Linear Models

Chapter Misspecified Linear Models Arguably, the strongest assumption that we made in Chapter 2 is that the regression function f (x) is of the form f (x) = x⊤ θ∗ . What if this assumption is violated? In reality, we do not really believe in the linear model and we hope that good statistical methods should be robust to deviations from this model. This is the problem of model misspecified linear models. Throughout this chapter, we assume the following model: Yi = f (Xi ) + εi , i = 1, . . . , n , (3.1) where ε = (ε1 , . . . , εn )⊤ is sub-Gaussian with variance proxy σ 2 . Here Xi ∈ IRd . When dealing with fixed design, it will be convenient to consider the vector g ∈ IRn defined for any function g : IRd → IR by g = (g(X1 ), . . . , g(Xn ))⊤ . In this case, we can write for any estimator fˆ ∈ IRn of f , 1 MSE(fˆ) = |fˆ − f |22 . n Even though the model may not be linear, we are interested in studying the statistical properties of various linear estimators introduced in the previous ls ˜ls ˆbic ˆL chapters: θˆls , θˆK , θX , θ , θ . Clearly, even with an infinite number of observations, we have no chance of finding a consistent estimator of f if we don’t know the correct model. Nevertheless, as we will see in this chapter something can still be said about these estimators using oracle inequalities. 3.1 ORACLE INEQUALITIES Oracle inequalities As mentioned in the introduction, an oracle is a quantity that cannot be constructed without the knowledge of the quantity of interest, here: the regression function. Unlike the regression function itself, an oracle is constrained to take a specific form. For all matter of purposes, an oracle can be viewed as an estimator (in a given family) that can be constructed with an infinite amount of data. This is exactly what we should aim for in misspecified models. When employing the least squares estimator θˆls , we constrain ourselves to estimating functions that are of the form x 7→ x⊤ θ, even though f itself may not be of this form. Therefore, the oracle fˆ is the linear function that is the closest to f . Rather than trying to approximate f by a linear function f (x) ≈ θ⊤ x, we make the model a bit more general and consider a dictionary H = {ϕ1 , . . . , ϕM } of functions where ϕj : IRd → IR. In the case, we can actually remove the assumption that X ∈ IRd . Indeed, the goal is now to estimate f using a linear combination of the functions in the dictionary: f ≈ ϕθ := M X θj ϕj . j=1 Remark 3.1. If M = d and ϕj (X) = X (j) returns the jth coordinate of X ∈ IRd then the goal is to approximate f (x) by θ⊤ x. Nevertheless, the use of a dictionary allows for a much more general framework. Note that the use of a dictionary does not affect the methods that we have been using so far, namely penalized/constrained least squares. We use the same notation as before and define 1. The least squares estimator: θ̂ls ∈ argmin θ ∈IRM n
2 1X Yi − ϕθ (Xi ) n i=1 (3.2) 2. The least squares estimator constrained to K ⊂ IRM : ls θ̂K ∈ argmin θ ∈K n
2 1X Yi − ϕθ (Xi ) n i=1 3. The BIC estimator: θ̂bic ∈ argmin θ ∈IRM n n1 X n i=1 o
2 Yi − ϕθ (Xi ) + τ 2 |θ|0 (3.3) 4. The Lasso estimator: θ̂L ∈ argmin θ ∈IRM n n1 X n i=1 o
2 Yi − ϕθ (Xi ) + 2τ |θ|1 (3.4) Definition 3.2. Let R(·) be a risk function and let H = {ϕ1 , . . . , ϕM } be a dictionary of functions from IRd to IR. Let K be a subset of IRM . The oracle on K with respect to R is defined by ϕθ̄ , where θ¯ ∈ K is such that R(ϕθ̄ ) ≤ R(ϕθ ) , ∀θ ∈ K . Moreover, RK = R(ϕθ̄ ) is called oracle risk on K. An estimator fˆ is said to satisfy an oracle inequality (over K) with remainder term φ in expectation (resp. with high probability) if there exists a constant C ≥ 1 such that IER(fˆ) ≤ C inf R(ϕθ ) + φn,M (K) , θ∈K or  IP R(fˆ) ≤ C inf R(ϕθ ) + φn,M,δ (K) ≥ 1 − δ , θ∈K ∀δ>0 respectively. If C = 1, the oracle inequality is sometimes called exact. Our goal will be to mimic oracles. The finite sample performance of an estimator at this task is captured by an oracle inequality. Oracle inequality for the least squares estimator While our ultimate goal is to prove sparse oracle inequalities for the BIC and Lasso estimator in the case of misspecified model, the difficulty of the extension to this case for linear models, is essentially already captured for the least squares estimator. In this simple case, can even obtain an exact oracle inequality. Theorem 3.3. Assume the general regression model (3.1) with ε ∼ subGn (σ 2 ). Then, the least squares estimator θˆls satisfies for some numerical constant C > 0, σ2 M MSE(ϕθˆls ) ≤ inf MSE(ϕθ ) + C log(1/δ) n θ∈IRM with probability at least 1 − δ. Proof. Note that by definition |Y − ϕθ̂ls |22 ≤ |Y − ϕθ̄ |22 where ϕθ̄ denotes the orthogonal projection of f onto the linear spam of ϕ1 , . . . , ϕn . Since Y = f + ε, we get |f − ϕθˆls |22 ≤ |f − ϕθ¯|22 + 2ε⊤ (ϕθˆls − ϕθ¯) Moreover, by Pythagoras’s theorem, we have |f − ϕθˆls |22 − |f − ϕθ¯|22 = |ϕθˆls − ϕθ¯|22 . It yields |ϕθ̂ls − ϕθ̄ |22 ≤ 2ε⊤ (ϕθ̂ls − ϕθ̄ ) . Using the same steps as the ones following equation (2.5) for the well specified case, we get σ2 M |ϕθˆls − ϕθ̄ |22 . log(1/δ) n with probability 1 − δ. The result of the lemma follows. Sparse oracle inequality for the BIC estimator The techniques that we have developed for the linear model above also allows to derive oracle inequalities. Theorem 3.4. Assume the general regression model (3.1) with ε ∼ subGn (σ 2 ). Then, the BIC estimator θˆbic with regularization parameter τ2 = 16σ 2 log(6eM ) , α ∈ (0, 1) αn (3.5) satisfies for some numerical constant C > 0, MSE(ϕθˆbic ) ≤ inf θ∈IRM n1 + α 1−α MSE(ϕθ )+ o Cσ 2 |θ|0 log(eM ) α(1 − α)n Cσ 2 + log(1/δ) α(1 − α)n with probability at least 1 − δ. Proof. Recall the the proof of Theorem 2.14 for the BIC estimator begins as follows: 1 1 |Y − ϕθˆbic |22 + τ 2 |θˆbic |0 ≤ |Y − ϕθ |22 + τ 2 |θ|0 . n n This is true for any θ ∈ IRM . It implies |f − ϕθˆbic |22 + nτ 2 |θˆbic |0 ≤ |f − ϕθ |22 + 2ε⊤ (ϕθˆbic − ϕθ ) + nτ 2 |θ|0 . Note that if θˆbic = θ, the result is trivial. Otherwise,  ϕ −ϕ  θ θˆbic 2ε⊤ (ϕθ̂bic − ϕθ ) = 2ε⊤ |ϕθˆbic − ϕθ |2 |ϕθˆbic − ϕθ |2 2 h ⊤  ϕθ̂bic − ϕθ i2 α ≤ ε + |ϕθˆbic − ϕθ |22 , α |ϕθ̂bic − ϕθ |2 2 where we use Young’s inequality 2ab ≤ α2 a2 + α2 b2 valif for a, b ≥ 0, α > 0. Next, since α |ϕ ˆbic − ϕθ |22 ≤ α|ϕθ̂bic − f |22 + α|ϕθ − f |22 , 2 θ we get for α < 1, (1 − α)|ϕθˆbic − f |22 ≤ (1 + α)|ϕθ − f |22 + nτ 2 |θ|0 2 2 ⊤ + ε U (ϕθˆbic − ϕθ ) − nτ 2 |θˆbic |0 α ≤ (1 + α)|ϕθ − f |22 + 2nτ 2 |θ|0 2 2 ⊤ + ε U (ϕθ̂bic −θ ) − nτ 2 |θˆbic − θ|0 α We conclude as in the proof of Theorem 2.14. A similar oracle can be obtained in expectation (exercise). The interpretation of this theorem is enlightening. It implies that the BIC estimator will mimic the best tradeoff between the approximation error MSE(ϕθ ) and the complexity of θ as measured by its sparsity. In particular this result, sometimes called sparse oracle inequality implies the following oracle inequality. Define the oracle θ¯ to be such that MSE(ϕθ̄ ) = min MSE(ϕθ ) θ∈IRM then, with probability at least 1 − δ, MSE(ϕθˆbic ) ≤ io 1+α Cσ 2 h ¯ MSE(ϕθ¯) + |θ|0 log(eM ) + log(1/δ) 1−α α(1 − α)n If the linear model happens to be correct, then, simply, MSE(ϕθ̄ ) = 0. Sparse oracle inequality for the Lasso To prove an oracle inequality for the Lasso, we need incoherence on the design. Here the design matrix is given by the n × M matrix Φ with elements Φi,j = ϕj (Xi ). Theorem 3.5. Assume the general regression model (3.1) with ε ∼ subGn (σ 2 ). Moreover, assume that there exists an integer k such that the matrix Φ satisfies assumption INC(k) holds. Then, the Lasso estimator θˆL with regularization parameter given by r r 2 log(2M ) 2 log(1/δ) 2τ = 8σ + 8σ (3.6) n n satisfies for some numerical constant C, MSE(ϕθˆL ) ≤ inf θ ∈IRM |θ|0 ≤k n1 + α 1−α MSE(ϕθ ) + + o Cσ 2 |θ|0 log(eM ) α(1 − α)n Cσ 2 log(1/δ) α(1 − α)n with probability at least 1 − δ. Proof. From the definition of θˆL , it holds for any θ ∈ IRM , 1 1 |Y − ϕθˆL |22 ≤ |Y − ϕθ |22 + 2τ |θ|1 − 2τ |θˆL |1 . n n Adding τ |θˆL − θ|1 on each side and multiplying by n, we get |ϕθˆL −f |22 −|ϕθ −f |22 +nτ |θˆL −θ|1 ≤ 2ε⊤ (ϕθˆL −ϕθ )+nτ |θˆL −θ|1 +2nτ |θ|1 −2nτ |θˆL |1 . (3.7) √ Next, note that INC(k) for any k ≥ 1 implies that |ϕj |2 ≤ 2 n for all j = 1, . . . , M . Applying Hölder’s inequality using the same steps as in the proof of Theorem 2.15, we get that with probability 1 − δ, it holds 2ε⊤ (ϕθˆL − ϕθ ) ≤ nτ ˆL |θ − θ|1 2 Therefore, taking S = supp(θ) to be the support of θ, we get that the righthand side of (3.7) is bounded by ≤ 2nτ |θˆL − θ|1 + 2nτ |θ|1 − 2nτ |θˆL |1 = 2nτ |θ̂L − θ|1 + 2nτ |θ|1 − 2nτ |θˆL |1 S ≤ 4nτ |θ̂SL S − θ|1 (3.8) with probability 1 − δ. It implies that either MSE(ϕθ̂L ) ≤ MSE(ϕθ ) or that |θ̂SLc − θS c |1 ≤ 3|θˆSL − θS |1 . so that θ = θˆL − θ satisfies the cone condition (2.17). Using now the CauchySchwarz inequality and Lemma 2.17 respectively, assume that |θ|0 ≤ k, we get p p 4nτ |θ̂SL − θ|1 ≤ 4nτ |S||θ̂SL − θ|2 ≤ 4τ 2n|θ|0 |ϕθˆL − ϕθ |2 . Using now the inequality 2ab ≤ 2 2 αa + α2 b2 , we get 16τ 2 n|θ|0 α + |ϕθ̂L − ϕθ |22 α 2 16τ 2 n|θ|0 ≤ + α|ϕθ̂L − f |22 + α|ϕθ − f |22 α 4nτ |θˆSL − θ|1 ≤ Combining this result with (3.7) and (3.8), we find (1 − α)MSE(ϕθ̂L ) ≤ (1 + α)MSE(ϕθ ) + 16τ 2 |θ|0 . α To conclude the proof of the bound with high probability, it only remains to divide by 1−α on both sides of the above inequality. The bound in expectation follows using the same argument as in the proof of Corollary 2.9. Maurey’s argument From the above section, it seems that the Lasso estimator is strictly better than the BIC estimator as long as incoherence holds. Indeed, if there is no sparse θ such that MSE(ϕθ ) is small, Theorem 3.4 is useless. In reality, no one really believes in the existence of sparse vectors but rater of approximately sparse vectors. Zipf’s law would instead favor the existence of vectors θ with absolute coefficients that decay polynomially when ordered from largest to smallest in absolute value. This is the case for example if θ has a small ℓ1 norm but is not sparse. For such θ, the Lasso estimator still enjoys slow rates as in Theorem 2.15, which can be easily extended to the misspecified case (see Problem 3.2). Fortunately, such vectors can be well approximated by sparse vectors in the following sense: for any vector θ ∈ IRM such that |θ|1 ≤ 1, there exists a vector θ′ that is sparse and for which MSE(ϕθ′ ) is not much larger than MSE(ϕθ ). The following theorem quantifies exactly the tradeoff between sparsity and MSE. It is often attributed to B. Maurey and was published by Pisier [Pis81]. This is why it is referred to as Maurey’s argument. Theorem 3.6. Let {ϕ1 , . . . , ϕM } be a dictionary normalized in such a way that √ max |ϕj |2 ≤ D n . 1≤j≤M Then for any integer k such that 1 ≤ k ≤ M and any positive R, we have min MSE(ϕθ ) ≤ min MSE(ϕθ ) + θ ∈IRM |θ |0 ≤2k θ ∈IRM |θ|1 ≤R D 2 R2 . k Proof. Define θ̄ ∈ argmin |ϕθ − f |22 θ∈IRM |θ|1 ≤R and assume without loss of generality that |θ¯1 | ≥ |θ¯2 | ≥ . . . ≥ |θ¯M |. Now decompose θ¯ = θ(1) +θ(2) , where supp(θ(1) ) ⊂ {1 . . . , k} and supp(θ(2) ) ⊂ {k + 1, . . . , M }. In particular it holds ϕθ̄ = ϕθ(1) + ϕθ(2) . Moreover, observe that |θ(2) |1 = M X j=k+1 |θ¯j | ≤ R n Let now U ∈ IR be a random vector with values in {0, ±Rϕ1 , . . . , ±RϕM } defined by (2) |θ j | , j = k + 1, . . . , M R |θ(2) |1 IP(U = 0) = 1 − . R √ and |U |2 ≤ RD n. Let now U1 , . . . , Uk be k indepen(2) IP(U = Rsign(θj )ϕj ) = Note that IE[U ] = ϕθ(2) dent copies of U define k 1X Ū = Ui . k i=1 ˜ 0 ≤ k. Therefore, |θ(1) + θ| ˜0 ≤ ¯ = ϕ for some θ˜ ∈ IRM such that |θ| Note that U θ̃ 2k and ¯ |2 = IE|f − ϕθ(1) − ϕθ(2) + ϕθ(2) − U ¯ |2 IE|f − ϕθ(1) − U 2 2 ¯ |2 = IE|f − ϕθ(1) − ϕθ(2) |2 + |ϕθ(2) − U 2 2 IE|U − IE[U ]|22 = |f − ϕθ̄ |22 + √k 2 (RD n) ≤ |f − ϕθ̄ |22 + k To conclude the proof, note that ¯ |2 = IE|f − ϕ (1) ˜|2 ≥ min |f − ϕθ |2 IE|f − ϕθ(1) − U 2 2 θ +θ 2 θ∈IRM |θ|0 ≤2k and to divide by n. Maurey’s argument implies the following corollary. Corollary 3.7. Assume that the assumptions of Theorem 3.4 hold and that the dictionary {ϕ1 , . . . , ϕM } is normalized in such a way that √ max |ϕj |2 ≤ n . 1≤j≤M Then there exists a constant C > 0 such that the BIC estimator satisfies r n h σ 2 |θ| log(eM ) log(eM ) io 0 MSE(ϕθˆbic ) ≤ inf 2MSE(ϕθ ) + C ∧ σ |θ | 1 n n θ∈IRM σ 2 log(1/δ) +C n with probability at least 1 − δ. Proof. Choosing α = 1/3 in Theorem 3.4 yields n σ 2 log(1/δ) σ 2 |θ|0 log(eM ) o MSE(ϕθ ) + C +C n n θ∈IRM MSE(ϕθˆbic ) ≤ 2 inf For any θ′ ∈ IRM , it follows from Maurey’s argument that there exist θ ∈ IRM such that |θ|0 ≤ 2|θ′ |0 and MSE(ϕθ ) ≤ MSE(ϕθ′ ) + 2|θ′ |21 |θ|0 It implies that MSE(ϕθ ) + C σ 2 |θ|0 log(eM ) 2|θ′ |21 σ 2 |θ|0 log(eM ) ≤ MSE(ϕθ′ ) + +C n |θ|0 n Taking infimum on both sides, we get n σ 2 |θ|0 log(eM ) o MSE(ϕθ ) + C n θ∈IRM n  | θ ′ |2 σ 2 k log(eM ) o 1 ≤ inf MSE(ϕθ′ ) + C min +C . k k n θ ′ ∈IRM inf To control the minimum over k, we need to consider three cases for the quantity r |θ′ |1 log M ¯ k= σ n 1. If 1 ≤ k̄ ≤ M , then we get  |θ′ |2 σ 2 k log(eM )  +C ≤ Cσ |θ′ |1 k n 1 min k 2. If k¯ ≤ 1, then |θ′ |21 ≤ C r log(eM ) n σ 2 log(eM ) , n which yields min k 3. If k¯ ≥ M , then  |θ′ |2 1 k +C σ 2 k log(eM )  σ 2 log(eM ) ≤C n n σ 2 M log(eM ) |θ′ |21 ≤C . n M Therefore, on the one hand, if M ≥ √ σ min k  |θ′ |2 |θ |1 log(eM)/n , we get σ 2 k log(eM )  |θ′ |21 +C ≤C ≤ Cσ |θ′ |1 k n M 1 r log(eM ) . n On the other hand, if M ≤ √ σ |θ|1 , log(eM)/n then for any Θ ∈ IRM , we have σ 2 |θ|0 log(eM ) σ 2 M log(eM ) ≤ ≤ Cσ|θ′ |1 n n r log(eM ) . n Note that this last result holds for any estimator that satisfies an oracle inequality with respect to the ℓ0 norm such as the result of Theorem 3.4. In particular, this estimator need not be the BIC estimator. An example is the Exponential Screening estimator of [RT11]. Maurey’s argument allows us to enjoy the best of both the ℓ0 and the ℓ1 world. The rate adapts to the sparsity of the problem and can be even generalized to ℓq -sparsity (see Problem 3.3). However, it is clear from the proof that this argument is limited to squared ℓ2 norms such as the one appearing in MSE and extension to other risk measures is non trivial. Some work has been done for non Hilbert spaces [Pis81, DDGS97] using more sophisticated arguments. 3.2 NONPARAMETRIC REGRESSION So far, the oracle inequalities that we have derived do not deal with the approximation error MSE(ϕθ ). We kept it arbitrary and simply hoped that it was small. Note also that in the case of linear models, we simply assumed that the approximation error was zero. As we will see in this section, this error can be quantified under natural smoothness conditions if the dictionary of functions H = {ϕ1 , . . . , ϕM } is chosen appropriately. In what follows, we assume for simplicity that d = 1 so that f : IR → IR and ϕj : IR → IR. Fourier decomposition Historically, nonparametric estimation was developed before high-dimensional statistics and most results hold for the case where the dictionary H = {ϕ1 , . . . , ϕM } forms an orthonormal system of L2 ([0, 1]): Z 0 1 ϕ2j (x)dx = 1 , Z 1 0 ϕj (x)ϕk (x)dx = 0, ∀ j = 6 k. We will also deal with the case where M = ∞. When H is an orthonormal system, the coefficients θj∗ ∈ IR defined by θj∗ = Z 0 are called Fourier coefficients of f . 1 f (x)ϕj (x)dx , Assume now that the regression function f admits the following decomposition ∞ X f= θj∗ ϕj . j=1 There exists many choices for the orthonormal system and we give only two as examples. Example 3.8. Trigonometric basis. This is an orthonormal basis of L2 ([0, 1]). It is defined by ϕ1 ϕ2k (x) ϕ2k+1 (x) ≡ 1 √ 2 cos(2πkx) , √ 2 sin(2πkx) , = = for k = 1, 2, . . . and x ∈ [0, 1]. The fact that it is indeed an orthonormal system can be easily check using trigonometric identities. The next example has received a lot of attention in the signal (sound, image, . . . ) processing community. Example 3.9. Wavelets. Let ψ : IR → IR be a sufficiently smooth and compactly supported function, called “mother wavelet ”. Define the system of functions ψjk (x) = 2j/2 ψ(2j x − k) , j, k ∈ Z . It can be shown that for a suitable ψ, the dictionary {ψj,k , j, k ∈ Z} forms an orthonormal system of L2 ([0, 1]) and sometimes a basis. In the latter case, for any function g ∈ L2 ([0, 1]), it holds g= ∞ X ∞ X θjk ψjk , j=−∞ k=−∞ θjk = Z 1 g(x)ψjk (x)dx . 0 The coefficients θjk are called wavelet coefficients of g. The simplest example is given by the Haar system obtained by taking ψ to be the following piecewise constant function (see Figure 3.1). We will not give more details about wavelets here but refer simply point the interested reader to [Mal09].  0 ≤ x < 1/2  1 −1 1/2 ≤ x ≤ 1 ψ(x) =  0 otherwise Sobolev classes and ellipsoids We begin by describing a class of smooth functions where smoothness is understood in terms of its number of derivatives. Recall that f (k) denotes the k-th derivative of f . 1 0 ψ(x) −1 0.0 0.5 1.0 x Figure 3.1. The Haar mother wavelet Definition 3.10. Fix parameters β ∈ {1, 2, . . . } and L > 0. The Sobolev class of functions W (β, L) is defined by n W (β, L) = f : [0, 1] → IR : f ∈ L2 ([0, 1]) , f (β −1) is absolutely continuous and Z 1 o [f (β) ]2 ≤ L2 , f (j) (0) = f (j) (1), j = 0, . . . , β − 1 0 Any function f ∈ W (β, L) can represented1 as its Fourier expansion along the trigonometric basis: f (x) = θ1∗ ϕ1 (x) + ∞ X k=1
θ2∗k ϕ2k (x) + θ2∗k+1 ϕ2k+1 (x) , ∀ x ∈ [0, 1] , where θ∗ = {θj∗ }j ≥1 is in the space of squared summable sequence ℓ2 (IN) defined by ∞ n o X ℓ2 (IN) = θ : θj2 < ∞ . j=1 For any β > 0, define the coefficients  jβ aj = (j − 1)β for j even for j odd (3.9) Thanks to these coefficients, we can define the Sobolev class of functions in terms of Fourier coefficients. 1 In the sense that lim k→∞ Z 0 1 |f (t) − k X j=1 θj ϕj (t)|2 dt = 0 Theorem 3.11. Fix β ≥ 1 and L > 0 and let {ϕj }j ≥1 denote the trigonometric basis of L2 ([0, 1]). Moreover, let {aj }j ≥1 be defined as in (3.9). A function f ∈ W (β, L) can be represented as f= ∞ X θj∗ ϕj , j=1 where the sequence {θj∗ }j ≥1 belongs to Sobolev ellipsoid of ℓ2 (IN) defined by ∞ n o X Θ(β, Q) = θ ∈ ℓ2 (IN) : a2j θj2 ≤ Q j=1 for Q = L2 /π 2β . Proof. Let us first recall the definition of the Fourier coefficients {sk (j)}k≥1 of the jth derivative f (j) of f for j = 1, . . . , β: Z 1 s1 (j) = f (j) (t)dt = f (j−1) (1) − f (j−1) (0) = 0 , 0 √ Z s2k (j) = 2 1 f (j) (t) cos(2πkt)dt , 0 √ Z s2k+1 (j) = 2 1 f (j) (t) sin(2πkt)dt , 0 The Fourier coefficients of f are given by θk = sk (0). Using integration by parts, we find that 1 √ Z 1 (β−1) √ (β −1) f (t) sin(2πkt)dt s2k (β) = 2f (t) cos(2πkt) + (2πk) 2 0 0 √ √ Z = 2[f (β−1) (1) − f (β−1) (0)] + (2πk) 2 1 f (β−1) (t) sin(2πkt)dt 0 = (2πk)s2k+1 (β − 1) . Moreover, s2k+1 (β) = √ (β−1) 2f (t) sin(2πkt) = −(2πk)s2k (β − 1) . 1 0 √ Z − (2πk) 2 1 f (β−1) (t) cos(2πkt)dt 0 In particular, it yields   s2k (β)2 + s2k+1 (β)2 = (2πk)2 s2k (β − 1)2 + s2k+1 (β − 1)2 By induction, we find that for any k ≥ 1, 2 2 s2k (β)2 + s2k+1 (β)2 = (2πk)2β θ2k + θ2k+1
Next, it follows for the definition (3.9) of aj that ∞ X 2β (2πk) 2 θ2k + 2 θ2k+1 k=1
=π 2β ∞ X 2 a22k θ2k +π 2β k=1 = π 2β ∞ X ∞ X 2 a22k+1 θ2k+1 k=1 a2j θj2 . j=1 Together with the Parseval identity, it yields Z 0 1 ∞ ∞ X X
2 f (β) (t) dt = s2k (β)2 + s2k+1 (β)2 = π 2β aj2 θj2 . j=1 k=1 To conclude, observe that since f ∈ W (β, L), we have Z 1 0 so that θ ∈ Θ(β, L2 /π 2β ) .
2 f (β) (t) dt ≤ L2 , It can actually be shown that the reciprocal is true, that is any function with Fourier coefficients in Θ(β, Q) belongs to if W (β, L) but we will not be needing this. In what follows, we will define smooth functions as functions with Fourier coefficients (with respect to the trigonometric basis) in a Sobolev ellipsoid. By extension, we write f ∈ Θ(β, Q) in this case and consider any real value for β. Proposition 3.12. The Sobolev ellipsoids enjoy the following properties (i) For any Q > 0, 0 < β ′ < β ⇒ Θ(β, Q) ⊂ Θ(β ′ , Q) (ii) For any Q > 0, β> 1 ⇒ f is continuous 2 The proof is left as an exercise (Problem 3.5) It turns out that the first functions in the trigonometric basis are orthonormal with respect to the inner product of L2 but also to the inner predictor associated to fixed design hf, gi := n1 f (Xi )g(Xi ) when the design is chosen to be regular, i.e., Xi = (i − 1)/n, i = 1, . . . , n. Lemma 3.13. Assume that {X1 , . . . , Xn } is the regular design, i.e., Xi = (i − 1)/n. Then, for any M ≤ n − 1, the design matrix Φ = {ϕj (Xi )} 1≤i≤n satisfies the ORT condition. 1≤j≤M Proof. Note first that for any j, j ′ ∈ {1, . . . , n − 1}, j 6= j ′ the inner product ϕ⊤ j ϕj ′ is of the form ϕ⊤ j ϕj ′ = 2 n−1 X uj (2πkj s/n)vj ′ (2πkj ′ s/n) s=0 where kj = ⌊j/2⌋ is the integer part of j/2 for any x ∈ IR, uj (x), vj ′ (x) ∈ {Re(eix ), Im(eix )}. Next, observe that if kj 6= kj ′ , we have n −1 X e i2πkj s n e− i2πk ′ s j n = s=0 n −1 X e i2π(kj −k ′ )s j n = 0. s=0 Moreover, if we define the vectors a, b, a′ , b′ ∈ IRn with coordinates such that e i2πkj s n = as + ibs and e n −1 X e i2πkj s n e− i2πk ′ s j n = a′s + ib′s , we get   = (a + ib)⊤ (a′ − ib′ ) = a⊤ a′ + b⊤ b′ + i b⊤ a′ − a⊤ b′ i2πk ′ s j n s=0 and consequently that   1 ⊤ ϕ ϕj ′ = a⊤ a′ + b⊤ b′ + i b⊤ a′ − a⊤ b′ 2 j with |a|2 |b|2 = |a′ |2 |b′ |2 = 0, i.e., either a = 0 or b = 0 and either a′ = 0 or b′ = 0. Therefore, in the case where kj 6= kj ′ , we have a⊤ a′ = −b⊤ b′ = 0, which implies case where kj the first case, sin(·) and the b ⊤ a′ = a⊤ b ′ = 0 ϕ⊤ j ϕj ′ = 0. To conclude the proof, it remains to deal with the = kj ′ . This can happen in two cases: |j ′ − j| = 1 or j ′ = j. In we have that {uj (x), vj ′ (x)} = {Re(eix ), Im(eix )}, i.e., one is a other is a cos(·). Therefore,   1 ⊤ ϕj ϕj ′ = a⊤ a′ + b⊤ b′ + i b⊤ a′ − a⊤ b′ = 0 2 The final case is j = j ′ for which, on the one hand, n −1 X e i2πkj s n e i2πkj s n s=0 = n −1 X e i4π kj s n =0 s=0 and on the other hand n −1 X s=0 e i2πkj s n e i2πkj s n = |a + ib|22 = |a|22 − |b|22 so that |a|2 = |b|2 . Moreover, by definition,  2|a|22 if j is even 2 |ϕj |2 = 2|b|22 if j is odd so that |ϕj |22 = 2 n −1 X i2πkj s |a|22 + |b|22 = e n 2 s=0 2 =n Therefore, the design matrix Φ is such that Φ⊤ Φ = nIM . Integrated squared error As mentioned in the introduction of this chapter, the smoothness assumption allows us to control the approximation error. Before going into the details, let us gain some insight. Note first that if θ ∈ Θ(β, Q), then a2j θj2 → 0 as j → ∞ so that |θj | = o(j −β ). Therefore, the θj s decay polynomially to zero and it makes sense to approximate f by its truncated Fourier series M X θj∗ ϕj =: ϕM θ∗ j=1 for any fixed M . This truncation leads to a systematic error that vanishes as M → ∞. We are interested in understanding the rate at which this happens. The Sobolev assumption to control precisely this error as a function of the tunable parameter M and the smoothness β. Lemma 3.14. For any integer M ≥ 1, and f ∈ Θ(β, Q), β > 1/2, it holds X 2 kϕM |θj∗ |2 ≤ QM −2β . (3.10) θ ∗ − f kL2 = j >M and for M = n − 1, we have 2 |ϕn−1 θ ∗ − f |2 ≤ 2n X j ≥n |θj∗ | 2 . Qn2−2β . Proof. Note that for any θ ∈ Θ(β, Q), if β > 1/2, then ∞ X j=2 |θj | = ∞ X j=2 a j |θ j | 1 aj v uX ∞ u ∞ 2 2X 1 ≤t a j θj by Cauchy-Schwarz 2 a j=2 j=2 j v u X u ∞ 1 ≤ tQ <∞ j 2β j=1 (3.11) Since {ϕj }j forms an orthonormal system in L2 ([0, 1]), we have X 2 min kϕθ − f k2L2 = kϕθ∗ − f kL = |θj∗ |2 . 2 θ∈IRM j>M When θ∗ ∈ Θ(β, Q), we have X j>M |θj∗ |2 = X j>M a2j |θj∗ |2 1 1 Q ≤ 2 Q ≤ 2β . 2 aM+1 M aj To prove the second part of the lemma, observe that X √ X ∗ ∗ |ϕn−1 − f | = θ ϕ ≤ 2 2n |θ j | , ∗ 2 j j θ 2 j ≥n j ≥n where in√the last inequality, we used the fact that for the trigonometric basis |ϕj |2 ≤ 2n, j ≥ 1 regardless of the choice of the design X1 , . . . , Xn . When θ∗ ∈ Θ(β, Q), we have s sX X X 1 X 1 ∗ ∗ 1 2 ∗ 2 |θj | = aj |θj | ≤ a j |θ j | . Qn 2 −β . 2 aj aj j ≥n j ≥n j ≥n j ≥n Note the truncated Fourier series ϕθ∗ is an oracle: this is what we see when we view f through the lens of functions with only low frequency harmonics. To estimate ϕθ∗ , consider the estimator ϕθˆls where θ̂ls ∈ argmin n X θ∈IRM i=1
2 Yi − ϕθ (Xi ) . Which should be such that ϕθˆls is close to ϕθ∗ . For this estimator, we have proved (Theorem 3.3) an oracle inequality for the MSE that is of the form 2 M 2 |ϕθM ˆls − f |2 ≤ inf |ϕθ − f |2 + Cσ M log(1/δ) , θ∈IRM C > 0. It yields 2 M M ⊤ M 2 |ϕM − ϕM θ ∗ |2 ≤ 2(ϕθˆls − ϕθ ∗ ) (f − ϕθ ∗ ) + Cσ M log(1/δ) θˆls X ⊤ = 2(ϕM − ϕM θj∗ ϕj ) + Cσ 2 M log(1/δ) θ∗ ) ( θˆls j>M = 2(ϕM θ̂ ls − X ⊤ ϕM θj∗ ϕj ) θ∗ ) ( j≥n + Cσ 2 M log(1/δ) , where we used Lemma 3.13 in the last equality. Together with (3.11) and Young’s inequality 2ab ≤ αa2 + b2 /α, a, b ≥ 0 for any α > 0, we get ⊤ 2(ϕM − ϕM θ∗ ) ( θˆls X j ≥n 2 θj∗ ϕj ) ≤ α|ϕM − ϕM θ ∗ |2 + θˆls C Qn2−2β , α for some positive constant C when θ∗ ∈ Θ(β, Q). As a result, 2 |ϕθ̂Mls − ϕM θ ∗ |2 . 1 σ2 M Qn2−2β + log(1/δ) α(1 − α) 1−α (3.12) M 2 M for any t ∈ (0, 1). Since, Lemma 3.13 implies, |ϕθM ˆls − ϕθ ∗ |2 = nkϕθˆls − 2 ϕM θ ∗ kL2 ([0,1]) , we have proved the following theorem. √ Theorem 3.15. Fix β ≥ (1 + 5)/4 ≃ 0.81, Q > 0, δ > 0 and assume the general regression model (3.1) with f ∈ Θ(β, Q) and ε ∼ subGn (σ 2 ), σ 2 ≤ 1. 1 Moreover, let M = ⌈n 2β+1 ⌉ and n be large enough so that M ≤ n − 1. Then the least squares estimator θˆls defined in (3.2) with {ϕj }M j=1 being the trigonometric basis, satisfies with probability 1 − δ, for n large enough, 2β kϕθˆls − f k2L2 ([0,1]) . n− 2β+1 + σ 2 log(1/δ) . n where the constant factors may depend on β, Q and σ. Moreover 2β IEkϕθ̂ls − f k2L2 ([0,1]) . n− 2β+1 . Proof. Choosing α = 1/2 for example and absorbing Q in the constants, we get from (3.12) and Lemma 3.13 that for M ≤ n − 1, 2 kϕθˆls − ϕθ∗ kL . n1−2β + σ 2 2 ([0,1]) M + log(1/δ) . n Using now Lemma 3.14 and σ 2 ≤ 1, we get kϕθˆls − f k2L2 ([0,1]) . M −2β + n1−2β + M + σ 2 log(1/δ) . n 1 Taking M = ⌈n 2β+1 ⌉ ≤ n − 1 for n large enough yields 2β kϕθ̂ls − f k2L2 ([0,1]) . n− 2β+1 + n1−2β + σ 2 log(1/δ) . n To conclude the proof, simply note that for the prescribed β, we have n1−2β ≤ 2β n− 2β+1 . The bound in expectation can be obtained by integrating the tail bound. Adaptive estimation 1 The rate attained by the projection estimator ϕθˆls with M = ⌈n 2β+1 ⌉ is actually optimal so, in this sense, it is a good estimator. Unfortunately, its implementation requires the knowledge of the smoothness parameter β which is typically unknown, to determine the level M of truncation. The purpose of adaptive estimation is precisely to adapt to the unknown β, that is to build an estimator 2β that does not depend on β and yet, attains a rate of the order of Cn− 2β+1 (up to a logarithmic lowdown). To that end, we will use the oracle inequalities for the BIC and Lasso estimator defined in (3.3) and (3.4) respectively. In view of Lemma 3.13, the design matrix Φ actually satisfies the assumption ORT when we work with the trigonometric basis. This has two useful implications: 1. Both estimators are actually thresholding estimators and can therefore be implemented efficiently 2. The condition INC(k) is automatically satisfied for any k ≥ 1. These observations lead to the following corollary. √ Corollary 3.16. Fix β ≥ (1 + 5)/4 ≃ 0.81, Q > 0, δ > 0 and n large enough 1 to ensure n − 1 ≥ ⌈n 2β+1 ⌉ assume the general regression model (3.1) with −1 f ∈ Θ(β, Q) and ε ∼ subGn (σ 2 ), σ 2 ≤ 1. Let {ϕj }nj =1 be the trigonometric n−1 n−1 basis. Denote by ϕθˆbic (resp. ϕθˆL ) the BIC (resp. Lasso) estimator defined in (3.3) (resp. (3.4)) over IRn−1 with regularization parameter given by (3.5) (resp. (3.6)). Then ϕn−1 , where θˆ ∈ {θˆbic , θˆL } satisfies with probability 1 − δ, θˆ 2β kϕn−1 − f k2L2 ([0,1]) . n− 2β+1 + σ 2 θˆ Moreover, 2 IEkϕn−1 − f kL . σ2 2 ([0,1]) θˆ log(1/δ) . n 2β  log n  2β+1 n . where constant factors may depend on β and Q. Proof. For θˆ ∈ {θˆbic , θˆL }, adapting the proofs of Theorem 3.4 for the BIC estimator and Theorem 3.5 for the Lasso estimator, for any θ ∈ IRn−1 , with probability 1 − δ |ϕθnˆ−1 − f |22 ≤ where R(|θ|0 ) := It yields 1 + α n−1 |ϕ − f |22 + R(|θ|0 ) . 1−α θ Cσ 2 Cσ 2 |θ0 | log(en) + log(1/δ) α(1 − α) α(1 − α) 2α |ϕn−1 − f |22 + 2(ϕn−1 − ϕn−1 )⊤ (ϕθn−1 − f ) + R(|θ|0 ) θ θˆ 1−α θ  2α 1  n−1 ≤ + |ϕθ − f |22 + α|ϕθn−1 − ϕθn−1 |22 + R(|θ|0 ) , ˆ 1−α α |ϕn−1 − ϕn−1 |22 ≤ θ θˆ ∗ where we used Young’s inequality once again. Choose now α = 1/2 and θ = θM , ∗ ∗ where θM is equal to θ on its first M coordinates and 0 otherwise so that ϕn−1 = ϕM θ ∗ . It yields θ∗ M |ϕn−1 θˆ n−1 n−1 n−1 2 n−1 2 2 2 − ϕn−1 θ ∗ |2 . |ϕθ ∗ − f |2 + R(M ) . |ϕθ ∗ − ϕθ ∗ |2 + |ϕθ ∗ − f |2 + R(M ) M M M Next, it follows from (3.11) that |ϕn−1 − f |22 . Qn2−2β . θ∗ Lemma 3.13, it yields Together with n−1 n−1 2 2 1−2β kϕn−1 − ϕn−1 + θ ∗ kL2 ([0,1]) . kϕθ ∗ − ϕθ ∗ kL2 ([0,1]) + Qn θˆ M M R(M ) . n Moreover, using (3.10), we find that kϕnθˆ−1 − f k2L2 ([0,1]) . M −2β + Qn1−2β + M σ2 log(en) + log(1/δ) . n n 1 To conclude the proof, choose M = ⌈(n/ log n) 2β+1 ⌉ and observe that the choice of β ensures that n1−2β . M −2β . This yields the high probability bound. The bound in expectation is obtained by integrating the tail. While there is sometimes a (logarithmic) price to pay for adaptation, it turns out that the extra logarithmic factor can be removed by a clever use of blocks (see [Tsy09, Chapter 3]). The reason why we get this extra logarithmic factor here is because we use a hammer that’s too big. Indeed, BIC and Lasso allow for “holes” in the Fourier decomposition and we use a much weaker version of their potential.