# Scalable Kernel Methods via Doubly Stochastic Gradients

arXiv: https://arxiv.org/abs/1407.5599 · HTML: https://mlsanity.com/paper/1407.5599/

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2014.

## Built on by (most cited first, 30 of 36)

- [LLaDA 1.5: Variance-Reduced Preference Optimization for Large Language Diffusion Models](https://mlsanity.com/paper/2505.19223/) (2025)
- [Provable Representation Learning for Imitation with Contrastive Fourier Features](https://mlsanity.com/paper/2105.12272/) (2021)
- [Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent](https://mlsanity.com/paper/2306.11589/) (2023)
- [A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learning](https://mlsanity.com/paper/2111.11485/) (2021)
- [Out-of-Distribution Generalization in Kernel Regression](https://mlsanity.com/paper/2106.02261/) (2021)
- [Stochastic Gradient Descent for Gaussian Processes Done Right](https://mlsanity.com/paper/2310.20581/) (2023)
- [Latent Variable Representation for Reinforcement Learning](https://mlsanity.com/paper/2212.08765/) (2022)
- [Diffusion Spectral Representation for Reinforcement Learning](https://mlsanity.com/paper/2406.16121/) (2024)
- [Robust, randomized preconditioning for kernel ridge regression](https://mlsanity.com/paper/2304.12465/) (2023)
- [Spectral risk-based learning using unbounded losses](https://mlsanity.com/paper/2105.04816/) (2021)
- [Quantization Algorithms for Random Fourier Features](https://mlsanity.com/paper/2102.13079/) (2021)
- [Efficient Parameter Optimisation for Quantum Kernel Alignment: A Sub-sampling Approach in Variational Training](https://mlsanity.com/paper/2401.02879/) (2024)
- [A Sparse Expansion For Deep Gaussian Processes](https://mlsanity.com/paper/2112.05888/) (2021)
- [Data Distribution Valuation](https://mlsanity.com/paper/2410.04386/) (2024)
- [Analysis of Kernel Mirror Prox for Measure Optimization](https://mlsanity.com/paper/2403.00147/) (2024)
- [Sharp Analysis of Random Fourier Features in Classification](https://mlsanity.com/paper/2109.10623/) (2021)
- [QC-ODKLA: Quantized and Communication-Censored Online Decentralized Kernel Learning via Linearized ADMM](https://mlsanity.com/paper/2208.02777/) (2022)
- [Stochastic Nonlinear Control via Finite-dimensional Spectral Dynamic Embedding](https://mlsanity.com/paper/2304.03907/) (2023)
- [Scalable spectral representations for multi-agent reinforcement learning in network MDPs](https://mlsanity.com/paper/2410.17221/) (2024)
- [Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems](https://mlsanity.com/paper/2112.14738/) (2021)
- [Demystifying SGD with Doubly Stochastic Gradients](https://mlsanity.com/paper/2406.00920/) (2024)
- [AmorLIP: Efficient Language-Image Pretraining via Amortization](https://mlsanity.com/paper/2505.18983/) (2025)
- [Fast and Scalable Adversarial Training of Kernel SVM via Doubly Stochastic Gradients](https://mlsanity.com/paper/2107.09937/) (2021)
- [Error Estimation for Random Fourier Features](https://mlsanity.com/paper/2302.11174/) (2023)
- [Unbiased Sliced Wasserstein Kernels for High-Quality Audio Captioning](https://mlsanity.com/paper/2502.05435/) (2025)
- [Joker: Joint Optimization Framework for Lightweight Kernel Machines](https://mlsanity.com/paper/2505.17765/) (2025)
- [Shallow Representation is Deep: Learning Uncertainty-aware and Worst-case Random Feature Dynamics](https://mlsanity.com/paper/2106.13066/) (2021)
- [Balanced Self-Paced Learning for AUC Maximization](https://mlsanity.com/paper/2207.03650/) (2022)
- [A Simple Algorithm For Scaling Up Kernel Methods](https://mlsanity.com/paper/2301.11414/) (2023)
- [Distributed Optimization via Kernelized Multi-armed Bandits](https://mlsanity.com/paper/2312.04719/) (2023)

## Abstract (arXiv)

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/√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.