Optimization, Learning, and Games with Predictable Sequences

By Alexander Rakhlin, Karthik Sridharan. 2013

427 citations recorded by the source corpus.

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 [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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Management Science and Operations Research

Citations in the corpus

Agnostic Federated Learning (2019, background): “Recently, Rakhlin and Sridharan (2013) and Daskalakis et al. (2017) gave an optimistic gradient descent algorithm for minimax optimizations.”
Training GANs with Optimism (2017, methodology): “…that Optimistic Mirror De-scent and its generalization of Optimistic Follow-the-Regularized-Leader (OFTRL), achieve faster convergence rates than gradient descent in convex-concave zero-sum games (Rakhlin & Sridharan, 2013a;b) and even in general normal form games (Syrgkanis et al., 2015).”
Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals (2018, background): “Correspondingly, one can transform a robust problem to a constrained one at the cost of an extra bisection search (e.g. Christiano et al., 2011; Rakhlin and Sridharan, 2013).”
An Online Learning Approach to Generative Adversarial Networks (2017, background): “This was later improved by Daskalakis et al. (2015); Rakhlin and Sridharan (2013), demonstrating a guarantee of ε = O (log T/T ) .”
Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks (2018, background): “1 (Improved) Optimistic Mirror Descent Daskalakis, Ilyas, Syrgkanis, and Zeng [2017] employed Optimistic Mirror Descent (OMD) [Rakhlin and Sridharan, 2013] motivated by online learning to solve the instability problem in GANs.”
Introduction to Multi-Armed Bandits (2019, background): “n be extended to inﬁnite action sets, as long as ALG and ADV admit o(T) expected regret for the repeated game with a given game matrix; see Exercise 9.5 for a precise formulation. Faster convergence. Rakhlin and Sridharan (2013); Daskalakis et al. (2015) obtain O~(1 t) convergence rates for repeated”
Improved Dynamic Regret for Non-degenerate Functions (2016, methodology): “In (Jadbabaie et al., 2015), the authors propose an adaptive algorithm based on the optimistic mirror descent (Rakhlin and Sridharan, 2013), such that the dynamic regret is given in terms of all the three regularities ( ∗ T , F T , and G T ).”
Stochastic matrix games with bandit feedback (2020, background): “Two aspects of this problem distinguish it from other setups considered in the literature [14, 8, 33].”
On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes (2018, methodology): “Note that, with ǫ = 0, (3) are the coordinate-wise stepsizes used in Ada-Grad (Duchi et al., 2011), while (2) have been used in online convex optimization to achieve adaptive regret guarantees, (e.g. Rakhlin and Sridharan, 2013; Orabona and P´al, 2018).”
Provable Self-Play Algorithms for Competitive Reinforcement Learning (2020, background): “C Proofs for Section 5 C.1 Proof of Theorem 9 The theorem is almost an immediate consequence of the general result on mirror descent (Rakhlin and Sridharan, 2013).”
Predictor-Corrector Policy Optimization (2018, background): “[54] Sasha Rakhlin and Karthik Sridharan.”
Fast Convergence of Regularized Learning in Games (2015, methodology): “Rakhlin and Sridharan [17] address this concern by modifying the OMD algorithm with additional smoothing and adaptive step-sizes so as to preserve the fast rates in the favorable case while still guaranteeing O(1/ p T ) regret for each player, no matter how the opponents play.”
A Counter-example to Karlin's Strong Conjecture for Fictitious Play (2014, background): “ of O(t−12) that is typically achieved by no-regret learning algorithms [13], [26], [8], and the improved convergence rate of O(logt t ) of some no-regret learning algorithms, obtained recently [11], [32]. Indeed, about ten years after Robinson’s proof and ﬁve decades ago, Samuel Karlin conjectured ”
Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile (2018, methodology): “Following Rakhlin and Sridharan ( ), this method is known as optimistic mirror descent (OMD), and was first studied under the name “mirror-prox” by Nemirovski ( ).”
ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problems and GANs (2019, neutral): “Although the recent name ‘optimism’ originates from its use in online optimization [6, 55, 56, 62], the idea dates back to Popov’s work in the 1980s [53] and has been studied independently in the mathematical programming community [35, 32, 34, 33, 7].”
Optimization in Dynamic Environments : Improved Regret Rates for Strongly Convex Problems (2016, neutral): “where Mt is a causally predictable sequence available to the algorithm prior to time t [18], [19].”
Faster saddle-point optimization for solving large-scale Markov decision processes (2019, methodology): “The proof is based on standard arguments, see, for instance, Lemma 1 of Rakhlin and Sridharan (2013b).”
Cycles in adversarial regularized learning (2017, background): “Along these lines, Daskalakis et al. [9] and Rakhlin and Sridharan [31] developed classes of dynamics that enjoy a O (log t/t ) regret minimization rate in two-player zero-sum games.”