Research map / Learning theory and algorithms / Kernels and regression theory
Exploring the Complexity of Deep Neural Networks through Functional Equivalence
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Uses permutation (functional) equivalence of feedforward networks to shrink the parameter space by factorials of widths, yielding tighter covering-number bounds that hold with biases and general activations, and argues this eases optimization.
Problem
Existing covering-number bounds for deep neural networks ignore parameter redundancy from functional equivalence, do not handle bias vectors, and depend on spectral norms; the paper asks how functional equivalence changes complexity and optimization of overparameterized networks.
Approach
Exploits permutation invariance of hidden neurons to restrict parameters to a canonical representative set (sorted biases), reducing volume by d_l! per layer and giving covering number bounds reduced by factorials of layer widths, explicit in width, depth, size and infinity-norm bound, valid with biases and general activations.
Key results
- Covering number of shallow networks reduced by a factor d_1! relative to prior bounds, and deep networks by d_1!...d_L!, both holding with bias vectors.
- For a shallow ReLU network with d_1=128, the factorial reduction 128! ≈ 10^215 exceeds the estimated atom count of the universe (~10^82).
- Volume of the effective parameter space scales as (2B)^S/(d_1!...d_L!), so widening the network shrinks it toward zero, offered as an explanation for easier training of overparameterized networks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Account for permutation equivalence in the parameterization | Deep feedforward neural networks · Deep feedforward neural networks | covering number: approximately a factor of $(d_1!d_2!\cdots d_L!)$ | Helped |
| Account for permutation equivalence in the parameterization | Shallow feedforward neural networks · Shallow feedforward neural networks | covering number: a factorial term $d_1!$ in the denominator | Helped |
| Restrict the parameter space to representatives of permutation-equivalent networks | Deep neural networks · Deep neural networks | effective parameter space volume: $(2B)^\mathcal{S}/(d_1!\cdots d_L!)$ | Helped |
| Increase network width | Overparameterized neural networks · Neural network training | effective parameter space volume: approaches zero | Helped |
| Use initialization schemes with identical random distributions for weights and biases within each layer | Optimization algorithms for deep neural networks · Convergence to an ERM solution | probability of convergence: at least $d_1^*\times\cdots\times d_L^*\times \mathbb{P}(\Delta_{\rm max}(\theta^{(0)}-\theta_n)\le \delta/2)$ | Helped |
| Use the permutation-invariant covering number bound | Neural networks in ERM · Estimation error | estimation error bound: subtracting at least $\log(d_1!\cdots d_L!)$ from the numerator | Helped |
Surprising findings
- Increasing width shrinks the effective parameter volume, suggesting overparameterized networks are easier to optimize, a counterintuitive complexity-reducing effect of width.
Limitations
- Only permutation invariance is considered; sign flip and scaling symmetries are neglected.
- Bounds still scale with parameter count S and can be vacuous for heavily overparameterized settings.
- Functional equivalence in practice may be limited to finite samples; no lower bounds on covering numbers are derived.
Experimental setup
Metrics: covering number bound metric entropy
Baselines: spectral-norm covering bound (Bartlett et al.) pseudo-dimension bound Neyshabur-style norm bounds
Builds on: covering number bounds for deep networks permutation symmetry of neural networks functional dimension
Closest papers by meaning
- The role of over-parametrization in generalization of neural networks (ICLR 2019 · similarity 0.88)
- On the Expected Complexity of Maxout Networks (NeurIPS 2021 · similarity 0.87)
- Sample complexity of data-driven tuning of model hyperparameters in neural networks with structured parameter-dependent dual function (NeurIPS 2025 · similarity 0.87)
- On the Hardness of Training Deep Neural Networks Discretely (AAAI 2025 · similarity 0.86)
- Going Beyond Neural Network Feature Similarity: The Network Feature Complexity and Its Interpretation Using Category Theory (ICLR 2024 · similarity 0.86)
- Position: A Theory of Deep Learning Must Include Compositional Sparsity (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.