# The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Models

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 83 references that are in the map.
- First posted on arXiv 19 Dec 2023.

## Builds on (most cited first, 30 of 35)

- [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)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019)
- [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)
- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss](https://mlsanity.com/paper/2002.04486/) (2020)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Implicit Bias of Gradient Descent on Linear Convolutional Networks](https://mlsanity.com/paper/1806.00468/) (2018)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Implicit Regularization in Deep Learning May Not Be Explainable by Norms](https://mlsanity.com/paper/2005.06398/) (2020)
- [How do infinite width bounded norm networks look in function space?](https://mlsanity.com/paper/1902.05040/) (2019)
- [Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks](https://mlsanity.com/paper/2002.10553/) (2020)
- [Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks](https://mlsanity.com/paper/1910.01663/) (2019)
- [Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy](https://mlsanity.com/paper/2007.06738/) (2020)
- [What Kinds of Functions do Deep Neural Networks Learn? Insights from Variational Spline Theory](https://mlsanity.com/paper/2105.03361/) (2021)
- [Revealing the Structure of Deep Neural Networks via Convex Duality](https://mlsanity.com/paper/2002.09773/) (2020)
- [Convex Geometry and Duality of Over-parameterized Neural Networks](https://mlsanity.com/paper/2002.11219/) (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)
- [The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutions](https://mlsanity.com/paper/2006.05900/) (2020)
- [Unraveling Attention via Convex Duality: Analysis and Interpretations of Vision Transformers](https://mlsanity.com/paper/2205.08078/) (2022)
- [Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programs](https://mlsanity.com/paper/2110.05518/) (2021)
- [Complexity of Training ReLU Neural Network](https://mlsanity.com/paper/1809.10787/) (2018)
- [Demystifying Batch Normalization in ReLU Networks: Equivalent Convex Optimization Models and Implicit Regularization](https://mlsanity.com/paper/2103.01499/) (2021)
- [Convex Formulation of Overparameterized Deep Neural Networks](https://mlsanity.com/paper/1911.07626/) (2019)

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

- [From SGD to Spectra: A Theory of Neural Network Weight Dynamics](https://mlsanity.com/paper/2507.12709/) (2025)
- [A Library of Mirrors: Deep Neural Nets in Low Dimensions are Convex Lasso Models with Reflection Features](https://mlsanity.com/paper/2403.01046/) (2024)
- [Unveiling Hidden Convexity in Deep Learning: a Sparse Signal Processing Perspective](https://mlsanity.com/paper/2603.23831/) (2026)
- [A Convexity-dependent Two-Phase Training Algorithm for Deep Neural Networks](https://mlsanity.com/paper/2510.25366/) (2025)
- [Convex Optimization of Spiking Neural Networks with Global and Approximation Guarantees](https://mlsanity.com/paper/2605.08022/) (2026)
- [Exact Convex Reformulations of Linear Neural Networks via Completely Positive Lifting](https://mlsanity.com/paper/2605.17692/) (2026)
- [Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback](https://mlsanity.com/paper/2605.26373/) (2026)

## Abstract (arXiv)

Due to the non-convex nature of training Deep Neural Network (DNN) models, their effectiveness relies on the use of non-convex optimization heuristics. Traditional methods for training DNNs often require costly empirical methods to produce successful models and do not have a clear theoretical foundation. In this study, we examine the use of convex optimization theory and sparse recovery models to refine the training process of neural networks and provide a better interpretation of their optimal weights. We focus on training two-layer neural networks with piecewise linear activations and demonstrate that they can be formulated as a finite-dimensional convex program. These programs include a regularization term that promotes sparsity, which constitutes a variant of group Lasso. We first utilize semi-infinite programming theory to prove strong duality for finite width neural networks and then we express these architectures equivalently as high dimensional convex sparse recovery models. Remarkably, the worst-case complexity to solve the convex program is polynomial in the number of samples and number of neurons when the rank of the data matrix is bounded, which is the case in convolutional networks. To extend our method to training data of arbitrary rank, we develop a novel polynomial-time approximation scheme based on zonotope subsampling that comes with a guaranteed approximation ratio. We also show that all the stationary of the nonconvex training objective can be characterized as the global optimum of a subsampled convex program. Our convex models can be trained using standard convex solvers without resorting to heuristics or extensive hyper-parameter tuning unlike non-convex methods. Through extensive numerical experiments, we show that convex models can outperform traditional non-convex methods and are not sensitive to optimizer hyperparameters.