# Efficient Global Optimization of Two-Layer ReLU Networks: Quadratic-Time Algorithms and Adversarial Training

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 54 references that are in the map.
- First posted on arXiv 6 Jan 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [DeepFool: a simple and accurate method to fool deep neural networks](https://mlsanity.com/paper/1511.04599/) (2015)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Adversarial Attacks on Neural Network Policies](https://mlsanity.com/paper/1702.02284/) (2017)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Greedy Layerwise Learning Can Scale to ImageNet](https://mlsanity.com/paper/1812.11446/) (2018)
- [Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks](https://mlsanity.com/paper/2002.10553/) (2020)
- [Learning with a Strong Adversary](https://mlsanity.com/paper/1511.03034/) (2015)
- [Training Neural Networks Without Gradients: A Scalable ADMM Approach](https://mlsanity.com/paper/1605.02026/) (2016)
- [Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs](https://mlsanity.com/paper/1702.07966/) (2017)
- [Random Smoothing Might be Unable to Certify ℓ_∞ Robustness for High-Dimensional Images](https://mlsanity.com/paper/2002.03517/) (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)
- [On the Complexity Analysis of Randomized Block-Coordinate Descent Methods](https://mlsanity.com/paper/1305.4723/) (2013)
- [ADMM for Efficient Deep Learning with Global Convergence](https://mlsanity.com/paper/1905.13611/) (2019)
- [Tightened Convex Relaxations for Neural Network Robustness Certification](https://mlsanity.com/paper/2004.00570/) (2020)
- [Data-Driven Certification of Neural Networks with Random Input Noise](https://mlsanity.com/paper/2010.01171/) (2020)
- [Practical Convex Formulation of Robust One-hidden-layer Neural Network Training](https://mlsanity.com/paper/2105.12237/) (2021)

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

- [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)
- [Improving the Accuracy-Robustness Trade-Off of Classifiers via Adaptive Smoothing](https://mlsanity.com/paper/2301.12554/) (2023)
- [MixedNUTS: Training-Free Accuracy-Robustness Balance via Nonlinearly Mixed Classifiers](https://mlsanity.com/paper/2402.02263/) (2024)
- [Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time](https://mlsanity.com/paper/2402.03625/) (2024)
- [CRONOS: Enhancing Deep Learning with Scalable GPU Accelerated Convex Neural Networks](https://mlsanity.com/paper/2411.01088/) (2024)
- [AdAUC: End-to-end Adversarial AUC Optimization Against Long-tail Problems](https://mlsanity.com/paper/2206.12169/) (2022)
- [Mixing Classifiers to Alleviate the Accuracy-Robustness Trade-Off](https://mlsanity.com/paper/2311.15165/) (2023)
- [Generative Feature Training of Thin 2-Layer Networks](https://mlsanity.com/paper/2411.06848/) (2024)
- [An Overview and Prospective Outlook on Robust Training and Certification of Machine Learning Models](https://mlsanity.com/paper/2208.07464/) (2022)
- [Can overfitted deep neural networks in adversarial training generalize? -- An approximation viewpoint](https://mlsanity.com/paper/2401.13624/) (2024)
- [Stability of Primal-Dual Gradient Flow Dynamics for Multi-Block Convex Optimization Problems](https://mlsanity.com/paper/2408.15969/) (2024)
- [Deep-ICE: the first globally optimal algorithm for minimizing 0-1 loss in two-layer ReLU and maxout networks](https://mlsanity.com/paper/2505.05740/) (2025)
- [Convex Optimization for Alignment and Preference Learning on a Single GPU](https://mlsanity.com/paper/2605.23244/) (2026)
- [Convex training of Lipschitz-regularized shallow neural networks](https://mlsanity.com/paper/2606.19652/) (2026)

## Abstract (arXiv)

The non-convexity of the artificial neural network (ANN) training landscape brings inherent optimization difficulties. While the traditional back-propagation stochastic gradient descent (SGD) algorithm and its variants are effective in certain cases, they can become stuck at spurious local minima and are sensitive to initializations and hyperparameters. Recent work has shown that the training of an ANN with ReLU activations can be reformulated as a convex program, bringing hope to globally optimizing interpretable ANNs. However, naively solving the convex training formulation has an exponential complexity, and even an approximation heuristic requires cubic time. In this work, we characterize the quality of this approximation and develop two efficient algorithms that train ANNs with global convergence guarantees. The first algorithm is based on the alternating direction method of multiplier (ADMM). It solves both the exact convex formulation and the approximate counterpart. Linear global convergence is achieved, and the initial several iterations often yield a solution with high prediction accuracy. When solving the approximate formulation, the per-iteration time complexity is quadratic. The second algorithm, based on the "sampled convex programs" theory, solves unconstrained convex formulations and converges to an approximately globally optimal classifier. The non-convexity of the ANN training landscape exacerbates when adversarial training is considered. We apply the robust convex optimization theory to convex training and develop convex formulations that train ANNs robust to adversarial inputs. Our analysis explicitly focuses on one-hidden-layer fully connected ANNs, but can extend to more sophisticated architectures.