Optimization, Learning, and Games with Predictable Sequences

Abstract

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.

Cited by in corpus (50)

• Fast Convergence of Regularized Learning in Games
• Near-Optimal Algorithms for Minimax Optimization
• Efficient Algorithms for Adversarial Contextual Learning
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise
• Predictive Online Convex Optimization
• A Counter-Example to Karlin's Strong Conjecture for Fictitious Play
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets
• Exploration by Optimisation in Partial Monitoring
• GANGs: Generative Adversarial Network Games
• Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient
• Adversarial Generalized Method of Moments
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities
• Adaptive Sampling for Stochastic Risk-Averse Learning
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games
• Multi-agent online learning in time-varying games
• Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
• Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
• Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games
• Adaptive Approximate Policy Iteration
• Tight last-iterate convergence rates for no-regret learning in multi-player games
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization
• Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks
• Near-Optimal No-Regret Learning in General Games
• Scale-Free Algorithms for Online Linear Optimization
• Taking a hint: How to leverage loss predictors in contextual bandits?
• Temporal Variability in Implicit Online Learning
• No-Regret Prediction in Marginally Stable Systems
• Recursive Experts: An Efficient Optimal Mixture of Learning Systems in Dynamic Environments
• Active Sampling for Min-Max Fairness
• Hedging in games: Faster convergence of external and swap regrets
• A Max-Min Entropy Framework for Reinforcement Learning
• Deep Online Convex Optimization with Gated Games
• A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Games
• Faster saddle-point optimization for solving large-scale Markov decision processes
• No-regret distributed learning in subnetwork zero-sum games
• Solving Combinatorial Games using Products, Projections and Lexicographically Optimal Bases
• Unconstrained Online Optimization: Dynamic Regret Analysis of Strongly Convex and Smooth Problems
• An Optimistic Acceleration of AMSGrad for Nonconvex Optimization
• Last Round Convergence and No-Instant Regret in Repeated Games with Asymmetric Information
• Optimistic and Adaptive Lagrangian Hedging
• No-Regret Learnability for Piecewise Linear Losses
• Follow the Neurally-Perturbed Leader for Adversarial Training
• Dynamic Regret Convergence Analysis and an Adaptive Regularization Algorithm for On-Policy Robot Imitation Learning
• Matrix games with bandit feedback
• Let's be Honest: An Optimal No-Regret Framework for Zero-Sum Games
• Strongly-Typed Agents are Guaranteed to Interact Safely
• Online Learning with Optimism and Delay
• Can Q-Learning be Improved with Advice?