Timezone: »
Poster
FALKON: An Optimal Large Scale Kernel Method
Alessandro Rudi · Luigi Carratino · Lorenzo Rosasco
Kernel methods provide a principled way to perform non linear, nonparametric learning. They rely on solid functional analytic foundations and enjoy optimal statistical properties. However, at least in their basic form, they have limited applicability in large scale scenarios because of stringent computational requirements in terms of time and especially memory. In this paper, we take a substantial step in scaling up kernel methods, proposing FALKON, a novel algorithm that allows to efficiently process millions of points. FALKON is derived combining several algorithmic principles, namely stochastic subsampling, iterative solvers and preconditioning. Our theoretical analysis shows that optimal statistical accuracy is achieved requiring essentially $O(n)$ memory and $O(n\sqrt{n})$ time. An extensive experimental analysis on large scale datasets shows that, even with a single machine, FALKON outperforms previous state of the art solutions, which exploit parallel/distributed architectures.
Author Information
Alessandro Rudi (École Normale Supérieure, INRIA)
Luigi Carratino (University of Genoa)
Lorenzo Rosasco (University of Genova- MIT - IIT)
More from the Same Authors
-
2021 Spotlight: Mixability made efficient: Fast online multiclass logistic regression »
Rémi Jézéquel · Pierre Gaillard · Alessandro Rudi -
2021 Spotlight: Beyond Tikhonov: faster learning with self-concordant losses, via iterative regularization »
Gaspard Beugnot · Julien Mairal · Alessandro Rudi -
2022 : Scalable Causal Discovery with Score Matching »
Francesco Montagna · Nicoletta Noceti · Lorenzo Rosasco · Kun Zhang · Francesco Locatello -
2023 Poster: Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models »
Anant Raj · Umut Simsekli · Alessandro Rudi -
2023 Poster: GloptiNets: Scalable Non-Convex Optimization with Certificates »
Gaspard Beugnot · Julien Mairal · Alessandro Rudi -
2023 Poster: Structured Zeroth-order for Non-smooth Optimization »
Marco Rando · Cesare Molinari · Lorenzo Rosasco · Silvia Villa -
2023 Poster: Assumption violations in causal discovery and the robustness of score matching »
Francesco Montagna · Atalanti Mastakouri · Elias Eulig · Nicoletta Noceti · Lorenzo Rosasco · Dominik Janzing · Bryon Aragam · Francesco Locatello -
2023 Poster: Estimating Koopman operators with sketching to provably learn large scale dynamical systems »
Giacomo Meanti · Antoine Chatalic · Vladimir Kostic · Pietro Novelli · Massimiliano Pontil · Lorenzo Rosasco -
2022 Poster: Learning Dynamical Systems via Koopman Operator Regression in Reproducing Kernel Hilbert Spaces »
Vladimir Kostic · Pietro Novelli · Andreas Maurer · Carlo Ciliberto · Lorenzo Rosasco · Massimiliano Pontil -
2022 Poster: Active Labeling: Streaming Stochastic Gradients »
Vivien Cabannes · Francis Bach · Vianney Perchet · Alessandro Rudi -
2021 Poster: ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions »
Luigi Carratino · Stefano Vigogna · Daniele Calandriello · Lorenzo Rosasco -
2021 Poster: Mixability made efficient: Fast online multiclass logistic regression »
Rémi Jézéquel · Pierre Gaillard · Alessandro Rudi -
2021 Poster: Overcoming the curse of dimensionality with Laplacian regularization in semi-supervised learning »
Vivien Cabannes · Loucas Pillaud-Vivien · Francis Bach · Alessandro Rudi -
2021 Poster: PSD Representations for Effective Probability Models »
Alessandro Rudi · Carlo Ciliberto -
2021 Poster: Beyond Tikhonov: faster learning with self-concordant losses, via iterative regularization »
Gaspard Beugnot · Julien Mairal · Alessandro Rudi -
2020 Poster: Kernel Methods Through the Roof: Handling Billions of Points Efficiently »
Giacomo Meanti · Luigi Carratino · Lorenzo Rosasco · Alessandro Rudi -
2020 Oral: Kernel Methods Through the Roof: Handling Billions of Points Efficiently »
Giacomo Meanti · Luigi Carratino · Lorenzo Rosasco · Alessandro Rudi -
2019 Poster: Implicit Regularization of Accelerated Methods in Hilbert Spaces »
Nicolò Pagliana · Lorenzo Rosasco -
2019 Poster: Beating SGD Saturation with Tail-Averaging and Minibatching »
Nicole Muecke · Gergely Neu · Lorenzo Rosasco -
2018 Poster: On Fast Leverage Score Sampling and Optimal Learning »
Alessandro Rudi · Daniele Calandriello · Luigi Carratino · Lorenzo Rosasco -
2018 Poster: Statistical and Computational Trade-Offs in Kernel K-Means »
Daniele Calandriello · Lorenzo Rosasco -
2018 Poster: Learning with SGD and Random Features »
Luigi Carratino · Alessandro Rudi · Lorenzo Rosasco -
2018 Spotlight: Statistical and Computational Trade-Offs in Kernel K-Means »
Daniele Calandriello · Lorenzo Rosasco -
2018 Spotlight: Learning with SGD and Random Features »
Luigi Carratino · Alessandro Rudi · Lorenzo Rosasco -
2018 Poster: Dirichlet-based Gaussian Processes for Large-scale Calibrated Classification »
Dimitrios Milios · Raffaello Camoriano · Pietro Michiardi · Lorenzo Rosasco · Maurizio Filippone -
2018 Poster: Manifold Structured Prediction »
Alessandro Rudi · Carlo Ciliberto · Gian Maria Marconi · Lorenzo Rosasco -
2017 Poster: Generalization Properties of Learning with Random Features »
Alessandro Rudi · Lorenzo Rosasco -
2017 Oral: Generalization Properties of Learning with Random Features »
Alessandro Rudi · Lorenzo Rosasco -
2017 Poster: Consistent Multitask Learning with Nonlinear Output Relations »
Carlo Ciliberto · Alessandro Rudi · Lorenzo Rosasco · Massimiliano Pontil -
2016 Poster: A Consistent Regularization Approach for Structured Prediction »
Carlo Ciliberto · Lorenzo Rosasco · Alessandro Rudi -
2016 Poster: Optimal Learning for Multi-pass Stochastic Gradient Methods »
Junhong Lin · Lorenzo Rosasco -
2015 Poster: Learning with Incremental Iterative Regularization »
Lorenzo Rosasco · Silvia Villa -
2015 Poster: Less is More: Nyström Computational Regularization »
Alessandro Rudi · Raffaello Camoriano · Lorenzo Rosasco -
2015 Oral: Less is More: Nyström Computational Regularization »
Alessandro Rudi · Raffaello Camoriano · Lorenzo Rosasco -
2013 Workshop: Modern Nonparametric Methods in Machine Learning »
Arthur Gretton · Mladen Kolar · Samory Kpotufe · John Lafferty · Han Liu · Bernhard Schölkopf · Alexander Smola · Rob Nowak · Mikhail Belkin · Lorenzo Rosasco · peter bickel · Yue Zhao -
2013 Poster: On the Sample Complexity of Subspace Learning »
Alessandro Rudi · Guillermo D Canas · Lorenzo Rosasco -
2012 Poster: Learning Manifolds with K-Means and K-Flats »
Guillermo D Canas · Tomaso Poggio · Lorenzo Rosasco -
2012 Poster: Multiclass Learning with Simplex Coding »
Youssef Mroueh · Tomaso Poggio · Lorenzo Rosasco · Jean-Jacques Slotine -
2012 Poster: Learning Probability Measures with respect to Optimal Transport Metrics »
Guillermo D Canas · Lorenzo Rosasco -
2010 Poster: A Primal-Dual Algorithm for Group Sparse Regularization with Overlapping Groups »
Sofia Mosci · Silvia Villa · Alessandro Verri · Lorenzo Rosasco -
2010 Poster: Spectral Regularization for Support Estimation »
Ernesto De Vito · Lorenzo Rosasco · Alessandro Toigo -
2009 Workshop: Kernels for Multiple Outputs and Multi-task Learning: Frequentist and Bayesian Points of View »
Mauricio A Alvarez · Lorenzo Rosasco · Neil D Lawrence -
2009 Poster: On Invariance in Hierarchical Models »
Jake Bouvrie · Lorenzo Rosasco · Tomaso Poggio