Fetching the paper…

Reading the bibliography…

2013

Optimization, Learning, and Games with Predictable Sequences

Rakhlin, Alexander, Sridharan, Karthik

Original
PDF
Post on X

Understand

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.

Optimization, Learning, and Games with Predictable Sequences · Around

Built on

Beyond the flow decomposition barrier
A. Goldberg and S. Rao · 1998
Earlier work this paper cites.
Adaptive game playing using multiplicative weights
Y. Freund and R. Schapire · 1999
Earlier work this paper cites.
Adaptive and self-confident on-line learning algorithms
P. Auer, N. Cesa-Bianchi, and C. Gentile · 2002
Earlier work this paper cites.
Prox-method with rate of convergence O(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems
A. Nemirovski · 2004
Earlier work this paper cites.

Similar

Smooth minimization of non-smooth functions
Y. Nesterov · 2005
Cited alongside, same era.
Prediction, Learning, and Games
N. Cesa-Bianchi and G. Lugosi · 2006
Cited alongside, same era.
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
P. Christiano, J. A Kelner, A. Madry, D. A. Spielman, and S.-H. Teng · 2011
Cited alongside, same era.
Near-optimal no-regret algorithms for zero-sum games
C. Daskalakis, A. Deckelbaum, and A. Kim · 2011
Cited alongside, same era.

Then

The multiplicative weights update method: A meta-algorithm and applications
S. Arora, E. Hazan, and S. Kale · 2012
Later among the works it cites.
Online optimization with gradual variations
C.-K. Chiang, T. Yang, C.-J. Lee, M. Mahdavi, C.-J. Lu, R. Jin, and S. Zhu · 2012
Later among the works it cites.
Online learning with predictable sequences
A. Rakhlin and K. Sridharan · 2013
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…