Computational Tradeoffs of Optimization-Based Bound Tightening in ReLU Networks
The use of Mixed-Integer Linear Programming (MILP) models to represent neural networks with Rectified Linear Unit (ReLU) activations has become increasingly widespread in the last decade. This has enabled the use of MILP technology to test-or stress-their behavior, to adversarially improve their training, and to embed them in optimization models leveraging their predictive power. Many of these MILP models rely on activation bounds. That is, bounds on the input values of each neuron. In this work, we explore the tradeoff between the tightness of these bounds and the computational effort of solving the resulting MILP models. We provide guidelines for implementing these models based on the impact of network structure, regularization, and rounding.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
ReLU Networks as Surrogate Models in Mixed-Integer Linear Programs
We consider the embedding of piecewise-linear deep neural networks (ReLU networks) as surrogate models in mixed-integer linear programming (MILP) problems. A MILP formulation of ReLU networks has recently been applied by…
Verifying message-passing neural networks via topology-based bounds tightening
Since graph neural networks (GNNs) are often vulnerable to attack, we need to know when we can trust them. We develop a computationally effective approach towards providing robust certificates for message-passing neural …
Graph ClassificationAn analysis of optimization problems involving ReLU neural networks
Solving mixed-integer optimization problems with embedded neural networks with ReLU activation functions is challenging. Big-M coefficients that arise in relaxing binary decisions related to these functions grow exponent…
Partition-based formulations for mixed-integer optimization of trained ReLU neural networks
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…
Tightening Discretization-based MILP Models for the Pooling Problem using Upper Bounds on Bilinear Terms
Discretization-based methods have been proposed for solving nonconvex optimization problems with bilinear terms such as the pooling problem. These methods convert the original nonconvex optimization problems into mixed-i…
valid