Mirror descent algorithms with logarithmic barriers

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.

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.

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.