Partition-based formulations for mixed-integer optimization of trained ReLU neural networks

Abstract

This paper introduces a class of mixed-integer formulations for trained ReLU neural networks. The approach balances model size and tightness by partitioning node inputs into a number of groups and forming the convex hull over the partitions via disjunctive programming. At one extreme, one partition per input recovers the convex hull of a node, i.e., the tightest possible formulation for each node. For fewer partitions, we develop smaller relaxations that approximate the convex hull, and show that they outperform existing formulations. Specifically, we propose strategies for partitioning variables based on theoretical motivations and validate these strategies using extensive computational experiments. Furthermore, the proposed scheme complements known algorithmic approaches, e.g., optimization-based bound tightening captures dependencies within a partition.

arXiv commentConference on Neural Information Processing Systems (NeurIPS) 2021

References in corpus (10)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Provable defenses against adversarial examples via the convex outer adversarial polytope
• Evaluating Robustness of Neural Networks with Mixed Integer Programming
• An approach to reachability analysis for feed-forward ReLU neural networks
• Semidefinite relaxations for certifying robustness to adversarial examples
• ReLU Networks as Surrogate Models in Mixed-Integer Linear Programs
• A Unified View of Piecewise Linear Neural Network Verification
• The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification
• Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming
• Scaling the Convex Barrier with Sparse Dual Algorithms

Cited by in corpus (6)

• Maximizing information from chemical engineering data sets: Applications to machine learning
• Optimal training of integer-valued neural networks with mixed integer programming
• Local Repair of Neural Networks Using Optimization
• Lyapunov-stable neural-network control
• A Comparison of Strategies to Embed Physics-Informed Neural Networks in Nonlinear Model Predictive Control Formulations Solved via Direct Transcription
• Where the Action is: Let's make Reinforcement Learning for Stochastic Dynamic Vehicle Routing Problems work!