Lecture 34: Optimistic VC Inequality for Random Classes of Sets

Lecture 34 Optimistic VC inequality for random classes of sets. 18.465 √ As in the previous lecture, let F = {(w, φ(x))H, �w� ≤ 1}, where φ(x) = ( λi φi (x))i≥1 , X ⊂ Rd . Define d(f, g) = �f − g�∞ = supx∈X |f (x) − g(x)|. The following theorem appears in Cucker & Smale: Theorem 34.1. ∀h ≥ d, log N (F , ε, d) ≤ where Ch is a constant.  Ch ε  2hd Note that for any x1 , . . . , xn , n 1X (f (xi ) − g(xi))2 n i=1 dx (f, g) = Hence, !1/2 ≤ d(f, g) = sup |f (x) − g(x)| ≤ ε. x N (F , ε, dx) ≤ N (F , ε, d). Assume the loss function L(y, f (x)) = (y − f (x))2 . The loss classis defined as L(y, F ) = {(y − f (x))2 , f ∈ F }. Suppose |y − f (x)| ≤ M. Then |(y − f (x))2 − (y − g(x))2 | ≤ 2M |f (x) − g(x)| ≤ ε. So,   ε , dx N (L(y, F ), ε, dx) ≤ N F , 2M and log N (L(y, F ), ε, dx) ≤ α= 2d h < 2 (see Homework 2, problem 4).  2MCh ε  2hd =  2MCh ε α Now, we would like to use specific form of solution for SVM: f (x) = Pn i=1 αi K(xi , x), i.e. f belongs to a random subclass. We now prove a VC inequality for random collection of sets. Let’s consider C(x1 , . . . , xn ) = {C : C ⊆ X } - random collection of sets. Assume that C(x1 , . . . , xn ) satisfies: (1) C(x1 , . . . , xn ) ⊆ C(x1 , . . . , xn , xn+1 ) Optimistic VC inequality for random classes of sets. Lecture 34 18.465 (2) C(π(x1 , . . . , xn )) = C(x1 , . . . , xn ) for any permutation π. Let △C (x1 , . . . , xn ) = card {C ∩ {x1 , . . . , xn }; C ∈ C} and G(n) = E△C(x1 ,...,xn ) (x1 , . . . , xn ). Theorem 34.2. P (C) − sup P C∈C(x1 ,...,xn ) Proof. ! Pn I(x ∈ C) nt2 i p i=1 ≥ t ≤ 4G(2n)e− 4 P (C) 1 n Consider event Ax = ( x = (x1 , . . . , xn ) : P (C) − sup C∈C(x1 ,...,xn ) ) Pn I(x ∈ C) i p i=1 ≥t P (C) 1 n So, there exists Cx ∈ C(x1 , . . . , xn ) such that Pn I(xi ∈ Cx ) P (Cx ) − n1 i=1 p ≥ t. P (Cx ) For x′1 , . . . , xn′ , an independent copy of x, n Px ′ if P (Cx ) ≥ 1 n 1X P (Cx ) ≤ I(x′i ∈ Cx ) n i=1 ! ≥ 1 4 (which we can assume without loss of generality). Together, n 1X I(x′i ∈ Cx ) P (Cx ) ≤ n i=1 and P (Cx ) − imply 1 n Pn I(xi ∈ Cx ) p i=1 ≥t P (Cx ) 1 n Pn Pn 1 ′ i=1 I(xi ∈ Cx ) − n i=1 I(xi ∈ Cx ) q P ≥ t. n 1 ′ i=1 (I(xi ∈ Cx ) + I(xi ∈ Cx )) 2n � Lecture 34 Optimistic VC inequality for random classes of sets. 18.465 Indeed, Pn I(xi ∈ Cx ) p i=1 0< t≤ P (Cx ) Pn P (Cx ) − n1 i=1 I(xi ∈ Cx ) ≤q
Pn 1 1 I(x ∈ C ) (C + P ) x i x i=1 2 n Pn Pn 1 1 ′ I(x ∈ C ) − x i i=1 I(xi ∈ Cx ) i=1 n ≤q n P
P n n 1 1 1 ′ i=1 I(xi ∈ Cx ) + n i=1 I(xi ∈ Cx ) 2 n P (Cx ) − 1 n Hence, multiplying by an indicator, ! n 1X ′ I(xi ∈ Cx ) · I(x ∈ Ax ) P (Cx ) ≤ n i=1   Pn Pn 1 1 ′ i=1 I(xi ∈ Cx ) i=1 I(xi ∈ Cx ) − n  ≤ Px ′  q n P
≥t P n n 1 1 1 ′ i=1 I(xi ∈ Cx ) i=1 I(xi ∈ Cx ) + n 2 n   Pn Pn 1 1 ′ i=1 I(xi ∈ Cx ) − n i=1 I(xi ∈ Cx )  q n P ≤ Px ′  sup
≥t P n n 1 1 1 ′ C∈C(x1 ,...,xn ) i=1 I(xi ∈ Cx ) + n i=1 I(xi ∈ Cx ) 2 n 1 · I(x ∈ Ax ) ≤ Px′ 4 Taking expectation with respect to x on both sides, ! Pn P (C) − n1 i=1 I(xi ∈ C) p ≥t sup P P (C) C∈C(x1 ,...,xn )   Pn Pn 1 1 ′ i=1 I(xi ∈ Cx ) i=1 I(xi ∈ Cx ) − n  q n P ≤ 4P  sup
≥t P n n 1 1 1 ′ C∈C(x1 ,...,xn ) i=1 I(xi ∈ Cx ) i=1 I(xi ∈ Cx ) + n 2 n   Pn Pn 1 1 ′ i=1 I(xi ∈ Cx ) i=1 I(xi ∈ Cx ) − n  q n P ≤ 4P  sup
≥t P n n 1 1 1 ′ C∈C(x1 ,...,xn ,x′1 ,...,x′n ) i=1 I(xi ∈ Cx ) + n i=1 I(xi ∈ Cx ) 2 n   Pn 1 ′ εi (I(xi ∈ Cx ) − I(xi ∈ Cx ))  q n Pi=1 = 4P  sup
≥t P n n ′ ′ 1 1 1 ′ C∈C(x1 ,...,xn ,x1 ,...,xn ) i=1 I(xi ∈ Cx ) + n i=1 I(xi ∈ Cx ) 2 n   Pn 1 ′ εi (I(xi ∈ Cx ) − I(xi ∈ Cx ))  q n Pi=1 = 4EPε  sup
≥t Pn ′ n ′ 1 1 1 ′ C∈C(x1 ,...,xn ,x1 ,...,xn ) i=1 I(xi ∈ Cx ) i=1 I(xi ∈ Cx ) + n 2 n Optimistic VC inequality for random classes of sets. Lecture 34 By Hoeffding,  4EPε  sup C∈C(x1 ,...,xn ,x′1 ,...,x′n ) 1 n q 1 2  Pn ′ i=1 εi (I(xi ∈ Cx ) − I(xi ∈ Cx )) 
≥t Pn 1 ′ i=1 I(xi ∈ Cx ) + n i=1 I(xi ∈ Cx )  Pn 1 n 18.465  t2  ≤ 4E△C(x1 ,...,xn ,x′1 ,...,x′n ) (x1 , . . . , xn , x′1 , . . . , xn′ ) · exp −  1  ′ ∈C )−I(x ∈C )) P x x i i √ 1 nP(I(x 2 n ′ 2n 2 − nt4 ≤ 4E△C(x1 ,...,xn ,x′1 ,...,x′n ) (x1 , . . . , xn , x′1 , . . . , xn′ ) · e = 4G(2n)e− nt2 4 i=1 (I(xi ∈Cx )+I(xi ∈Cx ))    2  