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.

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.

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.