Many results on generalization and distribution-free inference depend on the stability of a regression algorithm, which is often defined as the property that predictions on a new test point are not substantially altered by removing a single point at random from the training set. However, this stability property itself is an assumption that may not hold for highly complex predictive algorithms and/or nonsmooth data distributions. In this work we ask whether it is possible to infer the stability of an algorithm through “black-box testing”, where we cannot study the algorithm theoretically but instead try to determine its stability properties by the behavior of the algorithm on various data sets. Our results establish fundamental limits on the stability testing problem in the distribution-free setting.

This work is joint with Byol Kim.