Robustness Analysis of Neural Networks via Efficient Partitioning with Applications in Control Systems

Neural networks (NNs) are now routinely implemented on systems that must\noperate in uncertain environments, but the tools for formally analyzing how\nthis uncertainty propagates to NN outputs are not yet commonplace. Computing\ntight bounds on NN output sets (given an input set) provides a measure of\nconfidence associated with the NN decisions and is essential to deploy NNs on\nsafety-critical systems. Recent works approximate the propagation of sets\nthrough nonlinear activations or partition the uncertainty set to provide a\nguaranteed outer bound on the set of possible NN outputs. However, the bound\nlooseness causes excessive conservatism and/or the computation is too slow for\nonline analysis. This paper unifies propagation and partition approaches to\nprovide a family of robustness analysis algorithms that give tighter bounds\nthan existing works for the same amount of computation time (or reduced\ncomputational effort for a desired accuracy level). Moreover, we provide new\npartitioning techniques that are aware of their current bound estimates and\ndesired boundary shape (e.g., lower bounds, weighted $\\ell_\\infty$-ball, convex\nhull), leading to further improvements in the computation-tightness tradeoff.\nThe paper demonstrates the tighter bounds and reduced conservatism of the\nproposed robustness analysis framework with examples from model-free RL and\nforward kinematics learning.\n