48 citations · 130 across the 21 of their papers we have counts for
19 papers · 1 filter
ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization
Damien Scieur
We propose ABrA-GD (Adaptive Bregman Accelerated Gradient Descent), an adaptive algorithm for relatively smooth convex optimization. The algorithm is derived from a computable prim…
Strong Convexity of Sets in Riemannian Manifolds
Damien Scieur, David Martínez-Rubio, Thomas Kerdreux +2
Curvature properties of convex objects, such as strong convexity, are important in designing and analyzing convex optimization algorithms in the Hilbertian or Riemannian settings.…
Adaptive Quasi-Newton and Anderson Acceleration Framework with Explicit Global (Accelerated) Convergence Rates
Damien Scieur
Despite the impressive numerical performance of the quasi-Newton and Anderson/nonlinear acceleration methods, their global convergence rates have remained elusive for over 50 years…
The Curse of Unrolling: Rate of Differentiating Through Optimization
Damien Scieur, Quentin Bertrand, Gauthier Gidel +1
Computing the Jacobian of the solution of an optimization problem is a central problem in machine learning, with applications in hyperparameter optimization, meta-learning, optimiz…
Only Tails Matter: Average-Case Universality and Robustness in the Convex Regime
Leonardo Cunha, Gauthier Gidel, Fabian Pedregosa +2
The recently developed average-case analysis of optimization methods allows a more fine-grained and representative convergence analysis than usual worst-case results. In exchange,…
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…
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…
Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets
Thomas Kerdreux, Lewis Liu, Simon Lacoste-Julien +1
It is known that the Frank-Wolfe (FW) algorithm, which is affine-covariant, enjoys accelerated convergence rates when the constraint set is strongly convex. However, these results…
Generalization of Quasi-Newton Methods: Application to Robust Symmetric Multisecant Updates
Damien Scieur, Lewis Liu, Thomas Pumir +1
Quasi-Newton techniques approximate the Newton step by estimating the Hessian using the so-called secant equations. Some of these methods compute the Hessian using several secant e…
Average-case Acceleration for Bilinear Games and Normal Matrices
Carles Domingo-Enrich, Fabian Pedregosa, Damien Scieur
Advances in generative modeling and adversarial learning have given rise to renewed interest in smooth games. However, the absence of symmetry in the matrix of second derivatives p…
Average-case Acceleration Through Spectral Density Estimation
Fabian Pedregosa, Damien Scieur
We develop a framework for the average-case analysis of random quadratic problems and derive algorithms that are optimal under this analysis. This yields a new class of methods tha…
Universal Average-Case Optimality of Polyak Momentum
Damien Scieur, Fabian Pedregosa
Polyak momentum (PM), also known as the heavy-ball method, is a widely used optimization method that enjoys an asymptotic optimal worst-case complexity on quadratic objectives. How…
Generalized Framework for Nonlinear Acceleration
Damien Scieur
Nonlinear acceleration algorithms improve the performance of iterative methods, such as gradient descent, using the information contained in past iterates. However, their efficienc…
Nonlinear Acceleration of Momentum and Primal-Dual Algorithms
Raghu Bollapragada, Damien Scieur, Alexandre d'Aspremont
We describe convergence acceleration schemes for multistep optimization algorithms. The extrapolated solution is written as a nonlinear average of the iterates produced by the orig…
Nonlinear Acceleration of CNNs
Damien Scieur, Edouard Oyallon, Alexandre d'Aspremont +1
The Regularized Nonlinear Acceleration (RNA) algorithm is an acceleration method capable of improving the rate of convergence of many optimization schemes such as gradient descend,…
Online Regularized Nonlinear Acceleration
Damien Scieur, Edouard Oyallon, Alexandre d'Aspremont +1
Regularized nonlinear acceleration (RNA) estimates the minimum of a function by post-processing iterates from an algorithm such as the gradient method. It can be seen as a regulari…
Nonlinear Acceleration of Stochastic Algorithms
Damien Scieur, Alexandre d'Aspremont, Francis Bach
Extrapolation methods use the last few iterates of an optimization algorithm to produce a better estimate of the optimum. They were shown to achieve optimal convergence rates in a…
Integration Methods and Accelerated Optimization Algorithms
Damien Scieur, Vincent Roulet, Francis Bach +1
We show that accelerated optimization methods can be seen as particular instances of multi-step integration schemes from numerical analysis, applied to the gradient flow equation.…
Regularized Nonlinear Acceleration
Damien Scieur, Alexandre d'Aspremont, Francis Bach
We describe a convergence acceleration technique for unconstrained optimization problems. Our scheme computes estimates of the optimum from a nonlinear average of the iterates prod…