Research map / Learning theory and algorithms / Kernels and regression theory
A two-scale Complexity Measure for Deep Learning Models
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.
Introduces the two-scale effective dimension (2sED), a Fisher-geometry complexity measure that bounds generalization error, and a layerwise-computable lower bound (lower 2sED) for Markovian/feedforward models, validated on small MLPs and CNNs.
Problem
Existing complexity measures for deep models are either data-independent and loose, or require global Fisher spectrum computation that is infeasible for large models; a pre-training, scalable, modular complexity measure is needed for model selection.
Approach
Defines the two-scale effective dimension via a micro-scale covering radius and a meso-scale partition controlled by an exponent zeta, using Fisher balls and normalized Fisher information; for Markovian models a Jensen-based layerwise iterative lower bound makes it computable block by block.
Key results
- Lower 2sED is numerically very close to the full 2sED for an MLP 54-16-7 on Covertype and a CNN on MNIST across covering radii.
- Lower 2sED ranking of MLP architectures matches training loss ordering: MLP 54-16-7 achieves lower training loss with 10000 samples, while MLP 54-13-11-9-7 is better with 100000 samples.
- The stochastic perturbation variance sigma^2 has a negligible impact on both lower 2sED and 2sED.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use lower 2sED instead of 2sED | Markovian neural networks · Covertype and MNIST | approximation tightness | Helped |
| Vary the stochastic block variance σ² | Feed-forward neural networks · Covertype and MNIST | 2sED and lower 2sED | No clear effect |
| Increase the number of samples and parameterizations used for Monte Carlo estimation | Lower 2sED · Covertype, MNIST, and CIFAR10 | estimate stability | No clear effect |
| Use MLP 54-16-7 rather than the other tested MLPs | MLPs trained on Covertype · Covertype, 10000 training samples | training loss | Helped |
| Use MLP 54-13-11-9-7 rather than the other tested MLPs | MLPs trained on Covertype · Covertype, 100000 training samples | training loss | Helped |
| Vary the covering radius ε | MLP 54-16-7 and MLP 54-13-11-9-7 · Covertype | relative lower 2sED / expressiveness | Mixed |
Surprising findings
- The MLP with a bottleneck (54-10-2-10-25-7) has more parameters than MLP 54-16-7 yet is expected to have lower expressiveness, which the lower 2sED captures.
Limitations
- Exact eigendecomposition via numpy is used, which is intractable for large-scale models with high-dimensional FIM.
- Experiments are limited to small MLPs and CNNs on Covertype, MNIST and CIFAR10.
- Deterministic networks must be converted to stochastic variants with Gaussian noise to fit the framework.
Experimental setup
Datasets: Covertype MNIST CIFAR10
Benchmarks: Covertype MNIST CIFAR10
Metrics: lower 2sED training loss
Baselines: effective dimension (zeta=0)
Builds on: effective dimension (Abbas et al.) box-counting dimension K-FAC
Closest papers by meaning
- On Measuring Excess Capacity in Neural Networks (NeurIPS 2022 · similarity 0.86)
- Nearly-tight Bounds for Deep Kernel Learning (ICML 2023 · similarity 0.85)
- Finding Generalization Measures by Contrasting Signal and Noise (ICML 2023 · similarity 0.85)
- The $\varphi$ Curve: The Shape of Generalization through the Lens of Norm-based Capacity Control (NeurIPS 2025 · similarity 0.84)
- Topological Generalization Bounds for Discrete-Time Stochastic Optimization Algorithms (NeurIPS 2024 · similarity 0.83)
- On the Parameterization of Second-Order Optimization Effective towards the Infinite Width (ICLR 2024 · similarity 0.83)
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.