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

arXiv: https://arxiv.org/abs/1703.10622 · HTML: https://mlsanity.com/paper/1703.10622/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Mar 2017.

## Built on by (most cited first, 30 of 31)

- [Discover and Cure: Concept-aware Mitigation of Spurious Correlation](https://mlsanity.com/paper/2305.00650/) (2023)
- [Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2112.03968/) (2021)
- [Benign, Tempered, or Catastrophic: A Taxonomy of Overfitting](https://mlsanity.com/paper/2207.06569/) (2022)
- [Mechanism of feature learning in deep fully connected networks and kernel machines that recursively learn features](https://mlsanity.com/paper/2212.13881/) (2022)
- [Interpolating Classifiers Make Few Mistakes](https://mlsanity.com/paper/2101.11815/) (2021)
- [Simple, Fast, and Flexible Framework for Matrix Completion with Infinite Width Neural Networks](https://mlsanity.com/paper/2108.00131/) (2021)
- [xRFM: Accurate, scalable, and interpretable feature learning models for tabular data](https://mlsanity.com/paper/2508.10053/) (2025)
- [Toward Large Kernel Models](https://mlsanity.com/paper/2302.02605/) (2023)
- [Kernel Regression with Infinite-Width Neural Networks on Millions of Examples](https://mlsanity.com/paper/2303.05420/) (2023)
- [Robust, randomized preconditioning for kernel ridge regression](https://mlsanity.com/paper/2304.12465/) (2023)
- [Controlling the Inductive Bias of Wide Neural Networks by Modifying the Kernel's Spectrum](https://mlsanity.com/paper/2307.14531/) (2023)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [Many Perception Tasks are Highly Redundant Functions of their Input Data](https://mlsanity.com/paper/2407.13841/) (2024)
- [Fast training of large kernel models with delayed projections](https://mlsanity.com/paper/2411.16658/) (2024)
- [Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project](https://mlsanity.com/paper/2505.13723/) (2025)
- [Analysis of Structured Deep Kernel Networks](https://mlsanity.com/paper/2105.07228/) (2021)
- [Kernel PCA with the Nystr"om method](https://mlsanity.com/paper/2109.05578/) (2021)
- [Reconstructing Kernel-based Machine Learning Force Fields with Super-linear Convergence](https://mlsanity.com/paper/2212.12737/) (2022)
- [On the Nystrom Approximation for Preconditioning in Kernel Machines](https://mlsanity.com/paper/2312.03311/) (2023)
- [Exploring Adversarial Examples for Efficient Active Learning in Machine Learning Classifiers](https://mlsanity.com/paper/2109.10770/) (2021)
- [Changing the Kernel During Training Leads to Double Descent in Kernel Regression](https://mlsanity.com/paper/2311.01762/) (2023)
- [Joker: Joint Optimization Framework for Lightweight Kernel Machines](https://mlsanity.com/paper/2505.17765/) (2025)
- [Local Quadratic Convergence of Stochastic Gradient Descent with Adaptive Step Size](https://mlsanity.com/paper/2112.14872/) (2021)
- [Recipe for Fast Large-scale SVM Training: Polishing, Parallelism, and more RAM!](https://mlsanity.com/paper/2207.01016/) (2022)
- [RFFNet: Large-Scale Interpretable Kernel Methods via Random Fourier Features](https://mlsanity.com/paper/2211.06410/) (2022)
- [A Simple Algorithm For Scaling Up Kernel Methods](https://mlsanity.com/paper/2301.11414/) (2023)
- [Comparative analysis of Realistic EMF Exposure Estimation from Low Density Sensor Network by Finite & Infinite Neural Networks](https://mlsanity.com/paper/2504.07990/) (2025)
- [Training NTK to Generalize with KARE](https://mlsanity.com/paper/2505.11347/) (2025)
- [GPU-Enabled Large-Scale Optimization Using Randomized Linear Algebra](https://mlsanity.com/paper/2609.08136/) (2026)
- [Multivariate conformal uncertainty propagation in multitask atomistic simulation: Successes and pitfalls](https://mlsanity.com/paper/2609.31384/) (2026)

## Abstract (arXiv)

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.