Optimization, Learning, and Games with Predictable Sequences
This work addresses incremental improvements in optimization and game theory, providing new algorithms for researchers and practitioners in machine learning and related fields.
The paper tackles the problem of online learning and optimization by applying Optimistic Mirror Descent to various settings, resulting in a convergence rate of O((log T)/T) for zero-sum matrix games and extensions to offline optimization and convex programming.
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 Holder-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 2011. 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.