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
53 papers
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…
On the Consistency of Max-Margin Losses
Alex Nowak-Vila, Alessandro Rudi, Francis Bach
The foundational concept of Max-Margin in machine learning is ill-posed for output spaces with more than two labels such as in structured prediction. In this paper, we show that th…
Self-Supervised VQ-VAE for One-Shot Music Style Transfer
Ondřej Cífka, Alexey Ozerov, Umut Şimşekli +1
Neural style transfer, allowing to apply the artistic style of one image to another, has become one of the most widely showcased computer vision applications shortly after its intr…
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…
Learning Output Embeddings in Structured Prediction
Luc Brogat-Motte, Alessandro Rudi, Céline Brouard +2
A powerful and flexible approach to structured prediction consists in embedding the structured objects to be predicted into a feature space of possibly infinite dimension by means…
Music Source Separation in the Waveform Domain
Alexandre Défossez, Nicolas Usunier, Léon Bottou +1
Source separation for music is the task of isolating contributions, or stems, from different instruments recorded individually and arranged together to form a song. Such components…
Ranking and synchronization from pairwise measurements via SVD
Alexandre d'Aspremont, Mihai Cucuringu, Hemant Tyagi
Given a measurement graph and an unknown signal , we investigate algorithms for recovering from pairwise measurements of the form ; $\…
Regularity as Regularization: Smooth and Strongly Convex Brenier Potentials in Optimal Transport
François-Pierre Paty, Alexandre d'Aspremont, Marco Cuturi
Estimating Wasserstein distances between two high-dimensional densities suffers from the curse of dimensionality: one needs an exponential (wrt dimension) number of samples to ensu…
Partially Encrypted Machine Learning using Functional Encryption
Theo Ryffel, Edouard Dufour-Sans, Romain Gay +2
Machine learning on encrypted data has received a lot of attention thanks to recent breakthroughs in homomorphic encryption and secure multi-party computation. It allows outsourcin…
Affine Invariant Covariance Estimation for Heavy-Tailed Distributions
Dmitrii Ostrovskii, Alessandro Rudi
In this work we provide an estimator for the covariance matrix of a heavy-tailed multivariate distributionWe prove that the proposed estimator admits an \tex…
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…
Sharp Analysis of Learning with Discrete Losses
Alex Nowak-Vila, Francis Bach, Alessandro Rudi
The problem of devising learning strategies for discrete losses (e.g., multilabeling, ranking) is currently addressed with methods and theoretical analyses ad-hoc for each loss. In…
Sample Complexity of Sinkhorn divergences
Aude Genevay, Lénaic Chizat, Francis Bach +2
Optimal transport (OT) and maximum mean discrepancies (MMD) are now routinely used in machine learning to compare probability measures. We focus in this paper on \emph{Sinkhorn div…
A Kernel Perspective for Regularizing Deep Neural Networks
Alberto Bietti, Grégoire Mialon, Dexiong Chen +1
We propose a new point of view for regularizing deep neural networks by using the norm of a reproducing kernel Hilbert space (RKHS). Even though this norm cannot be computed, it ad…
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,…
Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distance
Giulia Luise, Alessandro Rudi, Massimiliano Pontil +1
Applications of optimal transport have recently gained remarkable attention thanks to the computational advantages of entropic regularization. However, in most situations the Sinkh…
Constant Step Size Stochastic Gradient Descent for Probabilistic Modeling
Dmitry Babichev, Francis Bach
Stochastic gradient methods enable learning probabilistic models from large amounts of data. While large step-sizes (learning rates) have shown to be best for least-squares (e.g.,…
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…
Sustainable computational science: the ReScience initiative
Nicolas P. Rougier, Konrad Hinsen, Frédéric Alexandre +42
Computer science offers a large set of tools for prototyping, writing, running, testing, validating, sharing and reproducing results, however computational science lags behind. In…
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…