Scaling the Convex Barrier with Sparse Dual Algorithms

arXiv:2101.05844v3 Announce Type: replace
Abstract: Tight and efficient neural network bounding is crucial to the scaling of neural network verification systems. Many efficient bounding algorithms have been presented recently, but they are often too loose to verify more challenging properties. This is due to the weakness of the employed relaxation, which is usually a linear program of size linear in the number of neurons. While a tighter linear relaxation for piecewise-linear activations exists, it comes at the cost of exponentially …

abstract algorithms arxiv cs.lg network neural network scaling systems type verification verify