Bounds on complexity of sparse neural networks with changing active units
Nearly Tight Rademacher Bounds for Sparsely Activated Neural Networks
Machine Learning
Summary
Neural networks often use only a few parts (hidden units) to respond to a single input, but different inputs may activate different parts. This paper studies how the complexity of such sparsely activated one-layer neural networks depends on how many parts are active and the overall network size. The authors provide mathematical bounds that explain how both the number of active units per input and the total network width affect the network's behavior. They also explore how the network's input range and bias values influence these complexity bounds. Their results help clarify the balance between sparsity and network size in understanding learning performance.
neural networksReLU activationsparsityRademacher complexitystatistical complexitysample sizeinput domainbias parametersminimax riskgeneralization bounds
Authors
Xiaoyu Li, Zhizhou Sha, Jiaojiao Jiang, Junbin Gao, Andi Han
Abstract
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.