Training neural networks to be certifiably robust is critical to ensure their safety against adversarial attacks. However, while promising, state-of-the-art results with certified training are far from satisfactory. Currently, it is very difficult to train a neural network that is both accurate and certifiably robust. In this work we take a step towards addressing this challenge. We prove that for every continuous function f , there exists a network n such that: (i) n approximates f arbitrarily close, and (ii) simple interval bound propagation of a region B through n yields a result that is arbitrarily close to the optimal output of f on B. Our result can be seen as a Universal Approximation Theorem for interval-certified ReLU networks. To the best of our knowledge, this is the first work to prove the existence of accurate, interval-certified networks.
The paper aims to show that there exist neural networks that can be certified by interval bound propagation. It claims to do this by showing that for any function f, there is a neural network g (close to f) such that interval bound propagation on g obtains bounds that are almost as good as one would get by applying interval bound propagation to f.
There are a couple issues with this paper. The first is that the main theorem does not imply the claimed high-level take-away in the paper in any practically relevant regime. This is because while the paper does show that there is a network that approximates f well enough, the size of the network in the construction is exponential (for instance, one of the neural network components in the construction involves summing over all hyperrectangles lying within a grid). The result is only plausibly practically relevant if there is a polynomially-sized network for which the bound propagation works.
The second issue is the comparison to related work, which omits both several key techniques in the literature and two related papers on universal approximation.
On universal approximation papers, see these two: https://arxiv.org/abs/1904.04861 and https://arxiv.org/abs/1811.05381. They consider a different proof strategy but more plausibly yield networks of reasonable size.
On key techniques in the literature: "typically by employing methods based on mixed integerlinear programming, SMT solvers and bound propagation" ignores several major techniques in the field: convex relaxations (SDP + LP), and randomized smoothing. Similarly, "specific training methods have beenrecently developed which aim to produce networks that are certifiably robust" again ignores entire families of techniques; Raghunathan et al. train SDP relaxations to perform well, while Cohen et al. train randomized smoothing to work well. Importantly, randomized smoothing is not about creating an over-approximation of the network but explicitly constructs networks that are smooth.
"some of the best results achieved on the popular MNIST (LeCun et al., 1998) and CIFAR10(Krizhevsky, 2009) datasets have been obtained with the simple Interval approximation (Gowalet al., 2018; Mirman et al., 2019)"
-Is this actually true? I just looked at Mirman et al. and it doesn't seem to explicitly compare to any existing bounds. My impression is that randomized smoothing (Cohen et al.) currently gets the best numbers, if we're allowed to train the network. If not allowed to train the network, Raghunathan et al. (Neurips 2018) performs well and is not compared to in the Mirman paper.
These omissions must be addressed as the introduction and related work is misleading in its current state.
Finally, some writing issues:
>>> While the evidence suggests "no", we prove that for realisticdatasets and specifications, such a network does exist and its certification can beestablished by propagating lower and upper bounds of each neuron through thenetwork
One cannot "prove" something for "realistic datasets", since "realistic datasets" is not a formal assumption. Please fix this.
>>> "the most relaxed yet computationally efficient convex relaxation"
What does most relaxed mean? Most relaxed would most straightforwardly mean outputting the entire space as the set of possibilities at each point, which is clearly not intended.