cs.LGNov 11, 2026

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

Authors: Ruizhi Deng, Guohao Shen, Tangrui Xiong

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 SS to S−HS-H (with HH denoting the number of scalable channels) and permutation symmetry divides the bound by the factorial count GG of channel permutations. We establish matching lower bounds showing that the exponent S−HS-H is sharp in general and that the divisor GG 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

Explore similar work

May 5, 2026

Most ReLU Networks Admit Identifiable Parameters

We study the realization map of deep ReLU networks, focusing on when a function determines its parameters up to scaling and permutation. To analyze hidden redundancies beyond these standard symmetries, we introduce a framework based on weighted polyhedral complexes. Our main result shows that for every architecture whose input and hidden layers have width at least two, there exists an open set of identifiable parameters. This implies that the functional dimension of every such architecture is exactly the number of parameters minus the number of hidden neurons. We further show that minimal functional representations can still have non-trivial parameter redundancies. Finally, we establish a generic depth hierarchy, whereby for an open set of parameters the realized function cannot be represented generically by any shallower network.
Apr 15, 2026

A Complete Symmetry Classification of Shallow ReLU Networks

Parameter space is not function space for neural network architectures. This fact, investigated as early as the 1990s under terms such as reverse engineering," or parameter identifiability", has led to the natural question of parameter space symmetries\textemdash the study of distinct parameters in neural architectures which realize the same function. Indeed, the quotient space obtained by identifying parameters giving rise to the same function, called the neuromanifold, has been shown in some cases to have rich geometric properties, impacting optimization dynamics. Thus far, techniques towards complete classifications have required the analyticity of the activation function, notably excising the important case of ReLU. Here, in contrast, we exploit the non-differentiability of the ReLU activation to provide a complete classification of the symmetries in the shallow case.
May 18, 2026

The Symmetries of Three-Layer ReLU Networks

We develop a framework for analyzing parameter symmetries in deep ReLU networks and obtain a complete characterization of the generic parameter fibers for three-layer bottleneck architectures. Our approach provides explicit semi-algebraic descriptions of these fibers and yields a polynomial time algorithm for deciding functional equivalence of two parameters. The symmetries include discrete and continuous transformations arising from layer composition, and depend on whether deeper layers hide or preserve geometric structure from preceding layers. Finally, we show that some of these symmetries induce local conservation laws along gradient flow, while others do not.