Source-linked AI summary
The Information Geometry of Mirror Descent
Garvesh Raskutti, Sayan Mukherjee
TL;DR
The paper addresses the limited geometric and statistical-efficiency analysis of mirror descent while seeking scalable first-order methods for information-geometric optimization. It proves an equivalence between Bregman-divergence mirror descent and natural gradient descent on a dual Riemannian manifold, yielding steepest-descent behavior, Cramér-Rao efficiency, and a first-order implementation of natural gradient descent.
Problem
Existing mirror-descent analysis does not precisely characterize its induced non-Euclidean geometry or its statistical relative efficiency, while natural gradient descent is second-order.
Method
The paper establishes that mirror descent with Bregman divergences is equivalent to natural gradient descent on the dual Riemannian manifold.
Results
Mirror descent is the steepest descent direction on the corresponding Riemannian space and, for exponential-family parameter estimation, achieves the Cramér-Rao lower bound.
Takeaways & Limitations
Natural gradient descent for exponential-family manifolds can be implemented as a first-order method through mirror descent, with computational gains for larger datasets.
Takeaways & Limitations
Open questions include adaptive step-size choices and characterizing mirror-descent geometry for proximity functions such as ℓp-norms.
Abstract
from arXiv · showhide
Information geometry applies concepts in differential geometry to probability and statistics and is especially useful for parameter estimation in exponential families where parameters are known to lie on a Riemannian manifold. Connections between the geometric properties of the induced manifold and statistical properties of the estimation problem are well-established. However developing first-order methods that scale to larger problems has been less of a focus in the information geometry community. The best known algorithm that incorporates manifold structure is the second-order natural gradient descent algorithm introduced by Amari. On the other hand, stochastic approximation methods have led to the development of first-order methods for optimizing noisy objective functions. A recent generalization of the Robbins-Monro algorithm known as mirror descent, developed by Nemirovski and Yudin is a first order method that induces non-Euclidean geometries. However current analysis of mirror descent does not precisely characterize the induced non-Euclidean geometry nor does it consider performance in terms of statistical relative efficiency. In this paper, we prove that mirror descent induced by Bregman divergences is equivalent to the natural gradient descent algorithm on the dual Riemannian manifold. Using this equivalence, it follows that (1) mirror descent is the steepest descent direction along the Riemannian manifold of the exponential family; (2) mirror descent with log-likelihood loss applied to parameter estimation in exponential families asymptotically achieves the classical Cramér-Rao lower bound and (3) natural gradient descent for manifolds corresponding to exponential families can be implemented as a first-order method through mirror descent.
1 Introduction
The introduction frames mirror descent as a first-order generalization of gradient descent for optimization on non-Euclidean manifolds, especially those arising in exponential families. It motivates Bregman divergences as a bridge between mirror descent, natural gradient descent, and statistical geometry.
- 1 Introduction: Parameters on non-Euclidean manifolds make ambient-space gradient descent different from the manifold's steepest descent direction.The introduction gives mean-parameter spaces for Poisson, Bernoulli, and other exponential families as examples.
- 1.1 Riemannian manifolds and natural gradient descent: Natural gradient descent selects the steepest descent direction on a Riemannian manifold, including manifolds induced by Fisher information.When the metric is the identity, the natural gradient reduces to standard gradient descent.
- 1.2 Mirror descent with Bregman divergences: Mirror descent generalizes online gradient descent by replacing squared ℓ2 proximity with a strictly convex proximity function.The resulting update induces non-Euclidean geometry while retaining a first-order optimization structure.
- 1.2 Mirror descent with Bregman divergences: Bregman divergences are a natural choice because they correspond to Kullback-Leibler divergences for exponential families.A one-to-one correspondence between Bregman divergences and exponential families supports their use in statistical inference and information geometry.
- 1.3 Our contribution: The paper proves that Bregman-divergence mirror descent is equivalent to natural gradient descent on the dual Riemannian manifold.This connection is intended to transfer natural gradient's geometric and statistical properties to a first-order method.
2 Equivalence through dual co-ordinates
The paper establishes mirror descent and natural gradient descent as equivalent descriptions under convex duality, with Bregman divergences inducing paired primal and dual Riemannian manifolds.
- Equivalence through dual coordinates: The equivalence proof uses convex conjugate functions, Bregman divergence identities, dual coordinates, and the chain rule.The argument first expresses mirror descent in the dual manifold and then identifies the resulting step with natural gradient descent.
- Bregman divergences and convex duality: Convex conjugacy links the primal and dual Bregman divergences through BH(µ, µ′) = BG(h(µ′), h(µ)) and BG(θ, θ′) = BH(g(θ′), g(θ)).These relations connect the divergence representations across the two coordinate systems.
- Bregman divergences and Riemannian manifolds: A strictly convex twice-differentiable G induces the Riemannian metric ∇2G on Θ, while its convex conjugate H defines the dual coordinate system and manifold.The Hessian ∇2G is positive definite, and the dual coordinates satisfy g = ∇G and h = ∇H with g = h−1.
- Bregman divergences and Riemannian manifolds: For Gaussian families, the primal and dual manifolds coincide with Euclidean space because both Hessian metrics equal Ip×p.The Bernoulli example instead yields a non-Euclidean metric consistent with the statistical manifold representation.
- Main Result: Theorem 1 shows that mirror descent with a Bregman divergence induced by G is equivalent to natural gradient descent on the dual manifold (Φ, ∇2H).The proof rewrites the mirror-descent update in dual coordinates and applies the chain rule.
3 Consequences
The paper connects mirror descent to natural gradient descent on Bregman-induced Riemannian manifolds, yielding statistical efficiency and a computationally simpler implementation. In exponential-family estimation, mirror descent follows the manifold's steepest direction and asymptotically attains the Cramér–Rao lower bound.
- 3 Consequences: Mirror descent with Bregman divergence follows the direction of steepest descent on the corresponding dual Riemannian manifold.This interpretation follows from its equivalence with natural gradient descent and had not previously been provided for mirror descent.
- 3 Consequences: Natural gradient descent can be implemented as a first-order method through mirror descent, avoiding direct computation of the Riemannian metric tensor.Natural gradient is second-order because it requires ∇2H, whereas mirror descent uses derivatives of the objective and proximity function.
- 3.1 Efficient parameter estimation in exponential families: Mirror descent's statistical-efficiency analysis extends beyond prior regret-focused analyses to second-order properties such as Fisher efficiency.The paper studies mirror descent efficiency from a statistical perspective for exponential-family parameter estimation.
- 3.1 Efficient parameter estimation in exponential families: Mirror descent applied to log loss for exponential-family parameter estimation asymptotically achieves the Cramér–Rao lower bound.The result is obtained by transferring natural-gradient Fisher-efficiency results through the mirror-descent equivalence.
- 3.2 Connection to other online methods on Riemannian manifolds: The retraction Rµ(v) = µ+v is a first-order Taylor approximation of the exponential map and yields the natural gradient step.This makes mirror descent an easily computable first-order approximation to manifold steepest descent for Bregman-induced Riemannian manifolds.
4 Discussion
The paper connects Bregman-divergence mirror descent to natural gradient descent on a dual Riemannian manifold. This connection yields statistical efficiency for exponential-family estimation and a first-order implementation with computational gains for larger datasets.
- Bregman-divergence mirror descent is equivalent to natural gradient descent on the dual Riemannian manifold.
- For exponential-family parameter estimation, mirror descent with the associated Bregman divergence achieves the Cramér-Rao lower bound.
- The equivalence enables natural gradient steps to be implemented as a first-order mirror descent method, offering computational gains for larger datasets.
- Open directions include adaptive step-size choices using Riemannian structure and characterizing mirror-descent geometry for other proximity functions such as ℓp-norms.