# Convex Geometry and Duality of Over-parameterized Neural Networks

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

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2020.

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

- [On the Implicit Bias in Deep-Learning Algorithms](https://mlsanity.com/paper/2208.12591/) (2022)
- [Implicit Regularization Towards Rank Minimization in ReLU Networks](https://mlsanity.com/paper/2201.12760/) (2022)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [On Margin Maximization in Linear and ReLU Networks](https://mlsanity.com/paper/2110.02732/) (2021)
- [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)
- [On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias](https://mlsanity.com/paper/2205.09072/) (2022)
- [Variation Spaces for Multi-Output Neural Networks: Insights on Multi-Task Learning and Network Compression](https://mlsanity.com/paper/2305.16534/) (2023)
- [Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputs](https://mlsanity.com/paper/2306.06479/) (2023)
- [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)
- [Mean-field Analysis of Piecewise Linear Solutions for Wide ReLU Networks](https://mlsanity.com/paper/2111.02278/) (2021)
- [Convexifying Transformers: Improving optimization and understanding of transformer networks](https://mlsanity.com/paper/2211.11052/) (2022)
- [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)
- [Noisy Interpolation Learning with Shallow Univariate ReLU Networks](https://mlsanity.com/paper/2307.15396/) (2023)
- [Deep Learning meets Nonparametric Regression: Are Weight-Decayed DNNs Locally Adaptive?](https://mlsanity.com/paper/2204.09664/) (2022)
- [Parallel Deep Neural Networks Have Zero Duality Gap](https://mlsanity.com/paper/2110.06482/) (2021)
- [Globally Optimal Training of Neural Networks with Threshold Activation Functions](https://mlsanity.com/paper/2303.03382/) (2023)
- [How do Minimum-Norm Shallow Denoisers Look in Function Space?](https://mlsanity.com/paper/2311.06748/) (2023)
- [The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Models](https://mlsanity.com/paper/2312.12657/) (2023)
- [Intrinsic dimensionality and generalization properties of the R-norm inductive bias](https://mlsanity.com/paper/2206.05317/) (2022)
- [Efficient displacement convex optimization with particle gradient descent](https://mlsanity.com/paper/2302.04753/) (2023)
- [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)
- [Information Processing Equalities and the Information-Risk Bridge](https://mlsanity.com/paper/2207.11987/) (2022)
- [Overparameterized ReLU Neural Networks Learn the Simplest Models: Neural Isometry and Exact Recovery](https://mlsanity.com/paper/2209.15265/) (2022)
- [Computational Advantages of Multi-Grade Deep Learning: Convergence Analysis and Performance Insights](https://mlsanity.com/paper/2507.20351/) (2025)
- [PathProx: A Proximal Gradient Algorithm for Weight Decay Regularized Deep Neural Networks](https://mlsanity.com/paper/2210.03069/) (2022)
- [Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes](https://mlsanity.com/paper/2311.10972/) (2023)
- [Supervising the Decoder of Variational Autoencoders to Improve Scientific Utility](https://mlsanity.com/paper/2109.04561/) (2021)

## Abstract (arXiv)

We develop a convex analytic approach to analyze finite width two-layer ReLU networks. We first prove that an optimal solution to the regularized training problem can be characterized as extreme points of a convex set, where simple solutions are encouraged via its convex geometrical properties. We then leverage this characterization to show that an optimal set of parameters yield linear spline interpolation for regression problems involving one dimensional or rank-one data. We also characterize the classification decision regions in terms of a kernel matrix and minimum ℓ1-norm solutions. This is in contrast to Neural Tangent Kernel which is unable to explain predictions of finite width networks. Our convex geometric characterization also provides intuitive explanations of hidden neurons as auto-encoders. In higher dimensions, we show that the training problem can be cast as a finite dimensional convex problem with infinitely many constraints. Then, we apply certain convex relaxations and introduce a cutting-plane algorithm to globally optimize the network. We further analyze the exactness of the relaxations to provide conditions for the convergence to a global optimum. Our analysis also shows that optimal network parameters can be also characterized as interpretable closed-form formulas in some practically relevant special cases.