Reviews: Diving into the shallows: a computational perspective on large-scale shallow learning

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.