109 citations · 280 across the 31 of their papers we have counts for
29 papers · 1 filter
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…
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…
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…
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…
Operator Splitting Performance Estimation: Tight contraction factors and optimal parameter selection
Ernest K. Ryu, Adrien B. Taylor, Carolina Bergeling +1
We propose a methodology for studying the performance of common splitting methods through semidefinite programming. We prove tightness of the methodology and demonstrate its value…
Lyapunov Functions for First-Order Methods: Tight Automated Convergence Guarantees
Adrien Taylor, Bryan Van Scoy, Laurent Lessard
We present a novel way of generating Lyapunov functions for proving linear convergence rates of first-order optimization methods. Our approach provably obtains the fastest linear c…
Efficient First-order Methods for Convex Minimization: a Constructive Approach
Yoel Drori, Adrien B. Taylor
We describe a novel constructive technique for devising efficient first-order methods for a wide range of large-scale convex minimization settings, including smooth, non-smooth, an…