Nearly Tight Rademacher Bounds for Sparsely Activated Neural Networks Xiaoyu Li1
Zhizhou Sha2
1 University of New South Wales 2 University of Texas at Austin
arXiv:2609.09130v1 [cs.LG] 8 Sep 2026
3 University of Sydney
Jiaojiao Jiang1
Junbin Gao3
Andi Han3
{xiaoyu.li2,jiaojiao.jiang}@unsw.edu.au [email protected] {junbin.gao,andi.han}@sydney.edu.au
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 𝑠, at most 𝑘 active units per input, and effective weight and bias bounds in the class’s fixed radius-𝑅 input domain satisfies √︁ 𝑊 , 𝐵, every size-𝑚 sample √ R (𝑆) ≤ 𝐶𝑊 𝑅 min{𝑘, 𝑠𝑘/𝑚 log3/2 (2𝑚)} + 𝑘𝐵/ 𝑚. 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 2𝑘 nonzero units and complexity 𝑂 (𝑘𝑊 𝑅/ 𝑚), whereas bias bounds comparable to 𝑊 𝑅 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 𝑊 𝑅, we also obtain agnostic minimax excess-risk bounds of order min{1, 𝑠/(𝑘𝑚)} up to logarithms.
Keywords: Activation sparsity, Rademacher complexity, metric entropy, neural networks, generalization
1
Introduction
Activation sparsity limits how many hidden units a network uses on an input, while allowing the identities of those units to change across inputs. It limits the number of nonzero contributions without simply reducing the number of available parameters. The statistical question is whether this input-dependent constraint controls a network’s capacity uniformly over all admissible activation patterns. Awasthi et al. (2024), henceforth ADKM, formulated this question for one-hidden-layer ReLU networks. Their model is motivated by sparse hidden activations, but imposes an exact mathematical promise: at most 𝑘 of the 𝑠 hidden units are active on every point in a prescribed √︁ input set. For bounded weights and inputs, e they obtained a Rademacher bound with dependence 𝑂 ( 𝑠𝑛𝑘/𝑚), where 𝑛 is the input dimension, and √ conjectured that the factor 𝑛 could be removed (Conjecture 20). The challenge is to retain the sparsity improvement in width while avoiding a count of all halfspace activation patterns. We establish the dimension-free rate up to log3/2 (2𝑚) and ask when its remaining width dependence is necessary. Our analysis separates three questions: the worst-case capacity of the fixed-domain class, the effect of the domain on admissible activation regions, and the agnostic learning difficulty under a specified loss. The answers distinguish sparse computation on each input from a globally small collection of useful neurons. 1
1.1
Model and results
Let 𝑛, 𝑠, 𝑚 ≥ 1, 1 ≤ 𝑘 ≤ 𝑠, and 𝑊 , 𝐵, 𝑅 ≥ 0. Fix a nonempty set X0 ⊆ {𝑥 ∈ ℝ𝑛 : ∥𝑥 ∥ 2 ≤ 𝑅} before sampling. Write 𝜎 (𝑧) = max{𝑧, 0}. 𝑊 ,𝐵 Definition 1 (ADKM’s class on a fixed input set). The class H𝑛,𝑠,𝑘 (X0 ) consists of restrictions to X0 of functions 𝑠 ∑︁ ℎ(𝑥) = 𝑢 𝑗 𝜎 (⟨𝑤 𝑗 , 𝑥⟩ − 𝑏 𝑗 ) 𝑗=1
admitting a representation with ∥𝑢 ∥ ∞ max ∥𝑤 𝑗 ∥ 2 ≤ 𝑊 ,
∥𝑢 ∥ ∞ max |𝑏 𝑗 | ≤ 𝐵,
𝑗
#{ 𝑗 : ⟨𝑤 𝑗 , 𝑥⟩ > 𝑏 𝑗 } ≤ 𝑘
𝑗
(𝑥 ∈ X0 ).
The input set is part of the class definition. Upper bounds hold on every 𝑆 = (𝑥 1, . . . , 𝑥𝑚 ) ∈ X0𝑚 ; a lower-bound construction is allowed to choose X0 and a distribution on it. Requiring sparsity on a larger set can give a smaller class. No assertion below identifies the support-wide class with a class chosen after seeing a sample. For independent uniform signs 𝜁𝑖 ∈ {−1, 1}, define R H (𝑆) =
𝑚 ∑︁ 1 𝔼𝜁 sup 𝜁𝑖 ℎ(𝑥𝑖 ), 𝑚 ℎ∈ H 𝑖=1
𝐴 = 𝑊 𝑅,
ℓ𝑚 = log(2𝑚),
𝜌𝑚 =
𝑚 1 ∑︁ 𝔼 𝜁𝑖 . 𝑚 𝑖=1
All√logarithms are natural unless indicated otherwise. The elementary moment bound in Lemma 9 gives √ 1/ 3𝑚 ≤ 𝜌𝑚 ≤ 1/ 𝑚. Theorem 2 (Dimension-free upper bound with separated bias). There is a universal constant 𝐶 ≥ 1 such that, for all parameters and input sets above and every 𝑆 ∈ X0𝑚 , ( √︂ ) 𝑠𝑘 3/2 R H𝑊 ,𝐵 ( X0 ) (𝑆) ≤ 𝐶𝐴 min 𝑘, ℓ + 𝑘𝐵𝜌𝑚 . (1) 𝑛,𝑠,𝑘 𝑚 𝑚 √ In addition, R H𝑊 ,𝐵 ( X0 ) (𝑆) ≤ 𝑘 (𝐴 + 𝐵) and R H𝑊 ,𝐵 ( X0 ) (𝑆) ≤ 2𝑠 (𝐴 + 𝐵)/ 𝑚. 𝑛,𝑠,𝑘
𝑛,𝑠,𝑘
Thus one may always take the smallest of the three upper bounds. The last one is useful in the dense regime 𝑘 = 𝑠, where it avoids a logarithmic loss. Dimension-free means that 𝑛 does not appear separately √ from 𝑅; on the unnormalized Boolean cube, 𝑅 = 𝑛 still carries a dimension dependence. Theorem 3 (Lower bound on i.i.d. samples). Let 𝑞 = min{⌊𝑠/𝑘⌋, 𝑚} and suppose 𝑛 ≥ 𝑞. There are a finite input set X0 in the radius-𝑅 ball and a marginal 𝐷𝑥 on it such that ( √︂ ) ! 1 𝑠𝑘 𝑘𝐵 𝔼𝑆∼𝐷𝑥𝑚 R H𝑊 ,𝐵 ( X0 ) (𝑆) ≥ √ 𝐴 min 𝑘, +√ . (2) 𝑛,𝑠,𝑘 𝑚 𝑚 4 2 The same expression lower-bounds the supremum over all admissible input sets and samples. √︁ √ e For 𝑛 ≥ 𝑞 and 𝑚 ≥ 𝑠/𝑘, these results determine the worst-case scaling Θ(𝐴 𝑠𝑘/𝑚 + 𝑘𝐵/ 𝑚), with logarithmic slack only in the weight term. For 𝑚 ≤ 𝑠/𝑘 and sufficiently large 𝑛, the weight term saturates at 𝑘𝐴. The bounds cover arbitrary 𝑠, 𝑘, 𝑚 without divisibility assumptions. They concern class complexity; Theorem 3 alone is not a lower bound on every learning algorithm. 2
The domain can change the answer. On the entire Euclidean ball, zero-bias 𝑘-sparsity forces at most √ 2𝑘 nonzero units, giving the smaller rate Θ(𝑘𝐴/ 𝑚) in the worst case (Proposition 10). Positive thresholds restore the width dependence: Theorem 12 realizes the lower √ rate on that same full-ball class, using separated spherical caps in only logarithmic dimension when 𝐵 ≥ ( 3/2)𝐴. Thus the lower bound need not rely on imposing sparsity only at isolated sampling locations. A same-loss learning characterization. We derive general bounded-loss guarantees and, separately, prove an agnostic minimax result for the normalized class and a fixed bounded linear loss. Under the explicit √︁ dimension and comparable-bias conditions of Theorem 14, its expected excess-risk rate is e Θ(min{1, 𝑠/(𝑘𝑚)}). This lower bound is established directly in the learning experiment, not inferred from Rademacher complexity. It is not a claim of optimality for every loss or for realizable learning. Comparison with the original bound. ADKM’s equation (15) has the displayed dependence √︁ (𝑊 𝑅 + √︁ √ 𝐵) 𝑠𝑛𝑘 log(𝑘𝑚(𝑅 + 𝐵))/ 𝑚 in its parameter regime. Their conjectured dependence is (𝑊 𝑅 + 𝐵) √ 𝑠𝑘/𝑚. √ Equation (1) removes the explicit 𝑛 at a logarithmic cost and improves the bias coefficient from 𝑠𝑘 to 𝑘. The logarithm-free form of their conjecture remains unresolved here. Bounds based only on the sum of √ the individual neuron complexities give 𝑂 (𝑠 (𝐴 + 𝐵)/ 𝑚); the point is to combine norm control with the shared activation budget.
1.2
Technique overview
The upper bound uses the total activation budget without fixing an activation pattern. The lower bounds then ask how many independently signed neuron clusters that budget permits, first on a discrete domain and then on the entire ball. From a network to one normalized neuron process. By positive homogeneity, absorb each outer weight’s magnitude into its neuron, leaving an outer sign and parameters ∥𝑣 𝑗 ∥ 2 ≤ 𝑊 , |𝛽 𝑗 | ≤ 𝐵. If 𝐼 𝑗 is its Í active sample set, double-counting gives 𝑗 |𝐼 𝑗 | ≤ 𝑘𝑚. Let F𝑡 be the sample-output vectors of one neuron active on at most 𝑡 coordinates, and put 𝑄 = max1≤𝑡 ≤𝑚 𝑡 −1/2 sup 𝑓 ∈ F𝑡 |⟨𝜁 , 𝑓 ⟩|. Then ∑︁ ∑︁ 𝑗
𝜁𝑖 𝜎 (⟨𝑣 𝑗 , 𝑥𝑖 ⟩ − 𝛽 𝑗 ) ≤ 𝑄
𝑖
∑︁ √︁
√ |𝐼 𝑗 | ≤ 𝑄 𝑠𝑘𝑚.
𝑗
Inactive √︁ units contribute zero. After division by 𝑚 and averaging, Lemma 4 bounds the network complexity by 𝑠𝑘/𝑚 𝔼𝑄. The displayed inequality holds for each sign vector: it does not require choosing the active sets before observing the signs. The remaining task is to control all activation counts simultaneously. A cover that preserves inactive coordinates. A direct affine approximation followed by ReLU can turn zero coordinates into small positive ones, losing the sparse support in its Euclidean error. We instead shift every approximating pre-activation downward. If ∥𝑔 − 𝑔b∥ ∞ ≤ 𝛿, then 𝑓b = 𝜎 (b 𝑔 − 𝛿) vanishes wherever √ b 𝑓 = 𝜎 (𝑔) vanishes and differs from 𝑓 by at most 2𝛿 elsewhere. Hence ∥ 𝑓 − 𝑓 ∥ 2 ≤ 2𝛿 𝑡 for 𝑓 ∈ F𝑡 . Applying this transformation to a dimension-free affine cover gives Lemma 5, without counting halfspace activation patterns. The centers are allowed outside the parameter-constrained class; only their approximation error matters.
3
√ One chain, rather than separate bounds at each count. Normalize F𝑡 by 𝑡 and take the symmetric union 𝑚 Ø 𝑇 = 𝑡 −1/2 F𝑡 ∪ −𝑡 −1/2 F𝑡 , 𝑄 = sup ⟨𝜁 , 𝑧⟩. 𝑧 ∈𝑇
𝑡 =1
The normalization removes 𝑡 from the cover’s scale-dependent entropy; selecting a member of the union costs only an additive log(2𝑚). A single finite chaining argument therefore bounds the expectation of the maximum itself, without interchanging maximum and expectation. Truncating √︁ the chain at radius at most √ (𝐴 + 𝐵)/ 𝑚 controls its residual by 𝐴 + 𝐵. The affine entropy contributes log(2𝑚), and summing over scales contributes another logarithm, giving 𝔼𝑄 = 𝑂 ((𝐴 + 𝐵) log3/2 (2𝑚)). This identifies the remaining logarithmic loss: removing the lower-order union cost alone would not remove it. Clipping thresholds separates the constant part. The preceding argument initially charges both 𝐴 and 𝐵 at the network rate. To refine it, clip 𝛽 to 𝛽 ◦ ∈ [−𝐴, 𝐴] and use the identity 𝜎 (⟨𝑣, 𝑥⟩ − 𝛽) = 𝜎 (⟨𝑣, 𝑥⟩ − 𝛽 ◦ ) + (−𝛽 − 𝐴)+
(∥𝑥 ∥ 2 ≤ 𝑅).
Clipping creates no new activation. Every nonzero constant correction comes from a unit previously active everywhere, so at most 𝑘 corrections occur. Thus ℎ = ℎ 0 + 𝑐, with clipped bias bound min{𝐴, 𝐵} and |𝑐 | ≤ 𝑘 (𝐵 − 𝐴)+ (Lemma 8). Applying the chain and the envelope bound to ℎ 0 , and the exact constant-class complexity to 𝑐, yields Theorem 2. Independent clusters and the geometry of the domain. For the discrete lower bound, use 𝑞 = min{⌊𝑠/𝑘⌋, 𝑚} orthogonal input directions and 𝑘 parallel neurons per direction. Each cluster carries its own √︁ sign. Under uniform i.i.d. sampling, its signed occupancy has absolute expectation of order 𝑚/𝑞, giving the weight lower bound without balanced-count or divisibility assumptions. The separate constant subclass supplies the bias term. On the full ball, however, a generic antipodal pair counts every nonzero zero-bias neuron, forcing at most 2𝑘 in total. To recover independent clusters there, we use disjoint spherical caps. √ Directions with pairwise inner product at most 1/2, together with threshold 𝜏𝐴 for 𝜏 = 3/2, prevent two clusters from activating at any point of the ball. A random-sign packing supplies the directions in 𝑂 (log(2𝑞)) dimensions. When 𝐵 ≥ 𝜏𝐴, each cap center still has output amplitude (1 − 𝜏)𝑘𝐴, so the same occupancy argument applies (Theorem 12). Turning sign encoding into a learning lower bound. A complexity lower bound alone does not establish learning hardness. Under the conditions of Theorem 14, normalization by 𝑘 (𝐴 + 𝐵) makes the cap construction’s sign amplitude a positive universal constant. Assign binary labels small unknown means 𝛿𝜃𝑏 at the 𝑞 cap centers. Adjacent sign choices have joint-sample KL divergence at most 𝑂 (𝑚𝛿 2 /𝑞). Choosing 𝛿 √︁ as a sufficiently small constant times 𝑞/𝑚 keeps adjacent distributions hard to distinguish. Total variation then limits any learner’s correlation with the signs, including randomized and improper √︁ learners. For the specified bounded linear loss, this gives an expected excess-risk lower bound of order 𝑞/𝑚. Approximate ERM and the complexity upper bound give the corresponding upper rate for that same loss and normalized class; Appendix B supplies the testing calculation.
1.3
Related work
Our comparison uses the support-wide class and product norms of Awasthi et al. (2024). Their expressivity and computational results are distinct from the capacity question studied here. Norm-based analyses such as 4
Neyshabur et al. (2015); Golowich et al. (2018) control complexity without imposing this activation promise. We use an elementary neuronwise bound as the dimension-free baseline rather than asserting that all such norm-based results have identical specializations. Other sparsity notions lead to different guarantees. Galanti et al. (2023) study compositionally sparse networks, in which each neuron has a limited number of inputs. Muthukumar and Sulam (2023) use activation stability and sensitivity analysis to obtain predictor-dependent, derandomized PAC-Bayes guarantees across multiple layers. Our result is a uniform complexity bound for an entire one-layer class with a fixed activation promise; it does not require stability under parameter perturbations. Scale-sensitive covers of norm-constrained linear classes have a long history (Zhang, 2002). The affine cover used here is an application of dual Sudakov (Pajor and Tomczak-Jaegermann, 1986; Ledoux and Talagrand, 1991); the chain uses the familiar multiscale principle of Dudley (1967). The contribution of the covering step is its compatibility with sparse supports. We include the finite chaining argument and a proof of the required geometric covering estimate so that the proof interfaces can be checked directly.
2
A dimension-free upper bound
We first prove the bound with scale 𝑀 = 𝐴 + 𝐵. We then separate the contribution of large biases. Vectors of sample evaluations use the unnormalized Euclidean norm in ℝ𝑚 . The covering number 𝑁 (𝑇 , 𝜖, ∥ · ∥) permits centers in the ambient vector space; all covers used below are finite and deterministic once the sample is fixed.
2.1
Reduction and the activation budget
Positive homogeneity gives the exact reduced representation ℎ(𝑥) =
𝑠 ∑︁
𝜀 𝑗 𝜎 (⟨𝑣 𝑗 , 𝑥⟩ − 𝛽 𝑗 ),
𝜀 𝑗 ∈ {−1, 1},
∥𝑣 𝑗 ∥ 2 ≤ 𝑊 ,
|𝛽 𝑗 | ≤ 𝐵.
(3)
𝑗=1
For 𝑢 𝑗 ≠ 0, take 𝑣 𝑗 = |𝑢 𝑗 |𝑤 𝑗 , 𝛽 𝑗 = |𝑢 𝑗 |𝑏 𝑗 , and 𝜀 𝑗 = sign(𝑢 𝑗 ). For 𝑢 𝑗 = 0, take 𝑣 𝑗 = 0, 𝛽 𝑗 = 0 and 𝜀 𝑗 = 1; this only decreases the activation count. Conversely, (3) is realized in Definition 1 by 𝑢 𝑗 = 𝜀 𝑗 , 𝑤 𝑗 = 𝑣 𝑗 , and 𝑏 𝑗 = 𝛽 𝑗 . Sparsity does not depend on the outer signs. For 𝑡 ∈ [𝑚], let 𝑚 F𝑡 = (𝜎 (⟨𝑣, 𝑥𝑖 ⟩ − 𝛽))𝑖=1 : ∥𝑣 ∥ 2 ≤ 𝑊 , |𝛽 | ≤ 𝐵, #{𝑖 : ⟨𝑣, 𝑥𝑖 ⟩ > 𝛽} ≤ 𝑡 , √ and set 𝑃 (𝑡) = sup 𝑓 ∈ F𝑡 |⟨𝜁 , 𝑓 ⟩| and 𝑄 = max𝑡 ∈ [𝑚] 𝑃 (𝑡)/ 𝑡. Each 𝑓 ∈ F𝑡 has entries in [0, 𝑀] and satisfies √ ∥𝑓 ∥ 2 ≤ 𝑀 𝑡. Lemma 4 (Sample relaxation and budget). For every 𝑆 ∈ X0𝑚 , √︂ 𝑠𝑘 𝔼𝜁 𝑄. (4) R H𝑊 ,𝐵 ( X0 ) (𝑆) ≤ 𝑛,𝑠,𝑘 𝑚 Proof. Enlarge the reduced parameter set by requiring sparsity only on 𝑆. For fixed parameters, maximizing Í Í over the outer signs yields 𝑗 |𝑁 𝑗 |, where 𝑁 𝑗 = 𝑖 𝜁𝑖 𝜎 (⟨𝑣 𝑗 , 𝑥𝑖 ⟩ − 𝛽 𝑗 ). Let 𝑡 𝑗 = #{𝑖 : ⟨𝑣 𝑗 , 𝑥𝑖 ⟩ > 𝛽 𝑗 }. A unit with Í √ 𝑡 𝑗 = 0 contributes zero; otherwise |𝑁 𝑗 | ≤ 𝑄 𝑡 𝑗 . Double-counting active sample-unit pairs gives 𝑗 𝑡 𝑗 ≤ 𝑘𝑚. Therefore, for every sign vector and admissible configuration, √︄ ∑︁ ∑︁ ∑︁ √︁ √ |𝑁 𝑗 | ≤ 𝑄 𝑡𝑗 ≤ 𝑄 𝑠 𝑡 𝑗 ≤ 𝑄 𝑠𝑘𝑚. 𝑗
𝑗
𝑗
5
Take the supremum, divide by 𝑚, and average over the signs.
2.2
□
Covering sparse outputs
The affine evaluation class A = {(⟨𝑣, 𝑥𝑖 ⟩ − 𝛽)𝑖 : ∥𝑣 ∥ 2 ≤ 𝑊 , |𝛽 | ≤ 𝐵} obeys log 𝑁 (A, 𝛿, ∥ · ∥ ∞ ) ≤ 80
𝐴2 log(2𝑚) + log(1 + 4𝐵/𝛿), 𝛿2
𝛿 > 0.
(5)
For completeness, Lemma 15 proves this estimate using a Gaussian packing argument. Restricting to span{𝑥𝑖 } deals with the fact that max𝑖 |⟨𝑣, 𝑥𝑖 ⟩| need only be a seminorm on the original space. Lemma 5 (Shifted cover). For 𝑡 ∈ [𝑚] and 𝜖 > 0, log 𝑁 (F𝑡 , 𝜖, ∥ · ∥ 2 ) ≤ 320
√ 𝐴2𝑡 log(2𝑚) + log(1 + 8𝐵 𝑡/𝜖). 𝜖2
(6)
√ Proof. Put 𝛿 = 𝜖/(2 𝑡) and cover A in sup norm at radius 𝛿. For 𝑓 = 𝜎 (𝑔) ∈ F𝑡 , choose a center 𝑔b with 𝑔 − 𝛿). If 𝑔𝑖 ≤ 0, then 𝑔b𝑖 − 𝛿 ≤ 0, so 𝑓𝑖 = 𝑓b𝑖 = 0. On the other coordinates, the ∥𝑔 − 𝑔b∥ ∞ ≤ 𝛿 and use 𝑓b = 𝜎 (b √ 1-Lipschitz property of ReLU gives |𝑓𝑖 − 𝑓b𝑖 | ≤ 2𝛿. Thus ∥ 𝑓 − 𝑓b∥ 2 ≤ 2𝛿 𝑡 = 𝜖. The transformed cover has no more centers than the affine cover; substituting 𝛿 in (5) proves the claim. The centers need not satisfy the bias constraint, which is why we use external covers. □
2.3
One chain over all normalized scales
Define the symmetric set 𝑚 Ø 𝑇 = 𝑡 −1/2 F𝑡 ∪ −𝑡 −1/2 F𝑡 . 𝑡 =1
It contains 0, has radius at most 𝑀, and satisfies 𝑄 = sup𝑧 ∈𝑇 ⟨𝜁 , 𝑧⟩. By scaling Lemma 5 and taking the union of 2𝑚 covers, we get the uniform estimate log 𝑁 (𝑇 , 𝜖, ∥ · ∥ 2 ) ≤ ℓ𝑚 + 320
𝐴2 ℓ𝑚 + log(1 + 8𝐵/𝜖). 𝜖2
(7)
The entropy cost of selecting an activation count is only log(2𝑚), separate from the 𝜖 −2 term. No comparison of the expectations of different 𝑃 (𝑡) is needed. Lemma 6 (Finite Rademacher chaining). Let 𝑇 ⊆ ℝ𝑚 have radius at most 𝐷 > 0 and put 𝑟 𝑗 = 𝐷2− 𝑗 . For an integer 𝐽 ≥ 1, suppose external 𝑟 𝑗 -nets exist with cardinalities 𝑁 𝑗 and log 𝑁 𝑗 ≤ 𝐻 𝑗 , where 0 ≤ 𝐻 1 ≤ · · · ≤ 𝐻 𝐽 . Then 𝐽 ∑︁ √︁ √ 𝔼 sup ⟨𝜁 , 𝑧⟩ ≤ 𝑚 𝑟 𝐽 + 6 𝑟𝑗 𝐻𝑗 . (8) 𝑧 ∈𝑇
𝑗=1
Proof. Choose deterministic net maps 𝜋 𝑗 with ∥𝑧 − 𝜋 𝑗 𝑧 ∥ 2 ≤ 𝑟 𝑗 and set 𝜋0𝑧 = 0, 𝑁 0 = 1. The edge set 𝐸 𝑗 = {𝜋 𝑗 𝑧 − 𝜋 𝑗 −1𝑧 : 𝑧 ∈ 𝑇 } has at most 𝑁 𝑗 𝑁 𝑗 −1 elements, each with norm at most 𝑟 𝑗 + 𝑟 𝑗 −1 = 3𝑟 𝑗 . For every deterministic vector 𝑎, Ö 2 2 𝔼𝑒 𝜆⟨𝜁 ,𝑎⟩ = cosh(𝜆𝑎𝑖 ) ≤ 𝑒 𝜆 ∥𝑎 ∥ 2 /2 . 𝑖
The exponential-moment maximal inequality therefore gives √︁ √︁ 𝔼 max ⟨𝜁 , 𝑎⟩ ≤ 3𝑟 𝑗 2 log(𝑁 𝑗 𝑁 𝑗 −1 ) ≤ 6𝑟 𝑗 𝐻 𝑗 . 𝑎∈𝐸 𝑗
6
If the edge set is a singleton, its expected maximum is zero, so the same inequality applies. Telescope from √ 0 to 𝜋 𝐽 𝑧 and use ⟨𝜁 , 𝑧 − 𝜋 𝐽 𝑧⟩ ≤ 𝑚 𝑟 𝐽 for the residual. Taking the supremum and expectation proves (8). The process is defined at every point of ℝ𝑚 , so external centers cause no change to the argument. □ Proposition 7 (Unseparated bound). There is a universal constant 𝐶 0 ≥ 1 such that √︁ 𝔼𝑄 ≤ 𝐶 0 𝑀ℓ𝑚3/2, R H𝑊 ,𝐵 ( X0 ) (𝑆) ≤ 𝐶 0 𝑀 𝑠𝑘/𝑚ℓ𝑚3/2 . 𝑛,𝑠,𝑘
√ Proof. If 𝑀 = 0, both quantities vanish. Otherwise use Lemma 6 with 𝐷 = 𝑀 and 𝐽 = max{1, ⌈log2 𝑚⌉}. √ Then 𝑚 𝑟 𝐽 ≤ 𝑀 and 𝐽 ≤ ℓ𝑚 /log 2. Since 𝐵 ≤ 𝑀, (7) permits 𝐻 𝑗 = ℓ𝑚 + 320𝐴2 ℓ𝑚 /𝑟 2𝑗 + ( 𝑗 + 4) log 2. Subadditivity of the square root,
Í
𝑗 ≥1 2
− 𝑗 = 1, and Í
𝑗 ≥1 2
−𝑗 √𝑗 + 4 ≤ Í
𝑗 ≥1 2
− 𝑗 ( 𝑗 + 4) = 6 give
√︁ √ √ √ 𝔼𝑄 ≤ 𝑀 + 6𝑀 ℓ𝑚 + 6 320 𝐴 ℓ𝑚 𝐽 + 36𝑀 log 2 ≤ 𝐶 0 𝑀ℓ𝑚3/2 . For example, one may take
√︁ √ 6 320 + 6 1 + 36 log 2 . + 𝐶0 = log 2 (log 2) 3/2
The comparison uses only 𝐴 ≤ 𝑀 and ℓ𝑚 ≥ log 2, including 𝑚 = 1. Lemma 4 yields the network bound.
2.4
□
Large biases contribute constants
𝑊 ,𝐵 Lemma 8 (Bias clipping). Put 𝑏 0 = min{𝐵, 𝐴} and 𝑑 = (𝐵 − 𝐴)+ . Every ℎ ∈ H𝑛,𝑠,𝑘 (X0 ) can be written on X0 as ℎ = ℎ 0 + 𝑐, where 𝑊 ,𝑏 0 ℎ 0 ∈ H𝑛,𝑠,𝑘 (X0 ), |𝑐 | ≤ 𝑘𝑑.
Proof. Use (3) and clip each 𝛽 𝑗 to [−𝐴, 𝐴]. For 𝑎 ∈ [−𝐴, 𝐴] and every 𝛽 ∈ ℝ, the three cases 𝛽 < −𝐴, −𝐴 ≤ 𝛽 ≤ 𝐴, and 𝛽 > 𝐴 give 𝜎 (𝑎 − 𝛽) = 𝜎 (𝑎 − 𝛽 ◦ ) + (−𝛽 − 𝐴)+,
𝛽 ◦ = max{−𝐴, min{𝛽, 𝐴}}.
(9)
Clipping creates no active unit at any input in the ball. A unit with 𝛽 < −𝐴 was strictly active everywhere Í before clipping, and a unit with 𝛽 > 𝐴 stays inactive. Hence ℎ 0 = 𝑗 𝜀 𝑗 𝜎 (⟨𝑣 𝑗 , 𝑥⟩ − 𝛽 ◦𝑗 ) belongs to the stated Í class. Every nonzero summand of 𝑐 = 𝑗 𝜀 𝑗 (−𝛽 𝑗 − 𝐴)+ comes from a unit active everywhere. Because X0 is nonempty, there can be at most 𝑘 such units, each contributing at most 𝑑 in absolute value. □
2.5
Proof of Theorem 2
Proof. The complexity of constants in [−𝑘𝑑, 𝑘𝑑] is 𝑘𝑑𝜌𝑚 . Subadditivity and Lemma 8 give the slightly sharper intermediate bound √︁ R H𝑊 ,𝐵 ( X0 ) (𝑆) ≤ (𝐴 + 𝑏 0 ) min{𝑘, 𝐶 0 𝑠𝑘/𝑚ℓ𝑚3/2 } + 𝑘𝑑𝜌𝑚 . (10) 𝑛,𝑠,𝑘
Here the two estimates for the clipped class are its pointwise envelope and Proposition 7. Using 𝐴 +𝑏 0 ≤ 2𝐴, 𝑑 ≤ 𝐵, and 𝐶 0 ≥ 1 proves (1) with 𝐶 = 2𝐶 0 . This also covers 𝐴 = 0: the clipped class is then zero and the original class consists exactly of constants in [−𝑘𝐵, 𝑘𝐵]. 7
The original envelope is |ℎ(𝑥)| ≤ 𝑘𝑀, proving the first additional bound. For the second, ignore sparsity and bound each signed neuron separately. Since the unsigned neuron class contains zero, sign symmetry and scalar contraction imply ! ∑︁ ∑︁ ∑︁ √ 𝔼 sup 𝜁𝑖 𝜎 (⟨𝑣, 𝑥𝑖 ⟩ − 𝛽) ≤ 2 𝑊 𝔼 𝜁𝑖 𝑥𝑖 + 𝐵𝔼 𝜁𝑖 ≤ 2𝑀 𝑚. ∥𝑣 ∥ ≤𝑊 ,|𝛽 | ≤𝐵
𝑖
𝑖
2
𝑖
√ Summing over 𝑠 neurons proves 2𝑠𝑀/ 𝑚.
3
□
Lower bounds on the same class
The lower bound uses parallel neurons within each cluster and orthogonal directions between clusters. Parallelism allows 𝑘 units to each attain value 𝐴 on a single input while respecting the radius constraint. Orthogonality makes the output values of different clusters independent parameters on the constructed support. Lemma 9 (A moment estimate). If 𝑍 has finite fourth moment and 𝔼𝑍 2 > 0, then 𝔼|𝑍 | ≥ In particular, 𝔼|
Í𝑚
𝑖=1 𝜁𝑖 | ≥
(𝔼𝑍 2 ) 3/2 . (𝔼𝑍 4 ) 1/2
√︁ 𝑚/3.
Proof. Hölder applied to |𝑍 | 2 = |𝑍 | 2/3 |𝑍 | 4/3 gives 𝔼𝑍 2 ≤ (𝔼|𝑍 |) 2/3 (𝔼|𝑍 | 4 ) 1/3 . For the sign sum, 𝔼𝑍 2 = 𝑚 and 𝔼𝑍 4 = 3𝑚 2 − 2𝑚 ≤ 3𝑚 2 . □
3.1
Proof of Theorem 3
Proof. First suppose 𝐴 > 0. Choose orthonormal vectors 𝑒 1, . . . , 𝑒𝑞 ∈ ℝ𝑛 and let 𝐷𝑥 be uniform on X0 = {𝑅𝑒 1, . . . , 𝑅𝑒𝑞 }. Use 𝑞 clusters of 𝑘 neurons each, with weight 𝑊 𝑒𝑏 and zero bias in cluster 𝑏. There are at most 𝑠 neurons; pad with inactive zero units when necessary. On 𝑅𝑒𝑏 , only cluster 𝑏 is active. Choosing a common outer sign 𝜃𝑏 ∈ {−1, 1} in that cluster realizes ℎ𝜃 (𝑅𝑒𝑏 ) = 𝑘𝐴𝜃𝑏 . Write 𝑋𝑖 = 𝑅𝑒 𝐽𝑖 , where the 𝐽𝑖 are i.i.d. uniform on [𝑞] and independent of the Rademacher signs. For each realized sample, optimizing over the cluster signs gives 𝑞 𝑚 ∑︁ 𝑘𝐴 ∑︁ R H𝑊 ,𝐵 ( X0 ) (𝑆) ≥ 𝔼𝜁 𝜁𝑖 1{𝐽𝑖 = 𝑏} . 𝑛,𝑠,𝑘 𝑚 𝑖=1
(11)
𝑏=1
For a fixed 𝑏, set 𝑍𝑏 =
Í
𝑖 𝜁𝑖 1{𝐽𝑖 = 𝑏} and 𝜆 = 𝑚/𝑞 ≥ 1. Independence and centering give
𝔼𝑍𝑏2 = 𝜆,
𝔼𝑍𝑏4 =
𝑚 3𝑚(𝑚 − 1) + ≤ 𝜆 + 3𝜆 2 ≤ 4𝜆 2 . 𝑞 𝑞2
Lemma 9, followed by (11), yields 𝔼𝑆 R H𝑊 ,𝐵 ( X0 ) (𝑆) ≥ 𝑛,𝑠,𝑘
√︁ 𝑘𝐴 √︁ 𝐴 𝑞/𝑚 ≥ √ min{𝑘, 𝑠𝑘/𝑚}. 2 2 2
For the last step, ⌊𝑠/𝑘⌋ ≥ 𝑠/(2𝑘) since 𝑠/𝑘 ≥ 1, and hence 𝑞 ≥ 12 min{𝑠/𝑘, 𝑚}. 8
(12)
The same class on the same support also contains the two constants ±𝑘𝐵: use 𝑘 zero-weight units with bias −𝐵 and a common outer sign. Thus for every sample, 𝑘𝐵 R H𝑊 ,𝐵 ( X0 ) (𝑆) ≥ 𝑘𝐵𝜌𝑚 ≥ √ . 𝑛,𝑠,𝑘 3𝑚
(13)
The two constructions are alternative subclasses; they need not fit simultaneously into one network. Taking the larger of (12) and (13) and using max{𝑎, 𝑏} ≥ (𝑎 + 𝑏)/2 proves (2). If 𝐴 = 0, take X0 = {0} and use only the constant subclass; the weight term is zero. Finally, a supremum over samples is at least their expectation under this marginal. □ Interpretation of the regimes. When 𝑚 ≤ 𝑠/𝑘, we may use one cluster per sample-sized support point; random repetitions only change constants in the lower bound. When 𝑚 ≥ 𝑠/𝑘, the ⌊𝑠/𝑘⌋ clusters are repeatedly observed and their signed sums have square-root fluctuations. The bias subclass has just one freely chosen sign, giving 𝑚 −1/2 decay independently of the number of available clusters. This explains the distinct width dependence in the upper bound. The dimensional condition is used to supply orthogonal cluster directions; it is not an assumption of Theorem 2, and no claim of sharpness for every smaller fixed dimension is made.
4
When does sparsity remove the width dependence?
The lower bound in Section 3 allows different neuron clusters to act independently on a discrete input set. Does its width dependence survive if sparsity is required throughout a full-dimensional convex domain? The answer depends on whether activation thresholds are available. Write 𝔹𝑛𝑅 = {𝑥 ∈ ℝ𝑛 : ∥𝑥 ∥ 2 ≤ 𝑅} and suppose 𝑅 > 0 throughout this section. Proposition 10 (Zero-threshold width collapse). Every zero-bias network that is 𝑘-sparse on 𝔹𝑛𝑅 has a reduced representation with at most min{𝑠, 2𝑘 } nonzero units. Consequently, for every 𝑆 ∈ (𝔹𝑛𝑅 )𝑚 , 4𝑘𝐴 R H𝑊 ,0 (𝔹𝑛 ) (𝑆) ≤ √ . 𝑅 𝑛,𝑠,𝑘 𝑚 √ The supremum over such samples is at least 𝑘𝐴𝜌𝑚 , so its order is 𝑘𝐴/ 𝑚. Proof. Use the reduced parameters in (3) and discard 𝑣 𝑗 = 0 units. Choose a unit direction outside the finitely many hyperplanes ⟨𝑣 𝑗 , 𝑥⟩ = 0. Each remaining unit is strictly active at exactly one of the two antipodal radius-𝑅 points. Both points lie in the required input domain, so the number of remaining units is at most 2𝑘. The neuronwise estimate in Theorem 2 then gives the upper bound. For the lower bound, repeat 𝑅𝑒 1 and use 𝑘 parallel units with weight 𝑊 𝑒 1 and a common outer sign. These networks are globally 𝑘-sparse and take values ±𝑘𝐴 on the sample. The case 𝑊 = 0 is immediate. □ Central symmetry alone is insufficient. On the finite set {±𝑅𝑒𝑏 : 𝑏 ∈ [𝑞]}, the zero-bias clusters from Section 3 remain admissible: most units can vanish on a given antipodal pair. The full-ball argument uses a pair that avoids every nonzero neuron’s zero hyperplane simultaneously. For a polytope X0 = conv(𝑉 ) with finitely many vertices, a related count holds even with biases. Every unit active somewhere is active at a vertex, since an affine function attains its maximum there. Hence at √ most 𝑘 |𝑉 | units are nonzero on the domain, giving the neuronwise bound 2𝑘 |𝑉 |(𝐴 + 𝐵)/ 𝑚. In particular, on an interval (𝑛 = 1), the width dependence disappears for every bias bound, not only for 𝐵 = 0. 9
Positive thresholds can instead isolate disjoint caps of the ball. Set √ 3 𝜏= , 𝑑𝑞 = min{𝑞, ⌈16 log(2𝑞)⌉}. 2 The following elementary packing suffices; we do not need sharp spherical-code bounds. Lemma 11 (Separated directions). If 𝑛 ≥ 𝑑𝑞 , there are unit vectors 𝑢 1, . . . , 𝑢𝑞 ∈ ℝ𝑛 with ⟨𝑢𝑏 , 𝑢𝑐 ⟩ ≤ 1/2 for 𝑏 ≠ 𝑐. Proof. If 𝑛 ≥ 𝑞, take orthogonal vectors. Otherwise 𝑛 ≥ 16 log(2𝑞). Take independent vectors uniform on Í {±𝑛 −1/2 }𝑛 . For aÍ fixed pair, their inner product has the law of 𝑛 −1 𝑛𝑟=1 𝜉𝑟 for independent uniform signs. 2 The bound 𝔼𝑒 𝜆 𝑟 𝜉𝑟 ≤ 𝑒 𝑛𝜆 /2 gives ℙ[⟨𝑢𝑏 , 𝑢𝑐 ⟩ > 1/2] ≤ 𝑒 −𝑛/8 . A union bound over pairs has probability at most 𝑞(𝑞 − 1)𝑒 −𝑛/8 /2 < 1. Thus a configuration with the required separation exists. □ Theorem 12 (A full-ball lower bound in logarithmic dimension). Let 𝑞 = min{⌊𝑠/𝑘⌋, 𝑚} and suppose 𝑛 ≥ 𝑑𝑞 . Put 𝑎 = min{𝐴, 𝐵/𝜏 }. There is a fixed marginal 𝐷𝑥 on 𝔹𝑛𝑅 such that √︁ 𝑘𝐵 1−𝜏 𝔼𝑆∼𝐷𝑥𝑚 R H𝑊 ,𝐵 (𝔹𝑛 ) (𝑆) ≥ 𝑐 cap 𝑎 min{𝑘, 𝑠𝑘/𝑚} + √ , 𝑐 cap = √ . (14) 𝑅 𝑛,𝑠,𝑘 𝑚 4 2 In particular, if 𝐵 ≥ 𝜏𝐴, the rate of Theorem 3 holds for the full-ball class itself, with only 𝑂 (log(2𝑞)) dimensions sufficient. Proof. Choose directions from Lemma 11 and put 𝐷𝑥 uniform on {𝑅𝑢 1, . . . , 𝑅𝑢𝑞 }. Suppose first that 𝑎 > 0. In cluster 𝑏, place 𝑘 copies of the unit 𝑣𝑏 = (𝑎/𝑅)𝑢𝑏 ,
𝛽𝑏 = 𝜏𝑎,
with a common outer sign 𝜃𝑏 . These parameters obey the norm and bias bounds. If two distinct clusters were active at an input 𝑥 ∈ 𝔹𝑛𝑅 , then ⟨𝑢𝑏 + 𝑢𝑐 , 𝑥⟩ > 2𝜏𝑅,
∥𝑢𝑏 + 𝑢𝑐 ∥ 22 = 2 + 2⟨𝑢𝑏 , 𝑢𝑐 ⟩ ≤ 3 = 4𝜏 2,
contradicting Cauchy–Schwarz. Thus the network is 𝑘-sparse at every point of the ball, not only at the sampling locations. At 𝑅𝑢𝑏 , its value is 𝑘𝑎(1 − 𝜏)𝜃𝑏 ; all other clusters are inactive because 1/2 < 𝜏. Pad with inactive units to width 𝑠. The moment√︁calculation √ in (12), with amplitude 𝑎(1 − 𝜏) replacing 𝐴, now gives a lower bound of 𝑎(1 − 𝜏) min{𝑘, 𝑠𝑘/𝑚}/(2 2). The same full-ball class contains the constants ±𝑘𝐵, contributing 𝑘𝐵𝜌𝑚 . Taking the larger of these two subclass bounds proves (14). If 𝑎 = 0, the constant subclass alone proves the assertion. □ What changes between the regimes? The zero-bias proposition turns pointwise sparsity into a global bound on the number of useful units. The cap construction defeats that implication by assigning different clusters disjoint activation regions. It also shows that a finite-support marginal does not require a function class whose sparsity promise is restricted to that finite support. For 𝑚 ≥ 𝑠/𝑘, the comparison is summarized in Table 1. The value 𝜏𝐴 is sufficient for the construction, not a proved critical threshold. The logarithmic dimension order is necessary for constant-amplitude sign encoding. Indeed, every full-ball network is 𝑘𝑊 -Lipschitz: along any segment, the finitely many affine pieces have gradients bounded by 𝑘𝑊 . When 𝐴 + 𝐵 > 0, normalization by 𝑘 (𝐴 + 𝐵) gives a function that is at most 1/𝑅-Lipschitz. If all signs on 𝑞 inputs can be realized at amplitude 𝛼 > 0, each pair of inputs must be at distance at least 2𝛼𝑅. Disjoint open balls of radius 𝛼𝑅 around them lie inside the ball of radius (1 + 𝛼)𝑅, so volume comparison gives 𝑞 ≤ (1 + 1/𝛼)𝑛 . This proves an Ω(log 𝑞) requirement when 𝛼 is constant; it is a statement about this encoding, not a necessary dimension condition for every complexity lower bound. 10
Table 1: Worst-case empirical complexity; 𝑔 = ⌊𝑠/𝑘⌋ and 𝑚 ≥ 𝑠/𝑘. The lower bounds also hold in expectation e permits logarithms in 𝑚; the middle row has none. for an appropriate i.i.d. marginal. Θ
5
Sparsity domain and bias
Dimension
Finite set, 𝐵 = 0 Entire ball, 𝐵 = 0 Entire ball, 𝐵 ≥ 𝜏𝐴
𝑛 ≥𝑔 𝑛≥1 𝑛 ≥ 𝑑𝑔
Complexity √︁ e Θ(𝐴 𝑠𝑘/𝑚) √ Θ(𝑘𝐴/ 𝑚) √︁ √ e Θ(𝐴 𝑠𝑘/𝑚 + 𝑘𝐵/ 𝑚)
Learning consequences
𝑊 ,𝐵 Fix the class H = H𝑛,𝑠,𝑘 (X0 ) before drawing data. In this section X0 is Borel, 𝐷 is a probability distribution on X0 × ℝ, and the loss ℓ : ℝ × ℝ → [0, 𝑏 ℓ ] is jointly Borel measurable and 𝐿-Lipschitz in its first argument. b𝑆 (ℎ) = 𝑚 −1 Í𝑖 ℓ (ℎ(𝑋𝑖 ), 𝑌𝑖 ). Put Write L𝐷 (ℎ) = 𝔼ℓ (ℎ(𝑋 ), 𝑌 ) and L √︁ 2𝑠 (𝐴 + 𝐵) 3/2 , 𝐶𝐴 min{𝑘, 𝑠𝑘/𝑚ℓ𝑚 } + 𝑘𝐵𝜌𝑚 . (15) 𝑈𝑚 = min 𝑘 (𝐴 + 𝐵), √ 𝑚
This is a deterministic upper bound on the empirical and expected complexity of the fixed class, for every admissible marginal. Corollary 13 (Agnostic and realizable guarantees). For any 𝜂 > 0, there exists a measurable 𝜂-approximate empirical risk minimizer ℎb ∈ H . For every 𝛿 ∈ (0, 1), with probability at least 1 − 𝛿 over 𝑆 ∼ 𝐷𝑚 it satisfies √︂ b − inf L𝐷 (ℎ) ≤ 4𝐿𝑈𝑚 + 2𝑏 ℓ log(2/𝛿) + 𝜂. L𝐷 (ℎ) (16) 2𝑚 ℎ∈ H If 𝑌 = ℎ★ (𝑋 ) almost surely for some ℎ★ ∈ H and ℓ (𝑦, 𝑦) = 0, then with probability at least 1 − 𝛿, √︂ b ≤ 2𝐿𝑈𝑚 + 𝑏 ℓ log(1/𝛿) + 𝜂. L𝐷 (ℎ) 2𝑚 These statements give statistical guarantees, without an efficient optimization claim.
(17)
Proof. The parameter space in (3) with the support-wide sparsity constraint is compact. Indeed, having at most 𝑘 strictly positive affine values at each fixed 𝑥 is a closed condition, and arbitrary intersections of these conditions remain closed in the bounded parameter box. The finitely many outer sign vectors preserve compactness. The parameter-to-function map is continuous in the uniform norm on X0 , since ∥𝑥 ∥ 2 ≤ 𝑅. Thus H is separable in that norm. Choose a fixed countable dense subclass. Lipschitz continuity of the loss makes its empirical and population infima agree with those of H . Selecting the first element of this subclass with empirical loss within 𝜂 of its countable infimum defines a measurable approximate ERM. This is an existence argument, not an effective search procedure. Symmetrization, scalar contraction, and bounded differences give, simultaneously for all ℎ ∈ H , the one-sided bound √︁ b𝑆 (ℎ) ≤ 2𝐿𝔼𝑆 ′ R H (𝑆 ′ ) + 𝑏 ℓ log(1/𝛿)/(2𝑚). L𝐷 (ℎ) − L Here 𝑆 ′ is an independent input sample. This is the expected-complexity form of the standard Rademacher generalization inequality (Bartlett and Mendelson, 2002; Mohri et al., 2018). The countable dense subclass justifies the suprema, and subtracting ℓ (0, 𝑌𝑖 ) before contraction does not change expected Rademacher complexity. Apply the same argument √︁ in the other direction and use a union bound to obtain uniform absolute deviation at most 2𝐿𝑈𝑚 + 𝑏 ℓ log(2/𝛿)/(2𝑚). The approximate ERM inequality then proves (16). b ≤ 𝜂 almost surely; the single one-sided event proves (17). b𝑆 (ℎ) In the realizable case, L □ 11
5.1
Agnostic minimax risk for a normalized bounded loss
We now fix one loss and match upper and lower bounds in the same statistical experiment. Suppose 𝐴 > 0, set 𝑔 = ⌊𝑠/𝑘⌋, and normalize the full-ball class as 𝑛
𝑊 ,𝐵 H = {ℎ/(𝑘 (𝐴 + 𝐵)) : ℎ ∈ H𝑛,𝑠,𝑘 (𝔹𝑛𝑅 )} ⊆ [−1, 1] 𝔹𝑅 .
For 𝑦 ∈ {−1, 1}, use the bounded linear loss ℓlin (𝑡, 𝑦) = 12 1 − 𝑦 clip(𝑡) ,
clip(𝑡) = max{−1, min{𝑡, 1}}.
It is 1/2-Lipschitz in 𝑡 and takes values in [0, 1]; replacing 𝑦 by clip(𝑦) extends it to all real labels. Let ! 𝔈𝑚 = inf sup 𝔼𝑆∼𝐷𝑚 L𝐷 ( 𝑓b) − inf L𝐷 (𝑓 ) , 𝑓b
𝑓 ∈H
𝐷
where 𝐷 ranges over all Borel distributions on 𝔹𝑛𝑅 × {−1, 1}. The infimum allows measurable, randomized and improper learning rules; their internal randomness is included in the expectation. The rule receives the sample, not the unknown distribution. No computation restriction is imposed. Theorem 14 (Agnostic minimax rate). Suppose 𝐴 > 0, 𝜏𝐴 ≤ 𝐵 ≤ 𝐴, and 𝑛 ≥ 𝑑𝑔 , where 𝜏, 𝑑𝑔 are defined in Section 4. There are universal constants 𝑐 1, 𝐶 1 > 0 such that, for all 𝑚 ≥ 1, √︁ √︁ 𝑐 1 min{1, 𝑠/(𝑘𝑚)} ≤ 𝔈𝑚 ≤ 𝐶 1 min{1, 𝑠/(𝑘𝑚) log3/2 (2𝑚)}. (18) The upper bound follows from approximate empirical risk minimization in the normalized class. For the lower bound, the spherical-cap construction realizes all independent signs on 𝑞 = min{𝑔, 𝑚} inputs with a constant normalized amplitude. Give the labels small, unknown signed means on those inputs. Adjacent sign choices have small joint-sample divergence, so no learning rule can reliably recover their correlations. Appendix B makes this testing argument explicit, including improper and randomized rules. 2 )) for sufficiently e For this loss and model, (18) yields an expected-excess-risk sample-size order Θ(𝑠/(𝑘𝜀 small 𝜀. The ratio 𝑠/𝑘 reflects the explicit output normalization by 𝑘 (𝐴 + 𝐵); it is not an unnormalized improvement from 𝑠𝑘 to 𝑠/𝑘. The theorem is loss-specific and agnostic. It does not establish a matching lower bound for the realizable guarantee above or for every bounded Lipschitz loss.
6
Scope and remaining questions
Activation sparsity does not by itself identify a globally small subnetwork. The full-ball comparison makes the distinction precise: zero thresholds force at most 2𝑘 nonzero units, whereas positive thresholds can isolate many independently signed caps, even in logarithmic dimension. Meanwhile, biases larger than the linear pre-activation range add only constants. These are different roles of thresholds, not conflicting statements about bias complexity. √︁ The logarithmic gap remains. Our affine cover contributes log(2𝑚), and summing the entropy bound over scales contributes another logarithm. The finite union over activation counts has only a lower-order cost. Removing that union cost alone cannot prove the logarithm-free conjecture. A direct process estimate, or an analysis retaining the simultaneous feasibility of all neuron configurations, may avoid losses introduced by the present relaxation. The domain results leave a more geometric question: how does complexity √ interpolate between the zero-bias collapse and the full-ball cap construction? The sufficient value 𝐵 = ( 3/2)𝑊 𝑅 is not shown to be 12
a critical threshold. The constants in the spherical-code dimension estimate are not sharp. Understanding small positive thresholds and fixed low dimension would explain more than improving a universal upper bound alone. Finally, the agnostic minimax characterization concerns one explicitly normalized bounded loss and comparable bias and weight scales. It does not settle realizable learning or every loss function. All classes here impose sparsity on a fixed input domain before data are drawn; observed training-set sparsity is not a substitute for that promise. Distribution-dependent sparsity and multilayer extensions require additional arguments.
References Pranjal Awasthi, Nishanth Dikkala, Pritish Kamath, and Raghu Meka. Learning neural networks with sparse activations. In Proceedings of the 37th Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 406–425. PMLR, 2024. URL https://proceedings.mlr.press/v247/awasthi24a.html. Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463–482, 2002. URL https://www.jmlr.org/papers/v3/bar tlett02a.html. Richard M. Dudley. The sizes of compact subsets of Hilbert space and continuity of Gaussian processes. Journal of Functional Analysis, 1(3):290–330, 1967. doi: 10.1016/0022-1236(67)90017-1. Tomer Galanti, Mengjia Xu, Liane Galanti, and Tomaso Poggio. Norm-based generalization bounds for sparse neural networks. In Advances in Neural Information Processing Systems, volume 36, pages 42482– 42501. Curran Associates, Inc., 2023. doi: 10.52202/075280-1843. URL https://proceedings.neurips.cc/p aper_files/paper/2023/hash/8493e190ff1bbe3837eca821190b61ff-Abstract-Conference.html. Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Proceedings of the 31st Conference on Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 297–299. PMLR, 2018. URL https://proceedings.mlr.press/v75/golowich18a.html. Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: Isoperimetry and Processes, volume 23 of Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer-Verlag, 1991. Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, second edition, 2018. Ramchandran Muthukumar and Jeremias Sulam. Sparsity-aware generalization theory for deep neural networks. In Proceedings of the 36th Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 5311–5342. PMLR, 2023. URL https://proceedings.mlr.press/v195/muthukumar2 3a.html. Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Proceedings of the 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 1376–1401. PMLR, 2015. URL https://proceedings.mlr.press/v40/Neyshabur15.html. Alain Pajor and Nicole Tomczak-Jaegermann. Subspaces of small codimension of finite-dimensional Banach spaces. Proceedings of the American Mathematical Society, 97(4):637–642, 1986. doi: 10.1090/S0002-9939-1 986-0845980-8. 13
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, 2009. doi: 10.1007/b13794. Tong Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2:527–550, 2002. URL https://www.jmlr.org/papers/v2/zhang02b.html.
14
A
The affine covering estimate
We give the finite-dimensional argument underlying (5). It is the usual Gaussian packing proof of dual Sudakov (Pajor and Tomczak-Jaegermann, 1986; Ledoux and Talagrand, 1991), specialized to the sample norm. Lemma 15 (Samplewise affine covering). For every radius-𝑅 sample, every 𝑊 , 𝐵 ≥ 0, and every 𝛿 > 0, the affine evaluation class satisfies (5). Proof. We first establish the linear bound. Let 𝑉 = span{𝑥 1, . . . , 𝑥𝑚 }, 𝑝 (𝑣) = max𝑖 |⟨𝑣, 𝑥𝑖 ⟩|, and 𝐿𝑋 = max𝑖 ∥𝑥𝑖 ∥ 2 . Orthogonal projection onto 𝑉 preserves the sample evaluations and decreases the Euclidean norm. If 𝑊 = 0 or 𝐿𝑋 = 0, the linear class is a singleton. Otherwise 𝑝 is a norm on 𝑉 . Let 𝐺 be a standard Gaussian in 𝑉 , 𝑎 = 𝔼𝑝 (𝐺) > 0, and 𝐾 = {𝑣 : 𝑝 (𝑣) ≤ 1}. For any centrally symmetric Borel set 𝐾 ′ and 𝑧 ∈ 𝑉 , Gaussian density integration gives ∫ 2 ′ − ∥𝑧 ∥ 22 /2 𝛾 (𝐾 + 𝑧) = 𝑒 𝑒 −⟨𝑧,𝑦⟩ 𝑑𝛾 (𝑦) ≥ 𝑒 − ∥𝑧 ∥ 2 /2𝛾 (𝐾 ′ ). (19) 𝐾′
Indeed, by symmetry the integral equals that of cosh(⟨𝑧, 𝑦⟩), which is at least 𝛾 (𝐾 ′ ). This argument applies in the Euclidean space 𝑉 with its own Gaussian density. Fix a covering radius 𝑟 > 0. Choose a maximal finite collection 𝑣 1, . . . , 𝑣 𝑁 ∈ 𝑊 𝐵 2 (𝑉 ) with pairwise 𝑝-distance strictly larger than 𝑟 . Such a collection exists because the ball is compact. Its closed 𝑟 -balls cover the ball, and the sets 𝑣 𝑗 + (𝑟 /2)𝐾 are disjoint. Put 𝜆 = 4𝑎/𝑟 . The dilated sets remain disjoint, and Markov’s inequality gives 𝛾 ((𝜆𝑟 /2)𝐾) = ℙ[𝑝 (𝐺) ≤ 2𝑎] ≥ 1/2. Using (19) and ∥𝑣 𝑗 ∥ 2 ≤ 𝑊 , 1≥
𝑁 ∑︁
𝛾 (𝜆𝑣 𝑗 + (𝜆𝑟 /2)𝐾) ≥
𝑗=1
𝑁 −𝜆2𝑊 2 /2 𝑒 . 2
It follows that log 𝑁 ≤ log 2 + 8𝑊 2𝑎 2 /𝑟 2 . If 𝑟 ≥ 𝑊 𝐿𝑋 , the single center 0 suffices instead. Otherwise, √︁ 𝑎 ≥ 2/𝜋 𝐿𝑋 , by choosing an input attaining 𝐿𝑋 and taking the expected absolute value of its Gaussian projection. Hence log 2 ≤ (𝜋 log 2/2)𝑊 2𝑎 2 /𝑟 2 , and in both cases log 𝑁 (𝑊 𝐵 2 (𝑉 ), 𝑟, 𝑝) ≤ 10𝑊 2𝑎 2 /𝑟 2 .
(20)
2 Each of the 2𝑚 Gaussian √︁ variables ±⟨𝐺, 𝑥𝑖 ⟩ has variance at most 𝑅 . The exponential-moment maximal inequality gives 𝑎 ≤ 𝑅 2 log(2𝑚). Setting 𝑟 = 𝛿/2 in (20) bounds the logarithm of the linear covering number by 80𝐴2 log(2𝑚)/𝛿 2 . Finally, a grid at spacing 𝛿/2, starting at −𝐵 and ending at the last such grid point not exceeding 𝐵, covers [−𝐵, 𝐵] at radius 𝛿/2 using at most ⌊4𝐵/𝛿⌋ + 1 points. Adding this grid to the linear cover makes a 𝛿-cover of affine evaluations. Cardinalities multiply, proving (5). □
Measurability and zero scales. For each fixed sample and 𝑡, the set of (𝑣, 𝛽) with at most 𝑡 positive sample pre-activations is closed in the compact parameter box: the violating set is the finite union of conditions under which 𝑡 + 1 specified coordinates are strictly positive. Its continuous image F𝑡 is compact and contains zero. The normalized union 𝑇 in Section 2 is a finite union of compact sets. Its suprema are finite; the sign probability space is itself finite. The proof handles 𝑀 = 0 before invoking a positive covering radius and chooses at least one chaining level even when 𝑚 = 1.
B
Proof of the agnostic minimax bound
We prove Theorem 14 for its normalized class and bounded linear loss. 15
Upper bound. Use a measurable 𝜂-approximate empirical risk minimizer in H , whose existence follows from the compactness argument for Corollary 13. The class is symmetric and contains zero. On its prediction range, ℓlin (𝑓 (𝑥), 𝑦) − 1/2 = −𝑦 𝑓 (𝑥)/2. Symmetrization and sign symmetry therefore give 𝑈𝑚 . 𝑘 (𝐴 + 𝐵)
b𝑆 (𝑓 )| ≤ 𝔼𝑆 ′ R (𝑆 ′ ) ≤ 𝔼 sup |L𝐷 (𝑓 ) − L H 𝑓 ∈H
Multiplying the Rademacher signs by the labels preserves their conditional law; the loss’s factor 1/2 cancels the symmetrization factor 2. Approximate ERM thus has expected excess risk at most 2𝑈𝑚 /(𝑘 (𝐴 + 𝐵)) + 𝜂, uniformly in 𝐷. Using (15), 𝑠 ≥ 𝑘, and 𝜌𝑚 ≤ 𝑚 −1/2 , and taking the better of this bound and the trivial bound 1, proves the upper inequality in (18). Letting 𝜂 ↓ 0 is legitimate in the infimum over learning rules; no exact measurable minimizer is needed. Lower bound: one fixed family before sampling. Put 𝑞 = min{𝑔, 𝑚}. Since 𝑑𝑞 ≤ 𝑑𝑔 , choose 𝑞 cap directions as in Theorem 12. Its construction with 𝑎 = 𝐴 yields functions 𝑓𝜃 ∈ H such that 𝑓𝜃 (𝑅𝑢𝑏 ) = 𝛼𝜃𝑏 ,
𝜃 ∈ {−1, 1}𝑞 ,
𝛼=
(1 − 𝜏)𝐴 1 − 𝜏 ≥ . 𝐴+𝐵 2
√︁ Set 𝛿 0 = (𝛼/4) 𝑞/𝑚 ≤ 1/4. For each fixed 𝜃 , define 𝐷𝜃 by drawing 𝑋 uniformly from the cap centers and setting 1 + 𝛿 0𝜃 𝑏 ℙ𝜃 [𝑌 = 1 | 𝑋 = 𝑅𝑢𝑏 ] = . 2 This family is fixed before sampling. Let 𝑃𝜃 = 𝐷𝜃𝑚 , and let 𝜃 (𝑏 ) flip coordinate 𝑏. The common input marginal gives 𝑚 1 + 𝛿0 𝛿 0 log 𝑞 1 − 𝛿0 2 4𝑚𝛿 0 ≤ . 𝑞
KL(𝑃𝜃 ∥𝑃𝜃 (𝑏) ) =
Here log((1 +𝑡)/(1 −𝑡)) ≤ 4𝑡 for 0 ≤ 𝑡 ≤ 1/2, for example by integrating 2/(1 −𝑡 2 ) ≤ 4. Pinsker’s inequality implies √︁ 𝛼 𝛼 TV(𝑃𝜃 , 𝑃𝜃 (𝑏) ) ≤ 𝛿 0 2𝑚/𝑞 = √ ≤ . 2 2 2 Fix any learning rule, including an improper or randomized one, and write 𝑇𝑏 = clip( 𝑓b(𝑅𝑢𝑏 )) ∈ [−1, 1]. Averaging over adjacent pairs and using the bounded-observable characterization of total variation, ∑︁ 𝛼 2−𝑞 𝜃𝑏 𝔼𝜃 𝑇𝑏 ≤ . 2 𝜃
For deterministic rules, pair each 𝜃 with 𝜃𝑏 = 1 with its flipped neighbor and use (𝔼𝜃 𝑇𝑏 − 𝔼𝜃 (𝑏) 𝑇𝑏 )/2 ≤ TV(𝑃𝜃 , 𝑃𝜃 (𝑏) ). Randomized post-processing cannot increase total variation, so the same inequality applies. The comparator 𝑓𝜃 has risk 1/2 − 𝛿 0𝛼/2. Thus the average, over this fixed family, of the learning rule’s expected excess risk is at least ! 𝑞 ∑︁ 𝛿 0𝛼 𝛿 0 ∑︁ −𝑞 ∑︁ −𝑞 2 𝔼𝜃 L𝐷𝜃 ( 𝑓b) − inf L𝐷𝜃 (𝑓 ) ≥ − 2 𝜃𝑏 𝔼𝜃 𝑇𝑏 2 2𝑞 𝑓 ∈H 𝜃
𝑏=1
𝛿 0𝛼 𝛼 2 √︁ ≥ = 𝑞/𝑚. 4 16 16
𝜃
A supremum over√𝐷 is at least this average. Finally, 𝑞 ≥ 21 min{𝑠/𝑘, 𝑚} and 𝛼 ≥ (1 − 𝜏)/2, so one may take 𝑐 1 = (1 − 𝜏) 2 /(64 2). This Assouad-type argument (Tsybakov, 2009, Chapter 2) directly bounds excess risk for the full-ball class, rather than converting a complexity lower bound.
AI Disclosure The original manuscript, including its activation-budget reduction and margin-shifted covering argument, was written by the authors. During subsequent revisions, we used OpenAI Codex, including GPT-5.6 Solar and GPT-6 Astra, to assist with proof checking, mathematical revisions, literature lookup, and exposition. Specifically, the AI-assisted revisions replaced the per-scale concentration and dyadic peeling steps with a single chaining argument over the union of normalized single-neuron classes (Section 2); introduced the threshold-clipping decomposition that isolates the constant contribution and removes the width and logarithmic factors from the bias term (Lemma 8); extended the clustered lower-bound construction to i.i.d. samples without divisibility assumptions (Theorem 3); added the zero-bias width-collapse result and the disjoint-cap lower bound on the entire ball in logarithmic dimension (Section 4); and reformulated the learning lower bound as an Assouad-type argument for the normalized class under a specified bounded linear loss, so that the learning upper and lower bounds concern the same statistical model (Theorem 14). AI tools also assisted with edge-case checks, finite-instance verification scripts, and expansion of the technique overview. We take full responsibility for all content in the final manuscript, including AI-assisted material, and for its correctness, originality, attribution, and citations.
17