18.657 Mathematics of Machine Learning, Lecture 3 Notes

18.657: Mathematics of Machine Learning Lecture 3 Sep. 16, 2015 Lecturer: Philippe Rigollet Scribe: James Hirst 1.5 Learning with a finite dictionary Recall from the end of last lecture our setup: We are working with a finite dictionary H = {h1 , . . . , hM } of estimators, and we would like to understand the scaling of this problem with respect to M and the sample size n. Given H, one idea is to simply try to minimize ˆ erm , the empirical risk based on the samples, and so we define the empirical risk minimizer, h by ˆ erm ∈ argmin R ˆ n (h). h h∈H ˆ instead of h ˆ erm when possible. Also recall the In what follows, we will simply write h ¯ which (somehow) minimizes the true risk and is defined by definition of the oracle, h, h̄ ∈ argmin R(h). h∈H ˆ cannot hope to do better than h ¯ in The following theorem shows that, although h general, the difference should not be too large as long as the sample size is not too small compared to M . ˆ satisfies Theorem: The estimator h ˆ ≤ R(h) ¯ + R(h) r 2 log(2M/δ) n with probability at least 1 − δ. In expectation, it holds that r ˆ ≤ R(h) ¯ + 2 log(2M ) . IE[R(h)] n ˆ we have R ˆ ≤R ¯ which gives ˆ n (h) ˆ n (h), Proof. From the definition of h, ˆ ≤ R(h) ¯ + [R ¯ − R(h)] ¯ + [R(h) ˆ −R ˆ ˆ n (h) ˆ n (h)]. R(h) The only term here that we need to control is the second one, but since we don’t have ¯ we will bound it by a maximum over H and then apply any real information about h, Hoeffding: r ¯ − R(h)] ¯ + [R(h) ˆ −R ˆ ≤ 2 max |R ˆ n (h) ˆ n (h)] ˆ n (hj ) − R(hj )| ≤ 2 log(2M/δ) [R j 2n with probability at least 1 − δ, which completes the first part of the proof. 15 To obtain the bound in expectation, we start with a standard trick from probability which bounds a max by its sum in a slightly more clever way. Here, let {Zj }j be centered random variables, then         1 1 IE max |Zj | = log exp sIE max |Zj | ≤ log IE exp s max |Zj | , j j j s s where the last inequality comes from applying Jensen’s inequality to the convex function exp(·). Now we bound the max by a sum to get   2  2M X 1 1 s log(2M ) s ≤ log IE [exp(sZj )] ≤ log 2M exp = + , s s 8n s 8n j=1 ˆ n (hj ) − R(hj ) in our case and then applied Hoeffding’s Lemma. Balwhere we used Zj = R p ancing terms by minimizing over s, this gives s = 2 2n log(2M ) and plugging in produces   r ˆ n (hj ) − R(hj )| ≤ log(2M ) , IE max |R j 2n which finishes the proof. 2. CONCENTRATION INEQUALITIES Concentration inequalities are results that allow us to bound the deviations of a function of random variables from its average. The first of these we will consider is a direct improvement to Hoeffding’s Inequality that allows some dependence between the random variables. 2.1 Azuma-Hoeffding Inequality Given a filtration {Fi }i of our underlying space X , recall that {∆i }i are called martingale differences if, for every i, it holds that ∆i ∈ Fi and IE [∆i |Fi ] = 0. The following theorem gives a very useful concentration bound for averages of bounded martingale differences. Theorem (Azuma-Hoeffding): Suppose that {∆i }i are margingale differences with respect to the filtration {Fi }i , and let Ai , Bi ∈ Fi−1 satisfy Ai ≤ ∆i ≤ Bi almost surely for every i. Then " #   1X 2n2 t2 IP ∆i > t ≤ exp − Pn . 2 n i=1 kBi − Ai k∞ i In comparison to Hoeffding’s inequality, Azuma-Hoeffding affords not only the use of non-uniform boundedness, but additionally requires no independence of the random variables. Proof. We start with a typical Chernoff bound. " # h P i h h P ii X IP ∆i > t ≤ IE es ∆i e−st = IE IE es ∆i |Fn−1 e−st i 16 h Pn−1 i Pn−1 2 2 ∆i ∆i = IE es IE[es∆n |Fn−1 ] e−st ≤ IE[es · es (Bn −An ) /8 ]e−st , where we have used the fact that the ∆i , i < n, are all Fn measureable, and then applied Hoeffding’s lemma on the inner expectation. Iteratively isolating each ∆i like this and applying Hoeffding’s lemma, we get # ! " n X s2 X ∆i > t ≤ exp kBi − Ai k2∞ e−st . IP 8 i i=1 Optimizing over s as usual then gives the result. 2.2 Bounded Differences Inequality Although Azuma-Hoeffding is a powerful result, its full generality is often wasted and can be cumbersome to apply to a given problem. Fortunately, there is a natural choice of the {Fi }i and {∆i }i , giving a similarly strong result which can be much easier to apply. Before we get to this, we need one definition. Definition (Bounded Differences Condition): Let g : X → IR and constants ci be given. Then g is said to satisfy the bounded differences condition (with constants ci ) if sup x1 ,...,xn ,x′i |g(x1 , . . . , xn ) − g(x1 , . . . , xi′ , . . . , xn )| ≤ ci for every i. Intuitively, g satisfies the bounded differences condition if changing only one coordinate of g at a time cannot make the value of g deviate too far. It should not be too surprising that these types of functions thus concentrate somewhat strongly around their average, and this intuition is made precise by the following theorem. Theorem (Bounded Differences Inequality): If g : X → IR satisfies the bounded differences condition, then   2t2 IP [|g(X1 , . . . , Xn ) − IE[g(X1 , . . . , Xn )| > t] ≤ 2 exp − P 2 . i ci Proof. Let {Fi }i be given by Fi = σ(X1 , . . . , Xi ), and define the martingale differences {∆i }i by ∆i = IE [g(X1 , . . . , Xn )|Fi ] − IE [g(X1 , . . . , Xn )|Fi−1 ] . Then " IP | X #   ∆i | > t = IP g(X1 , . . . , Xn ) − IE[g(X1 , . . . , Xn ) > t , i exactly the quantity we want to bound. Now, note that   ∆i ≤ IE sup g(X1 , . . . , xi , . . . , Xn )|Fi − IE [g(X1 , . . . , Xn )|Fi−1 ] xi 17   = IE sup g(X1 , . . . , xi , . . . , Xn ) − g(X1 , . . . , Xn )|Fi−1 =: Bi . xi Similarly,   ∆i ≥ IE inf g(X1 , . . . , xi , . . . , Xn ) − g(X1 , . . . , Xn )|Fi−1 =: Ai . xi At this point, our assumption on g implies that kBi − Ai k∞ ≤ ci for every i, and since Ai ≤ ∆i ≤ Bi with Ai , Bi ∈ Fi−1 , an application of Azuma-Hoeffding gives the result. 2.3 Bernstein’s Inequality Hoeffding’s inequality is certainly a powerful concentration inequality for how little it assumes about the random variables. However, one of the major limitations of Hoeffding is just this: Since it only assumes boundedness of the random variables, it is completely oblivious to their actual variances. When the random variables in question have some known variance, an ideal concentration inequality should capture the idea that variance controls concentration to some degree. Bernstein’s inequality does exactly this. Theorem (Bernstein’s Inequality): Let X1 , . . . , Xn be P independent, centered random variables with |Xi | ≤ c for every i, and write σ 2 = n−1 i Var(Xi ) for the average variance. Then " # ! 1X nt2 Xi > t ≤ exp − 2 2 IP . n 2σ + 3 tc i Here, one should think of t as being fixed and relatively small compared to n, so that strength of the inequality indeed depends mostly on n and 1/σ 2 . Proof. The idea of the proof is to do a Chernoff bound as usual, but to first use our assumptions on the variance to obtain a slightly better bound on the moment generating functions. To this end, we expand "∞ # ∞ k k−2 X (sXi )k X s c sXi IE[e ] = 1 + IE[sXi ] + IE ≤ 1 + Var(Xi ) , k! k! k=2 k=2 where we have used IE[Xik ] ≤ IE[Xi2 |Xi |k−2 ] ≤ Var(Xi )ck−2 . Rewriting the sum as an exponential, we get IE[esXi ] ≤ s2 Var(Xi )g(s), g(s) := esc − sc − 1 . c2 s2 The Chernoff bound now gives " # !   X 1X 2 2 2 IP Xi > t ≤ exp inf [s ( Var(Xi ))g(s) − nst] = exp n · inf [s σ g(s) − st] , s>0 s>0 n i i and optimizing this over s (a fun calculus exercise) gives exactly the desired result. 18 3. NOISE CONDITIONS AND FAST RATES ˆ we would like to obtain an upper bound To measure the effectiveness of the estimator h, ∗ ˆ = R(h) ˆ − R(h ). It should be clear, however, that this must depend on the excess risk E(h) significantly on the amount of noise that we allow. In particular, if η(X) is identically equal ˆ in to 1/2, then we should not expect to be able to say anything meaningful about E(h) general. Understanding this trade-off between noise and rates will be the main subject of this chapter. 3.1 The Noiseless Case A natural (albeit somewhat naı̈ve) case to examine is the completely noiseless case. Here, we will have η(X) ∈ {0, 1} everywhere, Var(Y |X) = 0, and E(h) = R(h) − R(h∗ ) = IE[|2η(X) − 1|1I(h(X) = 6 h∗ (X))] = IP[h(X) = 6 h∗ (X)]. Let us now denote ¯ i) = ˆ i) = Zi = 1I(h(X 6 Yi ) − 1I(h(X 6 Yi ), and write Z¯i = Zi − IE[Zi ]. Then notice that we have ˆ i) = ¯ i )), |Zi | = 1I(h(X 6 h(X and ˆ i) = Var(Zi ) ≤ IE[Zi2 ] = IP[h(X 6 ¯h(Xi )]. For any classifier hj ∈ H, we can similarly define Zi (hj ) (by replacing ˆh with hj throughout). Then, to set up an application of Bernstein’s inequality, we can compute n 1X ¯ i )] =: σ 2 . Var(Zi (hj )) ≤ IP[hj (Xi ) 6= h(X j n i=1 At this point, we will make a (fairly strong) assumption about our dictionary H, which ¯ = h∗ . Since the random variables Zi compare is that h∗ ∈ H, which further implies that h ¯ this will allow us to use them to bound E(h), ˆ which rather compares to h∗ . Now, to h, ¯ applying Bernstein (with c = 2) to the {Zi (hj )}i for every j gives ! " n # 1X ¯ nt2 δ IP Zi (hj ) > t ≤ exp − 2 4 =: , n M 2σj + 3 t i=1 and a simple computation here shows that it is enough to take s  2σj2 log(M/δ) 4 t ≥ max  , log(M/δ) =: t0 (j) n 3n for this to hold. From here, we may use the assumption ¯h = h∗ to conclude that h i ˆ > t0 (ĵ) ≤ δ, hˆ = h. ˆ IP E(h) j 19 ˆ which implies that However, we also know that σˆj2 ≤ E(h), s ˆ ≤ max  E(h)  ˆ 2E(h) log(M/δ) 4 , log(M/δ) n 3n ˆ gives the improved rate with probability 1 − δ, and solving for E(h) ˆ ≤ 2 log(M/δ) . E(h) n 20