Reviews: Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Acceleration

The algorithm essentially selects a random subset of training points and learns a (truncated) kernel ridge regression function on the selected subset. Under certain characteristic assumptions on the complexity of the function class in which the optimal function lies and on the complexity of the RKHS, the paper shows that the algorithm achieves optimal generalization guarantees. This is an improvement over the existing results in this setting in one of the regimes of the problem space. Additionally, the authors show that under a zero Bayes risk condition, the algorithm achieves a faster convergence rate to the Bayes risk. The main contribution of the paper lies in adapting the proof techniques used in the online kernel regression literature to the standard kernel regression setting.