# Optimal Sets and Solution Paths of ReLU Networks

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 47 references that are in the map.
- First posted on arXiv 31 May 2023.

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

- [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)
- [Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNs](https://mlsanity.com/paper/1802.10026/) (2018)
- [What is the State of Neural Network Pruning?](https://mlsanity.com/paper/2003.03033/) (2020)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Essentially No Barriers in Neural Network Energy Landscape](https://mlsanity.com/paper/1803.00885/) (2018)
- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [Online Learning Rate Adaptation with Hypergradient Descent](https://mlsanity.com/paper/1703.04782/) (2017)
- [Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks](https://mlsanity.com/paper/2002.10553/) (2020)
- [Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets](https://mlsanity.com/paper/1906.06247/) (2019)
- [On Connected Sublevel Sets in Deep Learning](https://mlsanity.com/paper/1901.07417/) (2019)
- [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)
- [Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositions](https://mlsanity.com/paper/2202.01331/) (2022)
- [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)
- [Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programs](https://mlsanity.com/paper/2110.05518/) (2021)
- [Demystifying Batch Normalization in ReLU Networks: Equivalent Convex Optimization Models and Implicit Regularization](https://mlsanity.com/paper/2103.01499/) (2021)
- [Decoupling Gating from Linearity](https://mlsanity.com/paper/1906.05032/) (2019)

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

- [The Real Tropical Geometry of Neural Networks](https://mlsanity.com/paper/2403.11871/) (2024)
- [A Library of Mirrors: Deep Neural Nets in Low Dimensions are Convex Lasso Models with Reflection Features](https://mlsanity.com/paper/2403.01046/) (2024)
- [Adversarial Training of Two-Layer Polynomial and ReLU Activation Networks via Convex Optimization](https://mlsanity.com/paper/2405.14033/) (2024)
- [Favorability of Loss Landscape with Weight Decay Requires Both Large Overparametrization and Initialization](https://mlsanity.com/paper/2505.22578/) (2025)
- [Unveiling Hidden Convexity in Deep Learning: a Sparse Signal Processing Perspective](https://mlsanity.com/paper/2603.23831/) (2026)
- [Algebraic Approach to Ridge-Regularized Mean Squared Error Minimization in Minimal ReLU Neural Network](https://mlsanity.com/paper/2508.17783/) (2025)
- [From Approximation Rates to Loss-Landscape Barrier Decay in Shallow ReLU Networks](https://mlsanity.com/paper/2602.17596/) (2026)
- [Optimizer-Induced Mode Connectivity: From AdamW to Muon](https://mlsanity.com/paper/2605.09991/) (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)
- [Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2610.05789/) (2026)

## Abstract (arXiv)

We develop an analytical framework to characterize the set of optimal ReLU neural networks by reformulating the non-convex training problem as a convex program. We show that the global optima of the convex parameterization are given by a polyhedral set and then extend this characterization to the optimal set of the non-convex training objective. Since all stationary points of the ReLU training problem can be represented as optima of sub-sampled convex programs, our work provides a general expression for all critical points of the non-convex objective. We then leverage our results to provide an optimal pruning algorithm for computing minimal networks, establish conditions for the regularization path of ReLU networks to be continuous, and develop sensitivity results for minimal ReLU networks.