  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.
