183 citations · 706 across the 60 of their papers we have counts for
11 papers · 1 filter
Massively scalable Sinkhorn distances via the Nyström method
Jason Altschuler, Francis Bach, Alessandro Rudi +1
The Sinkhorn "distance", a variant of the Wasserstein distance with entropic regularization, is an increasingly popular tool in machine learning and statistical inference. However,…
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…
On Fast Leverage Score Sampling and Optimal Learning
Alessandro Rudi, Daniele Calandriello, Luigi Carratino +1
Leverage score sampling provides an appealing way to perform approximate computations for large matrices. Indeed, it allows to derive faithful approximations with a complexity adap…
Approximating the Quadratic Transportation Metric in Near-Linear Time
Jason Altschuler, Francis Bach, Alessandro Rudi +1
Computing the quadratic transportation metric (also called the -Wasserstein distance or root mean square distance) between two point clouds, or, more generally, two discrete dis…
Learning with SGD and Random Features
Luigi Carratino, Alessandro Rudi, Lorenzo Rosasco
Sketching and stochastic gradient methods are arguably the most common techniques to derive efficient large scale learning algorithms. In this paper, we investigate their applicati…
Manifold Structured Prediction
Alessandro Rudi, Carlo Ciliberto, Gian Maria Marconi +1
Structured prediction provides a general framework to deal with supervised problems where the outputs have semantically rich structure. While classical approaches consider finite,…
Localized Structured Prediction
Carlo Ciliberto, Francis Bach, Alessandro Rudi
Key to structured prediction is exploiting the problem structure to simplify the learning process. A major challenge arises when data exhibit a local structure (e.g., are made by "…
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…
Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes
Loucas Pillaud-Vivien, Alessandro Rudi, Francis Bach
We consider stochastic gradient descent (SGD) for least-squares regression with potentially several passes over the data. While several passes have been widely reported to perform…
Approximating Hamiltonian dynamics with the Nyström method
Alessandro Rudi, Leonard Wossnig, Carlo Ciliberto +3
Simulating the time-evolution of quantum mechanical systems is BQP-hard and expected to be one of the foremost applications of quantum computers. We consider classical algorithms f…
Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces
Junhong Lin, Alessandro Rudi, Lorenzo Rosasco +1
In this paper, we study regression problems over a separable Hilbert space with the square loss, covering non-parametric regression over a reproducing kernel Hilbert space. We inve…