Abstract
We study the problem of (provably) learning the weights of a two-layer neural network with quadratic activations. In particular, we focus on the under-parametrized regime where the number of neurons is much smaller than the input dimension. By reframing neural network training as a low-rank matrix estimation problem, we provide a new algorithmic framework that is both theoretically robust and computationally fast.
Introduction
Training neural networks is notoriously difficult because the underlying optimization problems are highly non-convex. While deep learning works wonders in practice, we often lack "provable" guarantees—mathematical certainty that an algorithm will converge to the right answer efficiently. In this paper, Mohammadreza Soltani and Chinmay Hegde from Iowa State University tackle this head-on for a specific class of models: Polynomial Neural Networks.
Problem Formulation
The researchers focus on a two-layer network with quadratic activations ($\sigma(z) = z^2$). This is a "polynomial" network because the output is a quadratic form of the input. Specifically, they look at the under-parameterized regime, where the number of hidden neurons ($r$) is much smaller than the input dimension ($p$).
The challenge is twofold:
- Non-convexity: The loss function involves fourth-powers of the weights, making it prone to local minima.
- Computational Scaling: Existing provable methods often require Singular Value Decompositions (SVD) of large matrices, which scale cubically ($O(p^3)$) with the input dimension, making them impractical for high-dimensional data.
Methodology
The authors bridge the gap between neural networks and matrix sensing using three key techniques:
- The Lifting Trick: They observe that the network's output can be rewritten as $y = x^T L_* x$, where $L_*$ is a rank-$r$ symmetric matrix representing the weights. This "lifts" the problem from finding individual weights to estimating a low-rank matrix.
- Bias-Corrected Descent (EP-ROM): Standard gradient descent fails here because the "measurement operator" doesn't satisfy the usual mathematical regularity conditions. The authors discovered that the gradient is "biased" by a trace term. By explicitly subtracting this bias in their Exact Projections (EP-ROM) algorithm, they guarantee linear convergence.
- Modified Block-Krylov SVD (AP-ROM): To solve the $O(p^3)$ bottleneck, they introduce Approximate Projections (AP-ROM). Instead of full SVDs, they use randomized Block-Krylov methods. Crucially, they developed a Modified BK-SVD (MBK-SVD) that exploits the rank-one structure of the data to perform updates in nearly-linear time relative to the input size.
Key Results
The paper demonstrates that the proposed algorithms achieve linear convergence and near-optimal sample complexity.
- Linear Convergence: The error drops exponentially with the number of iterations. To reach a specific accuracy $\epsilon$, the algorithm only needs $O(\log(1/\epsilon))$ iterations.
- Sample Efficiency: The number of training samples required scales as $O(pr^3 \text{ polylog } p)$, which is nearly optimal for a fixed number of neurons $r$.
- Speedup: In high-dimensional tests ($p=1000$), the proposed AP-ROM was significantly faster than convex relaxation methods and other state-of-the-art non-convex solvers (see plot (c) in the results below). It effectively turns a cubic-time problem into a nearly-linear time one.
Conclusion
This work presents the first nearly-linear time method for provably learning two-layer polynomial neural networks in the under-parameterized regime. By combining a lifting trick with bias-corrected gradient descent and randomized linear algebra, the authors achieve linear convergence and near-optimal sample complexity. Future work includes extending these provable guarantees to deep, multi-layer architectures and more general activation functions like ReLU.
Summary updated