# Principled Deep Neural Network Training through Linear Programming

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2018.

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

- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [Parallel Successive Learning for Dynamic Distributed Model Training over Heterogeneous Wireless Networks](https://mlsanity.com/paper/2202.02947/) (2022)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Neural Spectrahedra and Semidefinite Lifts: Global Convex Optimization of Polynomial Activation Neural Networks in Fully Polynomial-Time](https://mlsanity.com/paper/2101.02429/) (2021)
- [Neural networks with linear threshold activations: structure and algorithms](https://mlsanity.com/paper/2111.08117/) (2021)
- [Multi-Edge Server-Assisted Dynamic Federated Learning with an Optimized Floating Aggregation Point](https://mlsanity.com/paper/2203.13950/) (2022)
- [Optimization Over Trained Neural Networks: Taking a Relaxing Walk](https://mlsanity.com/paper/2401.03451/) (2024)
- [The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Models](https://mlsanity.com/paper/2312.12657/) (2023)
- [Training Thinner and Deeper Neural Networks: Jumpstart Regularization](https://mlsanity.com/paper/2201.12795/) (2022)
- [Adaptive Target-Condition Neural Network: DNN-Aided Load Balancing for Hybrid LiFi and WiFi Networks](https://mlsanity.com/paper/2208.05035/) (2022)
- [Unveiling Hidden Convexity in Deep Learning: a Sparse Signal Processing Perspective](https://mlsanity.com/paper/2603.23831/) (2026)

## Abstract (arXiv)

Deep learning has received much attention lately due to the impressive empirical performance achieved by training algorithms. Consequently, a need for a better theoretical understanding of these problems has become more evident in recent years. In this work, using a unified framework, we show that there exists a polyhedron which encodes simultaneously all possible deep neural network training problems that can arise from a given architecture, activation functions, loss function, and sample-size. Notably, the size of the polyhedral representation depends only linearly on the sample-size, and a better dependency on several other network parameters is unlikely (assuming Pneq NP). Additionally, we use our polyhedral representation to obtain new and better computational complexity results for training problems of well-known neural network architectures. Our results provide a new perspective on training problems through the lens of polyhedral theory and reveal a strong structure arising from these problems.