mlsanityData to 7 Oct 2026

Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time

arXiv 2402.03625 ↗First posted 6 Feb 2024cs.LG math.OCcited by 11

Not on the map. Why?

Abstract (arXiv)

In this paper, we study the optimality gap between two-layer ReLU networks regularized with weight decay and their convex relaxations. We show that when the training data is random, the relative optimality gap between the original problem and its relaxation can be bounded by a factor of O(log n^0.5), where n is the number of training samples. A simple application leads to a tractable polynomial-time algorithm that is guaranteed to solve the original non-convex problem up to a logarithmic factor. Moreover, under mild assumptions, we show that local gradient methods converge to a point with low training loss with high probability. Our result is an exponential improvement compared to existing results and sheds new light on understanding why local gradient methods work well.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 34 of its 55 references that are in the map. First posted on arXiv 6 Feb 2024.

Builds on

34 of 55 references.

References · 34

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  3. 2021Convex optimizationcited by 2,479
  4. 2017Visualizing the Loss Landscape of Neural Netscited by 1,126
  5. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  6. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  7. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  8. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
  9. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
  10. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 139
  11. 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
  12. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 120
22 more
  1. 2020Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networkscited by 96
  2. 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
  3. 2017Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputscited by 61
  4. 2017An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysiscited by 52
  5. 2021A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Networkcited by 47
  6. 2017Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minimacited by 40
  7. 2020Tight Hardness Results for Training Depth-2 ReLU Networkscited by 35
  8. 2020Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithmscited by 33
  9. 2018Learning Two Layer Rectified Neural Networks in Polynomial Timecited by 31
  10. 2022Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositionscited by 31
  11. 2020The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutionscited by 30
  12. 2022Unraveling Attention via Convex Duality: Analysis and Interpretations of Vision Transformerscited by 30
  13. 2016No bad local minima: Data independent training error guarantees for multilayer neural networkscited by 29
  14. 2021Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programscited by 25
  15. 2018Complexity of Training ReLU Neural Networkcited by 23
  16. 2018Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalizationcited by 21
  17. 2017Exponentially vanishing sub-optimal local minima in multilayer neural networkscited by 19
  18. 2021Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activationscited by 15
  19. 2022Efficient Global Optimization of Two-Layer ReLU Networks: Quadratic-Time Algorithms and Adversarial Trainingcited by 15
  20. 2017The Multilinear Structure of ReLU Networkscited by 9
  21. 2021Parallel Deep Neural Networks Have Zero Duality Gapcited by 9
  22. 2023Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopescited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 4; 2025: 3; 2026: 4.

11 papers.

  1. 2024CRONOS: Enhancing Deep Learning with Scalable GPU Accelerated Convex Neural Networkscited by 4
  2. 2024Convex Approximation of Two-Layer ReLU Networks for Hidden State Differential Privacycited by 2
  3. 2024A Library of Mirrors: Deep Neural Nets in Low Dimensions are Convex Lasso Models with Reflection Featurescited by 1
  4. 2026Unveiling Hidden Convexity in Deep Learning: a Sparse Signal Processing Perspectivecited by 1
  5. 2024Convex Distillation: Efficient Compression of Deep Networks via Convex Optimizationcited by 0
  6. 2025Learning Provably Improves the Convergence of Gradient Descentcited by 0
  7. 2025Algebraic Approach to Ridge-Regularized Mean Squared Error Minimization in Minimal ReLU Neural Networkcited by 0
  8. 2025A Recovery Guarantee for Sparse Neural Networkscited by 0
  9. 2026Contract And Conquer: How to Provably Compute Adversarial Examples for a Black-Box Model?cited by 0
  10. 2026Convex Low-resource Accent-Robust Language Detection in Speech Recognitioncited by 0
  11. 2026Convex Optimization for Alignment and Preference Learning on a Single GPUcited by 0