Towards Provable Learning of Polynomial Neural Networks Using Low-Rank Matrix Estimation

Mohammadreza Soltani, Chinmay HegdeAISTATS 2018 · OpenReview

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$).

Architecture of a two-layer polynomial neural network with quadratic activations.

The challenge is twofold:

  1. Non-convexity: The loss function involves fourth-powers of the weights, making it prone to local minima.
  2. 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.
Experimental results: (a) Probability of success vs. number of measurements, (b) Convergence rate (error vs. iteration), and (c) Computational efficiency (error vs. time).

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

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 neuron...
BibTeX
@inproceedings{soltani2018towards,
  author = {Mohammadreza Soltani and Chinmay Hegde},
  title = {{Towards Provable Learning of Polynomial Neural Networks Using Low-Rank Matrix Estimation}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2018},
  url = {https://openreview.net/forum?id=3Un_sXNSDrj},
}
Figure