# Practical Convex Formulation of Robust One-hidden-layer Neural Network Training

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 51 references that are in the map.
- First posted on arXiv 25 May 2021.

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

- [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)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (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)
- [End to End Learning for Self-Driving Cars](https://mlsanity.com/paper/1604.07316/) (2016)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [End-to-End Training of Deep Visuomotor Policies](https://mlsanity.com/paper/1504.00702/) (2015)
- [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)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [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)
- [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)
- [The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutions](https://mlsanity.com/paper/2006.05900/) (2020)
- [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)
- [A Sequential Framework Towards an Exact SDP Verification of Neural Networks](https://mlsanity.com/paper/2010.08603/) (2020)

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

- [Efficient Global Optimization of Two-Layer ReLU Networks: Quadratic-Time Algorithms and Adversarial Training](https://mlsanity.com/paper/2201.01965/) (2022)
- [Mixing Classifiers to Alleviate the Accuracy-Robustness Trade-Off](https://mlsanity.com/paper/2311.15165/) (2023)
- [Adversarial Training of Two-Layer Polynomial and ReLU Activation Networks via Convex Optimization](https://mlsanity.com/paper/2405.14033/) (2024)
- [Unveiling Hidden Convexity in Deep Learning: a Sparse Signal Processing Perspective](https://mlsanity.com/paper/2603.23831/) (2026)

## Abstract (arXiv)

Recent work has shown that the training of a one-hidden-layer, scalar-output fully-connected ReLU neural network can be reformulated as a finite-dimensional convex program. Unfortunately, the scale of such a convex program grows exponentially in data size. In this work, we prove that a stochastic procedure with a linear complexity well approximates the exact formulation. Moreover, we derive a convex optimization approach to efficiently solve the "adversarial training" problem, which trains neural networks that are robust to adversarial input perturbations. Our method can be applied to binary classification and regression, and provides an alternative to the current adversarial training methods, such as Fast Gradient Sign Method (FGSM) and Projected Gradient Descent (PGD). We demonstrate in experiments that the proposed method achieves a noticeably better adversarial robustness and performance than the existing methods.