Title: Output Range Analysis for Deep Neural Networks,
Abstract: Deep neural networks (NN) are extensively used for machine learning tasks
such as image classification, perception and control of autonomous systems.
Increasingly, these deep NNs are also been deployed in high-assurance
applications. Thus, there is a pressing need for developing techniques to
verify neural networks to check whether certain user-expected properties are
satisfied. In this paper, we study a specific verification problem of computing
a guaranteed range for the output of a deep neural network given a set of
inputs represented as a convex polyhedron. Range estimation is a key primitive
for verifying deep NNs. We present an efficient range estimation algorithm that
uses a combination of local search and linear programming problems to
efficiently find the maximum and minimum values taken by the outputs of the NN
over the given input set. In contrast to recently proposed "monolithic"
optimization approaches, we use local gradient descent to repeatedly find and
eliminate local minima of the function. The final global optimum is certified
using a mixed integer programming instance. We implement our approach and
compare it with Reluplex, a recently proposed solver for deep neural networks.
We demonstrate the effectiveness of the proposed approach for verification of
NNs used in automated control as well as those used in classification.