Group Entropies and Mirror Duality: A Class of Flexible Mirror Descent Updates for Machine Learning

Andrzej Cichocki; Piergiulio Tempesta

cs.LGMar 9, 2026

Group Entropies and Mirror Duality: A Class of Flexible Mirror Descent Updates for Machine Learning

Authors: Andrzej Cichocki, Piergiulio Tempesta

Abstract

We introduce a comprehensive theoretical and algorithmic framework that bridges formal group theory and group entropies with modern machine learning, paving the way for an infinite, flexible family of Mirror Descent (MD) optimization algorithms. Our approach exploits the rich structure of group entropies, which are generalized entropic functionals governed by group composition laws, encompassing and significantly extending all trace-form entropies such as the Shannon, Tsallis, and Kaniadakis families. By leveraging group-theoretical mirror maps (or link functions) in MD, expressed via multi-parametric generalized logarithms and their inverses (group exponentials), we achieve highly flexible and adaptable MD updates that can be tailored to diverse data geometries and statistical distributions. To this end, we introduce the notion of mirror duality, which allows us to seamlessly switch or interchange group-theoretical link functions with their inverses, subject to specific learning rate constraints. By tuning or learning the hyperparameters of the group logarithms enables us to adapt the model to the statistical properties of the training distribution, while simultaneously ensuring desirable convergence characteristics via fine-tuning. This generality not only provides greater flexibility and improved convergence properties, but also opens new perspectives for applications in machine learning and deep learning by expanding the design of regularizers and natural gradient algorithms. We extensively evaluate the validity, robustness, and performance of the proposed updates on large-scale, simplex-constrained quadratic programming problems.

Figures & tables

Algorithm	$n=10^{3}$	$n=10^{4}$	$n=5\times 10^{4}$	Scaling
DMD ( $q=0.25$ )	$124\pm 22$	$136\pm 9$	$148\pm 7$	Near-constant
GEG ( $q=0.25$ )	$458\pm 102$	$503\pm 61$	$542\pm 44$	Near-constant
EG ( $q=1.0$ )	$>5000$	$>5000$	$>5000$	Stalled

Table 1. Iterations to convergence (

\delta_{t}=g_{\mathrm{FW}}(\textbf{{w}}_{t})/g_{\mathrm{FW}}(\textbf{{w}}_{0})\leq 10^{-4}

) across problem scales (

K=0.1n

\kappa=10^{3}

). Values are reported as mean

\pm

std over multiple independent runs.

Panel of Figure 1 — Figure 1. Relative primal gap (left column) and relative Frank–Wolfe duality gap (right column) versus iteration for EG, GEG, and DMD. Benchmarks are matrix-free SCQP instances with spectral normalization ( $\|\bm{Q}\|_{2}=1$ ) and condition number $\kappa=1\,000$ . The sparsity pattern is planted with $K=0.1n$ nonzero entries and the iteration budget is $T_{\max}=200$ . DMD (green) descends rapidly, reaching gaps orders of magnitude below those of EG (blue), which plateaus due to its inability to drive inactive weights to zero. Shaded regions indicate pointwise 95% confidence intervals across runs (mean $\pm 1.96\,\mathrm{SE}$ ).

Panel of Figure 2 — Figure 2. Support recovery: Jaccard index (IoU) versus iteration for varying sparsity levels $K\in\{100,300,500,700\}$ with $n=1\,000$ , $\kappa=1\,000$ , $\mathrm{SNR}=20$ dB. DMD behaves as a step-function classifier, attaining $\mathrm{IoU}=1.0$ within 2–15 iterations. EG consistently falls short of $\mathrm{IoU}\geq 0.9$ because it assigns small nonzero probabilities to inactive elements instead of eliminating them.

Algorithm	$K$	Final IoU	Iter to IoU $\geq 0.9$
DMD	100	$1.000\pm 0.000$	$6.3\pm 0.8$
EG	100	$0.588\pm 0.033$	$100.0\pm 0.0$
GEG	100	$1.000\pm 0.000$	$26.9\pm 3.8$
DMD	300	$1.000\pm 0.000$	$3.4\pm 0.5$
EG	300	$0.644\pm 0.019$	$100.0\pm 0.0$
GEG	300	$1.000\pm 0.000$	$14.6\pm 1.0$

Table 2. Support recovery statistics (

n=1\,000

\kappa=1\,000

\mathrm{SNR}=20

dB, 20 runs). “Final IoU” is measured at the last iteration; “Iter to IoU

\geq 0.9

” is the first iteration achieving that threshold (mean

\pm

std). DMD attains perfect recovery in fewer than 10 iterations on average, whereas EG fails to converge to the correct support within the 100-iteration budget.

Figure 3. Trajectory of support recovery (IoU) versus the relative FW duality gap (log scale). The vertical cliff for DMD and GEG indicates that these algorithms identify the correct sparsity structure ( $\mathrm{IoU}=1.0$ ) while the duality gap is still relatively large ( ${\sim}\,10^{-3}$ ), well before reaching high numerical precision.

Figure 4. Noise robustness: final relative FW duality gap after $T_{\max}=100$ iterations versus $\mathrm{SNR}$ (dB), averaged over 50 independent noise realizations with dispersion bands. Setup: $n=2\,000$ , $K=200$ , $\kappa=1\,000$ . DMD and GEG sustain low duality gaps for $\mathrm{SNR}>5$ dB, confirming the noise-gating property of the $q$ -exponential map.

Panel of Figure 5 — Figure 5. Robustness to ill-conditioning ( $n=2\,000$ , $\mathrm{SNR}=20$ dB, 100 iterations). (a) Iterations to reach the $10^{-3}$ FW duality threshold versus condition number $\kappa$ (up to $10^{7}$ ). (b) Support recovery delay versus $\kappa$ . DMD exhibits remarkable insensitivity to the condition number in both metrics.

Algorithm	$q=0.05$	$q=0.1$	$q=0.2$	$q=0.3$
DMD	$86.2\pm 27.8$	$98.4\pm 14.2$	$115.6\pm 18.5$	$142.3\pm 25.1$
GEG	$245.5\pm 92.4$	$312.7\pm 45.3$	$420.1\pm 62.8$	$565.4\pm 88.2$

Table 3. Iterations to reach a relative FW duality gap

\leq 10^{-4}

as a function of

q

(

n=2\,000

K=200

\kappa=1\,000

, 50 runs, mean

\pm

std).

Algorithm	$q=0.05$	$q=0.1$	$q=0.2$	$q=0.3$
DMD	$6.20\times 10^{-8}$	$1.25\times 10^{-7}$	$8.40\times 10^{-7}$	$3.55\times 10^{-6}$
GEG	$8.50\times 10^{-5}$	$4.10\times 10^{-4}$	$1.20\times 10^{-3}$	$6.80\times 10^{-3}$

Table 4. Relative primal gap after a fixed budget of 100 iterations as a function of

q

(

n=2\,000

K=200

\kappa=1\,000

, 50 runs).

Geometric Property	DMD (Convex Link)	GEG (Concave Link)
Curvature Profile $h^{\prime\prime}(w)$	Monotonically Increasing	Singular Decay ( $w^{-q}$ )
Global Smoothness $L_{F}$	Strictly Finite ( $\leq e$ )	Infinite ( $\to\infty$ )
Curvature-based step-size guideline	$\eta\leq\text{Constant}$	$\eta\leq 2\,(\bm{w}_{\min})^{q}$
Condition Number $\kappa_{F}$	$\leq e$ (Optimally Bounded)	$\kappa\to\infty$ (Unbounded)
Robustness to Stochastic Noise	High (Maintains Large $\eta$ )	Low (Amplified by Curvature)

Table 5. Theoretical comparison of the geometric properties of DMD versus GEG over the probability simplex.

Mirror Descent

Mirror descent uses Bregman geometry to design optimization updates suited to constraints, data structure, and learning dynamics.

See all 23 papers

Sep 25, 2026

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

Ask PDF

Mar 18, 2026

Mirror Descent on Riemannian Manifolds

Mirror Descent (MD) is a scalable first-order method widely used in large-scale optimization, with applications in image processing, policy optimization, and neural network training. This paper generalizes MD to optimization on Riemannian manifolds. In particular, we develop a Riemannian Mirror Descent (RMD) framework via reparameterization and further propose a stochastic variant of RMD. We also establish non-asymptotic convergence guarantees for both RMD and stochastic RMD. As an application to the Stiefel manifold, our RMD framework reduces to the Curvilinear Gradient Descent (CGD) method proposed in [26]. Moreover, when specializing the stochastic RMD framework to the Stiefel setting, we obtain a stochastic extension of CGD, which effectively addresses large-scale manifold optimization problems.

Jiaxin Jiang, Lei Shi, Jiyuan Tan

School of Mathematical Sciences, Fudan University, Shanghai 200433, China · Shanghai Key Laboratory for Contemporary Applied Mathematics, Fudan University, Shanghai 200433, China

Riemannian Optimization Stochastic Optimization Convergence

Ask PDF

Feb 2, 2026

A Geometry-Aware Efficient Algorithm for Compositional Entropic Risk Minimization

This paper studies optimization for a family of problems termed

\textbf{compositional entropic risk minimization}

, in which each data's loss is formulated as a Log-Expectation-Exponential (Log-E-Exp) function. The Log-E-Exp formulation serves as an abstraction of the Log-Sum-Exponential (LogSumExp) function when the explicit summation inside the logarithm is taken over a gigantic number of items and is therefore expensive to evaluate. While entropic risk objectives of this form arise in many machine learning problems, existing optimization algorithms suffer from several fundamental limitations including non-convergence, numerical instability, and slow convergence rates. To address these limitations, we propose a geometry-aware stochastic algorithm, termed

\textbf{SCENT}

, for the dual formulation of entropic risk minimization cast as a min--min optimization problem. The key to our design is a

\textbf{stochastic proximal mirror descent (SPMD)}

update for the dual variable, equipped with a Bregman divergence induced by a negative exponential function that faithfully captures the geometry of the objective. Our main contributions are threefold: (i) we establish an

O(1/\sqrt{T})

convergence rate of the proposed SCENT algorithm for convex problems; (ii) we theoretically characterize the advantages of SPMD over standard SGD update for optimizing the dual variable; and (iii) we demonstrate the empirical effectiveness of SCENT on extreme classification, partial AUC maximization, contrastive learning and distributionally robust optimization, where it consistently outperforms existing baselines. Code is available at https://github.com/Optimization-AI/SCENT.

Xiyuan Wei, Linli Zhou, Bokun Wang +2

Texas A&M University · University of Texas, Austin · National Taiwan University +1

Stochastic Optimization

Ask PDF

Abstract

Mirror Descent

Explore similar work

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

Mirror Descent on Riemannian Manifolds

A Geometry-Aware Efficient Algorithm for Compositional Entropic Risk Minimization