提出稀疏激活网络的紧致泛化界,揭示输入依赖稀疏性对复杂度的影响。
Nearly Tight Rademacher Bounds for Sparsely Activated Neural Networks
- 基于输入依赖稀疏性,设计新覆盖与链式论证方法
- 复杂度上界含 $k$ 和 $ ext{width } s$ 的耦合项,精度逼近理论极限
- 适用于研究稀疏神经网络泛化能力的理论工作者
在宽度为 $s$、每输入最多激活 $k$ 个隐单元、有效权重和偏置有界 $W,B$ 的单隐藏层 ReLU 模型中,对于固定半径 $R$ 输入域内的任意大小为 $m$ 的样本集,其 Rademacher 复杂度满足:$ mathcal{R}(S) leq CWR ext{min} { k, sqrt{sk/m} ext{log}^{3/2}(2m) } + kB/ sqrt{m}$。通过保持支撑的覆盖与归一化链式论证,消除了此前显式的维度因子(仅剩对数项)。在独立同分布边缘上构造下界,匹配上界至对数因子,揭示激活单元随输入变化仍保留宽度依赖。输入域至关重要:零偏置网络在整个球面上稀疏时,非零单元不超过 $2k$,复杂度为 $O(kWR/ sqrt{m})$;而当偏置与 $WR$ 同阶时,仅需对数维度即可恢复最坏情形率。球帽构造证明该结论,无需假设稀疏性仅在采样支撑上成立。对指定归一化有界损失及偏置与 $WR$ 可比的情形,还获得超失真率的近似最小最大界,阶为 $ ext{min} {1, sqrt{s/(km)} }$(对数内)。
原文摘要 · Abstract (English)
An input may activate few hidden units even when different inputs collectively use an entire network. We study the statistical complexity of this input-dependent sparsity in the one-hidden-layer ReLU model of Awasthi et al. (COLT 2024). For width $s$, at most $k$ active units per input, and effective weight and bias bounds $W,B$, every size-$m$ sample in the class's fixed radius-$R$ input domain satisfies $\mathcal{R}(S)\le CWR\min\{k,\sqrt{sk/m}\log^{3/2}(2m)\}+kB/\sqrt m$. A support-preserving cover and a single normalized chaining argument remove the previous explicit dimension factor, up to logarithms. Lower bounds on appropriate i.i.d. marginals match up to those logarithms, showing how changing active units across inputs retains a width dependence. The input domain matters: zero-bias networks sparse on the entire ball have at most $2k$ nonzero units and complexity $O(kWR/\sqrt m)$, whereas bias bounds comparable to $WR$ restore the worst-case rate on that same domain in only logarithmic dimension. A spherical-cap construction proves the latter claim without assuming sparsity merely on the sampling support. For a specified normalized bounded loss and biases comparable to $WR$, we also obtain agnostic minimax excess-risk bounds of order $\min\{1,\sqrt{s/(km)}\}$ up to logarithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。