Mirror Descent Under Generalized Smoothness

Smoothness is crucial for attaining fast rates in first-order optimization. However, many optimization problems in modern machine learning involve non-smooth objectives. Recent studies relax the smoothness assumption by allowing the Lipschitz constant of the gradient to grow with respect to the gradient norm, which accommodates a broad range of objectives in practice. Despite this progress, existing generalizations of smoothness are restricted to Euclidean geometry with $\ell_2$-norm and only have theoretical guarantees for optimization in the Euclidean space. In this paper, we address this limitation by introducing a new $\ell*$-smoothness concept that measures the norm of Hessians in terms of a general norm and its dual, and establish convergence for mirror-descent-type algorithms, matching the rates under the classic smoothness. Notably, we propose a generalized self-bounding property that facilitates bounding the gradients via controlling suboptimality gaps, serving as a principal component for convergence analysis. Beyond deterministic optimization, we establish sharp convergence for stochastic mirror descent, matching state-of-the-art under classic smoothness. Our theory also extends to non-convex and composite optimization, which may shed light on practical usages of mirror descent, including pre-training and post-training of LLMs.

How can we analyze optimization methods when the problem’s natural geometry is not Euclidean? Mirror descent is a classical method designed for such settings: instead of moving according to ordinary Euclidean distance, it adapts its updates to the geometry of the problem. This flexibility makes mirror descent useful in many areas of machine learning. At the same time, modern machine learning objectives often do not satisfy classical smoothness assumptions. Recent generalized smoothness theories address this issue, but they mainly apply to Euclidean gradient descent. As a result, there has been a gap between geometry-aware algorithms and generalized smoothness theory. Our paper bridges this gap. We introduce ℓ∗-smoothness, a generalized smoothness notion compatible with non-Euclidean geometries, and prove that mirror descent and several variants retain their standard convergence rates under this broader condition. Our results provide a unified theoretical basis for geometry-aware optimization under realistic smoothness assumptions, with supporting evidence from LLMs and CNNs.