When Deep Learning Meets Polyhedral Theory: A Survey

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—such as the typical fully connected feedforward neural network—amenable to analysis through polyhedral theory and to the application of methodologies such as linear programming and mixed-integer linear programming for a variety of purposes. In this paper, we survey the main topics emerging from this fast-paced area of work, which brings 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. History: Accepted by Andrea Lodi, Area Editor of Design and Analysis of Algorithms—Discrete. Funding: T. Serra was supported by the National Science Foundation (NSF) Division of Information and Intelligent Systems [Grant IIS 2104583], C. Tsay was supported by the Engineering and Physical Sciences Research Council (EPSRC) [Grant EP/T001577/1]. G. Muñoz was supported by the Chilean Research and Development Agency (ANID) [Grant PIA/PUENTE AFB230002].