# Neural Spectrahedra and Semidefinite Lifts: Global Convex Optimization of Polynomial Activation Neural Networks in Fully Polynomial-Time

arXiv: https://arxiv.org/abs/2101.02429 · HTML: https://mlsanity.com/paper/2101.02429/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 53 references that are in the map.
- First posted on arXiv 7 Jan 2021.

## Builds on (most cited first, 23 of 23)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [Greedy Layerwise Learning Can Scale to ImageNet](https://mlsanity.com/paper/1812.11446/) (2018)
- [On the Power of Over-parametrization in Neural Networks with Quadratic Activation](https://mlsanity.com/paper/1803.01206/) (2018)
- [Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks](https://mlsanity.com/paper/2002.10553/) (2020)
- [On the Computational Efficiency of Training Neural Networks](https://mlsanity.com/paper/1410.1141/) (2014)
- [Revealing the Structure of Deep Neural Networks via Convex Duality](https://mlsanity.com/paper/2002.09773/) (2020)
- [Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functions](https://mlsanity.com/paper/2006.15459/) (2020)
- [Reliably Learning the ReLU in Polynomial Time](https://mlsanity.com/paper/1611.10258/) (2016)
- [Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithms](https://mlsanity.com/paper/2012.13329/) (2020)
- [Convex Regularization Behind Neural Reconstruction](https://mlsanity.com/paper/2012.05169/) (2020)
- [Principled Deep Neural Network Training through Linear Programming](https://mlsanity.com/paper/1810.03218/) (2018)
- [Stationary Points of Shallow Neural Networks with Quadratic Activation Function](https://mlsanity.com/paper/1912.01599/) (2019)
- [Multi-output Polynomial Networks and Factorization Machines](https://mlsanity.com/paper/1705.07603/) (2017)
- [Optimization Landscapes of Wide Deep Neural Networks Are Benign](https://mlsanity.com/paper/2010.00885/) (2020)
- [A Revisit to Quadratic Programming with One Inequality Quadratic Constraint via Matrix Pencil](https://mlsanity.com/paper/1312.1400/) (2013)

## Built on by (most cited first, 14 of 14)

- [Unraveling Attention via Convex Duality: Analysis and Interpretations of Vision Transformers](https://mlsanity.com/paper/2205.08078/) (2022)
- [Hidden Convexity of Wasserstein GANs: Interpretable Generative Models with Closed-Form Solutions](https://mlsanity.com/paper/2107.05680/) (2021)
- [The Convex Geometry of Backpropagation: Neural Network Gradient Flows Converge to Extreme Points of the Dual Convex Program](https://mlsanity.com/paper/2110.06488/) (2021)
- [Parallel Deep Neural Networks Have Zero Duality Gap](https://mlsanity.com/paper/2110.06482/) (2021)
- [Optimal Neural Network Approximation of Wasserstein Gradient Direction via Convex Optimization](https://mlsanity.com/paper/2205.13098/) (2022)
- [Globally Optimal Training of Neural Networks with Threshold Activation Functions](https://mlsanity.com/paper/2303.03382/) (2023)
- [Training Quantized Neural Networks to Global Optimality via Semidefinite Programming](https://mlsanity.com/paper/2105.01420/) (2021)
- [Overparameterized ReLU Neural Networks Learn the Simplest Models: Neural Isometry and Exact Recovery](https://mlsanity.com/paper/2209.15265/) (2022)
- [Analysis and Design of Quadratic Neural Networks for Regression, Classification, and Lyapunov Control of Dynamical Systems](https://mlsanity.com/paper/2207.13120/) (2022)
- [Adversarial Training of Two-Layer Polynomial and ReLU Activation Networks via Convex Optimization](https://mlsanity.com/paper/2405.14033/) (2024)
- [Implicit Bias in Matrix Factorization and its Explicit Realization in a New Architecture](https://mlsanity.com/paper/2501.16322/) (2025)
- [Least Squares Training of Quadratic Convolutional Neural Networks with Applications to System Theory](https://mlsanity.com/paper/2411.08267/) (2024)
- [Why ReLU? A Bit-Model Dichotomy for Deep Network Training](https://mlsanity.com/paper/2602.19017/) (2026)
- [Regularized Least Squares Training of Quadratic Neural Networks with Applications to System Identification](https://mlsanity.com/paper/2609.17654/) (2026)

## Abstract (arXiv)

The training of two-layer neural networks with nonlinear activation functions is an important non-convex optimization problem with numerous applications and promising performance in layerwise deep learning. In this paper, we develop exact convex optimization formulations for two-layer neural networks with second degree polynomial activations based on semidefinite programming. Remarkably, we show that semidefinite lifting is always exact and therefore computational complexity for global optimization is polynomial in the input dimension and sample size for all input data. The developed convex formulations are proven to achieve the same global optimal solution set as their non-convex counterparts. More specifically, the globally optimal two-layer neural network with polynomial activations can be found by solving a semidefinite program (SDP) and decomposing the solution using a procedure we call Neural Decomposition. Moreover, the choice of regularizers plays a crucial role in the computational tractability of neural network training. We show that the standard weight decay regularization formulation is NP-hard, whereas other simple convex penalties render the problem tractable in polynomial time via convex programming. We extend the results beyond the fully connected architecture to different neural network architectures including networks with vector outputs and convolutional architectures with pooling. We provide extensive numerical simulations showing that the standard backpropagation approach often fails to achieve the global optimum of the training loss. The proposed approach is significantly faster to obtain better test accuracy compared to the standard backpropagation procedure.