# Random feature approximation for general spectral methods

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 45 references that are in the map.
- First posted on arXiv 19 Jun 2025.

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

- [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)
- [An operator learning perspective on parameter-to-observable maps](https://mlsanity.com/paper/2402.06031/) (2024)
- [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)
- [How many Neurons do we need? A refined Analysis for Shallow Networks trained with Gradient Descent](https://mlsanity.com/paper/2309.08044/) (2023)
- [Optimal Convergence Rates for Neural Operators](https://mlsanity.com/paper/2412.17518/) (2024)

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

- [Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networks](https://mlsanity.com/paper/2606.06764/) (2026)
- [A Smoothed Discrepancy Principle for Random Feature Methods and Neural Networks](https://mlsanity.com/paper/2609.21017/) (2026)

## Abstract (arXiv)

Random feature approximation is arguably one of the most widely used techniques for kernel methods in large-scale learning algorithms. In this work, we analyze the generalization properties of random feature methods, extending previous results for Tikhonov regularization to a broad class of spectral regularization techniques. This includes not only explicit methods but also implicit schemes such as gradient descent and accelerated algorithms like the Heavy-Ball and Nesterov method. Through this framework, we enable a theoretical analysis of neural networks and neural operators through the lens of the Neural Tangent Kernel (NTK) approach trained via gradient descent. 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.