publications

2023

1. NeurIPS23 Spotlight

   GloptiNets: Scalable Non-Convex Optimization with Certificates

   Gaspard Beugnot, Julien Mairal, and Alessandro Rudi

   2023

   arXiv HTML Video

2022

1. COLT22

   On the Benefits of Large Learning Rates for Kernel Methods

   Gaspard Beugnot, Julien Mairal, and Alessandro Rudi

   2022

   Abs arXiv PDF

   This paper studies an intriguing phenomenon related to the good generalization performance of estimators obtained by using large learning rates within gradient descent algorithms. First observed in the deep learning literature, we show that a phenomenon can be precisely characterized in the context of kernel methods, even though the resulting optimization problem is convex. Specifically, we consider the minimization of a quadratic objective in a separable Hilbert space, and show that with early stopping, the choice of learning rate influences the spectral decomposition of the obtained solution on the Hessian’s eigenvectors. This extends an intuition described by Nakkiran (2020) on a two-dimensional toy problem to realistic learning scenarios such as kernel ridge regression. While large learning rates may be proven beneficial as soon as there is a mismatch between the train and test objectives, we further explain why it already occurs in classification tasks without assuming any particular mismatch between train and test data distributions.

2021

1. NeurIPS21 Spotlight

   Beyond Tikhonov: faster learning with self-concordant losses, via iterative regularization

   Gaspard Beugnot, Julien Mairal, and Alessandro Rudi

   In Advances in Neural Information Processing Systems, 2021

   Abs HTML PDF Video

   The theory of spectral filtering is a remarkable tool to understand the statistical properties of learning with kernels. For least squares, it allows to derive various regularization schemes that yield faster convergence rates of the excess risk than with Tikhonov regularization. This is typically achieved by leveraging classical assumptions called source and capacity conditions, which characterize the difficulty of the learning task. In order to understand estimators derived from other loss functions, Marteau-Ferey et al. have extended the theory of Tikhonov regularization to generalized self concordant loss functions (GSC), which contain, e.g., the logistic loss. In this paper, we go a step further and show that fast and optimal rates can be achieved for GSC by using the iterated Tikhonov regularization scheme, which is intrinsically related to the proximal point method in optimization, and overcomes the limitation of the classical Tikhonov regularization.

2. UAI21

   Improving approximate optimal transport distances using quantization

   Gaspard Beugnot, Aude Genevay, Kristjan Greenewald, and 1 more author

   In Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, 27–30 jul 2021

   Abs PDF

   Optimal transport (OT) is a popular tool in machine learning to compare probability measures geometrically, but it comes with substantial computational burden. Linear programming algorithms for computing OT distances scale cubically in the size of the input, making OT impractical in the large-sample regime. We introduce a practical algorithm, which relies on a quantization step, to estimate OT distances between measures given cheap sample access. We also provide a variant of our algorithm to improve the performance of approximate solvers, focusing on those for entropy-regularized transport. We give theoretical guarantees on the benefits of this quantization step and display experiments showing that it behaves well in practice, providing a practical approximation algorithm that can be used as a drop-in replacement for existing OT estimators.