# Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programs

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 54 references that are in the map.
- First posted on arXiv 11 Oct 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Aggregated Residual Transformations for Deep Neural Networks](https://mlsanity.com/paper/1611.05431/) (2016)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Xception: Deep Learning with Depthwise Separable Convolutions](https://mlsanity.com/paper/1610.02357/) (2016)
- [Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learning](https://mlsanity.com/paper/1602.07261/) (2016)
- [SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and <0.5MB model size](https://mlsanity.com/paper/1602.07360/) (2016)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks](https://mlsanity.com/paper/1805.12076/) (2018)
- [How do infinite width bounded norm networks look in function space?](https://mlsanity.com/paper/1902.05040/) (2019)
- [Spurious Local Minima are Common in Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/1712.08968/) (2017)
- [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)
- [Learning One-hidden-layer Neural Networks with Landscape Design](https://mlsanity.com/paper/1711.00501/) (2017)
- [Failures of Gradient-Based Deep Learning](https://mlsanity.com/paper/1703.07950/) (2017)
- [SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data](https://mlsanity.com/paper/1710.10174/) (2017)
- [Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs](https://mlsanity.com/paper/1702.07966/) (2017)
- [Convex Geometry and Duality of Over-parameterized Neural Networks](https://mlsanity.com/paper/2002.11219/) (2020)
- [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)
- [Efficient approaches for escaping higher order saddle points in non-convex optimization](https://mlsanity.com/paper/1602.05908/) (2016)
- [Demystifying Batch Normalization in ReLU Networks: Equivalent Convex Optimization Models and Implicit Regularization](https://mlsanity.com/paper/2103.01499/) (2021)
- [Hidden Convexity of Wasserstein GANs: Interpretable Generative Models with Closed-Form Solutions](https://mlsanity.com/paper/2107.05680/) (2021)

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

- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositions](https://mlsanity.com/paper/2202.01331/) (2022)
- [Unraveling Attention via Convex Duality: Analysis and Interpretations of Vision Transformers](https://mlsanity.com/paper/2205.08078/) (2022)
- [The Real Tropical Geometry of Neural Networks](https://mlsanity.com/paper/2403.11871/) (2024)
- [Efficient Global Optimization of Two-Layer ReLU Networks: Quadratic-Time Algorithms and Adversarial Training](https://mlsanity.com/paper/2201.01965/) (2022)
- [Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks](https://mlsanity.com/paper/2110.09548/) (2021)
- [Neural networks with linear threshold activations: structure and algorithms](https://mlsanity.com/paper/2111.08117/) (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)
- [Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time](https://mlsanity.com/paper/2402.03625/) (2024)
- [Deep Learning meets Nonparametric Regression: Are Weight-Decayed DNNs Locally Adaptive?](https://mlsanity.com/paper/2204.09664/) (2022)
- [Optimal Sets and Solution Paths of ReLU Networks](https://mlsanity.com/paper/2306.00119/) (2023)
- [Parallel Deep Neural Networks Have Zero Duality Gap](https://mlsanity.com/paper/2110.06482/) (2021)
- [Globally Optimal Training of Neural Networks with Threshold Activation Functions](https://mlsanity.com/paper/2303.03382/) (2023)
- [Piecewise Linear Neural Networks and Deep Learning](https://mlsanity.com/paper/2206.09149/) (2022)
- [The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Models](https://mlsanity.com/paper/2312.12657/) (2023)
- [From Complexity to Clarity: Analytical Expressions of Deep Neural Network Weights via Clifford's Geometric Algebra and Convexity](https://mlsanity.com/paper/2309.16512/) (2023)
- [Overparameterized ReLU Neural Networks Learn the Simplest Models: Neural Isometry and Exact Recovery](https://mlsanity.com/paper/2209.15265/) (2022)
- [Convex Approximation of Two-Layer ReLU Networks for Hidden State Differential Privacy](https://mlsanity.com/paper/2407.04884/) (2024)
- [Fixing the NTK: From Neural Network Linearizations to Exact Convex Programs](https://mlsanity.com/paper/2309.15096/) (2023)
- [Convex Dual Theory Analysis of Two-Layer Convolutional Neural Networks with Soft-Thresholding](https://mlsanity.com/paper/2304.06959/) (2023)
- [Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks](https://mlsanity.com/paper/2501.05930/) (2025)
- [Why ReLU? A Bit-Model Dichotomy for Deep Network Training](https://mlsanity.com/paper/2602.19017/) (2026)
- [Exact Convex Reformulations of Linear Neural Networks via Completely Positive Lifting](https://mlsanity.com/paper/2605.17692/) (2026)
- [Convex training of Lipschitz-regularized shallow neural networks](https://mlsanity.com/paper/2606.19652/) (2026)
- [Effects of width-dependent model hyperparameters and ℓ2-regularization on the loss landscape of two-layer ReLU networks](https://mlsanity.com/paper/2607.16720/) (2026)

## Abstract (arXiv)

Understanding the fundamental mechanism behind the success of deep neural networks is one of the key challenges in the modern machine learning literature. Despite numerous attempts, a solid theoretical analysis is yet to be developed. In this paper, we develop a novel unified framework to reveal a hidden regularization mechanism through the lens of convex optimization. We first show that the training of multiple three-layer ReLU sub-networks with weight decay regularization can be equivalently cast as a convex optimization problem in a higher dimensional space, where sparsity is enforced via a group ℓ1-norm regularization. Consequently, ReLU networks can be interpreted as high dimensional feature selection methods. More importantly, we then prove that the equivalent convex problem can be globally optimized by a standard convex optimization solver with a polynomial-time complexity with respect to the number of samples and data dimension when the width of the network is fixed. Finally, we numerically validate our theoretical results via experiments involving both synthetic and real datasets.