(Almost) Provable Error Bounds Under Distribution Shift via Disagreement Discrepancy
Authors: Elan Rosenfeld
Saurabh Garg
Venue: NeurIPS 2023 poster (2023)
Keywords: accuracy estimation
error bounds
distribution shift
unsupervised domain adaptation
TL;DR: We give a bound for estimating accuracy under shift using unlabeled test data. It uses a simple condition which holds effectively 100% of the time. This closes the gap b/w vacuous, verifiable bounds and tighter ones which often overestimate accuracy.

Abstract: We derive a new, (almost) guaranteed upper bound on the error of deep neural networks under distribution shift using unlabeled test data. Prior methods are either vacuous in practice or 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 test error upper bounds. 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 natural and synthetic distribution shift benchmarks, our method gives valid error bounds while achieving average accuracy comparable to—though not better than—competitive estimation baselines.

(Almost) Provable Error Bounds Under
Distribution Shift via Disagreement Discrepancy
Elan Rosenfeld
Saurabh Garg Machine Learning Department
Machine Learning Department
Carnegie Mellon University elan@cmu.edh
Carnegie Mellon University
Abstract
We derive a new, (almost) guaranteed upper bound on the error of deep neural networks under distribution shift using unlabeled test data. Prior methods are either vacuous in practice or accurate on average but heavily underestimate error for a sizeable fraction of shifts. 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 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 H HAH-ddverrgene but is easier to evaluate and substantially tighter, consistently providing non- vacuous test error upper bounds. 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 "'dsagreement 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 wide range of natural and synthetic distribution shift benchmarks, our method gives valid error bounds while achieving average accuracy comparable to- though not better than competiiive estimation baselines.
Introduction
When deploying 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 [4
(typically vacuous in practice) assuming a precise model of how the distribution shift [57 10 Unfortunately, is difficult or impossible to determine how severely these assumptions
[
violated by real data (62]. 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 [2 3 40)
While these methods predict the test performance surprisingly well, they lack pointwise trustworthi- ness and verifiability: their estimates good on average over all distribution shifts, but they provide no signal of the quality of any individual prediction (here, each point a single test distribution, for which method predicts classifier's average accuracy). Because of the opaque conditions under which these methods work, is also difficult to anticipate their failure cases leees-indeed, it is reasonably common for them to substantially overestimate test accuracy for particular shift, which is prob- lematic when optimistic deployment would be very costly. Worse yet, we find that this gap grows with fest error (Figure [ making these predictions least reliable precisely when their reliability is most important. Although it is clearly impossible to guarantee upper bounds on test error for all shifts, there is still potential for error bounds that intuitive and reasonably trustworthy.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Target Accuracy Prediction
Dis (ours)
0.8
ATC
COT
AC
y ==x
0.2
0.3
0.4
0.5
0.6
0.7
0.9 1.0
Target Accuracy
Figure I: Our bound vs. three prior methods for estimation across a wide variety of distribution shift benchmarks (e.g., WILDs, BREEDs, DomainNet) and training methods (e.g., ERM, FixMatch, BN-adapt). Prior methods are accurate on average, but it is difficult or impossible to know when given prediction is reliable and why. Worse yet, they usually overestimate accuracy, with the gap growing as test accuracy decreases- this is precisely when a reliable, conservative estimate is most desirable. Instead, DIs² maximizes the disagreement discrepancy give reliable error upper bound which holds effectively 100% of the time. See Appendix F for stratification by training method.
In this work, we develop a method for (almost) provably bounding test error of classifiers under distribution shift using unlabeled test points. Our bound's only requirement is a simple, intuitive, condition which describes the ability of hypothesis class to achieve small loss on a particular objective defined over the (unlabeled) train and test distributions. Inspired by -ivvereieeeeecce [7 our method requires training critic to maximize agreement with the classifier of interest on the source distribution while simultaneously maximizing disagreement on the target distribution; we refer to this joint objective as the Disagreement Discrepancy, and so we name the method DIs?. We optimize this discrepancy over linear classifiers using deep features or linear functions thereof finetuned on only the training set. Recent evidence suggests that such representations are sufficient for highly expressive classifiers even under large distribution shift [61]. Experimentally, we find that our bound is valid effectively 100% of the time time consistentyy giving non-trivial lower bounds on test accuracy which are reasonably comparable to competitive baselines.
Additionally, our proof of the bound leads to natural (post-hoc) hypothesis test of the validity of its lone assumption. This provides an unusually strong positive signal: for more than half the datasets we evaluate we prove with high probability that the assumption holds; the corresponding indicator that it does not hold never occurs. We also show that is possible to approximately test this bound's likelihood of being valid priori using only unlabeled data: the optimization process itself provides useful information about the bound's validity, and we use this to construct a score which linearly correlates with the tightness of the bound. This score can then be used to relax the original bound into a sequence of successively tetter--e--less-coneeveee to make estimates according their specific risk tolerance.
estimates, interpolating between robustness
and accuracy and allowing
While maximizing agreement statistically well understood, our method also calls for maximizing disagreement on the target distribution. This is not so straightforward in the multiclass setting, and we observe that prior works use unsuitable losses which do not correspond minimizing the 0-1 loss of interest and are non-convex (or even concave) in the model logits 112 50 23 To rectify this, we derive a new "disagreement loss" which serves as an effective proxy loss for maximizing multiclass disagreement. Experimentally, disagreement) compared to prior methods, and we believe it can serve as a useful drop-in replacement for any future methods which require maximizing multiclass disagreement.
find that minimizing this loss results in lower risk (that is, higher
Experiments across numerous vision datasets (BREEDs 655, FMoW-WILD.
35 Visda [5]].
Domainnet [53), CIFAR1O, CIFAR 100 (36) and OfficeHome (69] demonstrate the effectiveness of our bound. Though DIs² is competitive with prior methods for error estimation, we emphasize that our focus is not on improving raw predictive accuracy rather, we hope to obtain reliable (i.e.,
'The few violations are expected priori, have an obvious explanation, and only occur for specific type of learned representation. We defer more detailed discussion of this until after present the bound.

---

correct), reasonably tight bounds on the test error of a given classifier under distribution shift. In particular, while existing methods tend to severely overestimate accuracy as the true accuracy drops. our bound maintains its validity while remaining non-vacuous, even for drops in accuracy large as 70%. addition to source-only training, we experiment with unsupervised domain adaptation methods that use unlabeled target data and show that our observations continue to hold.
2 Related Work
Estimating test error with unlabeled data. The generalization capabilities of overparameterized models on in-distribution data have been extensively studied using conventional machine learning
39 42). This research aims to bound the generalization gap by evaluating complexity measures of the trained model. However, these bounds tend to be numerically loose compared to actual generalization error 770 43 Another line of work instead explores the
tools 46 47
45
48
73
use of unlabeled data for predicting in-distribution generalization [56] 55 20 44 32]. More relevant to our work, there are several methods that predict the error of classifier under distribution shift with unlabeled test data: (i) methods that explicitly predict the correctness of the model on individual
unlabeled points [14] 15 8] and (ii) methods that directly estimate the overall error without making
a pointwise prediction
3
To achieve consistent estimate of the target accuracy, several works require calibration on the target domain 32 24]. However, these methods often yield poor estimates because deep models trained and calibrated source domain are not typically calibrated on previously unseen domains [49]. Additionally, [44 [4] require a subset of labeled target domains to learn a regression function that predicts model performance-butt thus requires significant priori knowledge about the nature of shift that, in practice, might not be available before models are deployed the wild.
Closest to our work is [1]. where the authors use commann-invaiian predictors as proxy for un- known target labels. However, like other works, their method only estimates the target accuracy- the actual error bounds they derive are not computable in practice. Second, even their estimate is compu- tationally demanding and relies on multiple approximations, tuning of numerous hyperparameters, e.g. lagrangian multipliers; as result, proper tuning is difficult and the method does not scale to modern deep networks. Finally, they suggest minimizing the (concave) negative cross-entropy loss, but we show that this can be poor proxy for maximizing disagreement, instead proposing more suitable replacement which we find performs much better.
Uniform convergence bounds. Our bound is inspired by classic analyses using H- and HAH- divergence [4 6 7 These provide error bounds via a complexity measure that both data- and hypothesis mhothesis-classee class- deeissddepddeen. This motivated a long line of work on training classifiers with small corresponding complexity, such as restricting classifiers' discriminative power between source and target data [8 67 38 72). Unfortunately, such bounds are often intractable to evaluate and are usually vacuous real world settings. We provide more detailed comparison to our approach in Section 3.1
3 Deriving an (Almost) Provable Error Bound
Notation. Let T denote the source and target (train and test) distributions, respectively, over labeled inputs (z. y) X' V, and let S, 7 denote sets of samples from them with cardinalities ns and n& (they also denote the corresponding empirical distributions). Recall that we observe only the covariates x without the label y when a sample is drawn from T. We consider classifiers h: X + R which output a vector of logits, and we let denote the particular classifier whose error aim to bound. Generally, we use H. to denote hypothesis class of such classifiers. Where clear from context, we use (xx) to refer to the argmax logit, i.e. the predicted class. We treat these classifiers as deterministic throughout, though our analysis can easily be extended to probabilistic classifiers and labels. For a distribution D on X x y, let (D, M/) == Ep [1 arg max,, h((z), # arg max,, h b'(x),,) denote the one-hot disagreement between classifiers h and h' on D. Let y" represent the true labeling function such that y" (a)) = y for all samples (x., y)) with some abuse of notation, we write eD (h) to mean eD (h, y² ), i.e. the 0-1 error of classifier h on distribution D.
The bound we derive in this work is extremely simple and relies one new concept:
3

---

Definition 3.1. The disagreement discrepancy (hh, h²) is the disagreement between h and h' on T minus their disagreement on S:
Ahh,h) := ch,
(h,
We leave the dependence on S, T implicit. Note that this term is symmetric in its arguments and signed- it can be negative. With this definition, we now have the following lemma:
Lemma 3.2. For any classifier h (h) = cs(h) Ah,,
Proof. By definition, (h( = ch(h) + (eT(h) es(h)) = es(h) + yh,
We cannot directly use Lemma 3.2 to estimate (Thh) because the second term is unknown. However, observe that y² is fixe.. That is, while learned h will depend on y² and S-and therefore A(h, v²) may be large under large distribution shift-y" is not chosen to maximize a(h, y") in response to the h we have learned. This means that for sufficiently expressive hypothesis class H. should be possible to identify an alternative labeling function h H for which A(h, h/) 2 A(h, v²) (we refer to such h' as the critic). In other words, we should be able to find an h E H. which, if it were the true labeling function, would imply at least as large of drop in accuracy from train to test as occurs in reality. This key observation serves the basis for our bound, and we discuss it in greater detail in Section
In this work we consider the class 76 of linear critics, with the features X' defined as nurce-finetunne neural representations or the logits output by the classifier Prior work provides strong evidence that this class has surprising capacity under distribution shift, including the possibility that functions very similar to y lic in H. [61, 34| 33). We formalize this intuition with the following assumption:
Assumption 3.3. Define h- == arg max (hh, 1t). We assume
(h,, y²) & A(h
Note that this statement is necessarily true whenever y" H; only becomes meaningful when considering restricted H. as we do here. Note also that this assumption is made specifically for h, i.c. on a per-classifier basis. This is important because while the above may not hold for every classifier h, it need only hold for the classifiers whose error would hope bound, which is in practice very small subset of classifiers (such as those which can be found by approximately minimizing the empirical training risk via SGD). From Lemma 3.2 we immediately have the following result:
Proposition 3.4. Under Assumption 3.3
ET
(h) S (h) + A(h,
Unfortunately, identifying the optimal critie ht intractable, meaning this bound still not estimable- we present an intermediate result for clarity of presentation. To derive the practical bound we report in our experiments, we need one additional step. In Section 4 we derive a "dis- agreement loss" which we use to approximately maximize the empirical disagreement discrepancy - -g(h, -). Relying this loss, we instead make the assumption:
Assumption 3.5. Suppose we identify the critic h E H which maximizes a concave surrogate to the empirical disagreement discrepancy. We assume (h,, v²) < A(h, h').
This assumption is slightly stronger than Assumption 3.3 in particular, Assumption 3.3 implies with high probability a weaker version of Assumption 3.5 with additional terms that decrease with increasing sample size and tighter proxy loss Thus, the difference in strength between these two assumptions shrinks as the number available samples grows and as the quality of our surrogate objective improves. Ultimately, our bound holds without these terms, implying that the stronger assumption is reasonable in practice. We can now present our main result:
Theorem 3.6 (Main Bound). Under Assumption
3.5 with probability 2 8-8.
(ns + 4nr) log 1/6 2n
(T()) S (e)(h) + A(h, R2) +
'Roughyy, Assumption 3.3 implies ( y²) < AC, A') O (v
log 1/6 min(ng.ny
+ where y is a data-
dependent measure of how lightly the surrogate loss bounds the 0-1 loss in expectation.

---

implies ey S cs(h) A(h,)') es(h,v") ("r es h²), so the problem reduces upper bounding these three terms. We define the random variables
Proof. Assumption 3.5
1/ss:
(((x)) h(xx)) + yi,
1(h(x;) * ((,))) TT =
r8,
1/ns:
h(xx,) + h(xx)) = Mi+
nt
0,
otherwise,
for source and target samples, respectively. By construction, the sum of all of these variables is precisely Eg eg(h, 1²) ey ht) -e((,, ti) (note these are the empirical terms). Further, observe that
Σ
Es|i(h(a.) + y.) - 1()(a.) -c
cs(h, cs (h,,
ss
Σ TT = -r(1(h(a,)) # =
and thus their expected sum cs y²) + eT (h, h²) cs h²), which are the population terms we hope to bound. Now we apply Hoeffding' inequality: the probability that the expectation exceeds
their sum by is no more than exp (3/nn))) +ur (V/r)²
21a
Solving for completes the proof. C
Remark 3.7. While we state Theorem 3.6 as an implication, Assumption 3.5 is equivalent to the stated bound up to finite-sample terms. Our empirical findings (and prior work) suggest that Assumption 3.5 is reasonable in general, but this equivalence allows us to actually prove that it holds in practice for many shifts. We elaborate on this Appendix
The core message behind Theorem 3.6 is that if there is a simple (i.e., linear) critic h/' with large disagreement discrepancy, the true y" could plausibly be this function, implying h could have high likewwi,, if no simple y² could hypothetically result in high error, we should expect low error.
Remark 3.8. Bounding error under distribution shift is fundamentally impossible without assumptions. Prior works which estimate accuracy using unlabeled data rely on experiments, suggesting that whatever condition allows their method to work holds in variety of settings [21 40 32, (24 using
these methods is equivalent to implicitly assuming that it will hold for future shifts. Understanding these conditions is thus crucial for assessing in given scenario whether they can be expected to be satisfied
3 It therefore of great practical value that Assumption 3.5 a simple, intuitive requirement: below we demonstrate that this simplicity allows to identify potential failure cases priori.
3.1 How Does D Improve over H- and HAH- Hive--Dieegeecc?
To verifiably bound classifier's under distribution shift, one must develop meaningful notion of distance between distributions. One early attempt at this was H-divergence [6 41) which measures the ability of binary hypothesis class discriminate between S and in feature space. This was later refined to HAH-divergence [7]. which is equal to H-divergence where the discriminator class comprises all exclusive-ors between pairs of functions from the original class H. Though these measures can in principle provide non-vace con-vacuous bounds, they usually do not, and evaluating them is intractable because it requires maximizing an objective over all pairs of hypotheses. Furthermore. these bounds are overly conservative even for simple function classes and distribution shifts because they rely on uniform convergence. In practice, we do not care about bounding the error of all classifiers in H-we only care to bound the error of h. This a clear advantage of DIs" over H.H.
The true labeling function is never worst-case." More importantly, we observe that should not expect the distribution shift to be truly worst case, because the test distribution T and ground truth
Wheether and when trust black-bor estimate that is consistently accurate in all observed settings is centuries-of old philosophical problem (30) which we do not address here. Regardless, Figure] shows that these estimates are not consistently accurate, making interpretability that much more important. 'If it were, we'd see exactly 0% test accuracy and when does that ever happen?
5

---

y2
Y3
h
3
y1
(a)
(b)
(c)
Figure 2: The advantage of DIs over bounds based on H-- and H. H.A Consider the task of classifying circles and squares (triangles are unlabeled). (a): Because 1ı and h2 @ ha perfectly discriminate between S (blue) and 'I (red), H- and HiA--divergence bounds are always vacuous. In contrast, DIs is only vacuous when 0% accuracy is induced by a reasonably likely ground truth (such v in (c), but not yī in (b)), and can often give non-vacuous bounds (such y/ in (b)).
y" are not chosen adversarially with respect to h. Figure gives simple demonstration of this point. Consider the task of learning a linear classifier to discriminate between squares and circles on the source distribution S (blue) and then bounding the error of this classifier on the target distribution T (red), whose true labels are unknown and are therefore depicted as triangles. Figure 2(a) demonstrttess that both H- and WAAH-divergenn achieve their maximal value of 1, because both hı and h2 t h3 perfectly discriminate between S and T. Thus both bounds would be vacuous.
Now, suppose we were to learn the max-margin l on the source distribution (Figure 2(b).. It is possible that the true labels are given by the worst-case boundary as depicted by vī (pink), thus "flipping" the labels and causing h have 0 accuracy on T. In this setting, vacuous bound is correct. However, this seems rather unlikely to occur in practice-instead, recent experimental evidence 34 suggests that the true yy will be much simpler. The maximum disagreement discrepancy here would be approximately 0.5, giving a test accuracy lower bound of 0.5-this is consistent with plausible alternative labeling functions such as y/ (orange). Even if y" not linear. we still expect that some linear function will induce larger discrepancy: this is precisely Assumption 3.3 Now suppose instead we learn å as depicted in Figure 2 Then a simple ground truth such as vī (green) is plausible, which would mean h has O accuracy on T. In this case, y is also critic with disagreement discrepancy equal to 1, and so DIS² would correctly output an error upper bound of 1.
A setting where D may be invalid. There is one setting where it should be clear that Assump- tion 3.3 is less likely to be satisfied: when the representation we are using is explicitly regular- ized to keep max A (h, h²) small. This occurs for methods such as DANN [88 and CDAN (38), which penalize the ability to discriminate between S and T in feature space. Given a critic h with large disagreement discrepancy, the discriminator D(x) = 1 (arg max,, Mi(x), arg max, h (x),)) will achieve high accuracy on this task (precisely, 1+A(h,A)) ). By contrapositive, enforcing low discriminatory power means that the max discrepancy must also be small. It follows that for these methods Dis should not be expected to hold universally, and in practice we see that this is the case (Figure 3) Nevertheless, when DIs does overestimate accuracy, it does so by significantly less than prior methods.
representation learning
2
Efficiently Maximizing the Disagreement Discrepancy
For a classifier h, Theorem 3.6 3.6 clearly prescribes how to bound its test error: first, train a critic h on the chosen X' to approximately maximize A ft), then evaluate cg(h) and Á(h, h() using a holdout set. The remaining difficulty is in identifying the maximizing h/ E H-ttha is, the one which minimizes (s, h!') and maximizes e M.). We can approximately minimize es (f, h() by minimizing the sample average of the convex surrogate Eloiistic := Tog|>] log softmax
as justified by statistical learning theory. However, it is less clear how to maximize e7 hh,

---

Target Accuracy Prediction
Dis
0.8
ATC
COT
AC
0.6
y=x
0.4
0.2
0.0
0.0
0.2
0.4
0.8 1.0
Target Accuracy
Figure 3: DIs may be invalid when the features are regularized to violate Assumption 3.5 Dowean-adversarrill representation learning algorithms such as DANN [8] and CDAN 388 minimize maxk'H Ahh, k²), meaning necessary condition is less likely be satisfied. Neverthe- less, when DIs does overestimate accuracy, it almost always does by less than prior methods.
indirectly
observe that these losses are not theoretically justified, as they do not upper bound the 0- disagreement loss or otherwise do not meaningfully enforce that higher agreement causes higher loss. Furthermore, they non-convex (or even concave) in the model logits, hindering optimization. Indeed, is casy to identify simple settings in which minimizing these losses will result in a degenerate classifier with arbitrarily small loss but high agreement. Instead, we derive new loss which satisfies the above desiderata and thus serves as a more principled approach to maximizing disagreement.
few prior works suggest proxy losses for multiclass disagreement 12 50
Definition 4.1. The disagreement logistic loss of classifier h on a labeled sample (x, y) is defined as
lai (h, = log
1
log + exp
h(x)y
Σ Mx)
D
Fact 4.2. The disagreement logistic loss is convex in ((x) and upper bounds the 0-1 disagreement loss (i.e., {arg max, hx)) = v)). For binary classification, the disagreement logistic loss is equivalent to the logistic loss with the label flipped.
We expect that lais maximizing disagreement in principled manner. We combine llogistic and lais to arrive at the empirical disagreement discrepancy objective:
useful drop-in replacement for any future algorithm which requires
La(W):
Σ S
Lroiisiic (h', h(x)) +
las x(x))). IT|
Σ FET
By construction, 1 1 La(')) is concave and bounds Á from below. However, note that the representations are already optimized for accuracy S, which suggests that predictions will have low entropy and that the i/log (>' scaling is unnecessary for balancing the two terms. We therefore drop the constant scaling factors; this often leads to higher discrepancy. In practice optimize this objective with multiple initializations and hyperparameters and select the solution with the largest empirical discrepancy on holdout set to ensure conservative bound. Experimentally. we find that results in smaller discrepancy; we
replacing las with any of the surrogate losses from [2 50 23
present these results Appendix B
Tightening the bound by optimizing over the logits. Looking at Theorem 3.6 it is clear that the value of the bound will decrease as the capacity of the hypothesis class is restricted. Since the number of features is large, one may expect that Assumption holds even for reduced feature set. In particular, it well documented that deep networks optimized with stochastic gradient descent learn representations with small effective rank, often not much more than the number of classes [ 2 information about S and T and that using the full feature space is unnecessarily conservative. To test this, evaluate 2 the full features, the logits output by h, and various fractions of the top
This suggests that the logits themselves should contain most the features'
7

---

principal components (PCs) of the features. We observe that using logits indeed results in tighter error bounds while still remaining valid-in contrast, using fewer top PCs also results in smaller emorr bounds, but at some point they become invalid (Figure C.2p. The bounds we report in this work are thus evaluated on the logits of h, except where we provide explicit comparisons in Section 5
Identifying the ideal number of PCs via a "validity score". Even though reducing the feature dimensionality eventually results in an invalid bound, it is tempting to consider how we may identify approximately when this occurs, which could give more accurate (though less conservative) prediction. We find that the optimization trajectory itself provides meaningful signal about this change. Specifically, Figure C.3 shows that for feature sets which not overly restrictive, the critic very rapidly ascends to the maximum source agreement, then slowly begins overfitting. For much more restrictive feature sets (i.e., fewer PCs), the critic optimizes much more slowly, suggesting that we have reached the point where we are artificially restricting H. and therefore underestimating the disagreement discrepancy. We design "validity score" which captures this phenomenon, and we observe that it is roughly linearly correlated with the tightness of the eventual bound (Figure C.4). Though the score is by no means perfect, we can evaluate DIs with successively fewer PCs and only retain those above certain score threshold, reducing the average prediction error while remaining reasonably conservative (Figure C.5 For further details, see Appendix C
Coverage (1)
Overest. (J) /
MAE (L)
DA?
x
X
x
Prediction Method
AC 25
0.1000 +.0
0.0333
020
0.1194 2002
0.1123
#.012
0.1091
#.011
0.1091 #.01
DoC
0.1667 1.040
0.0167
1.0167
0.1237
1.012
0.1096
1.012
0.1055
1.011
0.1083
1.012
ATC NE 21
0.2889 +.04
0,1333
0.044
0.0824
.00
0.0969
#.012
0.0665
=.00
0.0854
#0011
COT 40
0.2554 1. 1.0467
0.1667
1.049
0.0860
1.009
0.0948
1.011
0,0700 1.007 0.0808
1.010
Dis (Features)
1,0000
1,0000
0.0000
0.0000
0.2807
1.009
0.1918 1.008
DIs (Logits)
0.9889 +0011
0.7500
+.058
0.0011 +000
0.0475 #.00
0.1489 #.011 0.0945 #.0
DIs² (Logits w/o 8)
0.7556 0.45
0,4333 +.065
0.0771 #.013 0.0892 #.011
0.0887 #.009 0.0637 :00
Table I: Comparing the Dis bound to prior methods for predicting accuracy. DA denotes if the representations were learned via a nomain-adversariaa algorithm. We report what fraction of predictions correctly bound the true error (Coverage) and the average prediction error among shifts whose accuracy overestimated (Overest.), along with overall MAE. DIs² has substantially higher coverage and lower overestimation error, though lower overall MAE. By dropping the concentration term in Theorem we can get even better MAE even beating the baselines on aavasaaad representations at some cost to coverage.
5
Experiments
Datasets.
We conduct experiments across 11 vision benchmark datasets for distribution shift on datasets that span applications in object classification, satellite imagery, and medicine. We use four BREEDs datasets: (65] Entity Entity30, Nonliving26, and Living FMoW
[ and Camelyon
4 from WILDS (35] Officehome [69]: Visda (2]55:1: CIFAR1O, CIFARION [36]; and Domainet
(53. Each of these datasets consists of multiple domains with different types of natural and synthetic shifts. We consider subpopulation shift and natural shifts induced due to differences in the data collection process of ImageNet, i.e., ImageNetv2 660 and combination of both. For CIFARIO and CIFAR 100 we evaluate natural shifts due to variations in replication studies (59] and common corruptions (27. For all datasets, we use the same source and target domains commonly used in previous studies 22 64). We provide precise details about the distribution shifts considered in Appendix A Because distribution shifts vary widely in scope, prior evaluations which focus on only one specific type of shift (e.g., corruptions) often do not convey the full story. We therefore emphasize the need for more comprehensive evaluations across many different types of shifts and training methods, as we present here.
8

---

Experimental setup and protocols. Along with source-only training with ERM, we experiment with Unsupervised Domain Adaptation (UDA) methods that aim to improve target performance with unlabeled target data (FixMatch [66]. DANN [8. CIAN [8 and BN-adapt [37 ). We experiment with Densenet1 21 (28 and R
26 pretrained on ImageNet. For source-only ERM, as with other methods, we default to using strong augmentations: random horizontal flips, random crops, as well as Cutout [16] and RandAugment [33]. Unless otherwise specified, we default to full finetuning for source-only ERM and UDA methods. We use source hold-out performance to pick the best hyperparameters for the UDA methods, since we lack labeled validation data from the target distribution. For all of these methods, we fix the gggorithm-specfiii hyperparameters to their original recommendations following the experimental protocol in [22] For more details, see Appendix A
Methods evaluated. We compare DIs to four competitive baselines: Average Confidence (AC:
(25). Difference of Confidences (DoC; [4 Average Thresholded Confidence (ATC; (2I]), and
Confidence Optimal Transport (COT: 40). ). We give detailed descriptions of these methods in
Appendix A] For all methods, we implement post-hoc calibration on validation source data with temperature scaling [25]. which has been shown to improve performance. For DIS we report bounds evaluated both on the full features and on the logits of h as described in Section 4 Unless specified otherwise, we set 8 = .01 everywhere. We also experiment with dropping the lower order concentration term in Theorem 3.6 using only the sample average. Though this is of course no longer a conservative bound, we find it is an excellent predictor of test error and is worth including.
Metrics for evaluation. As our emphasis is on giving valid error bounds, we report the coverage, Le. the fraction of predictions for which the true error does not exceed the predieted error. We also report the standard prediction metric, mean absolute error (MAE). Finally, we measure the conditional average overestimation: this is the MAE among predictions which overestimate the accuracy. This metric captures the idea that the most important thing is giving a valid bound-bur -bt for some reason it is not, we'd d at least like it to be accurate as possible.
Reported metrics for all methods can be found in Table [ We aggregate results over all datasets, shifts, and training methods weessswwwss stratify only by whether the training method is domain- adversarial, as this affects the validity of Assumption 3.5 We find that DIs? achieves competitive MAE while maintaining substantially higher coverage, even for does overestimate accuracy, does so by much less, implying that it ideal for conservative estimation even when any given error bound is not technically satisfied. Dropping the concentration term performs even better (sometimes beating the baselines), at the cost of some coverage. This suggests that efforts to better estimate the true maximum discrepancy may yield even better predictors. We also show scatter plots to visualize performance on individual distribution shifts, plotting each source-target pair as single point. For these too we report separately the results for domain- adversarial (Figure 3) and annddomain-adveesariiill methods (Figure Tp. To avoid clutter, these two plots do not include DoC, as it performed comparably to AC. Figure 4(a) displays additional scatter plots which allow for a direct comparison of the variants of D Finally, Figure 4(b) plots the observed violation rate (i.c. 1 1-coverage) of D non-domain- add adversarial methods for varying 5. We observe that it lies at or below the line y = xr meaning the probabilistic bound provided by Theorem B.6 holds across range of failure probabilities. Thus we that our probabilistic bound is empirically valid all of the time-no not in the sense that each individual shift's error is upper bounded, but rather that the desired violation rate is always satisfied.
Results.
features. When
Strengthening the baselines improve coverage. Since the baselines we consider in this work prioritize predictive accuracy over conservative estimates, their coverage can possibly be improved without too much increase in error. We explore this option using LOOCV: for desired coverage, we learn parameter to either scale or shift a method's prediction to achieve that level of coverage on all but one of the datasets. We then evaluate the method on all shifts of the remaining dataset, and we repeat this for each dataset. Appendix D reports the results for varying coverage levels. We find that (i) the baselines do not achieve the desired coverage on the held out data, though they get somewhat close; and (ii) the adjustment causes them to suffer higher MAE than DIs?. Thus DIs is on the Pareto frontier of MAE and coverage, and is preferable when conservative bounds are desirable. We believe identifying alternative methods of host-hoe prediction adjustment is promising future direction.
9

---

Features
Logits
Logits
10
Oberved Violation Rate
0.30
y=x
68
9.
9:115
Proliction
Proliction
Prediction
0.10
0:23
0.2
02
0.
01)
0.31
Target Accuracy
Target Accuracy
Target Accuracy
Violation Probability
(a)
Figure 4: (a): Scatter plots depicting DIS estimated bound vs. true error for variety of shifts. "w/o 8 indicates that the lower-order term of Theorem 3.6 been dropped. (b): Observed bound violation rate desired probability 8. Observe that the true rate lies at or below across range of values.
6 Conclusion
The ability to evaluate trustworthy, non-vacuous error bounds for deep neural networks under distribution shift remains extremely important open problem. Due to the wide variety of shifts and the complexity of modern data, restrictive a priori assumptions on the distribution (i.e., before observing any data from the shift of interest) seem unlikely to be fruitful. On the other hand, prior methods which estimate accuracy using extra information-sur often rely on opaque conditions whose likelihood of being satisfied is difficult predict, and so they sometimes provide large underestimates of test error with no warning signs.
as unlabeled test samples-
This work bridges this gap with simple, intuitive condition and new disagreement loss which to- gether result competitive error prediction, while simultaneously providing an (almost) guaranteed probabilistic error bound. We also study how the process of evaluating the bound (e.g., the optimiza- tion landscape) can provide even more useful signal, enabling better predictive accuracy. We expect there is potential push further in each of these directions, hopefully extending the current accuracy- reliability Pareto frontier for test error bounds under distribution shift.
Acknowledgments and Disclosure of Funding
Thanks to Sam Sokota, Bingbin Liu, Yuchen Li, Yiding Jiang, Zack Lipton, Roni Rosenfeld, and Andrej Risteski for helpful comments. ER acknowledges the support of NSF via IIS-1909811 IIS- 1955532, OAC-1934584 SG acknowledges Amazon Graduate Fellowship and JP Morgan Al Ph.D. Fellowship for their support.
References
[1] Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In International Conference on Machine Learning, pages 244-253, PMLR, 2018.
[2] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019.
[3] Christina Back, Yiding Jiang, Aditi Raghunathan, and Zico Kolter. Agreement-on on-the oneeee-iinee Predicting the performance of neural networks under distribution shift. In Advances Neural Information Processing Systems, 2022.
[4] Peter Bandi, Oscar Geessink, Quirine Manson, Marcory Van Dijk, Maschenka Balkenhol, Meyke Hermsen, Babak Ehteshami Bejnordi, Byungjae Lee, Kyunghyun Paeng, Aoxiao Zhong, From detection individual metastases classification of lymph node status at the patient level: the camelyon17 challenge. IEEE Transactions Medical Imaging, 2018.
[5] Peter Bartlett, Dylan J Foster, and Matus Telgarsky. Opectrally-normalizee margin bounds for neural networks. In Advances in neural information processing systems, pages 6240-6249 2017.
10

---

[6] Shai Ben-David John Blitzer, Koby Crammer, and Fermando Pereira. Analysis of representations for domain adaptation. In Advances Neural Information Processing Systems, volume 19. MIT Press, 2006.
[7] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jen- nifer Wortman Vaughan. theory of learning from different domains. Machine learning, 79: 151-175, 2010.
[8] Jiefeng Chen, Frederick Liu, Besim Avci, Xi Wu, Yingyu Liang, and Somesh Jha. Detecting errors and estimating accuracy on unlabeled data with self-training ensembles. Advances in Neural Information Processing Systems, 34:14988 19800-4992, 2021.
[9] Mayee Chen, Karan Goel, Nimit S Sohoni, Fait Poms, Kayvon Fatahalian, and Christopher Ré. Mandoline: Model evaluation under distribution shift. In International Conference on Machine Learning, pages 1617-1629, PMLR, 2021.
[10] Yining Chen, Elan Rosenfeld, Mark Sellke, Tengyu Ma, and Andrej Risteski. Iterative feature matching: Toward provable domain generalization with logarithmic environments. In Advances in Neural Information Processing Systems, volume 35, pages 1725-1736. Curran Associates, Inc., 2022.
[11] Gordon Christie, Neil Fendley, James Wilson, and Ryan Mukherjee. Functional map of the world. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018.
[12] Ching- Gao Chuang, Antonio Torralba, and Stefanie Jegelka. Estimating generalization under distribution shifts via domain-invariant representations. International conference on machine learning, 2020.
[13] Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Randaugment: Practical automated data augmentation with reduced search space. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition workshops, pages 702-703, 2020.
[14] Weijian Deng and Liang Zheng. Are labels always necessary for classifier accuracy evaluation? In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 15069-15078, 2021.
[15] Weijian Deng, Stephen Gould, and Liang Zheng. What does rotation prediction tell us about classifier accuracy under varying testing environments? arXiv preprint arXiv:2106.05961, 2021.
[16] Terrance DeVries and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint arXiv: /708. 170.00022, 2017.
[17] Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv: /703. 1008, 2017.
[18] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adwe adversarial training of neural networks. J. Mach. Learn. Res., ((1)):096-2093 jan 2016. ISSN 1532-4435.
[19] Jacob Gardner, Geoff Pleiss, Kilian Q Weinberger, David Bindel, and Andrew G Wilson. Gpytorch: Blackbox matrix-matrix gaussian process inference with gpu acceleration. In Advances in Neural Information Processing Systems, pages 7576-7586, 2018.
[20] Saurabh Garg, Sivaraman Balakrishnan, Zico Kolter, and Zachary C Lipton. Ratt: Leveraging unlabeled data to guarantee generalization. arXiv preprint arXiv:2105.00300 2021.
[21] Saurabh Garg, Sivaraman Balakrishnan, Zachary Chase Lipton, Behnam Neyshabur, and Hanie Sedghi. Leveraging unlabeled data to predict duttt--diitribution performance. International Conference Learning Representations, 2022.
[22] Saurabh Garg, Nick Erickson, James Sharpnack, Alex Smola, Siva Balakrishnan, and Zachary Lipton. Risbench: Domain adaptation under relaxed label shift, International Conference on Machine Learning (ICML), 2023.
11

---

[23] Tom Ginsberg, Zhongyuan Liang, and Rahul G Krishnan. A learning based hypothesis test for harmful covariate shift. In The Eleventh International Conference on Learning Representations. 2023. htttlhttts:///eeeeeee http:p///.pppaereeeeeeeee///rrsr
[24] Devin Guillory, Vaishaal Shankar, Sayna Ebrahimi, Trevor Darrell, and Ludwig Schmidt. Predicting with confidence on unseen distributions. arXiv preprint arXiv:2107.03315. 2021.
[25] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning (ICML), 2017.
[26] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. Computer Vision and Pattern Recognition (CVPR), 2016.
[27] Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. arXiv preprint arXiv: 12261, 2019.
[28] Gao Huang. Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700-4708, 2017.
[29] Minyoung Huh, Hossein Mobahi, Richard Zhang, Brian Cheung. Pulkit Agrawal, and Phillip Isola. The low-rank simplicity bias in deep networks, 2022. URL /tttpp:tt////peereeee/ net/forum? 1d-dn4B7Mes222
[30] David Hume. An enquiry concerning human understanding: A critical edition, volume 3. Oxford University Press on Demand, 2000.
[31] Junguang Jiang, Yang Shu, Jianmin Wang, and Mingsheng Long. Transferability in deep
learning: A survey, 2022.
[32] Yiding Jiang. Vaishnavh Nagarajan, Christina Baek, and J Zico Kolter. Assessing generalization of SGD via disagreement. In International Conference on Learning Representations, 2022.
[33] Bingyi Kang, Saining Xie, Mareus Rohrbach, Zhicheng Yan, Albert Gordo, Jiashi Feng, and Yannis Kalantidis. Decoupling representation and classifier for long-tailed recognition. In International Conference on Learning Representations, 2020.
[34] Polina Kirichenko, Pavel Izmailov, and Andrew Gordon Wilson. Last layer re-training is sufficient for robustness to spurious correlations. arXiv preprini arXiv:2204.0200 2022.
[35] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, Tony Lee, Etienne David, Ian Stavness, Wei Guo. Berton A. Earnshaw, Imran S. Haque, Sara Beery, Jure Leskovec, Anshul Kundaje, Emma Pierson, Sergey Levine, Chelsea Finn, and Percy Liang. WILDS: A benchmark of in-the-wild distribution shifts. In International Conference on Machine Learning (ICML), 2021.
[36] Alex Krizhevsky and Geoffrey Hinton. Learning Multiple Layers of Features from Tiny Images. Technical report, Citeseer, 2009.
[37] Yanghao Li, Naiyan Wang. Jianping Shi, Jiaying Liu, and Xiaodi Hou. Revisiting batch normalization for practical domain adaptation. arXiv preprint 16330:1603 2016.
[38] Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Michael Jordan. Conditional adversarial domain adaptation. Advances in neural information processing systems, 2018.
[39] Philip M Long and Hanie Sedghi. Generalization bounds for deep convolutional neural networks. arXiv preprint arXiv: /2600, 2019.
[40] Yuzhe Lu, Zhenlin Wang, Runtian Zhai, Soheil Kolouri, Joseph Camphell, and Katia Sycara. Predicting out-of-distribution enror with confidence optimal transport. In ICLR 2023 Workshop on Pitfalls of limited data and computation for Trustworthy ML, 2023.
[41] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms, arXiv preprint 03X 2009.
12

---

[42] Vaishnavh Nagarajan and Zico Kolter. Deterministic pac- pac-bayesian generalization bounds for deep networks via generalizing noise-resilience. arXiv preprint arXiv:1905.13344 2019.
[43] Vaishnavh Nagarajan and J. Zico Kolter. Uniform convergence may be unable to explain generalization deep learning. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[44] Preetum Nakkiran and Yamini Bansal. Distributional generalization: A new kind of generaliza- tion. ArXiv, abs/2009.08092, 2019.
[45] Behnam Neyshabur. Implicit regularization in deep learning. arXiv preprint arXiv:1709.0195: 2017.
[46] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm- based capacity control neural networks. In Conference on Learning Theory, pages 1376-1401, 2015.
[47] Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. Exploring generalization in deep learning. arXiv preprint arXiv: 1706,08977 2017.
[48] Behnam Neyshabur; Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of over-parametrizzttion in generalization of neural networks. In International Conference on Learning Representations, 2018.
[49] Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshua V Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's 'ss uncer- tainty? evaluating predictive uncertainty under dataset shift. arXiv preprint arXiv: 02530, 2019.
[50] Matteo Pagliardini, Martin Jaggi, François Fleuret, and Sai Praneeth Karimireddy. Agree to disagree: Diversity through disagreement for better transferability. In The Eleventh International Conference on Learning Representations, 2023.
[51] Xingchao Peng, Ben Usman, Neela Kaushik, Judy Hoffmann Dequan Wang, and Kate Saenko. Visda: The visual domain adaptation challenge, 2017.
[52] Xingchao Peng, Ben Usman, Kuniaki Saito, Neela Kaushik, Judy Hoffman, and Kate Saenko. Syn2real: A new benchmark forsynthetic-to-real visual domain adaptation. arXiv preprint arXiv:1806.09755, 2018.
[53] Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching for multi-source domain adaptation. In Proceedings of the IEEE/CVF international conference on computer vision, pages 1406-1415, 2019.
[54] Mohammad Pezeshki, Oumar Kaba, Yoshua Bengio, Aaron C Courville, Doina Precup, and Guillaume Lajoie. Gradient starvation: A learning proclivity in neural networks. Advances in Neural Information Processing Syxtems, 34:1256-1277 2021.
[55] Emmanouil A Platanios, Hoifung Poon, Tom M Mitchell, and Eric Horvitz. Estimating accuracy from unlabeled data: A probabilistic logic approach. arXiv preprint 1705::/705.07000 2017.
[56] Emmanouil Antonios Platanios, Avinava Dubey, and Tom Mitchell. Estimating accuracy from unlabeled data: A bayesian approach. In International Conference on Machine Learning, pages 1416-1425, PMLR, 2016.
[57] Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint urXiv:/9088 05655, 2019.
[58] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do cifar-10 2018.
classifiers generalize to cifar-10? arXiv preprint
[59] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do cifar-10 classifiers generalize to cifar- 10? 2018. https: //wp/v/r/vvvv/// org/ /ttb////8..... 0045
13

---

[60] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize imagenet? In International Conference on Machine Learning, pages 5389-5400. PMLR, 2019.
[61] Elan Rosenfeld, Pradeep Ravikumar, and Andrej Risteski. Domain-adjusted regression or: Erm may already learn features sufficient for outtof-diitribution generalization. arXiv preprint arXiv:2202.06856 2022.
[62] Elan Rosenfeld, Pradeep Ravikumar, and Andrej Risteski. An online learning approach to inter- polation and extrapolation in domain generalization. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 2641-2657, PMLR, 28-30 Mar 2022.
[63] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journaal of computer vision, 1 115(3):211-22 1-22,, 2015.
[64] Shiori Sagawa, Pang Wei Koh, Tony Lee, Irena Gao, Sang Michael Xie, Kendrick Shen, Ananya Kumar, Weihua Hu, Michihiro Yasunaga, Henrik Marklund, Sara Beery, Etienne David, Ian Stavness, Wei Guo, Jure Leskovec, Kate Saenko, Tatsunori Hashimoto, Sergey Levine, Chelsea Finn, and Percy Liang. Extending the wilds benchmark for unsupervised adaptation. NeurlPS Workshop Distribution Shifts, 2021.
[65] Shibani Santurkar, Dimitris Tsipras, and Aleksander Madry. Breeds: Benchmarks for subpopu- lation shift. arXiv preprint arXiv:2008. 04859, 2020.
[66] Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang. Han Zhang, Colin A Raf- fel, Ekin Dogus Cubuk, Alexey Kurakin, and Chun-Liang Li. Fixmatch: Simplifying semi- supervised learning with consistency and confidence. Advances in Neural Information Process- ing Systems, 33, 2020.
[67] Baochen Sun, Jiashi Feng, and Kate Saenko. Return of frustratingly easy domain adaptation. In Proceedings of the AAAI Conference on Artificial Intelligence, 2016.
[68] Antonio Torralba, Rob Fergus, and William T. Freeman. 80 million tiny images: A large data set for nonparametric object and scene recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 30(1 1):1958- 1970, 2008
[69] Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan. Deep hashing network for unsupervised domain adaptation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5018-5027, 2017.
[70] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. urXiv preprint arXiv: 1.03530, 2016.
[71] Richard Zhang. Making convolutional networks shift-invariant again. In ICML, 2019.
[72] Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael Jordan. Bridging theory and algorithm for domain adaptation. In International Conference on Machine Learning. PMLR, 2019.
[73] Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P Adams, and Peter Orbanz. Non-vacuous generalization bounds at the imagenet scale: pac-bayesian compression approach. arXiv preprint 1rXvv:1804.05882, 2018.
14

---

Appendix
A Experimental Details
A.1 Description of Baselines
Average Thresholded Confidence (ATC). ATC first estimates a threshold on the confidence of softmax prediction (or on negative entropy) such that the number of source labeled points that get confidence greater than match the fraction correct examples, and then estimates the test error on on the target domain Dest as the expected number of target points that obtain score less than f, i.c.
ATC (8) = Σ I(s(((a4) <4,
where satisfies:
[ < Σm arg maxjey fz(2z)) + yil
Average Confidence (AC). Error estimated as average value of the maximum softmax confidence on the target data, i., AC Ei=1 maXjey (zx)).
Difference Of Confidence (DOC). We estimate error on the target by subtracting the difference of confidences source and target (as a surrogate to distributional distance (24)) from the error on
source distribution, i.e., DOCD, E maxjey fa( + Em= |arg maxjey [x;) # yi|
E maxjey (xx)) This is referred to as DOC-Feat in [24]
Confidence Optimal Transport (COT). COT uses the empirical estimator of the Earth Mover's Distance between labels from the source domain and softmax outputs of samples from the target domain to provide accuracy estimates:
R,m
COT D (8)
min rEII(S
Σ 4-=1
|1 ey, Mej
where S
(f{x)} are the softmax outputs on the unlabeled target data and Y {,, 1y=1 the labels on holdout source examples.
For all of the methods described above, we assume that {<+[)] are the unlabeled target samples and ((1s, )) are hold-out labeled source samples.
A.2 Dataset Details
In this section, we provide additional details about the datasets used in our benchmark study.
CIFARIO We the original CIFARIO dataset 36 as the source dataset. For target domains, we consider (i) synthetic shifts (CIFAR10-C) due to common corruptions (27]: and (ii) natural distribution shift, i.e., CIFAR 10v2
55 68 due to differences in data collection strategy. We randomly sample 3 set of CIFAR- datasets. Overall, we obtain 5 datasets (i.e., CIFARIOv1, C0v, CIFARIOC-Fross (severity 4), CIFARIOC-Pixelate (severity 5), CIFARIO-C Saturate (severity 5)).
CIFAR100 Similar to CIFAR10, we use the original CIFAR100 set as the source dataset. For target domains we consider synthetic shifts CCFFAR00-CC) due to common corruptions. We sample 4 CIFAR 100- datasets, overall obtaining 5 domains (i.e., CIFAR 100, CIFAR 100C-ooo (severity 4), CIFAR 100C-Motion Blur (severity 2), CIFARI00C-CCntras (severity 4), CIFAR100C-sppater (severity 2) ).
FMoW In order consider distribution shifts faced in the wild, we consider FMo FMWL-WILDS 35
11 from WILDS benchmark, which contains satellite images taken in different geographical regions and different times. We use the original train as source and OOD val and OOD test splits as target domains as they are collected over different time-period. Overall, we obtain 3 different domains.
Camelyon17 Similar to FMoW, we consider tumor identification dataset from the wilds bench- mark 4. We use the default train as source and OOD val and OOD test splits as target domains as they collected across different hospitals. Overall, obtain 3 different domains.
15

---

BREEDs We also consider BREEDs benchmark 665 in our setup to assess robustness to subpopulation shifts. BREEDs leverage class hierarchy ImageNet re-purpose original classes to be the subpopulations and defines classification task on superclasses. We consider distribution shift due to subpopulation shift which is induced by directly making the subpopulations present in the training and test distributions disjoint. BREEDs benchmark contains 4 datasets Entity- 13, Entity-30, Living-17, and Non-living-266 each focusing on different subtrees and levels in the hierarchy. We also consider natural shifts due to differences in the data collection process ImageNet [63] e.g, ImageNetv2 [60] and a combination of both. Overall, for each the obtain four different
BREEDs datasets (i.e., Entity-13, Entity-30, Living-17. 17, and Non-living-2 domains. We refer to them as follows: BREEDsv sub cuu--ooulation (sampled from ImageNetv I), BREEDsv1 sub-sopul coab--ooplaionn (sampled from ImageNetv 1). BREEDsv2 sub- poolllttpttoonn 1 (sampled from ImageNetv2), BREEDsv2 sub-population 2 (sampled from ImageNetv2). For each BREEDs dataset, BREEDsv sub-population A source and the other three target domains.
OfficeHome We use four domains (art, clipart, product and real) from OfficeHome dataset [69 We use the product domain source and the other domains target.
DomainNet We use four domains (clipart, painting, real, sketch) from the Domainnet dataset We use real domain the source and the other domains target.
Visda We use three domains (train, and test) from the Visda dataset While 'train' domain contains synthetic renditions of the objects, 'val' and 'test' domains contain real world images. To avoid confusing, the domain names with their roles as splits, we rename them as 'synthetic', 'Real-1' and 'Real-2', We use the synthetic (original train set) the source domain and use the other domains as target.
A.3 Setup and Protocols
Architecture Details
For all datasets, used the same architecture across different algorithms:
CIFAR-10: Resnet-18
26
pretrained on Imagenet
CIFAR-100: Resnet-18
26
pretrained on Imagenet
Camelyon: Densenet-121
28
nol pretrained on Imagenet as per the suggestion made in 35
FMoW: Densenet-121
28 pretrained Imagenet
BREEDs (Entity 13, Entity 30,
Living Nonliving26): Resnet-18 [26 not pretrained on Imagenet The main rationale is to avoid pre-training the superset dataset
per the suggestion in (65].
where we are simulating sub-population shift.
Officehome: Resnet-50
26
pretrained on Imagenet
Domainnet: Resnet-50
26
pretrained on Imagenet
Visda: Resnet-50
26
pretrained on Imagenet
Except for Resnets on CIFAR datasets, we used the standard pytorch implementation 19] For Resnet on cifar, refer to the implementation here: https:://p :/ggi thub. com/ hwtp//uuuaantttorrrrrae/ cifar For all the architectures, whenever applicable, we add antialiasing [71]. We use the official library released with the paper.
For pragenet- models with standard architectures, we use the publicly available models here: https::// httpss//pytorch org/vision/ stable/ /oteee/momell..em html For imagenet-pretrann models on the reduced input size images (e.g. 100, we train a model on Imagenet on reduced input size from scratch. We include the model with our publicly available repository.
Hlperpaaameeeer details First, tune learning rate and lg regularization parameter by fixing batch size for each dataset that correspond to maximum we can to 15GB GPU memory. We set the number of epochs for training as per the suggestions of the authors of respective benchmarks. Note that we define the number of epochs as a full pass over the labeled training source data. We summarize learning rate, batch size, number of epochs, and & regularization parameter used in study in Table A.3
For each algorithm, we use the hyperparameters reported in the initial papers. For domain-adversarin methods (DANN and CDANN), we refer to the suggestions made Transfer Learning Library [31 We tabulate hyperparameters for each algorithm next:
16

---

Dataset
Source
Target
CIFARTOv CIEARIÓV2, CIFARIOC-Frox (severity 4),
CIFARIO
CIFARI0v1
CIFAR -ixeelate (severity 5), CIFARIO-C Saturate (severity 5)
CIFARIO0, CIEAR 100C-Fog (severity 4),
CIFARTO0
10F
CIFAR Motion Blur (severity 2), CIFAR 100C-Contrast (severity 4),
CIFARI00C- (severity 2)
Camelyon
Camelyon
Camelyon (Hospital 1-3), Camelyon (Hospital 4), Camelyon (Hospital 5)
(Hospital 1-3)
FMoW
FMoW (2002-"13)
FMoW (2002- 11), FMoW (2013-116), FMoW (2016-118)
Entit13 (ImageNetvl sub popolatian I),
Entity13
Endiy (ImageNetvl sub-population 2).
Entity13 13
(ImageNetvl
Eatit (ImageNetv2 sub-population 1),
sub-population 1)
Entity (ImageNetv2 sub-population
Entit (ImageNetvl sub-population
Entity30 (ImageNetvl
Entity30 (ImageNetv1 sub-population
Entity30
Entity30 (ImageNetv2 sub-population I),
sub-population 1)
Entity30 (ImageNetv2 sub-population 2)
Living17 77 (ImageNetvl sub-population 1),
Living17
Living17 (ImageNetvl sub-population 2).
Living17
(ImageNetvl sub-population 1)
Living17 (ImageNetv2 sub population 1),
Living17 (ImageNetv2 sub-population 2)
Nonliving26 (ImageNetvl sub-population
Nonliving26 (ImageNetv1
Nonliving26 (ImageNetvl sub-population 2).
Nonliving26
Nonliving26 (ImageNetv2 sub- population l),
sub-population I)
Nonliving26 (ImageNetv2 sub tobo-pppulaiion 2)
Officehome
Product Real
Product, Art. ClipArt, Real Real, Puiniting, Sketch, ClipArt
DomainNet
Synthetic
Synthetic, Real-1 (originally referred to as val),
Visda
(originally referred
Real-2 (originally referred to as test)
to as train)
Table A.2: Details of the source and target datasets in our testbed.
Dataset
Epoch
Ratch
8 regularization
T Leaming
CIFARI0
200
0.0001 (chosen from (0.000 1.001,,e-550.00
0.01 (chosen from (0.001,0.01, 0,011, 0..00,,.001)
CIFARI00
50
200
0.0001 (chosen from (0.0001, 0,001, 10-01,1115,,000 0.00)
0.01 (chosen from (0.001,0.01 0.0001})
Camelyon
96
0.01
(ehosen from (0.01, 0.001, 0.0001,0.03)
0.03 (chosen from (0.003, 0.3, 0.0003, 0.03))
FMoW
(ehosen (0. (0.0001, le55,.00)))))
(chosen from (0.001, 0.01, 0.0001
Fatity13
256
5e-5 (chosen from (5e-5, Se-4, Ie-4, le:5))
0.2 (chosen from 10.1, 0,01, 0.00)
Entity30
40
256
5c-5 (ebosen from (5c-5, So-4, Io-4, Ie-5))
0.2 (ebesen from (0.1,
0.01, 0.03)
Living17
40
256
5o-5 (chosen from (5e-5, Io-4, lo-5))
0.2 (chosen from (0.1, 0.5, 0.2, 0.01, 0.00)
Nonliving26
(chosen from (56-5, 5c-4, Ie-4, le-5))
(chosen from (0.1, 0.5, 0.2, 0.01, 0.0))
Officehome
0.0001
(chosen from (0.0001. 0.00 Je.lleS,,, 0.0))
0.01 (chosen from (0.001,0.01,0.0000
DomainNer
96
0.0001
(chosen from (0.0001, 0.001, 1e-111555, 0.03)
0.01 (chosen from (0.001,0.01, 0.0001])
Visda
10
96
0.0001 (chosen from (0.0001, 0.001, 0.001, 0.0g)
0.01 (chosen from (0.001,0.01, 0.0.0.0.00000001
Table A.3: Details of the learning rate and batch size considered our testbed
DANN, CDANN, As per Transfer Learning Library suggestion, use a learning rate multiplier of 0.1 for the featurizer when initializing with pre-trained network and 1.0 otherwise. We default a penalty weight of 1.0 for all datasets with pre-trained initialization.
17

---

Fix.atth
We use the lambda is 1.0 and use threshold 7 as 0.9.
Compute Infrastructure Our experiments were performed across a combination of Nvidia T4, A6000, and V100 GPUs.
B Comparing Disagreement Losses
We define the alternate losses for maximizing disagreement:
1. Chuang et al. [12] minimize the negative cross-entropy loss, which is concave in the model logits. That is, they add the term log softmax (x),)) by) to the objective they are minimizing. This loss results in substantially lower disagreement discrepancy than the other two.
2. Pagliardini et al. [50) use loss which is not too different from ours. They define the disagreement objective for a point (z. y) as
exp(h(z)y) Dty exp()(r)g)
log
(I)
For comparison, Lis can be rewritten as
exp(h(x)))
log
+
(2)
- Eiru h(x)))
exp
where the incorrect logits are averaged and the exponential is pushed outside the sum. This modi- fication results in (2) being convex in the logits and an upper bound to the disagreement 0-1 loss, whereas (T) is neither.
Train
Test
Nepative Cross Entrops
(ours)
Count
201
Disagromment Diserquancy
Disagneement Discrepancy
Loss
Mean Discrepancy (Train)
Mean Discrepancy (Test)
Neg. X-Ent [12
0.3555 + .0124
0.1694 + .0105
D-BAT (50)
0.8145 .0177
0.3224 .0212
Edis (Ours)
0.8333 + .0132
0.3322 + .2055
Figure B.1 Table B.3: Histogram of disagreement discrepancies for each of the three losses, and the average values across all datasets. Bold (resp. Underline) indicates the method has higher average discrepancy under paired t-test at significance p = .01 (resp. p = .025).
Figure B. displays histograms of the achieved disagreement discrepancy across all distributions for each of the disagreement losses (all hyperparameters and random seeds are the same for all three losses). The table below reports the mean disagreement discrepancy on the train and test sets. We find that the negative cross-entropy, being a concave function, results in very low discrepancy. The D- BAT loss (Equation (T) reasonably competitive with our loss (Equation (2) on average, seemingly because it gets very high discrepancy on a subset of shifts. This suggests that it may be particularly suited for specific type of distribution shift, though it less good overall. Though the averages are reasonably close, the samples are not independent, so we run paired t-test and we find that the increases to average train and test discrepancies achieved by fait are significant at levels p = 0.024 and 0.009, respectively. With enough holdout data, reasonable approach would be to split the data in two: one subset to validate crities trained on either of the two losses, and another to evaluate the discrepancy of whichever one is ultimately selected.
18

---

C Exploration of the Validity Score
To experiment with reducing the complexity of the class H. we evaluate Dis on progressively fewer top principal components (PCs) of the features. Precisely, for features of dimension d, we evaluate DIs on the same features projected onto their top d/k components, for (Figure C.2 We see that while projecting to fewer and fewer PCs does reduce the enror bound value, unlike the logits it is a rather crude way to reduce complexity of H. meaning at some point goes too far and results in invalid error bounds.
4, 16, 32, 64, 128]
Full Features
Top 1/4 PCs
Top
10
L0
Deglic
10
02
C4
85
0.5
1.0
62
Taego Accerny
Accerwy
Top 1/32 PCs
Top 1/64 PCs
Top 1/128 PCs
Prudision 2
Protesten R.
00
Eagel Acceaay
Tigge AocereO
Tagel ACCELRO
Figure C.2: DIS bound fewer principal components are kept. Reducing the number of top principal components crudely reduces complexity (1-this leads to lower eπror estimates, but at some point the bounds become invalid for a large fraction of shifts.
However, during the optimization process we observe that around when this violation occurs, the task of training critic both agree on and disagree T goes from "casy" "hard". Figure C.3 shows that on the full features, the critic rapidly ascends to maximum agreement on S, followed by slow decay (due to both overfitting and learning simultaneously disagree on T). ). As we drop more and more components, this optimization becomes slower.
Source Agreement During Training
3.8
Agreeeer
orginal
PC1/1
02-
PCA/36
PCA7 52
PCA/ 54
128
Figure C.3: Agreement on one shift between h and N' on S during optimization. We observe that as the number of top PCs retained drops, the optimization occurs more slowly and less monotonically. For this particular shift, the bound becomes invalid when keeping only the top 1/128 components, depicted by the brown line.
We therefore design "validity score" intended to capture this phenomenon which we refer to as the cumulative ratio. This defined as the maximum agreement achieved, divided by the cumulative sum of absolute differences in agreement across all epochs up until the maximum was achieved.
19

---

improve raw Formally, let {a-)7=1 represent the agreement between h and after epoch i, i.e. 1 - <s h.). and define m arg [ a;- The cumulative ratio is then a -a:-a Thus, the agreement rapidly ascends to its maximum without ever going down over the course of an epoch, this ratio will be equal to and if non-monotonically ascends then the ratio will be significantly less.
am
This definition was simply the first metric we considered which approximately captures the behavior we observed; we expect could be greatly improved.
Valid Bound
Accuracy Minus Bound
0.8
Invalid Bound
0.6
0.4
0.2
0.0
-0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Cumulative & Ratio
Figure C.4: Cumulative & ratio versus error prediction gap. Despite its simplicity, the ratio captures the information encoded in the optimization trajectory, roughly linearly correlating with the tightness and validity of given prediction. It is thus a useful metric for identifying the ideal number of top PCs to use.
Figure C.4 displays scatter plot of the cumulative & ratio versus the difference in estimated and true error for DIs" evaluated on the full range of top PCs. A negative value implies that we have underestimated the error (i.e., the bound is not valid). We that this very simply metric roughly linearly correlates with the tightness of the hound, which suggests that evaluating over range of top PC counts and only keeping predictions whose f ratio is above certain threshold predictive accuracy without reducing coverage by too much. Figure C.5 shows that this is indeed the case: compared D evaluated the logits, keeping all predictions above a score threshold can produce more accurate error estimates, without too severely underestimating error in the worst case.
Logits (0. 15/0.99
Rat9 (0.14/0.96)
Ratio==0.9 0.9 (3.13/0.88)
Ratio =0.8 (0.10/0.33)
Accurcy Pretttton
Accuracy Preditiion
Accuraty Peddeeto
8.6
Accurazy
022
02
022
56
0.5
1.0
012
0.4
0.6
0.8
1.0
0.2
014
0.
0.5
1.0
0.2
0,4
0.6
100
Target Accuracy
Targel Accurazy
Target Accuracy
Targel Accuracy
Figure C.5: 2 bounds and MAE/ coverage as the cumulative L ratio threshold is lowered. Values in parenthesis are (MAE/ coverage). By only keeping predictions with ratio above varying threshold, we can smoothly interpolate between bound validity and raw error prediction accuracy.
20

---

D Making Baselines More Conservative with LOOCV
To more thoroughly compare DIs to prior estimation techniques, we consider strengthening of the baselines which may give them higher coverage without too much cost to prediction accuracy. Specifically, for each desired coverage level a E [0.9, 0.95, 0.99], we use all but one of the datasets to learn parameter to either scale or shift method's 's predictions enough to achieve coverage a. We then evaluate this scaled or shifted prediction on the distribution shifts of the remaining dataset, and we repeat this for each one.
The results, found in Table D.4 demonstrate that prior methods indeed be made to have much higher coverage, although as expected their MAE suffers. Furthermore, they still underestimate emror on the tail distribution shifts by quite a bit, and they rarely achieve the desired coverage on the heldout dataset-though they usually come reasonably close. In particular, ATC [2N and COT 40 do well with a shift parameter, e.g. the desired coverage a 0.95 ATC matches DIS in MAE and gets 94.4% coverage (compared to 98.9% by DIs²). However, its conditional average overestimation quite high, almost 9%. COT gets much lower overestimation (particularly for higher coverage levels), and it also appears to suffer less on the tail distribution shifts in the sense that 0.99 does not induce nearly as high MAE as does for ATC. However, at that level only achieves 95.6% coverage, and it averages almost 5% accuracy overestimation on the shifts it does not correctly bound (compared to % by Dis?). Also, its MAE still substantially higher than DIs?, despite getting lower coverage. Finally, order term, but based on the metrics we report there appears to be little reason to prefer it over the untransformed version, one of the baselines, the original Dis² bound.
evaluate the scale/shift approach
Dis bound without the lower
Taken together, these results imply that one's goal predictive accuracy and tail behavior is not important (worst -10%), ATC or COT will likely get reasonable coverage with shift parameter though they still significantly underestimate error on non-negligible fraction of shifts. one cares about the long tail of distribution shifts, or prioritizes being conservative at slight cost to average accuracy, DIs² is clearly preferable. Finally, we observe that the randomness which determines which shifts are not correctly bounded by DIs² is "decoupled" from the distributions themselves under Theorem 3.6, in the sense that is an artifact of the random samples, rather than a property of the distribution (recall Figure 4(b) This is in contrast with the shift/scale approach which would produce almost identical results under larger sample sizes because it does not account for finite sample effects. This implies that some distribution shifts simply "unsuitable" for prior methods because they do not satisfy whatever condition these methods rely on, and observing more samples will not remedy this problem. It is clear that working to understand these conditions is crucial for reliability and interpretability, since we are not currently able to identify which distributions are suitable a priori.
21

---

MAB (1)
Coverage (t)
Overest. (1)
a
0.9
0.95
0.99
0.9
0.95
0.99
0.9
0.95
0.99
Method
Adjustment
AC
none
0.106
0.122
0.118
shift
0,153
0.201
0.465
0.878
0.922
0.956
0.119
0.138
0.149
scale
0.195
0.221 0.416
0.911
0.922 0.967
0.135
0.097 0.145
DoC
0.105
0.167
0.122
shift
0.158
0.200
0.467
0.878
0.911 0.956
0.116
0.125 0.154
scale
0.195
0,223 0.417
0.900
0.944 0.967
0.123
0.139 0.139
ATC NE
none
0.067
0.289
0.083
shift
0.117
0.150 0.309
0.900
0.944 0.978
0.072
0.088 0.127
scale
0.128
0.153 0.357
0.889
0.933 0.978
0.062
0.074 0.144
COT
none
0.069
0.256
0.085
shift
0.115
0.140 0.232
0.878
0.944 0.956
0.049
0.065 0.048
scale
0.150
0.193 0.248
0.889
0.944 0.956
0.074
0.066 0.044
DIS (w/o 8)
none
0.083
0.756
0.072
shift
0.159
0.169
0.197
0.889
0.933
0.989
0.021
0.010 0.017
scale
0.149
0.168 0.197
0.889
0.933 0.989
0.023
0.021 0.004
DIs 10-2)
0.150
0.989
0.001
DIs2 10-
0.174
1.000
0.000
Table D.4: MAE, coverage, and conditional average overestimation for the strengthened baselines with shift scale parameter only used when an adjustment is learned, "none" "none"_repree" represeniin no adjustment does not vary with a.
representations. Because desired coverage is
22

---

E Proving that Assumption 3.5 Holds for Some Datasets
Here we describe how the equivalence of Assumption 3.5 and the bound in Theorem 3.6 to prove that the assumption holds with high probability. By repeating essentially the same proof as Theorem in the other direction, we get the following corollary:
Corollary E.1. If Assumption doss not hold, then with probability 2 1 8,
2(ns + (r) log 1/6
( > A(h,
ngnr
Note that the concentration term here different from Theorem 3.6 because we are bounding the empirical target error, rather than the true target error. The reason for this change is that now we can make direct use of its contrapositive:
Corollary E.2. With probability 1 8 over the randomness of the samples S and T, if it is the case that
2(ns ny) log 1/5
(7(h) S <g(()) + A(h,))
ngTT
then Assumption 3.5 must hold.
We evaluate this bound on non-domain con-domain-adversarrie shifts with 8 = 10 10-6. As some of the BREEDS shifts have few as 68 test samples, restrict ourselves to shifts with net 2 500 to ignore those where the finite-sample term heavily dominates; this removes a little over 20% of shifts. Among the remainder, we find that the bound in Corollary [.2 holds 55.7% of the time when using full features and 25.7% of the time when using logits. This means that for these shifts, we can be essentially certain that Assumption 3.5 and therefore also Assumption 3.3 is truc.
Note that the fact that the bound is not violated for a given shift does not all imply that the assumption is not true. In general, the only rigorous way to prove that Assumption 3.5 does not hold would to show that for fixed the fraction of shifts for which the bound in Theorem 3.6 does not hold is larger than 5 (in manner that is statistically significant under the appropriate hypothesis test). Because this never occurs in our experiments, we cannot conclude that the assumption is ever false. At the same time, the fact that the bound does hold at least 1 - 6 of the time does not prove that the assumption true-it merely suggests that it is reasonable and that the bound should continue to hold in the future. This is why it is important for Assumption 3.5 to be simple and intuitive, so that we can trust that it will persist and anticipate when will not.
However, Corollary E.2 allows us to make a substantially stronger statement. In fact, it says that for any distribution shift, with enough samples, we can prove a posteriori whether or not Assumption 3.5 holds, because the gap between these two bounds will shrink with increasing sample size.
23

---

Figure SStrtiffe by Training Method
1.0
Target Accuracy Prediction
HRM-aug-imagener
0.8
ERM-an Mag--aug-ie aug-rand
BN adapt
0.6
FixMatch
y=x
0.4
0.2
0.0
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Target Accuracy
Figure F.6: Error prediction stratified by training method. Stars denote Dis circles ATC NE. see that Dis maintains its validity across different training methods.
24


Reviews:
[{"review_id": "nRveTNOiPn", "reviewer": "Reviewer_xsfT", "summary": "The authors propose a novel approach to estimate error bounds for deep neural networks under distributions shift. The proposed bounds remedy the limitations of exiting bounds that either provide vacuous bounds or underestimate the error for a big fraction of shifts while also often requiring access to test labels. In contrast, the bounds proposed by the authors only use unlabeled test data under a simple, intuitive assumption about the hypothesis class's ability to achieve small loss on the unlabeled train and test distributions. More specifically, their approach involves optimizing a disagreement discrepancy between two classifiers using a novel disagreement loss. The experimental results show that the obtained bounds are non-vacuous and comparable to existing competitive baselines. \n\n\n\n", "questions": "- How does the calculation of the bound scale with the size of the dataset and model architecture in practice?\n- In which cases would you expect your bound to be vacuous? ", "limitations": "The authors identified a setting where their proposed bounds may be invalid. The above questions and feedback may help identify more limitations of this work to be explicitly discussed in the main text. ", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The presentation is clear and the paper is overall well-written. The notation is also introduced properly and make the theory easy to follow.\n- The limitations of previous works are also clearly stated and provide a good motivation for this work. \n- One of the main promises of this approach is allowing the user to interpolate between robustness and accuracy depending on the preferred level of risk tolerance.\n- The approach is overall simple and leads to non-vacuous bounds without using test labels. ", "weaknesses": "- The presentation of the results is the main drawback of this work for me! The choice of aggregating all the results over all datasets, shifts, and training methods is strange and does not allow an objective evaluation of the performance of the bounds and analysis of their drawbacks and limitations for the different scenarios. It is possible that the proposed bounds underperform severely on most of the datasets, shifts and training methods and perform exceptionally well on a subset of them. It is also concerning that even the appendix does not include the detailed evaluation for each dataset and shift pair separately. \n- Additionally, we see from Table 1 that the only scenario where the proposed bounds outperform existing baselines is if the concentration term in Theorem 3.6 s dropped at the expense of coverage. Hence, a more detailed and transparent presentation of the results is crucial to verify the claims made by the authors.\n- Including standard errors in Table 1 would also be crucial to verifying the validity of the results given the wide range of scenarios for which the performance was aggregated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback! You’ve stated that you are mostly concerned with missing experimental results, which we are happy to add. **We put preliminary results in our pdf response, which we'll expand on in the paper.**\n\nWe want to briefly explain why these results were not originally included. You believe we may be misrepresenting test error *prediction*, but we emphasize that **the focus of this work is on giving valid, non-vacuous *bounds***, with accuracy being secondary. Our experimental results are meant to emphasize coverage, but also show that we get competitive MAE.\n\n> **“choice of aggregating all the results”**\n\nWe agree that aggregating can obscure information. Our pdf response includes a rough version which stratifies by training method. We observe that **the pattern of accurate error estimation is retained across individual strata.** Preliminary results across datasets indicate that $\\text{DIS}^2$ does better or worse when other methods do: the worst is $.2293 \\pm .062$ (for ATC: $.1736 \\pm .039$; difficult to draw conclusions with large std errors), and the best is $.0766 \\pm .023$ (ATC: $.0758 \\pm .018$).\n\nWe originally aggregated the results because **stratifying presents a *less informative* evaluation of bound validity. Without aggregation, there isn’t enough statistical power to reject the null hypothesis that our bound is valid at the chosen confidence level.** The only way to demonstrate that our method *doesn’t* work is to show a statistically significant difference between the confidence level and the observed bound violation rate (Figure 4b). By stratifying, we would not have enough samples (i.e., shifts) in each group to distinguish between a valid/invalid bound.\n\n> **“it is possible to underperform on most methods and perform well on a subset”**\n\nThe results in the pdf show that this is not the case. This also seems unlikely in general since MAE is bounded in $[0,1]$, so the influence of outliers is limited. Note that this could *not* occur for validity bounds: if our method only gave valid bounds for a small subset, the enforced level $\\delta$ would be violated.\n\nWe hope this distinction is clear and that our new results convince you that our method predicts error robustly. As you’ve indicated that this is your main concern and that you otherwise like the paper, **please let us know if there are additional results you think are missing and we will be sure to include them.**\n\n> **“outperform existing baselines”**\n\nWe again point out that *pure accuracy* is not the focus of this work. We present a non-vacuous error bound under shift, and we are careful to never claim more. **We state as early as the abstract that our method does not do better than predictive baselines.** Where our method *does* outperform existing methods is coverage/reliability. We are unsure how this presentation could be made more transparent.\n\nAs you noted, $\\text{DIS}^2$ matches/outperforms baselines when dropping the concentration term. **This as a *strict improvement*---the other methods provide no coverage guarantees at all!** Dropping the concentration term puts all methods on equal footing for comparing raw accuracy.\n\nWhen reliability is important, we would retain the concentration term. **But now it no longer makes sense to compare $\\text{DIS}^2$ to prior work purely on the basis of MAE, because our method provides guarantees and the other methods do not.** Instead we consider coverage, and our results show that $\\text{DIS}^2$ gets excellent coverage, while retaining competitive accuracy.\n\nWhen coverage is not important at all, other methods may be preferable, as we point out in the paper. We even go so far as to *strengthen the baselines* by exploring ways to improve their coverage without reducing accuracy (Appendix D).\n\n> **including standard errors**\n\nWe’ve recreated Table 1 with standard errors in our pdf. Since “coverage” is a binary variable and we already report $\\hat p$, the only missing data was $n=90$, which is available in the Appendix. Stratified across training methods there is not much variation in MAE: the worst is $.1589\\pm .022$, and the best is $.1360\\pm.024$.\n\n> **Bound calculation scaling**\n\nCalculating the bound is trivial. It takes ~5-10s on one GPU for the largest datasets with $n_{\\mathcal{S}} + n_{\\mathcal{T}} \\approx$ 62K, less than a second for the smaller ones—this could be sped up with stochastic optimization. **It does not scale with the model architecture** because we are optimizing over the frozen features of the network—the cost to extract these features is one pass over the dataset, exactly the same as the cost to evaluate accuracy. The optimization is similarly cheap because it is a convex objective optimized over linear predictors.\n\n> **”When to expect the bound to be vacuous?”**\n\n**This is an important question and crucial to understanding what makes our method so much stronger than prior bounds.**\n\nFor simplicity, consider an interpolating network with 100\\% train accuracy. By definition, our method will give a vacuous bound when there is a linear critic which fully agrees on train and fully disagrees on test. **This is exactly when we would *want* to output a vacuous bound.**\n\nKnowing nothing about the test distribution a priori, we cannot conclude that this critic is less likely to be correct than the network itself. And if it *were* the correct function, it would imply 100\\% test error. Therefore, we cannot rule out the possibility that our network has 100\\% error, and so it is “correct” to output a vacuous bound (assuming our focus is on reliability, as in this work). In other words, the bound will be vacuous precisely when it is “correct” to output a vacuous bound (conservatively). We hope this explanation is clear.\n\n**We are committed to presenting this work transparently, and we will add the metrics you’ve requested. We hope this will convince you to improve your recommendation. Please let us know if you have any additional concerns.**"}, {"review_id": "bGzP8Vk7JG", "reviewer": "Reviewer_rQbE", "summary": "This paper describes a novel method to estimate the error of a classifier under a shift of distribution. It relies on finding a worst case \"critic\" classifier which maximizes disagreement on some unlabeled target domain and hence bounds the disagreement with the true labeling function. The authors apply several necessary ticks to make the bound tractable and non-vacuous: (i) they introduce a new disagreement loss which can be efficiently maximized to find the critique and (ii) they only consider linear critics. While those two aspects make it possible that computed bounds are violated, in practice they show their bound is competitive in terms of mean absolute error while providing a better coverage than other methods.\n", "questions": "See weaknesses. ", "limitations": "Limitations of the approach are mentioned adequately in various parts of the paper. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Clarity: I found the paper well written and enjoyable to read. Presenting complex ideas in simple terms is one of the contribution of this work. Related works are cited adequately, I would only suggest adding [1] which seems also relevant. \n\nOriginality: While I find the insights and derivation not entirely novel---the derivation in [2] also relies on the same idea of bounding disagreement on the target domain with a worst-case critic while agreeing on the source domain---using those with the goal to provide an error bound on the target distribution is novel to me. Furthermore, the authors propose a novel disagreement loss. \n\nSignificance: The proposed approach is simple to implement yet competitive, I can see it being useful to the community. \n\nReferences:\n\n[1] Predicting Out-of-Distribution Error with the Projection Norm (https://arxiv.org/abs/2202.05834)\n\n[2] Agree to Disagree: Diversity through Disagreement for Better Transferability (https://arxiv.org/abs/2202.04414)", "weaknesses": "While they are an extreme case, datasets with completely spurious correlations such as the ones in [3,4,2] might be interesting to consider. For those datasets, the best critic is actually $y^*$. You can then see if your approach recovers the right critic despite your added linearity constraint. As those datasets are shown in [4] to be a failure case when relying on logits, this might fail unless other features are used.\n\nReferences:\n\n[3] Evading the Simplicity Bias: Training a Diverse Set of Models Discovers Solutions with Superior OOD Generalization (https://arxiv.org/abs/2105.05612)\n\n[4] Last Layer Re-Training is Sufficient for Robustness to Spurious Correlations (https://arxiv.org/abs/2204.02937)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks so much for your thoughtful feedback! **We are very happy to hear that you appreciated the presentation; we took great pains to present this work as clearly as possible.**\n\nWe will add the suggested reference [1] to the related work section. We remark that it would not make sense to include this work as a baseline—despite the title, our understanding is that that method does not actually predict error, but rather ranks models to enable model selection.\n\nThanks for the additional datasets; these will certainly contribute a better understanding of the resulting critic. Note that the best critic is a function of the *classifier accuracy*, not the dataset itself. That is, unless the classifier has 0\\% train error and 100\\% test error, it is not the case that the best critic $h^* = y^*$. You are correct that with the linearity constraint we may not recover the best critic, but the advantage of our approach is that *we don’t need to recover $y^\\*$*, which means that *we don’t need the true $y^\\*$ to be linear to give a valid bound!*\n\nWe agree that the derivation is not completely new, and we are careful to properly attribute prior work: we emphasize the connection to $\\mathcal{H}\\Delta\\mathcal{H}$-divergence at several points. On the other hand, **we do feel that the use of this idea to give distribution-free non-vacuous error bounds on modern deep networks under distribution shift**—the first such result, that we are aware of—is quite noteworthy.\n\n**Thanks again for your helpful suggestions. We hope you will advocate for this work during the reviewer discussion.**"}, {"review_id": "clmROeae44", "reviewer": "Reviewer_JSAn", "summary": "This paper provides new error bound of distribution shift based on a notion called disagreement discrepancy. By assuming that the model class has enough expressiveness, it is theoretically proven that the error can be bounded by the worst-case disagreement discrepancy. Empirical investigation shows that such a method provides valid error bounds.", "questions": "1.\tIn line 246, what does “the logits output by $\\hat{h}$” mean?\n\n2.\tThe method bounds the  disagreement discrepancy between h and true label by the worst-case disagreement discrepancy with respect to h. However, when the model class is highly expressive, how we can expect the worst-case bound to be tight?\n\n3.\tDoes the method preserve the order of error? That is, if we have the error of model A is larger than model B, can we observe that the Dis^2 of model A is also larger than model B? \n", "limitations": "Please refer to “weakness”.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe proposed method is novel and interesting. The paper does a great work in demonstrating why such a measure is better than $\\mathcal{H}-$ and $\\mathcal{H}\\Delta \\mathcal{H}$-divergence.\n\n2.\tThis paper provides exhaustive experiments to test the performance of proposed measure.\n", "weaknesses": "1.\tThe writing of this paper can be further polished. For example, the authors can briefly introduce $\\mathcal{H}-$ and $\\mathcal{H}\\Delta \\mathcal{H}$-divergence in Section 3.\n\n2.\tAccording to the experiments, the proposed measure is not better than existing baselines.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback! To address your points:\n\n> **“briefly introduce $\\mathcal{H}$- and $\\mathcal{H}\\Delta\\mathcal{H}$-divergence”**\n\nWe do roughly describe them in Section 3.1, but we will add a more detailed description with the additional space.\n\nYou’ve stated the writing could use improvement—since this is just one example, **could you indicate anywhere else you believe the writing could be improved?** We would very much like to present this work clearly.\n\n> **”the proposed measure is not better than existing baselines.”**\n\nWe acknowledge this point and we tried to clearly convey it several times throughout the paper. **But we do not believe that this constitutes a weakness of our method**. The goal of our approach is to give valid, non-vacuous error *bounds*, with raw accuracy being a secondary objective. We discuss this in more detail in our overall response to all reviewers.\n\n> **what does “the logits output by $\\hat h$” mean?**\n\nRecall that $\\hat h$ is the last layer of the network, which linearly transforms the features $\\phi(x)$ into logits $h^\\top \\phi(x)$ to then produce a vector of probabilities via softmax. We are saying that instead of optimizing the critic on the features $\\phi(x)$, we can also optimize directly on the logits $h^\\top \\phi(x)$ (if there are $k$ classes, the logit space will be $k$-dimensional).\n\n> **”how we can expect the worst-case bound to be tight?”**\n\nThis is an important point and is key to understanding our bound. In fact, assuming the validity condition is met, **our method will give a bound that is exactly as tight as possible. If it gives a loose bound, it means it would would be *improper* to give a bound that is any tighter.**\n\nWe use the term “improper” here to distinguish from “incorrect”. Any bound that is not an equality can of course be tightened while remaining correct. But in this setting, we have *no knowledge* of the distribution shift beyond unlabeled data. Thus, for a given critic which implies large test error, there is no justification for the conclusion that this critic is less likely to be correct than the network itself. And if it *were* the correct function, it would imply the reported error on the test distribution. Therefore, we cannot rule out the possibility that our network has this error, and so it is “improper” to output a bound that is any tighter.\n\n**This is precisely the idea conveyed by Figure 2(c).** Recall that we don’t have labels for the test set (red triangles). Therefore, **both $y^\\* = \\hat h$ and $y^\\* = y_3^\\*$ can be considered equally plausible,** because they both perfectly match the training data. Here, $\\text{DIS}^2$ would return a bound of 0.5. In one possible universe, we have $y^\\* = y_3^\\*$, then $\\hat h$ will have test error 0.5 and our bound will be exact. In another universe our bound may be loose. **But we cannot distinguish between these universes without labels for $\\mathcal{T}$**, and therefore it would be “improper” to output a bound tighter than 0.5.\n\nWe hope the above discussion is clear!\n\n> **”Does the method preserve the order of error?”**\n\nGreat question! The answer can be deduced from Figure 1: “preserving error order” is equivalent to points further to the right on the X-axis also being further to the top on the Y-axis. We see that $\\text{DIS}^2$ does approximately preserve order—there are a few points with a different rank than would be predicted (other methods exhibit the same), but overall we see the desired pattern.\n\nHowever, we also observe that Figure 1 omits an additional factor, namely source accuracy. So one thing we realize would be useful to report is whether $\\text{DIS}^2$ and other methods preserve order in estimating the *drop in accuracy* from source to target. We plotted the result in our pdf response and it looks quite similar to Figure 1—all methods are reasonably order-preserving, with occasional outliers. Thanks for bringing this up!\n\n**We hope our response above (and our general response to all reviewers) answers your questions and that you will consider improving your recommendation. Please let us know if you have any additional concerns.**"}, {"review_id": "fbvpfhMUYD", "reviewer": "Reviewer_TEVz", "summary": "The paper aims to propose a way to characterize the error bounds under distribution shift with provable error guarantees. Based on several assumptions, the authors show that the target error bound can be reasonably estimated by maximizing the agreement within the desired classifier on source distribution and maximizing the disagreement on the target distribution, i.e. $DIS^2$. The authors justified the validity of $DIS^2$ by comparing it to other existing methods both from theoretical and empirical perspectives, and showed that it successfully upper bounds the error under distribution shift. The authors also discussed to what extent the assumptions hold in practice with empirical findings.\n", "questions": "See weaknesses.", "limitations": "Yes, the limitations have been adequately addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The problem of justifying the validity of the trained models under distribution shift is important in modern machine learning. The prior work based on data dependent uniform convergence or assumptions of how distribution shifts are relatively vacuous in practice. The author proposes a method to characterize the error bound of the trained model on target distribution that is theoretically sound with assumptions almost empirically verifiable, making it a significant progress in this area. \n", "weaknesses": "Weaknesses:\n\n1. Although empirical evidence shows that both Assumptions 3.3 and 3.5 are reasonable, the observations are still based on limited data. There could be cases when the assumptions fail to hold. The paper discussed a setting (domain-adversarial learning) where the proposed method $DIS^2$ may be invalid. It is still unclear to me when the assumptions do or do not hold in practice. From a theoretical perspective, is it related to the representativeness of the hypothesis class H? On the empirical side, although except for the adversarial learning case the target function is rarely the worst case, I still feel there could be a possibility. After all that is the whole point of worst-case analysis. Hence, this point of view needs to be supported by more substantive evidence, probably based on real data.\n\n2. The representativeness of the hypothesis class is partly based on how many features the algorithm uses in training. There is a section talking about how the number of features affects the value of the error bound (the logits). It would be interesting to discuss these empirical findings together with hypothesis class representation.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your thorough review! We appreciate that you have recommended acceptance, and that you consider the presentation and contribution of this work to be of high quality.\n\n> **“There could be cases when the assumptions fail to hold”**\n\nWe agree that there are cases where the assumption might not hold. The best we can do in practice is to test our method in a wide variety of settings. We emphasize that **explicitly stating our assumption is strictly superior to not giving any guarantees at all.** Prior methods also make assumptions, implicitly. So, there could just as easily be settings where *their* assumptions fail to hold, but that would be harder to anticipate since *we don’t know what those assumptions are.*\n\n> **”is it related to the representativeness of the hypothesis class H?”**\n\n\nThe validity of the assumption depends on the *interaction* between the capacity of $\\mathcal{H}$, the predictions of $\\hat h$, and the true labeling function $y^\\*$. This cannot be made more mathematically precise without making additional distributional assumptions. Since our intent was to use the weakest assumption possible, we did not go this route. (Very) roughly, you can think of it as assuming that $\\mathcal{H}$ contains a function “somewhat close” to $y^*$ (e.g., if $y^\\* \\in \\mathcal{H}$ then Assumption 3.3 is immediately satisfied).\n\n> **”discuss these empirical findings together with hypothesis class representation”**\n\nWe are not entirely sure we understand you here. Are you suggesting that we move the empirical results on reducing the number of features (i.e., Figures C.4/C.5 in the Appendix) to this section in the main body? Or add some additional discussion there? If you could please clarify we will be happy to flesh out the writing as necessary.\n\n> **”although…the target function is rarely the worst case, I still feel there could be a possibility. After all that is the whole point of worst-case analysis”**\n\n\nWe totally agree. **But all prior methods give vacuous error bounds under shift.** \n\nFundamentally, any guarantee is going to require some assumption. Since all prior assumptions are too weak to give non-vacuous bounds, we need to explore the correct way of strengthening them to make any progress. This work represents one such attempt.\n\nYou wrote that we haven’t provided real evidence that the worst case doesn’t actually happen. We believe the fact that our method consistently works *is* data-based evidence for this claim. Further, as we remark in the footnote on page 5, **the “true” worst case would be precisely 0\\% test accuracy.** As far as we are aware, this doesn’t happen in reality.\n\nOur extensive experiments imply that the assumption holds in practice, which is the most anyone could hope for. If someone doesn’t believe it will hold, that’s fine—but if they want to say anything meaningful at all, they’ll need to choose some *other* assumption to make."}, {"review_id": "64bIrPwy9I", "reviewer": "Reviewer_uhaU", "summary": "The paper proposes a method that under certain assumptions provides upper bounds on the accuracy under distribution shift when provided with unlabelled test data from the shift's target distribution.", "questions": "Why is Method [1] (Agreement-on-the-line) not compared to in the evaluations? This should be possible after it is fit on some other shifted distributions.\n\nCertain assumptions on the distribution shift seem to be necessary, besides the discussed model-specific settings. For example, the bounds would not hold for a shift with similar images but switched class labels. Can such extreme cases be formalized and excluded?", "limitations": "Whether the necessary assumptions hold is extensively discussed and tested for standard distribution shifts. It is however not clear to what kinds of situations one can or cannot expect the method to generalize.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The assumptions necessary to obtain the bounds are clearly stated and discussed.\n\nThe problem of estimating performance under distribution shift is important, and it is not clear whether meaningful bounds are possible. As such, the attempt of providing almost provable bounds in the way that it is done here could be a good contribution in this direction.\n\nThe experimental evaluations are quite extensive and reasonable. Particularly the careful examinations of when the assumptions are fulfilled are important and support these assumptions.", "weaknesses": "The method strongly depends on the function class in which the optimal critic is searched for, and potentially also on its approximation quality within that class. This means that when one allows a perfect critic to be found, which intuitively would look like it should be allowed since it definitely exists if the source and target distributions have smaller overlap than the source test error, then the obtained bounds are vacuous.\nOn the other hand, one can not know a priori whether a function class is large enough to contain a critic that satisfies Assumption 3.3 and thus provides a trustworthy guaranteed bound.\nThese issues are clearly stated and discussed, and it is shown that the necessary assumptions easily hold when considering linear functions on features for standard networks and benchmarks.\nHowever, it is not clear how reliably the method could be transferred to new, potentially less regular datasets and/or models. The bounds after all rely on assumptions that can only be confirmed empirically after the true labels of the target distribution are known.\n\nCompared to other methods, the proposed $Dis^2$ method makes estimates on the accuracy on the target distribution that are worse than simple baselines. This means that the issues of the provability of the bounds mentioned above are important weaknesses.\n\nIn l. 215, it is not clear that the logistic surrogate is still a valid approximation after it is combined with the disagreement logistic loss. The combination of the two losses should be discussed as the sum looks straightforward but has as far as I can see no intrinsic reason to be natural. There is balancing done by leaving out the $1/\\log|Y|$ term, which seems very ad hoc. Other combinations like e.g. sum of squares or other powers of the individual losses would appear just as valid. Would it make sense (for certain function classes) to do a constraint optimization of the disagreement on the target data while fixing the decisions on the source (i.e. $\\epsilon_S{\\hat{h}, h') = 0$)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback! We address your comments below.\n\n> **The bounds…rely on assumptions…confirmed empirically after the true labels…are known** \n\nYou’re correct that we can’t confirm our assumption until the true labels are known. **It’s important to remember that this is true of *every* method, including the baselines.** \n\nThe baselines also rely on assumptions—**their failures imply these assumptions are often not met.** The difference is that their assumptions are *unstated and unknown*, so it’s impossible in to even *guess* whether they will work. Instead, these papers use experiments to show their methods work—most of the time. But when they fail (which is not uncommon), **there’s no way to anticipate it.**\n\nWe present experiments to demonstrate that our method is consistently reliable and accurate. But we also explicitly state a simple condition for guaranteed validity **and this allows us to identify failure cases a priori** (a very useful property).\n\nSince the focus of this paper is on *reliable bounds*, this represents a substantial improvement over prior work. Please see our overall response for further discussion.\n\n> **not clear how reliably the method transfers to new, potentially less regular datasets and/or models**\n\nAs it’s impossible to evaluate on all datasets/models, **this statement is true for *every* ML method.** It is standard to evaluate on a wide set of benchmarks, with the hope that observations transfer.\n\n> **the proposed method…worse than baselines…provability of the bounds mentioned are important weaknesses**\n\nWe agree that absent “true” provability, average accuracy is more important. But **a *true* guaranteed bound under shift is impossible without assumptions.** As we wrote above, the baselines we compare to all rely on *unknown* assumptions which could fail at any time. Further, all prior bounds are vacuous in practice.\n\n**The only way to be really, truly certain of a reliable error bound is to predict 100\\% error.** We hope you agree that we should aspire to do better than that!\nThis means that “reliability” is a continuum—in a given setting, we decide how *important* a valid bound is and choose the appropriate method.\n\nIf “reliable bound” is the goal, **our method represents substantial progress.** Extensive experiments show $\\text{DIS}^2$ consistently gives valid bounds. It does so while allowing us to identify failure cases a priori, at a small cost to overall accuracy. Furthermore, we can give relaxed bounds along the accuracy/reliability pareto frontier—**this is a very useful feature which other methods lack.**\n\nIf reliability is not at all important, then it could make sense to use other methods; we tried to clearly convey this point several times throughout the paper. **But such a setting is not the focus of this work.**\n\n> **Why is Agreement-on-the-line not compared to?**\n\nWe don’t compare to that method as the cost is substantially higher than just training the base model (it requires training many models for *each* distribution shift). In this work we consider methods with negligible overhead beyond training the model being evaluated. However, note that the pattern of severely underestimating test error is present in that method (e.g. the rightmost plots in Figure 1 of that paper).\n\n> **Certain assumptions on the distribution shift seem to be necessary, besides the discussed model-specific settings. For example…with similar images but switched class labels. Can such extreme cases be formalized and excluded?**\n\nWe want to make sure we are understanding this point correctly. Are you saying that **(i)** this example implies assumptions on the distribution are necessary **in addition to** our existing assumption; or **(ii)** simply that one could make a more “fine-grained” assumption to exclude settings such as your example?\n\nIf you mean **(i)**, then we want to clarify that **our bound does not need any additional conditions—Assumption 3.3 already handles this case.** Recall, Assumption 3.3 states that $\\epsilon_T(\\hat h, y^\\* ) - \\epsilon_S(\\hat h, y^\\*) \\leq \\epsilon_T(\\hat h, h^\\* ) - \\epsilon_S(\\hat h, h^\\*)$ where $\\hat h$ is the classifier we are evaluating, $y^\\*$ is the true labeling function, and $h^\\*$ is the critic that maximizes the disagreement discrepancy.\n\nIn the setting you’ve described, there are two possibilities: either (a) the capacity of $\\mathcal{H}$ is large enough to express a critic $h^\\*$ which achieves larger discrepancy than $y^\\*$, or (b) no such critic exists in $\\mathcal{H}$. If (a), $\\text{DIS}^2$ will predict test error close (perhaps equal) to 1. **This bound will be valid *and* very close to the true error.** If we are in setting (b), then the assumption is not met (note that (b) is exactly the negation of (a), and (a) is exactly Assumption 3.3).\n\nIf you meant **(ii)**, note that our assumption *could* be made more mathematically precise as you are suggesting, but only by making additional distributional assumptions. Since our intent was to use the weakest assumption possible, we did not go this route.\n\n> **Logistic loss**\n\nCertainly, other combinations could work; since the precise loss was not our main focus, we didn’t extensively explore other options. The loss we derived works well—better than prior works. Designing alternatives could be an interesting follow-up.\n\nLeaving out the $\\log Y$ term was intentional: since the features are optimized for “agreement” (the data is separable according to $\\hat h$), equal weighting would give an unbalanced objective. We observed this in practice, so we rescaled.\n\nWe did consider constraint optimization! Some algorithms have been designed for this in the fairness literature [1]. Unfortunately they only work for binary classification; we spent some time trying to extend it to multiclass but didn’t want to go too far down that path.\n\n[1] “Predictive Multiplicity in Classification.” Marx et al. 2020"}, {"review_id": "BbEr61Q6xQ", "reviewer": "Reviewer_PQBq", "summary": "This paper try to propose a new metric on evaluation of the distribution shift of dataset. The authors first prove the proposed error estimation bound with some assumptions. Then they demonstrate the effectiveness of their method through training a surrogate model maximizing the disagreement discrepancy. The authors conduct experiments on different dataset, showing that their method never overestimate the prediction accuracy on the target domain.", "questions": "Most questions are listed in the weakness part.\n\nMinor:\n1. Please explain the meaning of '(almost) Provable'", "limitations": "Shown in weakness part", "rating": 3, "confidence": 3, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "1. The authors try to use unlabeled data in the target domain, which is believed can bring benefits on predict the accuracy on the target domain.\n2. The author introduce an interesting conception, named disagreement discrepancy, that represents the maximum difference between the target domain and source domain in the hypothesis set. This conception may provide some insights on the investigation of domain shift.\n\n", "weaknesses": "1. Certain evaluation metrics seem unclear. The reviewer finds it confusing why the method's characteristic of never overestimating the target accuracy—consistently underestimating it—is considered advantageous, particularly when its Mean Absolute Error (MAE) significantly underperforms compared to other methods. The reviewer recommends the authors to illustrate the benefits of this particular feature.\n2. When compared with the baseline methods, the proposed metric falls short in terms of some crucial metrics, such as the Mean Absolute Error (MAE)\n3. The authors attempt to train an additional network by maximizing the discrepancy in disagreement. However, this approach may be time-consuming and unreliable due to its sensitivity to the training hyperparameters.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. \n\nIn your review, you evaluated the soundness as “poor”. We are not sure we understand the reason for this evaluation. Our understanding is that soundness is meant to evaluate the correctness of claims in a given work. Do you believe that our bound or our experiments are not valid? **If not, could you please clarify why you gave this evaluation, so that we can address whatever concerns you have?**\n\n\n* “**The reviewer finds it confusing why…never overestimating the target accuracy…is considered advantageous, particularly when MAE significantly underperforms.**\n\nConsider a scenario where a model will be making crucial decisions: self-driving cars, medical diagnoses, financial agents, etc. If we deploy this model expecting 80% accuracy and its actual accuracy is 20%, the result could be very costly. In this setting, a valid error bound is *essential* and accuracy of an error prediction only matters if we can trust it.\n\nThis is exactly when consistent error overestimation is important. Say we need a *maximum* of 20% error for a model to be reasonably safely deployed. If our method predicts 20% error, you can be quite sure that it’s ok to deploy. If our method predicts 50% error, the model *might* still be ok to deploy—but we probably don’t want to take that chance!\n\nIf you were to use a different method to predict error here and it predicted 10% error, you might then deploy it, only to discover that the *true* error is 50%. **But by then the damage may already be done.**\n\nWe hope it is clear that there are *many* settings where overestimating error is advantageous. Please see our response to all reviewers for more details.\n\n> **”compared with the baseline methods, the proposed metric falls short in terms of some crucial metrics, such as the Mean Absolute Error (MAE).** \n\nWe want to emphasize that **the primary focus of this work is on giving valid, non-vacuous error *bounds***, with accurate prediction being secondary, though still important. We believe we were as upfront as possible about this in our writeup. Indeed, **as early as the abstract we state that we do not beat the baselines purely on MAE.**\n\nWhere our method *does* outperform existing methods is reliability, and it does so substantially. Based on our point above about the need for reliability, we hope you agree that this also represents a meaningful contribution. We discuss this in greater detail in our response to all reviewers.\n\nYou stated that our method falls short on metric***s*** (plural). But we are not sure what other metrics you may be referring to? Our method does *much* better on coverage and has much lower MAE on the (very few) points for which it underestimates error. **Could you please clarify what other metrics you were talking about?**\n\n\n> **”The authors…train an additional network by maximizing the discrepancy in disagreement. However, this approach may be time-consuming and unreliable due to its sensitivity to the training hyperparameters.”** \n\nThis is not correct. Our method trains a *linear* layer on frozen features. This optimization is extremely cheap due to its simplicity and convexity, taking literally seconds. It is also very insensitive to hyperparameters because of the convexity.\n\n\n> **”Please explain the meaning of '(almost) Provable”**\n\n“Almost” is used to highlight the fact that we need an assumption for the bound to hold provably. The error bound is guaranteed if the assumption is valid—but by definition, assumptions cannot be proven a priori, so it cannot be truly guaranteed in all settings. Notably, this is true of *all* methods that predict or bound error (including the baselines), even if they don't state it.\n\nOur extensive experiments across numerous benchmarks show that on natural distribution shifts the assumption holds and our method gives valid error bounds. Hence, though our method works well, “almost” is used to cover extreme scenarios where the assumption may not hold true, making the error bound incorrect."}]

Author rebuttal:
Thanks to all reviewers for their helpful comments and suggestions!

We worked very hard to present this work as clearly as possible, so we are glad to hear that **reviewers xsfT, rQbE, TEVz, and uhaU all found the writing clear and easy to follow (even “enjoyable to read”!)**

A few reviewers pointed out that our method does not match existing baselines on Mean Absolute Error (MAE). We want to emphasize that **the primary focus of this work is on giving valid, non-vacuous error *bounds***, (that is the title of the paper, after all!) with accurate prediction being secondary, though still important. 

We believe we were as upfront as possible about this in our writeup. Indeed, **as early as the abstract we state that we do not beat the baselines purely on MAE.** Where our method does outperform existing methods is reliability and conditional MAE, *and it does so by a huge margin.*

We think that in safety-critical settings where reliability is important, **a minor drop in overall accuracy is a small price to pay for substantially more reliable error bounds.** This is precisely what our method offers.

Consider a scenario where a model will be making crucial decisions: self-driving cars, medical diagnoses, etc. If we deploy this model expecting 80% accuracy and its actual accuracy is 20%, the result could be very costly. In this setting, a valid error bound is *essential* and accuracy of an error prediction only matters if we can trust it. Here the baselines do *very poorly* and our method substantially improves on SOTA—to our knowledge it is the first to give non-vacuous bounds. **If you agree that there are settings where average accuracy is secondary to reliability,** then we see no reason that having slightly worse accuracy should be considered a weakness, given that our method has substantially better coverage.

The main takeaway from our experimental results is that if we *only* care about accuracy, other methods might be preferable, as we state throughout the paper. **But if we are at all worried about overestimating test accuracy then coverage becomes important—and $\text{DIS}^2$ gets *much* better coverage, and has much lower conditional MAE.** We discuss this point further in Appendix D, where we even attempt to *strengthen the baselines*—but we find that our method is still best.

Our response pdf includes an updated Table 1 with standard errors and Figure 1 stratified by training method, as requested by reviewer **xsfT**. The other plot depicts estimated vs. true *drop in accuracy* (as opposed to test accuracy), as suggested by reviewer **JSAn**.

Meta-review: This meta review is based on the reviews, the authors rebuttal and the discussions with the reviewers, discussions with the SAC, and ultimately my own judgement on the paper. There was a majority feeling that the paper contributes sound and interesting contributions. I feel this work deserves to be featured at NeurIPS and will attract interest from the community. I would like to personally invite the authors to carefully revise their manuscript to take into account the remarks and suggestions made by reviewers - in particular, making the goals of the paper more clear might help (this is a concern raised by one of the reviewers, who unfortunately didn't engage with your rebuttal - sorry about this). Congratulations!
Decision: Accept (poster)