2024/05/22 by Jake A. Soloff, Rina Foygel Barber, Soloff, Jake A. +3 · 4 citations
Computer Science · #FOS: Computer and information sciences #FOS: Mathematics #Fuzzy Logic and Control Systems #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2405.14064
openalex publication_date 2024/05/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We propose a new framework for algorithmic stability in the context of multiclass classification. In practice, classification algorithms often operate by first assigning a continuous score (for instance, an estimated probability) to each possible label, then taking the maximizer -- i.e., selecting the class that has the highest score. A drawback of this type of approach is that it is inherently unstable, meaning that it is very sensitive to slight perturbations of the training data, since taking the maximizer is discontinuous. Motivated by this challenge, we propose a pipeline for constructing stable classifiers from data, using bagging (i.e., resampling and averaging) to produce stable continuous scores, and then using a stable relaxation of argmax, which we call the "inflated argmax," to convert these scores to a set of candidate labels. The resulting stability guarantee places no distributional assumptions on the data, does not depend on the number of classes or dimensionality of the covariates, and holds for any base classifier. Using a common benchmark data set, we demonstrate that the inflated argmax provides necessary protection against unstable classifiers, without loss of accuracy.