4 papers
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…