Sharp Covering-Number Bounds for Feedforward ReLU Networks via Parameter Symmetries

Ruizhi Deng, Guohao Shen, Tangrui XiongarXiv 2026 · arXiv

TL;DR

This paper provides the first "sharp" (mathematically tight) theoretical bounds on the functional complexity of ReLU neural networks by accounting for their inherent parameter symmetries. By formally "quotienting out" the redundancies caused by neuron permutations and positive weight scaling, the authors prove that a network's true complexity is significantly lower than its raw parameter count suggests, leading to tighter statistical guarantees for deep learning.

What Problem Does This Paper Address?

In deep learning, we often talk about "overparameterization"—the fact that modern models have far more parameters ($S$) than training data points. However, the raw number of parameters is a deceptive measure of a model's actual capacity. Because of the way neural networks are structured, many different parameter configurations can represent the exact same mathematical function.

For example, in a ReLU network, you can swap two neurons in a hidden layer (permutation) or scale up the incoming weights of a neuron while scaling down its outgoing weights (scaling) without changing the output. Standard statistical learning theory often ignores these redundancies, leading to "loose" complexity bounds that don't fully explain why these massive models generalize so well. This paper seeks to close that gap by providing a precise, "sharp" count of a network's functional degrees of freedom.

Methods

The authors tackle this using a three-pronged theoretical approach:

  1. Unified Architecture: They define a "unified block network" that encompasses Multi-Layer Perceptrons (MLPs), Convolutional Neural Networks (CNNs), and Residual Networks (ResNets). This allows them to prove results that apply to almost all standard feedforward architectures.
  2. Symmetry Characterization: They prove a "completeness" result: for ReLU and Leaky ReLU networks, positive channel scaling and channel permutation are the only smooth (quasianalytic) ways to change parameters while keeping the function identical.
  3. Quotienting the Parameter Space: To find the "covering number"—a measure of how many "balls" of a certain radius it takes to cover the space of all possible functions the network can represent—they mathematically collapse all equivalent parameter settings into single points.
A residual block; the identity shortcut adds the input h after the second activation.

As shown in Figure 1, even complex structures like residual blocks have internal symmetries (in the "inner layer") that can be exploited to reduce complexity.

Datasets

Not discussed in the paper. As a theoretical work in statistical learning theory, the authors focus on proving universal mathematical properties rather than benchmarking on specific datasets like ImageNet or CIFAR-10.

Key Insights and Ideas

  • The Exponent Reduction ($S \to S-H$): The most significant "aha" moment is that continuous scaling symmetry doesn't just reduce the size of the function space; it actually reduces the dimensionality (the exponent) of the complexity bound. Specifically, the exponent drops from the total parameter count $S$ to $S-H$, where $H$ is the number of scalable hidden channels.
  • The Factorial Divisor ($G$): Permutation symmetry provides a discrete reduction. If a layer has $d$ neurons, there are $d!$ ways to arrange them. The authors show the total complexity is divided by the product of these factorials ($G$) across all layers.
  • Sharpness: The authors didn't just find an upper bound; they proved a matching lower bound. This confirms that their formula is "sharp"—it is the best possible theoretical description of ReLU network complexity under these conditions.
  • Symmetry as a Regularizer: The results suggest that the "flat directions" often observed in the loss landscapes of neural networks are a direct consequence of these symmetries. Optimization doesn't need to "find" a specific point; it just needs to find any point on a "scaling fiber" or "permutation orbit."

Key Results

The paper establishes a new state-of-the-art for covering-number bounds, summarized in the comparison table below:

Table 1: Comparison of ε-covering number bounds N(F, ε, ∥· ∥) for neural networks.
  • Quantitative Bound: The uniform covering number $N$ is bounded by $(C_+/G)\epsilon^{-(S-H)}$.
  • Impact of Scaling: In a shallow network with 128 neurons, the exponent reduction from $S$ to $S-H$ can reduce the complexity measure by a factor of $10^{-256}$ at a typical precision level ($\epsilon = 10^{-2}$).
  • Statistical Risk: These bounds translate directly into better "excess risk" guarantees. The authors show that for Gaussian regression, the dependence of the error on the model size is governed by $S-H$ rather than $S$, providing a more optimistic (and accurate) view of model generalization.

Limitations and Future Work

  • Generic Identifiability: While the $S-H$ exponent reduction is universal, the $1/G$ factorial divisor is strictly proven for one-hidden-layer networks and "generically identifiable" deep networks. Proving this divisor holds for all deep architectures remains an open challenge.
  • Data-Dependent Symmetries: The current work looks at "global" equivalence (functions that are identical for all possible inputs). In practice, two different networks might produce identical outputs only on the specific training data points. Capturing these "data-dependent" symmetries could lead to even tighter bounds.
  • Beyond ReLU: The authors suggest extending this "volume-packing" framework to architectures with normalization layers (like BatchNorm) or self-attention mechanisms (Transformers), where more complex rotational and projective symmetries exist.

Summary updated

Abstract

In neural networks, distinct parameter configurations often realize the same input--output mapping, indicating that nominal parameter counts can overstate functional complexity. In this paper, we characterize the parameter-space symmetries of ReLU and Leaky ReLU networks across fully connected, convolutional, and residual architectures. We prove that every quasianalytic parameter map preserving the network function is a composition of positive channel scaling and channel permutation. By quotienting out both symmetries, we derive uniform covering-number upper bounds in which positive scaling reduces the complexity exponent from the total parameter count $S$ to $S-H$ (with $H$ denoting the number of scalable channels) and permutation symmetry divides the bound by the factorial count $G$ of channel permutations. We establish matching lower bounds showing that the exponent $S-H$ is sharp in general and that the divisor $G$ is attained for one-hidden-layer and generically identifiable networks. We further extend these results to general continuous piecewise-linear activated networks. Finally, we apply our covering-number bounds to derive statistical risk guarantees for empirical risk minimization and capacity control beyond i.i.d.\ settings, and show how the underlying symmetries help explain weight rebalancing in function approximation and flat directions in empirical risk optimization.
BibTeX
@misc{deng2026sharp,
  author = {Ruizhi Deng and Guohao Shen and Tangrui Xiong},
  title = {{Sharp Covering-Number Bounds for Feedforward ReLU Networks via Parameter Symmetries}},
  year = {2026},
  eprint = {2611.15300},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.15300},
}

Loading related content...

Figure