Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent

Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, Adam R. Klivans

TL;DR

This paper establishes the first superpolynomial lower bounds for training one-layer neural networks using gradient descent on Gaussian distributions. This means that even for this simple network architecture and a common data distribution, gradient descent fundamentally struggles to learn efficiently, requiring an impractically long time to achieve good performance. The work introduces a novel construction of orthogonal neural networks to prove these hardness results, impacting our understanding of why certain assumptions are crucial for efficient deep learning.

What Problem Does This Paper Address?

A central question in deep learning theory is understanding when and why gradient descent works. While it's a powerful optimization tool, its theoretical guarantees are often limited, especially for non-convex problems like training neural networks. Prior work has shown that training neural networks can be computationally hard in certain settings, but these hardness results often relied on specific, less realistic assumptions (e.g., discrete data, specific activation functions, or limited query models). This paper tackles the challenge of proving hardness for a more realistic and fundamental scenario: learning a simple, one-layer neural network with standard activation functions (like ReLU and sigmoid) under a common data distribution (Gaussian), using the ubiquitous gradient descent algorithm. The authors aim to show that even in this "simplest possible setting," gradient descent faces fundamental limitations in terms of time complexity.

Methods

The core of the paper's contribution lies in a novel construction of a family of one-layer neural networks that are orthogonal with respect to spherical Gaussian distributions. This orthogonality is key to establishing lower bounds in the Statistical Query (SQ) model, a theoretical framework that captures many practical learning algorithms, including gradient descent.

Here's a breakdown of their approach:

  • Orthogonal Family Construction: They construct a family of neural networks, Corth(n,k), where each network is a one-layer function with m = 2^k hidden units. The novelty lies in how these networks are designed to be orthogonal. They leverage a "sign-symmetry" property of the underlying distribution and carefully choose inner and outer activation functions (like ReLU, sigmoid, or tanh).
  • Statistical Query (SQ) Model: The lower bounds are proven within the SQ model. This model abstracts away the specifics of how a learner accesses data, focusing instead on the ability to query the expected value of functions related to the data distribution. Gradient descent, when using square-loss, can be simulated using inner-product queries in this model.
  • Statistical Dimension (SDA): The authors utilize the concept of statistical dimension, a measure of the complexity of a concept class in the SQ model. A higher statistical dimension implies harder learning. Their orthogonal construction allows them to bound the SDA, which then translates into lower bounds on the number of queries (and thus time) required for learning.
  • Norm Lower Bounds: To ensure that the constructed functions are not trivially easy to learn (e.g., by outputting a constant), they also prove lower bounds on the norms of these neural network functions under the Gaussian distribution. This is crucial for the theoretical machinery to work.

Datasets

The paper does not introduce new datasets. Instead, it focuses on theoretical analysis using a synthetic data distribution: the standard Gaussian distribution, $N(0, I_n)$. The experiments section uses synthetic data generated from this distribution, with labels derived from the constructed one-layer neural networks.

Key Insights and Ideas

  • Fundamental Limits of Gradient Descent: The most striking insight is that even for a simple one-layer network and Gaussian data, gradient descent faces inherent superpolynomial time complexity. This suggests that the "curse of dimensionality" or the inherent difficulty of the optimization landscape for neural networks is not solely an artifact of complex architectures or non-standard data.
  • Orthogonality as a Tool for Hardness: The paper demonstrates the power of constructing orthogonal function families to prove hardness results in the SQ model. This technique, while not entirely new, is applied here in a novel way to the specific problem of learning one-layer neural networks with common activations.
  • Impact on Practical Heuristics: The results imply that common practices like using overparameterized networks (e.g., in the NTK regime) might not fundamentally overcome the time complexity limitations imposed by gradient descent for these simple network structures.
  • Broad Applicability of Activations: The lower bounds hold for a broad class of activations, including ReLU and sigmoid, making the results more general and relevant to modern deep learning.

Key Results

  • Superpolynomial Lower Bounds: The paper proves the first superpolynomial lower bounds for learning one-layer neural networks using gradient descent with respect to the Gaussian distribution. This means that any algorithm relying on gradient descent will require time that grows faster than any polynomial in the input dimension to achieve small test error.
  • Stronger Bounds for Classification: For classification tasks, they achieve even stronger results, ruling out general Statistical Query (SQ) algorithms (which include gradient descent) from learning these networks in polynomial time.
  • Specific Complexity: The lower bounds are shown to be roughly $n^{\Omega(\log m)}$ queries, where $n$ is the input dimension and $m$ is the number of hidden units. For polynomial-sized networks ($m = \text{poly}(n)$), this translates to a superpolynomial query complexity of $n^{\Omega(\log n)}$.

Limitations and Future Work

  • Focus on One-Layer Networks: The primary limitation is that the results are for one-layer neural networks. Extending these superpolynomial lower bounds to deeper networks remains a significant open challenge.
  • SQ Model vs. Real-World SGD: While the SQ model captures many learning algorithms, it doesn't perfectly represent Stochastic Gradient Descent (SGD) which operates on individual data points. The authors note that proving unconditional lower bounds for SGD would imply P ≠ NP, indicating the difficulty of this extension.
  • Specific Distribution: The analysis is primarily for the Gaussian distribution. While the construction uses sign-symmetry, which can apply to other distributions, the specific norm bounds and detailed analysis are tied to the Gaussian.
  • Future Work: The authors suggest that improving their bounds from quasipolynomial to exponential for the number of hidden units is an interesting open question. They also highlight the need to understand the role of specific assumptions (like hidden weight orthogonality) that enable efficient learning in practice.

Summary updated

Abstract

We prove the first superpolynomial lower bounds for learning one-layer neural networks with respect to the Gaussian distribution using gradient descent. We show that any classifier trained using gradient descent with respect to square-loss will fail to achieve small test error in polynomial time given access to samples labeled by a one-layer neural network. For classification, we give a stronger result, namely that any statistical query (SQ) algorithm (including gradient descent) will fail to achieve small test error in polynomial time. Prior work held only for gradient descent run with small batch sizes, required sharp activations, and applied to specific classes of queries. Our lower bounds hold for broad classes of activations including ReLU and sigmoid. The core of our result relies on a novel construction of a simple family of neural networks that are exactly orthogonal with respect to all spherically symmetric distributions.
BibTeX
@inproceedings{goel2020superpolynomial,
  author = {Surbhi Goel and Aravind Gollakota and Zhihan Jin and Sushrut Karmalkar and Adam R. Klivans},
  title = {{Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=25JAv8fYKdA},
}
Figure