  There has been a rapid development and interest in adversarial training and
defenses in the machine learning community in the recent years. One line of
research focuses on improving the performance and efficiency of adversarial
robustness certificates for neural networks \cite{gowal:19, wong_zico:18,
raghunathan:18, WengTowardsFC:18, wong:scalable:18, singh:convex_barrier:19,
Huang_etal:19, single-neuron-relax:20, Zhang2020TowardsSA}. While each
providing a certification to lower (or upper) bound the true distortion under
adversarial attacks via relaxation, less studied was the tightness of
relaxation. In this paper, we analyze a family of linear outer approximation
based certificate methods via a meta algorithm, IBP-Lin. The aforementioned
works often lack quantitative analysis to answer questions such as how does the
performance of the certificate method depend on the network configuration and
the choice of approximation parameters. Under our framework, we make a first
attempt at answering these questions, which reveals that the tightness of
linear approximation based certification can depend heavily on the
configuration of the trained networks.
