When Deep Learning Meets Polyhedral Theory – A Survey (arxiv.org)

This survey maps the intersection of deep learning and polyhedral theory: because modern feedforward networks overwhelmingly use piecewise-linear activations like ReLU, their input–output behavior decomposes into a finite set of linear regions (polytopes). The paper organizes and synthesizes work that models these regions and network decisions with tools from linear optimization—primarily Linear Programming (LP) and Mixed-Integer Linear Programming (MILP)—to analyze expressivity (counts and shapes of linear regions), construct exact or bounded formulations of network outputs, and pose training, verification, and compression tasks as optimization problems. For the AI/ML community the significance is twofold. First, polyhedral methods give exact, interpretable characterizations and formal guarantees (e.g., provable adversarial attacks or certificates of robustness, exact neuron activation patterns), enabling rigorous verification and explainability beyond empirical testing. Second, they provide optimization-based strategies for training, pruning and model reduction (e.g., MILP-based compression or layer-wise formulations) and for deriving tight relaxations that trade off scalability and exactness. Key technical themes covered include counting/tight bounds on linear regions, big-M and cutting-plane MILP encodings, convex relaxations for certification, relaxation-tightening techniques, and practical scalability limits that motivate hybrid and approximate methods. The survey highlights both the power of polyhedral approaches for formal guarantees and the ongoing challenges of scaling them to very large networks and non-ReLU architectures.