7 papers · 1 filter
Automated tight Lyapunov analysis for first-order methods
Manu Upadhyaya, Sebastian Banert, Adrien B. Taylor +1
We present a methodology for establishing the existence of quadratic Lyapunov inequalities for a wide range of first-order methods used to solve convex optimization problems. In pa…
Provable non-accelerations of the heavy-ball method
Baptiste Goujaud, Adrien Taylor, Aymeric Dieuleveut
In this work, we show that the heavy-ball ($\HB$) method provably does not reach an accelerated convergence rate on smooth strongly convex problems. More specifically, we show that…
Counter-examples in first-order optimization: a constructive approach
Baptiste Goujaud, Aymeric Dieuleveut, Adrien Taylor
While many approaches were developed for obtaining worst-case complexity bounds for first-order optimization methods in the last years, there remain theoretical gaps in cases where…
Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization
Benjamin Dubois-Taine, Francis Bach, Quentin Berthet +1
We consider the problem of minimizing the sum of two convex functions. One of those functions has Lipschitz-continuous gradients, and can be accessed via stochastic oracles, wherea…
Acceleration Methods
Alexandre d'Aspremont, Damien Scieur, Adrien Taylor
This monograph covers some recent advances in a range of acceleration techniques frequently used in convex optimization. We first use quadratic optimization problems to introduce t…
Nonlinear conjugate gradient methods: worst-case convergence rates via computer-assisted analyses
Shuvomoy Das Gupta, Robert M. Freund, Xu Andy Sun +1
We propose a computer-assisted approach to the analysis of the worst-case convergence of nonlinear conjugate gradient methods (NCGMs). Those methods are known for their generally g…