A Law of Robustness beyond Isoperimetry

Understand

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 $\mathbb{R}^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(\sqrt{n/p})$ of the interpolating neural network with $p$ parameters on arbitrary data distributions.