Last Iterate Convergence

Last-iterate convergence in optimization and game theory focuses on whether the final iteration of an algorithm converges to a desired solution (e.g., Nash equilibrium), rather than relying on averaging across iterations. Current research investigates this property across various models, including mean field games, Markov decision processes, and zero-sum games, employing algorithms like optimistic gradient descent-ascent, multiplicative weights update, and policy gradient methods. Achieving last-iterate convergence offers significant advantages for practical applications by providing a stable and directly usable solution, improving efficiency and reducing computational costs in large-scale problems. Furthermore, understanding the conditions under which last-iterate convergence holds provides valuable insights into the dynamics of learning algorithms and their behavior in complex systems.

Papers

October 22, 2024

Magnetic Preference Optimization: Achieving Last-iterate Convergence for Language Models Alignment
Mingzhi Wang, Chengdong Ma, Qizhi Chen, Linjian Meng, Yang Han, Jiancong Xiao, Zhaowei Zhang, Jing Huo, Weijie J. Su, Yaodong Yang
Reinforcement Learning Preference Optimization Mirror Descent Self Play Two Player Zero Sum Language Model Alignment Last Iterate Convergence

October 8, 2024

The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD
Thomas Steinke, Milad Nasr, Arun Ganesh, Borja Balle, Christopher A. Choquette-Choo, Matthew Jagielski, Jamie Hayes, Abhradeep Guha Thakurta, Adam Smith, Andreas Terzis
State of the Art Specific Heuristic Privacy Analysis Empirical Privacy Last Iterate Convergence Differential Analysis User Configurable Privacy Defense

October 7, 2024

Last Iterate Convergence in Monotone Mean Field Games
Noboru Isobe, Kenshi Abe, Kaito Ariu
Mean Field Game Last Iterate Convergence Proximal Point Large Scale Game

September 2, 2024

Last-Iterate Convergence of Payoff-Based Independent Learning in Zero-Sum Stochastic Games
Zaiwei Chen, Kaiqing Zhang, Eric Mazumdar, Asuman Ozdaglar, Adam Wierman
Stochastic Game Last Iterate Convergence Zero Sum Markov Game Matrix Game Best Response Independent Q Learning Zero Sum Matrix Game

August 21, 2024

Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs
Washim Uddin Mondal, Vaneet Aggarwal
Primal Dual Constrained Markov Decision Process Policy Parameterization Last Iterate Convergence Policy Parametrization

August 1, 2024

A Policy-Gradient Approach to Solving Imperfect-Information Games with Iterate Convergence
Mingyang Liu, Gabriele Farina, Asuman Ozdaglar
Policy Gradient Last Iterate Convergence Imperfect Information Game Information Extensive Form Game

July 15, 2024

Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning
Alessandro Montenegro, Marco Mussi, Matteo Papini, Alberto Maria Metelli
Policy Gradient Primal Dual Constrained Reinforcement Learning Last Iterate Convergence Stochastic Policy Agnostic Exploration

June 15, 2024

March 12, 2024

On the Last-Iterate Convergence of Shuffling Gradient Methods
Zijian Liu, Zhengyuan Zhou
Convergence Rate Gradient Method Last Iterate Convergence Incremental Gradient Shuffling Gradient

March 11, 2024

Last Iterate Convergence of Incremental Methods and Applications in Continual Learning
Xufeng Cai, Jelena Diakonikolas
Continual LEArning Financial Application Convergence Guarantee Last Iterate Convergence Proximal Point Incremental Model Incremental Gradient

February 20, 2024

Uniform Last-Iterate Guarantee for Bandits and Reinforcement Learning
Junyan Liu, Yunfan Li, Ruosong Wang, Lin F. Yang
Linear Bandit Last Iterate Convergence Order Optimal Regret

December 28, 2023

Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization
James Kotary, Jacob Christopher, My H Dinh, Ferdinando Fioretto
Back Propagation Last Iterate Convergence Algorithm Unrolling Unrolled Optimization

December 13, 2023

Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods
Zijian Liu, Zhengyuan Zhou
Stochastic Gradient Descent Stochastic Gradient Last Iterate Convergence Optimal Convergence Rate High Probability Convergence

November 1, 2023

Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games
Yang Cai, Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, Haipeng Luo, Weiqiang Zheng
Practical Algorithm Video Game Two Player Zero Sum Last Iterate Convergence

September 8, 2023

Learning Zero-Sum Linear Quadratic Games with Improved Sample Complexity and Last-Iterate Convergence
Jiduan Wu, Anas Barakat, Ilyas Fatkhullin, Niao He
Multi Agent Reinforcement Learning Sample Complexity Last Iterate Convergence Dynamic Game Differential Game Linear Quadratic Quadratic System

August 22, 2023

Efficient Last-iterate Convergence Algorithms in Solving Games
Linjian Meng, Zhenxing Ge, Wenbin Li, Bo An, Yang Gao
Two Player Zero Sum Regret Algorithm Last Iterate Convergence Game Solving

June 29, 2023

Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds
Yang Cai, Michael I. Jordan, Tianyi Lin, Argyris Oikonomou, Emmanouil-Vasileios Vlatakis-Gkaragkounis
Video Game Riemannian Manifold Riemannian Gradient Last Iterate Convergence Riemannian Counterpart Independent Rate

March 5, 2023

Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback
Yang Cai, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng
Bandit Feedback Markov Game Last Iterate Convergence Zero Sum Markov Game Matrix Game

February 2, 2023

ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPs
Ted Moskovitz, Brendan O'Donoghue, Vivek Veeriah, Sebastian Flennerhag, Satinder Singh, Tom Zahavy
Reinforcement Learning Markov Decision Process Constrained Reinforcement Learning Constrained Markov Decision Process Last Iterate Convergence Gradient Descent Ascent Optimistic Gradient

Last Iterate Convergence

Papers

Magnetic Preference Optimization: Achieving Last-iterate Convergence for Language Models Alignment

The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD

Last Iterate Convergence in Monotone Mean Field Games

Last-Iterate Convergence of Payoff-Based Independent Learning in Zero-Sum Stochastic Games

Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs

A Policy-Gradient Approach to Solving Imperfect-Information Games with Iterate Convergence

Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning

Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms

Last-iterate Convergence Separation between Extra-gradient and Optimism in Constrained Periodic Games

On the Last-Iterate Convergence of Shuffling Gradient Methods

Last Iterate Convergence of Incremental Methods and Applications in Continual Learning

Uniform Last-Iterate Guarantee for Bandits and Reinforcement Learning

Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization

Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods

Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games

Learning Zero-Sum Linear Quadratic Games with Improved Sample Complexity and Last-Iterate Convergence

Efficient Last-iterate Convergence Algorithms in Solving Games

Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds

Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback

ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPs