# The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutions

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2020.

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

- [Test-Time Training on Video Streams](https://mlsanity.com/paper/2307.05014/) (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)
- [Penalising the biases in norm regularisation enforces sparsity](https://mlsanity.com/paper/2303.01353/) (2023)
- [Mildly Overparameterized ReLU Networks Have a Favorable Loss Landscape](https://mlsanity.com/paper/2305.19510/) (2023)
- [Provable Guarantees for Neural Networks via Gradient Feature Learning](https://mlsanity.com/paper/2310.12408/) (2023)
- [Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time](https://mlsanity.com/paper/2402.03625/) (2024)
- [Optimal Sets and Solution Paths of ReLU Networks](https://mlsanity.com/paper/2306.00119/) (2023)
- [The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Models](https://mlsanity.com/paper/2312.12657/) (2023)
- [Loss Landscape of Shallow ReLU-like Neural Networks: Stationary Points, Saddle Escape, and Network Embedding](https://mlsanity.com/paper/2402.05626/) (2024)
- [On the Global Convergence of Natural Actor-Critic with Two-layer Neural Network Parametrization](https://mlsanity.com/paper/2306.10486/) (2023)
- [Practical Convex Formulation of Robust One-hidden-layer Neural Network Training](https://mlsanity.com/paper/2105.12237/) (2021)
- [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)
- [A Combinatorial Perspective on the Optimization of Shallow ReLU Networks](https://mlsanity.com/paper/2210.00176/) (2022)
- [On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrization](https://mlsanity.com/paper/2211.07675/) (2022)
- [A qualitative difference between gradient flows of convex functions in finite- and infinite-dimensional Hilbert spaces](https://mlsanity.com/paper/2310.17610/) (2023)
- [Nonasymptotic theory for two-layer neural networks: Beyond the bias-variance trade-off](https://mlsanity.com/paper/2106.04795/) (2021)
- [PathProx: A Proximal Gradient Algorithm for Weight Decay Regularized Deep Neural Networks](https://mlsanity.com/paper/2210.03069/) (2022)
- [Convex Approximation of Two-Layer ReLU Networks for Hidden State Differential Privacy](https://mlsanity.com/paper/2407.04884/) (2024)
- [Wasserstein Distributionally Robust Shallow Convex Neural Networks](https://mlsanity.com/paper/2407.16800/) (2024)
- [Spring-block theory of feature learning in deep neural networks](https://mlsanity.com/paper/2407.19353/) (2024)
- [Fixing the NTK: From Neural Network Linearizations to Exact Convex Programs](https://mlsanity.com/paper/2309.15096/) (2023)
- [A Library of Mirrors: Deep Neural Nets in Low Dimensions are Convex Lasso Models with Reflection Features](https://mlsanity.com/paper/2403.01046/) (2024)
- [Favorability of Loss Landscape with Weight Decay Requires Both Large Overparametrization and Initialization](https://mlsanity.com/paper/2505.22578/) (2025)
- [Fine-Tuning Adaptive Stochastic Optimizers: Determining the Optimal Hyperparameter ε via Gradient Magnitude Histogram Analysis](https://mlsanity.com/paper/2311.11532/) (2023)
- [Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks](https://mlsanity.com/paper/2501.05930/) (2025)
- [Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback](https://mlsanity.com/paper/2605.26373/) (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)
- [Removing spurious minima for planar features by skip connections](https://mlsanity.com/paper/2610.01728/) (2026)

## Abstract (arXiv)

We prove that finding all globally optimal two-layer ReLU neural networks can be performed by solving a convex optimization program with cone constraints. Our analysis is novel, characterizes all optimal solutions, and does not leverage duality-based analysis which was recently used to lift neural network training into convex spaces. Given the set of solutions of our convex optimization program, we show how to construct exactly the entire set of optimal neural networks. We provide a detailed characterization of this optimal set and its invariant transformations. As additional consequences of our convex perspective, (i) we establish that Clarke stationary points found by stochastic gradient descent correspond to the global optimum of a subsampled convex problem (ii) we provide a polynomial-time algorithm for checking if a neural network is a global minimum of the training loss (iii) we provide an explicit construction of a continuous path between any neural network and the global minimum of its sublevel set and (iv) characterize the minimal size of the hidden layer so that the neural network optimization landscape has no spurious valleys. Overall, we provide a rich framework for studying the landscape of neural network training loss through convexity.