(Almost) Provable Error Bounds Under Distribution Shift via Disagreement Discrepancy

When deploying a model, it is important to be confident in how it will perform under inevitable distribution shift. Standard methods for achieving this include data dependent uniform convergence bounds (Ben-David et al., 2006, Mansour et al., 2009) (typically vacuous in practice) or assuming a precise model of how the distribution can shift (Chen et al., 2022, Rahimian and Mehrotra, 2019, Rosenfeld et al., 2021). Unfortunately, it is difficult or impossible to determine how severely these assumptions are violated by real data ("all models are wrong"), so practitioners usually cannot trust such bounds with confidence. To better estimate test performance in the wild, some recent work instead tries to directly predict accuracy of neural networks using unlabeled data from the test distribution of interest, (Baek et al., 2022, Garg et al., 2022, Lu et al., 2023). While these methods predict the test performance surprisingly well, they lack pointwise trustworthiness and verifiability: their estimates are good on average over all distribution shifts, but they provide no guarantee or signal of the quality of any individual prediction (here, each point is a single test distribution, for which a method predicts a classifier's average accuracy). Because of the opaque conditions under which these methods work, it is also difficult to anticipate their failure cases--indeed, it is reasonably common for them to substantially overestimate test accuracy for a particular shift, which is problematic when optimistic deployment can be costly or catastrophic.