# Random feature approximation for general spectral methods

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 45 references that are in the map.
- First posted on arXiv 29 Aug 2023.

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

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes](https://mlsanity.com/paper/1805.10074/) (2018)
- [Optimal Rates For Regularization Of Statistical Inverse Learning Problems](https://mlsanity.com/paper/1604.04054/) (2016)
- [Global convergence of the Heavy-ball method for convex optimization](https://mlsanity.com/paper/1412.7457/) (2014)
- [Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces](https://mlsanity.com/paper/1801.06720/) (2018)
- [Every Model Learned by Gradient Descent Is Approximately a Kernel Machine](https://mlsanity.com/paper/2012.00152/) (2020)
- [Stochastic Heavy Ball](https://mlsanity.com/paper/1609.04228/) (2016)
- [Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime](https://mlsanity.com/paper/2006.12297/) (2020)
- [Learning with SGD and Random Features](https://mlsanity.com/paper/1807.06343/) (2018)
- [The Future is Log-Gaussian: ResNets and Their Infinite-Depth-and-Width Limit at Initialization](https://mlsanity.com/paper/2106.04013/) (2021)
- [On the Optimality of Misspecified Spectral Algorithms](https://mlsanity.com/paper/2303.14942/) (2023)
- [Error Bounds for Learning with Vector-Valued Random Features](https://mlsanity.com/paper/2305.17170/) (2023)
- [Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms](https://mlsanity.com/paper/1801.07226/) (2018)
- [Learning to Learn Kernels with Variational Random Features](https://mlsanity.com/paper/2006.06707/) (2020)
- [Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis](https://mlsanity.com/paper/2206.12802/) (2022)
- [Implicit Regularization of Accelerated Methods in Hilbert Spaces](https://mlsanity.com/paper/1905.13000/) (2019)
- [Statistical Optimality and Computational Efficiency of Nystr"om Kernel PCA](https://mlsanity.com/paper/2105.08875/) (2021)

## Abstract (arXiv)

Random feature approximation is arguably one of the most popular techniques to speed up kernel methods in large scale algorithms and provides a theoretical approach to the analysis of deep neural networks. We analyze generalization properties for a large class of spectral regularization methods combined with random features, containing kernel methods with implicit regularization such as gradient descent or explicit methods like Tikhonov regularization. For our estimators we obtain optimal learning rates over regularity classes (even for classes that are not included in the reproducing kernel Hilbert space), which are defined through appropriate source conditions. This improves or completes previous results obtained in related settings for specific kernel algorithms.