Sharp Covering-Number Bounds for Feedforward ReLU Networks via Parameter Symmetries
Ruizhi Deng, Guohao Shen, Tangrui Xiong
原文摘要
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.
cs.LG · math.ST · stat.ML