FALKON: An Optimal Large Scale Kernel Method
Kernel methods provide a principled way to perform non linear, nonparametric learning. They rely on solid functional analytic foundations and enjoy optimal statistical properties. However, at least in their basic form, they have limited applicability in large scale scenarios because of stringent computational requirements in terms of time and especially memory. In this paper, we take a substantial step in scaling up kernel methods, proposing FALKON, a novel algorithm that allows to efficiently process millions of points. FALKON is derived combining several algorithmic principles, namely stochastic subsampling, iterative solvers and preconditioning. Our theoretical analysis shows that optimal statistical accuracy is achieved requiring essentially O(n) memory and O(n √ n) time. An extensive experimental analysis on large scale datasets shows that, even with a single machine, FALKON outperforms previous state of the art solutions, which exploit parallel/distributed architectures.
Comments:
- line 19. "... the a variety of ..." -> "... a variety of ..."
- line 25. "... show that there are large class..." -> "... show that there is a large class..."
- line 113. "... that in this case t=sqrt(n)log(n) are needed to achieve..." I guess that the word "iterations" is missing? The same concern is with line 114
- Table 1. The last but one line in the table. There is a problem with a reference for "Nystrom + sgd"
- line 195. "Intuitevely, these conditions measure the size of H, if gamma is small then H is small rates are faster, and the regularity of f, if r is big f is
regular and rates are faster." -> "Intuitevely, these conditions measure the size of H (if gamma is small then H is small and rates are faster) and the regularity of f (if r is big f is regular and rates are faster)."?
- line 204. There should be a space between "O(1/n)." and "By selecting"
Conclusion:
1) In FALCON we need to use the number of inducing points M ~ sqrt(n). Thus in general we are limited in the number of inducing points we can use if n >> 1.
Gaussian Process regression is a probabilistic counterpart of the kernel ridge regression and provides the same regression function, as well as uncertainty quantification, not accessible in case of KRR. Sparse Gaussian Processes (in fact this is the Nystrom approximation), are used to process large samples. Recently, they propose to approximate not the GP model (using Nystrom approximation), but its posterior by optimizing evidence lower bound (ELBO), see 
https://www.prowler.io/sparse-gps-approximate-the-posterior-not-the-model/
Thus, by considering inducing points as latent variables, we can optimize ELBO to tune their values. By restricting the family of variational distributions and limiting inducing points to belong to some tensor (see applications of tensor methods for GP e.g. in "A. G. Wilson and H. Nickisch. Kernel interpolation for scalable structured gaussian processes // In International Conference on Machine Learning, pages 1775–1784, 2015", "E. Burnaev, M. Belyaev, E. Kapushev. Computationally efficient algorithm for Gaussian Processes based regression in case of structured samples // Computational Mathematics and Mathematical Physics, 2016, Vol. 56, No. 4, pp. 499–513, 2016") we can use tensor algebra to efficiently perform SGD optimization of ELBO even in case when M ~ n and so we can better approximate the posterior. Could the authors comment on this approach to kernel regression learning? What connections does ELBO optimization by SGD wrt inducing points may have with the proposed learning scheme?
2) The topic of the paper is important. The paper is well written and contains not only efficient algorithm, but also useful theoretical results. Do the authors have available programming code with results of experiments? It could be useful to specify a link to github with this code.