604 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- École Normale Supérieure - PSLFR41 papers
- Institut national de recherche en sciences et technologies du numériqueFR30 papers
- Département d'InformatiqueFR17 papers
- Centre National de la Recherche ScientifiqueFR6 papers
- Université Paris Sciences et LettresFR5 papers
- CentraleSupélecFR3 papers
- École Normale SupérieureBI3 papers
- Institut Polytechnique de ParisFR3 papers
- Laboratoire Traitement et Communication de l’InformationFR3 papers
- Massachusetts Institute of TechnologyUS3 papers
- CEA Paris-Saclay - Etablissement de SaclayFR2 papers
- Centre de Vision NumériqueFR2 papers
15 papers · 1 filter
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…
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…
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…
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…
On Lazy Training in Differentiable Programming
Lenaic Chizat, Edouard Oyallon, Francis Bach
In a series of recent theoretical works, it was shown that strongly over-parameterized neural networks trained with gradient-based methods could converge exponentially fast to zero…
Robust Seriation and Applications to Cancer Genomics
Antoine Recanati, Nicolas Servant, Jean-Philippe Vert +1
The seriation problem seeks to reorder a set of elements given pairwise similarity information, so that elements with higher similarity are closer in the resulting sequence. When a…
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,…
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…
Convergence Rate of Frank-Wolfe for Non-Convex Objectives
Simon Lacoste-Julien
We give a simple proof that the Frank-Wolfe algorithm obtains a stationary point at a rate of on non-convex objectives with a Lipschitz continuous gradient. Our ana…
Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression
Aymeric Dieuleveut, Nicolas Flammarion, Francis Bach
We consider the optimization of a quadratic objective function whose gradients are only accessible through a stochastic oracle that returns the gradient at any given point plus a z…
On the Global Linear Convergence of Frank-Wolfe Optimization Variants
Simon Lacoste-Julien, Martin Jaggi
The Frank-Wolfe (FW) optimization algorithm has lately re-gained popularity thanks in particular to its ability to nicely handle the structured constraints appearing in machine lea…
A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints
Nicolas Boumal
We propose a new algorithm to solve optimization problems of the form for a smooth function under the constraints that is positive semidefinite and the diagonal…
Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
Afonso S. Bandeira, Nicolas Boumal, Amit Singer
Maximum likelihood estimation problems are, in general, intractable optimization problems. As a result, it is common to approximate the maximum likelihood estimator (MLE) using con…
Low-rank optimization with trace norm penalty
B. Mishra, G. Meyer, F. Bach +1
The paper addresses the problem of low-rank trace norm minimization. We propose an algorithm that alternates between fixed-rank optimization and rank-one updates. The fixed-rank op…