A Law of Robustness beyond Isoperimetry
Authors: Yihan Wu, Heng Huang, Hongyang Zhang
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove a Lipschitzness lower bound Ω( p 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 Ω(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)). |
| Researcher Affiliation | Academia | 1Department of Computer Science, University of Maryland at College Park 2School of Computer Science, University of Waterloo. Correspondence to: Yihan Wu <ywu42@umd.edu>, Heng Huang <heng@umd.edu>, Hongyang Zhang <hongyang.zhang@uwaterloo.ca>. |
| Pseudocode | No | The paper contains mathematical proofs and theoretical derivations but no explicitly labeled pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not contain any statements or links indicating that source code for the described methodology is publicly available. |
| Open Datasets | No | The paper discusses theoretical aspects of robust interpolation with 'noisy training data' and mentions 'CIFAR10' and 'Image Net' as examples of real-world datasets in a discussion of empirical observations by others, but does not specify any particular public or open dataset used for its own research. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments, therefore no dataset split information for validation is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments, therefore no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, therefore no specific experimental setup details like hyperparameters or training configurations are provided. |