Optimization Over Trained Neural Networks: Taking a Relaxing Walk
This work addresses scalability issues in optimization over neural networks for applications like verification and compression, representing an incremental improvement over existing methods.
The paper tackles the challenge of solving optimization problems over trained neural networks, which becomes difficult as network size increases, by proposing a scalable heuristic based on exploring global and local linear relaxations. The result is a method that is competitive with state-of-the-art MILP solvers and prior heuristics, producing better solutions with increases in input size, depth, and neuron count.
Besides training, mathematical optimization is also used in deep learning to model and solve formulations over trained neural networks for purposes such as verification, compression, and optimization with learned constraints. However, solving these formulations soon becomes difficult as the network size grows due to the weak linear relaxation and dense constraint matrix. We have seen improvements in recent years with cutting plane algorithms, reformulations, and an heuristic based on Mixed-Integer Linear Programming (MILP). In this work, we propose a more scalable heuristic based on exploring global and local linear relaxations of the neural network model. Our heuristic is competitive with a state-of-the-art MILP solver and the prior heuristic while producing better solutions with increases in input, depth, and number of neurons.