论文标题
超出等级的鲁棒性定律
A Law of Robustness beyond Isoperimetry
论文作者
论文摘要
我们研究了在有界空间支持的任意数据分布的强大插值问题，并提出了鲁棒性的两倍。强大的插值是指通过Lipschitz函数在$ \ Mathbb {r}^d $中以$ n $ n $嘈杂的培训数据点的插值问题。尽管从等级分布中得出样品时，该问题已被充分理解，但对于在通用或最差的分布中的性能方面的性能仍然未知。我们证明了interpolating神经网络的Lipschitzness下限$ω（\ sqrt {n/p}）$，在任意数据分布上使用$ p $参数。通过此结果，我们验证了Bubeck，Li和Nagaraj在具有多项式权重的两层神经网络上的先前工作中的鲁棒性猜想定律。然后，我们将结果扩展到任意插值近似器，并证明Lipschitzness下限$ω（n^{1/d}）$用于可靠的插值。我们的结果证明了鲁棒性的两倍定律：i）当$ n = \ mathrm {poly}（d）（d）$和ii）中，我们表明了过度参数化的潜在益处，而ii）我们证明了当$ O（1）$ -Lipschitz强大的插入功能时，当$ n = \ n = \ exp（exp（d exp））$。
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 $Ω(\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 $Ω(n^{1/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=\mathrm{poly}(d)$, and ii) we disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=\exp(ω(d))$.
