# Lipschitz Bounds and Provably Robust Training by Laplacian Smoothing

arXiv: https://arxiv.org/abs/2006.03712 · HTML: https://mlsanity.com/paper/2006.03712/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2020.

## Built on by (most cited first, 17 of 17)

- [CLIP: Cheap Lipschitz Training of Neural Networks](https://mlsanity.com/paper/2103.12531/) (2021)
- [Robust Implicit Networks via Non-Euclidean Contractions](https://mlsanity.com/paper/2106.03194/) (2021)
- [A Quantitative Geometric Approach to Neural-Network Smoothness](https://mlsanity.com/paper/2203.01212/) (2022)
- [Improving the Robustness of Transformer-based Large Language Models with Dynamic Attention](https://mlsanity.com/paper/2311.17400/) (2023)
- [Adversarial for Good? How the Adversarial ML Community's Values Impede Socially Beneficial Uses of Attacks](https://mlsanity.com/paper/2107.10302/) (2021)
- [Learning Globally Smooth Functions on Manifolds](https://mlsanity.com/paper/2210.00301/) (2022)
- [Gradient Shaping: Enhancing Backdoor Attack Against Reverse Engineering](https://mlsanity.com/paper/2301.12318/) (2023)
- [GeoRecon: Graph-Level Representation Learning for 3D Molecules via Reconstruction-Based Pretraining](https://mlsanity.com/paper/2506.13174/) (2025)
- [Failure Cases Are Better Learned But Boundary Says Sorry: Facilitating Smooth Perception Change for Accuracy-Robustness Trade-Off in Adversarial Training](https://mlsanity.com/paper/2508.02186/) (2025)
- [Defending against Adversarial Malware Attacks on ML-based Android Malware Detection Systems](https://mlsanity.com/paper/2501.13782/) (2025)
- [An Overview and Prospective Outlook on Robust Training and Certification of Machine Learning Models](https://mlsanity.com/paper/2208.07464/) (2022)
- [A Hybrid Approach for Smart Alert Generation](https://mlsanity.com/paper/2306.07983/) (2023)
- [Learning Lipschitz Feedback Policies from Expert Demonstrations: Closed-Loop Guarantees, Generalization and Robustness](https://mlsanity.com/paper/2103.16629/) (2021)
- [Robust Adversarial Classification via Abstaining](https://mlsanity.com/paper/2104.02334/) (2021)
- [Lipschitz-Regularized Critics Lead to Policy Robustness Against Transition Dynamics Uncertainty](https://mlsanity.com/paper/2404.13879/) (2024)
- [Enhance Hyperbolic Representation Learning via Second-order Pooling](https://mlsanity.com/paper/2410.22026/) (2024)
- [Beyond Coefficients: Forecast-Necessity Testing for Interpretable Causal Discovery in Nonlinear Time-Series Models](https://mlsanity.com/paper/2604.18751/) (2026)

## Abstract (arXiv)

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.