Sharp Covering-Number Bounds for Feedforward ReLU Networks via Parameter Symmetries
Organizations: Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong
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 to (with denoting the number of scalable channels) and permutation symmetry divides the bound by the factorial count of channel permutations. We establish matching lower bounds showing that the exponent is sharp in general and that the divisor 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.
Figures & tables
| Reference | Architectures | Norm | Upper bound | Lower bound |
|---|---|---|---|---|
| Bartlett et al. (2017) | MLP (no bias) | – | ||
| Lin and Zhang (2019) | MLP, CNN (no bias) | – | ||
| Bartlett et al. (2019) | MLP, CNN, ResNet | – | ||
| Long and Sedghi (2020) | MLP, CNN (no bias) | – | ||
| Shen (2024) | MLP | – | ||
| Ou and Bölcskei (2026) | MLP |
ReLU Neural Networks
Rectified linear unit (ReLU) neural networks use piecewise-linear activations to study approximation, learning dynamics, expressivity, and verification.
See all 133 papers