[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Stochastic Approximation on Riemannian Manifolds

Published: 01 April 2021 Publication History

Abstract

The standard theory of stochastic approximation (SA) is extended to the case when the constraint set is a Riemannian manifold. Specifically, the standard ODE method for analyzing SA schemes is extended to iterations constrained to stay on a manifold using a retraction mapping. In addition, for submanifolds of a Euclidean space, a framework is developed for a projected SA scheme with approximate retractions. The framework is also extended to non-differentiable constraint sets.

References

[1]
Absil PA and Malick J Projection like retractions on matrix manifolds SIAM J. Control Optim. 2012 22 1 135-158
[2]
Absil PA, Mahoney R, and Sepulchre R Optimization Algorithms on Matrix Manifolds 2008 Princeton Princeton University Press
[3]
Alongi JM and Nelson GS Recurrence and Topology 2007 Providence, RI American Mathematical Soc
[4]
Arnold VI Ordinary Differential Equations 2001 Berlin Springer
[5]
Aubin JP Mutational and Morphological Analysis: Tools for Shape Evolution and Morphogenesis. Systems and Control: Foundations and Applications 1999 Boston Birkhauser
[6]
Aubin JP and Cellina A Differential Inclusions: Set-Valued Maps and Viability Theory 1984 New York Springer
[7]
Benaim M A dynamical system approach to stochastic approximation SIAM J. Control Optim. 1996 34 2 437-472
[8]
Benaim M and Hirsch MW Asymptotic pseudotrajectories and chain recurrent flows, with applications J. Dyn. Differ. Equ. 1996 8 1 141-176
[9]
Benaim M, Hofbauer J, and Sorin S Stochastic approximations and differential inclusions SIAM J. Control Optim. 2005 44 1 328-348
[10]
Bertsekas DP and Tsitsiklis JN Parallel and Distributed Computation 1989 Englewood Cliffs, NJ Prentice Hall
[11]
Bianchi P and Jakubowicz J Convergence of a multi-agent projected stochastic gradient algorithm for non-convex optimization IEEE Trans. Autom. Control 2013 58 2 391-405
[12]
Bonnabel S Stochastic gradient descent on Riemannian manifolds IEEE Trans. Autom. Control 2013 58 2 391-405
[13]
Borkar VS Stochastic approximation with two time scales Syst. Control Lett. 1997 29 5 291-294
[14]
Borkar VS Stochastic Approximation: A Dynamical Systems Viewpoint 2008 Cambridge, UK Hindustan Book Agency, New Delhi, and Cambridge University Press
[15]
Bottou, L.: Online learning and stochastic approximations. In: Saad, D. (ed.) On-Line Learning in Neural Networks, vol. 17(9), p. 142 (1998)
[16]
Deutsch F Best Approximation in Inner Product Spaces 2001 New York Springer
[17]
Deutsch F and Hundal H The rate of convergence of Dykstra’s cyclic projections algorithm: the polyhedral case Numer. Funct. Anal. Optim. 1994 15 5 537-565
[18]
do Carmo MP Riemannian Geometry 1992 Boston, MA Birkhauser Boston Inc.
[19]
Dupuis P Large deviations analysis of reflected diffusions and constrained stochastic approximation algorithms in convex sets Stochastics 1987 21 1 63-96
[20]
Dupuis P and Nagurney A Dynamical systems and variational inequalities Ann. Oper. Res. 1993 44 1 7-42
[21]
Hairer E, Lubich C, and Wanner G Geometric Numerical Integration 2002 Berlin Springer
[22]
Helmke U and Moore JB Optimization and Dynamical Systems 2012 Berlin Springer
[23]
Higham N Computing the nearest correlation matrix—a problem from finance IMA J. Numer. Anal. 2012 22 3 329-343
[24]
Hurley M Chain recurrence, semiflows, and gradients J. Dyn. Differ. Equ. 1995 7 3 437-456
[25]
Kushner HJ and Clark DS Stochastic Approximation Methods for Constrained and Unconstrained Systems 1978 New York Springer
[26]
Kushner HJ and Yin GG Stochastic Approximation and Recursive Algorithms and Applications 2003 2 New York Springer
[27]
Lee JM Riemannian Manifolds: An Introduction to Curvature 2006 New York Springer
[28]
Lewis AS and Malick J Alternating projections on manifolds Math. Oper. Res. 2008 33 1 216-234
[29]
Ljung L Analysis of recursive stochastic algorithms IEEE Trans. Autom. Control 1977 22 4 551-575
[30]
Mathkar AS and Borkar VS Nonlinear gossip SIAM J. Control Optim. 2016 54 3 1535-1557
[31]
Nedic A Convergence rate of distributed averaging dynamics and optimization in networks Found. Trends Syst. Control 2015 2 1
[32]
Oja E Subspace Methods of Pattern Recognition 1983 Hertfordshire, UK Research Studies Press
[33]
Qi C, Gallivan KA, and Absil PA Diehl M, Glineur F, Jarlebring E, and Michiels W Riemannian BFGS algorithm with applications Recent Advances in Optimization and Its Applications in Engineering 2010 Berlin Springer 183-192
[34]
Ring W and Wirth B Optimization methods on Riemannian manifolds and their application to shape space SIAM J. Control Optim. 2012 22 2 596-627
[35]
Robbins H and Monro S A stochastic approximation method Ann. Math. Stat. 1951 22 400-407
[36]
Rockafellar RT and Wets RJB Variational Analysis 1998 Berlin Springer
[37]
Serea OS On reflecting boundary problem for optimal control SIAM J. Control Optim. 2003 42 2 559-575
[38]
Shah, S.M., Borkar, V.S.: Distributed stochastic approximation with local constraints (submitted) (2017)
[39]
Trendafilov NT A continuous-time approach to the oblique Procrustes problem Behaviormetrika 1999 26 2 167-181
[40]
Tsitsiklis JN, Bertsekas DP, and Athans M Distributed asynchronous deterministic and stochastic gradient optimization algorithms IEEE Trans. Autom. Control 1986 31 9 803-812
[41]
Wen J, Gallivan KA, and Absil PA A Broyden class of quasi-Newton methods for Riemannian optimization SIAM J. Optim. 2015 25 3 1660-1685

Cited By

View all
  • (2023)Riemannian Smoothing Gradient Type Algorithms for Nonsmooth Optimization Problem on Compact Riemannian Submanifold Embedded in Euclidean SpaceApplied Mathematics and Optimization10.1007/s00245-023-10061-x88:3Online publication date: 3-Oct-2023

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Applied Mathematics and Optimization
Applied Mathematics and Optimization  Volume 83, Issue 2
Apr 2021
614 pages

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 April 2021

Author Tags

  1. Stochastic approximation
  2. Riemannian manifolds
  3. Retraction mappings
  4. ODE method
  5. Two time scales
  6. Differential inclusions

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 25 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Riemannian Smoothing Gradient Type Algorithms for Nonsmooth Optimization Problem on Compact Riemannian Submanifold Embedded in Euclidean SpaceApplied Mathematics and Optimization10.1007/s00245-023-10061-x88:3Online publication date: 3-Oct-2023

View Options

View options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media