Geometry and Optimization of Shallow Polynomial Networks

Yossi Arjevani, Joan Bruna, Joe Kileel, Elzbieta Polak, Matthew Trager

TL;DR

This paper uses the tools of algebraic geometry to provide a precise map of the optimization landscape for shallow polynomial neural networks. The authors demonstrate that while overparameterization generally helps, the specific distribution of training data can trigger an "exponential explosion" of local minima, challenging the common theoretical reliance on simple Gaussian data assumptions.

What Problem Does This Paper Address?

In deep learning, we often observe that larger networks are easier to train, a phenomenon attributed to "overparameterization." However, most theoretical explanations for why this works rely on highly simplified models (like linear networks) or unrealistic assumptions (like having an infinite number of neurons).

The authors aim to bridge this gap by studying shallow polynomial networks. These networks are non-linear and non-convex—making them "real" enough to be interesting—but they possess a rich algebraic structure that allows for exact mathematical analysis. The core question is: How do the network's width and the training data's distribution interact to create (or eliminate) "bad" local minima?

Methods

The researchers treat neural network training as a problem of low-rank tensor approximation. Specifically:

  • Algebraic Geometry: They identify the function space of these networks as a set of symmetric tensors. This allows them to use the Alexander-Hirschowitz Theorem to define exactly when a network is "wide enough" to represent certain functions.
  • Teacher-Student Framework: They analyze a scenario where a "student" network tries to learn from a fixed "teacher" network.
  • Data Discriminants: They introduce a novel tool called the teacher-metric data discriminant. This is a mathematical boundary in the space of possible datasets; crossing this boundary signifies a qualitative change in the optimization landscape (e.g., the sudden appearance of new local minima).
  • Landscape Analysis: For quadratic networks ($d=2$), they extend the classical Eckart-Young Theorem (which describes the best low-rank approximation of a matrix) to account for different data distributions.

Datasets

The paper is primarily theoretical and does not use standard benchmarks like ImageNet. Instead, it uses:

  • Synthetic Gaussian Data: Used to prove that under "nice" distributions, the number of critical points is small and manageable.
  • Generic i.i.d. Distributions: Used to demonstrate that for most other types of data, the landscape becomes significantly more complex.
  • Macaulay2 Simulations: The authors used the Macaulay2 software for symbolic algebraic computations to find explicit polynomial equations for their discriminants.

Key Insights and Ideas

  • The Three Regimes of Width: The authors classify network width into three geometric stages:
  • Low-dimensional: The network can only represent a tiny fraction of possible functions.
  • Thick: The network can represent a "solid" chunk of the function space but not everything.
  • Filling: The network can represent any symmetric polynomial of that degree.
  • The "Gaussian Trap": Much of deep learning theory assumes data is Gaussian because it makes the math easier. This paper shows that this is a dangerous simplification. For a quadratic network, Gaussian data results in only $n$ critical points, but "generic" data can result in $(3^n - 1)/2$ critical points—an exponential increase.
  • Bad Minima are Persistent: Even in very wide networks, "bad" local minima can exist. While they might be "escapable" (meaning there is a downward path to a global minimum), they still have "basins of attraction" that can trap gradient descent if the initialization is unlucky.

Key Results

  • Theorem 36 (Gaussian Eckart-Young): The authors provide a complete characterization of all critical points and their "Hessian signatures" (which tell you if a point is a minimum, maximum, or saddle point) for quadratic networks trained on Gaussian data.
  • Theorem 37 (The Complexity Leap): They prove that for non-Gaussian i.i.d. coordinates, there exist "teacher" models where the number of critical points explodes to $(3^n - 1)/2$.
  • Numerical Validation: In experiments with a 5D input and a 3-neuron student, they showed that SGD actually hits the specific local minima predicted by their theory, confirming that these algebraic "focal points" are real obstacles in practice.

Limitations and Future Work

  • Shallow Architecture: The results are currently limited to "shallow" networks (one hidden layer). Extending this to deep architectures remains a major challenge due to the increasing complexity of the algebraic varieties involved.
  • Polynomial vs. ReLU: While polynomial networks are great for math, most practitioners use ReLU activations. The authors suggest their "filling" and "thick" concepts apply to ReLU, but the exact algebraic tools (like discriminants) are harder to define there.
  • Degree Constraints: Much of the detailed landscape analysis is focused on quadratic ($d=2$) or 2D ($n=2$) cases. The authors hope to generalize these results to higher-degree polynomials in future work.

Summary updated

Abstract

We study shallow neural networks with monomial activations and output dimension one. The function space for these models can be identified with a set of symmetric tensors with bounded rank. We describe general features of these networks, focusing on the relationship between width and optimization. We then consider teacher-student problems, which can be viewed as problems of low-rank tensor approximation with respect to non-standard inner products that are induced by the data distribution. In this setting, we introduce a teacher-metric data discriminant which encodes the qualitative behavior of the optimization as a function of the training data distribution. Finally, we focus on networks with quadratic activations, presenting an in-depth analysis of the optimization landscape. In particular, we present a variation of the Eckart-Young Theorem characterizing all critical points and their Hessian signatures for teacher-student problems with quadratic networks and Gaussian training data.
BibTeX
@article{arjevani2026geometry,
  author = {Yossi Arjevani and Joan Bruna and Joe Kileel and Elzbieta Polak and Matthew Trager},
  title = {{Geometry and Optimization of Shallow Polynomial Networks}},
  journal = {SIAM J. Appl. Algebra Geom.},
  year = {2026},
  doi = {10.1137/25m1732994},
}
Figure