# A Law of Robustness beyond Isoperimetry

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 40 references that are in the map.
- First posted on arXiv 23 Feb 2022.

## Builds on (most cited first, 20 of 20)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Pervasive Label Errors in Test Sets Destabilize Machine Learning Benchmarks](https://mlsanity.com/paper/2103.14749/) (2021)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [Certified Adversarial Robustness with Additive Noise](https://mlsanity.com/paper/1809.03113/) (2018)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Randomized Smoothing of All Shapes and Sizes](https://mlsanity.com/paper/2002.08118/) (2020)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [Convergence of Adversarial Training in Overparametrized Neural Networks](https://mlsanity.com/paper/1906.07916/) (2019)
- [Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness](https://mlsanity.com/paper/2002.03239/) (2020)
- [A law of robustness for two-layers neural networks](https://mlsanity.com/paper/2009.14444/) (2020)
- [Lower Bounds on Adversarial Robustness from Optimal Transport](https://mlsanity.com/paper/1909.12272/) (2019)
- [Provable tradeoffs in adversarially robust classification](https://mlsanity.com/paper/2006.05161/) (2020)
- [Random Smoothing Might be Unable to Certify ℓ_∞ Robustness for High-Dimensional Images](https://mlsanity.com/paper/2002.03517/) (2020)
- [Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification](https://mlsanity.com/paper/2006.16384/) (2020)
- [PAC-learning in the presence of evasion adversaries](https://mlsanity.com/paper/1806.01471/) (2018)

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

- [A Resilient and Accessible Distribution-Preserving Watermark for Large Language Models](https://mlsanity.com/paper/2310.07710/) (2023)
- [A Watermark for Order-Agnostic Language Models](https://mlsanity.com/paper/2410.13805/) (2024)
- [De-mark: Watermark Removal in Large Language Models](https://mlsanity.com/paper/2410.13808/) (2024)
- [Solving a Class of Non-Convex Minimax Optimization in Federated Learning](https://mlsanity.com/paper/2310.03613/) (2023)
- [Distortion-free Watermarks are not Truly Distortion-free under Watermark Key Collisions](https://mlsanity.com/paper/2406.02603/) (2024)
- [A direct proof of a unified law of robustness for Bregman divergence losses](https://mlsanity.com/paper/2405.16639/) (2024)
- [On damage of interpolation to adversarial robustness in regression](https://mlsanity.com/paper/2601.16070/) (2026)
- [Does Order Matter : Connecting The Law of Robustness to Robust Generalization](https://mlsanity.com/paper/2602.20971/) (2026)
- [A law of robustness for two-layer neural networks with arbitrary weights](https://mlsanity.com/paper/2607.07778/) (2026)

## Abstract (arXiv)

We study the robust interpolation problem of arbitrary data distributions supported on a bounded space and propose a two-fold law of robustness. Robust interpolation refers to the problem of interpolating n noisy training data points in ℝd by a Lipschitz function. Although this problem has been well understood when the samples are drawn from an isoperimetry distribution, much remains unknown concerning its performance under generic or even the worst-case distributions. We prove a Lipschitzness lower bound Omega(√n/p) of the interpolating neural network with p parameters on arbitrary data distributions. With this result, we validate the law of robustness conjecture in prior work by Bubeck, Li, and Nagaraj on two-layer neural networks with polynomial weights. We then extend our result to arbitrary interpolating approximators and prove a Lipschitzness lower bound Omega(n1/d) for robust interpolation. Our results demonstrate a two-fold law of robustness: i) we show the potential benefit of overparametrization for smooth data interpolation when n=poly(d), and ii) we disprove the potential existence of an O(1)-Lipschitz robust interpolating function when n=exp(ω(d)).