  Neural networks (NNs) are now routinely implemented on systems that must
operate in uncertain environments, but the tools for formally analyzing how
this uncertainty propagates to NN outputs are not yet commonplace. Computing
tight bounds on NN output sets (given an input set) provides a measure of
confidence associated with the NN decisions and is essential to deploy NNs on
safety-critical systems. Recent works approximate the propagation of sets
through nonlinear activations or partition the uncertainty set to provide a
guaranteed outer bound on the set of possible NN outputs. However, the bound
looseness causes excessive conservatism and/or the computation is too slow for
online analysis. This paper unifies propagation and partition approaches to
provide a family of robustness analysis algorithms that give tighter bounds
than existing works for the same amount of computation time (or reduced
computational effort for a desired accuracy level). Moreover, we provide new
partitioning techniques that are aware of their current bound estimates and
desired boundary shape (e.g., lower bounds, weighted $\ell_\infty$-ball, convex
hull), leading to further improvements in the computation-tightness tradeoff.
The paper demonstrates the tighter bounds and reduced conservatism of the
proposed robustness analysis framework with examples from model-free RL and
forward kinematics learning.
