Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
Investigating the statistical complexity of one-hidden-layer ReLU networks where only $k$ of $s$ total hidden units activate per input, this work establishes nearly tight Rademacher complexity and agnostic minimax excess-risk bounds. The authors eliminate prior explicit input-dimension factors to prove an empirical Rademacher bound of $\tilde{\mathcal{O}}(WR\min\{k, \sqrt{sk/m}\} + kB/\sqrt{m})$. Matching lower bounds reveal that dynamic, input-dependent activation inevitably incurs a $\sqrt{s}$ width penalty unless zero-bias constraints are enforced over full-ball geometries.
Even when an input activates only $k$ of $s$ hidden units, sample complexity cannot escape the total parameter count, incurring an inescapable $\tilde{\Theta}(\sqrt{sk/m})$ rate while eliminating all explicit dependencies on input dimension.
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.