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

By Siyuan Ma, Mikhail Belkin. 2017

81 citations recorded by the source corpus.

In this paper we first identify a basic limitation in gradient descent-based optimization methods when used in conjunctions with smooth kernels. An analysis based on the spectral properties of the kernel demonstrates that only a vanishingly small portion of the function space is reachable after a polynomial number of gradient descent iterations. This lack of approximating power drastically limits gradient descent for a fixed computational budget leading to serious over-regularization/underfitting. The issue is purely algorithmic, persisting even in the limit of infinite data. To address this shortcoming in practice, we introduce EigenPro iteration, based on a preconditioning scheme using a small number of approximately computed eigenvectors. It can also be viewed as learning a new kernel optimized for gradient descent. It turns out that injecting this small (computationally inexpensive and SGD-compatible) amount of approximate second-order information leads to major improvements in convergence. For large data, this translates into significant performance boost over the standard kernel methods. In particular, we are able to consistently match or improve the state-of-the-art results recently reported in the literature with a small fraction of their computational budget. Finally, we feel that these results show a need for a broader computational perspective on modern large-scale learning to complement more traditional statistical and convergence analyses. In particular, many phenomena of large-scale high-dimensional inference are best understood in terms of optimization on infinite dimensional Hilbert spaces, where standard algorithms can sometimes have properties at odds with finite-dimensional intuition. A systematic analysis concentrating on the approximation power of such algorithms within a budget of computation may lead to progress both in theory and practice.

Subfields: Artificial Intelligence, Computational Mechanics, Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Scaling & Learning Theory

Citations in the corpus

The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning (2017, methodology): “We give two examples: Laplace kernel trained using EigenPro [MB17] on MNIST [LBBH98] and on a subset (of size 5 · 104) of TIMIT [GLF+93].”
The Marginal Value of Adaptive Gradient Methods in Machine Learning (2017, background): “In a similar vein, Ma and Belkin [10] have shown that gradient methods may not be able to find complex solutions at all in any reasonable amount of time.”
On exponential convergence of SGD in non-convex over-parametrized learning (2018, background): “Furthermore, the distance to minimizer can be inﬁnite in many important settings, including optimization via logistic loss [12] or inverse problems over Hilbert spaces, as in kernel methods [9].”
On the Spectral Bias of Neural Networks (2018, background): “Ma & Belkin (2017) have further shown that for smooth kernels, a target function cannot be approximated within (cid:15) precision in any polynomial of 1 /(cid:15) steps by gradient descent.”
To understand deep learning we need to understand kernel learning (2018, methodology): “A remark on the importance of accelerated algorithms, hardware and SGD. Finally, we note that the experiments shown in this paper, particularly ﬁtting noisy labels with Gaussian ker-1 nels, would be difﬁcult to conduct without fast kernel training algorithms (we used EigenPro-SGD [MB17], which provi”