mlsanityData to 7 Oct 2026

When Deep Learning Meets Polyhedral Theory: A Survey

arXiv 2305.00241 ↗First posted 29 Apr 2023math.OC cs.LGcited by 39

Not on the map. Why?

Abstract (arXiv)

In the past decade, deep learning became the prevalent methodology for predictive modeling thanks to the remarkable accuracy of deep neural networks in tasks such as computer vision and natural language processing. Meanwhile, the structure of neural networks converged back to simpler representations based on piecewise constant and piecewise linear functions such as the Rectified Linear Unit (ReLU), which became the most commonly used type of activation function in neural networks. That made certain types of network structure unicodex2014such as the typical fully-connected feedforward neural networkunicodex2014 amenable to analysis through polyhedral theory and to the application of methodologies such as Linear Programming (LP) and Mixed-Integer Linear Programming (MILP) for a variety of purposes. In this paper, we survey the main topics emerging from this fast-paced area of work, which bring a fresh perspective to understanding neural networks in more detail as well as to applying linear optimization techniques to train, verify, and reduce the size of such networks.

Key facts. Cited by 39 papers in the map (data through 7 Oct 2026). Builds on 209 of its 363 references that are in the map. First posted on arXiv 29 Apr 2023.

Builds on

209 of 363 references.

References · 209

  1. 2017Attention Is All You Needcited by 59,932
  2. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  3. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  4. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  5. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  6. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
  7. 2022Hierarchical Text-Conditional Image Generation with CLIP Latentscited by 6,539
  8. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  9. 2013Intriguing properties of neural networkscited by 5,114
  10. 2018MobileNetV2: Inverted Residuals and Linear Bottleneckscited by 4,773
  11. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,530
  12. 2014Going Deeper with Convolutionscited by 4,231
38 more
  1. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,590
  2. 2015Continuous control with deep reinforcement learningcited by 3,279
  3. 2014Sequence to Sequence Learning with Neural Networkscited by 2,974
  4. 2018Deep contextualized word representationscited by 2,285
  5. 2019SpecAugment: A Simple Data Augmentation Method for Automatic Speech Recognitioncited by 1,355
  6. 2019Self-training with Noisy Student improves ImageNet classificationcited by 1,304
  7. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  8. 2014Deep Learning in Neural Networks: An Overviewcited by 765
  9. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 739
  10. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  11. 2015BinaryConnect: Training Deep Neural Networks with binary weights during propagationscited by 571
  12. 2014Convex Optimization: Algorithms and Complexitycited by 569
  13. 2016Error bounds for approximations with deep ReLU networkscited by 567
  14. 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 564
  15. 2020VectorNet: Encoding HD Maps and Agent Dynamics from Vectorized Representationcited by 528
  16. 2018Efficient Neural Network Robustness Certification with General Activation Functionscited by 439
  17. 2018Lipschitz regularity of deep neural networks: analysis and efficient estimationcited by 413
  18. 2014On the Number of Linear Regions of Deep Neural Networkscited by 378
  19. 2018On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Modelscited by 322
  20. 2017The Expressive Power of Neural Networks: A View from the Widthcited by 318
  21. 2016On the Expressive Power of Deep Neural Networkscited by 302
  22. 2019Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networkscited by 290
  23. 2018Towards Fast Computation of Certified Robustness for ReLU Networkscited by 254
  24. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
  25. 2017Formal Verification of Piece-Wise Linear Feed-Forward Neural Networkscited by 241
  26. 2019Algorithms for Verifying Deep Neural Networkscited by 221
  27. 2018Sorting out Lipschitz function approximationcited by 211
  28. 2019Towards Stable and Efficient Training of Verifiably Robust Neural Networkscited by 204
  29. 2018Sensitivity and Generalization in Neural Networks: an Empirical Studycited by 187
  30. 2013Maxout Networkscited by 186
  31. 2018Formal Security Analysis of Neural Networks using Symbolic Intervalscited by 185
  32. 2018Semidefinite relaxations for certifying robustness to adversarial examplescited by 178
  33. 2021Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspectivecited by 168
  34. 2019Complexity of Linear Regions in Deep Networkscited by 166
  35. 2018Efficient Formal Safety Analysis of Neural Networkscited by 165
  36. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
  37. 2019Deep ReLU Networks Have Surprisingly Few Activation Patternscited by 160
  38. 2021Activation Functions in Deep Learning: A Comprehensive Survey and Benchmarkcited by 153

50 most cited of 209 All 209 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 5; 2024: 14; 2025: 11; 2026: 9.

39 papers.

Sort:

By area:

  1. 2024Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planescited by 33
  2. 2024The Real Tropical Geometry of Neural Networkscited by 23
  3. 2024Certified Robustness to Data Poisoning in Gradient-Based Trainingcited by 17
  4. 2025Depth-Bounds for Neural Networks via the Braid Arrangementcited by 11
  5. 2025Better Neural Network Expressivity: Subdividing the Simplexcited by 11
  6. 2024Optimization Over Trained Neural Networks: Taking a Relaxing Walkcited by 10
  7. 2023Topological Expressivity of ReLU Neural Networkscited by 9
  8. 2023PySCIPOpt-ML: Embedding Trained Machine Learning Models into Mixed-Integer Programscited by 8
  9. 2024Neural Networks and (Virtual) Extended Formulationscited by 8
  10. 2025The Computational Complexity of Counting Linear Regions in ReLU Neural Networkscited by 7
  11. 2023Computational Tradeoffs of Optimization-Based Bound Tightening in ReLU Networkscited by 6
  12. 2024Generating Likely Counterfactuals Using Sum-Product Networkscited by 6
27 more
  1. 2024Certification for Differentially Private Prediction in Gradient-Based Trainingcited by 6
  2. 2025Reinforcement learning with combinatorial actions for coupled restless banditscited by 5
  3. 2026Most ReLU Networks Admit Identifiable Parameterscited by 5
  4. 2025Time to Spike? Understanding the Representational Power of Spiking Neural Networks in Discrete Timecited by 4
  5. 2026Exact Certification of Data-Poisoning Attacks Using Mixed-Integer Programmingcited by 3
  6. 2023Deep Learning for Two-Stage Robust Integer Optimizationcited by 2
  7. 2024Defining Neural Network Architecture through Polytope Structures of Datasetcited by 2
  8. 2024Expressiveness of Multi-Neuron Convex Relaxations in Neural Network Certificationcited by 2
  9. 2025Relating Piecewise Linear Kolmogorov Arnold Networks to ReLU Networkscited by 2
  10. 2025Global optimization of graph acquisition functions for neural architecture searchcited by 2
  11. 2024A rank decomposition for the topological classification of neural representationscited by 1
  12. 2024A Computational Tropical Geometry Framework for Neural Networkscited by 1
  13. 2025Arithmetic Circuits and Neural Networks for Regular Matroidscited by 1
  14. 2026Relaxation-Informed Training of Neural Network Surrogate Modelscited by 1
  15. 2023Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithmscited by 0
  16. 2024Parallel Algorithms for Exact Enumeration of Deep Neural Network Activation Regionscited by 0
  17. 2024Implicit Hypersurface Approximation Capacity in Deep ReLU Networkscited by 0
  18. 2024Tightening convex relaxations of trained neural networks: a unified approach for convex and S-shaped activationscited by 0
  19. 2025Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogatecited by 0
  20. 2025Conformal Mixed-Integer Constraint Learning with Feasibility Guaranteescited by 0
  21. 2025Maxout Polytopescited by 0
  22. 2026An Efficient Spatial Branch-and-Bound Algorithm for Global Optimization of Gaussian Process Posterior Mean Functionscited by 0
  23. 2026Lipschitz Optimization for Formal Verification of Homographiescited by 0
  24. 2026Hybrid Robustness Verification for Spatio-Temporal Neural Networkscited by 0
  25. 2026Tropical Circuits with Scalar Multiplication Gatescited by 0
  26. 2026Input convex neural networks as surrogates in mathematical optimisationcited by 0
  27. 2026Affine Geometry of Gaussian ReLU Networks via Conditional Kac-Rice Formulascited by 0