Accelerated Mirror Descent Method through Variable and Operator Splitting
Long Chen, Hao Luo, Jingrong Wei, Zeyi Xu, Yuan Yao · 2026
Read Accelerated Mirror Descent Method through Variable and Operator Splitting by Long Chen, Hao Luo, Jingrong Wei, Zeyi Xu, Yuan Yao (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-19038.txt.
Introduction
Long Chen and four co-authors speed up mirror descent, a method that bends downhill search around a space's shape. A mirror function encodes the shape and the limits of the space, which keeps steps valid while they converge. Speeded up forms of the method exist, drawn from a system of differential equations.
The team derives their version by splitting the work into a variable part and an operator part. Splitting lets each piece be handled by the tool that fits it best. The result is a faster method with the same kind of guarantees, aimed at large problems where shape and limits matter.
Catalog record
| CREATOR | Long Chen, Hao Luo, Jingrong Wei, Zeyi Xu, Yuan Yao |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-19038
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Accelerated Mirror Descent Method through Variable and Operator Splitting Thanks: Submitted to the editors DATE. Long Chen, Hao Luo, Jingrong Wei, Zeyi Xu, Yuan Yao Abstract Mirror descent uses the mirror function to encode geometry and constraints, improving convergence while preserving feasibility. Accelerated Mirror Descent Methods (Acc-MD) are derived from a discretization of an accelerated mirror ODE system using a variable–operator splitting framework. A geometric assumption, termed the Generalized Cauchy-Schwarz (GCS) condition, is introduced to quantify the compatibility between the objective and the mirror geometry, under which the first accelerated linear convergence for Acc-MD on a broad class of problems is established. Numerical experiments on smooth and composite optimization tasks demonstrate that Acc-MD exhibits superior stability and competitive acceleration compared to existing variants. keywords Accelerated Mirror Descent, Convex Optimization, Convergence Rate, Lyapunov Analysis Funding. † † runningheads: Accelerated Mirror Descent Methods / Accelerated Mirror Descent Methods MSC 90C25, 65K10, 37N40 1 Introduction Consider the unconstrained convex optimization problem \min_{x\in\mathbb{R}^{n}}f(x), where f is convex and differentiable. Mirror descent [ 25 ] updates as x_{k+1}=\arg\min_{x\in\mathbb{R}^{n}}\left\{\langle\nabla f(x_{k}),x\rangle+\frac{1}{\alpha_{k}}D_{\phi}(x,x_{k})\right\}, (1) where \alpha_{k}>0 is the step size, \phi is a smooth, strictly convex mirror function of Legendre type, and D_{\phi}(\cdot,\cdot) is the associated Bregman divergence. In [ 26 ] , Nesterov proposed an accelerated version that later inspired the mirror–prox method [ 24 ] . The mirror function encodes both geometry and constraints, with applications in imaging, phase transition, signal processing, and machine learning [ 27 , 6 , 15 , 21 , 2 , 19 ] . One use of mirror descent is as a nonlinear preconditioner. Relative smoothness is defined by D_{f}(x,y)\leq LD_{\phi}(x,y) . The Lipschitz constant of \nabla f is L_{f} . Mirror descent improves convergence when L\ll L_{f} , especially if L_{f}=\infty (i.e., when f is not smooth in the Euclidean sense). Another use of mirror descent is to impose constraints through the mirror function. For example, the entropic mirror descent method uses Shannon’s entropy \phi(x)=\sum_{i}x_{i}\log x_{i} , which ensures that x_{i} stay in the unit simplex. In [ 5 ] , mirror descent is seen as a nonlinear projected subgradient-type method for constrained optimization. While acceleration is well-understood in Euclidean spaces, extending it to general Bregman geometries remains challenging due to the lack of a natural coupling between the primal and dual metrics. Recently, acceleration has been studied by viewing optimization algorithms as discretizations of continuous-time ODE dynamics. Krichene, Bayen, and Bartlett [ 18 ] extended the ODE framework for Nesterov acceleration [ 30 ] to accelerated mirror descent, showing that suitable discretizations yield a \mathcal{O}(L_{f}/k^{2}) rate. Wibisono, Wilson, and Jordan [ 33 ] derived a Bregman Lagrangian that captures accelerated flows. Yuan and Zhang [ 35 ] developed high-resolution ODEs and recovered the optimal \mathcal{O}(L_{f}/k^{2}) rate for accelerated mirror descent methods in [ 26 ] . Also starting from Nesterov acceleration, Yu et al. [ 34 ] extended the method to work under generalized smoothness [ 20 ] and established the O(1/k^{2}) rate. Other variants are in [ 1 , 14 ] . However, these analyses [ 18 , 26 , 33 , 34 , 35 , 1 , 14 ] do not use relative smoothness, D_{f}(x,y)\leq LD_{\phi}(x,y) . Thus, convergence guarantees can be loose outside the Euclidean setting, especially when L is small but L_{f} is large or infinite. Birnbaum, Devanur, and Xiao [ 8 ] showed that mirror descent achieves a \mathcal{O}(L/k) rate under relative smoothness. For composite problems F(x)=f(x)+g(x) , where g is convex but possibly non-smooth, the Bregman Proximal Gradient (BPG) method [ 31 ] achieves a \mathcal{O}(L/k) rate; see also [ 3 , 22 , 36 ] . In [ 22 ] , Lu, Freund, and Nesterov introduced relative strong convexity, \mu D_{\phi}(x,y)\leq D_{f}(x,y) , and proved a linear convergence rate of 1-\mu/L for mirror descent. Later, Hanzely and Richtárik [ 17 ] extended the linear convergence to stochastic mirror descent . Without extra structure, mirror descent methods are limited to \mathcal{O}(1/k) complexity [ 13 ] . Extra conditions are needed for acceleration under relative smoothness. Under the gradient dominated condition and the \theta -uniform condition, the Bregman gradient method achieved linear convergence [ 4 ] . The Accelerated Bregman Proximal Gradient (ABPG) method [ 16 ] obtains a rate \mathcal{O}(L/k^{\gamma}) based on the triangle scaling exponent (TSE) \gamma\leq 2 . Full acceleration \mathcal{O}(L/k^{2}) requires \gamma=2 . Notably, no accelerated linear rate is known under relative strong convexity. Table 1 summarizes recent convergence results for mirror descent and accelerated mirror descent methods. Table 1 : Convergence rates of mirror descent and accelerated mirror descent methods. The mirror function \phi is assumed strongly convex and differentiable of Legendre type. Algorithm / Theory Assumptions Convergence rate Nesterov (2005) [ 26 ] Nemirovski (2005) [ 24 ] f : L_{f} -smooth \mathcal{O}(1/k) Krichene et. al. (2015) [ 18 ] Yuan and Zhang (2024) [ 35 ] f : L_{f} -smooth \mathcal{O}(L_{f}/k^{2}) Birnbaum et. al. (2011) [ 8 ] f : L -relative smooth \mathcal{O}(L/k) Hanzely et. al. (2021) [ 16 ] triangle scaling exponent \gamma\leq 2 f : L -relative smooth \mathcal{O}(L/k^{\gamma}) Lu et. al. (2018) [ 22 ] Teboulle (2018) [ 31 ] f : \mu -relative convex, L -relative smooth \mathcal{O}\!\big((1-\mu/L)^{k}\big) ( New ) Algorithm 1 , 2 Theorem 6 f : \mu -relative convex, L -relative smooth generalized Cauchy-Schwarz ( A2 ) \mathcal{O}\!\big((1+\sqrt{\mu/C_{f,\phi}})^{-k}\big) ( New ) Algorithm 4 Theorem 16 f : L -relative smooth, generalized Cauchy-Schwarz ( A2 ) \mathcal{O}(C_{f,\phi}/k^{2}) In this work, we develop accelerated mirror descent methods. Using the variable and operator splitting (VOS) framework from [ 10 ] , we propose a new accelerated mirror descent (Acc-MD) flow: \left\{\begin{aligned} x^{\prime}&=y-x,\\ \left(\nabla\phi(y)\right)^{\prime}&=-\mu^{-1}\nabla f(x)+\nabla\phi(x)-\nabla\phi(y),\end{aligned}\right. (2) with x(0)=x_{0} and y(0)=y_{0} . The variable is split into x and y . At equilibrium, y^{\star}=x^{\star} and \nabla f(x^{\star})=0 . The variable y allows operator splitting \nabla f(x) and \nabla\phi(y) . From discretizations of ( 2 ), we design Acc-MD methods: algorithm 1 and algorithm 2 . We introduce a new assumption ( A2 ), a generalized Cauchy-Schwarz (GCS) inequality with constant C_{f,\phi} . Based on GCS, We establish the first accelerated linear convergence result for mirror descent, with rate (1+\sqrt{\mu/C_{f,\phi}})^{-1} . We show cases where GCS ( A2 ) holds and C_{f,\phi} is explicit. As seen in Figure 1 (Section 4.4 ), GCS covers important geometries, such as Example 9 , where ABPG [ 16 ] based on TSE fails to accelerate. We do not claim GCS is more general than TSE, or that Acc-MD is always better than ABPG. Instead, they address different structure regimes . See Section 4.4 for discussion. For the convex case \mu=0 , we use a perturbation-homotopy argument [ 10 ] to derive the optimal accelerated rate \mathcal{O}(C_{f,\phi}/k^{2}) under GCS. For composite problems \min_{x}f(x)+g(x) , our method leads to a Bregman proximal gradient variant that handles non-smooth g using variable splitting in the gradient term. We test the Acc-MD methods on smooth, non-smooth, and constrained convex problems. Results show benefits over existing mirror descent methods. The paper is organized as follows. Section 2 gives preliminaries. Section 3 reviews mirror descent and gives a proof for linear convergence in relative strongly convex cases. Section 4 introduces the Acc-MD flow and proves accelerated