# Parallel Deep Neural Networks Have Zero Duality Gap

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 52 references that are in the map.
- First posted on arXiv 13 Oct 2021.

## Builds on (most cited first, 30 of 32)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Aggregated Residual Transformations for Deep Neural Networks](https://mlsanity.com/paper/1611.05431/) (2016)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Xception: Deep Learning with Depthwise Separable Convolutions](https://mlsanity.com/paper/1610.02357/) (2016)
- [Identity Mappings in Deep Residual Networks](https://mlsanity.com/paper/1603.05027/) (2016)
- [Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learning](https://mlsanity.com/paper/1602.07261/) (2016)
- [SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and <0.5MB model size](https://mlsanity.com/paper/1602.07360/) (2016)
- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit](https://mlsanity.com/paper/1902.06015/) (2019)
- [Gradient descent aligns the layers of deep linear networks](https://mlsanity.com/paper/1810.02032/) (2018)
- [Constrained Reinforcement Learning Has Zero Duality Gap](https://mlsanity.com/paper/1910.13393/) (2019)
- [Mean Field Analysis of Neural Networks: A Central Limit Theorem](https://mlsanity.com/paper/1808.09372/) (2018)
- [Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks](https://mlsanity.com/paper/2002.10553/) (2020)
- [Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy](https://mlsanity.com/paper/2007.06738/) (2020)
- [Revealing the Structure of Deep Neural Networks via Convex Duality](https://mlsanity.com/paper/2002.09773/) (2020)
- [Stochastic Particle Gradient Descent for Infinite Ensembles](https://mlsanity.com/paper/1712.05438/) (2017)
- [Sparse Optimization on Measures with Over-parameterized Gradient Descent](https://mlsanity.com/paper/1907.10300/) (2019)
- [Convex Geometry and Duality of Over-parameterized Neural Networks](https://mlsanity.com/paper/2002.11219/) (2020)
- [Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithms](https://mlsanity.com/paper/2012.13329/) (2020)
- [Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programs](https://mlsanity.com/paper/2110.05518/) (2021)
- [Global convergence of neuron birth-death dynamics](https://mlsanity.com/paper/1902.01843/) (2019)
- [Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis](https://mlsanity.com/paper/2012.15477/) (2020)
- [Demystifying Batch Normalization in ReLU Networks: Equivalent Convex Optimization Models and Implicit Regularization](https://mlsanity.com/paper/2103.01499/) (2021)
- [On Learnability via Gradient Method for Two-Layer ReLU Neural Networks in Teacher-Student Setting](https://mlsanity.com/paper/2106.06251/) (2021)
- [A Convex Duality Framework for GANs](https://mlsanity.com/paper/1810.11740/) (2018)
- [Convex Regularization Behind Neural Reconstruction](https://mlsanity.com/paper/2012.05169/) (2020)

## Built on by (most cited first, 9 of 9)

- [Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks](https://mlsanity.com/paper/2110.09548/) (2021)
- [Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time](https://mlsanity.com/paper/2402.03625/) (2024)
- [Globally Optimal Training of Neural Networks with Threshold Activation Functions](https://mlsanity.com/paper/2303.03382/) (2023)
- [ReLU Neural Networks with Linear Layers are Biased Towards Single- and Multi-Index Models](https://mlsanity.com/paper/2305.15598/) (2023)
- [Analyzing Neural Network-Based Generative Diffusion Models through Convex Optimization](https://mlsanity.com/paper/2402.01965/) (2024)
- [Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes](https://mlsanity.com/paper/2311.10972/) (2023)
- [Fixing the NTK: From Neural Network Linearizations to Exact Convex Programs](https://mlsanity.com/paper/2309.15096/) (2023)
- [A Library of Mirrors: Deep Neural Nets in Low Dimensions are Convex Lasso Models with Reflection Features](https://mlsanity.com/paper/2403.01046/) (2024)
- [Unveiling Hidden Convexity in Deep Learning: a Sparse Signal Processing Perspective](https://mlsanity.com/paper/2603.23831/) (2026)

## Abstract (arXiv)

Training deep neural networks is a challenging non-convex optimization problem. Recent work has proven that the strong duality holds (which means zero duality gap) for regularized finite-width two-layer ReLU networks and consequently provided an equivalent convex training problem. However, extending this result to deeper networks remains to be an open problem. In this paper, we prove that the duality gap for deeper linear networks with vector outputs is non-zero. In contrast, we show that the zero duality gap can be obtained by stacking standard deep networks in parallel, which we call a parallel architecture, and modifying the regularization. Therefore, we prove the strong duality and existence of equivalent convex problems that enable globally optimal training of deep networks. As a by-product of our analysis, we demonstrate that the weight decay regularization on the network parameters explicitly encourages low-rank solutions via closed-form expressions. In addition, we show that strong duality holds for three-layer standard ReLU networks given rank-1 data matrices.