Random feature approximation for general spectral methods
This work provides theoretical insights for speeding up kernel methods and analyzing deep neural networks, but appears incremental as it builds on previous results in related settings.
The paper tackles the problem of analyzing generalization properties for spectral regularization methods combined with random features, including kernel methods with implicit or explicit regularization, and obtains optimal learning rates over regularity classes, even for those not in the reproducing kernel Hilbert space.
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.