109 citations · 280 across the 31 of their papers we have counts for
32 papers
Mirror descent algorithms with logarithmic barriers
Alberto De Marchi, Yura Malitsky, Adrien B. Taylor
This work derives convergence guarantees for mirror descent and proximal mirror descent algorithms when a logarithmic barrier is used as a distance-generating function. Standard ap…
Mirror Polyak and a Primal-Dual Lifting
Frederik Kunstner, Ryan D'Orazio, Victor S. Portella +1
First-order methods typically require a specific step-size that depends on the regularity conditions of the objective function, such as the smoothness, Lipschitz continuity, or str…
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…
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…
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…
Quadratic minimization: from conjugate gradient to an adaptive Heavy-ball method with Polyak step-sizes
Baptiste Goujaud, Adrien Taylor, Aymeric Dieuleveut
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…
Convergence of Proximal Point and Extragradient-Based Methods Beyond Monotonicity: the Case of Negative Comonotonicity
Eduard Gorbunov, Adrien Taylor, Samuel Horváth +1
Algorithms for min-max optimization and variational inequalities are often studied under monotonicity assumptions. Motivated by non-monotone machine learning applications, we follo…
Optimal first-order methods for convex functions with a quadratic upper bound
Baptiste Goujaud, Adrien Taylor, Aymeric Dieuleveut
We analyze worst-case convergence guarantees of first-order optimization methods over a function class extending that of smooth and convex functions. This class contains convex fun…
A systematic approach to Lyapunov analyses of continuous-time models in convex optimization
Céline Moucer, Adrien Taylor, Francis Bach
First-order methods are often analyzed via their continuous-time models, where their worst-case convergence properties are usually approached via Lyapunov functions. In this work,…
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…
Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalities
Eduard Gorbunov, Adrien Taylor, Gauthier Gidel
The Past Extragradient (PEG) [Popov, 1980] method, also known as the Optimistic Gradient method, has known a recent gain in interest in the optimization community with the emergenc…
PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python
Baptiste Goujaud, Céline Moucer, François Glineur +3
PEPit is a Python package aiming at simplifying the access to worst-case analyses of a large family of first-order optimization methods possibly involving gradient, projection, pro…
Super-Acceleration with Cyclical Step-sizes
Baptiste Goujaud, Damien Scieur, Aymeric Dieuleveut +2
We develop a convergence-rate analysis of momentum with cyclical step-sizes. We show that under some assumption on the spectral gap of Hessians in machine learning, cyclical step-s…
A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip
Mathieu Even, Raphaël Berthier, Francis Bach +5
We introduce the continuized Nesterov acceleration, a close variant of Nesterov acceleration whose variables are indexed by a continuous time parameter. The two variables continuou…
A Continuized View on Nesterov Acceleration
Raphaël Berthier, Francis Bach, Nicolas Flammarion +2
We introduce the "continuized" Nesterov acceleration, a close variant of Nesterov acceleration whose variables are indexed by a continuous time parameter. The two variables continu…
An optimal gradient method for smooth strongly convex minimization
Adrien Taylor, Yoel Drori
We present an optimal gradient method for smooth strongly convex optimization. The method is optimal in the sense that its worst-case bound on the distance to an optimal point exac…
On the oracle complexity of smooth strongly convex minimization
Yoel Drori, Adrien Taylor
We construct a family of functions suitable for establishing lower bounds on the oracle complexity of first-order minimization of smooth strongly-convex functions. Based on this co…
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…
Convergence of Constrained Anderson Acceleration
Mathieu Barré, Adrien Taylor, Alexandre d'Aspremont
We prove non asymptotic linear convergence rates for the constrained Anderson acceleration extrapolation scheme. These guarantees come from new upper bounds on the constrained Cheb…
Principled Analyses and Design of First-Order Methods with Inexact Proximal Operators
Mathieu Barré, Adrien Taylor, Francis Bach
Proximal operations are among the most common primitives appearing in both practical and theoretical (or high-level) optimization methods. This basic operation typically consists i…
Complexity Guarantees for Polyak Steps with Momentum
Mathieu Barré, Adrien Taylor, Alexandre d'Aspremont
In smooth strongly convex optimization, knowledge of the strong convexity parameter is critical for obtaining simple methods with accelerated rates. In this work, we study a class…
Optimal Complexity and Certification of Bregman First-Order Methods
Radu-Alexandru Dragomir, Adrien Taylor, Alexandre d'Aspremont +1
We provide a lower bound showing that the convergence rate of the NoLips method (a.k.a. Bregman Gradient) is optimal for the class of functions satisfying the -smoothne…
Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions
Adrien Taylor, Francis Bach
We provide a novel computer-assisted technique for systematically analyzing first-order methods for optimization. In contrast with previous works, the approach is particularly suit…