261 citations · 576 across the 22 of their papers we have counts for
24 papers
Differentiable Clustering with Perturbed Spanning Forests
Lawrence Stewart, Francis S Bach, Felipe Llinares López +1
We introduce a differentiable clustering method based on stochastic perturbations of minimum-weight spanning forests. This allows us to include clustering in end-to-end trainable p…
Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes
Marin Ballu, Quentin Berthet
Optimal transport is an important tool in machine learning, allowing to capture geometric properties of the data through a linear program on transport polytopes. We present a singl…
Regression as Classification: Influence of Task Formulation on Neural Network Features
Lawrence Stewart, Francis Bach, Quentin Berthet +1
Neural networks can be trained to solve regression problems by using gradient-based methods to minimize the square loss. However, practitioners often prefer to reformulate regressi…
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…
A unified software/hardware scalable architecture for brain-inspired computing based on self-organizing neural models
Artem R. Muliukov, Laurent Rodriguez, Benoit Miramond +4
The field of artificial intelligence has significantly advanced over the past decades, inspired by discoveries from the fields of biology and neuroscience. The idea of this work is…
Efficient and Modular Implicit Differentiation
Mathieu Blondel, Quentin Berthet, Marco Cuturi +5
Automatic differentiation (autodiff) has revolutionized machine learning. It allows to express complex computations by composing elementary ones in creative ways and removes the bu…
Self-Supervised Learning of Audio Representations from Permutations with Differentiable Ranking
Andrew N Carr, Quentin Berthet, Mathieu Blondel +2
Self-supervised pre-training using so-called "pretext" tasks has recently shown impressive performance across a wide range of modalities. In this work, we advance self-supervised l…
Stochastic Optimization for Regularized Wasserstein Estimators
Marin Ballu, Quentin Berthet, Francis Bach
Optimal transport is a foundational problem in optimization, that allows to compare probability distributions while taking into account geometric aspects. Its optimal objective val…
Fast Differentiable Sorting and Ranking
Mathieu Blondel, Olivier Teboul, Quentin Berthet +1
The sorting operation is one of the most commonly used building blocks in computer programming. In machine learning, it is often used for robust statistics. However, seen as a func…
Learning with Differentiable Perturbed Optimizers
Quentin Berthet, Mathieu Blondel, Olivier Teboul +3
Machine learning pipelines often rely on optimization procedures to make discrete decisions (e.g., sorting, picking closest neighbors, or shortest paths). Although these discrete d…
Minimax estimation of smooth densities in Wasserstein distance
Jonathan Niles-Weed, Quentin Berthet
We study nonparametric density estimation problems where error is measured in the Wasserstein distance, a metric on probability distributions popular in many areas of statistics an…
Regularized Contextual Bandits
Xavier Fontaine, Quentin Berthet, Vianney Perchet
We consider the stochastic contextual bandit problem with additional regularization. The motivation comes from problems where the policy of the agent must be close to some baseline…
Statistical Windows in Testing for the Initial Distribution of a Reversible Markov Chain
Quentin Berthet, Varun Kanade
We study the problem of hypothesis testing between two discrete distributions, where we only have access to samples after the action of a known reversible Markov chain, playing the…
Unsupervised Alignment of Embeddings with Wasserstein Procrustes
Edouard Grave, Armand Joulin, Quentin Berthet
We consider the task of aligning two sets of points in high dimension, which has many applications in natural language processing and computer vision. As an example, it was recentl…
Optimal link prediction with matrix logistic regression
Nicolai Baldin, Quentin Berthet
We consider the problem of link prediction, based on partial observation of a large network, and on side information associated to its vertices. The generative model is formulated…
Fast Rates for Bandit Optimization with Upper-Confidence Frank-Wolfe
Quentin Berthet, Vianney Perchet
We consider the problem of bandit optimization, inspired by stochastic optimization and online learning problems with bandit feedback. In this problem, the objective is to minimize…
Exact recovery in the Ising blockmodel
Quentin Berthet, Philippe Rigollet, Piyush Srivastava
We consider the problem associated to recovering the block structure of an Ising model given independent observations on the binary hypercube. This new model, called the Ising bloc…
Average-case Hardness of RIP Certification
Tengyao Wang, Quentin Berthet, Yaniv Plan
The restricted isometry property (RIP) for design matrices gives guarantees for optimal recovery in sparse linear models. It is of high interest in compressed sensing and statistic…
Detection of Planted Solutions for Flat Satisfiability Problems
Quentin Berthet, Jordan S. Ellenberg
We study the detection problem of finding planted solutions in random instances of flat satisfiability problems, a generalization of boolean satisfiability formulas. We describe th…
Resource Allocation for Statistical Estimation
Quentin Berthet, Venkat Chandrasekaran
Statistical estimation in many contemporary settings involves the acquisition, analysis, and aggregation of datasets from multiple sources, which can have significant differences i…
Statistical and computational trade-offs in estimation of sparse principal components
Tengyao Wang, Quentin Berthet, Richard J. Samworth
In recent years, sparse principal component analysis has emerged as an extremely popular dimension reduction technique for high-dimensional data. The theoretical challenge, in the…
Optimal Testing for Planted Satisfiability Problems
Quentin Berthet
We study the problem of detecting planted solutions in a random satisfiability formula. Adopting the formalism of hypothesis testing in statistical analysis, we describe the minima…
Computational Lower Bounds for Sparse PCA
Quentin Berthet, Philippe Rigollet
In the context of sparse principal component detection, we bring evidence towards the existence of a statistical price to pay for computational efficiency. We measure the performan…
Optimal detection of sparse principal components in high dimension
Quentin Berthet, Philippe Rigollet
We perform a finite sample analysis of the detection levels for sparse principal components of a high-dimensional covariance matrix. Our minimax optimal test is based on a sparse e…