Optimization, Learning, and Games with Predictable Sequences
We provide several applications of Optimistic Mirror Descent, an online learning algorithm based on the idea of predictable sequences. First, we recover the Mirror Prox algorithm for offline optimization, prove an extension to Hölder-smooth functions, and apply the results to saddle-point type problems. Next, we prove that a version of Optimistic Mirror Descent (which has a close relation to the Exponential Weights algorithm) can be used by two strongly-uncoupled players in a finite zero-sum matrix game to converge to the minimax equilibrium at the rate of O((log T )T ). This addresses a question of Daskalakis et al [6]. Further, we consider a partial information version of the problem. We then apply the results to convex programming and exhibit a simple algorithm for the approximate Max Flow problem.
The authors apply the Optimistic Mirror Descent 
      algorithm to a variety of problems where smoothness induces a certain 
      amount of predictability in the resulting loss function sequences. In 
      particular, better rates are possible when either: 1) the objective G is 
      fixed for all t, and smooth, or 2) the problem is a saddle point problem 
      on a function phi(f, x) which is appropriately smooth for each of its 
      arguments individually, and the optimistic mirror descent algorithm is 
      played against itself. These are rather specialized notions of 
      predictability, but they lead to some interesting results. Section 4 
      extends this to zero-sum games, and Section 5 considers approximate smooth 
      convex programming. Unlike many applications of online algorithms, 
      the goal in most cases in this paper is to solve a batch optimization 
      problem. This should probably be made more explicit in the introduction. 
      Section 3: The author’s need to be more clear about why this 
      section improves on the result from Lemma 3. The key point (I think) is 
      that the smoothness assumptions of Cor 5 may be satisfied even if G(f) = 
      inf_x phi(f, x) is not smooth. Note that an alternative approach to 
      solving the problem of Sec 3 is to run an online algorithm against a 
      best-response adversary. It is worth asking whether or not any online 
      algorithm paired with a best-response oracle can lead to the convergence 
      rates like 1/T produced by the procedure introduced here. (Perhaps not, 
      since this would appear to destroy predictability). Section 4: Be 
      more clear on how this section improves on Section 3. The key seems to be 
      adding robustness to an arbitrary adversary in addition to the good bounds 
      for the predictable one. The results of Sec 4.2 are rather weaker than the 
      section title suggests. I would suggest describing this setting as 
      multi-point bandit feedback, and citing “Optimal Algorithms for Online 
      Convex Optimization with Multi-Point Bandit Feedback”. Based on the 
      notational similarities, it seems quite likely the authors are aware of 
      this work. It really should have been cited in the submission. It also 
      seems somewhat surprising that 4 points are needed, rather than just 2 --- 
      this should be discussed. Section 5: It’s not clear to me that one 
      can assume F^* is known WLOG. At the very least, the binary search 
      procedure needs to be made precise: Are we running the algorithm of 
      section 5 at each step of the binary search? If so, how do you check 
      whether the guess of F^* is too high or too low? How does using a guess of 
      F^* that is off by some amount delta impact the final bound of Lemma 8? 
      This carries over to Sec 5.1 as well of course. Also, Eq (11) 
      appears to fit into the setup of Sec 3 (Cor 5), why do we need the 
      machinery of Sec 4.2 here (Lemma 7)? Is Line 368 a typo? In 
      general, the paper suffers from some typos that made it more difficult to 
      review, and could also probably use a bit more discussion of related work 
      (several particular citations are recommended below). Local 
      points: - Line 112: This simple intuition and analysis for Mirror 
      Prox is very nice. - Line 93: This bound can be seen as a direct 
      generalization of the result that the “Be The Leader” (BTL) algorithm 
      suffers no regret, since you arrive at a BTL algorithm by taking Delta_t = 
      M_t. This is worth mentioning, as well as a citation to “Efﬁcient 
      algorithms for online decision problems” (Adam Kalai and Santosh Vempala). 
      - Line 131: I would find the section title “Saddle-Point 
      Optimization” more clear. - Line 154-155: citing “Adaptive game 
      playing using multiplicative weights” (Yoav Freund and Robert E. Schapire) 
      is probably appropriate. This citation is also appropriate at lines 
      208-209. - Line 223: More detail needed, explain exactly why Sec 3 
      doesn’t lead to this result (because it doesn’t handle an arbitrary 
      adversary as well?), as well as why a direct application of mirror-prox 
      does not provide strong decoupling. - Line 225, also lines 265 and 
      268: It’s imprecise to refer to regret bounds like 1/T or 1/Sqrt(T), you 
      need to multiply through by T to get regret as defined on line 65. 
      Alternatively, refer to these as convergence rates. - Line 
      312-314: Typos in both “Build estimates” sections of the pseudo-code, you 
      want r^+ - r^-, as written all the a’s and b’s are zero. - Line 
      366: Epsilon hasn’t be defined yet, introduce as an arbitrary constant eps 
      > 0 earlier in the statement. - Line 368: Do you mean Corollary 
      5, not Lemma 7? If Lemma 7 is really intended, then the procedure needs to 
      be made more clear, e.g., what is the matrix A here? - Appendix: 
      The proofs make extensive use of copy-paste, which makes them much harder 
      to read because there is so much repetition. Please re-structure the 
      proofs so they are less verbose and the main arguments are more 
      clear.