Nearly Tight Rademacher Bounds for Input-Dependent Sparsity

Paper: 2609.09130 Authors: Xiaoyu Li, Zhizhou Sha, Jiaojiao Jiang, Junbin Gao, Andi Han Categories: cs.LG, stat.ML

The Gap

A neural network’s capacity is usually discussed in terms of its width, but the capacity that matters for a particular input is smaller: an input may activate few hidden units even when different inputs collectively use an entire network. A very wide network can behave, per-example, like a much narrower one.

That observation is intuitive and it has a statistical consequence — if the effective network is narrow, generalisation guarantees ought to be able to say so. But the classical complexity measures are computed over the whole architecture, so they cannot express input-dependent sparsity, and a bound that ignores the phenomenon will be loose exactly in the regime people care about: wide models with sparse activation.

   CAPACITY VERSUS EFFECTIVE CAPACITY

   capacity is usually discussed in terms of WIDTH
   but the capacity that matters for a PARTICULAR INPUT is smaller:
     AN INPUT MAY ACTIVATE FEW HIDDEN UNITS even when different
     inputs COLLECTIVELY use an ENTIRE network
        |
        v
   -> a very WIDE network can behave, PER-EXAMPLE, like a
      much NARROWER one
        |
        v
   [THE STATISTICAL CONSEQUENCE]
     if the EFFECTIVE network is narrow, generalisation guarantees
     ought to be able to say so
        |
        v
   BUT classical complexity measures are computed over the WHOLE
   architecture
     -> they CANNOT express input-dependent sparsity
     -> a bound that ignores the phenomenon is LOOSE EXACTLY in
        the regime people care about: WIDE MODELS WITH SPARSE
        ACTIVATION

The Increment

One sentence: Before this paper, Rademacher complexity for sparsely activated networks carried an explicit dimension factor; after it, a support-preserving cover removes that factor up to logarithms, matching lower bounds confirm a width dependence remains, and the input domain turns out to change the answer qualitatively.

Core Mechanism

The setting is the one-hidden-layer ReLU model of Awasthi et al. (COLT 2024), with parameters stated precisely: width s, at most k active units per input, and effective weight and bias bounds W and B. Fixing these makes the question exact rather than qualitative.

The main upper bound: every size-m sample in the class’s fixed radius-R input domain satisfies

   R(S)  <=  C W R  min{ k , sqrt(sk/m) log^{3/2}(2m) }  +  k B / sqrt(m)

The structure of that bound is the finding. The min is doing the interesting work: the complexity is the smaller of k — the number of active units, a constant with respect to sample size — and a term that decays as 1/sqrt(m) while depending on sqrt(s). So as the sample grows, the complexity term stops being dominated by the raw count of active units and starts behaving like a decaying rate that still knows about the width. Neither factor alone would be right: a bound in k alone would be constant in m, and a bound in s alone would ignore that few units are active.

Two techniques produce this: a support-preserving cover and a single normalized chaining argument, which together remove the previous explicit dimension factor, up to logarithms. “Support-preserving” and “single” are the operative words. The cover respects which units are active, so it does not pay for units that never fire. And a single chaining argument, rather than a chained sequence of them, is what avoids accumulating a dimension factor. Removing a leftover dimension factor is a meaningful improvement rather than a cosmetic one, because it is the difference between a bound that degrades with width and one that tracks the effective size.

Matching lower bounds on appropriate i.i.d. marginals agree up to those logarithms, and the lower bounds show that changing active units across inputs retains a width dependence. So the sqrt(s) in the upper bound is not slack: it is the price of the units that different inputs use at different times. The upper and lower bounds close the question, which is what “nearly tight” asserts.

Then the input domain, which turns out to matter more than one might expect. Zero-bias networks that are sparse on the entire ball have at most 2k nonzero units and complexity O(kWR/sqrt(m)) — a clean decaying rate with no width term at all. But bias bounds comparable to WR restore the worst-case rate on that same domain in only logarithmic dimension. So the favourable answer is not a property of sparsity alone: it requires the bias regime to cooperate. And the claim is proved by a spherical-cap construction that does not assume sparsity merely on the sampling support — closing the loophole where a guarantee holds only for the specific inputs drawn.

Finally, for a specified normalized bounded loss and biases comparable to WR, the paper obtains agnostic minimax excess-risk bounds of order min{1, sqrt(s/(km))} up to logarithms — an excess-risk form that a learning-theory reader can compare directly with standard rates.

   SETTING: the one-hidden-layer ReLU model of Awasthi et al. (2024)
     WIDTH s | at most k ACTIVE UNITS PER INPUT
     effective WEIGHT and BIAS bounds W and B

   [THE MAIN UPPER BOUND] for every size-m sample in the class's
   fixed radius-R input domain:

     R(S)  <=  C W R  min{ k , sqrt(sk/m) log^{3/2}(2m) }  +  k B / sqrt(m)

   THE STRUCTURE OF THE BOUND IS THE FINDING
     the MIN is doing the interesting work: complexity is the
     SMALLER of
       k                    -- the ACTIVE UNIT COUNT, CONSTANT in m
       sqrt(sk/m) log(...)   -- DECAYS as 1/sqrt(m) while still
                                depending on sqrt(s)
     -> as the sample grows, complexity stops being dominated by the
        RAW COUNT of active units and starts behaving like a
        DECAYING RATE THAT STILL KNOWS ABOUT THE WIDTH
     <- a bound in k alone would be CONSTANT in m
     <- a bound in s alone would IGNORE that few units are active

   TWO TECHNIQUES PRODUCE IT
     a SUPPORT-PRESERVING cover
       <- respects WHICH UNITS ARE ACTIVE: does not pay for units
          that never fire
     + a SINGLE normalized chaining argument
       <- SINGLE rather than a chained sequence of them is what
          avoids ACCUMULATING A DIMENSION FACTOR
     -> removes the previous EXPLICIT DIMENSION FACTOR, up to logs
     <- a meaningful improvement: the difference between a bound that
        DEGRADES WITH WIDTH and one that TRACKS THE EFFECTIVE SIZE

   MATCHING LOWER BOUNDS on appropriate i.i.d. marginals agree up to
   those logarithms
     -> CHANGING ACTIVE UNITS ACROSS INPUTS RETAINS A WIDTH DEPENDENCE
     <- so the sqrt(s) is NOT slack: it is the price of the units that
        different inputs use at different times
     -> upper and lower bounds CLOSE the question: "NEARLY TIGHT"

   THE INPUT DOMAIN MATTERS MORE THAN ONE MIGHT EXPECT
     ZERO-BIAS networks sparse on the ENTIRE BALL:
       at most 2k NONZERO units, complexity O(kWR/sqrt(m))
       -- a clean decaying rate with NO WIDTH TERM at all
     BUT bias bounds comparable to WR RESTORE THE WORST-CASE RATE on
       that same domain IN ONLY LOGARITHMIC DIMENSION
       -> the favourable answer is NOT a property of sparsity alone:
          the BIAS REGIME must cooperate
     proved by a SPHERICAL-CAP construction that does NOT assume
       sparsity merely on the SAMPLING SUPPORT
       <- closes the loophole where a guarantee holds only for the
          specific inputs drawn

   FINALLY: for a specified normalized bounded loss and biases
   comparable to WR, AGNOSTIC MINIMAX EXCESS-RISK bounds of order
     min{ 1, sqrt( s / (k m) ) }   up to logarithms
     -> an excess-risk form a learning-theory reader can compare
        directly with standard rates

Think of it as the difference between a warehouse’s total floor area and the space one order occupies. A million-square-metre warehouse holds a lot in principle, but if any given order only ever touches a hundred shelves, then what determines how well you can learn to fill orders is those hundred shelves — plus, crucially, how many different shelves the orders collectively touch. That second term is why a width dependence survives: if different orders use different shelves, some penalty for the warehouse’s size is real. And the result about zero bias is a caution: “orders only touch a few shelves” being true in general does not help if it is only true on average for the orders you happened to sample — which is exactly what the spherical-cap construction rules out by not assuming sparsity merely on the sampling support.

Key Concepts

• Input-dependent sparsity as the object of study: at most k active units per input, however wide the network. It is the regime where classical architecture-level complexity measures are loose.
• The min{k, sqrt(sk/m)} structure: complexity is the smaller of a constant in sample size and a decaying rate that retains width dependence. Neither term alone would be correct, and the crossover is the substantive content.
• Removing an explicit dimension factor: a support-preserving cover plus a single chaining argument. A single chain, rather than a sequence of them, is what avoids accumulating the factor.
• Width dependence as a genuine price: matching lower bounds under randomly drawn marginals. It shows the sqrt(s) reflects the cost of inputs using different units, not slack in the proof.
• Bias regime and domain: zero-bias sparse networks on the ball get a width-free rate, but biases comparable to WR restore the worst-case rate. It makes the favourable result conditional on more than sparsity.
• Excess-risk form: min{1, sqrt(s/(km))} for a specified loss and bias regime. It is the form that permits direct comparison with standard rates.

Framework Shift

Before (architecture-level complexity):
  measure complexity over the whole network
  -> the explicit dimension factor persists
  -> bounds are loose in the wide-and-sparsely-activated regime
  -> input-dependent sparsity is not expressible

After (support-aware complexity, nearly tight):
  support-preserving cover + single normalized chaining
  -> R(S) <= CWR min{k, sqrt(sk/m) log^{3/2}(2m)} + kB/sqrt(m)
  -> matching lower bounds retain a width dependence
  -> zero-bias on the ball: O(kWR/sqrt(m)), no width term
     but biases ~ WR restore the worst-case rate
  -> excess risk of order min{1, sqrt(s/(km))}

From measuring a network’s complexity by its architecture, to measuring it by which units an input actually uses, the core shift is that the guarantee becomes tight in the wide-but-sparse regime — at the cost of making the answer depend on the bias regime and the input domain.

Expert Assessment

Problem choice: Excellent, and it takes on the regime where classical bounds are least informative. Wide models with sparse activation are what practitioners actually train, and a complexity measure that cannot express per-input sparsity is measuring the wrong object.

Method maturity: The result is nearly tight, which is the strongest position a complexity bound can occupy — the upper bound is not merely an improvement but is matched, so the width dependence is characterised rather than unexplained. Removing an explicit dimension factor via a support-preserving cover and a single chaining argument is a technical improvement with a clear reason, and the paper states that reason. The treatment of the input domain is the most valuable part: showing that zero-bias sparsity on the ball gives a width-free rate while biases comparable to WR restore the worst case turns a clean result into a conditional one, which is more honest and more useful.

Experimental integrity: This is a theory paper, so the scrutiny falls on assumptions and on whether tightness is genuine. The setting is explicit — one hidden layer, ReLU, at most k active units, specified weight and bias bounds, a fixed input domain — and the paper is clear that the results are for that class. The spherical-cap construction is a notable methodological point, because proving the claim without assuming sparsity merely on the sampling support is what prevents the guarantee from being an artefact of the drawn sample. The open question is depth: multi-layer behaviour, where sparsity interacts across layers, is outside the stated setting.

Writing quality: The bound is written out rather than gestured at, which is what makes a tightness claim checkable, and the identification of which term does what inside the min is the kind of commentary that saves a reader an hour. Because the input-domain result is the counterintuitive part, a short paragraph on the intuition for why biases comparable to WR reintroduce the worst case would repay its space.

Verdict: strong accept — it makes an input-dependent sparsity bound nearly tight, removes a spurious dimension factor with a technique whose reason is stated, and shows the favourable rate is conditional on the bias regime rather than on sparsity alone.

Takeaways

• Measure the capacity an input uses, not the capacity the architecture has. A wide network with few active units per example is a narrower object statistically.
• Check whether a favourable rate is conditional. Here the width-free rate requires a zero-bias regime; biases comparable to WR bring the worst case back.
• Do not assume sparsity on the sampling support. Proving a claim without that assumption is what distinguishes a property of the class from an artefact of the draw.
• Read min terms as crossover statements. When a bound is the smaller of a constant and a decaying rate, the interesting content is where they cross and what each depends on.