Mirror Descent

Follow this topic Ask about this topic

Momentum

2 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 17

All topics

Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games
Sep 30, 2026Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng XiongLast-Iterate Convergence Oracle Complexity
Department of Computer Sciences, University of Wisconsin-Madison
Averaged Mirror Descent and Dual Gradient Methods: Convergent Algorithms for Entropic Gromov-Wasserstein Problems
Sep 25, 2026Joanna Marks, Gabriel Rioux, Riccardo PasseggeriGradient Descent Mirror Descent
⋆Denotes equal contribution to this work.
Independent Reinforcement Learning in Discounted Markov Games
Sep 1, 2026Asrin Efe Yorulmaz, Ugur Aydin, Tamer BasarReinforcement Learning Game Theory
Department of Electrical and Computer Engineering, University of Illinois Urbana-Champaign, Urbana, IL, 61801, USA
Establishing Boundary KKT Convergence of Mirror Descent through Reparameterization
Aug 7, 2026Kuangyu Ding, Kim-Chuan TohNonconvex Optimization Mirror Descent
School of Industrial Engineering, Purdue University, West Lafayette, IN 47907, USA. · Department of Mathematics, National University of Singapore, Singapore 119076.
Non-KKT Accumulation in Entropic Mirror Descent
Aug 3, 2026Kuangyu Ding, Kim-Chuan TohOptimization Convergence Analysis Mirror Descent
School of Industrial Engineering, Purdue University, West Lafayette, IN 47907, USA. · Department of Mathematics and Institute of Operations Research and Analytics, National University of Singapore, Singapore 119076.
Incremental Learning in Mirror Flows
Jun 22, 2026Raphaël Berthier, Loucas Pillaud-VivienContinual Learning Mirror Descent
Sorbonne Université, Inria, Centre Inria de Sorbonne Université, Paris, France · CERMICS, CNRS, ENPC, Institut Polytechnique de Paris, Marne-la-Vallée, France
Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity
Jun 9, 2026Shira Vansover-Hager, Matan Schliserman, Ofir Schlisselberg +1Algorithmic Stability Mirror Descent
Blavatnik School of Computer Science and AI, Tel Aviv University · Google Research
DICE: Entropy-Regularized Equilibrium Selection for Stable Multi-Agent LLM Coordination
Jun 6, 2026Yi Xie, Zhanke Zhou, Chentao Cao +2Multi-Agent Coordination Game Theory
Department of Electrical & Computer Engineering University of Arizona Tucson, AZ 85721-0104, USA · Department of Computer Science Hong Kong Baptist University Kowloon Tong, Hong Kong SAR
Bregman meets Lévy: Stochastic mirror descent with heavy-tailed noise in continuous and discrete time
Jun 2, 2026Pierre-Louis Cauvin, Panayotis MertikopoulosStochastic Optimization Stochastic Differential Equations
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.
HORST: Composing Optimizer Geometries for Sparse Transformer Training
May 20, 2026Tom Jacobs, Rohan Jain, Rebekka BurkholzDeep Learning Optimization Transformer
CISPA Helmholtz Center for Information Security
$φ$ -Balancing for Mixture-of-Experts Training
May 14, 2026Lizhang Chen, Jonathan Li, Qi Wang +5Expert Load Balancing Mirror Descent
University of Texas at Austin · 2Northwestern University.
Concave Statistical Utility Maximization Bandits via Influence-Function Gradients
Apr 24, 2026Matías Carrasco, Alejandro CholaquidisMulti-Armed Bandits Mirror Descent
Universidad ORT Uruguay Montevideo, Uruguay · Facultad de Ciencias Universidad de la República Montevideo, Uruguay
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
Apr 17, 2026Côme Fiegel, Pierre Ménard, Tadashi Kozuno +2Nash Equilibrium Last-Iterate Convergence
ENSAE Paris - CREST, Palaiseau, France · Inria - FairPlay · ENS Lyon, Lyon, France +3
State-space models through the lens of ensemble control
Mar 13, 2026Ye Feng, Jianfeng LuMirror Descent Optimal Control
Basic Inequalities for First-Order Optimization with Applications to Statistical Risk Analysis
Dec 31, 2025Seunghoon Paik, Kangjie Zhou, Matus Telgarsky +1Early Stopping Gradient Descent
University of California, Berkeley · Columbia University · New York University
Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization
Apr 13, 2025Qiankun Shi, Han Yuan, Xiao Wang +1Zeroth-Order Optimization Augmented Lagrangian Method
Sun Yat-sen University, Guangzhou, 510006, China · Pengcheng Laboratory, Shenzhen, 518066, China · Sun Yat-sen University, Guangzhou, 518066, China +1
Block-Norm Geometries for Online Mirror Descent with Sparse Losses
Date pendingSwati Gupta, Jai Moondra, Mohit SinghOnline Convex Optimization Online Mirror Descent
MIT · CMU · Georgia Tech

Sep 30, 2026, quant-phJ/K move · Enter open · S save

Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games

Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong

Department of Computer Sciences, University of Wisconsin-Madison

Last-Iterate Convergence Oracle Complexity Zero-Sum Games Mirror Descent Nash Equilibrium Computation

Open paper AskPDF arXiv

Optimistic matrix mirror-prox (OMMP) computes

ε

-approximate Nash equilibria in quantum zero-sum games with an

O(1/\varepsilon)

average-iterate guarantee [arXiv:2311.10859]. We investigate whether this dependence on accuracy is tight and whether geometric last-iterate convergence can be guaranteed. We study these questions through explicit games with one qubit per player. First, we prove an

Ω(1/\varepsilon)

lower bound for the uniform-average output that includes the maximally mixed initial state, independently of the regularizer and step size. Second, we construct a fixed game on which optimistic gradient descent-ascent (OGDA), initialized at the maximally mixed state, has last-iterate Frobenius distance to equilibrium

Θ(1/t)

and duality gap

Θ(1/t^3)

for every sufficiently small fixed step size. A separate fixed game exhibits arbitrarily long delays in reducing the initial error by a constant factor across a family of initial states. Finally, we give a fixed game with a unique, strictly complementary equilibrium on which optimistic matrix multiplicative weights updates (OMMWU) converge only polynomially from the maximally mixed state for every fixed positive step size. The last-iterate Frobenius distance and quantum relative entropy from the equilibrium to the iterates decay as

Θ(1/t)

, while the duality gap decays as

Θ(1/t^2)

Momentum

Related topics

Latest papers 17