User menu

Global rates of convergence for nonconvex optimization on manifolds

Bibliographic reference Boumal, Nicolas ; Absil, Pierre-Antoine ; Cartis, Coralia. Global rates of convergence for nonconvex optimization on manifolds. In: IMA Journal of Numerical Analysis,
Permanent URL
  1. Absil P.-A., Baker C.G., Gallivan K.A., Trust-Region Methods on Riemannian Manifolds, 10.1007/s10208-005-0179-9
  2. Absil, Optimization Algorithms on Matrix Manifolds (2008)
  3. Absil P. -A., Mahony Robert, Trumpf Jochen, An Extrinsic Look at the Riemannian Hessian, Lecture Notes in Computer Science (2013) ISBN:9783642400193 p.361-368, 10.1007/978-3-642-40020-9_39
  4. Absil P.-A., Malick Jérôme, Projection-like Retractions on Matrix Manifolds, 10.1137/100802529
  5. Absil P.-A., Oseledets I. V., Low-rank retractions: a survey and new results, 10.1007/s10589-014-9714-4
  6. Absil, Technical Report UCL-INMA-2009.024 (2009)
  7. Adler R. L., Newton's method on Riemannian manifolds and a geometric model for the human spine, 10.1093/imanum/22.3.359
  8. Bandeira, Proceedings of the 29th Conference on Learning Theory, COLT 2016. (2016)
  9. Bento Glaydston C., Ferreira Orizon P., Melo Jefferson G., Iteration-Complexity of Gradient, Subgradient and Proximal Point Methods on Riemannian Manifolds, 10.1007/s10957-017-1093-4
  10. Bhojanapalli, 07221 (2016)
  11. Birgin E. G., Gardenghi J. L., Martínez J. M., Santos S. A., Toint Ph. L., Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models, 10.1007/s10107-016-1065-8
  12. Boumal Nicolas, Riemannian Trust Regions with Finite-Difference Hessian Approximations are Globally Convergent, Lecture Notes in Computer Science (2015) ISBN:9783319250397 p.467-475, 10.1007/978-3-319-25040-3_50
  13. Boumal (2015)
  14. Boumal Nicolas, Nonconvex Phase Synchronization, 10.1137/16m105808x
  15. Boumal, J. Mach. Learn. Res, 15, 1455 (2014)
  16. Boumal, Advances in Neural Information Processing Systems, 2757 (2016)
  17. Burer Samuel, Monteiro Renato D.C., Local Minima and Convergence in Low-Rank Semidefinite Programming, 10.1007/s10107-004-0564-1
  18. Cartis C., Gould N. I. M., Toint Ph. L., On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems, 10.1137/090774100
  19. Cartis Coralia, Gould Nicholas I. M., Toint Philippe L., Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity, 10.1007/s10107-009-0337-y
  20. Cartis, ERGO Technical Report 11–009. School of Mathematics (2011)
  21. Cartis C., Gould N.I.M., Toint Ph.L., Complexity bounds for second-order optimality in unconstrained optimization, 10.1016/j.jco.2011.06.001
  22. Cartis Coralia, Gould Nicholas I.M., Toint Philippe L., On the complexity of finding first-order critical points in constrained nonlinear optimization, 10.1007/s10107-012-0617-9
  23. Cartis, NA Technical Report, Maths E-print Archive1912 (2015)
  24. Cartis Coralia, Gould Nicholas I. M., Toint Philippe L., On the Evaluation Complexity of Constrained Nonlinear Least-Squares and General Constrained Nonlinear Optimization Using Second-Order Methods, 10.1137/130915546
  25. Cartis, Found. Comput. Math (2017)
  26. Chavel, Riemannian Geometry: A Modern Introduction (2006)
  27. Conn Andrew R., Gould Nicholas I. M., Toint Philippe L., Trust Region Methods, ISBN:9780898714609, 10.1137/1.9780898719857
  28. Curtis Frank E., Robinson Daniel P., Samadi Mohammadreza, A trust region algorithm with a worst-case iteration complexity of $$\mathcal{O}(\epsilon ^{-3/2})$$ O ( ϵ - 3 / 2 ) for nonconvex optimization, 10.1007/s10107-016-1026-2
  29. Edelman Alan, Arias Tomás A., Smith Steven T., The Geometry of Algorithms with Orthogonality Constraints, 10.1137/s0895479895290954
  30. Gabay D., Minimizing a differentiable function over a differential manifold, 10.1007/bf00934767
  31. Ge, Advances in Neural Information Processing Systems, 29, 2973 (2016)
  32. Goemans Michel X., Williamson David P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, 10.1145/227683.227684
  33. Golub, Matrix Computations (2012)
  34. Huang (2016)
  35. Huang Wen, Gallivan K. A., Absil P.-A., A Broyden Class of Quasi-Newton Methods for Riemannian Optimization, 10.1137/140955483
  36. McCoy Michael, Tropp Joel A., Two proposals for robust PCA using semidefinite programming, 10.1214/11-ejs636
  37. Mei (2017)
  38. Monera, Rev. R. Acad. Cienc. Exactas, Físicas Nat. Ser. A Math. RACSAM, 881 (2014)
  39. Moré Jorge J., Sorensen D. C., Computing a Trust Region Step, 10.1137/0904038
  40. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course (2004)
  41. Nocedal, Numerical Optimization (1999)
  42. O’Neill, Semi-Riemannian Geometry: With Applications to Relativity (1983)
  43. Qi (2011)
  44. Ring Wolfgang, Wirth Benedikt, Optimization Methods on Riemannian Manifolds and Their Application to Shape Space, 10.1137/11082885x
  45. Ruszczyński, Nonlinear Optimization (2006)
  46. Sato Hiroyuki, A Dai–Yuan-type Riemannian conjugate gradient method with the weak Wolfe conditions, 10.1007/s10589-015-9801-1
  47. Shub, Proceedings of VII ELAM., 69 (1986)
  48. Smith, Fields Inst. Commun., 3, 113 (1994)
  49. Sorensen D. C., Newton’s Method with a Model Trust Region Modification, 10.1137/0719026
  50. Steihaug Trond, The Conjugate Gradient Method and Trust Regions in Large Scale Optimization, 10.1137/0720042
  51. Sun Ju, Qu Qing, Wright John, Complete Dictionary Recovery Over the Sphere II: Recovery by Riemannian Trust-Region Method, 10.1109/tit.2016.2632149
  52. Sun Ju, Qu Qing, Wright John, A Geometric Analysis of Phase Retrieval, 10.1007/s10208-017-9365-9
  53. Toint, P. (1981) Towards an efficient sparsity exploiting Newton method for minimization. Sparse Matrices and Their Uses (I.Duff ed). Academic Press, pp. 57--88.
  54. Townsend, J. Mach. Learn. Res., 17, 1 (2016)
  55. Berger (2017)
  56. Udriste (1994)
  57. Vandereycken Bart, Low-Rank Matrix Completion by Riemannian Optimization, 10.1137/110845768
  58. Vavasis, Nonlinear Optimization: Complexity Issues (1991)
  59. Yang, Pacific J. Optim, 10, 415 (2014)
  60. Zhang, 1617 (2016)
  61. Zhang, H., Reddi, S. & SraS. (2016) Riemannian SVRG: fast stochastic optimization on Riemannian manifolds. Advances in Neural Information Processing Systems. Curran Associates. pp. 4592--4600.