On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks

Arturs Backurs, Piotr Indyk, Ludwig Schmidt

Abstract

Empirical risk minimization (ERM) is ubiquitous in machine learning and underlies most supervised learning methods. While there has been a large body of work on algorithms for various ERM problems, the exact computational complexity of ERM is still not understood. We address this issue for multiple popular ERM problems including kernel SVMs, kernel ridge regression, and training the final layer of a neural network. In particular, we give conditional hardness results for these problems based on complexity-theoretic assumptions such as the Strong Exponential Time Hypothesis (SETH). Under these assumptions, we show that there are no algorithms that solve the aforementioned ERM problems to high accuracy in sub-quadratic time. We also give similar hardness results for computing the gradient of the empirical loss, which is the main computational burden in many non-convex learning tasks.

Introduction

Empirical Risk Minimization (ERM) serves as the foundational framework for most supervised machine learning tasks, ranging from Support Vector Machines (SVMs) to deep neural networks. Although many convex ERM problems are solvable in polynomial time, traditional complexity theory—often relying on NP-hardness—is frequently too coarse to determine the precise computational limits of these algorithms.

In the era of massive datasets, where $n$ (the number of examples) can reach millions, a quadratic time algorithm ($O(n^2)$) is often computationally prohibitive. This research investigates whether more efficient, sub-quadratic (e.g., nearly-linear) algorithms exist for these fundamental problems. Furthermore, the study examines the complexity of computing batch gradients for neural networks, questioning if shortcuts exist to compute gradients faster than the standard $O(n \cdot m)$ time required to process $n$ parameters across $m$ examples.

Methodology: Fine-Grained Complexity

To analyze problems already known to be in P (polynomial time), the authors utilize fine-grained complexity theory. Their proofs are conditioned on the Strong Exponential Time Hypothesis (SETH), a widely accepted conjecture in computer science stating that the Boolean satisfiability problem (CNF-SAT) cannot be solved significantly faster than $2^n$ time.

The authors perform mathematical reductions from established "hard" problems:

  1. Orthogonal Vectors Problem (OVP)
  2. Bichromatic Hamming Close Pair (BHCP)

Both OVP and BHCP are known to require nearly quadratic time under SETH. By embedding these problems into the objective functions of common machine learning tasks, the authors demonstrate that any sub-quadratic algorithm for the ML task would effectively disprove SETH, a result that would have profound implications for the field of theoretical computer science.

Key Insights

  • The High-Accuracy Bottleneck: The expressiveness of kernel methods and neural networks inherently leads to computational hardness. There is no universal algorithm capable of solving these ERM problems to high accuracy in sub-quadratic time for all possible data distributions.
  • Theoretical Support for Stochastic Gradient Descent (SGD): The lower bounds established in this paper apply specifically to high-accuracy solutions, where the runtime depends logarithmically on the error ($\log(1/\epsilon)$). This provides a rigorous theoretical justification for the success of SGD. By settling for lower accuracy (polynomial dependence on $1/\epsilon$), SGD successfully bypasses the quadratic time bottleneck.
  • Limits of Gradient Computation: The research proves that computing a batch gradient is fundamentally "rectangular." No general mathematical shortcut exists to compute gradients significantly faster than the time taken to inspect each example and parameter individually.

Main Results

The paper establishes conditional lower bounds for several key machine learning problems, assuming the validity of SETH:

  • Kernel Methods: For problems such as hard-margin SVMs, Kernel Ridge Regression, and Kernel PCA, achieving high-accuracy solutions requires $O(n^{2-o(1)})$ time.
  • Neural Network Training: Training the final layer of a depth-2 neural network with $n$ units and $n$ examples also necessitates nearly quadratic time.
  • Gradient Computation: Computing the gradient of the empirical risk for a network with $n$ parameters and $m$ examples requires at least $O((n \cdot m)^{1-o(1)})$ time.

Discussion and Future Work

While these results provide rigorous worst-case bounds, they do not rule out efficient algorithms for specific, "well-behaved" datasets. For instance, datasets with low-dimensional latent structures may still be processed efficiently, explaining why approximation methods like the Nyström method or random Fourier features are effective in practice.

Future research could explore "reverse reductions," potentially applying fast approximate algorithms developed in the ML community to solve theoretical problems like the closest pair problem. Additionally, the search for fine-grained lower bounds continues in other areas of continuous optimization and machine learning.

Summary updated

Abstract

Empirical risk minimization (ERM) is ubiquitous in machine learning and underlies most supervised learning methods. While there has been a large body of work on algorithms for various ERM problems, the exact computational complexity of ERM is still not understood. We address this issue for multiple popular ERM problems including kernel SVMs, kernel ridge regression, and training the final layer of a neural network. In particular, we give conditional hardness results for these problems based on complexity-theoretic assumptions such as the Strong Exponential Time Hypothesis. Under these assumptions, we show that there are no algorithms that solve the aforementioned ERM problems to high accuracy in sub-quadratic time. We also give similar hardness results for computing the gradient of the empirical loss, which is the main computational burden in many non-convex learning tasks.
BibTeX
@inproceedings{backurs2017fine,
  author = {Arturs Backurs and Piotr Indyk and Ludwig Schmidt},
  title = {{On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=BJW5-vWubS},
}
Figure