last-iterate convergence

Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback
We revisit the problem of learning in two-player zero-sum Markov games, focusing on developing an algorithm that is uncoupled, …
arxiv
Doubly Optimal No-Regret Learning in Monotone Games
We consider online learning in multi-player smooth monotone games. Existing algorithms have limitations such as (1) being only …
PDF arxiv
Accelerated Single-Call Methods for Constrained Min-Max Optimization
We study first-order methods for constrained min-max optimization. Existing methods either requires two gradient calls or two …
PDF arxiv
Finite-Time Last-Iterate Convergence for Learning in Multi-Player Games
We study the question of last-iterate convergence rate of the extragradient algorithm by Korpelevich [1976] and the optimistic gradient …
PDF Video
Accelerated Algorithms for Monotone Inclusions and Constrained Nonconvex-Nonconcave Min-Max Optimization
We study monotone inclusions and monotone variational inequalities, as well as their generalizations to non-monotone settings. We first …
PDF arxiv
Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalities
The monotone variational inequality is a central problem in mathematical programming that unifies and generalizes many important …
PDF arxiv