Scalable Kernel Methods via Doubly Stochastic Gradients

By Bo Dai, Bo Xie, Niao He, Yingyu Liang, Anant Raj, Maria-Florina Balcan, Le Song. 2014

238 citations recorded by the source corpus.

The general perception is that kernel methods are not scalable, so neural nets become the choice for large-scale nonlinear learning problems. Have we tried hard enough for kernel methods? In this paper, we propose an approach that scales up kernel methods using a novel concept called "doubly stochastic functional gradients". Based on the fact that many kernel methods can be expressed as convex optimization problems, our approach solves the optimization problems by making two unbiased stochastic approximations to the functional gradient—one using random training points and another using random features associated with the kernel—and performing descent steps with this noisy functional gradient. Our algorithm is simple, need no commit to a preset number of random features, and allows the flexibility of the function class to grow as we see more incoming data in the streaming setting. We demonstrate that a function learned by this procedure after t iterations converges to the optimal function in the reproducing kernel Hilbert space in rate O(1/t), and achieves a generalization bound of O(1/√t). Our approach can readily scale kernel methods up to the regimes which are dominated by neural nets. We show competitive performances of our approach as compared to neural nets in datasets such as 2.3 million energy materials from MolecularSpace, 8 million handwritten digits from MNIST, and 1 million photos from ImageNet using convolution features.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

On the Error of Random Fourier Features (2015, background): “Recent work has also exploited these embeddings in some of the most-scalable kernel methods to date (Dai et al. 2014).”
Kernel-Based Just-In-Time Learning for Passing Expectation Propagation Messages (2015, background): “A more efficient way to support a large number of random features is to store only the random seed used to generate the features, and to generate the coefficients on-the-fly as needed (Dai et al., 2014).”
Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels (2014, methodology): “ time, with O(ns) memory requirements. This technique is immensely successful, and has been used in recent years to obtain state-of-the-art accuracies for some classical datasets [Huang et al., 2014, Dai et al., 2014, Sindhwani and Avron, 2014, Lu et al., 2014]. The starting point of Rahimi and Rech”
Deep Fried Convnets (2014, methodology): “Our work is in line with recent interest in combining kernels with deep neural networks (Huang et al., 2014; Cho & Saul, 2009; Dai et al., 2014; Mairal et al., 2014).”
Boosting the Actor with Dual Critic (2017, methodology): “The RBF kernel bandwidth is chosen via median trick (Dai et al., 2014; Rajeswaran et al., 2017).”
Smoothed Dual Embedding Control (2017, methodology): “The RBF kernel bandwidth is chosen via median trick (Dai et al., 2014; Rajeswaran et al., 2017).”
Provable Representation Learning for Imitation with Contrastive Fourier Features (2021, background): “It is possible to extend the statement of Theorem 3 to generalized linear dynamics and reward models based on kernels by replacing the gradient in the bound with the functional gradient with respect to the kernel [16].”
Neural Kernels Without Tangents (2020, background): “Fortunately, recent work on kernel optimization (Ma & Belkin, 2018; Dai et al., 2014; Shankar et al., 2018; Wang et al., 2019) paves a way to scale our approach to larger datasets.”
Converting High-Dimensional Regression to High-Dimensional Conditional Density Estimation (2017, background): “[6]), then the resulting conditional density estimator will scale as well.”
On the Equivalence between Quadrature Rules and Random Features (2015, background): “…rates for non-parametric least-squares regression (Hsu et al., 2014) but with an improved computational complexity, and a study of the consequences of our improved approximation result for online learning and stochastic approximation, in the spirit of Dai et al. (2014); Dieuleveut and Bach (2014)”
Learning from Conditional Distributions via Dual Embeddings (2016, methodology): “Extended algorithms with random feature, doubly SGD (Dai et al., 2014), neural networks as well as their hybrid can be found in Appendix E.”
Less is More: Nyström Computational Regularization (2015, background): “Extensive experimental analysis shows that the considered approach achieves state of the art performances on benchmark large scale datasets.”
Learning from Conditional Distributions via Dual Kernel Embeddings (2016, methodology): “However, this can be avoided by exploiting random features and the “doubly” stochastic gradient idea introduced in [7].”
How to Scale Up Kernel Methods to Be As Good As Deep Neural Nets (2014, background): “In an upcoming paper, the authors there study how to use random features for online learning [14].”
On the Similarity between the Laplace and Neural Tangent Kernels (2020, methodology): “Exponential Kernels Specifications For the Laplace and Gaussian kernels, we searched for 10 kernel width values (1/c) from 2 × ν to ν in the log space with base 2, where ν is chosen heuristically as the median of pairwise l2 distances between data points (known as the median trick [19]).”
Learning with SGD and Random Features (2018, background): “A stochastic coordinate descent approach is considered in [21], see also [22, 23].”
A survey of randomized algorithms for training neural networks (2016, background): “Another research in [20] scaled up the kernel methods by a novel concept called “doubly stochastic functional gradient”.”