Gradient descent on overparameterized neural networks typically operates at the Edge of Stability (EoS), where the largest Hessian eigenvalue hovers around a step-size-dependent threshold. We study how sparse connectivity changes generalization below this threshold in two-layer ReLU networks. Prior results have shown that for fully-connected networks (FCNs), generalization guarantees in this regime degrade and become vacuous on high-dimensional spherical inputs. Our analysis reveals that sparse connectivity fundamentally alters this picture. Under sparse connectivity, the network processes a collection of low-dimensional patches rather than the full input vector, so the effective constraint imposed by the stability condition is governed by the geometry of the training patch collection. We prove that when the receptive fields are small relative to the ambient dimension, the effective constraint yields non-vacuous generalization bounds in precisely the spherical regime where FCNs provably fail. The same framework also reveals a contrasting failure mode: if the patch collection lacks geometric structure, the constraint becomes unable to prevent overfitting. We corroborate this theory by analyzing the patch geometry of natural images, showing that standard convolutional designs produce patch multiset with low-dimensional structure that facilitates generalization. This provides a principled explanation for the generalization advantage of convolutional networks. Thus, our analysis yields a unified framework that identifies how architecture, data geometry, and gradient descent jointly govern generalization performance.
Figures & tables
Figure 1: Data × architecture determines the geometry that gradient descent interacts with.
Figure 2: Generalization-gap scaling in synthetic experiments. (Left) GenGap(fθ,D) versus the sample size n on a log–log scale. The fitted slope summarizes the empirical rate: if GenGap≲n−c , then log(GenGap)≤−clogn+b , so a more negative slope indicates faster decay (better generalization). In our experiments, the FCN slope is nearly flat (slope =−0.03 at d=10 ), whereas SCN exhibits increasingly negative slopes as d grows (slope =−0.34 at d=100 , −0.69 at d=200 , and −0.86 at d=400 ), indicating faster decay with n . (Right) GenGap(fθ,D) versus the ambient dimension d with n fixed, illustrating that for SCN (with patch size m≪d ) the generalization gap remains stable and can even decrease as d increases. More details can be found in Appendix G .
Figure 3: Interpolation below the edge of stability. Left. Training loss and generalization gap, showing that the SCN interpolates noisy labels in the random spherical-patch setting. Middle. The largest Hessian eigenvalue hovers near 2/η≈10 , indicating compatibility with the EoS regime. Right. Scatter plot of per-neuron path norm ∣vk∣∥wk∥ against activation rate nJ1∑i,j\mathds1{wkTπj(xi)>bk} . Many neurons have large path norms while activating on only a small fraction of the patch multiset, consistent with the failure mode in Theorem 4.3 : rare activations can fit labels while keeping the sharpness small.
Figure 4: Patch geometry vs. image geometry on CIFAR-10. Left: PCA explained-variance ratio for the patch cloud ( R27 , solid) and the ambient image cloud ( R3072 , dashed). Patches concentrate 90% variance in 3 principal directions; images need over 100 . Right: Half-space concentration curves Ψ(T)=P(depth(X)≥T) for T∈[0,0.5] . Larger area means deeper points and fewer opportunities for near-isolating hyperplanes. The patch cloud shows markedly larger concentration.
Figure 5: Generalization on CIFAR-10 with noisy labels. Two-layer SCN ( 3×3 convolution, stride 1 , no padding) vs. FCN of the same width, both trained with full-batch GD ( η=0.2 ). Left: Training loss (solid) and generalization gap (dashed) over epochs. The SCN stabilizes near the noise floor; the FCN interpolates. Middle: Sharpness λmax(∇2L) . Both networks hover around 2/η≈10 after ∼ 3k epochs (before that the loss of FCN has not started to converge), confirming the BEoS regime. Right: Excess risk over training epochs. After 2 k epochs the SCN stabilizes at a much lower excess risk than the FCN.
Representative backbone
Core sparse connectivity pattern
Dimension of the processed unit
ResNet-50 ( He et al., 2016 )
3×3 bottleneck convolution
3×3×Cin (up to Cin=512 )
ResNeXt-50 ( Xie et al., 2017 )
3×3 grouped convolution
3×3×Cin/g (up to g=32 )
ConvNeXt-T ( Liu et al., 2022 )
7×7 depthwise convolution
7×7=49
ViT-B/16 ( Dosovitskiy et al., 2021 )
uniform Transformer
768 for all blocks
Swin-T ( Liu et al., 2021b )
hierarchical Transformer
96→192→384→768
Table 1: The design trend of sparse connectivity in modern vision backbones.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Panel A: ImageNet classification top-1 accuracy
Model and input
16×16
8×8
4×4
2×2
1×1
DeiT-B, 64×64 input
68.2
76.9
80.1
80.8
81.3
DeiT-B, 128×128 input
78.1
81.0
82.3
82.9
–
Adventurer-B, 224×224 input
82.6
83.9
84.3
84.5
84.6
Panel B: Sequence-length ablation on ImageNet top-1 accuracy
Model and input
Seq. length
Interpolated coarse tokens
True patch scaling
Appendix
Table 2: Selected patchification-scaling results adapted from [ Wang et al., 2025b ] . Patch size denotes the side length of the square image patch used to form one token. Panel A shows that reducing patch size improves ImageNet accuracy. Panel B separates true patch-size reduction from only increasing the sequence length by interpolating coarse tokens. Here we only list their results on DeiT-B [ Touvron et al., 2021 ] and Adventurer-B [ Wang et al., 2025a ] .
Figure 6: SCN generalizes on high-dimensional spherical data.(Left) With d=400 and fixed patch size m≪d , train loss plateaus near σ2 while excess risk decreases to 0.15 , confirming generalization rather than memorization. (Middle) Sharpness saturates at BEoS ( λmax≈2/η ). (Right) Neurons spread across moderate activation rates, unlike the sparse isolation in flat interpolation (Figure 3 ). This validates Theorem 4.3 : when m≪d , stability-induced regularization prevents overfitting. Results averaged over 5 seeds with η=0.2 , trained for 30k epochs.
d
J
Gen Gap
Excess Risk
100
10
1.283±0.114
0.613±0.101
200
20
0.780±0.076
0.352±0.047
400
40
0.295±0.004
0.147±0.010
Appendix
Table 3: Generalization gap and excess risk for SCN on spherical data (corresponding to Figure 2(a) ). As ambient dimension d increases with fixed patch size m , both metrics decrease—confirming the “blessing of dimensionality”.
Figure 7: FCN satisfies BEoS but still memorizes (Left) FCN ( d=10 ) interpolates noisy labels (train loss →0 ) while excess risk remains ≈σ2 . (Middle) Sharpness saturates at BEoS. (Right) Activation pattern after training. Despite satisfying BEoS, FCN fails to generalize—confirming that on spherical data, stability constraints alone are insufficient without convolutional structure. Averaged over 5 seeds; with similar setting as Figure 6
Training modern neural networks often relies on large learning rates, operating at the edge of stability, where the optimization dynamics exhibit oscillatory and chaotic behavior. Empirically, this regime often yields improved generalization performance, yet the underlying mechanism remains poorly understood. In this work, we represent stochastic optimizers as random dynamical systems, which often converge to a fractal attractor set (rather than a point) with a smaller intrinsic dimension. Building on this connection and inspired by Lyapunov dimension theory, we introduce a novel notion of dimension, coined the `sharpness dimension', and prove a generalization bound based on this dimension. Our results show that generalization in the chaotic regime depends on the complete Hessian spectrum and the structure of its partial determinants, highlighting a complexity that cannot be captured by the trace or spectral norm considered in prior work. Experiments across various MLPs and transformers validate our theory while also providing new insights into the recently observed phenomenon of grokking.
Mario Tuci, Caner Korkmaz, Umut Şimşekli +1
INRIA, CNRS, Département d’Informatique de l’Ecole Normale Supérieure / PSL, France · Department of Computing, Imperial College London, United Kingdom
One of the fundamental challenges in the deep learning community is to theoretically understand how well a deep neural network generalizes to unseen data. However, current approaches often yield generalization bounds that are either too loose to be informative of the true generalization error or only valid to the compressed nets. In this study, we present a simple yet non-vacuous generalization bound from the optimization perspective. We achieve this goal by leveraging that the hypothesis set accessed by stochastic gradient algorithms is essentially fractal-like and thus can derive a tighter bound over the algorithm-dependent Rademacher complexity. The main argument rests on modeling the discrete-time recursion process via a continuous-time stochastic differential equation driven by fractional Brownian motion. Numerical studies demonstrate that our approach is able to yield plausible generalization guarantees for modern neural networks such as ResNet and Vision Transformer, even when they are trained on a large-scale dataset (e.g. ImageNet-1K).
Chengli Tan, Jiangshe Zhang, Junmin Liu +1
Northwestern Polytechnical University, Xi’an, China · Xi’an Jiaotong University, Xi’an, China · SGIT AI Lab, State Grid Corporation of China, Xi’an, China
We address the fundamental question of why deep neural networks generalize by establishing a pointwise generalization theory for fully connected networks. This framework resolves long-standing barriers to characterizing the rich nonlinear feature-learning regime and builds a new statistical foundation for representation learning. For each trained model, we characterize the hypothesis via a pointwise Riemannian Dimension, derived from the eigenvalues of the learned feature representations across layers. This establishes a principled framework for deriving hypothesis-dependent, representation-aware generalization bounds. These bounds offer a systematic upgrade over approaches based on model size, products of norms, and infinite-width linearizations, yielding guarantees that are orders of magnitude tighter in both theory and experiment. Analytically, we identify the structural properties and mathematical principles that explain the tractability of deep networks. Empirically, the pointwise Riemannian Dimension exhibits substantial feature compression, decreases with increased over-parameterization, and captures the implicit bias of optimizers. Taken together, our results indicate that deep networks are mathematically tractable in practical regimes and that their generalization is sharply explained by pointwise, feature-spectrum-aware complexity.