Black-box tests for algorithmic stability

DOI10.1093/IMAIAI/IAAD039MaRDI QIDQ6384395zbMATH OpenOpenAlexFDO

Authors Byol Kim, Rina Foygel Barber

Publication date 30 November 2021

Full work available at URL https://doi.org/10.1093/imaiai/iaad039

Mathematics Subject Classification ID

Parametric inference (62Fxx) Artificial intelligence (68Txx)

Abstract: Algorithmic stability is a concept from learning theory that expresses the degree to which changes to the input data (e.g., removal of a single data point) may affect the outputs of a regression algorithm. Knowing an algorithm's stability properties is often useful for many downstream applications -- for example, stability is known to lead to desirable generalization properties and predictive inference guarantees. However, many modern algorithms currently used in practice are too complex for a theoretical analysis of their stability properties, and thus we can only attempt to establish these properties through an empirical exploration of the algorithm's behavior on various data sets. In this work, we lay out a formal statistical framework for this kind of "black-box testing" without any assumptions on the algorithm or the data distribution and establish fundamental bounds on the ability of any black-box test to identify algorithmic stability.

Cited in

(3)

• Algorithmic stability implies training-conditional coverage for distribution-free prediction methods
• Select without fear: almost all minibatch schedules generalize optimally
• The limits of assumption-free tests for algorithm performance

This page was built for publication: Black-box tests for algorithmic stability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6384395)