Understanding Machine Learning: From Theory to Algorithms

26.1 The Rademacher Complexity 381 and therefore mR(A′)≤log ( ∑ a∈A′ ∏m i=1 exp ( a^2 i 2 )) = log ( ∑ a∈A′ exp ( ‖a‖^2 / 2 ) ) ...

382 Rademacher Complexities be omitted since bothaanda′are from the same setAand the rest of the expression in the supremum is n ...

26.3 Generalization Bounds for SVM 383 Finally, since the variablesσ 1 ,...,σmare independent we have Eσ [ ‖ ∑m i=1 σixi‖^22 ] = ...

384 Rademacher Complexities We shall consider the following general constraint-based formulation. LetH= {w:‖w‖ 2 ≤B}be our hypot ...

26.3 Generalization Bounds for SVM 385 Proof Throughout the proof, let the loss function be the ramp loss (see Sec- tion 15.2.3) ...

386 Rademacher Complexities Remark 26.2 Note that all the bounds we have derived do not depend on the dimension ofw. This proper ...

26.5 Bibliographic Remarks 387 Our proof of the concentration lemma is due to Kakade and Tewari lecture notes. Kakade, Sridharan ...

27 Covering Numbers In this chapter we describe another way to measure the complexity of sets, which is called covering numbers. ...

27.2 From Covering to Rademacher Complexity via Chaining 389 Next, we derive a contraction principle. lemma27.3 For eachi ∈[m], ...

390 Covering Numbers We can now write R(A) = 1 mE〈σ,a ∗〉 = 1 mE [ 〈σ,a∗−b(M)〉+ ∑M k=1 〈σ,b(k)−b(k−1)〉 ] ≤ 1 m E [ ‖σ‖‖a∗−b(M)‖ ] ...

27.3 Bibliographic Remarks 391 27.3 Bibliographic Remarks The chaining technique is due to Dudley (1987). For an extensive study ...

28 Proof of the Fundamental Theorem of Learning Theory In this chapter we prove Theorem 6.8 from Chapter 6. We remind the reader ...

28.2 The Lower Bound for the Agnostic Case 393 Combining this with Lemma 26.8 we obtain the following bound on the Rademacher co ...

394 Proof of the Fundamental Theorem of Learning Theory that there areh+,h−∈ Hfor whichh+(c) = 1 andh−(c) =−1. Define two distri ...

28.2 The Lower Bound for the Agnostic Case 395 Therefore, max b∈{± 1 } P[LDb(A(y))−LDb(hb) =] = max b∈{± 1 } ∑ y Pb[y] (^1) [A( ...

396 Proof of the Fundamental Theorem of Learning Theory h∈ Hsuch thath(ci) =bifor alli∈[d], and its error is^1 − 2 ρ. In additio ...

28.2 The Lower Bound for the Agnostic Case 397 y∈ {± 1 }m, letyIdenote the elements ofycorresponding to indices for which jr=ian ...

398 Proof of the Fundamental Theorem of Learning Theory As long asm < 8 dρ 2 , this term would be larger thanρ/4. In summary, ...

28.3 The Upper Bound for the Realizable Case 399 Claim 1 P[S∈B]≤ 2 P[(S,T)∈B′]. Proof of Claim 1: SinceSandTare chosen independe ...

400 Proof of the Fundamental Theorem of Learning Theory EA∼D 2 m[f(A,Aj)]. Since this holds for anyjit also holds for the expect ...