Porcupine Neural Networks: (Almost) All Local Optima are Global

Soheil Feizi, Hamid Javadi, Jesse M. Zhang, David TsearXiv 2017 · arXiv

Introduction

Training neural networks is a fundamental challenge in machine learning. While optimization landscapes are theoretically non-convex and training is NP-complete in the worst case, simple local search methods like Stochastic Gradient Descent (SGD) are remarkably effective in practice. This discrepancy between "worst-case" theory and "average-case" success suggests that typical neural network landscapes might possess hidden structural properties. Researchers from Stanford have introduced Porcupine Neural Networks (PNNs) to bridge this gap. PNNs are a constrained class of two-layer networks designed to have a "nice" provable optimization landscape while remaining powerful function approximators.

Architecture and Methodology

The defining characteristic of a Porcupine Neural Network is its geometric constraint on weights. In a standard two-layer network, weight vectors can point in any direction in $d$-dimensional space. In a PNN, the incoming weight vector to each hidden neuron is restricted to lie on one of a fixed set of lines—resembling the quills of a porcupine.

PNN architecture (a) and the geometric constraint on weight vectors (b), where weights are restricted to a finite set of lines.

The architecture typically consists of a two-layer network with ReLU activations and Gaussian inputs. The authors analyze the population risk (expected error over the input distribution) rather than empirical risk. By treating PNNs as an angular discretization of the continuous weight space, they derive a specific kernel function, $\psi(x)$, which characterizes the interaction between these "quills."

Theoretical Landscape Analysis

The primary contribution of this work is the "Local is Global" guarantee. For specific configurations, such as scalar or "degree-one" PNNs (where each neuron connects to only one input), the optimization landscape is proven to be essentially convex in most regions.

For general PNNs, the authors demonstrate that as long as the set of lines is sufficiently diverse (specifically, if at least $d$ lines have diverse signs), every local optimum is a global one. This result tames the "non-convex boogeyman" that usually complicates neural network theory. Furthermore, the paper highlights the role of over-parameterization: as the number of neurons ($k$) increases relative to the number of lines ($r$), the probability of encountering a "bad" local minimum decreases exponentially.

Experimental Results and Approximation

To validate these theoretical findings, the authors conducted simulations using synthetic datasets with Gaussian inputs. They employed a "teacher-student" setup, where a PNN (student) attempts to approximate a standard, unconstrained two-layer network (teacher).

The PNN approximation error (normalized MSE) decreases steadily as the number of neurons increases, following a polynomial decay rate.

A critical concern with discretization is the "curse of dimensionality," which might require an exponential number of lines to approximate high-dimensional spaces. However, both theoretical analysis and empirical evidence show that a polynomially-large PNN is sufficient for high-accuracy approximation. In experiments with input dimensions $d=5$ and $d=15$, the approximation error decreased steadily as more neurons were added, confirming that PNNs are practical and efficient approximators.

Conclusion and Future Directions

Porcupine Neural Networks provide a theoretical framework for understanding why local search works in non-convex landscapes. By constraining weights to a finite set of lines, the authors achieve a landscape where local optima are global, without sacrificing approximation power.

However, several challenges remain for future research:

  • Depth: The current analysis is limited to two-layer architectures; extending these proofs to deep networks is an open problem.
  • Layer Trainability: The second layer is currently assumed to be fixed (e.g., all ones).
  • Empirical Risk: Future work should account for the noise introduced by finite sample sizes (empirical risk) versus the idealized population risk studied here.
  • Activations: The current kernel derivations are specific to ReLU activations.

Despite these limitations, PNNs offer a promising path toward a more rigorous understanding of neural network optimization.

Summary updated

Abstract

Neural networks have been used prominently in several machine learning and statistics applications. In general, the underlying optimization of neural networks is non-convex which makes their performance analysis challenging. In this paper, we take a novel approach to this problem by asking whether one can constrain neural network weights to make its optimization landscape have good theoretical properties while at the same time, be a good approximation for the unconstrained one. For two-layer neural networks, we provide affirmative answers to these questions by introducing Porcupine Neural Networks (PNNs) whose weight vectors are constrained to lie over a finite set of lines. We show that most local optima of PNN optimizations are global while we have a characterization of regions where bad local optimizers may exist. Moreover, our theoretical and empirical results suggest that an unconstrained neural network can be approximated using a polynomially-large PNN.
BibTeX
@misc{feizi2017porcupine,
  author = {Soheil Feizi and Hamid Javadi and Jesse M. Zhang and David Tse},
  title = {{Porcupine Neural Networks: (Almost) All Local Optima are Global}},
  year = {2017},
  eprint = {1710.02196},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1710.02196},
}
Figure