Timezone: »

Overcoming the Convex Barrier for Simplex Inputs
Harkirat Singh Behl · M. Pawan Kumar · Philip Torr · Krishnamurthy Dvijotham

Tue Dec 07 08:30 AM -- 10:00 AM (PST) @
Recent progress in neural network verification has challenged the notion of a convex barrier, that is, an inherent weakness in the convex relaxation of the output of a neural network. Specifically, there now exists a tight relaxation for verifying the robustness of a neural network to $\ell_\infty$ input perturbations, as well as efficient 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, in this case, not only can one design a tight relaxation that overcomes the convex barrier, but the size of the relaxation remains linear in the number of neurons, thereby leading to simpler and more efficient algorithms. We establish the scalability of our overall approach via the specification of $\ell_1$ robustness for CIFAR-10 and MNIST classification, where our approach improves the state of the art verified accuracy by up to $14.4\%$. Furthermore, we establish its accuracy on a novel and highly challenging task of verifying the robustness of a multi-modal (text and image) classifier to arbitrary changes in its textual input.

Author Information

Harkirat Singh Behl (University of Oxford)

I am a DPhil student at the University of Oxford. I am a member of the Torr Vision Group and the Optimization for Vision and Learning group. My supervisors are Prof. Philip Torr and Prof. Pawan Kumar. I completed my undergraduate degree from Indian Institute of Technology (IIT) Kanpur in May 2018. I did a summer research internship in MSR Redmond in 2019 with Dr. Vibhav Vineet. My research interests lie in designing optimization algorithms for problems of practical interest in Computer Vision and Machine Learning.

M. Pawan Kumar (Ecole Centrale Paris)
Philip Torr (University of Oxford)
Krishnamurthy Dvijotham (DeepMind)

Krishnamurthy Dvijotham is a research scientist at Google Deepmind. Until recently, he was a research engineer at Pacific Northwest National Laboratory (PNNL) in the optimization and control group. He was previously a postdoctoral fellow at the Center for Mathematics of Information at Caltech. He received his PhD in computer science and engineering from the University of Washington, Seattle in 2014 and a bachelors from IIT Bombay in 2008. His research interests span stochastic control theory, artificial intelligence, machine learning and markets/economics, and his work is motivated primarily by problems arising in large-scale infrastructure systems like the power grid. His research has won awards at several conferences in optimization, AI and machine learning.

More from the Same Authors