Principled deep neural network training through linear programming

DOI10.1016/J.DISOPT.2023.100795MaRDI QIDQ6054389zbMATH OpenOpenAlexFDO

Authors Daniel Bienstock, Gonzalo Muñoz, Sebastian Pokutta

Publication date 28 September 2023

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.03218

zbMATH Keywords

deep learninglinear programmingpolyhedral theory

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Artificial neural networks and deep learning (68T07) Integer programming (90C10) Nonlinear programming (90C30)

Abstract: 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 $PeqNP$). 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.

Recommendations

• scientific article; zbMATH DE number 724205
• Deep neural networks and mixed integer linear optimization
• scientific article; zbMATH DE number 1150492
• A neural network representation of linear programming
• Maximum principle based algorithms for deep learning
• Recurrent neural networks for linear programming: Analysis and design principles
• Deep Neural Networks for Solving Large Linear Systems Arising from High-Dimensional Problems
• Lagrange programming neural networks
• Linear Neural Network Training Algorithms For Real-World Benchmark Problems
• scientific article; zbMATH DE number 1054676

Cites work

• A survey of safety and trustworthiness of deep neural networks: verification, testing, adversarial attack and defence, and interpretability
• Approximation Algorithms for Training One-Node ReLU Neural Networks
• Complexity of training ReLU neural network
• Deep learning
• Extension complexity, MSO logic, and treewidth
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 7626727 (Why is no real title available?)
• scientific article; zbMATH DE number 7246283 (Why is no real title available?)
• Lossless compression of deep neural networks
• LP formulations for polynomial optimization problems
• Neural networks with linear threshold activations: structure and algorithms
• Optimization methods for large-scale machine learning
• Regularisation of neural networks by enforcing Lipschitz continuity
• The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
• The Pathwidth and Treewidth of Cographs
• Treewidth. Computations and approximations
• Understanding machine learning. From theory to algorithms

Cited in

(6)

• Deep neural networks and mixed integer linear optimization
• A game-theoretic perspective of deep neural networks
• A game-theoretic analysis of deep neural networks
• The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
• Multicomposite nonconvex optimization for training deep neural networks
• Optimization of sparsity-constrained neural networks as a mixed integer linear program

This page was built for publication: Principled deep neural network training through linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6054389)