text: 208,17,1100817646520418304,1092693586263457792,Greg Yang,"[1/4] Everybody knows adversarial examples are a problem, and a lot of people tried to provably verify NN robustness. But seems convex relaxation alone runs into a theoretical and empirical barrier --- not tight enough! See our new paper <LINK> <LINK> [2/4] This may be obvious to some, but at least 10 papers last year kept pushing convex relaxation, like @RICEric22 and @zicokolter’s LP method and recently @pushmeet’s January paper on interval bound propagation. [3/4] Algorithms that bypass this barrier include Raghunathan’s SDP formulations, MILP from Tedrake’s group, SMT (reluplex), Lipschitz constant bound, and hybrid approaches ← we encourage folks to explore these ideas further! [4/4] Collaboration with our super duper awesome AI resident @hadisalman94, along with Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang. Also special thanks to @ilyaraz2! @zicokolter Thanks Zico! You are right, and indeed we discuss this more carefully in the conclusion of the paper: ""In general, none of [the above] are strictly better than the convex relaxation approach, sacrificing either speed or accuracy"" --- so 100% on the same page here! @zicokolter Yep big fans of the randomized smoothing @deepcohen (very impressed by this) and Wasserstein robustness @RICEric22 papers! :)",http://arxiv.org/abs/1902.08722,"Verification of neural networks enables us to gauge their robustness against adversarial attacks. Verification algorithms fall into two categories: exact verifiers that run in exponential time and relaxed verifiers that are efficient but incomplete. In this paper, we unify all existing LP-relaxed verifiers, to the best of our knowledge, under a general convex relaxation framework. This framework works for neural networks with diverse architectures and nonlinearities and covers both primal and dual views of robustness verification. We further prove strong duality between the primal and dual problems under very mild conditions. Next, we perform large-scale experiments, amounting to more than 22 CPU-years, to obtain exact solution to the convex-relaxed problem that is optimal within our framework for ReLU networks. We find the exact solution does not significantly improve upon the gap between PGD and existing relaxed verifiers for various networks trained normally or robustly on MNIST and CIFAR datasets. Our results suggest there is an inherent barrier to tight verification for the large class of methods captured by our framework. We discuss possible causes of this barrier and potential future directions for bypassing it. Our code and trained models are available at this http URL . ","A Convex Relaxation Barrier to Tight Robustness Verification of Neural