Log-Free Stability Certificate

(1) Integrate the method at checkpoint selection and optimizer evaluation, operating on per-example loss contributions and a small probe subset rather than on every training example. At checkpoint t, define g_i(S) as a centered contribution such as loss(f_{theta(S)},Z_i) minus loss(f_{theta(S)},V_i), where V_i is an independent validation example matched by class or task type. (2) For each probe example j, replace Z_j by an independent sample to form S^(j), then recompute the g_i values. Estimate cross-example sensitivity with beta_hat=max over i not equal to j of absolute(g_i(S^(j))-g_i(S)); use a high quantile instead of a maximum if outliers dominate. For M, hold S excluding i fixed, draw K independent replacements Z_i^(k), compute the corresponding g_i values, and set M_hat to the maximum absolute conditional average. Compute C_p=16 p beta_hat + M_hat sqrt(2p/n) for p in {2,4,8}. (3) Exact replacement retraining is expensive, so first implement it for a small probe set and a small model. Then use a one-step influence approximation: delta_theta_j=-eta times the gradient of loss_j, and approximate g_i(S^(j))-g_i(S) by the gradient of g_i transposed with delta_theta_j. The theorem supplies the coefficient 16p and the inverse-square-root n scaling; all probe estimates are empirical. (4) Run a first experiment on CIFAR-10 with a small ResNet and a two-layer MLP, comparing SGD, AdamW, and weight decay at matched training loss. Compare certificate values with the eventual test gap and test whether selecting the lowest-C_p checkpoint improves test accuracy over selecting the lowest training loss. Success is better rank correlation with future generalization and lower test error at equal train loss, with probe computation below 10 percent of training cost.