Reviews: On Robustness to Adversarial Examples and Polynomial Optimization

The paper studies the robustness of machine learning classifiers against adversarial examples. The authors use semi definite programming (SDP) in order to obtain provable polynomial-time adversarial attacks against hypothesis classes that are degree-1 and degree-2 polynomial threshold functions. Furthermore, the authors show that learning polynomial threshold functions of degree 2 or higher in a robust sense (against adversarial examples) is computationally a hard problem. The authors also experiment with 2-layer neural networks and with an SDP method they either find adversarial examples or certify that none exist within a certain budget delta available to the adversary. First of all, there are parts of the paper that are very well written and other parts that I assume were rushed for the NeurIPS submission deadline.