mlsanityData to 14 Oct 2026

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

arXiv 2202.01331 ↗First posted 2 Feb 2022cs.LGcited by 31

Not on the map. Why?

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.

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

27 of 75 references.

References · 27

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  3. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 927
  4. 2017Deep Reinforcement Learning that Matterscited by 754
  5. 2019Deep Double Descent: Where Bigger Models and More Data Hurtcited by 672
  6. 2016CVXPY: A Python-Embedded Modeling Language for Convex Optimizationcited by 641
  7. 2016Input Convex Neural Networkscited by 414
  8. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 331
  9. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 306
  10. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 243
  11. 2017A Rewriting System for Convex Optimization Problemscited by 179
  12. 2018Greedy Layerwise Learning Can Scale to ImageNetcited by 115
15 more
  1. 2020Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networkscited by 98
  2. 2014Linear Coupling: An Ultimate Unification of Gradient and Mirror Descentcited by 58
  3. 2020Revealing the Structure of Deep Neural Networks via Convex Dualitycited by 54
  4. 2020A Brief Prehistory of Double Descentcited by 44
  5. 2017Geometry of Optimization and Implicit Regularization in Deep Learningcited by 39
  6. 2020Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithmscited by 34
  7. 2020The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutionscited by 30
  8. 2021On the Reproducibility of Neural Network Predictionscited by 29
  9. 2021Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programscited by 25
  10. 2021Demystifying Batch Normalization in ReLU Networks: Equivalent Convex Optimization Models and Implicit Regularizationcited by 21
  11. 2020The Curious Case of Convex Neural Networkscited by 16
  12. 2020Convex Regularization Behind Neural Reconstructioncited by 15
  13. 2022Efficient Global Optimization of Two-Layer ReLU Networks: Quadratic-Time Algorithms and Adversarial Trainingcited by 15
  14. 2021Hidden Convexity of Wasserstein GANs: Interpretable Generative Models with Closed-Form Solutionscited by 14
  15. 2019Decoupling Gating from Linearitycited by 13

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 4; 2023: 7; 2024: 12; 2025: 3; 2026: 5.

31 papers.

Sort:

By area:

  1. 2024Riemannian Preconditioned LoRA for Fine-Tuning Foundation Modelscited by 52
  2. 2022Unraveling Attention via Convex Duality: Analysis and Interpretations of Vision Transformerscited by 30
  3. 2024The Real Tropical Geometry of Neural Networkscited by 24
  4. 2023Variation Spaces for Multi-Output Neural Networks: Insights on Multi-Task Learning and Network Compressioncited by 18
  5. 2022Convexifying Transformers: Improving optimization and understanding of transformer networkscited by 12
  6. 2024Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Timecited by 11
  7. 2023Optimal Sets and Solution Paths of ReLU Networkscited by 10
  8. 2024Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networkscited by 8
  9. 2024Analyzing Neural Network-Based Generative Diffusion Models through Convex Optimizationcited by 7
  10. 2023Efficient displacement convex optimization with particle gradient descentcited by 5
  11. 2023On the Global Convergence of Natural Actor-Critic with Two-layer Neural Network Parametrizationcited by 5
  12. 2024CRONOS: Enhancing Deep Learning with Scalable GPU Accelerated Convex Neural Networkscited by 4
19 more
  1. 2022On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrizationcited by 3
  2. 2026On the Interplay of Priors and Overparametrization in Bayesian Neural Network Posteriorscited by 3
  3. 2022PathProx: A Proximal Gradient Algorithm for Weight Decay Regularized Deep Neural Networkscited by 2
  4. 2024Convex Approximation of Two-Layer ReLU Networks for Hidden State Differential Privacycited by 2
  5. 2024Wasserstein Distributionally Robust Shallow Convex Neural Networkscited by 2
  6. 2024Generative Feature Training of Thin 2-Layer Networkscited by 2
  7. 2023Training a Two Layer ReLU Network Analyticallycited by 1
  8. 2023Fixing the NTK: From Neural Network Linearizations to Exact Convex Programscited by 1
  9. 2024Randomized Geometric Algebra Methods for Convex Neural Networkscited by 1
  10. 2024Why Line Search when you can Plane Search? SO-Friendly Neural Networks allow Per-Iteration Optimization of Learning and Momentum Rates for Every Layercited by 1
  11. 2026Unveiling Hidden Convexity in Deep Learning: a Sparse Signal Processing Perspectivecited by 1
  12. 2023Convex Dual Theory Analysis of Two-Layer Convolutional Neural Networks with Soft-Thresholdingcited by 0
  13. 2024Convex Distillation: Efficient Compression of Deep Networks via Convex Optimizationcited by 0
  14. 2025Sliced-Wasserstein Distance-based Data Selectioncited by 0
  15. 2025Algebraic Approach to Ridge-Regularized Mean Squared Error Minimization in Minimal ReLU Neural Networkcited by 0
  16. 2025A Recovery Guarantee for Sparse Neural Networkscited by 0
  17. 2026Convex Low-resource Accent-Robust Language Detection in Speech Recognitioncited by 0
  18. 2026Convex Optimization for Alignment and Preference Learning on a Single GPUcited by 0
  19. 2026Convex training of Lipschitz-regularized shallow neural networkscited by 0