Lipschitz Bounds and Provably Robust Training by Laplacian Smoothing

Abstract

In this work we propose a graph-based learning framework to train models with provable robustness to adversarial perturbations. In contrast to regularization-based approaches, we formulate the adversarially robust learning problem as one of loss minimization with a Lipschitz constraint, and show that the saddle point of the associated Lagrangian is characterized by a Poisson equation with weighted Laplace operator. Further, the weighting for the Laplace operator is given by the Lagrange multiplier for the Lipschitz constraint, which modulates the sensitivity of the minimizer to perturbations. We then design a provably robust training scheme using graph-based discretization of the input space and a primal-dual algorithm to converge to the Lagrangian's saddle point. Our analysis establishes a novel connection between elliptic operators with constraint-enforced weighting and adversarial learning. We also study the complementary problem of improving the robustness of minimizers with a margin on their loss, formulated as a loss-constrained minimization problem of the Lipschitz constant. We propose a technique to obtain robustified minimizers, and evaluate fundamental Lipschitz lower bounds by approaching Lipschitz constant minimization via a sequence of gradient $p$-norm minimization problems. Ultimately, our results show that, for a desired nominal performance, there exists a fundamental lower bound on the sensitivity to adversarial perturbations that depends only on the loss function and the data distribution, and that improvements in robustness beyond this bound can only be made at the expense of nominal performance. Our training schemes provably achieve these bounds both under constraints on performance and~robustness.

arXiv comment34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada

References in corpus (18)

• Ensemble Adversarial Training: Attacks and Defenses
• Provable defenses against adversarial examples via the convex outer adversarial polytope
• Certified Defenses against Adversarial Examples
• Efficient Neural Network Robustness Certification with General Activation Functions
• Robust Large Margin Deep Neural Networks
• Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach
• Training robust neural networks using Lipschitz bounds
• Robustness of classifiers: from adversarial to random noise
• Adversarial Robustness May Be at Odds With Simplicity
• A Modern Take on the Bias-Variance Tradeoff in Neural Networks
• Sorting out Lipschitz function approximation
• Model Compression with Adversarial Robustness: A Unified Optimization Framework
• Asymptotic behavior of ${\ell }_p$-based Laplacian regularization in semi-supervised learning
• Preventing Gradient Attenuation in Lipschitz Constrained Convolutional Networks
• Algorithms for Lipschitz Learning on Graphs
• Lipschitz regularized Deep Neural Networks generalize and are adversarially robust
• Lipschitz Properties for Deep Convolutional Networks
• Precise Tradeoffs in Adversarial Training for Linear Regression

Cited by in corpus (3)

• CLIP: Cheap Lipschitz Training of Neural Networks
• Improving the Robustness of Transformer-based Large Language Models with Dynamic Attention
• Gradient Shaping: Enhancing Backdoor Attack Against Reverse Engineering