Math @ Duke

Publications [#323274] of Sayan Mukherjee
Papers Published
 Raskutti, G; Mukherjee, S, The information geometry of mirror descent,
Lecture notes in computer science, vol. 9389
(January, 2015),
pp. 359368, ISBN 9783319250397 [doi]
(last updated on 2017/04/01)
Abstract: © Springer International Publishing Switzerland 2015.We prove the equivalence of two online learning algorithms, mirror descent and natural gradient descent. Both mirror descent and natural gradient descent are generalizations of online gradient descent when the parameter of interest lies on a nonEuclidean manifold. Natural gradient descent selects the steepest descent direction along a Riemannian manifold by multiplying the standard gradient by the inverse of the metric tensor. Mirror descent induces nonEuclidean structure by solving iterative optimization problems using different proximity functions. In this paper, we prove that mirror descent induced by a Bregman divergence proximity functions is equivalent to the natural gradient descent algorithm on the Riemannian manifold in the dual coordinate system.We use techniques from convex analysis and connections between Riemannian manifolds, Bregman divergences and convexity to prove this result. This equivalence between natural gradient descent and mirror descent, implies that (1) mirror descent is the steepest descent direction along the Riemannian manifold corresponding to the choice of Bregman divergence and (2) mirror descent with loglikelihood loss applied to parameter estimation in exponential families asymptotically achieves the classical CramérRao lower bound.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

