Super-Acceleration with Cyclical Step-sizes.
Baptiste GOUJAUD, Damien SCIEUR, Aymeric DIEULEVEUT, Adrien TAYLOR, Fabian PEDREGOSA
2021
Cyclical step-sizes are becoming increasingly popular in the optimization of deep learning problems. Motivated by recent observations on the spectral gaps of Hessians in machine learning, we show that these step-size schedules offer a simple way to exploit them. More precisely, we develop a convergence rate analysis for quadratic objectives that provides optimal parameters and shows that cyclical learning rates can improve upon traditional lower complexity bounds. We further propose a systematic approach to design optimal first order methods for quadratic minimization with a given spectral structure. Finally, we provide a local convergence rate analysis beyond quadratic minimization for the proposed methods and illustrate our findings through benchmarks on least squares and logistic regression problems.
Acceleration in optimization.
Damien SCIEUR, Francis BACH, Alexandre d ASPREMONT, Antonin CHAMBOLLE, Francis BACH, Alexandre d ASPREMONT, Antonin CHAMBOLLE, Joseph SALMON, Yurii NESTEROV, Antonin CHAMBOLLE, Joseph SALMON
2018
In many fields, such as optimization, the performance of a method is often characterized by its convergence rate. However, accelerating an algorithm requires some knowledge of the problem structure and such improvements are the result of a case-by-case study. Many acceleration techniques have been developed in the last decades and are now massively used. Despite their simplicity, these methods are often based on purely algebraic arguments and generally lack intuitive explanations. Recently, a lot of work has been done to make connections between accelerated algorithms and other scientific domains, such as control theory or differential equations. However, these explanations are often based on complex arguments and most of them use unconventional tools in their analysis. One of the contributions of this thesis is an attempt to explain accelerated algorithms using the theory of integration methods, which has been extensively studied and enjoys a strong theoretical analysis. In particular, we show that optimization methods are in fact instances of integration methods, when integrating the gradient flow equation. With standard arguments, we intuitively explain the origin of the acceleration. On the other hand, accelerated methods need additional parameters, compared to slower methods, which are usually difficult to estimate. Moreover, these schemes are built for a particular configuration and cannot be used elsewhere. Here, we explore another approach to accelerating optimization algorithms, which uses generic acceleration arguments. In numerical analysis, these tools have been developed to accelerate sequences of scalars or vectors, by building in parallel another sequence with a better convergence rate. These methods can be combined with an iterative algorithm, accelerating it in most cases. In practice, these extrapolation methods are not so much used, notably because of their lack of convergence guarantees and their instability. We extend these methods by regularizing them, which will allow a deeper theoretical analysis and stronger convergence results, especially when applied to optimization methods.
Acceleration in optimization.
Damien SCIEUR
2018
In many different fields such as optimization, the performance of a method is often characterized by its rate of convergence. However, accelerating an algorithm requires a lot of knowledge about the problem’s structure, and such improvement is done on a case-by-case basis. Many accelerated schemes have been developed in the past few decades and are massively used in practice. Despite their simplicity, such methods are usually based on purely algebraic arguments and often do not have an intuitive explanation. Recently, heavy work has been done to link accelerated algorithms with other fields of science, such as control theory or differential equations. However, these explanations often rely on complex arguments, usually using non-conventional tools in their analysis. One of the contributions of this thesis is a tentative explanation of optimization algorithms using the theory of integration methods, which has been well studied and enjoys a solid theoretical analysis. In particular, we will show that optimization scheme are special instance of integration methods when integrating the classical gradient flow. With standard arguments, we intuitively explain the origin of acceleration. On the other hand, accelerated methods usually need additional parameters in comparison with slower one, which are in most cases difficult to estimate. In addition, these schemes are designed for one particular setting and cannot be used elsewhere. In this thesis, we explore a new approach for accelerating optimization algorithms, which uses generic acceleration arguments. In numerical analysis, these tools have been developed for accelerating sequences of scalars or vectors, by building on the side another sequence with a better convergence rate. These methods can be combined with an iterative algorithm, speeding it up in most cases. In practice, extrapolation schemes are not widely used due to their lack of theoretical guarantees and their instability. We will extend these methods by regularizing them, allowing a deeper theoretical analysis and stronger convergence results, especially when applied to optimization methods.
