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

Sep 30, 2026quant-ph

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

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)

.

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

Sep 25, 2026cs.LG

Averaged Mirror Descent and Dual Gradient Methods: Convergent Algorithms for Entropic Gromov-Wasserstein Problems

The Gromov-Wasserstein (GW) distance measures the discrepancy between metric measure (mm) spaces and identifies optimal alignments between them based solely on their intrinsic structure. Since it identifies isomorphic mm spaces, it provides a natural notion of distance for heterogeneous datasets which may admit isomorphic representations. In order to accelerate computation of GW distances, many practitioners employ entropic regularization to obtain an Entropic GW (EGW) problem. The most popular EGW solver is the Mirror Descent (MD) algorithm, which reduces EGW computations to an iterative process where an entropic optimal transport (EOT) problem is solved at each iteration. Despite its widespread use, the convergence of MD for this problem has only been established for restricted classes of costs. On the other hand, a recently proposed dual gradient method is available for general costs, but requires a choice of step size which depends on the regularization parameter. To address these two issues, we introduce Averaged Mirror Descent (AMD), which averages consecutive MD steps, and prove its convergence for arbitrary costs. Then, we establish that the dual gradient method with a fixed step size also converges for arbitrary costs at the cost of a more complicated iteration. In both cases, we also account for inexact iterations which are inescapable in practice. We compare the empirical performance of these methods across various settings and, in particular, show that AMD and the dual gradient method both converge on an example where classical MD fails.

Joanna Marks, Gabriel Rioux, Riccardo Passeggeri

⋆Denotes equal contribution to this work.

Gradient Descent Mirror Descent Optimal Transport Wasserstein Distance

Sep 1, 2026cs.GT

Independent Reinforcement Learning in Discounted Markov Games

In this work, we study radically uncoupled learning in discounted general-sum Markov games. Assuming ``

\mathsf{ETH}

for

\mathsf{PPAD}

", we show that, for every fixed discount factor, there is no polynomial-time algorithm for computing inverse-polynomially accurate coarse correlated equilibria in discounted general-sum Markov games when players learn independently in decentralized settings. Complementing this hardness result, we provide what appears to be the first \emph{radically uncoupled} algorithm with sub-exponential convergence guarantees to coarse correlated equilibria in discounted general-sum Markov games without imposing any structural restrictions on the game. Our algorithm is a \emph{layered} variant of optimistic mirror descent with an increasing step-size schedule tailored to the multi-agent setting. Finally, we develop both full-feedback and partial feedback versions of the aforementioned algorithm and establish sub-exponential convergence guarantees for each case.

Asrin Efe Yorulmaz, Ugur Aydin, Tamer Basar

Department of Electrical and Computer Engineering, University of Illinois Urbana-Champaign, Urbana, IL, 61801, USA

Reinforcement Learning Game Theory Decentralized Learning Mirror Descent Decentralized MARL

Aug 7, 2026math.OC

Establishing Boundary KKT Convergence of Mirror Descent through Reparameterization

Sequence convergence to a boundary Karush--Kuhn--Tucker (KKT) point has long remained unclear for nonconvex mirror descent with Legendre kernels. The difficulty arises from the blow-up of the gradient of the Legendre kernel at the boundary. Recent work~\cite{dingtoh2026nonkkt} shows that mirror descent can accumulate at non-KKT boundary points despite decreasing objective values, precluding a convergence guarantee to KKT points in general. Despite this negative result, mirror descent remains effective in many real applications. Motivated by this contrast, we address the boundary difficulty directly and establish KKT convergence of mirror descent for a broad class of structured nonconvex problems. We analyze mirror descent in reparameterized variables, where the Hessian metric is flattened and remains nondegenerate as the boundary is approached. Under extension and definability conditions jointly coupling the objective, the Legendre kernel, and the feasible region, the reparameterized sequence has finite length and converges, thereby recovering convergence to a KKT point of the original sequence. Our general framework applies to some concrete instances: Shannon entropy, Fermi--Dirac entropy, and power kernels on polyhedron.

Kuangyu Ding, Kim-Chuan Toh

School of Industrial Engineering, Purdue University, West Lafayette, IN 47907, USA. · Department of Mathematics, National University of Singapore, Singapore 119076.

Nonconvex Optimization Mirror Descent

Aug 3, 2026math.OC

Non-KKT Accumulation in Entropic Mirror Descent

For mirror descent generated by a Legendre kernel, perhaps one of the most basic question in optimization is this: must every accumulation point of a bounded mirror descent sequence be Karush--Kuhn--Tucker (KKT) stationary under proper stepsizes? We show that the answer is no. A longstanding obstacle to resolving this question is the boundary blow-up of the Legendre gradient: it keeps every mirror step in the interior, while at a boundary limit, the inverse entropy metric vanishes on active coordinates and can erase the dual-feasibility in the KKT system. We construct

C^\infty

objectives and bounded sequences generated by the Shannon-entropic mirror descent on the nonnegative orthant

\R_+^n

, for every

n\geq 3

, and on the probability simplex

Δ_n

, for every

n\geq 4

, such that, in each case, the set of accumulation points is a smooth boundary circle containing a nonempty relatively open arc of non-KKT points. The steps satisfy

α_k\asymp k^{-β}

with

β\in(1/2,1)

, the objective values are nonincreasing, and the objectives are entropy-relatively smooth. Hence the pathology stems from the degeneracy of the Bregman geometry at the boundary, rather than from failure of descent, or improper stepsizes. To the best of our knowledge, these provide the first counterexamples to KKT accumulation for bounded mirror descent sequences with nonincreasing objective values.

Kuangyu Ding, Kim-Chuan Toh

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.

Optimization Convergence Analysis Mirror Descent

Jun 22, 2026math.OC

Incremental Learning in Mirror Flows

We study mirror flows generated by a convex quadratic loss and a general convex lower semicontinuous mirror potential. We show that, when initialized near the boundary of the domain of the mirror potential, their rescaled trajectories converge to a limiting mirror flow whose potential is the indicator function of the domain. In this limit, the primal variable minimizes the loss over a time-dependent hypothesis set: the subdifferential of the support function of the domain, evaluated at the dual variable. This characterization provides a general mechanism for incremental learning in mirror flows.

Raphaël Berthier, Loucas Pillaud-Vivien

Sorbonne Université, Inria, Centre Inria de Sorbonne Université, Paris, France · CERMICS, CNRS, ENPC, Institut Polytechnique de Paris, Marne-la-Vallée, France

Continual Learning Mirror Descent Incremental Learning

Jun 9, 2026cs.LG

Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity

Mirror Descent (MD) extends Gradient Descent (GD) beyond Euclidean geometry and has recently reappeared as a lens for KL-regularized policy optimization in reinforcement learning and LLM post-training. This raises a basic robustness question, crucial to reproducibility and reliability: how sensitive are MD dynamics to their inputs? We focus on initialization, often itself a pretrained or previously aligned model. Quadratic-regularized MD, including GD and Mahalanobis geometries, is well-known to be stable for convex smooth objectives. We show a sharp contrast: once the regularizer is non-quadratic, MD can be exponentially more sensitive to initialization than GD, even with a well-conditioned regularizer in Euclidean norm. We give a three-dimensional construction with a convex, smooth objective and a strongly convex, smooth, well-conditioned regularizer where an initial

\varepsilon

perturbation is quickly amplified to

\min\{\text{polylog}^{-1}(1/\varepsilon), \varepsilon e^{Ω(ηT)}\}

after

T

iterations of MD with step size

η

. For canonical KL-regularized MD on the simplex, we show that even linear objectives can amplify an initial

\varepsilon

perturbation exponentially fast in high-dimensional or near-boundary regimes. Finally, we show that adding a Bregman regularization term toward an anchor point can stabilize the dynamics while largely preserving the optimization guarantees, and that the choice of anchor is crucial: anchoring at the initialization only partially mitigates the instability, whereas anchoring at a fixed point yields a more stable mechanism.

Shira Vansover-Hager, Matan Schliserman, Ofir Schlisselberg +1

Blavatnik School of Computer Science and AI, Tel Aviv University · Google Research

Algorithmic Stability Mirror Descent Gradient Descent Dynamics

Jun 6, 2026cs.LG

DICE: Entropy-Regularized Equilibrium Selection for Stable Multi-Agent LLM Coordination

Multi-agent large language model (LLM) systems often fail to reliably outperform a single strong model equipped with best-of-N sampling. We argue that a core source of this instability is ill-posed equilibrium selection: current systems specify what information agents share, but not which coordination convention should be selected. We formalize a broad class of such systems as discounted incomplete-information Markov games and show that two common pathologies, oscillation between competing conventions and drift across them, can both induce unstable learning and linear Bayesian regret. To obtain a well-posed target, we introduce the Heterogeneous Quantal Response Equilibrium (HQRE), an entropy-regularized equilibrium concept with agent- and state-dependent temperatures. Under a monotonicity condition, HQRE is unique, admits linearly convergent mirror updates, and yields bounded Bayesian regret; the same condition yields rollout-measurable stability diagnostics. We instantiate this objective in two algorithms: DICE-PC, which coordinates frozen models through prompt-control actions, and DICE-FT, which performs parameter-efficient mirror fine-tuning. Across eleven benchmarks in four domains, DICE improves accuracy-cost trade-offs over strong within-class baselines; on reasoning and planning tasks, DICE-PC improves by 4.3 percentage points on average and DICE-FT by 8.5 points.

Yi Xie, Zhanke Zhou, Chentao Cao +2

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

Multi-Agent Coordination Game Theory Mirror Descent Multi-Agent LLMs

Jun 2, 2026math.OC

Bregman meets Lévy: Stochastic mirror descent with heavy-tailed noise in continuous and discrete time

We study the robustness of stochastic mirror descent (SMD) under heavy-tailed noise, focusing on whether the method retains its convergence guarantees when run with infinite-variance stochastic gradient input. To address this question in a principled manner, we begin by introducing a continuous-time model of SMD as a stochastic differential equation (SDE) driven by a centered Lévy noise process with finite

p

-th order moments,

1 < p \leq 2

. This scheme -- which we call the Lévy mirror flow (LMF) -- arises naturally as the scaling limit of SMD in the presence of heavy-tailed noise. In particular, when

p < 2

-- the heavy noise regime -- the trajectories of LMF generically exhibit jump discontinuities of arbitrary magnitude which, if frequent enough, lead to infinite variance. Nonetheless, despite this highly singular behavior, we show that LMF attains

ε

-optimality within

\mathcal{O}(ε^{-p/(p-1)})

time in the convex case, and within

\mathcal{\tilde O}(ε^{-1/(p-1)})

time for (relatively) strongly convex objectives. These guarantees provide a transparent characterization of the impact of frequent long jumps on the convergence of the process, and percolate to a series of matching discrete-time guarantees for several variants of SMD under heavy-tailed noise.

Pierre-Louis Cauvin, Panayotis Mertikopoulos

Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.

Stochastic Optimization Stochastic Differential Equations Heavy-Tailed Noise Mirror Descent Stochastic Optimization Convergence Heavy-Tailed Distributions+1

May 20, 2026cs.LG

HORST: Composing Optimizer Geometries for Sparse Transformer Training

Sparsifying transformers remains a fundamental challenge, as standard optimizers fail to simultaneously encourage sparsity and maintain training stability. Effective adaptive optimizers exhibit an implicit

L_{\infty}

bias favoring stability, yet, sparsity requires an

L_1

bias. To integrate sparsity, we propose a composition of optimizer steps, which we cast as non-commutative operators to analyze and combine their optimization geometry in a principled way. This yields HORST (Hyperbolic Operator for Robust Sparse Training), a modular optimizer that inherits stability from adaptive methods while inducing

L_1

sparsity bias through a hyperbolic mirror map. Our experiments demonstrate its utility for sparse training of transformers on both vision and language tasks. HORST consistently and significantly outperforms AdamW baselines across all sparsity levels, with large gains at higher sparsity.

Tom Jacobs, Rohan Jain, Rebekka Burkholz

CISPA Helmholtz Center for Information Security

Deep Learning Optimization Transformer Neural Network Optimization Mirror Descent Sparse Neural Networks

May 14, 2026cs.LG

$φ$ -Balancing for Mixture-of-Experts Training

Mixture-of-Experts (MoE) models rely on balanced expert utilization to fully realize their scalability. However, existing load-balancing methods are largely heuristic and operate on noisy mini-batch assignment statistics, introducing bias relative to population-level objectives. We propose

φ

-balancing, a principled framework that directly targets population-level expert balance by minimizing a strictly convex, symmetric, and differentiable potential of the expected routing distribution. Using convex duality, we derive an equivalent min-max formulation and obtain a simple online algorithm via mirror descent, yielding an efficient EMA-based routing adjustment with negligible overhead. Across large-scale pretraining and downstream fine-tuning,

φ

-balancing consistently outperforms prior Switch-style and loss-free baselines, demonstrating more stable and effective expert utilization.

Lizhang Chen, Jonathan Li, Qi Wang +5

University of Texas at Austin · 2Northwestern University.

Expert Load Balancing Mirror Descent Mixture-of-Experts Models

Apr 24, 2026stat.ML

Concave Statistical Utility Maximization Bandits via Influence-Function Gradients

We study stochastic multi-armed bandits in which the objective is a statistical functional of the long-run reward distribution, rather than expected reward alone. Under mild continuity assumptions, we show that the infinite-horizon problem reduces to optimizing over stationary mixed policies: each weight vector

w

on the simplex induces a mixture law

P^w

, and performance is measured by the concave utility

U(w)=\mathfrak U(P^w)

. For differentiable statistical utilities, we use influence-function calculus to derive stochastic gradient estimators from bandit feedback. This leads to an entropic mirror-ascent algorithm on a truncated simplex, implemented through multiplicative-weights updates and plug-in estimates of the influence function. We establish regret bounds that separate the mirror-ascent optimization error from the bias caused by estimating the influence function. The framework is developed for general concave distributional utilities and illustrated through variance and Wasserstein objectives, with numerical experiments comparing exact and plug-in influence-function implementations.

Matías Carrasco, Alejandro Cholaquidis

Universidad ORT Uruguay Montevideo, Uruguay · Facultad de Ciencias Universidad de la República Montevideo, Uruguay

Multi-Armed Bandits Mirror Descent

Apr 17, 2026cs.LG

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback

We study the problem of learning in zero-sum matrix games with repeated play and bandit feedback. Specifically, we focus on developing uncoupled algorithms that guarantee, without communication between players, the convergence of the last-iterate to a Nash equilibrium. Although the non-bandit case has been studied extensively, this setting has only been explored recently, with a bound of

\mathcal{O}(T^{-1/8})

on the exploitability gap. We show that, for uncoupled algorithms, guaranteeing convergence of the policy profiles to a Nash equilibrium is detrimental to the performance, with the best attainable rate being

Ω(T^{-1/4})

in contrast to the usual

Ω(T^{-1/2})

rate for convergence of the average iterates. We then propose two algorithms that achieve this optimal rate up to constant and logarithmic factors. The first algorithm leverages a straightforward trade-off between exploration and exploitation, while the second employs a regularization technique based on a two-step mirror descent approach.

Côme Fiegel, Pierre Ménard, Tadashi Kozuno +2

ENSAE Paris - CREST, Palaiseau, France · Inria - FairPlay · ENS Lyon, Lyon, France +3

Nash Equilibrium Last-Iterate Convergence Game Theory Zero-Sum Games Convergence Analysis Mirror Descent+1

Mar 13, 2026math.OC

State-space models through the lens of ensemble control

State-space models (SSMs) are effective architectures for sequential modeling, but a rigorous theoretical understanding of their training dynamics is still lacking. We formulate continuous-time SSM parameter-path optimization as an ensemble optimal control problem: each input sequence generates a corresponding state trajectory in the ensemble, while the trainable parameter path forms a common control shared by all trajectories. Within this formulation, model evaluation is represented by the forward state equation and backward sensitivity propagation by the corresponding adjoint equation. We show that the Hamiltonian gradient with respect to the control variable represents the negative first-variation density of the reduced ensemble objective. Using this representation, we analyze a Bregman mirror-descent scheme for the continuous-time ensemble objective; in Euclidean geometry this reduces to functional projected gradient descent. State-adjoint and Hamiltonian-gradient stability yield two-sided relative curvature of the reduced objective and relative convexity under sufficient regularization. We further show that in the relatively convex regime the optimal-control problem admits a minimizer, which is unique under relative strong convexity. For SSMs, the explicit stability-generated defect

κ_{\mathrm{stab}}^{\mathrm{SSM}}

gives an

O(1/k)

objective rate at

τ=κ_{\mathrm{stab}}^{\mathrm{SSM}}

and geometric convergence to the unique minimizer for

τ>κ_{\mathrm{stab}}^{\mathrm{SSM}}

, under the stated stepsize condition.

Ye Feng, Jianfeng Lu

Mirror Descent Optimal Control State Space Models

Dec 31, 2025math.ST

Basic Inequalities for First-Order Optimization with Applications to Statistical Risk Analysis

In this work, we introduce

\textit{basic inequalities}

for first-order iterative optimization algorithms, forming a simple yet versatile framework which connects implicit and explicit regularization. Building on related comparison inequalities for optimization iterates that already exist in the literature, we extend and unify these arguments to produce a general framework, which can be used as a tool for statistical analysis. In more detail, let

f

denote the objective function to be optimized. Given a first-order iterative algorithm initialized at

θ_0

, with current iterate

θ_T

, the basic inequality upper bounds

f(θ_T) - f(z)

for any reference point

z

in terms of the accumulated step sizes, and the distances between

θ_0

,

θ_T

, and

z

. These distances are measured in a geometry inherent to the optimization algorithm, which then translates into a notion of regularization being applied across the path of iterates. In addition to refining existing results on gradient descent, we provide new results for mirror descent and other first-order methods. We then show how to use these basic inequalities to derive elementary yet useful bounds on the prediction risk of early-stopped gradient descent and exponentiated gradient descent iterates in generalized linear models. We also supplement these findings with numerical experiments.

Seunghoon Paik, Kangjie Zhou, Matus Telgarsky +1

University of California, Berkeley · Columbia University · New York University

Early Stopping Gradient Descent Mirror Descent Generalized Linear Models Implicit Regularization

Apr 13, 2025math.OC

Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization

In this paper, we study nonconvex constrained stochastic zeroth-order optimization problems with exact constraints and stochastic objective evaluations. To solve this class of problems, we propose a framework of mirror descent linearized augmented Lagrangian methods that employs two-point stochastic zeroth-order gradient estimators and exploits non-Euclidean mirror descent geometry. Under mild assumptions, we establish oracle complexity guarantees for finding an

ε

-KKT point parameterized by

p \geq 2

. Under Rademacher smoothing, our analysis reveals a trade-off between the variance of the zeroth-order gradient estimators and the smoothness of the mirror map. In the high-accuracy regime, the resulting effective oracle complexity is

\mathcal{O}(p d^{2/p}ε^{-3})

for

p \in [2,2\ln d]

and

\mathcal{O}(\ln d\,ε^{-3})

for

p > 2\ln d

. These bounds reduce the dimension dependence in the leading term. When

p=2

, our method recovers the Euclidean setting with an oracle complexity of

\mathcal{O}(dε^{-3})

, improving the

ε

-dependence over existing methods. Furthermore, to eliminate initial near-feasibility requirements, we introduce a multi-stage scheme that finds an

ε

-KKT point within

\mathcal{O}(1+\log\log(e/ε))

stages while maintaining the leading-order complexity. Numerical tests on QCQPs, black-box adversarial attacks, and fairness-constrained classification demonstrate the effectiveness of our proposed method.

Qiankun Shi, Han Yuan, Xiao Wang +1

Sun Yat-sen University, Guangzhou, 510006, China · Pengcheng Laboratory, Shenzhen, 518066, China · Sun Yat-sen University, Guangzhou, 518066, China +1

Zeroth-Order Optimization Augmented Lagrangian Method Mirror Descent Constrained Optimization

Date pendingmath.OC

Block-Norm Geometries for Online Mirror Descent with Sparse Losses

The performance of online mirror descent depends critically on the geometry induced by its mirror map, yet standard algorithms largely rely on two canonical choices: Euclidean and entropic geometry. We show that these two geometries can both be substantially suboptimal when loss gradients are sparse. We introduce a family of randomized block-norm mirror maps that interpolates between Euclidean and entropic geometries and adapts to intermediate sparsity structure. For several standard convex sets, including

\ell_p

balls, ellipsoids, boxes, and Minkowski sums of norm balls, we prove polynomial-in-dimension improvements in regret bounds over the better of online projected gradient descent and exponentiated gradient. We further construct explicit online convex optimization instances for which these improvements are realized: on a simple polytope, an intermediate block geometry achieves a

\text{poly}(d)

separation in regret from both Euclidean and entropic geometries in dimension

d

, while on the probability simplex we obtain a separation of order

\Omega(\sqrt{\log d}/\log\log d)

. Finally, we study geometry selection when sparsity is unknown. We show that naively alternating between mirror maps can incur linear regret, even though either mirror map alone has sublinear regret, and give a Hedge meta-algorithm that competes with the best mirror map in a finite portfolio. For random block geometries, this yields regret within an

O(\sqrt{\log\log d})

factor of the best random uniform block norm chosen in hindsight.

Swati Gupta, Jai Moondra, Mohit Singh

MIT · CMU · Georgia Tech

Online Convex Optimization Online Mirror Descent Mirror Descent