18.657 Mathematics of Machine Learning, Lecture 7 Notes

18.657: Mathematics of Machine Learning Lecturer: Philippe Rigollet Scribe: Zach Izzo Lecture 7 Sep. 30, 2015 In this lecture, we continue our discussion of covering numbers and compute upper ˆ x (F). We then discuss chaining and bounds for specific conditional Rademacher averages R n conclude by applying it to learning. Recall the following definitions. We define the risk function (X, Y ) ∈ X × [−1, 1] , R(f ) = IE[`(X, f (X))], for some loss function `(·, ·). The conditiona Rademacher average that we need to control is " # n 1X R(`l ◦ F) = sup IE sup σi `(yi , f (xi )) . f ∈F n (x1 ,y1 ),...,(xn ,yn ) i=1 Furthermore, we defined the conditional Rademacher average for a point x = (x1 , . . . , xn ) to be " # n 1X x R̂n (F) = IE sup σi f (xi ) . f ∈F n i=1 Lastly, we define the ε-covering number N (F, d, ε) to be the minimum number of balls (with respect to the metric d) of radius ε needed to cover F. We proved the following theorem: Theorem: Assume |f | ≤ 1 for all f ∈ F. Then ( ) r x , ε)) 2 log(2N ( , d F 1 R̂xn (F) ≤ inf ε + , ε>0 n where dx1 is given by n dx1 (f, g) 1X = |f (xi ) − g(xi )|. n i=1 We make use of this theorem in the following example. Define Bpd = {x ∈ IRd : |x|p ≤ 1}. d }, and X = B d . By Hölder’s inequality, Then take f (x) = ha, xi, set F = {ha, ·i : a ∈ B∞ 1 we have |f (x)| ≤ |a|∞ |x|1 ≤ 1, so the theorem above holds. We need to compute the covering number N (F, dx1 , ε). Note d , there exists v = (v , . . . , v ) such that v = g(x ) and that for all a ∈ B∞ 1 n i i n 1X |ha, xi i − vi | ≤ ε n i=1 for some function g. For this case, we will take g(x) = hb, xi, so vi = hb, xi i. Now, note the following. Given this definition of g, we have d1x (f, g) = n n i=1 i=1 1X 1X |ha, x1 i − hb, xi i| = |ha − b, xi i| ≤ |a − b|∞ n n 1 by Hölder’s inequality and the fact that |x|1 = 1. So if |a − b|∞ ≤ ε, we can take vi = hb, xi i. We just need to find a set of {b1 , . . . , bM } ⊂ IRd such that, for any a there exists bj such d into cubes with side length ε and that |a − bj |∞ < ∞. We can do this by dividing B∞ d must land in one taking the bj ’s to be the set of vertices of these cubes. Then any a ∈ B∞ of these cubes, so |a − bj |∞ ≤ ε as desired. There are c/εd of such bj ’s for some constant c > 0. Thus d N (B∞ , dx1 , ε) ≤ c/εd . We now plug this value into the theorem to obtain ( ) r d) 2 log(c/ε R̂nx (F) ≤ inf ε + . ε≥0 n Optimizing over all choices of ε gives r d log(n) ∗ ε =c n r R̂xn (F) ⇒ ≤c d log(n) . n Note that in this final inequality, the conditional empirical risk no longer depends on x, since we “sup’d” x out of the bound during our computations. In general, one should ignore x unless it has properties which will guarantee a bound which is better than the sup. Another important thing to note is that we are only considering one granularity of F in our final result, namely the one associated to ε∗ . It is for this reason that we pick up an extra log factor in our risk bound. In order to remove this term, we will need to use a technique called chaining. 5.4 Chaining We have the following theorem. Theorem: Assume that |f | ≤ 1 for all f ∈ F. Then   Z q 12 1 x x R̂n ≤ inf 4ε + √ log(N (F , d2 , t))dt . ε>0 n ε (Note that the integrand decays with t.) Proof. Fix x = (x1 , . . . , xn ), and for all j = 1, . . . , N , let Vj be a minimal 2−j -net of F under the dx2 metric. (The number N will be determined later.) For a fixed f ∈ F, this process will give us a “chain” of points fi◦ which converges to f : dx2 (fi◦ , f ) ≤ 2−j . Define F = {(f (x1 ), . . . , f (xn ))> , f ∈ F} ⊂ [−1, 1]n . Note that R̂xn (F) = 1 IE sup hσ, f i n f ∈F where σ = (σ1 , . . . , σn ). Observe that for all N , we can rewrite hσ, f i as a telescoping sum: ◦ ◦ ◦ ◦ ◦ hσ, f i = hσ, f − fN i + hσ, fN − fN −1 i + . . . + hσ, f1 − f0 i 2 where f0◦ := 0. Thus N R̂xn (F) ≤ X1 1 ◦ IE sup |hσ, f − fN i| + IE sup |hσ, fj◦ − fj◦−1 i| . n f ∈F n f ∈F j=1 We can control the two terms in this inequality separately. Note first that by the CauchySchwarz inequality, dx (f, f ◦ ) 1 ◦ IE sup |hσ, f − fN i| ≤ |σ|2 2 √ N . n f ∈F n √ ◦ ) ≤ 2−N , we have Since |σ|2 = n and dx2 (f, fN 1 ◦ i| ≤ 2−N . IE sup |hσ, f − fN n f ∈F Now we turn our attention to the second term in the inequality, that is N X 1 S= IE sup |hσ, fj◦ − fj◦−1 i|. n f ∈F j=1 Note that since fj◦ ∈ Vj and fj◦−1 ∈ Vj −1 , there are at most |Vj ||Vj−1 | possible differences fj◦ − fj◦−1 . Since |Vj −1 | ≤ |Vj |/2, |Vj ||Vj −1 | ≤ |Vj |2 /2 and we find ourselves in the finite dictionary case. We employ a risk bound from earlier in the course to obtain the inequality p 2 log(2|B|) Rn (B) ≤ max |b|2 . b∈B n In the present case, B = {fj◦ − fj◦−1 , f ∈ F } so that |B| ≤ |Vj |2 /2. It yields q p 2|V |2 2 log( 2j ) log |Vj | = 2r · , Rn (B) ≤ r · n n where r = supf ∈F |fj◦ − fj◦−1 |2 . Next, observe that √ √ √ |fj◦ − fj◦−1 |2 = n · dx2 (fj◦ , fj◦−1 ) ≤ n(dx2 (fj◦ , f ) + dx2 (f, fj◦−1 )) ≤ 3 · 2−j n . by the triangle inequality and the fact that dx2 (fj◦ , f ) ≤ 2−j . Substituting this back into our bound for Rn (B), we have r r log |Vj || log(N (F , dx2 , 2−j )) −j −j Rn (B) ≤ 6 · 2 =6·2 n n since Vj was chosen to be a minimal 2−j -net. The proof is almost complete. Note that 2−j = 2(2−j − 2−j−1 ) so that N 6 X −j √ 2 n q j=1 N q 12 X −j log(N (F, dx2 , 2−j )) = √ (2 − 2−j−1 ) log(N (F, dx2 , 2−j )) . n j=1 Next, by comparing sums and integrals (Figure 1), we see that N X −j (2 −j−1 −2 ) q log(N (F, dx2 , 2−j )) j=1 3 Z 1/2 ≤ 2−(N +1) q log(N (F , dx2 , t))dt. Figure 1: A comparison of the sum and integral in question. So we choose N such that 2−(N +2) ≤ ε ≤ 2−(N +1) , and by combining our bounds we obtain R̂xn (F ) ≤2 −N 12 +√ n Z 1/2 q 2−(N +1) log(N (F, dx2 , t))dt Z ≤ 4ε + 1p log(N, F, t)dt ε since the integrand is non-negative. (Note: this integral is known as the “Dudley Entropy Integral.”) Returning to our earlier example, since N (F, dx2 , ε) ≤ c/εd , we have   Z q 12 1 x 0 d R̂n (F) ≤ inf 4ε + √ log((c /t) )dt . ε>0 n ε R1p Since 0 log(c/t)dt = c̄ is finite, we then have p R̂xn (F) ≤ 12c̄ d/n. Using chaining, we’ve been able to remove the log factor! 5.5 Back to Learning We want to bound " n 1X Rn (` ◦ F) = sup IE sup σi `(yi , f (xi )) f ∈F n (x1 ,y1 ),...,(xn ,yn ) # . i=1 Pn  We consider R̂nx (Φ ◦ F ) = IE supf ∈F n1 i=1 σi Φ ◦ f (xi ) for some L-Lipschitz function Φ, that is |Φ(a) − Φ(b)| ≤ L|a − b| for all a, b ∈ [−1, 1]. We have the following lemma.  4 Theorem: (Contraction Inequality) Let Φ be L-Lipschitz and such that Φ(0) = 0, then R̂xn (Φ ◦ F) ≤ 2L · R̂xn (F) . The proof is omitted and the interested reader should take a look at [LT91, Kol11] for example. As a final remark, note that requiring the loss function to be Lipschitz prohibits the use of R-valued loss functions, for example `(Y, ·) = (Y − ·)2 . References [Kol11] Vladimir Koltchinskii. Oracle inequalities in empirical risk minimization and sparse ´ ´ de Probabilités de Saint-Flour XXXVIII-2008. Lecrecovery problems. Ecole d’Eté ture Notes in Mathematics 2033. Berlin: Springer. ix, 254 p. EUR 48.10 , 2011. [LT91] Michel Ledoux and Michel Talagrand. Probability in Banach spaces, volume 23 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 1991. Isoperimetry and processes. 5