63.6k citations · 104.5k across the 42 of their papers we have counts for
17 papers · 1 filter
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…
SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality
Courtney Paquette, Kiwon Lee, Fabian Pedregosa +1
We propose a new framework, inspired by random matrix theory, for analyzing the dynamics of stochastic gradient descent (SGD) when both number of samples and dimensions are large.…
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…
Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysis
Courtney Paquette, Bart van Merriënboer, Elliot Paquette +1
Average-case analysis computes the complexity of an algorithm averaged over all possible inputs. Compared to worst-case analysis, it is more representative of the typical behavior…
Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization
Geoffrey Négiar, Gideon Dresdner, Alicia Tsai +4
We propose a novel Stochastic Frank-Wolfe (a.k.a. conditional gradient) algorithm for constrained smooth finite-sum minimization with a generalized linear prediction/structure. Thi…
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…
Proximal Splitting Meets Variance Reduction
Fabian Pedregosa, Kilian Fatras, Mattia Casotto
Despite the rise to fame of incremental variance-reduced methods in recent years, their use in nonsmooth optimization is still limited to few simple cases. This is due to the fact…
Linearly Convergent Frank-Wolfe with Backtracking Line-Search
Fabian Pedregosa, Geoffrey Negiar, Armin Askari +1
Structured constraints in Machine Learning have recently brought the Frank-Wolfe (FW) family of algorithms back in the spotlight. While the classical FW algorithm has poor local co…
Frank-Wolfe Splitting via Augmented Lagrangian Method
Gauthier Gidel, Fabian Pedregosa, Simon Lacoste-Julien
Minimizing a function over an intersection of convex sets is an important task in optimization that is often much more challenging than minimizing it over each individual constrain…
Adaptive Three Operator Splitting
Fabian Pedregosa, Gauthier Gidel
We propose and analyze an adaptive step-size variant of the Davis-Yin three operator splitting. This method can solve optimization problems composed by a sum of a smooth term for w…
Frank-Wolfe with Subsampling Oracle
Thomas Kerdreux, Fabian Pedregosa, Alexandre d'Aspremont
We analyze two novel randomized variants of the Frank-Wolfe (FW) or conditional gradient algorithm. While classical FW algorithms require solving a linear minimization problem over…
Improved asynchronous parallel optimization analysis for stochastic incremental methods
Rémi Leblond, Fabian Pedregosa, Simon Lacoste-Julien
As datasets continue to increase in size and multi-core computer architectures are developed, asynchronous parallel optimization algorithms become more and more essential to the fi…
Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimization
Fabian Pedregosa, Rémi Leblond, Simon Lacoste-Julien
Due to their simplicity and excellent performance, parallel asynchronous variants of stochastic gradient descent have become popular methods to solve a wide range of large-scale op…
ASAGA: Asynchronous Parallel SAGA
Rémi Leblond, Fabian Pedregosa, Simon Lacoste-Julien
We describe ASAGA, an asynchronous parallel version of the incremental gradient algorithm SAGA that enjoys fast linear convergence rates. Through a novel perspective, we revisit an…