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

Arturs Backurs, Piotr Indyk, Ludwig Schmidt

Executive Summary

Empirical Risk Minimization (ERM) is the foundational framework underlying most supervised machine learning methods, from Support Vector Machines (SVMs) to deep neural networks. While numerous algorithms exist to solve ERM problems, a massive gap has remained in our theoretical understanding: What is the absolute fastest we can solve these problems?

This paper establishes that many fundamental machine learning tasks—including Kernel SVMs, Kernel Ridge Regression, and training neural network layers—likely cannot be solved in sub-quadratic time for high-accuracy solutions. By linking these problems to the Strong Exponential Time Hypothesis (SETH), the authors prove that the current "slow" $O(n^2)$ algorithms are likely the best possible for general datasets.

The Computational Bottleneck

Whether training an SVM or a deep neural network, the core objective is to minimize a loss function over a set of training data. As datasets grow into the millions, even a "polynomial" $O(n^2)$ algorithm becomes a significant computational bottleneck. Researchers have long sought "silver bullet" algorithms that could achieve nearly linear time ($O(n)$) for high-accuracy solutions. This paper investigates whether such speedups are mathematically possible or if we are hitting a fundamental computational wall.

Methodology: Fine-Grained Complexity

Because this is a theoretical work focused on complexity proofs, it does not rely on standard empirical benchmarks like ImageNet or MNIST. Instead, it constructs "hard" synthetic instances of data to prove that no algorithm can perform well on all possible inputs.

To do this, the authors utilize the framework of fine-grained complexity. Traditional NP-hardness is often too "coarse" for problems that already have polynomial-time solutions. Instead, the authors use reductions from well-studied problems in theoretical computer science:

  1. Orthogonal Vectors (OVP): Given two sets of vectors, determine if any pair is orthogonal.
  2. Bichromatic Hamming Close Pair (BHCP): Find the closest pair of vectors between two sets under Hamming distance.

The authors demonstrate that if one could solve ERM problems (like Kernel SVM) in sub-quadratic time ($n^{2-\epsilon}$), one could also solve OVP and BHCP faster than currently thought possible. This would disprove the Strong Exponential Time Hypothesis (SETH)—a core conjecture in complexity theory which posits that certain logic problems (like CNF-SAT) cannot be solved significantly faster than exhaustive search.

Key Insights

  • The Cost of Expressiveness: The very features that make kernel methods and neural networks powerful—their ability to embed data into complex spaces—are exactly what make them computationally expensive. For instance, the "expressiveness" of the Gaussian kernel is directly linked to the hardness of its optimization.
  • High Accuracy is the Hard Part: The paper distinguishes between low-accuracy solutions (achievable quickly via methods like Stochastic Gradient Descent) and high-accuracy solutions (where the error $\epsilon$ is very small). The quadratic bottleneck specifically applies to algorithms where the runtime depends logarithmically on the error ($1/\epsilon$).
  • Gradient Computation Bottleneck: Even the simple act of computing a gradient for a batch of data in a neural network is shown to be "rectangular" ($O(n \cdot m)$). This suggests that for general activation functions like ReLU or Sigmoid, we cannot compute batch gradients significantly faster than simply processing each example one by one.
  • Activation Functions Matter: Interestingly, if polynomial activation functions are used, faster algorithms do exist. The hardness results specifically target standard non-linearities like ReLU and Sigmoid.

Principal Results

  • Kernel Methods: For Kernel SVM, Kernel Ridge Regression, and Kernel PCA using the Gaussian kernel, approximating the optimal value within a factor of $1+\epsilon$ requires almost quadratic time ($n^{2-o(1)}$), assuming SETH.
  • Neural Networks: Training just the top layer of a depth-2 neural network requires almost quadratic time to reach high accuracy.
  • Gradient Hardness: Computing the norm of the gradient for the top layer of a neural network takes time proportional to the product of the number of examples and the number of units ($O(n \cdot m)$). There is no algorithmic "shortcut" for batch gradients in the general case.

Limitations and Future Directions

It is important to note that these results are worst-case. They do not rule out the existence of faster algorithms for "well-behaved" data, such as datasets with low-dimensional underlying structures or specific clustering properties.

Furthermore, the proofs focus on kernels with "exponential tails" (like the Gaussian kernel). The authors suggest that "heavy-tailed" kernels (like the Cauchy kernel) might be an interesting area for future study to determine if they share the same hardness. Finally, the techniques used here do not apply to linear kernels, which are known to be solvable in $O(nd^2)$ time. The computational gap between linear and non-linear complexity remains a key distinction and an exciting frontier in the field.

Summary updated

Abstract

Empirical risk minimization (ERM) is ubiquitous in machine learning and underlies most supervised learning methods. While there is 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