26657d5ff9020d2abefe558796b99584-Paper.pdf

Specifically, there now exists a tight relaxation for verifying therobustness ofaneural networkto` input perturbations, aswell asefficient primal and dual solvers for the relaxation. Buoyed by this success, we consider the problem of developing similar techniques for verifying robustness to input perturbations within the probability simplex. We prove a somewhat surprising result that,inthiscase, notonlycanonedesign atightrelaxation thatovercomes the convexbarrier,butthe size ofthe relaxation remains linear inthe number of neurons, thereby leading tosimpler and more efficient algorithms.