  We derive an (almost) guaranteed upper bound on the error of deep neural
networks under distribution shift using unlabeled test data. Prior methods
either give bounds that are vacuous in practice or give estimates that are
accurate on average but heavily underestimate error for a sizeable fraction of
shifts. In particular, the latter only give guarantees based on complex
continuous measures such as test calibration -- which cannot be identified
without labels -- and are therefore unreliable. Instead, our bound requires a
simple, intuitive condition which is well justified by prior empirical works
and holds in practice effectively 100% of the time. The bound is inspired by
$\mathcal{H}\Delta\mathcal{H}$-divergence but is easier to evaluate and
substantially tighter, consistently providing non-vacuous guarantees.
Estimating the bound requires optimizing one multiclass classifier to disagree
with another, for which some prior works have used sub-optimal proxy losses; we
devise a "disagreement loss" which is theoretically justified and performs
better in practice. We expect this loss can serve as a drop-in replacement for
future methods which require maximizing multiclass disagreement. Across a wide
range of benchmarks, our method gives valid error bounds while achieving
average accuracy comparable to competitive estimation baselines. Code is
publicly available at https://github.com/erosenfeld/disagree_discrep .
