Diving into the shallows: a computational perspective on large-scale shallow learning
Remarkable recent success of deep neural networks has not been easy to analyze theoretically. It has been particularly hard to disentangle relative significance of architecture and optimization in achieving accurate classification on large datasets. On the flip side, shallow methods (such as kernel methods) have encountered obstacles in scaling to large data, despite excellent performance on smaller datasets, and extensive theoretical analysis. Practical methods, such as variants of gradient descent used so successfully in deep learning, seem to perform below par when applied to kernel methods. This difficulty has sometimes been attributed to the limitations of shallow architecture. In this paper we identify a basic limitation in gradient descent-based optimization methods when used in conjunctions with smooth kernels. Our analysis demonstrates that only a vanishingly small fraction of the function space is reachable after a polynomial number of gradient descent iterations. That drastically limits the approximating power of gradient descent leading to over-regularization. The issue is purely algorithmic, persisting even in the limit of infinite data. To address this shortcoming in practice, we introduce EigenPro iteration, a simple and direct preconditioning scheme using a small number of approximately computed eigenvectors. It can also be viewed as learning a kernel optimized for gradient descent. Injecting this small, computationally inexpensive and SGD-compatible, amount of approximate second-order information leads to major improvements in convergence. For large data, this leads to a significant performance boost over the state-of-the-art kernel methods. In particular, we are able to match or improve the results reported in the literature at a small fraction of their computational budget. For complete version of this paper see https://arxiv.org/abs/1703.10622.
This paper looks at analyzing the problem of long times required for convergence of kernel methods when optimized via gradient descent. They define a notion of computational reach of gradient descent after t iterations and the failure of gradient descent to reach the epsilon neighborhood of an optimum after t iterations. They give examples of simplistic function settings with binary labels where gradient descent takes a long time to converge to the optimum. They also point out that adding regularization improves the condition number of the eigenspectrum (resulting in possible better convergence) but also leads to overregularization at times.
They introduce the notion of EigenPro, where they pre-multiply the data using a preconditioner matrix, which can be pre-computed, improves the time for convergence by making the lower eigenvalues closer to the largest one as well as making cost per iteration efficient. They do a randomized SVD of the data matrix/kernel operator to get the eigenvalues and generate the pre-conditioning matrix using the ratio of the eigenvalues.They show that the per-iteration time is not much higher than kernel methods and demonstrate experiments to show that the errors are minimized better than standard kernel methods using less GPU time overall. The acceleration provided is significant for some of the Kernels. 
The paper is dense in presentation but is well written and not very difficult to follow. However there would be a lot of details that can be provided to compare how the pre-conditioning matrix can influence gradient descent in general and whether it should always be applied to data matrices every time we try to train a linear model on data. The authors also provide the argument of how lowering the ratio of the smaller eigenvalues compared to the larger one makes the problem more amenable to convergence. It would be good to see some motivation/geometric description of how the method provides better convergence using gradient descent. It would also be interesting to explore if other faster algorithms including proximal methods as well as momentum based methods also can benefit from such pre-conditioning and can improve the rates of convergence for kernel methods.