Constructing Algorithmic Stability from Support Unlearning

Abstract

Uniform algorithmic stability is a classical route to non-vacuous generalization bounds, yet existing analyses typically track the forward optimization trajectory on adjacent training sets. This paper develops a different construction of the same stability parameter. We introduce support unlearning, a deletion axiom that aligns only the support of a post-deletion map with that of retraining and is strictly weaker than certified unlearning. Adjacent n-size datasets are realized as two deletions from a common enlarged sample. A support unlearning operator, assembled from an efficiency envelope and a minimizer transport map, then defines unlearning stability. We prove that unlearning stability coincides with classical uniform stability and controls the generalization gap. For efficient learners we obtain general Lipschitz upper bounds in terms of the displacement of empirical minimizers under deletion. Concrete rates follow under standard geometry: O(1/n) in the strongly convex case and O(1/n) in the convex and weakly convex cases, with no non-vanishing additive constant. The results establish sample deletion as a constructive path from machine unlearning to uniform stability.