Black box tests for algorithmic stability
  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.
