mlsanityData to 14 Oct 2026

Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programs

arXiv 2110.05518 ↗First posted 11 Oct 2021cs.LG cs.AI cs.CCcited by 25

Not on the map. Why?

Abstract (arXiv)

Understanding the fundamental mechanism behind the success of deep neural networks is one of the key challenges in the modern machine learning literature. Despite numerous attempts, a solid theoretical analysis is yet to be developed. In this paper, we develop a novel unified framework to reveal a hidden regularization mechanism through the lens of convex optimization. We first show that the training of multiple three-layer ReLU sub-networks with weight decay regularization can be equivalently cast as a convex optimization problem in a higher dimensional space, where sparsity is enforced via a group ℓ1-norm regularization. Consequently, ReLU networks can be interpreted as high dimensional feature selection methods. More importantly, we then prove that the equivalent convex problem can be globally optimized by a standard convex optimization solver with a polynomial-time complexity with respect to the number of samples and data dimension when the width of the network is fixed. Finally, we numerically validate our theoretical results via experiments involving both synthetic and real datasets.

Key facts. Cited by 25 papers in the map (data through 14 Oct 2026). Builds on 27 of its 54 references that are in the map. First posted on arXiv 11 Oct 2021.

Builds on

27 of 54 references.

References · 27

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,349
  3. 2016Wide Residual Networkscited by 3,070
  4. 2016Aggregated Residual Transformations for Deep Neural Networkscited by 2,546
  5. 2021Convex optimizationcited by 2,515
  6. 2016Xception: Deep Learning with Depthwise Separable Convolutionscited by 2,332
  7. 2016Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learningcited by 1,512
  8. 2016SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and <0.5MB model sizecited by 1,060
  9. 2016CVXPY: A Python-Embedded Modeling Language for Convex Optimizationcited by 641
  10. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 342
  11. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 331
  12. 2018On the Optimization of Deep Networks: Implicit Acceleration by Overparameterizationcited by 284
15 more
  1. 2017A Rewriting System for Convex Optimization Problemscited by 179
  2. 2018Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networkscited by 142
  3. 2019How do infinite width bounded norm networks look in function space?cited by 106
  4. 2017Spurious Local Minima are Common in Two-Layer ReLU Neural Networkscited by 104
  5. 2018On the Power of Over-parametrization in Neural Networks with Quadratic Activationcited by 102
  6. 2020Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networkscited by 98
  7. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 81
  8. 2017Failures of Gradient-Based Deep Learningcited by 80
  9. 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
  10. 2017Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputscited by 61
  11. 2020Convex Geometry and Duality of Over-parameterized Neural Networkscited by 49
  12. 2020Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithmscited by 34
  13. 2016Efficient approaches for escaping higher order saddle points in non-convex optimizationcited by 23
  14. 2021Demystifying Batch Normalization in ReLU Networks: Equivalent Convex Optimization Models and Implicit Regularizationcited by 21
  15. 2021Hidden Convexity of Wasserstein GANs: Interpretable Generative Models with Closed-Form Solutionscited by 14

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 4; 2022: 6; 2023: 7; 2024: 3; 2025: 1; 2026: 4.

25 papers.

Sort:

  1. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  2. 2022Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositionscited by 31
  3. 2022Unraveling Attention via Convex Duality: Analysis and Interpretations of Vision Transformerscited by 30
  4. 2024The Real Tropical Geometry of Neural Networkscited by 24
  5. 2022Efficient Global Optimization of Two-Layer ReLU Networks: Quadratic-Time Algorithms and Adversarial Trainingcited by 15
  6. 2021Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networkscited by 14
  7. 2021Neural networks with linear threshold activations: structure and algorithmscited by 12
  8. 2021The Convex Geometry of Backpropagation: Neural Network Gradient Flows Converge to Extreme Points of the Dual Convex Programcited by 11
  9. 2024Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Timecited by 11
  10. 2022Deep Learning meets Nonparametric Regression: Are Weight-Decayed DNNs Locally Adaptive?cited by 10
  11. 2023Optimal Sets and Solution Paths of ReLU Networkscited by 10
  12. 2021Parallel Deep Neural Networks Have Zero Duality Gapcited by 9
13 more
  1. 2023Globally Optimal Training of Neural Networks with Threshold Activation Functionscited by 9
  2. 2022Piecewise Linear Neural Networks and Deep Learningcited by 7
  3. 2023The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Modelscited by 7
  4. 2023From Complexity to Clarity: Analytical Expressions of Deep Neural Network Weights via Clifford's Geometric Algebra and Convexitycited by 4
  5. 2022Overparameterized ReLU Neural Networks Learn the Simplest Models: Neural Isometry and Exact Recoverycited by 3
  6. 2024Convex Approximation of Two-Layer ReLU Networks for Hidden State Differential Privacycited by 2
  7. 2023Fixing the NTK: From Neural Network Linearizations to Exact Convex Programscited by 1
  8. 2023Convex Dual Theory Analysis of Two-Layer Convolutional Neural Networks with Soft-Thresholdingcited by 0
  9. 2025Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networkscited by 0
  10. 2026Why ReLU? A Bit-Model Dichotomy for Deep Network Trainingcited by 0
  11. 2026Exact Convex Reformulations of Linear Neural Networks via Completely Positive Liftingcited by 0
  12. 2026Convex training of Lipschitz-regularized shallow neural networkscited by 0
  13. 2026Effects of width-dependent model hyperparameters and ℓ2-regularization on the loss landscape of two-layer ReLU networkscited by 0