math.OCMar 17, 2026

Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioning

Authors: Junwen Qiu, Leilei Mei, Junyu Zhang

Organizations: Industrial Systems Engineering and Management, National University of Singapore

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

The global Lipschitz smoothness condition underlies most convergence and complexity analyses via two key consequences: the descent lemma and the gradient Lipschitz continuity. How to study the performance of optimization algorithms in the absence of Lipschitz smoothness remains an active area. The relative smoothness framework from Bauschke-Bolte-Teboulle (2017) and Lu-Freund-Nesterov (2018) provides an extended descent lemma, ensuring convergence of Bregman-based proximal gradient methods and their vanilla stochastic counterparts. However, many widely used techniques (e.g., momentum schemes, random reshuffling, and variance reduction) additionally require the Lipschitz-type bound for gradient deviations, leaving their analysis under relative smoothness an open area. To resolve this issue, we introduce the dual kernel conditioning (DKC) regularity condition to regulate the local relative curvature of the kernel functions. Combined with the relative smoothness, DKC provides a dual Lipschitz continuity for gradients: even though the gradient mapping is not Lipschitz in the primal space, it preserves Lipschitz continuity in the dual space induced by a mirror map. We verify that DKC is widely satisfied by popular kernels and is closed under affine composition and conic combination. With these novel tools, we establish the first complexity bounds as well as the iterate convergence of random reshuffling mirror descent for constrained nonconvex relative smooth problems.

Figures & tables

Figure 1: The first illustrates the dual space interpretation of mirror descent. The second illustrates the construction of the integration path z(t)z(t) in Lemmas 2.6 and 2.8 , by mapping the line segment between ∇h(x)\nabla h(x) and ∇h(y)\nabla h(y) back to the primal space. The third illustrates ∇h∗(B)\nabla h^{*}(\mathcal{B}) under quartic power kernel, where B\mathcal{B} is a ball in the dual space. This shows that when ∇h(X)\nabla h(\mathcal{X}) is convex in dual space, X\mathcal{X} may not necessarily be convex in primal space.
 xk,i+1∈arg min⁡u∈Z{⟨u,∇fπik(xk,i)⟩+1αkDh(u,xk,i)}x^{k,i+1}\in\argmin_{u\in\mathcal{Z}}\left\{\langle u,\nabla f_{\pi^{k}_{i}}(x^{k,i})\rangle+\frac{1}{\alpha_{k}}\mathcal{D}_{h}(u,x^{k,i})\right\} (11)
Algorithm 1 Random Reshuffling Mirror Descent (RRMD)
Figure 2: Numerical results on phase retrieval problem. Performance over five independent run.
Figure 3: Numerical results on Poisson inverse problem. Performance over five independent run.
More in this topic

Random Reshuffling

See all 11 papers

Explore similar work

CardsList
Aug 7, 2026

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 OptimizationMirror Descent
AskPDF
Jun 30, 2026

Random Reshuffling Dominates Stochastic Gradient Descent

Stochastic Gradient Descent (SGD\textsf{SGD}) is one of the most classical optimization algorithms with favorable theoretical guarantees, yet the practical implementation of SGD\textsf{SGD} differs subtly from its well-known form and is often referred to as Shuffling Stochastic Gradient Descent (Shuffling SGD\textsf{Shuffling SGD}). A particularly popular strategy in Shuffling SGD\textsf{Shuffling SGD} is Random Reshuffling (RR\textsf{RR}), which has achieved great empirical success across numerous experiments. Despite its strong performance, RR\textsf{RR} has long been considered a heuristic due to a lack of theoretical support. Over the last decade, people have finally established provable convergence rates for RR\textsf{RR}, thus justifying its observed superiority. However, for smooth convex optimization, two clouds over the convergence theory of RR\textsf{RR} remain to this day. More precisely, according to the current theory, Shuffling SGD\textsf{Shuffling SGD} under RR\textsf{RR} converges only when the stepsize is smaller than a threshold proportional to 1/n1/n, where nn is the number of summands in the objective (or the number of data points). Consequently, the optimally tuned theoretical rate of Shuffling SGD\textsf{Shuffling SGD} under RR\textsf{RR} is strictly worse than that of SGD\textsf{SGD} when the number of epochs is smaller than another threshold proportional to nn. These two restrictions heavily limit the applicability of existing theories and leave a critical mismatch with practice. In this work, for the first time, we prove that RR\textsf{RR} dominates SGD\textsf{SGD} in smooth convex optimization under any reasonable stepsize after any finite number of epochs, thereby addressing a longstanding open question.

Zijian Liu

Stern School of Business, New York University

Stochastic Optimization ConvergenceRandom ReshufflingStochastic Gradient Descent
AskPDF
Aug 24, 2026

Mirror descent algorithms with logarithmic barriers

This work derives convergence guarantees for mirror descent and proximal mirror descent algorithms when a logarithmic barrier is used as a distance-generating function. Standard approaches cannot be applied when the solution lies on the boundary, where the Bregman divergence blows up. We show that, in a specific setting, both methods enjoy an O(log⁡k/k)O(\log k / k) rate, which is also tight. In addition, our contributions include: (i) a new technique for handling the blow-up; (ii) a resolution of a gap in the theory of relative smoothness; and (iii) a comparison of the proposed approach with interior-point methods.

Alberto De Marchi, Yura Malitsky, Adrien B. Taylor

University of the Bundeswehr Munich, Germany. · Faculty of Mathematics, University of Vienna, Austria. · Inria, DI ENS, CNRS, PSL Research University, France.

Mirror Descent
AskPDF