# StreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 71 references that are in the map.
- First posted on arXiv 23 Aug 2021.

## Builds on (most cited first, 14 of 14)

- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [FALKON: An Optimal Large Scale Kernel Method](https://mlsanity.com/paper/1705.10958/) (2017)
- [Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates](https://mlsanity.com/paper/1305.5029/) (2013)
- [Faster Kernel Ridge Regression Using Sketching and Preconditioning](https://mlsanity.com/paper/1611.03220/) (2016)
- [A la Carte - Learning Fast Kernels](https://mlsanity.com/paper/1412.6493/) (2014)
- [Convergence of Graph Laplacian with kNN Self-tuned Kernels](https://mlsanity.com/paper/2011.01479/) (2020)
- [Conformalized Kernel Ridge Regression](https://mlsanity.com/paper/1609.05959/) (2016)
- [Kernel Least Mean Square with Adaptive Kernel Size](https://mlsanity.com/paper/1401.5899/) (2014)
- [Multiscale regression on unknown manifolds](https://mlsanity.com/paper/2101.05119/) (2021)
- [A Comparative Study of Pairwise Learning Methods based on Kernel Ridge Regression](https://mlsanity.com/paper/1803.01575/) (2018)
- [Natural Graph Wavelet Packet Dictionaries](https://mlsanity.com/paper/2009.09020/) (2020)
- [Properties of Laplacian Pyramids for Extension and Denoising](https://mlsanity.com/paper/1909.07974/) (2019)
- [Sigma-Delta and Distributed Noise-Shaping Quantization Methods for Random Fourier Features](https://mlsanity.com/paper/2106.02614/) (2021)
- [Construction and Monte Carlo estimation of wavelet frames generated by a reproducing kernel](https://mlsanity.com/paper/2006.09870/) (2020)

## Abstract (arXiv)

Kernel ridge regression (KRR) is a popular scheme for non-linear non-parametric learning. However, existing implementations of KRR require that all the data is stored in the main memory, which severely limits the use of KRR in contexts where data size far exceeds the memory size. Such applications are increasingly common in data mining, bioinformatics, and control. A powerful paradigm for computing on data sets that are too large for memory is the streaming model of computation, where we process one data sample at a time, discarding each sample before moving on to the next one. In this paper, we propose StreaMRAK - a streaming version of KRR. StreaMRAK improves on existing KRR schemes by dividing the problem into several levels of resolution, which allows continual refinement to the predictions. The algorithm reduces the memory requirement by continuously and efficiently integrating new samples into the training model. With a novel sub-sampling scheme, StreaMRAK reduces memory and computational complexities by creating a sketch of the original data, where the sub-sampling density is adapted to the bandwidth of the kernel and the local dimensionality of the data. We present a showcase study on two synthetic problems and the prediction of the trajectory of a double pendulum. The results show that the proposed algorithm is fast and accurate.