# Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositions

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 75 references that are in the map.
- First posted on arXiv 2 Feb 2022.

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

- [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)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Deep Reinforcement Learning that Matters](https://mlsanity.com/paper/1709.06560/) (2017)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Input Convex Neural Networks](https://mlsanity.com/paper/1609.07152/) (2016)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Greedy Layerwise Learning Can Scale to ImageNet](https://mlsanity.com/paper/1812.11446/) (2018)
- [Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks](https://mlsanity.com/paper/2002.10553/) (2020)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [Revealing the Structure of Deep Neural Networks via Convex Duality](https://mlsanity.com/paper/2002.09773/) (2020)
- [A Brief Prehistory of Double Descent](https://mlsanity.com/paper/2004.04328/) (2020)
- [Geometry of Optimization and Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1705.03071/) (2017)
- [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)
- [On the Reproducibility of Neural Network Predictions](https://mlsanity.com/paper/2102.03349/) (2021)
- [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)
- [The Curious Case of Convex Neural Networks](https://mlsanity.com/paper/2006.05103/) (2020)
- [Convex Regularization Behind Neural Reconstruction](https://mlsanity.com/paper/2012.05169/) (2020)
- [Efficient Global Optimization of Two-Layer ReLU Networks: Quadratic-Time Algorithms and Adversarial Training](https://mlsanity.com/paper/2201.01965/) (2022)
- [Hidden Convexity of Wasserstein GANs: Interpretable Generative Models with Closed-Form Solutions](https://mlsanity.com/paper/2107.05680/) (2021)
- [Decoupling Gating from Linearity](https://mlsanity.com/paper/1906.05032/) (2019)

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

- [Riemannian Preconditioned LoRA for Fine-Tuning Foundation Models](https://mlsanity.com/paper/2402.02347/) (2024)
- [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)
- [Variation Spaces for Multi-Output Neural Networks: Insights on Multi-Task Learning and Network Compression](https://mlsanity.com/paper/2305.16534/) (2023)
- [Convexifying Transformers: Improving optimization and understanding of transformer networks](https://mlsanity.com/paper/2211.11052/) (2022)
- [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)
- [Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks](https://mlsanity.com/paper/2404.18769/) (2024)
- [Analyzing Neural Network-Based Generative Diffusion Models through Convex Optimization](https://mlsanity.com/paper/2402.01965/) (2024)
- [Efficient displacement convex optimization with particle gradient descent](https://mlsanity.com/paper/2302.04753/) (2023)
- [On the Global Convergence of Natural Actor-Critic with Two-layer Neural Network Parametrization](https://mlsanity.com/paper/2306.10486/) (2023)
- [CRONOS: Enhancing Deep Learning with Scalable GPU Accelerated Convex Neural Networks](https://mlsanity.com/paper/2411.01088/) (2024)
- [On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrization](https://mlsanity.com/paper/2211.07675/) (2022)
- [On the Interplay of Priors and Overparametrization in Bayesian Neural Network Posteriors](https://mlsanity.com/paper/2603.22030/) (2026)
- [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)
- [Generative Feature Training of Thin 2-Layer Networks](https://mlsanity.com/paper/2411.06848/) (2024)
- [Training a Two Layer ReLU Network Analytically](https://mlsanity.com/paper/2304.02972/) (2023)
- [Fixing the NTK: From Neural Network Linearizations to Exact Convex Programs](https://mlsanity.com/paper/2309.15096/) (2023)
- [Randomized Geometric Algebra Methods for Convex Neural Networks](https://mlsanity.com/paper/2406.02806/) (2024)
- [Why Line Search when you can Plane Search? SO-Friendly Neural Networks allow Per-Iteration Optimization of Learning and Momentum Rates for Every Layer](https://mlsanity.com/paper/2406.17954/) (2024)
- [Unveiling Hidden Convexity in Deep Learning: a Sparse Signal Processing Perspective](https://mlsanity.com/paper/2603.23831/) (2026)
- [Convex Dual Theory Analysis of Two-Layer Convolutional Neural Networks with Soft-Thresholding](https://mlsanity.com/paper/2304.06959/) (2023)
- [Convex Distillation: Efficient Compression of Deep Networks via Convex Optimization](https://mlsanity.com/paper/2410.06567/) (2024)
- [Sliced-Wasserstein Distance-based Data Selection](https://mlsanity.com/paper/2504.12918/) (2025)
- [Algebraic Approach to Ridge-Regularized Mean Squared Error Minimization in Minimal ReLU Neural Network](https://mlsanity.com/paper/2508.17783/) (2025)
- [A Recovery Guarantee for Sparse Neural Networks](https://mlsanity.com/paper/2509.20323/) (2025)
- [Convex Low-resource Accent-Robust Language Detection in Speech Recognition](https://mlsanity.com/paper/2605.23235/) (2026)
- [Convex Optimization for Alignment and Preference Learning on a Single GPU](https://mlsanity.com/paper/2605.23244/) (2026)

## Abstract (arXiv)

We develop fast algorithms and robust software for convex optimization of two-layer neural networks with ReLU activation functions. Our work leverages a convex reformulation of the standard weight-decay penalized training problem as a set of group-ℓ1-regularized data-local models, where locality is enforced by polyhedral cone constraints. In the special case of zero-regularization, we show that this problem is exactly equivalent to unconstrained optimization of a convex "gated ReLU" network with non-singular gates. For problems with non-zero regularization, we show that convex gated ReLU models obtain data-dependent approximation bounds for the ReLU training problem. To optimize the convex reformulations, we develop an accelerated proximal gradient method and a practical augmented Lagrangian solver. We show that these approaches are faster than standard training heuristics for the non-convex problem, such as SGD, and outperform commercial interior-point solvers. Experimentally, we verify our theoretical results, explore the group-ℓ1 regularization path, and scale convex optimization for neural networks to image classification on MNIST and CIFAR-10.