48 citations · 130 across the 21 of their papers we have counts for
24 papers
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.…
SING: A Plug-and-Play DNN Learning Technique
Adrien Courtois, Damien Scieur, Jean-Michel Morel +2
We propose SING (StabIlized and Normalized Gradient), a plug-and-play technique that improves the stability and generalization of the Adam(W) optimizer. SING is straightforward to…
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,…
Convergence Rates for the MAP of an Exponential Family and Stochastic Mirror Descent -- an Open Problem
Rémi Le Priol, Frederik Kunstner, Damien Scieur +1
We consider the problem of upper bounding the expected log-likelihood sub-optimality of the maximum likelihood estimate (MLE), or a conjugate maximum a posteriori (MAP) for an expo…
Connecting Sphere Manifolds Hierarchically for Regularization
Damien Scieur, Youngsung Kim
This paper considers classification problems with hierarchically organized classes. We force the classifier (hyperplane) of each class to belong to a sphere manifold, whose center…
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…
Accelerating Smooth Games by Manipulating Spectral Shapes
Waïss Azizian, Damien Scieur, Ioannis Mitliagkas +2
We use matrix iteration theory to characterize acceleration in smooth games. We define the spectral shape of a family of games as the set containing all eigenvalues of the Jacobian…
Extragradient with player sampling for faster Nash equilibrium finding
Carles Domingo Enrich, Samy Jelassi, Carles Domingo-Enrich +3
Data-driven modeling increasingly requires to find a Nash equilibrium in multi-player games, e.g. when training GANs. In this paper, we analyse a new extra-gradient method for Nash…
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…