# Parsimonious Online Learning with Kernels via Sparse Projections in Function Space

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Dec 2016.

## Built on by (most cited first, 13 of 13)

- [Online, Informative MCMC Thinning with Kernelized Stein Discrepancy](https://mlsanity.com/paper/2201.07130/) (2022)
- [QC-ODKLA: Quantized and Communication-Censored Online Decentralized Kernel Learning via Linearized ADMM](https://mlsanity.com/paper/2208.02777/) (2022)
- [Distributed Gradient Descent for Functional Learning](https://mlsanity.com/paper/2305.07408/) (2023)
- [Nonparametric Sparse Online Learning of the Koopman Operator](https://mlsanity.com/paper/2405.07432/) (2024)
- [Multistage Stochastic Optimization via Kernels](https://mlsanity.com/paper/2303.06515/) (2023)
- [Composable Learning with Sparse Kernel Representations](https://mlsanity.com/paper/2103.14474/) (2021)
- [Random Feature Approximation for Online Nonlinear Graph Topology Identification](https://mlsanity.com/paper/2110.09935/) (2021)
- [Ahpatron: A New Budgeted Online Kernel Learning Machine with Tighter Mistake Bound](https://mlsanity.com/paper/2312.07032/) (2023)
- [Stochastic Gradient Descent for Nonparametric Additive Regression](https://mlsanity.com/paper/2401.00691/) (2024)
- [A Tensor Low-Rank Approximation for Value Functions in Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2501.10529/) (2025)
- [Nonparametric Sparse Online Learning of the Koopman Operator](https://mlsanity.com/paper/2501.16489/) (2025)
- [Binary Kernel Logistic Regression: a sparsity-inducing formulation and a convergent decomposition training algorithm](https://mlsanity.com/paper/2512.19440/) (2025)
- [Deep kernel hedging](https://mlsanity.com/paper/2609.34474/) (2026)

## Abstract (arXiv)

Despite their attractiveness, popular perception is that techniques for nonparametric function approximation do not scale to streaming data due to an intractable growth in the amount of storage they require. To solve this problem in a memory-affordable way, we propose an online technique based on functional stochastic gradient descent in tandem with supervised sparsification based on greedy function subspace projections. The method, called parsimonious online learning with kernels (POLK), provides a controllable tradeoff? between its solution accuracy and the amount of memory it requires. We derive conditions under which the generated function sequence converges almost surely to the optimal function, and we establish that the memory requirement remains finite. We evaluate POLK for kernel multi-class logistic regression and kernel hinge-loss classification on three canonical data sets: a synthetic Gaussian mixture model, the MNIST hand-written digits, and the Brodatz texture database. On all three tasks, we observe a favorable tradeoff of objective function evaluation, classification performance, and complexity of the nonparametric regressor extracted the proposed method.