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

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

## Key facts

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

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

- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositions](https://mlsanity.com/paper/2202.01331/) (2022)
- [Unraveling Attention via Convex Duality: Analysis and Interpretations of Vision Transformers](https://mlsanity.com/paper/2205.08078/) (2022)
- [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)
- [Inductive Bias of Multi-Channel Linear Convolutional Networks with Bounded Weight Norm](https://mlsanity.com/paper/2102.12238/) (2021)
- [Variation Spaces for Multi-Output Neural Networks: Insights on Multi-Task Learning and Network Compression](https://mlsanity.com/paper/2305.16534/) (2023)
- [Efficient Global Optimization of Two-Layer ReLU Networks: Quadratic-Time Algorithms and Adversarial Training](https://mlsanity.com/paper/2201.01965/) (2022)
- [Neural Spectrahedra and Semidefinite Lifts: Global Convex Optimization of Polynomial Activation Neural Networks in Fully Polynomial-Time](https://mlsanity.com/paper/2101.02429/) (2021)
- [Hidden Convexity of Wasserstein GANs: Interpretable Generative Models with Closed-Form Solutions](https://mlsanity.com/paper/2107.05680/) (2021)
- [Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks](https://mlsanity.com/paper/2110.09548/) (2021)
- [The Convex Geometry of Backpropagation: Neural Network Gradient Flows Converge to Extreme Points of the Dual Convex Program](https://mlsanity.com/paper/2110.06488/) (2021)
- [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)
- [Parallel Deep Neural Networks Have Zero Duality Gap](https://mlsanity.com/paper/2110.06482/) (2021)
- [Optimal Neural Network Approximation of Wasserstein Gradient Direction via Convex Optimization](https://mlsanity.com/paper/2205.13098/) (2022)
- [Globally Optimal Training of Neural Networks with Threshold Activation Functions](https://mlsanity.com/paper/2303.03382/) (2023)
- [Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization](https://mlsanity.com/paper/2203.12633/) (2022)
- [Implicit Regularization for Group Sparsity](https://mlsanity.com/paper/2301.12540/) (2023)
- [The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Models](https://mlsanity.com/paper/2312.12657/) (2023)
- [Analyzing Neural Network-Based Generative Diffusion Models through Convex Optimization](https://mlsanity.com/paper/2402.01965/) (2024)
- [Training Quantized Neural Networks to Global Optimality via Semidefinite Programming](https://mlsanity.com/paper/2105.01420/) (2021)
- [When Diffusion Models Memorize: Inductive Biases in Probability Flow of Minimum-Norm Shallow Neural Nets](https://mlsanity.com/paper/2506.19031/) (2025)
- [On the Global Convergence of Natural Actor-Critic with Two-layer Neural Network Parametrization](https://mlsanity.com/paper/2306.10486/) (2023)
- [Practical Convex Formulation of Robust One-hidden-layer Neural Network Training](https://mlsanity.com/paper/2105.12237/) (2021)
- [From Complexity to Clarity: Analytical Expressions of Deep Neural Network Weights via Clifford's Geometric Algebra and Convexity](https://mlsanity.com/paper/2309.16512/) (2023)
- [On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrization](https://mlsanity.com/paper/2211.07675/) (2022)
- [Fixing the NTK: From Neural Network Linearizations to Exact Convex Programs](https://mlsanity.com/paper/2309.15096/) (2023)
- [Implicit Bias in Matrix Factorization and its Explicit Realization in a New Architecture](https://mlsanity.com/paper/2501.16322/) (2025)
- [Convex Dual Theory Analysis of Two-Layer Convolutional Neural Networks with Soft-Thresholding](https://mlsanity.com/paper/2304.06959/) (2023)

## 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.