mlsanityData to 14 Oct 2026

Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithms

arXiv 2012.13329 ↗First posted 24 Dec 2020cs.LG cs.AI cs.CCcited by 34

Not on the map. Why?

Abstract (arXiv)

We describe the convex semi-infinite dual of the two-layer vector-output ReLU neural network training problem. This semi-infinite dual admits a finite dimensional representation, but its support is over a convex set which is difficult to characterize. In particular, we demonstrate that the non-convex neural network training problem is equivalent to a finite-dimensional convex copositive program. Our work is the first to identify this strong connection between the global optima of neural networks and those of copositive programs. We thus demonstrate how neural networks implicitly attempt to solve copositive programs via semi-nonnegative matrix factorization, and draw key insights from this formulation. We describe the first algorithms for provably finding the global minimum of the vector output neural network training problem, which are polynomial in the number of samples for a fixed data rank, yet exponential in the dimension. However, in the case of convolutional architectures, the computational complexity is exponential in only the filter size and polynomial in all other parameters. We describe the circumstances in which we can find the global optimum of this neural network training problem exactly with soft-thresholded SVD, and provide a copositive relaxation which is guaranteed to be exact for certain classes of problems, and which corresponds with the solution of Stochastic Gradient Descent in practice.

Key facts. Cited by 34 papers in the map (data through 14 Oct 2026). First posted on arXiv 24 Dec 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 10; 2022: 6; 2023: 10; 2024: 3; 2025: 2; 2026: 3.

34 papers.

Sort:

By area:

  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. 2021Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programscited by 25
  5. 2021Demystifying Batch Normalization in ReLU Networks: Equivalent Convex Optimization Models and Implicit Regularizationcited by 21
  6. 2021Inductive Bias of Multi-Channel Linear Convolutional Networks with Bounded Weight Normcited by 18
  7. 2023Variation Spaces for Multi-Output Neural Networks: Insights on Multi-Task Learning and Network Compressioncited by 18
  8. 2022Efficient Global Optimization of Two-Layer ReLU Networks: Quadratic-Time Algorithms and Adversarial Trainingcited by 15
  9. 2021Neural Spectrahedra and Semidefinite Lifts: Global Convex Optimization of Polynomial Activation Neural Networks in Fully Polynomial-Timecited by 14
  10. 2021Hidden Convexity of Wasserstein GANs: Interpretable Generative Models with Closed-Form Solutionscited by 14
  11. 2021Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networkscited by 14
  12. 2021The Convex Geometry of Backpropagation: Neural Network Gradient Flows Converge to Extreme Points of the Dual Convex Programcited by 11
22 more
  1. 2024Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Timecited by 11
  2. 2023Optimal Sets and Solution Paths of ReLU Networkscited by 10
  3. 2021Parallel Deep Neural Networks Have Zero Duality Gapcited by 9
  4. 2022Optimal Neural Network Approximation of Wasserstein Gradient Direction via Convex Optimizationcited by 9
  5. 2023Globally Optimal Training of Neural Networks with Threshold Activation Functionscited by 9
  6. 2022Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimizationcited by 8
  7. 2023Implicit Regularization for Group Sparsitycited by 8
  8. 2023The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Modelscited by 7
  9. 2024Analyzing Neural Network-Based Generative Diffusion Models through Convex Optimizationcited by 7
  10. 2021Training Quantized Neural Networks to Global Optimality via Semidefinite Programmingcited by 6
  11. 2025When Diffusion Models Memorize: Inductive Biases in Probability Flow of Minimum-Norm Shallow Neural Netscited by 6
  12. 2023On the Global Convergence of Natural Actor-Critic with Two-layer Neural Network Parametrizationcited by 5
  13. 2021Practical Convex Formulation of Robust One-hidden-layer Neural Network Trainingcited by 4
  14. 2023From Complexity to Clarity: Analytical Expressions of Deep Neural Network Weights via Clifford's Geometric Algebra and Convexitycited by 4
  15. 2022On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrizationcited by 3
  16. 2023Fixing the NTK: From Neural Network Linearizations to Exact Convex Programscited by 1
  17. 2025Implicit Bias in Matrix Factorization and its Explicit Realization in a New Architecturecited by 1
  18. 2023Convex Dual Theory Analysis of Two-Layer Convolutional Neural Networks with Soft-Thresholdingcited by 0
  19. 2024Convex Distillation: Efficient Compression of Deep Networks via Convex Optimizationcited by 0
  20. 2026On the Loss Landscape Geometry of Regularized Deep Matrix Factorization: Uniqueness and Sharpnesscited by 0
  21. 2026Exact Convex Reformulations of Linear Neural Networks via Completely Positive Liftingcited by 0
  22. 2026Convex Low-resource Accent-Robust Language Detection in Speech Recognitioncited by 0