Scalable Kernel Methods via Doubly Stochastic Gradients

Abstract

The general perception is that kernel methods are not scalable, and neural nets are the methods of choice for nonlinear learning problems. Or have we simply not tried hard enough for kernel methods? Here we propose an approach that scales up kernel methods using a novel concept called "doubly stochastic functional gradients". Our approach relies on the fact that many kernel methods can be expressed as convex optimization problems, and we solve the problems by making two unbiased stochastic approximations to the functional gradient, one using random training points and another using random functions associated with the kernel, and then descending using this noisy functional gradient. We show that a function produced 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 performance of $O(1/\sqrt{t})$. This doubly stochasticity also allows us to avoid keeping the support vectors and to implement the algorithm in a small memory footprint, which is linear in number of iterations and independent of data dimension. Our approach can readily scale kernel methods up to the regimes which are dominated by neural nets. We show that our method can achieve competitive performance to neural nets in datasets such as 8 million handwritten digits from MNIST, 2.3 million energy materials from MolecularSpace, and 1 million photos from ImageNet.

32 pages, 22 figures

References in corpus (3)

• Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
• Deep Fried Convnets
• On Data Preconditioning for Regularized Loss Minimization

Cited by in corpus (26)

• Decentralized Online Learning with Kernels
• Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
• Structured adaptive and random spinners for fast machine learning computations
• The Deep Kernelized Autoencoder
• Variational Inference for Gaussian Process Models with Linear Complexity
• Learning from Conditional Distributions via Dual Embeddings
• Deep Fried Convnets
• Kernel Distributionally Robust Optimization
• Random Feature-based Online Multi-kernel Learning in Environments with Unknown Dynamics
• Local Group Invariant Representations via Orbit Embeddings
• On the Complexity of Learning with Kernels
• Provable Representation Learning for Imitation with Contrastive Fourier Features
• Density Matching Reward Learning
• On Kernel Derivative Approximation with Random Fourier Features
• Faster Kernel Ridge Regression Using Sketching and Preconditioning
• Deep Kernelized Autoencoders
• An $N\log N$ Parallel Fast Direct Solver for Kernel Matrices
• On Bochner's and Polya's Characterizations of Positive-Definite Kernels and the Respective Random Feature Maps
• Out-of-Distribution Generalization in Kernel Regression
• Doubly stochastic large scale kernel learning with the empirical kernel map
• Kernelized Classification in Deep Networks
• NYTRO: When Subsampling Meets Early Stopping
• SGD with Variance Reduction beyond Empirical Risk Minimization
• Not-So-Random Features
• Fuzzy Hashing as Perturbation-Consistent Adversarial Kernel Embedding
• Large-scale Kernel Methods and Applications to Lifelong Robot Learning