Optimizing Objective Functions from Trained ReLU Neural Networks via Sampling
This work addresses the computational challenge of optimizing neural networks for researchers and practitioners in machine learning, offering incremental improvements to existing methods.
The paper tackles the problem of optimizing trained ReLU neural networks by developing scalable, sampling-based algorithms that reduce mixed-integer optimization problems into easier linear or smaller mixed-integer subproblems, showing convergence and sample complexity guarantees while validating performance against state-of-the-art methods and demonstrating effectiveness in warm-starting.
This paper introduces scalable, sampling-based algorithms that optimize trained neural networks with ReLU activations. We first propose an iterative algorithm that takes advantage of the piecewise linear structure of ReLU neural networks and reduces the initial mixed-integer optimization problem (MIP) into multiple easy-to-solve linear optimization problems (LPs) through sampling. Subsequently, we extend this approach by searching around the neighborhood of the LP solution computed at each iteration. This scheme allows us to devise a second, enhanced algorithm that reduces the initial MIP problem into smaller, easier-to-solve MIPs. We analytically show the convergence of the methods and we provide a sample complexity guarantee. We also validate the performance of our algorithms by comparing them against state-of-the-art MIP-based methods. Finally, we show computationally how the sampling algorithms can be used effectively to warm-start MIP-based methods.