Timezone: »

 
Poster
A Law of Robustness beyond Isoperimetry
Yihan Wu · Heng Huang · Hongyang Zhang

Thu Jul 27 04:30 PM -- 06:00 PM (PDT) @ Exhibit Hall 1 #331
in Poster Session 6 »
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 $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. 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(n^{1/d})$ for robust interpolation. Our results demonstrate a two-fold law of robustness: a) we show the potential benefit of overparametrization for smooth data interpolation when $n=poly(d)$, and b) we disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=\exp(\omega(d))$.
[ PDF]  [ Poster] 

Author Information

Yihan Wu (University of Maryland, College Park)
Heng Huang (University of Pittsburgh & JD Finance America Corporation)
Hongyang Zhang (University of Waterloo)

More from the Same Authors