Short Paper - Quadratic minimization: from conjugate gradient to an adaptive Polyak’s momentum method with Polyak step-sizes
In this work, we propose an adaptive variation on the classical Heavy-ball method for convex quadratic minimization. The adaptivity crucially relies on so-called “Polyak step-sizes”, which consists of using the knowledge of the optimal value of the optimization problem at hand instead of problem par...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Université de Montpellier
2024-11-01
|
| Series: | Open Journal of Mathematical Optimization |
| Subjects: | |
| Online Access: | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.36/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1825205179087060992 |
|---|---|
| author | Goujaud, Baptiste Taylor, Adrien Dieuleveut, Aymeric |
| author_facet | Goujaud, Baptiste Taylor, Adrien Dieuleveut, Aymeric |
| author_sort | Goujaud, Baptiste |
| collection | DOAJ |
| description | In this work, we propose an adaptive variation on the classical Heavy-ball method for convex quadratic minimization. The adaptivity crucially relies on so-called “Polyak step-sizes”, which consists of using the knowledge of the optimal value of the optimization problem at hand instead of problem parameters such as a few eigenvalues of the Hessian of the problem. This method happens to also be equivalent to a variation of the classical conjugate gradient method, and thereby inherits many of its attractive features, including its finite-time convergence, instance optimality, and its worst-case convergence rates.The classical gradient method with Polyak step-sizes is known to behave very well in situations in which it can be used, and the question of whether incorporating momentum in this method is possible and can improve the method itself appeared to be open. We provide a definitive answer to this question for minimizing convex quadratic functions, an arguably necessary first step for developing such methods in more general setups. |
| format | Article |
| id | doaj-art-d59fe8e407e34286bbd502f98b6aa6b2 |
| institution | Kabale University |
| issn | 2777-5860 |
| language | English |
| publishDate | 2024-11-01 |
| publisher | Université de Montpellier |
| record_format | Article |
| series | Open Journal of Mathematical Optimization |
| spelling | doaj-art-d59fe8e407e34286bbd502f98b6aa6b22025-02-07T14:01:18ZengUniversité de MontpellierOpen Journal of Mathematical Optimization2777-58602024-11-01511010.5802/ojmo.3610.5802/ojmo.36Short Paper - Quadratic minimization: from conjugate gradient to an adaptive Polyak’s momentum method with Polyak step-sizesGoujaud, Baptiste0Taylor, Adrien1Dieuleveut, Aymeric2CMAP, Ecole Polytechnique, Institut Polytechnique de ParisINRIA, Ecole Normale Supérieure, PSL Research University, ParisCMAP, Ecole Polytechnique, Institut Polytechnique de ParisIn this work, we propose an adaptive variation on the classical Heavy-ball method for convex quadratic minimization. The adaptivity crucially relies on so-called “Polyak step-sizes”, which consists of using the knowledge of the optimal value of the optimization problem at hand instead of problem parameters such as a few eigenvalues of the Hessian of the problem. This method happens to also be equivalent to a variation of the classical conjugate gradient method, and thereby inherits many of its attractive features, including its finite-time convergence, instance optimality, and its worst-case convergence rates.The classical gradient method with Polyak step-sizes is known to behave very well in situations in which it can be used, and the question of whether incorporating momentum in this method is possible and can improve the method itself appeared to be open. We provide a definitive answer to this question for minimizing convex quadratic functions, an arguably necessary first step for developing such methods in more general setups.https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.36/OptimizationQuadraticConjugate GradientHeavy-ballPolyak step-sizesOptimality |
| spellingShingle | Goujaud, Baptiste Taylor, Adrien Dieuleveut, Aymeric Short Paper - Quadratic minimization: from conjugate gradient to an adaptive Polyak’s momentum method with Polyak step-sizes Open Journal of Mathematical Optimization Optimization Quadratic Conjugate Gradient Heavy-ball Polyak step-sizes Optimality |
| title | Short Paper - Quadratic minimization: from conjugate gradient to an adaptive Polyak’s momentum method with Polyak step-sizes |
| title_full | Short Paper - Quadratic minimization: from conjugate gradient to an adaptive Polyak’s momentum method with Polyak step-sizes |
| title_fullStr | Short Paper - Quadratic minimization: from conjugate gradient to an adaptive Polyak’s momentum method with Polyak step-sizes |
| title_full_unstemmed | Short Paper - Quadratic minimization: from conjugate gradient to an adaptive Polyak’s momentum method with Polyak step-sizes |
| title_short | Short Paper - Quadratic minimization: from conjugate gradient to an adaptive Polyak’s momentum method with Polyak step-sizes |
| title_sort | short paper quadratic minimization from conjugate gradient to an adaptive polyak s momentum method with polyak step sizes |
| topic | Optimization Quadratic Conjugate Gradient Heavy-ball Polyak step-sizes Optimality |
| url | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.36/ |
| work_keys_str_mv | AT goujaudbaptiste shortpaperquadraticminimizationfromconjugategradienttoanadaptivepolyaksmomentummethodwithpolyakstepsizes AT tayloradrien shortpaperquadraticminimizationfromconjugategradienttoanadaptivepolyaksmomentummethodwithpolyakstepsizes AT dieuleveutaymeric shortpaperquadraticminimizationfromconjugategradienttoanadaptivepolyaksmomentummethodwithpolyakstepsizes |