  This study uses CAPM (Convex Adversarial Polytope for Maxpool-based CNN) to
improve the verified bound for general purpose maxpool-based convolutional
neural networks (CNNs) under bounded norm adversarial perturbations. The
maxpool function is decomposed as a series of ReLU functions to extend the
convex relaxation technique to maxpool functions, by which the verified bound
can be efficiently computed through a dual network. The experimental results
demonstrate that this technique allows the state-of-the-art verification
precision for maxpool-based CNNs and involves a much lower computational cost
than current verification methods, such as DeepZ, DeepPoly and PRIMA. This
method is also applicable to large-scale CNNs, which previous studies show to
be often computationally prohibitively expensive. Under certain circumstances,
CAPM is 40-times, 20-times or twice as fast and give a significantly higher
verification bound (CAPM 98% vs. PRIMA 76%/DeepPoly 73%/DeepZ 8%) as compared
to PRIMA/DeepPoly/DeepZ. Furthermore, we additionally present the time
complexity of our algorithm as $O(W^2NK)$, where $W$ is the maximum width of
the neural network, $N$ is the number of neurons, and $K$ is the size of the
maxpool layer's kernel.
