From Local Scores to Post Hoc Certificates

Data selection often scores examples using local derivatives at a reference model, although subset quality is set by retraining. We ask when these scores certify that no alternative in a declared exchange neighbourhood improves a returned subset beyond a tolerance. Existing uniform approximation bounds support such guarantees, but symmetric corrections also account for overestimated gains. Since overprediction preserves an upper bound, we focus on correcting underestimated gains. To bound these gains, we represent an exchange as continuous weight transfer, with its local prediction giving the starting slope of the retrained-utility curve. Under verifiable smoothness and curvature conditions, we derive a one-sided correction that retains target curvature’s suppression while controlling training-curvature variation and curvature differences between exchanged examples. Combined with scores recomputed at the returned subset’s trained model, this correction covers the neighbourhood in one computation, without retraining or enumerating alternatives. Exhaustive CIFAR-10 one-swap auditing demonstrates certification despite prediction error, with 14.3% local overprediction of the maximum retrained gain and an analytic correction adding 0.011% to that prediction. On a fixed empirical detection target, our verified certificate covers four exchanges at tolerance 0.02, versus two for symmetric and one for convex tangent bounds.