Research map / Learning theory and algorithms / Kernels and regression theory
Understanding Nonlinear Implicit Bias via Region Counts in Input Space
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.
Proposes region count (number of connected same-label regions in low-dimensional input subspaces) as a reparametrization-invariant implicit bias measure, shows it correlates with generalization gap on CIFAR-10/100 and ImageNet, and proves that large learning rate yields small region counts for two-layer ReLU nets.
Problem
Implicit bias in nonlinear neural networks is poorly defined; parameter-based measures (norm, normalized margin) are not invariant to reparametrization and correlate weakly with generalization gaps.
Approach
Characterize implicit bias by counting connected decision regions with the same predicted label within low-dimensional input subspaces (convex hulls of training points), a function-determined quantity invariant to reparametrization; extends 2D fragmentation score to arbitrary dimensions and links it to learning rate via sharpness and an activation-pattern bound.
Key results
- Region count correlates with generalization gap at 0.98 per network on CIFAR-10 and 0.93 across all three main networks.
- Correlation remains high across 9 architectures and CIFAR-100/ImageNet (e.g., ResNet18 0.96 on CIFAR-100, 0.91 on ImageNet), and across optimizers and subspace dimensions 2-5.
- Theorem: for two-layer ReLU nets at edge of stability, average region count is bounded by O(N/(r^2 eta)), so larger learning rate yields smaller region counts.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use larger learning rates | Neural networks trained on CIFAR-10 · CIFAR-10 | region count | Helped |
| Use smaller batch sizes | Neural networks trained on CIFAR-10 · CIFAR-10 | region count | Helped |
| Measure region count instead of relying on parameter norm or margin | ResNet18 · CIFAR-10 | correlation with generalization gap | Helped |
| Use region count as the indicator | Neural networks across architectures and datasets · CIFAR-10, CIFAR-100, ImageNet | correlation with generalization gap: 0.98; 0.96; 0.91 | Helped |
| Increase the counting subspace dimension from 2D to 3D (ablation) | Region count · CIFAR-10, ResNet18 | correlation with generalization gap: 0.96 -> 0.97 | No clear effect |
| Use Adam instead of SGD (ablation) | Region count · CIFAR-10, ResNet18 | correlation with generalization gap: 0.98 -> 0.92 | Hurt |
| Use Adagrad instead of SGD (ablation) | Region count · CIFAR-10, ResNet18 | correlation with generalization gap: 0.98 -> 0.96 | Hurt |
| Generate lines from two test points instead of two training points (ablation) | Region count · CIFAR-10, ResNet18 | correlation with generalization gap: 0.98 -> 0.98 | No clear effect |
| Generate lines from a training point extended in a random direction (ablation) | Region count · CIFAR-10, ResNet18 | correlation with generalization gap: 0.98 -> 0.98 | No clear effect |
| Expand the line-coordinate range from [0,1] to [-1,2] (ablation) | Region count · CIFAR-10, ResNet18 | correlation with test accuracy: 0.98 -> 0.96 | No clear effect |
| Use Mixup augmentation (ablation) | ResNet-18 · CIFAR-10 | region count | Helped |
| Use random crop and random horizontal flip augmentation (ablation) | ResNet-18 · CIFAR-10 | test accuracy | Helped |
Surprising findings
- Norm-based and margin-based measures show low correlation with generalization gap in the deep learning regime.
- Expanding the sampling range of 1D segments (alpha range) changes region counts substantially but keeps correlation high.
Limitations
- Theory covers only two-layer ReLU networks with a simplified setup and a bound with an extra N dependence.
- Region count is only defined for classification tasks.
- Counts are estimated on grid approximations of low-dimensional subspaces rather than the full input space.
Experimental setup
Datasets: CIFAR-10 CIFAR-100 ImageNet-1k
Benchmarks: CIFAR-10 CIFAR-100 ImageNet-1k
Metrics: region count Pearson correlation with generalization gap test accuracy
Baselines: Frobenius distance to initialization output-space margin input-space margin
Builds on: fragmentation score (double descent decision regions) edge of stability linear region counting for ReLU networks
Closest papers by meaning
- The Implicit Bias of Structured State Space Models Can Be Poisoned With Clean Labels (NeurIPS 2025 · similarity 0.87)
- Conflicting Biases at the Edge of Stability: Norm versus Sharpness Regularization (ICML 2026 · similarity 0.87)
- Bias of Stochastic Gradient Descent or the Architecture: Disentangling the Effects of Overparameterization of Neural Networks (ICML 2024 · similarity 0.85)
- Simplicity Bias in Overparameterized Machine Learning (AAAI 2024 · similarity 0.85)
- Mirror, Mirror of the Flow: How Does Regularization Shape Implicit Bias? (ICML 2025 · similarity 0.85)
- Flavors of Margin: Implicit Bias of Steepest Descent in Homogeneous Neural Networks (ICLR 2025 · similarity 0.85)
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.