Computational Tradeoffs of Optimization-Based Bound Tightening in ReLU Networks

2023/12/27 by Fabian Badilla, Marcos Goycoolea, Badilla, Fabian +5 · 1 voice · 1 citation
Computer Science · Mathematics · #Advanced Neural Network Applications #Adversarial Robustness in Machine Learning #Machine Learning and Algorithms #cs.LG #math.OC

paper · pdf · doi:10.48550/arxiv.2312.16699

arxiv published 2023/12/27 · arxiv updated 2024/01/30

Abstract

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.

Cited by

• Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogate

Discussions

• Is it worth running MILPs (vs. LPs) to calculate tighter activation bounds for big M formulations of neural networks? We look into that in "Computational Tradeoffs of Optimization-Based Bound Tighten [bsky, 3 points, 1 comments]

Related

• An analysis of optimization problems involving ReLU neural networks
• Partition-based formulations for mixed-integer optimization of trained ReLU neural networks
• Strong mixed-integer programming formulations for trained neural networks
• Activation-Descent Regularization for Input Optimization of ReLU Networks
• ReLU activated Multi-Layer Neural Networks trained with Mixed Integer Linear Programs