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

arXiv: https://arxiv.org/abs/2306.00312 · HTML: https://mlsanity.com/paper/2306.00312/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 62 of its 75 references that are in the map.
- First posted on arXiv 1 Jun 2023.

## Builds on (most cited first, 30 of 62)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Domain-Adversarial Training of Neural Networks](https://mlsanity.com/paper/1505.07818/) (2015)
- [Benchmarking Neural Network Robustness to Common Corruptions and Perturbations](https://mlsanity.com/paper/1903.12261/) (2019)
- [RandAugment: Practical automated data augmentation with a reduced search space](https://mlsanity.com/paper/1909.13719/) (2019)
- [FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence](https://mlsanity.com/paper/2001.07685/) (2020)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Improved Regularization of Convolutional Neural Networks with Cutout](https://mlsanity.com/paper/1708.04552/) (2017)
- [Do ImageNet Classifiers Generalize to ImageNet?](https://mlsanity.com/paper/1902.10811/) (2019)
- [WILDS: A Benchmark of in-the-Wild Distribution Shifts](https://mlsanity.com/paper/2012.07421/) (2020)
- [Moment Matching for Multi-Source Domain Adaptation](https://mlsanity.com/paper/1812.01754/) (2018)
- [Can You Trust Your Model's Uncertainty? Evaluating Predictive Uncertainty Under Dataset Shift](https://mlsanity.com/paper/1906.02530/) (2019)
- [Deep Hashing Network for Unsupervised Domain Adaptation](https://mlsanity.com/paper/1706.07522/) (2017)
- [Decoupling Representation and Classifier for Long-Tailed Recognition](https://mlsanity.com/paper/1910.09217/) (2019)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [VisDA: The Visual Domain Adaptation Challenge](https://mlsanity.com/paper/1710.06924/) (2017)
- [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019)
- [Return of Frustratingly Easy Domain Adaptation](https://mlsanity.com/paper/1511.05547/) (2015)
- [Making Convolutional Networks Shift-Invariant Again](https://mlsanity.com/paper/1904.11486/) (2019)
- [Last Layer Re-Training is Sufficient for Robustness to Spurious Correlations](https://mlsanity.com/paper/2204.02937/) (2022)
- [Functional Map of the World](https://mlsanity.com/paper/1711.07846/) (2017)
- [Bridging Theory and Algorithm for Domain Adaptation](https://mlsanity.com/paper/1904.05801/) (2019)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Revisiting Batch Normalization For Practical Domain Adaptation](https://mlsanity.com/paper/1603.04779/) (2016)
- [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018)

## Built on by (most cited first, 16 of 16)

- [One-Shot Strategic Classification Under Unknown Costs](https://mlsanity.com/paper/2311.02761/) (2023)
- [Monitoring Risks in Test-Time Adaptation](https://mlsanity.com/paper/2507.08721/) (2025)
- [On Continuous Monitoring of Risk Violations under Unknown Shift](https://mlsanity.com/paper/2506.16416/) (2025)
- [Adapting to Online Distribution Shifts in Deep Learning: A Black-Box Approach](https://mlsanity.com/paper/2504.07261/) (2025)
- [Sparse Causal Discovery with Generative Intervention for Unsupervised Graph Domain Adaptation](https://mlsanity.com/paper/2507.07621/) (2025)
- [Pitfalls of Unlabeled Disagreement-Based Drift Detection in Streaming Tree Ensembles](https://mlsanity.com/paper/2605.12803/) (2026)
- [Beyond Top-Class Agreement: Using Divergences to Forecast Performance under Distribution Shift](https://mlsanity.com/paper/2312.08033/) (2023)
- [Source-Free Domain-Invariant Performance Prediction](https://mlsanity.com/paper/2408.02209/) (2024)
- [ODD: Overlap-aware Estimation of Model Performance under Distribution Shift](https://mlsanity.com/paper/2506.14978/) (2025)
- [Knowledge Distillation of Uncertainty using Deep Latent Factor Model](https://mlsanity.com/paper/2510.19290/) (2025)
- [ODP-Bench: Benchmarking Out-of-Distribution Performance Prediction](https://mlsanity.com/paper/2510.27263/) (2025)
- [Bridging Domain Expertise and Generalization for Performance Estimation](https://mlsanity.com/paper/2606.06335/) (2026)
- [Reliably Detecting Model Failures in Deployment Without Labels](https://mlsanity.com/paper/2506.05047/) (2025)
- [On the Bayes Inconsistency of Disagreement Discrepancy Surrogates](https://mlsanity.com/paper/2512.05931/) (2025)
- [Candidate Comparability Before Promotion: Conditional Validation in Adaptive Network Intrusion Detection](https://mlsanity.com/paper/2609.04388/) (2026)
- [How Many Samples Are Enough for Learning Across Domains?](https://mlsanity.com/paper/2609.39336/) (2026)

## Abstract (arXiv)

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 HDeltaH-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/disagreediscrep .