证明了两层神经网络在任意权重下仍存在鲁棒性下界，揭示了过拟合的内在限制。
A law of robustness for two-layer neural networks with arbitrary weights
- 用函数空间覆盖替代参数空间覆盖，突破无界权重的分析瓶颈。
- 在高维球面或高斯数据上，拟合噪声标签时 Lipschitz 常数至少为 Ω(ε√(n/(m log(mnd/ε))))。
- 适用于 ReLU 等分段线性激活，且对冗余隐藏单元不敏感，适合研究泛化与过拟合的读者。
Bubeck、Li 与 Nagaraj 提出猜想：对于一般数据，任意两层神经网络若用 m 个神经元拟合 n 个带噪声标签，则其 Lipschitz 常数至少为 √(n/m) 阶，且对权重大小无限制。此前研究仅在参数有界时成立。本文针对任意实数权重、偏置及仿射跳跃连接的两层网络，在数据均匀分布在 𝕊^{d−1}（d≥3）或服从 N(0, I_d/d) 时，证明该猜想成立，仅差一个对数因子。当标签在 [−1,1] 内、噪声方差 σ² > 0，且网络拟合误差 ε 低于噪声水平时，以高概率有 Lip(f) ≥ c ε√(n/(¯m log(C¯m nd/ε)))，其中 ¯m = (K−1)m+1。进一步，对于实际产生的分段线性函数，若其不同拐点超平面数 k(f) ≤ n，该下界仍成立，且与冗余隐藏单元无关。证明核心是函数空间覆盖与一个刚性引理：在 d≥3 时，每个标准拐点系数受函数 Lipschitz 常数控制，因不同超平面上的拐点无法在一般点相消。该刚性在 d=2 时失效，且存在宽度 2n 的 ReLU 网络在过参数化极限下达到该下界。
原文摘要 · Abstract (English)
Bubeck, Li and Nagaraj conjectured that, for generic data, any two-layer neural network with $m$ neurons that fits $n$ noisy labels must have Lipschitz constant at least of order $\sqrt{n/m}$, with no restriction on the size of the weights. Bubeck and Sellke proved a universal version of this law for Lipschitz-parameterized classes, but under a polynomial bound on the parameters; at depth three that boundedness hypothesis is genuinely necessary. The two-layer unbounded-weight case requires a different argument. We prove the conjectured law, up to one logarithmic factor, for every continuous piecewise-linear activation, in particular for ReLU networks. For data drawn uniformly from $\mathbb{S}^{d-1}$, $d\ge3$, or from $N(0,I_d/d)$, labels in $[-1,1]$ with noise level $σ^2>0$, and any width-$m$ two-layer network with arbitrary real weights, biases and affine skip connection, fitting the data $\varepsilon$ below the noise floor forces $\mathrm{Lip}(f)\ge c\,\varepsilon\sqrt{n/(\bar m\log(C\bar m nd/\varepsilon))}$, $\bar m=(K-1)m+1$, with high probability. A realized-kink-count version holds on the same event: every realized two-layer piecewise-linear function with $k(f)\le n$ distinct kink hyperplanes obeys the bound with $\bar m$ replaced by $k(f)+1$, irrespective of how many redundant hidden units parameterize it. The proof replaces parameter-space covering, impossible for unbounded weights, by a function-space covering. The central deterministic ingredient is a rigidity lemma: on $B_2$, and on $\mathbb{S}^{d-1}$ for $d\ge3$, the coefficient of each canonical kink is controlled by the Lipschitz constant of the realized function, because kinks on distinct hyperplanes cannot cancel at generic points. Rigidity genuinely fails at $d=2$, and an explicit two-layer ReLU interpolant with $O(1)$ Lipschitz constant at width $2n$ matches the law at the overparameterized endpoint.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。