mlsanityData to 14 Oct 2026

Parallel Deep Neural Networks Have Zero Duality Gap

arXiv 2110.06482 ↗First posted 13 Oct 2021cs.LG math.OCcited by 9

Not on the map. Why?

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.

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

32 of 52 references.

References · 32

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2016Wide Residual Networkscited by 3,070
  3. 2016Aggregated Residual Transformations for Deep Neural Networkscited by 2,546
  4. 2021Convex optimizationcited by 2,515
  5. 2016Xception: Deep Learning with Depthwise Separable Convolutionscited by 2,332
  6. 2016Identity Mappings in Deep Residual Networkscited by 1,965
  7. 2016Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learningcited by 1,512
  8. 2016SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and <0.5MB model sizecited by 1,060
  9. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 466
  10. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 426
  11. 2019Implicit Regularization in Deep Matrix Factorizationcited by 405
  12. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 331
20 more
  1. 2019Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limitcited by 187
  2. 2018Gradient descent aligns the layers of deep linear networkscited by 182
  3. 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 151
  4. 2018Mean Field Analysis of Neural Networks: A Central Limit Theoremcited by 107
  5. 2020Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networkscited by 98
  6. 2020Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracycited by 71
  7. 2020Revealing the Structure of Deep Neural Networks via Convex Dualitycited by 54
  8. 2017Stochastic Particle Gradient Descent for Infinite Ensemblescited by 52
  9. 2019Sparse Optimization on Measures with Over-parameterized Gradient Descentcited by 50
  10. 2020Convex Geometry and Duality of Over-parameterized Neural Networkscited by 49
  11. 2020Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithmscited by 34
  12. 2021Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programscited by 25
  13. 2019Global convergence of neuron birth-death dynamicscited by 22
  14. 2020Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysiscited by 21
  15. 2021Demystifying Batch Normalization in ReLU Networks: Equivalent Convex Optimization Models and Implicit Regularizationcited by 21
  16. 2021On Learnability via Gradient Method for Two-Layer ReLU Neural Networks in Teacher-Student Settingcited by 16
  17. 2018A Convex Duality Framework for GANscited by 15
  18. 2020Convex Regularization Behind Neural Reconstructioncited by 15
  19. 2021Neural Spectrahedra and Semidefinite Lifts: Global Convex Optimization of Polynomial Activation Neural Networks in Fully Polynomial-Timecited by 14
  20. 2021Hidden Convexity of Wasserstein GANs: Interpretable Generative Models with Closed-Form Solutionscited by 14

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 0; 2023: 4; 2024: 3; 2025: 0; 2026: 1.

9 papers.

  1. 2021Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networkscited by 14
  2. 2024Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Timecited by 11
  3. 2023Globally Optimal Training of Neural Networks with Threshold Activation Functionscited by 9
  4. 2023ReLU Neural Networks with Linear Layers are Biased Towards Single- and Multi-Index Modelscited by 8
  5. 2024Analyzing Neural Network-Based Generative Diffusion Models through Convex Optimizationcited by 7
  6. 2023Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopescited by 2
  7. 2023Fixing the NTK: From Neural Network Linearizations to Exact Convex Programscited by 1
  8. 2024A Library of Mirrors: Deep Neural Nets in Low Dimensions are Convex Lasso Models with Reflection Featurescited by 1
  9. 2026Unveiling Hidden Convexity in Deep Learning: a Sparse Signal Processing Perspectivecited by 1