18.657 Mathematics of Machine Learning, Lecture 22 Notes

18.657: Mathematics of Machine Learning Lecture 22 Nov. 30, 2015 Lecturer: Philippe Rigollet Scribe: Aden Forrow 7. BLACKWELL’S APPROACHABILITY 7.1 Vector Losses David Blackwell introduced approachability in 1956 as a generalization of zero sum game theory to vector payoffs. Born in 1919, Blackwell was the first black tenured professor at UC Berkeley and the seventh black PhD in math in the US. Recall our setup for online linear optimization. At time t, we choose an action at ∈ ∆K and the adversary chooses zt ∈ B∞ (1). We then get a loss ℓ(at , zt ) = hat , zt i. In the full information case, where we observe zt and not just ℓ(at , zt ), this is the same as prediction with expert advice. Exponential weights leads to a regret bound r n Rn ≤ log(K). 2 The setup of a zero sum game is nearly identical: • Player 1 plays a mixed strategy p ∈ ∆n . • Player 2 plays q ∈ ∆m . • Player 1’s payoff is p⊤ M q. Here M is the game’s payoff matrix. Theorem: Von Neumann Minimax Theorem max min p⊤ M q = min max p⊤ M q. p∈∆n q∈∆m q∈∆m p∈∆n The minimax is called the value of the game. Each player can prevent the other from doing any better than this. The minimax theorem implies that if there is a good response pq to any individual q, then there is a silver bullet strategy p that works for any q. Corollary: If ∀q ∈ ∆n , ∃p such that p⊤ M q ≥ c, then ∃p such that ∀q, p⊤ M q ≥ c. Von Neumann’s minimax theorem can be extended to more general sets. The following theorem is due to Sion (1958). Theorem: Sion’s Minimax Theorem Let A and Z be convex, compact spaces, and f : A × Z → R. If f (a, ·) is upper semicontinuous and quasiconcave on Z ∀a ∈ A and 1 f (·, z) is lower semicontinuous and quasiconvex on A ∀z ∈ Z, then inf sup f (a, z) = sup inf f (a, z). z∈Z a∈A a∈A z∈Z (Note - this wasn’t given explicitly in lecture, but we do use it later.) Quasiconvex and quasiconcave are weaker conditions than convex and concave respectively. Blackwell looked at the case with vector losses. We have the following setup: • Player 1 plays a ∈ A • Player 2 plays z ∈ Z • Player 1’s payoff is ℓ(a, z) ∈ Rd We suppose A and Z are both compact and convex, that ℓ(a, z) is bilinear, and that kℓ(a, z)k ≤ R ∀a ∈ A, z ∈ Z. All norms in this section are Euclidean norms. Can we translate the minimax theorem directly to this new setting? That is, if we fix a set S ⊂ Rd , and if ∀z ∃a such that ℓ(a, z) ∈ S, does there exist an a such that ∀z ℓ(a, z) ∈ S? No. We’ll construct a counterexample. Let A = Z = [0, 1], ℓ(a, z) = (a, z), and S = {(a, z) ∈ [0, 1]2 : a = z}. Clearly, for any z ∈ Z there is an a ∈ A such that a = z and ℓ(a, z) ∈ S, but there is no a ∈ A such that ∀z, a = z. Instead of looking for a single best strategy, we’ll play a repeated game. At time t, player 1 plays at = at (a1 , z1 , . . . , at−1 , zt−1 ) and player 2 plays zt = zt (a1 , z1 , . . . , at−1 , zt−1 ). Player 1’s average loss after n iterations is n 1X ℓ(at , zt ) ℓ̄n = n t=1 Let d(x, S) be the distance between a point x ∈ Rd and the set S, i.e. d(x, S) = inf kx − sk. s∈S If S is convex, the infimum is a minimum attained only at the projection of x in S. Definition: A set S is approachable if there exists a strategy at = at (a1 , z1 , . . . , at−1 , zt−1 ) such that limn→∞ d(ℓ¯n , S) = 0. Whether a set is approachable depends on the loss function ℓ(a, z). In our example, we can choose a0 = 0 and at = zt−1 to get n 1X (zt−1 , zt ) = (z̄, z̄) ∈ S. n→∞ n lim ℓ̄n = lim n→∞ t=1 So this S is approachable. 7.2 Blackwell’s Theorem We have the same conditions on A, Z, and ℓ(a, z) as before. 2 Theorem: Blackwell’s Theorem Let S be a closed convex set of R2 with kxk ≤ R ∀x ∈ S. If ∀z, ∃a such that ℓ(a, z) ∈ S, then S is approachable. Moreover, there exists a strategy such that 2R d(ℓ̄n , S) ≤ √ n Proof. We’ll prove the rate; approachability of S follows immediately. The idea here is to transform the problem to a scalar one where Sion’s theorem applies by using half spaces. Suppose we have a half space H = {x ∈ Rd : hw, xi ≤ c} with S ⊂ H. By assumption, ∀z ∃a such that ℓ(a, z) ∈ H. That is, ∀z ∃a such that hw, ℓ(a, z)i ≤ c, or max minhw, ℓ(a, z)i ≤ c. z∈Z a∈A By Sion’s theorem, min maxhw, ℓ(a, z)i ≤ c. a∈A z∈Z So ∃a∗H such that ∀z ℓ(a, z) ∈ H. This works for any H containing S. We want to choose Ht so that ℓ(at , zt ) brings the average ℓ¯t closer to S than ℓ¯t−1 . An intuitive choice is to have the hyperplane W bounding Ht be the separating hyperplane between S and ℓ¯t−1 closest to S. This is Blackwell’s strategy: let W be the hyperplane through πt ∈ argminµ∈S kℓ¯t−1 − µk with normal vector ℓ̄t−1 − πt . Then H = {x ∈ Rd : hx − πt , ℓ̄t−1 − πt i ≤ 0}. Find a∗H and play it. We need one more equality before proving convergence. The average loss can be expanded: t−1 1 ℓ̄t−1 + ℓt t t t−1 ¯ t−1 1 = (ℓt−1 − πt ) + πt + ℓt t t t ℓ̄t = Now we look at the distance of the average from S, using the above equation and the definition of πt+1 : d(ℓ¯t , S)2 = kℓ̄t − πt+1 k2 ≤ kℓ̄t − πt k2 2 t−1 ¯ 1 (ℓt−1 − πt ) + (ℓt − πt ) t t  2 t−1 kℓt − πt k2 t−1 d(ℓ¯t−1 , S)2 + + 2 2 hℓt − πt , ℓ¯t−1 − πt i = t t2 t = Since ℓt ∈ H, the last term is negative; since ℓt and πt are both bounded by R, the middle 2 term is bounded by 4R . Letting µ2t = t2 d(ℓ̄t , S)2 , we have a recurrence relation t2 µ2t ≤ µ2t−1 + 4R2 , 3 implying µ2n ≤ 4nR2 . Rewriting in terms of the distance gives the desired bound, 2R d(ℓ̄t , S) ≤ √ n Note that this proof fails for nonconvex S. 7.3 Regret Minimization via Approachability K (1). As we showed before, exponential weights R ≤ Consider the case A = ∆K , Z = B∞ n p c n log(K). We can get the same dependence on n with an approachability-based strategy. First recall that n n 1 1X 1X Rn = ℓ(at , zt ) − min ℓ(ej , zt ) j n n n t=1 t=1 # " n n 1X 1X = max ℓ(at , zt ) − ℓ(ej , zt ) j n n t=1 t=1 If we define a vector average loss n 1X ℓ̄n = (ℓ(at , zt ) − ℓ(e1 , zt ), . . . , ℓ(at , zt ) − ℓ(eK , zt )) ∈ RK , n t=1 − → 0 if and only if all components of ℓ¯n are nonpositive. That is, we need d(ℓ¯n , OK ) → 0, − K where OK = {x ∈ R : −1 ≤ xi ≤ 0, ∀i} is the nonpositive orthant. Using Blackwell’s approachability strategy, we get r Rn K − ≤ d(ℓ̄n , OK ) ≤ c . n n p √ The K dependence is worse than exponential weights, K instead of log(K). How do we find a∗H ? As a concrete example, let K = 2. We need a∗H tp satisfy Rn n ∗ hw, ℓ(a∗H , z)i = hw, haH , ziy − zi ≤ c for all z. Here y is the vector of all ones. Note that c ≥ 0 since 0 is in S and therefore in H. Rearranging, ha∗H , zihw, yi ≤ hw, zi + c, Choosing a∗H = w hw,yi will work; the inequality reduces to hw, zi ≤ hw, zi + c. Approachability in the bandit setting with only partial feedback is still an open problem. 4 References [Bla56] D. Blackwell, An analog of the minimax theorem for vector payoffs, Pacific J. Math. 6 (1956), no. 1, 1–8 [Sio58] M. Sion, On general minimax theorems. Pacific J. Math. 8 (1958), no. 1, 171–176. 5