User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Exact Worst-Case Convergence Rates of the Proximal Gradient Method for Composite Convex Minimization

Primary tabs

download
  • Open access
  • PDF
  • 361.36 K
Taylor, Adrien B. [UCL] Hendrickx, Julien [UCL] Glineur, François [UCL]

We study the worst-case convergence rates of the proximal gradient method for minimizing the sum of a smooth strongly convex function and a non-smooth convex function, whose proximal operator is available. We establish the exact worst-case convergence rates of the proximal gradient method in this setting for any step size and for different standard performance measures: objective function accuracy, distance to optimality and residual gradient norm. The proof methodology relies on recent developments in performance estimation of first-order methods, based on semidefinite programming. In the case of the proximal gradient method, this methodology allows obtaining exact and non-asymptotic worst-case guarantees that are conceptually very simple, although apparently new. On the way, we discuss how strong convexity can be replaced by weaker assumptions, while preserving the corresponding convergence rates. We also establish that the same fixed step size policy is optimal for all three performance measures. Finally, we extend recent results on the worst-case behavior of gradient descent with exact line search to the proximal case.

(eng) The PDF file contains the final version of the author's manuscript.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès libre
Publication date 2018
Language Anglais
Journal information "Journal of Optimization Theory and Applications" - Vol. 178, p. 455-476 (2018)
Peer reviewed yes
Publisher Springer Nature
issn 0022-3239
e-issn 1573-2878
Publication status Publié
Affiliation UCL - SST/ICTM/INMA - Pôle en ingénierie mathématique
Keywords proximal gradient method ; composite convex optimization ; convergence rates ; worst-case analysis
Links
  1. Polyak, B.T.: Introduction to Optimization. Optimization Software, New York (1987)
  2. Nesterov Yurii, Introductory Lectures on Convex Optimization, ISBN:9781461346913, 10.1007/978-1-4419-8853-9
  3. Ryu, E.K., Boyd, S.: A primer on monotone operator methods. Appl. Comput. Math. 15(1), 3–43 (2016)
  4. Lessard Laurent, Recht Benjamin, Packard Andrew, Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints, 10.1137/15m1009597
  5. Schmidt, M., Le Roux, N., Bach, F.: Convergence rates of inexact proximal-gradient methods for convex optimization. In: Advances in Neural Information Processing Systems, pp. 1458–1466 (2011)
  6. Zhang Hui, Cheng Lizhi, Restricted strong convexity and its applications to convergence analysis of gradient-type methods in convex optimization, 10.1007/s11590-014-0795-x
  7. Necoara I., Nesterov Yu., Glineur F., Linear convergence of first order methods for non-strongly convex optimization, 10.1007/s10107-018-1232-1
  8. Karimi Hamed, Nutini Julie, Schmidt Mark, Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition, Machine Learning and Knowledge Discovery in Databases (2016) ISBN:9783319461274 p.795-811, 10.1007/978-3-319-46128-1_50
  9. Drori Yoel, Teboulle Marc, Performance of first-order methods for smooth convex minimization: a novel approach, 10.1007/s10107-013-0653-0
  10. Taylor Adrien B., Hendrickx Julien M., Glineur François, Smooth strongly convex interpolation and exact worst-case performance of first-order methods, 10.1007/s10107-016-1009-3
  11. Taylor Adrien B., Hendrickx Julien M., Glineur François, Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization, 10.1137/16m108104x
  12. Parikh, N., Boyd, S.: Proximal algorithms. Found. Trends Optim. 1(3), 123–231 (2013)
  13. Combettes Patrick L., Pesquet Jean-Christophe, Proximal Splitting Methods in Signal Processing, Springer Optimization and Its Applications (2011) ISBN:9781441995681 p.185-212, 10.1007/978-1-4419-9569-8_10
  14. de Klerk Etienne, Glineur François, Taylor Adrien B., On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions, 10.1007/s11590-016-1087-4
  15. Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999)
  16. Bubeck Sébastien, Convex Optimization: Algorithms and Complexity, 10.1561/2200000050
  17. Drori, Y.: Contributions to the Complexity Analysis of Optimization Algorithms. Ph.D. Thesis, Tel-Aviv University (2014)
  18. Nesterov Yu., Gradient methods for minimizing composite functions, 10.1007/s10107-012-0629-5
  19. Taylor, A.B.: Convex Interpolation and Performance Estimation of First-Order Methods for Convex Optimization. Ph.D. Thesis, Université catholique de Louvain (2017)
  20. Nemirovsky A.S, Information-based complexity of linear operator equations, 10.1016/0885-064x(92)90013-2
  21. Devolder Olivier, Glineur François, Nesterov Yurii, First-order methods of smooth convex optimization with inexact oracle, 10.1007/s10107-013-0677-5
  22. Nesterov Yu., Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems, 10.1137/100802001
  23. Kim Donghwan, Fessler Jeffrey A., Optimized first-order methods for smooth convex minimization, 10.1007/s10107-015-0949-3
  24. Drori Yoel, The exact information-based complexity of smooth convex minimization, 10.1016/j.jco.2016.11.001
  25. Taylor Adrien B., Hendrickx Julien M., Glineur Francois, Performance estimation toolbox (PESTO): Automated worst-case analysis of first-order optimization methods, 10.1109/cdc.2017.8263832
Bibliographic reference Taylor, Adrien B. ; Hendrickx, Julien ; Glineur, François. Exact Worst-Case Convergence Rates of the Proximal Gradient Method for Composite Convex Minimization. In: Journal of Optimization Theory and Applications, Vol. 178, p. 455-476 (2018)
Permanent URL http://hdl.handle.net/2078.1/198401