PaperlayerView exact revision on arXiv

Source-linked AI summary

Nearly Tight Rademacher Bounds for Sparsely Activated Neural Networks

Xiaoyu Li, Zhizhou Sha, Jiaojiao Jiang, Junbin Gao, Andi Han

arXiv:2609.09130v1cs.LGstat.ML

TL;DR

The question is whether input-dependent sparsity controls network capacity uniformly over admissible activation patterns, rather than merely limiting contributions on each input. For the thresholded lower bound, random-sign packing supplies directions in 𝑂(log(2𝑞)) dimensions; when 𝐵≥𝜏𝐴, each cap center has output amplitude (1 −𝜏)𝑘𝐴 (Theorem 12). The upper bound is dimension-free up to logarithmic factors, while full-ball zero-bias sparsity collapses to at most 2k units and comparable positive thresholds restore width dependence.

  • Problem

    The question is whether input-dependent sparsity controls network capacity uniformly over admissible activation patterns, rather than merely limiting contributions on each input.

    Source: §1 · p. 1

  • Method

    For the thresholded lower bound, random-sign packing supplies directions in 𝑂(log(2𝑞)) dimensions; when 𝐵≥𝜏𝐴, each cap center has output amplitude (1 −𝜏)𝑘𝐴 (Theorem 12).

    Source: §1.2 · p. 4

  • Results

    The upper bound is dimension-free up to logarithmic factors, while full-ball zero-bias sparsity collapses to at most 2k units and comparable positive thresholds restore width dependence.

    Source: §1 · p. 1, §1.1 · p. 3, §1.2 · p. 4

  • Takeaways & Limitations

    The domain and availability of activation thresholds determine whether pointwise sparsity also limits the total number of useful neurons.

    Source: §1.1 · p. 3, §1.2 · p. 4

    The agnostic minimax characterization applies to one explicitly normalized bounded loss and comparable bias and weight scales, and does not establish a matching lower bound for realizable learning or every bounded Lipschitz loss.

    Source: §5.1 · p. 12, §6 · p. 13

Abstract

from arXiv · show

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.

1 Introduction

Activation sparsity limits active units per input without fixing their identities, raising whether it controls capacity across all admissible activation patterns. The paper establishes a dimension-free rate up to logarithmic factors, studies when width dependence persists, and outlines the constructions and proof tools behind those results.

1.1 Model and results

  • On the full Euclidean ball, zero-bias k-sparsity forces at most 2k nonzero units, whereas positive thresholds restore width dependence through disjoint spherical caps.The cap construction works in logarithmic dimension and does not restrict the sparsity promise to isolated sample locations.Source: §1.1 · p. 3
  • The upper bound removes the explicit input-dimension factor at logarithmic cost, while the logarithm-free form of the conjecture remains unresolved.The comparison also improves the bias coefficient from sk to k.Source: §1.1 · p. 3

1.2 Technique overview

  • A support-preserving cover avoids counting activation patterns, and one chain over normalized activation-count classes controls all counts simultaneously.The cover shifts approximating pre-activations downward to preserve zero coordinates; normalization removes the count from the cover’s scale-dependent entropy.Source: §1.2 · pp. 3–4

1.3 Related work

  • The analysis addresses a uniform complexity bound for a one-layer class with a fixed activation promise, distinct from compositional sparsity and stability-based guarantees.The covering step adapts scale-sensitive covering and chaining tools to sparse supports.Source: §1.3 · p. 5

2 A dimension-free upper bound

The section develops a dimension-free complexity bound by preserving sparse supports in covers and chaining across activation scales. It separates large-bias contributions as constants.

2.1 Reduction and the activation budget

  • Counting active sample-unit pairs bounds the total activation budget by km, linking network complexity to the per-input sparsity constraint.The argument bounds each unit's signed contribution using Q√t_j, where t_j is its number of active sample points.Source: §2.1 · p. 5

2.2 Covering sparse outputs

  • Shifting each affine approximant downward before applying ReLU preserves zero coordinates while keeping the sparse outputs within the cover's Euclidean error.For an affine approximation error δ, the downward shift ensures inactive coordinates remain zero.Source: §2.2 · p. 6

2.3 One chain over all normalized scales

  • A single finite chain over normalized activation scales incurs only a log(2m) cost for selecting the activation count, without comparing scale-specific expectations.The normalization removes the activation count from the cover's scale-dependent entropy.Source: §2.3 · p. 6

2.4 Large biases contribute constants

  • Biases beyond the input-dependent range are clipped, leaving a bounded-bias network plus a constant correction contributed only by units active everywhere.At most k such corrections occur, each bounded in magnitude by the excess bias range.Source: §2.4 · p. 7

2.5 Proof of Theorem 2

  • Theorem 2 gives a universal-constant bound by combining the clipped-class envelope with Proposition 7, including the zero-envelope case.When the clipped-class envelope is zero, the original class consists of constants.Source: §2.5 · p. 7

3 Lower bounds on the same class

The lower-bound construction uses independently signed neuron clusters on separate inputs to show how changing active units across a sample retains width dependence. Its dimension condition supplies the directions needed for that encoding.

3.1 Proof of Theorem 3

  • A finite-support marginal assigns one cluster of k parallel neurons to each orthogonal input direction, allowing independent output signs across clusters.On input R e_b, only cluster b is active and the network can output kAθ_b.Source: §3.1 · p. 8, §3 · p. 8
  • A separate constant-function subclass contributes a kB/√m term, so the lower bound combines alternative weight and bias constructions.The weight-cluster and constant subclasses need not fit simultaneously into one network.Source: §3.1 · p. 9
  • The construction's dimension condition supplies orthogonal cluster directions; the authors do not claim sharpness for every smaller fixed dimension.For m≥s/k, repeatedly observed clusters yield square-root fluctuations, while for m≤s/k the construction can use one cluster per support point.Source: §3.1 · pp. 8–9

4 When does sparsity remove the width dependence?

Whether input-wise sparsity removes width dependence on the full ball depends on the activation thresholds. Zero biases collapse the number of useful units, whereas positive thresholds allow distinct clusters to activate on separated regions.

4 When does sparsity remove the width dependence?

  • Zero-bias networks that are k-sparse throughout the ball have a reduced representation with at most 2k nonzero units and worst-case complexity of order kA/√m.The upper bound follows from finding antipodal radius-R points that avoid every nonzero neuron's zero hyperplane simultaneously.Source: §4 · p. 9
  • Central symmetry alone does not force width collapse: on a finite union of antipodal pairs, different zero-bias clusters can remain admissible.The full-ball argument instead uses an antipodal pair avoiding every nonzero neuron's zero hyperplane.Source: §4 · p. 9
  • On a polytope with finitely many vertices, at most k|V| units are nonzero on the domain, yielding a neuronwise bound even with biases.On an interval, this removes width dependence for every bias bound.Source: §4 · p. 9
  • When B≥τA, the full-ball class retains the lower-bound rate with only O(log(2q)) dimensions sufficient.Separated directions support clusters whose activation regions do not overlap anywhere on the ball.Source: §4 · p. 10
  • The logarithmic dimension requirement is necessary for constant-amplitude sign encoding, not for every complexity lower bound.The argument uses Lipschitzness and volume comparison to bound how many inputs can realize all signs at fixed amplitude.Source: §4 · p. 10

5 Learning consequences

The section derives statistical guarantees for the fixed sparse class and then gives an agnostic minimax characterization for one normalized bounded loss. Its learning guarantees are existence results, not claims of efficient optimization.

5 Learning consequences

  • For bounded Lipschitz losses, an approximate empirical risk minimizer exists measurably, and the section gives agnostic and realizable statistical guarantees.The realizable guarantee assumes labels equal a class member's predictions almost surely and zero loss on equal arguments.Source: §5 · p. 11
  • The existence proof uses compactness and separability to select the first element of a countable dense subclass whose empirical loss is within η of its infimum.This selection argument does not provide an effective search procedure.Source: §5 · p. 11
  • The generalization argument applies symmetrization, scalar contraction, and bounded differences to obtain a uniform one-sided bound, then uses the reverse direction and a union bound for absolute deviation.The proof cites the expected-complexity form of the standard Rademacher generalization inequality.Source: §5 · p. 11

5.1 Agnostic minimax risk for a normalized bounded loss

  • Under the stated dimension and comparable-bias conditions, the agnostic minimax result is specific to one normalized bounded loss and does not establish matching realizable or all-loss lower bounds.The associated expected-excess-risk sample-size order is eΘ(s/(kε^2)) for sufficiently small ε.Source: §5.1 · p. 12

6 Scope and remaining questions

The section distinguishes pointwise activation sparsity from a globally small set of useful units and identifies unresolved bounds and scope limits. In particular, the logarithm-free conjecture and the geometry between two domain regimes remain open questions.

6 Scope and remaining questions

  • Zero thresholds force at most 2k nonzero units on the full ball, while positive thresholds can isolate independently signed caps and restore width dependence, even in logarithmic dimension.These are distinct threshold effects; the cap construction's sufficient threshold is not established as critical.Source: §6 · p. 12
  • The logarithm-free form of the conjecture remains unresolved; removing the finite-union cost alone would not establish it.The present entropy bound and summing over chaining scales contribute logarithmic factors.Source: §6 · p. 12
  • The domain results leave open how complexity interpolates between zero-bias collapse and the full-ball cap construction; spherical-code dimension constants are also not sharp.Understanding small positive thresholds and fixed low dimension is identified as a remaining question.Source: §6 · pp. 12–13
  • The agnostic minimax characterization covers one normalized bounded loss with comparable bias and weight scales, while all classes require sparsity on a fixed domain before sampling.The section does not settle realizable learning, every loss, distribution-dependent sparsity, or multilayer extensions.Source: §6 · p. 13

A The affine covering estimate

The affine covering estimate bounds sample evaluations using a Gaussian packing argument in the span of the sample. Its proof handles the sample seminorm by restricting to that span and combines linear and bias covers.

A The affine covering estimate

  • The samplewise affine covering lemma applies to every radius-R sample, all W,B ≥ 0, and every δ > 0.The lemma bounds the affine evaluation class by the covering estimate labeled (5).Source: A The affine covering estimate · p. 15
  • The proof restricts the linear class to the span of the sample, where the maximum sample evaluation defines a norm, and uses Gaussian packing to bound its covering number.Projection preserves sample evaluations while decreasing Euclidean norm.Source: A The affine covering estimate · p. 15
  • A Gaussian maximal inequality controls the sample evaluations, and a grid over the bias interval combines with the linear cover to cover affine evaluations.The stated logarithmic covering bound includes a term proportional to A^2 log(2m)/δ^2 and the bias grid has at most floor(4B/δ)+1 points.Source: A The affine covering estimate · p. 15
  • The proof treats zero scales separately and establishes compactness and finiteness for the relevant covering and chaining suprema.It also handles the case m = 1 by choosing at least one chaining level.Source: A The affine covering estimate · p. 15

B Proof of the agnostic minimax bound

The proof establishes the minimax upper bound with approximate empirical risk minimization and the lower bound with a fixed family of cap-based sign choices. The testing argument bounds excess risk directly, including for improper or randomized learning rules.

B Proof of the agnostic minimax bound

  • The upper bound uses a measurable approximate empirical risk minimizer and bounds expected excess risk through the normalized class's complexity.The proof takes the better of this bound and the trivial bound of 1.Source: B Proof of the agnostic minimax bound · p. 16
  • The lower-bound proof uses cap directions to realize independent signs, then a fixed family of distributions with small unknown signed label means to make neighboring choices difficult to distinguish.The argument controls adjacent distributions' divergence and applies to improper or randomized rules.Source: B Proof of the agnostic minimax bound · p. 16
  • The lower-bound argument directly bounds expected excess risk for the full-ball class rather than deriving learning hardness from a complexity lower bound.It averages excess risk over a fixed family of sign choices and uses an Assouad-type argument.Source: B Proof of the agnostic minimax bound · pp. 16–17

AI Disclosure

The authors wrote the original manuscript, including its activation-budget reduction and margin-shifted covering argument. Later revisions used OpenAI Codex, including GPT-5.6 Solar and GPT-6 Astra, for proof checking, mathematical revisions, literature lookup, and exposition.

AI Disclosure

  • AI-assisted revisions replaced per-scale concentration and dyadic peeling with normalized single-neuron-class chaining, added threshold clipping for the bias term, and extended clustered lower bounds to i.i.d. samples without divisibility assumptions.These changes appear in Section 2, Lemma 8, and Theorem 3.Source: AI Disclosure · p. 17
  • Revisions added a zero-bias width-collapse result and a disjoint-cap lower bound on the entire ball in logarithmic dimension.The lower-bound construction does not assume sparsity only on the sampling support.Source: AI Disclosure · p. 17
  • The learning lower bound was reformulated as an Assouad-type argument for a normalized class under specified bounded linear loss, aligning the learning upper and lower bounds to one model.AI tools also assisted with edge-case checks, finite-instance verification scripts, and expansion of the technique overview.Source: AI Disclosure · p. 17
  • The authors take full responsibility for the final manuscript, including AI-assisted material and its correctness, originality, attribution, and citations.Source: AI Disclosure · p. 17
Loading 2609.09130v1…