Modern learning systems often interpolate training data while still generalizing well, yet it remains unclear when algorithmic stability explains this behavior. We model training as a function-space trajectory and measure sensitivity to single-sample perturbations along this trajectory. We propose a contractive propagation condition and a stability certificate obtained by unrolling the resulting recursion. A small certificate implies stability-based generalization, while we also prove that there exist interpolating regimes with small risk where such contractive sensitivity cannot hold, showing that stability is not a universal explanation. Experiments confirm that certificate growth predicts generalization differences across optimizers, step sizes, and dataset perturbations. The framework therefore identifies regimes where stability explains generalization and where alternative mechanisms must account for success.
Figures & tables
Figure 1: Empirical relationship between the stability certificate and generalization error across all logged runs. The association is descriptive and is used to validate that the certificate behaves as a stability diagnostic under the controlled interventions of this section.
Step size η
Final certificate
Final test MSE
Gen. gap
0.05
0.005593
0.060443
-0.004349
0.10
0.011187
0.060445
-0.004256
0.20
0.022378
0.060447
-0.004072
0.40
0.044765
0.060453
-0.003714
Table 1: Terminal certificate and performance across GD step sizes (averaged over seeds). "Gen. gap" denotes terminal test MSE minus train MSE and can be negative at finite sample. Values are computed from the logged runs.
Figure 2: Neighbor-selection ablation (GD, η=0.2 ). Curves show the certificate prefix and the probe discrepancy under random index replacement versus high-leverage index replacement, averaged over seeds.
Replacement type
Final certificate
Probe discrepancy
Random replaced index
0.022378
9.4×10−5
High-leverage replaced index
0.010410
4.8×10−5
Table 2: Neighbor-selection ablation (GD, η=0.2 ). "Probe discrepancy" denotes the terminal probe-based RMS prediction difference dT . Values are averaged over seeds from the logged runs.
Figure 3: Optimizer comparison at the logged step sizes. Curves show certificate prefix and test MSE averaged over seeds. The purpose is diagnostic. Hyperparameters are not tuned to equalize convergence speed or interpolation across optimizers.
Optimizer
Final certificate
Final test MSE
Gen. gap
SGD
0.000093
0.060442
-0.004
GD
0.022378
0.060447
-0.004
Adam
28.295664
0.220317
0.220
Table 3: Optimizer comparison at the logged step sizes (averaged over seeds). "Gen. gap" denotes terminal test MSE minus train MSE. Values are computed from the logged runs.
Figure 4: Label-permutation intervention (GD, η=0.2 ). Curves show certificate prefix and test MSE averaged over seeds under clean labels versus permuted labels.
Labels
Final certificate
Final test MSE
Gen. gap
Clean labels
0.022378
0.060447
-0.004072
Permuted labels
0.018466
0.060446
-0.003877
Table 4: Clean versus permuted labels (GD, η=0.2 ), averaged over seeds from the logged runs. "Gen. gap" denotes terminal test MSE minus train MSE.
Figure 5: Step-size sweep (GD). Larger step sizes increase certificate growth. Terminal test MSE changes only mildly at the reported scale, but the certificate responds monotonically to the stability-relevant control parameter.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Step t
η=0.05
η=0.2
η=0.4
50
0.00143
0.00562
0.01124
100
0.00281
0.01118
0.02244
150
0.00420
0.01679
0.03361
200
0.00559
0.02238
0.04477
Appendix
Table 5: Representative certificate prefix values during training (GD, decay spectrum).
Step t
Random replacement
High-leverage replacement
50
2.4×10−5
1.2×10−5
100
4.8×10−5
2.4×10−5
150
7.1×10−5
3.6×10−5
200
9.4×10−5
4.8×10−5
Appendix
Table 6: Prediction discrepancy growth for different neighbor choices (GD, η=0.2 ).
Step t
SGD
GD
Adam
50
0.00002
0.0056
18.7
100
0.00005
0.0112
23.9
150
0.00007
0.0168
26.4
200
0.00009
0.0224
28.3
Appendix
Table 7: Certificate growth across optimizers (prefix values).
Step t
Clean labels
Random labels
50
0.00562
0.00464
100
0.01118
0.00926
150
0.01679
0.01387
200
0.02238
0.01847
Appendix
Table 8: Certificate evolution under clean and random labels (GD, η=0.2 ).