The DOI matches its Crossref record; 43 of the 43 references it cites were found in a registry or an index.
Global rates of convergence for nonconvex optimization on manifolds
Open accessAbstract
We consider the minimization of a cost function f on a manifold $\mathcal{M}$ using Riemannian gradient descent and Riemannian trust regions (RTR). We focus on satisfying necessary optimality conditions within a tolerance ε. Specifically, we show that, under Lipschitz-type assumptions on the pullbacks of f to the tangent spaces of $\mathcal{M}$, both of these algorithms produce points with Riemannian gradient smaller than ε in $\mathcal{O}\big(1/\varepsilon ^{2}\big)$ iterations. Furthermore, RTR returns a point where also the Riemannian Hessian’s least eigenvalue is larger than −ε in $\mathcal{O} \big(1/\varepsilon ^{3}\big)$ iterations. There are no assumptions on initialization. The rates match their (sharp) unconstrained counterparts as a function of the accuracy ε (up to constants) and hence are sharp in that sense. These are the first deterministic results for global rates of convergence to approximate first- and second-order Karush-Kuhn-Tucker points on manifolds. They apply in particular for optimization constrained to compact submanifolds of ${\mathbb{R}^{n}}$, under simpler assumptions.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Advances in neural information processing systems 7
Cios, K., & Shields, M. (1997) · Neurocomputing · doi:10.1016/s0925-2312(97)90018-7 · Cited by 22,059
(2021) · A First Course in Statistical Programming with R · doi:10.1017/9781108993456.011 · Cited by 13,724
(1999) · Springer Series in Operations Research and Financial Engineering · doi:10.1007/b98874 · Cited by 9,482
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
Introductory Lectures on Convex Optimization: A Basic Course
Nesterov, Y. E. (2014) · Medical Entomology and Zoology · Cited by 3,557
Conn, A. R., Gould, N. I. M., & Toint, P. L. (2000) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719857 · Cited by 2,981
Introductory Lectures on Convex Optimization
Nesterov, Y. (2004) · Applied Optimization · doi:10.1007/978-1-4419-8853-9 · Cited by 2,698
The Geometry of Algorithms with Orthogonality Constraints
Edelman, A., Arias, T. A., & Smith, S. T. (1998) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479895290954 · Cited by 2,685
Semi-Riemannian Geometry With Applications to Relativity
O’Neill, B. (2011) · Cited by 2,236
Optimization Algorithms on Matrix Manifolds
Absil, P.-A., Mahony, R., & Sepulchre, R. (2008) · Princeton University Press eBooks · doi:10.1515/9781400830244 · Cited by 1,840
Self-citationSEMI-RIEMANNIAN GEOMETRY With Applications to Relativity
MacCallum, M. A. H. (1984) · Bulletin of the London Mathematical Society · doi:10.1112/blms/16.3.328 · Cited by 1,692
Moré, J. J., & Sorensen, D. C. (1983) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0904038 · Cited by 1,411
Riemannian Geometry: A Modern Introduction
Chavel, I. (1994) · Cited by 842
The Conjugate Gradient Method and Trust Regions in Large Scale Optimization
Steihaug, T. (1983) · SIAM Journal on Numerical Analysis · doi:10.1137/0720042 · Cited by 824
Manopt, a Matlab toolbox for optimization on manifolds
Boumal, N., Mishra, B., Absil, P.-A., & Sepulchre, R. J. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1308.5200 · Cited by 737
Self-citation(2013) · Encyclopedia of Systems Biology · doi:10.1007/978-1-4419-9863-7_101044 · Cited by 736
Ruszczynski, A. (2006) · Princeton University Press eBooks · doi:10.1515/9781400841059 · Cited by 696
On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
Kaufmann, E., Cappé, O., & Garivier, A. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1407.4443 · Cited by 661
Newton’s Method with a Model Trust Region Modification
Sorensen, D. C. (1982) · SIAM Journal on Numerical Analysis · doi:10.1137/0719026 · Cited by 560
Low-Rank Matrix Completion by Riemannian Optimization
Vandereycken, B. (2013) · SIAM Journal on Optimization · doi:10.1137/110845768 · Cited by 491
Trust-Region Methods on Riemannian Manifolds
Absil, P.-A., Baker, C. G., & Gallivan, K. A. (2007) · Foundations of Computational Mathematics · doi:10.1007/s10208-005-0179-9 · Cited by 461
Self-citationLocal Minima and Convergence in Low-Rank Semidefinite Programming
Burer, S., & Monteiro, R. D. C. (2005) · Mathematical Programming · doi:10.1007/s10107-004-0564-1 · Cited by 347
Optimization Methods on Riemannian Manifolds and Their Application to Shape Space
Ring, W., & Wirth, B. (2012) · SIAM Journal on Optimization · doi:10.1137/11082885x · Cited by 303
Projection-like Retractions on Matrix Manifolds
Absil, P.-A., & Malick, J. (2012) · SIAM Journal on Optimization · doi:10.1137/100802529 · Cited by 296
Self-citationCartis, C., Gould, N. I. M., & Toint, P. L. (2010) · Mathematical Programming · doi:10.1007/s10107-009-0337-y · Cited by 275
Self-citationNewton's method on Riemannian manifolds and a geometric model for the human spine
Adler, R. L. (2002) · IMA Journal of Numerical Analysis · doi:10.1093/imanum/22.3.359 · Cited by 271
Optimization techniques on Riemannian manifolds
Smith, S. (1995) · Hamiltonian and Gradient Flows, Algorithms and Control · doi:10.1090/fic/003/09 · Cited by 258
Global Optimality of Local Search for Low Rank Matrix Recovery
Bhojanapalli, S., Neyshabur, B., & Srebro, N. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.07221 · Cited by 218
A Broyden Class of Quasi-Newton Methods for Riemannian Optimization
Huang, W., Gallivan, K. A., & Absil, P.-A. (2015) · SIAM Journal on Optimization · doi:10.1137/140955483 · Cited by 189
Self-citationPymanopt: A Python Toolbox for Optimization on Manifolds using Automatic DifferentiationPreprint
Townsend, J., Koep, N., & Weichwald, S. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1603.03236 · Cited by 180
Curtis, F. E., Robinson, D. P., & Samadi, M. (2016) · Mathematical Programming · doi:10.1007/s10107-016-1026-2 · Cited by 159
Nonconvex Phase Synchronization
Boumal, N. (2016) · SIAM Journal on Optimization · doi:10.1137/16m105808x · Cited by 151
Self-citationRiemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
Zhang, H., Reddi, S. J., & Sra, S. (2016) · arXiv · doi:10.48550/arxiv.1605.07147 · Cited by 140
First-order Methods for Geodesically Convex OptimizationPreprint
Zhang, H., & Sra, S. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.06053 · Cited by 134
Complete Dictionary Recovery Over the Sphere II: Recovery by Riemannian Trust-Region Method
Sun, J., Qu, Q., & Wright, J. N. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2632149 · Cited by 114
Bandeira, A. S., Boumal, N., & Voroninski, V. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.04426 · Cited by 100
Self-citationTwo proposals for robust PCA using semidefinite programming
McCoy, M., & Tropp, J. A. (2011) · Electronic Journal of Statistics · doi:10.1214/11-ejs636 · Cited by 94
Iteration-Complexity of Gradient, Subgradient and Proximal Point Methods on Riemannian Manifolds
Bento, G. C., Ferreira, O. P., & Melo, J. G. (2017) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-017-1093-4 · Cited by 78
Complete dictionary recovery over the sphere
Sun, J., Qu, Q., & Wright, J. N. (2015) · International Conference on Sampling Theory and Applications · doi:10.1109/sampta.2015.7148922 · Cited by 78
Boumal, N. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1506.00575 · Cited by 77
Self-citationLow-rank retractions: a survey and new results
Absil, P.-A., & Oseledets, I. V. (2014) · Computational Optimization and Applications · doi:10.1007/s10589-014-9714-4 · Cited by 52
Self-citationSolving SDPs for synchronization and MaxCut problems via the Grothendieck inequalityPreprint
Song, M. N., Misiakiewicz, T., Andrea Montanari, A., & Oliveira, R. I. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1703.08729 · Cited by 47
Bini, D. A. (2013) · Discrete mathematics and its applications · doi:10.1201/b16113-72 · Cited by 26
Cited by
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
Chi, Y., Lu, Y. M., & Chen, Y. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2937282 · Cited by 360
SE-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group
Rosen, D. M., Carlone, L., Bandeira, A. S., & Leonard, J. J. (2019) · The International Journal of Robotics Research · doi:10.1177/0278364918784361 · Cited by 282
Blind Demixing for Low-Latency Communication
Dong, J., Yang, K., & Shi, Y. (2019) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2018.2886191 · Cited by 22
Metadata
- Authors
- Boumal, N., Absil, P.-A., & Cartis, C.
- Venue
- IMA Journal of Numerical Analysis
- Publisher
- Oxford University Press (OUP)
- Published
- 2018-02-07
- Volume
- 39
- Issue
- 1
- Pages
- 1-33
- ISSN
- 0272-4979 (ISSN-L)
- 1464-3642
- OpenAlex
- W2402588523
- Cited by
- 271
- References
- 43
- FWCI
- 27.61
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.