On the Bayes Inconsistency of Disagreement Discrepancy Surrogates
Authors: Neil G Marchant
Andrew Craig Cullen
Feng Liu
Sarah Monazam Erfani
Venue: ICLR 2026 Poster (2026)
Keywords: Bayes consistency
distribution shift
disagreeent discrepancy
surrogate losses
adversarial robustness
Primary area: learning theory
TL;DR: Current surrogate objectives for disagreement discrepancy are not Bayes consistent. We prove this and introduce the first one that is.

Abstract: Deep neural networks often fail when deployed in real-world contexts due to distribution shift, a critical barrier to building safe and reliable systems. An emerging approach to address this problem relies on _disagreement discrepancy_—a measure of how the disagreement between two models changes under a shifting distribution. The process of maximizing this measure has seen applications in bounding error under shifts, testing for harmful shifts, and training more robust models. However, this optimization involves the non-differentiable zero-one loss, necessitating the use of practical surrogate losses. We prove that existing surrogates for disagreement discrepancy are not Bayes consistent, revealing a fundamental flaw: maximizing these surrogates can fail to maximize the true disagreement discrepancy. To address this, we introduce new theoretical results providing both upper and lower bounds on the optimality gap for such surrogates. Guided by this theory, we propose a novel disagreement loss that, when paired with cross-entropy, yields a provably consistent surrogate for disagreement discrepancy. Empirical evaluations across diverse benchmarks demonstrate that our method provides more accurate and robust estimates of disagreement discrepancy than existing approaches, particularly under challenging adversarial conditions.

Published as a conference paper at ICLR 2026
ON THE BAYES INCONSISTENCY OF DISAGREEMENT DISCREPANCY SURROGATES
Neil G. Marchant, Andrew C. Cullen, Feng Liu & Sarah M. Erfani School of Computing & Information Systems, University of Melbourne, Australia (nma rchant, andrew. cul len, feng. liul, sarah, erfani @nn mimelllb b. edu
ABSTRACT
Deep neural networks often fail when deployed in real-world contexts due distribution shift, a critical barrier to building safe and reliable systems. An emerging approach address this problem relies on disagreement discrepancy- measure of how the disagreement between two models changes under shifting distribution. The process of maximizing this measure has seen applications bounding error under shifts, testing for harmful shifts, and training more robust models. However, this optimization involves the non-differentiable zero-one loss, necessitating the use of practical surrogate losses. We prove that existing surrogates for disagreement discrepancy are not Bayes consistent, revealing a fundamental flaw: maximizing these surrogates can fail to maximize the true disagreement discrepancy. To address this, we introduce new theoretical results providing both upper and lower bounds the optimality gap for such surrogates. Guided by this theory, we propose novel disagreement loss that, when paired with cross-entropy, yields provably consistent surrogate for disagreement discrepancy. Empirical evaluations across diverse benchmarks demonstrate that our method provides more accurate and robust estimates of disagreement discrepancy than existing approaches, particularly under challenging adversarial conditions.
INTRODUCTION
The reliability of deep neural networks is frequently undermined by distribution shift, where a model's performance degrades when encountering data different from its training distribution (Mansour et al., 2009; Ganin et al., 2016; Long et al., 2018; Duchi & Namkoong, 2021). This challenge a major barrier to deploying safe and robust machine learning systems in the real world. Research to address this has yielded several paradigms. An emerging line of work is based on the concept of disagreement discrepancy (Rosenfeld & Garg, 2023). This refers to measure of how the disagreement between two models-a trainable model and a reference model-changess from a source distribution to a target distribution. Maximizing disagreement discrepancy has proven be versatile, with applications ranging from bounding model eтror on unlabeled target data (Rosenfeld & Garg, 2023), to designing statistical tests for harmful shifts (Ginsberg et al., 2023), and training models with improved robustness to distribution shifts (Pagliardini et al., 2023).
While promising, this line of work harbors a critical, unaddressed challenge. The true objective for disagreement discrepancy involves the non-differentiable zero-one loss, making it incompatible with gradient-buss based optimization. Consequently. all existing methods rely on continuous surrogate losses. This raises fundamental question that has been overlooked: does optimizing the surrogate objective faithfully optimize the true disagreement discrepancy? This concern not merely theoretical; Mishra & Liu (2025) reported instabilities during training, suggesting that current surrogates may be ill-suited for the task.
In this work, we provide the first rigorous analysis of surrogates for disagreement discrepancy. We ground our analysis in the framework of Bayes consistency (Steinwart, 2007). While stronger guarantees like 7 H--oonistenncy exist (Awasthi et al., 2022a:b), their application to the complex models used practice remains an open challenge. Bayes consistency is therefore the crucial first step: a surrogate that is not sound in the asymptotic limit is fundamentally unreliable.

---

Published as a conference paper at ICLR 2026
Our analysis requires extending the standard framework for surrogate loss consistency, originally developed for classification (Zhang, 2004b), to the unique setting of an objective that is a difference of risks. The core of our theoretical contribution is the development of lower and upper bounds on the objective's 's optimality gap. These bounds are analogous to classic excess error bounds from statistical learning theory (Zhang, 2004a; Bartlett et al., 2006). Using this machinery, surrogates are not Bayes consistent, revealing a foundational flaw in current methods. We then design novel surrogate objective that combines the standard cross-entropy loss for the source risk with new disagreement loss that is specifically designed to pair with it. We prove that our surrogate is the first achieve Bayes consistency for the task of maximizing disagreement discrepancy, establishing principled foundation for reliably optimizing these objectives in practice.
prove that existing
We empirically validate our surrogate in the context of two important downstream applications. First, we consider bounding a model's error under shift, following the framework of Rosenfeld & Garg (2023). The validity and tightness of this error bound depend directly on accurately estimating the disagreement discrepancy, maximized over a class of critic models. Our experiments, conducted across an array of vision benchmarks, e.g., WILDs (Koh et al., 2021), BREEDs (Santurkar et al., 2021), 1), and DomainNet (Peng et al., 2019), and training methods, demonstrate that surrogate provides more accurate estimate of this value, achieving a larger maximized disagreement discrepancy than existing surrogates in almost 80% of scenarios tested. Furthermore, we introduce a challenging new evaluation with adversarially chosen target data, where our surrogate exhibits significantly superior robustness. Second, we consider harmful covariate shift detection (Ginsberg et al., 2023), where we show that our consistent surrogate translates to higher statistical power.
By resolving this foundational inconsistency, our work establishes more principled and reliable basis for the use of disagreement discrepancy in analyzing and improving model robustness under distribution shift.
2 RELATED WORK
Our work on the consistency of surrogates for disagreement discrepancy intersects with two main areas: the study of consistency in machine learning and the development of discrepancy-bast based methods for addressing distribution shift. Below we review key literature these areas.
2.1 CONSISTENCY MACHINE LEARNING
Analysis of surrogate objectives in machine learning centers ensuring that optimizing tractable surrogate also optimizes the true, intractable target. This is formalized through a hierarchy of guarantees, each offering different level of assurance. Our work extends this line of inquiry the setting of disagreement discrepancy, which combines risks with differing losses and distributions.
The foundational guarantee is Bayes consistency (Steinwart, 2007), an asymptotic property requiring that the minimizer of the surrogate objective over all measurable functions is also optimal for the target objective. It has been established for convex margin-based losses in binary classification (Zhang, 2004a; Bartlett et al., 2006) and extended to multi-class settings (Tewari & Bartlett, 2007).
more refined asymptotic guarantee is H-consistency (Awasthi et al., 2022a). Instead of considering all functions, it restricts the analysis to a specific hypothesis set H. It requires that the learned model's target risk converges to the risk of the best model within the set H. Recent work has explored H-consistency for binary and multi-class classification (Awasthi et al., 2022a;b; Mao et al., 2023a), as well as for tasks like pairwise ranking (Mao al., 2023b), learning with abstention (Mao et al., 2024), and structured prediction (Mao et al., 2023c). However, these studies generally rely on hypothesis sets (e.g., linear models, lne-layer networks) that are not representative of the complex, deep neural networks used in modern practice. This limited applicability to practical model classes motivates our focus on Bayes consistency as the crucial first step in our analysis.
To formally establish consistency, we use the powerful tool of the excess error bound. This provides quantitative link between the surrogate and target suboptimality, stating that an c-suboptimal surrogate solution is at most f subb-subal for the target. As noted by Awasthi et al. (2022a), such bound is a necessary precursor to any full sinite-sample guarantee, as it provides the link between the statistical error (from finite data) and the true target error. Our work establishes this foundational link for
2

---

Published as a conference paper at ICLR 2026
disagreement discrepancy: prove excess error bound to establish the Bayes consistency of our proposed surrogate, analogous to the classic result of Zhang (2004a).
2.2 DISAGREEMENT DISCREPANCY AND RELATED CONCEPTS
The concept of disagreement discrepancy is closely related to H HLAH-divergence (Ben-David et al., 2010), which measures the maximal disagreement between any two models from a class H. across two distributions. While foundational for error bounds under distribution shift, its direct computation is intractable due to the maximization over all model pairs.
Recent work has operationalized this idea by maximizing disagreement discrepancy with respect only one model (a critic) against a fixed reference model. Rosenfeld & Garg (2023) used this approach bound test error under distribution shift using unlabeled data, proposing a smooth disagreement loss as surrogate for maximizing disagreement. Building on this, Mishra & Liu (2025) introduced a discounted disagreement to address potential instabilities where the source and target domains overlap, resulting in less conservative error bounds. Our analysis shows that the surrogate objectives in these works are not Bayes consistent.
The versatility of this critic-based disagreement framework has led to its adoption in other contexts. For detecting harmful distribution shifts, Ginsberg al. (2023) developed statistical test using an ensemble of classifiers that maximize out-of-domal disagreement while maintaining in-domain consistency. However, our analysis shows that their surrogate, incorporating a disagreement cross- entropy loss, is also inconsistent. Beyond shift detection, Pagliardini et al. (2023) propose D-BAT, which uses a disagreement discrepancy-bars based objective as a diversity- diversity-inducing regularizer for training ensembles. By encouraging agreement between models on training data but disagreement distribution data, they empirically show that the induced diversity can help mitigate shortcut learning and transferabilityy. While empirically successful, the surrogate objective used in their work, like others in the literature, lacks a formal consistency guarantee. Our proposed surrogate provides a direct path to placing such powerful training methods on more reliable theoretical foundation.
out-of-
3 PROBLEM SETTING AND PRELIMINARIES
To formally analyze surrogates for disagreement discrepancy, we first establish our problem setting. We focus on the covariate shift setting in which the input distribution changes from source to target, while the conditional output distribution remains the same. Formally, we define an input space X' with source and target distributions S and T, respectively. The corresponding output space the set of K classes [ [l,..., K) unless otherwise specified. We consider the case where there is a single ground truth output for each input, represented by a labeling function y" X y.
For any subset X' C X, softmax function as (s). e Σ Ee= e for RK and E [K] The indicator function 1 returns 1 if predicate A is true and O otherwise.
S1x* to denote the distribution $ restricted to X". We denote the K
3.1 MODELS
Central to the problem formulation the concept of critic model, used in recent work (Rosenfeld Garg, 2023; Ginsberg et al., 2023; Pagliardini et al., 2023) to maximize disagreement discrepancy with respect to fixed reference models. We denote the critic as f: X Z, where typically 2 is the logit space R Reference models, denoted as h: X' + 3, return raw outputs rather than logits. To accommodate scenarios involving multiple reference models, we use the notation h (/1,12.... fu...... ., (ip) when needed. To convert logits to raw outputs, introduce utility function A + v, which, unless otherwise specified, set to
A(s) min arg max 9; KE[K]
for s E K and we write Az as shorthand for f(x). Here the min operation is a tie-breaking mechanism, selecting the smallest index where multiple logits share the same maximum value.
Formally, for any event C X, we define Sixe (A) = S(4 n S((")) assuming S(2') > 0. "he symbol A is chosen represent this function as it alludes the argmax operation.
3

---

Published as a conference paper at ICLR 2026
3.2 LOss FUNCTIONS AND RISK
We consider loss functions of the form f: X' x 3 x 2 + R. where E(x, z) measures the loss for input & with reference model output y and critic model output Note that while standard losses typically do not depend on H, we maintain this general form to accommodate certain analytical loss functions introduced later. Given loss and reference model h, we define the risk of the critic model f on distribution S as R(e, h, f[( = Ex~s(t(X, f(X), f(X)).
3.3 GENERALIZED DISAGREEMENT DISCREPANCY AND SURROGATES
We now present generalized formulation of disagreement discrepancy that captures the notions considered in recent work (Rosenfeld & Garg, 2023; Ginsberg et al., 2023; Pagliardini et al., 2023). Disagreement discrepancy quantifies the extent to which critic model agrees with reference models differently source and target distributions. Maximizing this measure with respect to the critic has diverse applications, including developing models with robust representations under distribution shift and assessing model's generalization capability to target distributions.
Definition 1 (Disagreement Discrepancy). Let 5, 'T' be the source and target distributions on input space X. For pair of reference models h (h1, h22) and critic model f, we define the generalized disagreement discrepancy as
da h, (| T) = aR(( h2, Af((T) R(ezo, h1 Af)
where (z, y. 3/) 1y is the zero-one loss and a > 0 allows a trade-off between the two terms. For brevity, we omit the a subscript when
Previous work has used specific instances of this generalized formulation:
Rosenfeld & Garg (2023) set h1 h2 to the model under evaluation and 1. Ginsberg et al. (2023) set h1 to the ground truth labeling function, h2 to the model under 1/N where N is the size of the source dataset.
evaluation, and
Pagliardini et al. (2023) set hy to the ground truth labeling function, b2 to separate model trained on source data, and treat a as a tunable hyperparameter.
While the disagreement discrepancy is the ideal objective in the above works, its use of the zero-one loss makes incompatible with gradient-based optimization methods. To address the limitation of non-differentiabblity prior work introduced surrogate objectives. We present a generalized formulation of these surrogates that aligns with Definition 1.
Definition 2 (Surrogate Disagreement Discrepancy). Given loss functions fagr: X' x )' 2 - R IR differentiable their third argument, we define surrogate for generalized disagreement discrepancy as
and lais : X' x Y'y'
(h, T) = R(Lugr, A(S) + aR(Rais h2, [])
where lage encourages agreement and lais encourages disagreement. This surrogate is designed be minimized, unlike d. (S, T), which is designed to be maximized.
Across the literature, the cross-entropy loss
lee y, s) = log os),
(2)
has consistently been employed as surrogate for the agreement loss (Rosenfeld & Garg, 2023; Ginsberg et al., 2023; Pagliardini et al., 2023). In contrast, there no consensus on a surrogate for the disagreement Ioss (Chuang al., 2020; Pagliardini al., 2023; Ginsberg et al., 2023; Rosenfeld & Garg, 2023). Within this work we focus on the disagreement losses proposed by Rosenfeld & Garg (2023) and Ginsberg et (2023):
I'r at)). JRG (x., y, = log ((vu x-11 Eeen
(3)
1
dis y.
Σ logo
K
While both losses are convex and differentiable in s, we show Section 4.3 that they do not yield a consistent surrogate for disagreement discrepancy.
4

---

Published as a conference paper at ICLR 2026
4 CONSISTENCY OF DISAGREEMENT DISCREPANCY SURROGATES
This section presents our theoretical analysis of surrogate losses for disagreement discrepancy. Consistency is crucial property for any surrogate objective, as it provides the guarantee that minimizing the surrogate also leads to a solution for the true, non-differentiable objective. This property forms a vital theoretical underpinning for applications that rely on such surrogates. Our analysis proceeds as follows: we first define Bayes consistency for disagreement discrepancy; then we reformulate the disagreement discrepancy facilitate our analysis; next we prove that existing surrogates are not Bayes consistent; and finally we introduce our novel surrogate and prove its consistency.
4.1 BAYES CONSISTENCY FOR DISAGREEMENT DISCREPANCY
Our goal is to determine whether surrogate objectives faithfully optimize the true disagreement discrepancy. To formalize this, we employ the concept of Bayes consistency, fundamental notion in learning theory that assesses whether optimizing a surrogate loss asymptotically leads to the optimization of the true risk (Zhang, 2004b). We extend this concept to disagreement discrepancy as follows:
Definition 3 (Bayes consistency for disagreement discrepancy). A surrogate d, for disagreement discrepancy da is Bayes consistent if, for any sequence of critic models {fn} and distributions S, T on X.
TT)
inf lalh, ('S, &
N'EH
implies
sup (((,,) du & O. MEN
This definition ensures that when a sequence of critic models optimizes the surrogate objective arbitrarily well (in probability), it simultancously optimizes the true disagreement discrepancy. Bayes consistency provides a theoretical foundation for analyzing surrogate objectives, offering insights into their asymptotic behavior and their relationship to the true disagreement discrepancy. This analysis is particularly valuable given the non-differentiaabiiiy of the true objective, which precludes direct optimization in practice.
4.2 REFORMULATION OF DISAGREEMENT DISCREPANCY
Existing theory for proving consistency of surrogate losses has typically been constructed in terms of objective functions expressible as single risk (Zhang, 2004a; Bartlett et al., 2006; Tewari & Bartlett, 2007). However, the disagreement discrepancy is sum of two risks with respect to different distributions, posing a challenge: we cannot simply apply existing theory to each risk separately, as they are intrinsically coupled from optimization perspective. To overcome this, we present decomposition that rewrites the objective as sum of decoupled risks using pseudo-losses.
To begin, let ps and pr denote the density functions of the source and target distributions, respec- tively.² We define two loss functionals as follows:
(1 (1, v1, pr(x)) ps(x)
12,,,,2((,,5 = ps())2pp(1)
l2 (2 U2 z)
(5)
(ps(x) (r(xx)
L2lh,, (r, y,,, 2) = (p(())<p(())
(1x y1, 2) + l2 U2
for z E X' (V1, y2) E e Z, and losses E,, fz: X x y x 2 + R, where the dependence on and T is implicit.
Using these loss functional templates, we rewrite the disagreement discrepancy
d.(h, (S T) = R(e, (S) + R(2,, h, Af)(T),
We assume density functions exist with respect to common dominating measure. The theory generalizes measure theory by replacing density ratios with Badon-Nikodyy derivatives assuming absolute continuity.
5

---

Published as a conference paper at ICLR 2026
and its surrogate as
d. (4,4,,1(5 [1(, (( [[(S) R((2, h, SI(T),
with pseudo-losses l = L1 220 a fzol. l2 Lz-- lzo: lo; a lz & = L1 [Lagr: a ddis and i L2 Bgg laiel. (See Appendix B for an analysis of the pointwise optimizers of these pseudo-losses.) This reformulation has a crucial property: for any given input æ X, precisely one of E (xx, ;) and (2, y. 2) = 0 is non-zero. The same property holds for the surrogate losses & and lz. This allows pointwise optimization of f. effectively decoupling the two risks in our analysis.
In the following subsections, we leverage this reformulation to prove the inconsistency of existing surrogates and introduce new, consistent surrogate for disagreement discrepancy.
4.3 INCONSISTENCY OF PRIOR SURROGATE
Having reformulated the disagreement discrepancy and its surrogate in terms of pseudo-losses we now analyze the Bayes consistency of existing surrogates. Specifically, we focus on the surrogates proposed by Rosenfeld & Garg (2023) and Ginsberg et al. (2023) and demonstrate they are not Bayes consistent in general. Proofs for this section can be found Appendices A and C.
Our proof strategy extends the framework of Zhang (2004b) by developing lower bound on the optimality gap of the true disagreement discrepancy. While Zhang (2004b) provide an upper bound useful for proving Bayes consistency (which we will employ later), our complementary lower bound is crucial for establishing inconsistency. We first develop this lower bound for a single risk in Appendix A and then apply it to disagreement discrepancy in Appendix C.
The inconsistency stems from fundamental mismatch in the optimal predictions over certain regions of the input space. Specifically, there exist regions where the optimal critic for the surrogate disagrees with the optimal critic for the true disagreement discrepancy. The following theorem formalizes this insight by providing a lower bound on the optimality gap of the true disagreement discrepancy.
Theorem Consider a classification task with K classes, where h: X + [K] is a reference model outputting a pair of class labels and f: X + EK is critic model outputting logits. Let S,T be distributions on X and a > O. For (0, 1) and 5 E (0, 12a),, define restricted input space:
p2( (2) 5 51-
X" TIEE:M1C h200=12()00)))) h2(2)) (x) (b))))) 0,A+85
Let de be either Rosenfeld & Garg's 's surrogate" with lais = RGG X = K/(2K - 2). or Ginsberg dis
et al's surrogate with lais = pGLK X = 1/(K - 1), and lagt = Lee in both cases. Then for both surrogates, there exists convex function Ç 00) [0, 0o) that is continuous at 0 with ((0)= = 5/(1 5)15(x9)20 + ( such that
sup th (((, - dalh, A(S,T) 2 (daal f(SSx,, f'HH
inf feHH
(((5,,,)
The key insight of this theorem is that the lower bound function Ç can be positive at zero, which occurs whenever either the source or target distribution assigns positive measure to the restricted space X". In these cases, a gap remains between the surrogate and true disagreement discrepancy even when perfectly optimized. This violates the Bayes consistency conditions in Definition 3, yielding the following inconsistency result:
Corollary 5. In the setting Theorem 4, the surrogates proposed by Rosenfeld & Garg (2023) and Ginsberg et al. (2023) are not Bayes consistent for disagreement discrepancy when K > 2.
This result exposes a fundamental limitation of these surrogates. It shows that there exist distributions for which optimizing them does not optimize the true disagreement discrepancy, even with infinite data and unlimited model capacity. This underscores the need for carefully designed surrogates, as seemingly reasonable choices may yield suboptimal solutions in certain scenarios.
*We consider generalization of Rosenfeld Garg's surrogate with a >> 0 and distinct reference models.

---

Published as a conference paper at ICLR 2026
4.4 A NEW CONSISTENT SURROGATE
We now propose a new disagreement loss that, when combined with cross-entropy agreement loss, yields consistent surrogate for disagreement diserepancy, with proof' contained in Appendix D.
Our analysis of existing surrogates revealed inconsistencies arising from mismatches between the optimal solutions of the surrogate and true objectives. Addressing this issue, we propose the following disagreement loss:
(9) The design of this loss is motivated by its symmetry with the cross-entry agreement loss (2). While minimizing cross-entropy agreement loss log (s),, encourages agreement with y by setting (s) our disagreement loss - logg(1 a (s))y) encourages disagreement with y by setting (s)y = O. Importantly, our disagreement loss doesn't It specify how the remaining probabilities should be configured, aligning with the true disagreement loss - This symmetry and alignment with the true losses contribute to the consistency of our surrogate.
Ouur (I, y, s) = - log (1 - -s))))
dis
To formally establish consistency, we employ the framework Zhang (2004b), which provides an upper bound on the optimality gap for a true risk in terms of the optimality gap of a surrogate risk. We extend this result to disagreement discrepancy, leveraging our reformulation of the objective as a sum of two disjoint risks. The resulting upper bound is presented in the following theorem:
Theorem 6. Consider classification task where h: X - [K] a reference model outputting pair of class labels and f: X + RRK is a critic model outputting logits. For any a > 0, let d be our surrogate with Edis- (Ouur and lagr hew Then, for any distributions S, T on X, there exists concave function & [0, xc) + [0, o.) that is continuous at O with E(O) = 0, such that
sup (h, (S) - th A(S, SE SEW
(d (d ((al.))s((( ((S,T) - inf dalh, (((..))) NEH
This result is analogous to the classic excess error bounds from statistical learning theory (Zhang, 2004a), adapted here for objective that is not traditional risk/emror. As diseussed in Section 2.1, this type of bound is the crucial component for controlling the calibration error in a full finite-sample analysis. The key property of the bounding function in our theorem is that it is continuous 0 with E(0) = O. This property ensures that as the surrogate optimality gap vanishes, so too does the true optimality gap, which directly leads to the following consistency result:
Corollary 7. Our surrogate for disagreement discrepancy with cross-entropy agreement loss and the disagreement loss specified (9) is Bayes consistent for all K 2 2.
In guaranteeing that optimizing our surrogate will optimize the true disagreement discrepancy, in the limit of infinite data and unrestricted model capacity, we are able to address the fundamental limitations in prior works. This also provides the theoretical foundation for the use of our surrogate in applications involving disagreement discrepancy.
Remark 8. Theorem and Corollary 7 also hold for the surrogates of Rosenfeld & Garg (2023) and Ginsberg et al. (2023) when K 2, as they equivalent our surrogate in the binary setting.
5 EMPIRICAL EVALUATION OF SURROGATES
We evaluate our surrogate on two downstream applications where maximizing disagreement discrep- ancy is central: bounding model error under covariate shift and detecting harmful distribution shifts. In both cases, the validity of the downstream result depends accurate optimization of the true disagreement discrepancy.
5.1 APPLICATION: ERROR BOUNDS UNDER COVARIATE SHIFF
We first consider the framework of Rosenfeld & Garg (2023) for bounding model error under covariate shift. Their key result is a probabilistic upper bound, composed of three terms: the empirical source error, sample correction term, and the empirical disagreement discrepancy (see Appendix E).
Crucially, the disagreement discrepancy term is estimated by optimizing a surrogate for disagreement discrepancy, and the reliability of the entire bound depends the quality of this optimization. As
7

---

Published as a conference paper at ICLR 2026
Disorepnccy
100
0.20
Observed vislation rateo
0.75
70-
0.15
Surrogate
c:50
Surogate Our
50+
RG23
6.25-
Mo:
0.00
0.85
3.50
0.75
0.00
0.00
0.100
0.15
0.20
Disagreement Discrepancy
Desired violation rate,
Comparison of disagreement discrepancy esti- mates for each surrogate. Left: Estimated vs. maximum achieved discrepancy across 130 shifts/models, where prox- imity to dashed line indicates better performance. Right: Frequency of achieving maximum discrepancy.
Figure 1:
Figure 2: Calibration of error bounds: observed vs. desired violation rates (6). The dashed y line represents per- feet calibration. Our surrogate demon- strates improved calibration.
will show, underestimating the true disagreement discrepancy-a risk with inconsistent surrogates- yields deceptively tighter bound that may be invalid (i.e., the true eπror exceeds the bound). This provides rigorous testbed for our work: better surrogates recover larger discrepancies and yield more trustworthy eтror bounds.
Our experiments evaluate how different surrogates for disagreement discrepancy affect the error bound's 's performance, replicating the setup of Rosenfeld & Garg (2023) under natural shifts (Sec- tion 5.1.1) and extending scenarios with adversarially chosen target data (Section 5.1.2).
5.1.1 REPLICATION OF EXPERIMENTS WITH EXISTING AND NEW SURROGATES
To compare the effectiveness of our surrogate with that of Rosenfeld & Garg (2023), we focus on the disagreement discrepancy term of the error bound mentioned above (see Theorem 21 in Appendix for details). A larger value of this term indicates better estimate for fixed critic hypothesis class H.
We replicated the experiments of Rosenfeld & Garg (2023) using their code, evaluating our proposed surrogate alongside theirs across 11 vision benchmark datasets for distribution shift. Models under evaluation (h) were trained on source data using empirical risk minimization (ERM) or one of four unsupervised domain adaptation methods: FixMatch (Sohn et al., 2020), BN-adapt (Li et al., 2017), DANN (Ganin et al., 2016) or CDAN (Long et al., 2018). The critic model was constructed by appending tunable linear layer to the frozen weights of h, transforming the original logits.
Figure/ compares the disagreement discrepancies achieved by each surrogate against the maximum across 130 shift and model combinations. Since the true maximum is intractable, use the largest value achieved by any surrogate in each scenario as practical reference. Our surrogate attains this maximum in nearly 80% of cases, indicating stronger estimates of the true disagreement discrepancy. one-sided Wilcoxon signed-rane raak test also confirms its superiority (p = 1.8 x 10-1
These results are complemented by Figure 2, which reports the calibration of error bounds for each surrogate. Our surrogate yields better calibration than Rosenfeld & Garg's s across most 8 values, producing more reliable bounds, though both methods show elevated violation rates for small 6. Appendix G.I provides additional comparisons of error bounds versus actual errors, disaggregated by training method and critic architecture.
5.1.2 ROBUSTNESS TO ADVERSARIALDS CHOSEN TARGET DATA
To further assess the reliability of error bounds, we extend our evaluation to scenarios with adver- sarially chosen target data setting not considered in prior work. This stress test provides crucial insights into how the bounds perform under more challenging conditions.
While adversarially chosen target data not considered by Rosenfeld & Garg (2023), still closely following their experimental setup, using 8 of their datasets and focusing on models trained with ERM. We construct adversarial target data by iteratively maximizing the gap between the bound
8

---

Published as a conference paper at ICLR 2026
0.P5
Surrogate
Ours
Disagreement
0.25
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Dieagreement Discrepancy
Surrogate
Ours
RG28
074
25%
50%
75%
100% DPL
25%
50%
75%
100%% Dns
25%
50%
75%
100% DN
25%
50%
75%
100%
Rate
Figure 3: Comparison of disagreement discrepancy estimates for each surrogate under adversarial attacks on target data. Top: Estimated vs. maximum achieved disagreement discrepancy for each surrogate (GLK23, Ours, RG23), faceted by fraction attacked instances. Points closer to the dashed line indicate better performance. Bottom: Corresponding bar plots displaying the rate at which each surrogate achieves rank (highest), 2, (lowest) disagreement discrepancy.
and true target error, subject to -norm constraints. Across our experiment set, we test different fractions of attacked data f. using values of 0%. 12.5%, 25% and 50%. Further details of our attack procedure and experimental setup can be found in Appendices F and G.2, respectively.
Figure 3 compares our surrogate with those of Rosenfeld & Garg (2023) and Ginsberg et al. (2023) in estimating the maximum disagreement discrepancy under adversarial target data. Results shown as scatter plots each surrogate's ' estimate versus the maximum achieved across surrogates for that scenario, faceted by the attack fraction f. Accompanying rank plots show the frequency with which each surrogate achieves the top estimate. Our surrogate exhibits strong robustness, achieving the highest estimate in 87.5% of cases for f 0%, rising to 100% for f = 50%. A one-sided Wilcoxon signed-rank test against a composite baseline (the best of the RG23 and GLK23 surrogates) confirms this advantage across all f. with p 3.3 10- results indicate that our surrogate provides more reliable discrepancy estimates under adversarial conditions, enabling more robust error bounds. Additional results, including comparisons of true error versus bounds and breakdowns by shift, appear in Appendix G.2.
0% and p < 6.0 10-10 for 0%. These
5.2 APPLICATION: DETECTING HARMFUL COVARIATE SHIFT
Maximizing disagreement discrepancy also serves as powerful mechanism for detecting distribution shift. We explore this application using the Detectron framework (Ginsberg et al., 2023), which detects harmful covariate shift for a deployed model via a hypothesis test. Specifically. a critic model is trained to maximize disagreement discrepancy with h unlabeled target data; if the resulting disagreement rate significantly exceeds the rate expected under the source distribution, the shift is flagged harmful.
To assess the role of surrogate consistency in this setting, we adopt the experimental setup of Ginsberg al. (2023) on the UCI Heart Disease (HD) dataset (Andras Janosi, 1989). We retain the original 5-class labels (disease severity) rather than the binary target used in prior work, as our surrogate and the baseline coincide when K 2. We train XGBoost (Chen & Guestrin, 2016) critics, comparing our surrogate against the GL.23 baseline (see Appendix G.3 for details). We vary the number of target samples N {10, 20, 50), and repeat each experiment 500 times to estimate ROC curves. Confidence intervals for the AUC and ROC curves are computed using stratified bootstrapping with 1000 samples.
Figure 4 and Table I present the results. Our surrogate consistently outperforms the baseline across all sample sizes. As shown in Table 1, the 95% confidence intervals for the AUC do not overlap between the two methods for any N. confirming that the improvement is statistically significant in both low-data and higher-data regimes. These results suggest that for this task, the theoretical consistency of the loss function translates to improved statistical power.

---

Published as a conference paper at ICLR 2026
N
Surrogate
AUC-ROC
1.30
0.75
10
GLK23
0.821
+0.025
-0.025
Ours
0.908
+0.019
-0.017
0.28
20
GLK23
0.913
+0.016
-0.019
0.00
Ours
0.984
-0.006
++0
0.0
0.1
0.2
08
0.4
0.50.0
0.1
D.
0.3 FPR
0.4
0.50.0
0.1
0.
033
0.4
0.5
50
GLK23
0.995
+00003
00.002
Surrogate
Ours
1.000 -0.000
++0.000
Figure ROC curves for harmful shift detection on UCI-HD. Error bars indicate 95% bootstrapped confidence intervals.
Table 1: AUC-ROC for shift detec- tion on UCI-HD.
6 CONCLUSION
Disagreement discrepancy has emerged powerful framework for addressing distribution shift, with applications spanning error bounding, shift detection, and robust model training. However, this work reveals a fundamental theoretical flaw: existing surrogate objectives for disagreement discrepancy are not Bayes consistent, meaning that optimizing these surrogates can fail to optimize the true disagreement discrepancy. This inconsistency undermines the theoretical foundations of methods that rely these surrogates and may explain practical instabilities reported in prior work.
Our theoretical analysis provides both upper and lower bounds on the optimality gap between true and surrogate objectives, establishing comprehensive framework for understanding surrogate quality in this setting. Guided by this theory, we propose a novel disagreement loss that, when paired with cross-entropy, yields the first provably Bayes consistent surrogate for disagreement discrepancy. Our empirical evaluation demonstrates that this theoretical improvement translates to practical benefits in downstream applications: our surrogate consistently yields more reliable error bounds under covariate shift, particularly under adversarial conditions, and achieves higher statistical power for detecting harmful covariate shifts.
While our focus on Bayes consistency considers optimization over the class of measurable functions, this choice is deliberate and necessary. H-consistency (Zhang & Agarwal, 2020), while theoretically appealing for its consideration of restricted hypothesis classes, remains limited in practice- no successful H-consistency analysis exists for the deep neural networks used in modern applications. Bayes consistency therefore provides an appropriate and achievable foundation for establishing the soundness of surrogate objectives before pursuing more restrictive analyses.
Our work opens several promising directions. A full finite-sample guarantee requires bounding both the calibration error (the gap between surrogate and target objectives) and the estimation error bound directly addresses the former. The next challenge is to
(arising from finite samples); develop bounds on the estimation error for disagreement discrepancy. Moreover, while our surrogate resolves the consistency issue, assumptions underlying applications like error bounding may not always hold, as demonstrated by our adversarial experiments. This underscores the need for care when deploying these methods in practice.
By establishing the first consistent surrogate for disagreement discrepancy, our work provides a principled theoretical foundation for this important class of methods. This contribution not only resolves existing inconsistencies but also paves the way for more reliable and robust approaches to handling distribution shift in machine learning systems.
REPRODUCIBILITY STATEMENT
Complete proofs for all theoretical claims, including the inconsistency of existing surrogates (The- orem 4, Corollary 5) and the consistency of our proposed surrogate (Theorem 6, Corollary 7), are provided in Appendices C and D respectively. The general framework for proving inconsistency is detailed in Appendix A. All mathematical assumptions and conditions are explicitly stated within these proofs.
10

---

Published as a conference paper at ICLR 2026
Detailed experimental configurations provided in Appendix G. For the replication experiments in Section 5.1.1, we utilize the publicly available code and datasets released by Rosenfeld & Garg (2023), with our modifications clearly documented. For the adversarial robustness experiments in Sec- tion 5.1.2, we provide complete source code at pre-processing, model training, attack implementation including scripts for dataset downloading and pre-procese (detailed in Appendix F), and generation of all figures and tables. For the harmful shift experiments in Section 5.2, we use the public code released by Ginsberg et al. (2023), with modifications clearly documented in Appendix G.3.
ACKNOWLEDGMENTS
The authors would like to thank Chris Leckie, Amar Kaur and Paul Montague for their valuable input during the course of this research project. This work was supported by the Australian Defence Science and Technology Group via the Advanced Strategic Capabilities Accelerator program and the University of Melbourne's 's Research Computing Services and Petascale Campus Initiative.
REFERENCES
William Steinbrunn Andras Janosi. Heart disease, 1989. URL http:://rrchve....s.....ccaaaas
Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong. H-consistency bounds for surrogate loss minimizers. In Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pp. 1117-1174, 17-23 Jul 2022a. URL I 62/awasthi22c.hin
https://rooceedingssu 16l
Pranjal Awasthi, Anqi Mao, Mehryar Mohri. and Yutao Zhong. Multi-class H- consistency bounds. In Advances Neural Information Processing Systems, vol- 35, pp. 782-795, 2022b. URL https://rrocedingg.eeuriii wtw.:/ddiinns.eurss.scc.eoeoeeee necpaps files/paper/2222/illl 11139977af1dd55daal
43977647228--Paapppp Papper-Conferenee.pff. 14977
Peter Bartlett, Michael Jordan, and Jon McAuliffe.
Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):188-556, 2006. doi: 111119800122145500000000
URL https://doi.or//10.. htt.0///0000.0000010000000000000
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine Learning, 19(1):151-175, 2010. doi:
Tianqi Chen and Carlos Guestrin. XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '16, p 785-794, 2016. doi: 10. 145/2999672..29377555 URL https::/doi.orgg// 1145/293667..
2939785.
Ching- Cao Chuang, Antonio Torralba, and Stefanie Jegelka. Estimating generalization under dis- tribution shifts via domain-invariant representations. In Proceedings of the 37th International Conference Machine Learning. volume 119 of Proceedings of Machine Learning Research, pp. 1984-1994, 13-18 Jul 2020. URL https:/pproceedings mlr, press/v 199chhang20a.httml
John C. Duchi and Hongseok Namkoong. Learning models with uniform performance via dis- tributionally robust optimization. The Annals of Statistics, 49(3):1378 1406, 2021. doi: 10.1214/00AA02200 URL
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François training neural networks.
Laviolette, Mario March, and Victor Lempitsky. Journal of Machine Learning Research, 17(59):1-35 2016. URL http://jmll:orr/ppppers/// 15- 15-239.html..
Tom Ginsberg, Zhongyuan Liang, and Rahul G Krishnan. A learning based hypothesis test for harmful covariate shift. The Eleventh International Conference on Learning Representations, 2023. URL http:://opemeeieeeeee/tmmddddddd

---

Published as a conference paper at ICLR 2026
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness common corruptions and perturbations. In International Conference on Learning Representations, 2019.
URL http::///pnneeeeeee////ono/mmmna
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), July 2017.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsub- ramani, Weihua Hu, Michihiro Yasunaga. Richard Lanas Phillips, Irena Gao. Tony Lee, Etienne David, Ian Stavness, Wei Guo, Berton Earnshaw, Imran Haque, Sara M Beery, Jure Leskovec, Anshul Kundaje, Emma Pierson, Sergey Levine, Chelsea Finn, and Percy Liang. WILDS: A benchmark of in-the-wild distribution shifts. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 5637-5664, 18-24 Jul 2021. URL https://proceedings mrr..ssss/y 139/11199///l a.hmml.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, April 2009. URL http:://www.e..oooottoedddd learning- features- 2009-TR,pdl
Yanghao Li, Naiyan Wang, Jianping Shi, Jiaying Liu, and Xiaodi Hou. Revisiting batch normalization for practical domain adaptation, 2017. URL https//opeenevvew.ee///oummm httpe///ooorummmd//u///oeeeee
Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Michael I Jordan. Conditional
adversarial domain adaptation. In Advances in Neural Information Processing Sys- tems, volume 31, 2018. URL http://poceeddngg.euuuipspccoc pttprrpp..ppppppppillpppppp/pppp :b88805773354337788860022 108dd8 pff.........
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In Proceedings The 22nd Annual Conference on Learning Theooy (COLT 2009),
Montréal, Canada, 2009, URL http://ww..c..
http://www.cs.yy..co www.ws.ww..e../..... wwwh////oorr//pssscip//nadd
Anqi Mao, Mehryar Mohri. and Yutao Zhong. H-consistency bounds: Characteriza- tion and extensions. In Advances in Neural Information Processing Systems, vol- ume 36, pp. 4470-4508, 2023a. URL https://pnoceeddngs.neue hww.r//nnnnnuurisccc//ppppoo files/paper2002//lll//
Anqi Mao, Mehryar Mohri, and Yutao Zhong. h-consistency bounds for pairwise misranking loss surrogates. Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 23723-344322 233022, 23-29 Jul 2023b. URL https//pooceedins..lrrsssss/ wwtpmr/rses///222222...mm.
Anqi Mao, Mehryar Mohri, and Yutao Zhong. Structured prediction with stronger consis- tency guarantees. In Advances in Neural Information Processing Systems, volume 36, pp. 46903-46937 2023c. URL PaaeeeaaeaaCCCoooeeeeeeeeeepppp 92776628886377777 10016991111-PPP
Angi Mao, Mehryar Mohri, and Yutao Zhong. Theoretically grounded loss functions and algorithms for score-based multi-class abstention. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 4753 4761, 02 04 May 2024. URL https://proceedingg mir, 2asppreres/222/m224.aaaaa
Aayush Mishra and Anqi Liu. ODD: Overlap-aware estimation of model performance under dis- tribution shift. In The 41st Conference on Uncertainty in Artificial Intelligence, 2025. URL
Matteo Pagliardini, Martin Jaggi. François Fleuret, and Sai Praneeth Karimireddy. Agree disagree: Diversity through disagreement for better transferability. In The Eleventh International Conference Learning Representations, 2023. URL. http::///pppaaeeeeeetetoo///lt/o
12

---

Published as a conference paper at ICLR 2026
Xingchao Peng, Ben Usman, Neela Kaushik, Dequan Wang, Judy Hoffman, and Kate Saenko. VisDA: A synthetic-to-red benchmark for visual domain adaptation. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR) Workshops, June 2018.
Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching for multi-source domain adaptation. Proceedings of the IEEE/CVE International Conference on Computer Vision (ICCV), October 2019.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do CIFAR-10 classifiers generalize CIFAR-107, 2018. URL https:///aaii..or//aaaaaaa http//aass//100.0000 806.00451. arXiv: 1806 306.00451 [cs.LG]
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do ImageNet classifiers generalize to ImageNet? Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5389-5400, 09-15 Jun 2019, URL http://pwweeednn..mmmmrree/s//// 1tt.t//////ecttth.....
Elan Rosenfeld and Saurabh Garg- (Almost) provable error bounds under distribution shift via disagreement discrepancy. In Advances in Neural Information Processing Systems, vol- files/paper/2223/ile//
ume 36, pp. 28761-28784, 2023. URL http://ppoccdddnng..uuur.s..o//s Papee-Cooonooffeeeeeppp
5bach1 655
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei- Fei. ImageNet large scale visual recognition challenge. International Journal of Computer Vision, 115(3):2 Dec 2015. ISSN 1573-1405. doi: 10.1007/s 10.1007/11126--15--886666 URL https:/dooi.org/ 10. 1007/s 123-011-0816.-
Shibani Santurkar, Dimitris Tsipras, and Aleksander Madry. BREEDS: Benchmarks for subpopulation shift. In International Conference Learning Representattons, 2021. URL https://openreview.
net/forum Senfforumiid=mQPPPe My
Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raffel, Ekin Do- gus Cubuk, Alexey Kurakin, and Chun-Liang Li. FixMatch: Simplifying semi-supervised learning with consistency and confidence. In Advances Neural Information Processing Systems, vol- ume 33, pp. 596-608, 2020. URL http:://noeedding.earrrss..ooppp httpapprr.illsspppee////////e/ (0966ddccaabble6555eee3333337773 Pd.....d..
Ingo Steinwart. How to compare different loss functions and their risks. Constructive Approximation, 26(2):225-287, 2007. doi: 10. 10.11007//000665-000-006666
Ambuj Tewari and Peter L. Bartlett, On consistency of multiclass classification methods. Journal of Machine Learning Research, 8(36):00071005,, 2007. URL html.
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 (CVPR), July 2017.
Mingyuan Zhang and Shivani Agarwal. Bayes consistency H-consistency: The interplay between surrogate loss functions and the scoring function class. In Advances in Neural Information Processing Systems, volume 33, pp. 16927-16936, 2020. URL http://proceedins..eurri www.riissn.euriss... ccl
Tong Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1):56-85, 2004a. ISSN 00905364. URL http://www.
jstor.orgstaalle/444444.
Tong Zhang. Statistical analysis of some multi-category large margin classification methods. J. Mach. Learn. Res., 12112-1251111 December 2004b. ISSN 1532-4435. URL https://mllr.rr//pperrs//
wolume5/hhnggg0/ZZnngguo..
13

---

Published as a conference paper at ICLR 2026
A GENERAL FRAMEWORK FOR PROVING INCONSISTENCY
This appendix presents a general framework for proving the inconsistency of surrogate loss functions in the context of single risk objective. While the main focus of our paper is on objectives that are sum of two risks over different distributions with different losses (i.e., the disagreement discrepancy), the results developed here for a single risk serve as crucial building block for our later analysis.
We adapt and extend the upper bound of Zhang (2004b. Appendix A) to develop lower bound on the optimality gap of a target objective in terms of the optimality gap of surrogate objective. This lower bound is crucial for proving inconsistency, as it allows to show cases where optimizing the surrogate does not necessarily lead to optimizing the true objective.
Our framework considers true loss function f X' y x 21 - IR and a surrogate loss function è: xxXxy'22 22 > IR. The true objective is to select critic model f: X - Zg that minimizes the risk RiC, h. AD) and the surrogate objective is to minimize the risk R(é, h. f](D). Here A: Z Z1 a mapping between model output critic models in pointwise optimizable hypothesis class H = [s: X 22}. which is relevant for Bayes consistency, Central to our analysis is the concept of excess loss, defined for the true loss as f(x, y. 2) [(z, y) inf e2 f(x, y, 2'), and similarly for the surrogate loss with 2, 2 E Zz.
from logits to class labels. We assume the objective
optimized
The key idea of our framework is relate these excess losses through carefully constructed functional, which forms the basis for our analysis.
Definition 9. Define AG as functional that takes true and surrogate losses é, ė inputs and returns mapping AG[e, :] (0) X + 00) such that for any 0, x E y E y:
AGIC, (E, = inf Al(x,y, =EC((((a).)))
where C(0 {= Z2 A ((x 2) I c). We also overload AG to define another functional that returns mapping AG[e, 2] [0, 00) [0, oo) with only one argument such that
AGIE, (()) = inf AGIe, x,)
(x
For brevity, we drop the functional arguments e, when clear from context.
Intuitively, AGIE, (e, x, v) gives the smallest possible value of the true excess loss point (x, v). considering all outputs where the surrogate excess loss at most e. The overloaded version AGIe, (c) extends this idea to the entire input space, providing the smallest true excess loss achievable when the surrogate excess loss is bounded by everywhere. This functional allows to analyze how well optimizing the surrogate loss translates to optimizing the true loss, which is crucial for proving inconsistency.
Next, we establish some properties of AG(E, that we will use in our analysis.
Proposition 10. AG[E, ?s satisfies the following properties:
1. AG[E, (e) 2 0,
2. AG[E, (20) 0.
3. AG[E, (c) is non-increasing over its domain, and
4. AG(e, (A ((. y. 2)) < S A A(z)) for any x E X, E y and a E Zz.
Proof. We prove each property below:
1. This follows since A b(z, A(=)) 2 0 for all x E X, E and E Zz.
2. When +00, x, and unconstrained, so the minimal excess loss is zero
14

---

Published as a conference paper at ICLR 2026
3. Increasing relaxes the constraint on 2, and 2, thereby yielding infimum that is non- increasing.
4. Replacing the constraint set {a' E X,y E V, 22 , ;/1 S A (xx, y, =)} by the subset fa' E &X,Y E Vv E Z2 2('.v'.2' = bound.
A (xx y, 2)} yields the upper
The following theorem is central to our framework. It provides lower bound on the optimality gap of the true risk in terms of the optimality gap the surrogate risk, mediated by a convex function.
Theorem 11. Let ((t) be a convex function [0, oc) such that ((e) < AG(e,)((e) Then for any distribution D on X, reference model h: X - V, critic model f: - Zz and mapping A: B2 + 21 we have
< (NE XNDD A((X,
E AX(XX,(X)
XND
Proof. We have
( E A((X,MXX)
E. C(A((X,((X),
by Jensen's 's inequality
X~D
X-D
E ALX
by assumption by Proposition 10
X
E (e(x,)(x),A((x)))
xnD
This theorem lays the groundwork for proving Bayes inconsistency. The next step in our analysis is show the existence of a convex function ((c) that not only satisfies the conditions of the theorem, but also remains positive as the surrogate optimality gap approaches zero under some conditions. We construct such function below and establish its properties.
Proposition 12. Let AG: [0, oo) [0, sc). The function (.(c) supaço, {ae + b|VW 2
aw AG(w)) satisfies the following properties:
1. C, is convex.
2. (+(c) s AG(() for all 2 O.
3. Ç. is non-increasing.
4. For any convex finction Ç such that Ç(c) AG((), ((c) S (.(e).
5. Assume there exists such that ac AG(()) & AG((). Then is continuous at 0.
Proof. We prove each property below:
1. The function Ç. is defined as the pointwise supremum of convex functions, hence it is also convex.
2. This follows directly from the definition of C..
3. Consider e' 2 2 O. For any < 0 and 6 e IR such that aw bb < AG(w) for all w 2 0, we
have ac' S ac + Taking the supremum over all such a and we get (c()) < (c)..
4. At any é 2 O. we can find line that satisfies aw + < ((w) for all w 2 0 and ((e) = ae bb Together with the assumption that ((c) < AG(E), this implies ((c) < (c(c).
15

---

Published as a conference paper at ICLR 2026
5. For any 0, let 6 Then by definition, (. ad + (G (the line ab (0)
may not be maximal). So (.) - (.(6) = AG(O) - (. - -aò = c/2 < c. Thus lim (e(e) (0).
Building on the properties of ç. from Proposition 12, we now identify conditions ensuring the convex function S. remains positive as the surrogate optimality gap approaches zero.
Corollary 13. Suppose there exists > O such thut AG[e, (c) > 0. Then there exists convex
function [0, 00) that depends only on the loss functions E, such that Ç is continuous zero and ((0) AG|e, (0) > 0. Moreover
((E, E A((X,MX)) & A(XX,M(X)
XxDD
X
for any distribution D on X. reference model h: X + V, critic model f: X - Z2 and mapping A: Z2 Z1.
Proof. Consider the convex function Ç. defined Proposition 12. satisfies the condition ((e) S AGIe, (t), hence the inequality follows from Theorem 11.
We now only need show that Ç+ is continuous hood of e = 0, is non-increasing, and bounded below by zero, there exists a line ae + b with < 0 and b (G such that + AG(e) for all 0. Hence by Property 5 of Proposition 10, Ç. is continuous at zero.
Since AG(() is positive in some neighbor-
B EXCESS PSEUDO-LOSSES
In this appendix, evaluate the excess loss for various pseudo-losses introduced in Section 4.2. Recall from Appendix A, that for a given loss l: Xxxyx Z. we define the excess loss as Af(x, y: z) = ((z, y, 2) inz f(x, y, 2). This analysis is crucial for understanding the behavior of these pseudo- losses and their impact on the consistency surrogate objectives for disagreement discrepancy in Sections 4.3 and 4.4.
B. TRUE LOsS
We evaluate the excess loss for the two pseudo-losses L,, lg that appear in the true disagreement discrepancy, as formulated in (6). Specifically, for {1, 2} we consider the loss function & = L, -a Eg where L; is defined in (5), lzo is the zero-one loss and > O. For input E X, reference model labels y E [K]2 and critic model label y E [K], we have
apr(2)
inf (x,,,,1)) = inf 1 1ps())2pr(4) vE[K]
1 (Lute
1 vutVv'
v'E[]]
(2(
0,
1/1 1/2
opp(()
Pa(z)
< 1,
=pp(x)2pp(()) x
apr (x)
91 y2 A
(pp
> 1,
(a) (x)
Ps(2)
Ps(x)
V1 V2.
where the optimizer is s/ y1 y2 for the first case, y y' = y1 * y2 for the third case. Similarly,
V1
y2 for the second case and
ps(x)
inf 62(x,.1)) v'[[]
inf 1 (p()))pp)(1) V'jR
uitoy - a: a1 vott
(.))
y1 y/2 apr (2))
p=(x)
1,
[p(())<pp(())
pr (z)
ps(a)
ar
y1 y2 A ps(x)
apr
1,
y1 * y2,
16

---

Published as a conference paper at ICLR 2026
where the optimizer is y' y1 U/2 for the first case, s' # y1 Y2 for the second case, and y' = y1 + 1/2 for the third case.
Thus have
apr(x)
A A4(E,,,1 = 11 (o))222)())
ps(x) 10
> 1y: (1 app(T)
apT (x) (2(
-1 aoppi
+
pg(0)
ps(
Ps(#))
A Al2(1,y,0)) = (p))
DIFY - a v2
p2(
ps(x)
app ag(e)
>1 1/
ax + all yo
(pr(x)
B.2 OUR SURROGATE
We evaluate the excess loss for the pseudo-losses that appear in the surrogate for disagreement discrepancy (7) when using our disagreement loss. Specifically, for i E {1,2) we consider the loss
& = Li(fon d where L; is defined in (5), loo is the cross-entropy loss defined in (2), g0urs is
dis
our disagreement loss defined in (9) and a >
Since & and &g have a similar functional form, we analyze them together by writing for E 21,
E X. [K] and E IK
(, (i(x) (x) v) (p))((x) Cour (z,, 12 s))
where
Pa(x)
i=2Aj= 1,
(xx) (16(1)277))) i 1, (p(())<m)))) i == 2,
Pr Pr p
and pi.(x)
i=
(10)
otherwise.
Observe that
e'xt
) - ap),2(2) log (1 e eax²
inf (xx = inf (i(z) (p),1(x)) log Ee e.
BER*
SER
Eeen. ex
inf
((xx) (-Pt,1 (z) log(4n, ap),2(x) log(1 9vz))
qeAx-1
where the second equality follows by letting q == (e"t,..,, E. e AK-1. If (t,1 or (r))(x)= = then inf (, y, s) = 0. Otherwise, there are two cases to consider:
If y y2: the minimum is achieved q such that dy with all other components equal to zero. This implies A(s) = 3/1 and infgege (,(x, y, s)
If the minimum is achieved at such that 4y, p. (a) the remaining mass distributed arbitrarily across the other components. This implies A(s) y1 apr(x) < or A(s) y1 if spr(x) and
PL)(w)
-1+ apr (x) P=(x)
with
Ps(
ps(a)
inf ((c.y,s) = (iz)) (p.(())
(1+ apr(x)) + ap),2(0) log 1+ ps(x)
ps(x))
SER
apr (z)
We note that the optimizers in each case match the corresponding optimizers for the true loss.
17

---

Published as a conference paper at ICLR 2026
Thus we have A ( = alog Pr (x)) O. Otherwise
Letve exc
pf((() = and (Z) = log
6'vl
ex
opr(2
e
(2,(2,y,s) = - -pps())2pre)
log
+
log 1
E. e*
Ps
et
+1y==
log
1
apr
apr
log
1
ps (x)
ps
ps (s(x)
app (x)
(2(2)
c²
A2(,,,, - <p(()))
log
+ taloy
1
PT
E e+c
Ene
(s)
log 1 opr(a)
p2(x)
a
1+
(r)
(2(
apr(a)
B.3 ROSENFELD AND GARG'S SURROGATE
We evaluate the excess loss for the two pseudo-losses that appear in the surrogate for disagreement discrepancy (7) when using Rosenfeld & Garg's disagreement loss. Specifically, for i E [1,2] we consider the loss & L Cece dis where Iı is defined in (5), fee is the cross-entropy loss defined and K 2.
in (2), dis is Rosenfeld & Garg's ss disagreement loss defined in (3),
Since & and &g have similar functional form, we analyze them together by defining for E [1,2).
E X, y [K] E IR:
(. = <i(x) (pt,(x)) lee (z, y1 s) + a2),((z) dis (x, V2, s))
where Çi and Ptù are defined in (10).
Substituting the expressions for feo and RRG die we have
Ee e*vi
inf ss = inf SEE
(((x) (p:)(z) log log BER
+ ap) log 1 0. -- - Eners )
(11)
For the special cases where (x) or (r,2(z) we observe that the minimum loss zero.
For the more general case where Pt.1 (x) > 0) and (t,((z) > O. we solve the problem by computing the gradient with respect to s, and solving for the stationary points.
Let = (c"t..... ..... c*x)) Σ. c* denote the softmax probability vector corresponding to s. There are four distinct cases to consider for the gradient components:
1. For k 1/1 y22 we have
0 dl.c,yys) (((z) (pri(o)(ax -1) apt,2(x)
Osk
K-1
1 1 uvz n- Eetto
2. For k 1/1 1/2, we have
0 (li(r,y.s) Ce(z)) (pLLlo(las 1) ap)2(2)
Osk
1 1 + x- Enei &
3. For k = 1/2 Uı. we have
ali(I.y,s) Ci(z) (pralE)au + ap:2((x)
Osk
1 - -But Eogr
4. For k + V1, k + U2, we have
i (l, <i(z) (ota(E)as - apt)2(x)
Osk
K - 1 e Boz k-t Eeroo 8,
18

---

Published as a conference paper at ICLR 2026
Case 1: y y1 U2: Assuming (z(z) & O, there is stationary point s* for i and = 2 such that:
ex c + Eest e -1) -pp,2(2)
Pa.(1)
+ + -i Eesy
0%
ap),(2))
(1,1(x) et + Ecgs ex
4k +
K-1 1 - Eng
The equation for components k & y implies s = C' for some constant C' E R, i.c. all components of s* excluding Sy are equal. Hence the system of equations K can be simplified equation in u == 5 C:
K
(1,1(z)
ap,.2 (x) Ite-u-
eu + K-- K
The solution for both i and = 2 2 = log bx
pa(al (ppo(t))
where
1
(x(r) (r (1)(K)))+ + v (K- 1)r (K-
1)2(r 1)2.
(12)
This corresponds to a score vector such that s = C. + log bx
ps(a)) [pp and 8 C for all + y.
One can show that the behavior of the solution changes at the critical point Specifically,
P=(x) K
opr(")
2k-2
Pa(x) K for 0
2K-2 we have 0 < bx
ps(n) apr(2)
< 1 and the critic predicts A(s*) + y.
apr(x)
for (s(
apy (x) 2K we have dy
ps(a
1 and the critic predicts A(s*)
app (2))
for p=(w)
2K-2 we have by
Pa(#) (2)
and the critic predicts A(s*) = y.
(2)
We note that the optimizer for the surrogate losses does not match the optimizer for the true losses inputs x such that
K
Ps(ar)
< The minimum surrogate loss for given æ, y is
2K-2
apr(z)
inf (,, (1x))a. log sER
1+
(a(x))
(apr(())
P2(x)
+ aaG(()))2(z) log 1 bk
(13)
apr (x)
Case 2: y11 # y2: Let = ( w/ Σ. ef denote the softmax probability vector correspond-
.....,e"
ing to s. Assuming (i(x) # 0, there is a stationary point at s* for i = 1 and i = 2 such that:
Pi, (1) 1) ap;, (x)
K
1 Sy Eerry
Pi.1 (x) = -pp),((1)
1 -st - Eety, 22
ap),2(x)
(1)( K-1 +
Vk v1 4 y2.
Eesry
The last equation for components h & {yn, y2) implies QK for some C E (0, 1), i.e., all components of q excluding o and or equal. Using this result, the system of equations simplifies to (K 1)(1 )
4/ -(K 1)C. The only valid solution is obtained in the limit q- - 0 and q3, + 1. This implies A(s*) yı, which matches the optimizer for the true loss. By appropriately taking the limit, we find the infimum for a given &. y is therefore
inf 2, ()),
#ERK
19

---

Published as a conference paper at ICLR 2026
Thus we have (x,,,,, = log e'xt
Exre'
pr(x) = 0 and A22(z,y,s)
a aog c x Entrs 00) ) if pf(s)x = O. Otherwise
Ene
(l)(,,y,s) 1 pp())2pp(x)
loog
apT(2)
log e x Enrono A0))
ps(
ps(())
ps(()) app (x)
bx 1 log
+ K 1K-1)
1, log dy
apr(o)
in apr(2) (x)
ps(x)
log 1 bK
(T(
cpp (x:
Al2(2,y,s) <pp
(2( log
Exeee
+ log
0²v0 x:. Eeros )
(pp(F)
ps (s(
(s(())
+ KK -1)
y ws opr(x)
log
app
(x)
ps (z)
1y 22 opr (I)
log
cxpr (x)
ps(x)
-, log
1+bK
(x))(x)
B.4 GINSBERG ET AL.'S SURROGATE
We evaluate the excess loss for the two pseudo-losses that appear in the surrogate for disagreement discrepancy (7) when using Ginsberg et al.'s disagreement loss. Specifically, for E (1,2) we consider the loss 2, = Lilkce, c where L; is defined in (5). fee is the cross-entropy loss
defined in (2), pGLK is Ginsberg et al.'s disagreement loss defined in (4), > 0, and K >>> 2. dis
Since & and lg have similar functional form, analyze them together by defining for i E {1,2). E X. [K]2, IK:
s) (x(x) (p),(()) loo Wl. + (x))(())
dis
(LL((,, y2 8))
Enen 0n
a2)2(2))
Eneere
= (x))
(r. log
+
Σ log
09
02/22
(2)
Σs se + (p(,(()) + ap))((2)) log Σ ctc )exe)
=((x))
where G and Ptù are defined in (10) and we have used the definitions of foo and dis
in (2) and (4),
respectively.
We now consider the problem of minimizing (xx, s) with respect to s E R.K For the special cases where Pt.1 (xr) 0 or (z) = O, we observe that infgeRx (xx v, = 0. For the more general case where Pt.1 (I) 0 and (z.) O, we solve the problem by computing the gradient with respect to and solving for the stationary points.
Let q = (e (e.,,..,, e**)/ Ee e*h denote the softmax probability vector corresponding to s. There are four distinct cases to consider for the gradient components:
1. For l 1/1 # 1/2 we have
ol.s.,y.s) (1(z) (-pus(e)-
ap),((z)
(p11(z)+ ap.,((2)) gb
Osk
K K-1
2. For k 1/1 y/, we have
a (l, (x(x)
(x(x)) (-pra(0) + (pL)(x) + (p)2((z)) gx)
Osk
20

---

Published as a conference paper at ICLR 2026
3. For k V2 y1, we have
(l((r,y,s) (i(z) (p(a(x) + ap:.((z))
Usk
4. For k + M1, + y/, we have
0l,(,,y,s) (i(x)) (-apxe(1) + (p),(x) + ap))(())) q
8sk
To solve for the stationary points, consider the cases y1 y/2 and y1 # y2 separately. Below
define r(z) = ps(p)/ (apr)((ap((z)).
Case 1: y y1 1/2 Assuming (i(x) + there a stationary point at q" for i 1 and 2 such that:
(z.1
r(x)
G (r)( + (x))2(())
r(æ) +1
ap. d (1)(x) + ap)2(x)
K-1
K K-1r(z) 1r()
is straightforward verify that this point minimizer. This implies A(s*) = yf)) > and A(s*) + y r(x) सं.. We note that the optimizer for the surrogate losses does not match the optimizer for the true losses at x such that K-I given v, is therefore
1. The minimum surrogate loss for apr()) <
(o(r)
inf ((x = pi,1 (x) log 1 apr(x) SERR
ps((x)
Ps(()) apr(s) + 1)
app,2(x))og (K- (k-
(14)
Case 2: 1/1 # 122 Assuming ((x)) * there a stationary point at q" for i and 2 such that:
g Pz,1(z) + ap))(*)
r(x)(K - 1)
K-1
P1,((z) + (p))2(2)
K --1 r(z) +1
05 O,
(p))(x)
at (L,((z) (p))(()
K-1
A y2-
K - 1r())+1
is straightforward to verify that this point a minimizer. This implies A(s*) yı. which matches the optimizer for the true loss. The minimum surrogate loss for given 2, y is therefore
Ps(()) +1 +1)
inf ((xx,,s) (0)1(0) + (p)2 (K BER
(pp
-(pL1(0) + ap)2(4)
log (K - P2(())
K
app (x)
21

---

Published as a conference paper at ICLR 2026
Thus we have A (,, = k Eotes log
(Iveee) ps(x) = 0 and (li =
are
log E,,0h 6'v2
if pr(() = O. Otherwise
A (2, -1p)())2r((0))
1 1i (pp()) (1+
log
et
(K - 1)
(pp(2)
ps(
+
(K - 1)ps(a))
Σe es
(K 1)
(s(
cxpr (x)
opr (2)
Ps(x)
(K ()ps(a)
log
Σ En o
(K (K-1)
apr(x)
+1
(cer(e
+ I Ay a K -
e'v (K - 1)
opp (m) + +11
p=(x)
(22 = -ppo())<p((s)
log
Σe e+=
(K 1)
p=(x) apr (a)
e Ee e
(ss(t)
+ +1))
log
(K -K-1) 1)
K
apr (x)
og (2)
C PROOFS FOR SECTION 4.3
This appendix contains proofs for the results presented in Section 4.3. The key result of this section Theorem 4, which we prove using Corollary 13 developed in Appendix A.
As a first step, we must prove that the condition for Corollary 13 holds: namely that the relevant AG functional positive within neighborhood of zero. This done for the pseudo-losses associated with the surrogate of Rosenfeld & Garg (2023) below.
Lemma 14. Consider the framework of Appendix A for a classification task with K > 2 classes, where y [K]2 is the reference oulput space, Z, [K] is the model outpul space, and Zg R&K is the raw (logit) model output space. Assume the mapping A: RRK - [K] from logits to predictions as defined in (1). For fixed
(0.
2K 22-2 K-2 ). set the input space to the restricted input space X' for
Rosenfeld & Garg's surrogate as defined (8). Then for true loss l Lilexo E2ol and surrogate loss l = Lilfee, a (GLK) we have
I i= 1, ad, i= 2,
AG(e,21(c)) inf (x.N)x2'I1]]
Rale,, =
for all e < (8) where
log
+ K+26(K bx x (0) +K-1
Kby IN
2K log 1tbx (o
i= 1,
(6) =
a
K -2)((K11) log
2k
( +
Kbx (8
a log
i+be( x0 18)
i= 2,
and :x: [0, 00) + [0, oo) is defined in (12).
Proof. Let r(x) = Pafw)
(p) and let (((z) and (z)(2) be as defined in (10). Fix x E X' such that
((x)) # and (y.w) for y E [K] (i.e., the reference outputs identical). We begin by proving the following:
Claim: We have
&GI,, = (r(x)-1- 1, i= 1, 10 r(x)), i= 2.
(15)
for all e < (x) where
(r(x))
2 1=bx
(x) = (t.((x) log (x(r(x)) + 1-1
+ +0p12(2) log
22

---

Published as a conference paper at ICLR 2026
To prove the claim, we first recall from Definition 9 that:
AGI[s, (i(,,,,)((, -
inf A (c((,,, =EC,2)((,
with
= x)
( sc).
When e O, we know from the analysis in Appendix B.3 that (1,,] x, E lAk: +
y/ Sk CJ [sy, C + log bx (r(z))] [C' K]]. For any in this set, we have A(s) y. then straightforward to show, using the expressions for A derived Appendix B.I, that AGIE, 20, x, y) is equal to the RHS of (15).
The claim follows if we can prove that A(s) for all E Clii(e, y) such that e < <x))), since the value of A ( A(s)) and hence AG(4,, (r, are the same as at 6 = 0. To demonstrate
this, find the minimum surrogate loss A (1,, y, s) with respect and show that it is equal to e* (xx). The loss minimization problem is
RR such that A(s) + y.
inf SER A
inf ((..y.s) inf (z.y.))) A (z,y,,s) A(R)
SERR
The unconstrained problem (second term) solved Appendix B.3, where minimizers s* are found to satisfy satisfy sy > maXcşy S. Such minimizers are outside the feasible region for the constrained problem (first term), where we need & < maXeyy 8 Since the objective is convex 8, solutions to the constrained problem must lie on the boundary where 8y maxezy Sc. This, together with the symmetry of the objective with respect to components sy for k * y. means the minimizers s* for the unconstrained problem are vectors where all components equal.
Substituting the optimizer into the first term above, and using the previously evaluated result (13) for the second term, have
K
inf A (2( = (t,((x) log K + (x),2(() log 2 - Pt.1 (x) (x) SER* A(s)
1
bx
pa(x) (p)
ps(x)) (pp
ap)
log log 1 dx
=
which completes the proof of the claim.
Next, we find a threshold e (5) that is valid for all x X" by minimizing c'(x: over E X".
Since e² (x) only depends on x via r(x), and is monotonically increasing function of r(x:) for K 2K-2 + 8 I r(x) < 1 - 8, we have that the minimum is achieved at r(x) = -K-2 + 5.
K
Now by Definition 9 we have for < <5) that
AGi Pe](E)
inf AGi(2, 22)e, (x.w)
inf a(1 r(x))
"EX'
aò.
The second inequality follows from the claim proved above and the third inequality follows by setting r(x:) 1-8. 8.
We obtain a similar result for the surrogate of Ginsberg et al. (2023) below. The proof follows the same structure as the proof of Lemma 14.
Lemma 15. Consider the framework of Appendix A for a classification task with K > 2 classes, where y [K] the reference output space, Z1 [[]] is the model output space, and Z, R K is the raw (logit) model output space. Assume the mapping A: R + [K] from logits to predictions K-2 set the input space to the restricted imput space X' for 2k-2)
is as defined in (1). For fixed 8 E (0,
23

---

Published as a conference paper at ICLR 2026
Ginsberg al.' 's surrogate defined in (8). Then for tree loss & Lilkzo- -a 22l and surrogate loss l, Lillee: c we have
1-5: 1,
6
inf AG(e, = (I.))
Pi(e,,
add
i i= 2,
for all e < (6) where
K K-1 log bik b[k-1)+K + log 6(K-1)+1
6K(K-1)+K
AiK 1[K-1)+K
i=
(6) =
ar log o(K- ((K-1)+))
+ a K-1
3(K-1)+1 log
[K(KK -1)
8[K-1)+K
Next we present result that allows compose the convex envelope functions that appear in Appendix A. This is needed, as we will apply the bound of Appendix A to each risk term in the reformulated disagreement discrepancy.
Lemma 16. Let Ç1, <2: [0, oo) 7 [0, 20) be convex functions that are continuous at zero and non-increasing. Then the function Ç: [0, oc) + [0, 00) such that
((c) 4 2200
inf
(1(() (2(22)
has the following properties:
1. it satisfies ((11 + ( (2(e2) any 61,02 (0)
2. it is convex,
3. it is non-increasing,
4. it satisfies ((D) (1) (2)),, and
5. it is continuous zero.
Proof. We prove each property below:
1. This holds trivially by definition.
2. Let e 2
and (e1, e2) and (c),)) be pairs that are arbitrarily close achieving the
infimum for {(c) and ((c'), respectively. For À [o, 11, the convex combination of these has components that sum to de (1-1)ed A)e'. By the definition
pairs X(E1, 62) + (1- +11-1((d)
of 6, we have Ç()e + (1 - Aje') S (A( + (1 1 A)e) + (2()e2 + A)e)) Applying
the convexity Çi and (2 the right-hand side yields
+(()))))) Since this inequality holds for values that can be made arbitrarily close the result follows.
<()e (1 A)e')= < ((G((e)) (2(e2)) (1
3. Let e 2 and (c1, (2) be a pair such that 6 + c2 = c and (1(c)) + (2((2) is arbitrarily close
((e). Now for e' e, consider the pair (e1, 62 (e' <)). The sum of its components is
é1 + 62 + - = é'. By the definition of Ç. we have ((e') < (E1)) + (2(E2 + (e' e)). Since (2 is non-increasing, it follows that Ca(e2 + (e' e)) (2(e2). This leads to the inequality ((e') < (1(E1) + (2(E2). As this holds for a value arbitrarily close to ((e), we conclude that ((E") S (E)) as required.
4. This holds by definition. For 0, the only pair (2) satisfying the constraints is (0,0) so the infimum is taken over a single point.
5. We need to show that lim {(c) ((0). From the fact that Ç is non-increasing, we already have ((e) < (()) for any e 2 For the reverse inequality, consider an arbitrary
8 > O. By the continuity of and Ce at zero, there exists 7 0 such that for any
x E [0, .7) both (z) > (0) - 6/2 and (2(x) > (2( - 6/2. Now, if we choose <1 + E2, both 6 and e2 must be less than 17. This implies that any term in the infimum, Çi (e) + S2 (2((),, is strictly greater than (0)+C2(0) -0)-8.
c (0, then for any decomposition
Therefore, the infimum itself must satisfy ((e) 2 ((0) 8, which completes the proof.
24

---

Published as a conference paper at ICLR 2026
We now use Lemmas 14, 15 and and Corollary 13 to lower bound the optimality gap of disagree- ment discrepancy in terms of the optimality gap of the surrogates, evaluated on subset of the input space.
Theorem 4. Consider a classification task with K classes, where h: X - [K] is a reference model outputting pair of class labels and f: X R.K is critic model outputting logits. Let S, T be distributions on X' and a > O. For E (0, 1) and 5 E (0, 2²) define restricted input space:
X" X' IEX: -
0,A+85
(pp S 51-83. 6).
ps(
Let dn be either Rosenfeld & Garg's surrogate" with lais dis X K/(2K - 2), or Ginsberg al.'s surrogate with Ldis dis X = 1/(KK 1), and lagr fee both cases. Then for both surrogates, there exists a convex function Ç [0, 00) + [0, 00) that is continuous at 0 with <(0) 0/(1 -8)1s(8)20 - + ((2)) such that
- dalh, fl(.T) 2 5 da h, fI(5)x,,
inf dalh, (1))x: -lx))) T PEH
sup JEHH
Proof. For E {1,2}, let 4; = L,[- Ez a Ez0] and & = Lslkce, Edis.. Using the fact that da hh ()) -d [h, fT 8) and expanding out the definitions, have
sup (a (((, d. (h. T) MER
= add- [1, [[T, - inf a d. 1 (T) PEN
= R(6,, h AS((5) inf M, AS)( + Ri62, AAT(() PEW
inf h2, AT)
PEW
RlAC, 2 R|A &,, (f)()) + R[A l2, h, Af((
(16)
(17)
Note that (16) follows since I' can be optimized pointwise and (17) follows by replacing R|A 4, h, ( and R|A f2, h, AT] xxxx)))))))))))))))))) by lower bound of zero
Next, we apply Corollary 13 (17) on the restricted input space X' using (,x, v.y) 3/) as the true loss and (a, y, s) the surrogate loss. Lemmas 14 and 15 ensure that AG (c) 5/(1 8)1 ab1;=2 > 0 within a neighborhood of = 0 for Rosenfeld & Garg and Ginsberg et al. 'ss' surrogates respectively. This is needed to apply Corollary 13.
As a result, there exists a convex function C:: (0) + [0, oc) that is continuous at zero, with (0) 5/(1 8)15(x))50 such that
Si R (1
= fl(1xx)
inf Rie f((5)x)) PER
(18)
The last line follows since f can be optimized pointwise. By the same argument, there exists convex function (2: [0, oo) + [0, oo) that is continuous at zero with (2(0) = ad a51 ((x))> such that
R| E2 h, Af](T] 2 Ca h, f(TT)x)
inf Rie2, f((T(x)) FI(Tlx)) Fer
(19)
Now let
<(<)
10re=...:0.000 (((e)) + (2(e2).
inf
(20)
We consider generalization of Rosenfeld Garg's surrogate with a and distinct reference models.
25

---

Published as a conference paper at ICLR 2026
By Lemma 16, is convex and continuous zero, with <(0) =((()) r(x)ss- Using the property that ((11 + 22) (161) (2(E2) from Lemma 16, along with (18), (19) and (17) yields
sup dalh, T) - (( J'
26 h, h f((sxx)) inf R(e,, h ('(()) Rie,, flT)xx inf R(22, h, fT(())) (x))) MEN
Men
= [[5)) ((x))
inf à. 1,, (S) 7
MEN
as required.
Corollary 5. In the setting of Theorem 4, the surrogates proposed by Rosenfeld & Garg (2023) and Ginsberg et al. (2023) are not Bayes consistent for disagreement discrepancy when K >
Proof. We reuse definitions from the statement of Theorem 4.
Using (7) and the fact that the critic f'
can be optimized pointwise, can rewrite the surrogate optimality gap
la fn)
inf da [h, f((,T) R h. f.l(S) RIA h, (n] PER
2 R Ł f. xx) R|A 8, h, (x))
= d x Txx)
inf d, [4,
PEN
where the inequality follows by replacing R[A 2, h, (f] and R|A l A by lower bound of zero. By the sandwich theorem, have
d hh fml(s,T) inf da (S) 0 F'EH.
= lh (S) T(x)) -
inf dt, ["), 2 o. f'HN
Consider Ç as defined in (20) and let
X, S ( d. (x1(
inf [h, (S) T(x))
Pen
Since Ç is continuous at zero, the continuous mapping theorem implies X,, 2 ((0). Let S, T be such that 5(X') 0 or T T(X') where X' is defined in (8). Then <(0) 5/(1 6)1s(x))00 + a51T(x)50 is strictly positive.
We prove that
Y, sup d, (((S, da [h, fn)(S.T MER
does not converge in probability to zero by contradiction. Suppose Y, 2g Then by Slutsky's theorem, X, Y. & ((0). Now by preservation of inequality in the limit, if Zn 2 Z and Z, S 0 for all n, then Z < 0. Applying this Z. X. Y, implies ((0) 0, which contradiction. O
D PROOFS FOR SECTION 4.4
This appendix contains proofs for the results presented in Section 4.3. The key result of this section Theorem 4, which we will prove using an upper bound of Zhang (2004b) that is analogous to our lower bound, presented in Corollary 13.
We begin by introducing a functional AH that relates the the true and surrogate excess losses. This functional plays similar role as AG in Definition 9.
26

---

Published as a conference paper at ICLR 2026
Definition 17. Let AH(e 00) x & y - [0, oo) be function such that for any E X,
y e...
+00.
C(e 00
AH[C,8[(e,2,)) =
inf (if=:Ec((()))))) A l(I,, 9, otherwise,
where C(di(,, = f= E A y, Az) 2 e). We also define AH(e [0, oo) - (0)
such that
inf AH(e, (e,,,))) AHle, (a.v)ER'x
Having defined AH, ready to restate the upper bound of Zhang (2004b) (labeled Corollary 26 in their paper). It provides an upper bound on the optimality gap of the true risk in terms of the optimality gap of the surrogate risk.
Theorem 18 (Zhang, 2004b). the loss function is bounded, and the function in Definition 17 satisfies Ve O, [H (e) > O, then there exists concave function &: [0, oo) - [0, oc) that depends only on e, i, such that E(O) = 0 and lim E(6) = O. Moreover, given h: X + V.
f:X- + Z we have
E A SE E X(X,,X(),, XND
XND
for all distributions on
Before we can apply this result to prove Theorem 6, we must prove that the positivity condition on AH holds for the true/surrogate losses of interest. We do this in the lemma below.
Lemma 19. Consider classification setting where the reference model output space consists of pairs of labels y = [K]², and the evaluation model output space consists of logits = RR Let A: X [K] be as defined in (1). Consider the true loss & = Lifbx. (oo] and corresponding surrogate loss & Lifece, (Ours), where Li defined (5), loe is defined in (2), and tOuss defined in (9). Thenfor E {1,2} and all e > O we have (H, (,](c) > O.
Proof. We prove the result by evaluating A [[e, (,, x, directly for four cases: = and 91 = y2. 2 and y1 + y2. ex
and /1 y/, and 2 and yı + y2. For brevity, define = "e* 2. e* and r(x) = opr (r))s((())
Case l:i and yı y2. Using the expression for A derived in Appendix B.1 have
Ir(a) <max s. ((())>1)( r(x)) 2 2) (1,)(e,,,,)) {s IR
For r(z) I 1, this set is non-empty when Sy1 < maxe/n Se, r(x) < - e and r(x) I a. Using the expression for A i derived in Appendix B.2, we have
inf seC(e,((s.))
A (2,
inf - -log(gn, (1+r(x))) - +1)
8u <
2 I+ r(x)
log
+ +r(x) log
1 1+)(
Similarly, when r(x) > 1 the set C((i](E, is non-empty when on max, Ge, r(z) 2 e and r(x)= a, where we have
inf seC
A (2,
inf - logg(g,, (10,.11111 (1+r(x))) - -(z) +r(1
2
log
+r(x) log
1 1 r(z)
1+x)
27

---

Published as a conference paper at ICLR 2026
Thus have
AH(e, 2) 2 min log 1 r(x) + +r(x) log
> 0.
1 (+r()))
Case 2: = 1 with y1 # y2. Using the expression for A we have
Clailee, (s E RK (x))) (Is,, <max.eys r(x)1s,,, mmax, x.) 2c..
This set can be partitioned into subsets:
G( = S R
8y
< max Se, Syz F max Se ogtnn
for r(x) 50,55,
C2(Ei((e,,,,))) = S ReKK
88
< max 86, 8y. = max 88 cg
for max - 13 S r(w) S a,
where (1 = C2lte](e,,,)) 0 outside the specified domains.
For r(z) E c, $ we have
inf xEC, (
Ali(r,y,s) (EC((G))(,)))))
inf
log((n)) - r(xx) log(1 9p.))
log2,
and for max - 13 rr(z) we have
inf (d) xEC,(()((,,.)))
inf - -log(1s.) r(x) log(1 9v.)
seC,((])(sx,))
lim log(K 7) log)) 17), 7-00-
log K.
Thus have
21,e,,, min(log log K} 0.
Case 3: i = with y1 = y/. Using the expression for & derived Appendix B.1, we have
Cl62](E,,, x, y) {s R (s) (1s,, <max s - -()))==)))((()))----1--1-------- c)
For ((r) 2 this is non-empty when Sn max Sc, ( 1 andrz))) 1/a. Using the expression for A l derived in Appendix B.2, we have
[H|(,, {2](E,,,,)) = s)C(e))(
inf A (x)
=a inf -r(x)-''o((0))) log(en, (1 + r(x))) log((1 Go. (1++)(((())) +r(x)-1))
9,1
-r((x)- log ( 2 aog
2 (1+r(x)-1
1 r(+) + a log
On the other hand, when r(x)-1 < the set (r,, is non-empty when 8y. = max, 8c. r(x)-1 < 1 c/a and r(x) < 1/a, where we have
inf AH(e, (2)e, xec(e,
A (,
= a inf -r(x) - log(gv, (1 + r(x))) log((1 - (1+)((+((x))) +)(x)-1)
2,
2
2
ar(x)-1 log
+ a
1 r(x)
1+r
Thus have
2
AH (8, (2,
min
(r(x) log
+ a log
r(x) (min
1+r(x)
1 1+r(x)
> 0.
28

---

Published as a conference paper at ICLR 2026
Case 4: i= 2 and V1 * V2- Using the expression for A la have
((2))(e, {s RK r<) (r(x))+11,, <maxotor + 1 1 max, 2 This set can be partitioned into subsets:
C1 = s SE RK syn < max Se, Sya + max Se
for =r(z)= < <a,
of
C2((2((,,,)) { SERR: 8y
for max (0. - 13 s <r(zz)+ <a, <<a
max Ses 8v2 = max 80 cx
where Ci = C2(Ea((e,z,y)) 9 outside the specified domains.
For a. S r(()) < a, we have
inf sEC,((a](s,..))
A
inf =EC,(
ar(x)-+ log (1v, + a log (1 992)
= =ar(x) log
clog2,
and for m0 & 13 1-15 ((()) < we have
inf Alz(E,y,s)) xECa(t)(o,))))
inf or(x)- log (gy, log (1 Toz
sECa(ta]((ar))))
lim or(x)- log(K (K + n) + a log(K - 11) m-00
a log K.
Thus have
(H (,)(c, minfclog log K} > 0.
Hence we have shown that [ (e, 0 for any x X, y E [K]2 and implies AH (c(()) > as required.
0, which
We also need the following result which allows us to compose the convex functions that appear in the framework of Zhang (2004b, Appendix A).
Lemma 20. Let Eι, f2: [0, oo) [0, x)) be conver functions that are continuous at and
non-increasing. Then the function a: [0, oo) - [0, oo) such that
g(c) =
sup
+
202.20220..000
has the following properties:
it satisfies (1(e) + (2(e2) S E(e + for any 61,62 E (0)
2. it is concave,
3. it is non-decreasing.
4. it satisfies g(0) (1) (0), and
5. it is continuous at zero.
Proof. The proof follows a similar structure as the proof of Lemma 16.
We now use Lemma 19 and Theorem 18 to upper bound the optimality gap of disagreement discrep- ancy in terms of the optimality gap of our surrogate.
29

---

Published as a conference paper at ICLR 2026
Theorem 6. Consider classification task where h: X - [K] is reference model outputting pair of class labels and f: X + RK is a critic model ouiputting logits. For any a > let d. be our surrogate with Edis = @Ours and lagr = lee. Then, for any distributions S, T on X, there exists concave function Ç [0, 00) > [0, 00) that is continuous at with {(0) 0, such that
sup d. [h, ()) dh (), S a. (b, [\(S,T) - inf a. [b. M((,))) FEH
PEN
Proof. Using the fact that da h, f)( -a (12, h1), f(CT, S) and expanding out the definitions, we have
sup dalh, (), dolh, [) da [(/g, h1) f(T,,) neWW
a inf da ((C MEN
R|C,, Af(((()) inf R|4 Af(((())
JEEH
+ R inf h, J'EH
R h AS](S) + R|A (I,
where the last equality follows since f' can be optimized pointwise. Applying Theorem 18 to cach of these terms gives
sup da ('( d. & (R, ((C.:/S..TTTS(,,,,,,., N'
+ Ea (
(21)
where ε and &2 concave non-decreasing functions that are continuous zero and satisfy (0)
(0) = O. Note that in order to invoke Theorem 18, we have used Lemma 19 which guarantees
positivity of (f,, (e)(e) for any 0. We have also used the fact that é and & are bounded.
Next, we define the function ę: [0, oo) - 20)
{ = 6,+6,-6,,1
sup
(61) + (2(62),
which is concave, continuous at zero and satisfies {(0) = (2))++20(0)) = 0 by Lemma 20. Combining the first property of Lemma 20 with (21) yields
sup d. (S, th, ([S, <
[]() + R|A 82, h. .I(T)
NEH
= dalh, =cddalt.f(S..T)
inf @a(h, (((S.T))
fEH
where we have again used the fact that f' can be optimized pointwise in the last equality.
Corollary 7. Our surrogate for disagreement discrepancy with cross-entropy agreement loss and the disagreement loss specified (9) is Bayes consistent for all 2
Proof. The result follows from Theorem 6. Let Gn å. [h, (*),, - inf new d. [h, (S, T) and G, /' [a (") lh, dal T.), By the continuous mapping theorem and continuity of at zero, we have {(G.,) & 0. Also, by Theorem 6, we have 0 5 G, S E(G,) ) for all
n. Applying the sandwich theorem yields the desired result: Gn & 0.
E ROSENFELD AND GARG'S ERROR BOUND UNDER COVARIATE SHIFT
This appendix presents the enror bound for models under covariate shift, as proposed by Rosenfeld & Garg (2023). While this content is not novel, we include here to make our paper self-contained and to provide necessary context for experiments in Section 5 and the attack described in Appendix F.
Rosenfeld Garg (2023) developed a method to bound the error of a model under distribution shift using disagreement discrepancy, requiring only labeled source data and unlabeled target data. Their
30

---

Published as a conference paper at ICLR 2026
approach involves training critic model, chosen from specified hypothesis class, to maximize the disagreement discrepancy between itself and the model under evaluation. This maximized disagreement discrepancy is then used to construct probabilistic upper bound the target enror The bound is formally stated the following theorem:
Theorem 21 (Error bound). Let Su: Sie and Tiz, Tue be train and test datasets drawn i...d. from the source distribution S and target distribution T, respectively. Let y²: X + [ be the ground truth la- beling function, h: X - [K] be the model under evaluation and f E arg min dlh, (St. , Tur) be the optimal critic within hypothesis class H S off: {f:X - R=} Assume d(h,y' (s,, 1 ((,, Then with probability 1 we have
(1Stel + ()T log 1/6
Rleeo- y", ,h((T) S Ril20: ()(e + ( Tre)
2 St [Tiel
error target
eIrOr SOUrCC
disagroement discrepancy
sample correction
The accuracy of this bound critically depends estimating the disagreement discrepancy term. Here, the consistency of the surrogate plays crucial role. A consistent surrogate ensures that, asymptotically, optimizing it leads to the same result as optimizing the true disagreement discrepancy, This provides theoretical justification for using the surrogate in training the critic fo and, consequently, in estimating the upper bound.
The bound's validity also relies on a key assumption: d(h, y (S) S d(h, (S, This assump- tion states that the disagreement discrepancy achieved by the optimal critic f should be at least as large as that achieved by the ground truth labeling function y*. The extent to which this assumption holds depends on several factors:
The expressiveness of the critic's hypothesis class H.
The quality of the surrogate disagreement discrepancy
The effectiveness of the optimization procedure
When these factors align favorably, the trained critic I* should achieve disagreement discrepancy that meets or exceeds what would be obtained using the ground truth labeling function y". However, as we observe our experiments (Section 5), this assumption does not always hold in practice, leading to potential violations of the bound.
The analysis surrogate consistency and its impact on the reliability this bound forms the core of work, as detailed in the main text.
F ATTACKING ROSENFELD & GARG'S ERROR BOUND
This appendix describes an attack on the error bound of Rosenfeld & Garg (2023), aiming to underestimate the error by perturbing the target data. We perturb fraction of the inputs, constraining the perturbation for each input in loe -norm to e. The attack can be viewed as an application of projected gradient descent.
Let
(|Seel + 4(Trol) log 1/6 2 [Ta]
ub(Tir, Tro) = R(fzo "e,e:."",, (i((,o) + f Tro) +
denote the upper bound on the target error from Theorem 21. Note that we've dropped the dependence on the source train/test datasets Su. Ste. and made explicit that the critic model I' (T(ii)) E arg max d(h, [Sr, Tir) depends on the target training dataset Ter.
Our objective the attacker is minimize the difference between the upper bound and the actual target error ub(Tur. Tix) R(e " .nhhhh)Ta (Tto), subject to the for constraint on the perturbation to the target train and test instances. If this difference becomes negative, have triggered violation of the bound. By dropping terms that are constant with respect to the target datasets, we can equivalently minimize:
R[ezo, h, (T())) R(exo v" hhhhh""TT (Tuc).
31

---

Published as a conference paper at ICLR 2026
This problem cannot be solved using gradient-based optimization, the zero-one loss lzo is not differentiable. Additionally, f (Tur, which is the solution to an optimization problem, is difficult to differentiate through.
To address these challenges, we employ a two-step optimization procedure that uses differentiable surrogate losses. For this attack scenario, make exception to usual treatment of the reference model h. While throughout the paper we' ve assumed returns raw outputs (class labels), here we need access to its logits or class probabilities to compute gradients with respect the target data. This is necessary for the attack but does not change our general framework.
Our two-step procedure is as follows:
1. Optimize the target test data Tie:
Replace R((zo; h, Af* (Tio) with - R(Laix, ( (Tar)))TTee) where (ais(r; P, s) takes as input a probability vector p E Ax-1 over classes instead of a class label. This encourages agreement between the reference model h and critic model f (due to the minus sign). We use the Gumbel softmax trick to make this loss differentiable in the class probabilities output by h.
Replace A( y" (T(eT)) with -R[lee. "eceeyy"h]((" (Tie). encouraging disagreement be- tween the reference model h and ground truth labeling function y* (due to the minus sign).
Compute the gradient of the surrogate with respect to the selected target test inputs, take gradient descent step, and project the perturbation onto the fo -norm ball of radius e centered on the original target input.
2. Update the target training data Tir using the same surrogate objective and algorithm as for the test data, followed by updating the model (T.r).
Importantly, since the objective consists of sums over target data, we can optimize the target inputs in batches. This allows us to attack large datasets without needing to load all inputs into memory simultaneously. which would be infeasible for datasets with tens of thousands of images.
G FURTHER EXPERIMENTAL DETAILS AND RESULTS
G.1 REPLICATION OF EXPERIMENTS WITH EXISTING AND NEW SURROGATES
This appendix provides additional details and results for the replication of experiments from Rosenfeld & Garg (2023), complementing the results and discussion in Section 5.1.1.
Experimental Setup We briefly describe key elements of the experimental setup in an effort to make our paper self-contained. For comprehensive details, readers are referred Appendix of Rosenfeld & Garg (2023) and their publicly released code The experiments utilize 11 publicly available vision datasets commonly used in distribution shift contexts:
CIFARIO (Krizhevsky & Hinton, 2009): Original as source; CIFAR10v2 (Recht et al., 2018)
and CIFAR (Hendrycks & Dietterich, 2019) targets.
CIFAR100 (Krizhevsky & Hinton, 2009): Original as source; CIFAR100-C (Hendrycks & Dietterich, 2019) as target.
FMoW from WILDS (Koh et al., 2021): Train split as source; other splits (collected at later times) targets.
Camelyon17 from WILDS (Koh et al., 2021): Train split as source; other splits (from different hospitals) as targets.
BREEDS (Santurkar al., 2021): Datasets derived from ImageNet (Russakovsky al., 2015), including entity 13, entity30, living and nonliving26. Original ImageNet subpopu- lation as source; subpopulation and ImageNetv2 (Recht al., 2019) subpopulations and 2 as targets.
hhans///gthhh..cmmmmmeesdddddggg discrep
32

---

Published as a conference paper at ICLR 2026
ERM, FixMatch BN-adapl
DANN,
0.8
Error (Actual)
Surrogate
Ours
RG22
0.2
Error (Bound)
Figure 5: Comparison of error bounds versus actual error on target data for our surrogate and that of Rosenfeld & Garg (2023). Each point represents shift/model, with points above the dashed line indicating bound violations. Results are disaggregated by training method: non-domain adversarial training (left) versus domain-adversarial training (right).
OfficeHome (Venkateswara et al., 2017): Product domain as source, other domains as targets.
DomainNet (Peng et al., 2019): Real domain as source, other domains as targets.
Syn2Real (Peng al., 2018): Train split (synthetic object renders) source, other splits (real object images) as targets.
Models used include ResNet-18. ResNet-50 (He al., 2016), and DenseNet-121 (Huang al., 2017), depending on the dataset. Generally, models are pretrained on ImageNet and then fine-tuned on the source dataset. Training/fine ttnnintttnngggg on source data employs five methods: empirical risk minimization (ERM), FixMatch (Sohn et al., 2020), BN-adapt (Li al., 2017), CDAN (Long et al., 2018), or DANN (Ganin et al., 2016), with data augmentation applied during training.
Crities are implemented as linear models that consume either logits or features from the model under evaluation. Specifically, the weights of the evaluated model are frozen, and only an appended linear layer is tunable. Unless otherwise specified, logit-based critics used. All loss functions involving softmax operations, including the standard cross-entropy loss and our proposed disagreement loss, implemented in log-space ensure numerical stability.
Additional Results In Section 5.1.1, we compared surrogates based on their resulting estimates for the disagreement discrepancy, where larger estimates superior. This is the only term in Rosenfeld & Garg's ' error bound (Theorem 21) that depends on the surrogate. Here, we provide additional results comparing the complete error bound (including all terms) with the actual error labeled target data.
Figure 5 compares the error bound and actual error for numerous shift/model pairs. We disaggregate by model training method: domain adversarial training (DANN, CDAN) on the right and non-domain adversarial training methods (ERM, FixMatch, BN-adapt) on the left. We observe more violations of the bound (points above the dashed line) for models trained using domain adversarial methods. Specifically, there are 13 violations when using Rosenfeld & Garg's 's surrogate versus 6 violations for our surrogate. Rosenfeld & Garg (2023) attribute this DANN and CDAN penalizing the ability to discriminate between source and target distributions in feature space, effectively minimizing the disagreement discrepancy term in the error bound. They argue that this scenario violates the assumption of their bound, DANN and CDAN can produce models that are, in some sense, worst-case (adversarial) for the bound.
We also consider different critic architecture. Figure 6 compares logit-based and feature-based critic architectures. Rosenfeld & Garg (2023) suggest that feature-based critics tend to have greater bounds. Our results confirm
capacity than logit-based critics, resulting in more conservative this behavior for critics trained with our surrogate. Note that this figure only includes models trained using ERM, FixMatch, and BN-adapt, excluding domain adversarial trained models.
33

---

Published as a conference paper at ICLR 2026
Foatures
Logis
Loghs wio
1.00
0.75
Error (Actual)
Surrogate
0.50
Ours
RC23
0.00
1
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Error (Bound)
Figure 6: Comparison of error bounds versus actual eπrоr on target data for our surrogate and that of Rosenfeld & Garg (2023). Each point represents shift/model, with points above the dashed line indicating bound violations. Only models trained using ERM, FixMatch, and BN-adapt are included. Results disaggregated by critic architecture: feature-based (left), logit-based (middle), and logit-based without term (right).
G.2 ROBUSTNESS TO ADVERSARIALLY CHOSEN DATA
This appendix provides additional results and details about the experiments assessing the robustness of Rosenfeld & Garg's ' error bounds to adversarially chosen target data, complementing the results presented in Section 5.1.2.
Due the unavailability of the exact models and train/test splits used in the replication experiments, attempted to recreate the setup described in Appendix A of Rosenfeld Garg (2023) and partially outlined in our Appendix G. We used 8 of the 11 datasets listed in Appendix G.1: CIFAR1O, CIFAR100 FMoW, BREEDS (entity 13, entity30, living 17, nonliving26), and OfficeHome. DomainNet and Syn2Real were excluded due to their qualitative similarity to OfficeHome (shifts based on image style). Camelyon17 was omitted as it is binary classification dataset where the surrogates for disagreement discrepancy are equivalent. We added iWildCam2020 from WILDS (Koh al., 2021) in place of Camelyon17, using the predefined splits (covering distinct camera deployments).
Experimental Setup
For each dataset, we used the same model architecture as Rosenfeld & Garg (2023): ResNet or DenseNet, with a ResNet-50 pretrained on ImageNet for iWildCam. In most cases, models were pretrained on ImageNet. We trained or fine-tuned on source data using empirical risk minimization with data augmentation, excluding other training algorithms like FixMatch, BN-adapt, CDAN, and DANN for these experiments.
Critics were implemented as linear models consuming logits from the model under evaluation. We trained 30 randomly initialized critics parallel and selected the best one. Following Rosenfeld Garg (2023), the critics were trained for 100 epochs using the AdamW optimizer, with a learning rate of 10-3 and weight decay
10-4, All loss functions involving softmax operations, including the standard cross-entropy loss and our proposed disagreement loss, are implemented in log-space to ensure numerical stability.
We attacked the target datasets using the approach detailed in Appendix F. We varied the fraction of attacked images f in the target dataset over values f E {0, 12.5, 25, 50%). In all cases, we ran the attack for 20 steps with step size of 8/255, constraining the magnitude of the perturbation for each image in f to 4/255. When updating the critic each step, we used only 5 epochs, resulting in total of 100 epochs of critic training over the course of the attack.
Additional Results In Section 5.1.2, we compared surrogates based on their resulting estimates for the disagreement discrepancy, where larger estimates superior. Figure 7 supplements these results with scatter plots comparing the complete error bound with the actual error on the attacked target data. Results faceted by attack fraction f. We observe that the bound increasingly underestimates
34

---

Published as a conference paper at ICLR 2026
0.0% attacked
12.5% artcked
25 25.0% attacked
50 5% attacked
1.00
Error (Actual)
Surrogate Ours
0.50
RG23
CL/23
0.00 5.
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.25
0.50
0.75
0.25
0.50
0.75
1.00
Error (Bound)
Figure 7: Comparison of error bounds versus actual enror attacked target data for our surrogate and that Rosenfeld & Garg (2023). Each point represents shift/model, with points above the dashed line indicating bound violations. Results faceted by the fraction of attacked instances in the target data.
the actual error as f increases, suggesting decreased robustness of the bound. Consistent with earlier results for disagreement discrepancy, our surrogate is least likely to underestimate the error, achieving the fewest violations for all values of f.
For completeness, we provide the results plotted in Figures 3 and 7 in tabular form in Table 2. Note that the attacks reported in the table computed using our surrogate. We caution against comparing results at the level of source/target pairs, as we only run the attack and compute the bound once per pair, and there are several sources of randomness; instead, our analysis aggregates results across all pairs, providing a more robust statistical basis for our conclusions about the surrogates' performance.
G.3 APPLICATION TO HARMFUL SHIFT DETECTION
To train the critic model using XGBoost, we implemented custom objective function that defines the first-order gradient and second-order Hessian (H) the loss with respect to the raw model logits. The total objective is weighted sum over source samples S (where we minimize agreement loss) and target samples T (where we minimize disagreement loss). For a given input æ; E R.K be the vector of logits output by the critic model, and let be the class predicted by the reference model. Let p = (s) be the predicted probabilities. We utilize diagonal upper bound on the Hessian to ensure numerical stability and efficient tree splitting, is standard in XGBoost implementations.
Agreement Objective For source samples, the critic minimizes the agreement loss &ee defined in (2). The gradient is the standard cross-entrops gradient. For the second-order term, the standard diagonal upper bound for all classes
Å 2p pp))
Disagreement Objective For target samples, the critic minimizes disagreement loss. The specific Hessian bound depends on the surrogate employed.
Our Surrogate. We minimize gOurs defined in (9). We derived diagonal bounds on the Hessian ensure convexity in the local neighborhood of the prediction:
12py py). 2pxP,
if l: = 8.
A
if + y.
GLK23 Surrogate. The baseline minimizes d defined in (4), As this is functionally equivalent to cross-entropy loss against soft target distribution, we use the standard diagonal bound for all classes
Å 21 (1 pk)-
35

---

Published as a conference paper at ICLR 2026
Erce (Bound)
Disagneemen Discrepancy
Source
Target
Amack (%)
Emur (Actual)
GLK23
Our
RG23
GLK23
Ours
RG23
cifar
citar 10.1v6
0.003
0.149
0.287
0.194
0.011
0.169
0.076
12.5
0.151
0.154
0.285
0.214
0.024
0.154
0.084
25
0.219
0.136
50
0.154
0.285
SfartOc.rrsst.vvv
0.169
0.169
0.567
0.065
0.059
0.155
12.5
0.160
0.551
0.768
0.158
25
0.361
0.150
0.523
0.254
0.400
0.413
0.144
50
0.357
0.145
0.319
0.270
0.035
0.409
0,160
ciaar pibclle-picllttt.eeee
0.320
0.281
0.769
0.479
0.171
0.659
0.369
12.5
0.356
0.265
0.729
0.459
0.155
0.619
0,349
25
0.391
0.254
0.695
50
0.489
0.212
0.653
0.439
0.102
0.543
0.329
ciaa lovel5
12.5
0.136
0.124
0.340
0.142
0.144
0.230
0,092
25
0.171
0.119
0.315
0,140
0.009
0.205
0,050
50
0.290
0.118
0.316
0.143
0.008
0.206
0.033
cifar
cifar Jever
0.330
0.481
1.000
0.942
0.200
0.969
0.661
0.519
0.570
0.988
0.984
0.217
30
0.616
0.082
1.000
1.000
0.399
0.987
0,775
100s motion Nur. level?
0485
0.935
0.962
0,652
12.5
0.405
01407
1.000
0.940
0.214
0.964
0.657
25
0.452
0.523
1.000
0.948
0,240
0.970
0.665
0.555
0.551
cifar Spp.pereetter
0,300
0.461
1.000
0.842
0.178
0.913
0,560
0.460
0.554
25
0.404
0.466
1.000
0.826
0.183
0.914
0,363
90
0.507
0.433
1.000
0.856
0.200
0.922
0,573
1miiy11 subb
auttt133.sb2
0.465
0.347
0.442
0.484
0.093
0.187
0,230
12.5
0.519
0.362
0.446
0.441
0.108
0.192
0.187
25
0.571
0.332
0.428
0.424
0.078
0.174
0,169
0.293
0.470
0.449
0.216
0,195
3miity30 subl
entiy300
0.648
0.530
0.334
0,330
0.528
0.726
0.687
0.342
0,302
25
0.724
0.492
0.702
0.648
0.108
0,318
0.264
50
0.812
0.433
0.708
0.619
0.039
0.321
0,235
fnowwj121 J0212
1115
0.455
0.511
0.883
0.712
0.068
0.440
0.269
12.5
0.450
0.497
0.878
0.668
0.054
0.436
0.225
25
0.552
0.477
0.221
50
0.454
0.007
0.672
0.011
0.464
0.230
f616_1618
0.553
0.953
0.302
13.5
0.528
0.530
0.906
0.715
0.077
0.463
0.273
23
0.594
0.502
0.901
0.700
0.060
0.159
0.257
50
0.717
0.461
0.925
0.697
0.118
0.483
0.254
mwikccam21100
Iwildcam20200
0.206
0.822
1.000
1.000
0.493
0.790
0.726
12.5
0.304
0.848
1.000
1.000
0.763
0,738
0.823
1.000
0.765
0.723
30
0.426
0.803
1.000
1.000
0.534
0,777
0,227
livieg17
0.618
0.771
0.849
0.112
0.390
12.5
0.734
01.9%
0.741
0.768
0.139
0.282
0.309
25
0.756
0.567
0.778
0.743
0.108
0.319
0.284
0.408
0.801
nonliving26 subl
nomliving26.suh2
0.643
0.606
0.854
0.805
0.262
0.510
0.461
0.559
25
0.520
0.803
0.788
0.186
0.459
0.384
50
0.804
0.476
0.797
0.696
0.133
0.453
0.352
officchome_mmoouz
afficchome.nt
0.457
0.609
1.000
1.000
0.390
0.973
0.910
12.5
0.483
0.633
1.000
1.000
0.114
0.966
0.910
25
0.545
0.619
1.000
1.000
0.430
0.959
0.905
30
0.547
1.000
officehome clipart
0.619
0.717
1.000
1.000
0.955
0.921
1.000
0.8%6
25
0.670
0.888
10000
1.000
0.462
0.941
0.892
50
0.730
0.685
1.000
1.000
0.471
0.957
0.903
afficchomccaal
0.246
0.474
1.000
0.974
0.259
0.863
0.759
12.5
0.300
01503
1.000
0.944
0.277
0.867
0.718
25
0.483
50
0.508
0.727
Table 2: Comparison of target error bounds and estimated disagreement discrepancies across different surrogates for various source/target data pairs. For attack rates greater than 0%, the target datasets are adversarially perturbed using our proposed disagreement loss and surrogate for disagreement discrepancy.
36

---

Published as a conference paper at ICLR 2026
H USE OF LARGE LANGUAGE MODELS
We used large language models (LLMs) as writing assistance tools to help synthesize and polish text based on author-provided content, including drafts, bullet points, and technical explanations. LLMs were also employed to review mathematical proof' for potential errors. All substantive content, theoretical contributions, experimental design, and scientific conclusions are the original work of the authors. The LLMs did not contribute to the conceptual development of the research or the generation of novel ideas, and their usage does not constitute authorship-level contribution.
37


Reviews:
[{"review_id": "WQWv9iNOlI", "reviewer": "Reviewer_H4wG", "summary": "The paper studies disagreement discrepancy, an approach that has been recently popular for distribution shifts problem related to error estimation, testing, and robustness. Earlier works propose to maximise the disagreement discrepancy by employing some surrogate loss function, however the main finding of this paper is that the employed surrogate may not be Bayes consistent, which is necessary. The paper then  proposes a Bayes consistent surrogate for the problem.", "questions": "In Equation 1, what is the $\\min$ over?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. I think paper makes clear theoretical contribution, which is also important. I've seen the works on disagreement discrepancy before as applied for testing, and have found the application to be hacky. The current contribution studies the soundness of it, and indeed, the finding that prior approaches are not sound is original and of significance. \n2. The paper is also thorough (I like the appendix, although I didn't verify everything too closely), but the decomposition of the risk using density ratios, and the resulting Bayes inconsistency analysis seems correct to me. In that sense, the proposed surrogate is also sound (wonder why do the authors think, that was not already employed in prior works as a disagreement loss, as it seems super intuitive).", "weaknesses": "1. Overall, I do like the paper from the theoretical contribution perspective. However, I'm not sure I followed the experimental section that well. Could authors clarify what is max disagreement discrepancy (in Figure 1) and how it is defined and estimated? I also feel writing wise, the paper assumes too much background on prior work. \n2. Furthermore, I think while the quality of surrogate is the main focus of the paper, the paper does not connect to downstream applications. I'd assume in testing works, the proposed surrogate could help aid better testing power.\n3. Additionally, I feel like the new disagreement loss can be unstable as $\\sigma(s)_{y}$ approaches 1, which it can as neural networks can get overconfident. Has that been considered before? I assume that could or could not happen, and in fact, maybe the proposed disagreement could even lead to better calibrated probability estimates? I'd be curious to learn some perspectives on this. \n\nSummary: I think the paper makes clean theoretical contribution, that is useful. But from the practical side, I can have a better assessment if the above questions are addressed in the rebuttal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "magTJiecLl", "reviewer": "Reviewer_cJ7E", "summary": "The paper studies the use of surrogate losses to maximize disagreement discrepancy - a quantity used for error bounds under covariate shift, shift detection, and robust training. The authors claim to prove that commonly used disagreement surrogates are not Bayes consistent for multi-class problems and develop upper/lower bounds on the optimality gap. Guided by this analysis, they propose a new disagreement loss, $ ℓ^{ours}_{​dis}(x,y,s)=−log(1−σ(s)_y​) $\nwhich, when paired with cross-entropy agreement loss, yields a surrogate provably Bayes-consistent. Empirical results on a variety of vision benchmarks (WILDS, BREEDS, DomainNet) and adversarially perturbed target data show improved estimation of the disagreement discrepancy and better calibration of the associated error bounds versus prior surrogates.", "questions": "1) How general is the proposed framework for difference-of-risk objectives? Could it apply to other discrepancy-based metrics (e.g., fairness gaps, calibration errors), or is it specific to disagreement discrepancy?\n2) Theorems 4 and 6 provide lower and upper bounds on optimality gaps. Are these bounds tight in practice, or are they mostly asymptotic constructs with little finite-sample relevance?\n3) How sensitive are your results to the choice of the critic’s hypothesis class H? Have you considered the notion of H-consistency or provided any analysis for finite-capacity critics?\n4) Does the new surrogate require calibration of $\\alpha$ to maintain consistency, or is it theoretically invariant to this hyperparameter?\n5) What guided the decision to use a frozen feature extractor and a linear critic head? Would your results change with a trainable or deeper critic? \n6) Can you provide mean ± std results over multiple random seeds for key tables and figures?\n7) Have you compared against any of the newer disagreement-based methods?\n8) Would it be possible to include a visual example or schematic showing how your surrogate modifies the disagreement landscape compared to Rosenfeld & Garg’s surrogate?\n9) Do you expect your theoretical framework to extend naturally to other discrepancy measures?\n10) Could your approach provide practical benefits in domains beyond covariate shift?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper tackles a fundamental open question in the theory of domain adaptation and covariate shift: whether the surrogate losses used for estimating disagreement discrepancy are theoretically sound.\nFew prior works examined the consistency properties of such surrogates; most focused on empirical performance.\nThe authors provide what appears to be the first demonstration that the popular disagreement surrogates of Rosenfeld & Garg (2023) and Ginsberg et al. (2023) are Bayes-inconsistent in the multi-class (K > 2) case.\nThis negative result is conceptually important because it challenges implicit assumptions underlying a growing body of empirical research.\nThe proposed alternative surrogate loss, proven (under stated assumptions) to be Bayes-consistent, gives the work a constructive dimension - turning a theoretical diagnosis into a practical remedy.\nWhile the proofs appear well-structured and follow logically from standard surrogate-consistency frameworks, a full validation would require a detailed check of each derivation and of how the assumptions are applied. The arguments look rigorous and well-motivated, but independent verification is still needed to certify formal correctness.", "weaknesses": "The main theoretical guarantee - Bayes consistency - is asymptotic and does not specify convergence rates or finite-sample behavior.\nThis makes it unclear how the surrogate behaves with limited data or under model misspecification. Without sample-complexity or generalization bounds, practitioners lack quantitative guidance on when the theoretical improvement translates into measurable gains.\n\nThe analysis assumes covariate shift only, i.e., $P(Y \\textbar X) $ remains constant across domains. In real-world distribution shifts, label shift, concept drift, or conditional shift frequently occur - cases where the proposed theory may not apply or may even break down. No empirical evidence is provided for robustness beyond this assumption.\n\nThe paper largely dismisses H-consistency (consistency under restricted hypothesis classes) as \"limited in practice\" without detailed justification or experiments comparing H-consistent and Bayes-consistent outcomes. Since DNNs are not universal function approximators in practice, H-consistency might be more relevant than Bayes consistency.\n\nThe results depend on the structure of discrete label sets and the softmax parameterization. It is unclear whether the framework extends to regression, structured prediction, or representation-learning contexts where disagreement discrepancy is also used.\n\nWhile the experimental results are broad in scope, they are not statistically rigorous. Most results are reported as single runs, without standard deviations, making it difficult to assess robustness or reproducibility. The paper would benefit from multi-seed evaluations and statistical significance tests.\n\nHyperparameter sensitivity is not explored: the method introduces parameter $\\alpha$ whose effect on stability and performance remains unclear.\n\nThere is no discussion of computational overhead (e.g., runtime, convergence rate) introduced by the new surrogate.\nThe theoretical contribution is strong, but the empirical evidence supporting its practical relevance remains somewhat limited in depth and statistical reliability.\n\nThe paper compares primarily with Rosenfeld & Garg (2023) and Ginsberg et al. (2023), which are relevant but now slightly dated.\nMore recent 2024–2025 methods tackle disagreement-based discrepancy estimation and should be included for completeness.\nWithout these baselines, it is difficult to assess whether the proposed surrogate remains competitive with the current state of the art in practical terms.\n\nThe lack of up-to-date comparisons weakens the empirical claim of superiority, even though the theoretical advance remains valid.\nOverall, the paper’s main weaknesses lie not in its conceptual or theoretical core, which is solid, but in its empirical completeness and clarity of assumptions. Statistical validation is thin, comparisons are slightly outdated, and the theoretical applicability to finite neural critics could be more clearly discussed. These issues do not undermine the core contribution but do limit the paper’s perceived maturity and readiness for publication at the very top tier.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DC7gDvMceX", "reviewer": "Reviewer_RFmD", "summary": "The paper considers the problem of measuring maximal discrepancy in covariate shifts in the context of bounding generalization errors, noting that the theory is based on 0-1 losses, but surrogate losses used in practice, while convex, are not consistent. That is, the optimizer of the surrogate loss does not converge to the solution of 0-1 loss due to the choice of the disagreement loss. A consistent disagreement loss is proven and shown to perform better in estimating the actual discrepancy.", "questions": "What is the purpose of minimum in (1) and if it is needed what is it taken with respect to what?\n\nLine 95 The limitations of theory is noted but could be made clearer on why 'practical model classes' are note covered by $\\mathcal{H}$-consistency. \"While H-consistency provides valuable insights, its limited applicability to practical model classes\" It is not until line 493 that deep neural networks are mentioned. \n\nLine 111 Could be more clear by defining what exactly \"this framework\" is. I understand it to be the description at line 104–105.\n\nLine 132 The description of a probability \"intersected with $\\mathcal{X}'$ is strange and imprecise. Why not say it is the conditional distribution for points in the subset $\\mathcal{X}'$. \n\nLine 399 The critic was using the frozen weights. In cases where the reference model like ERM is not aware of the target data, couldn't a better critic be built on top of the backbone optimized in a different unsupervised domain adaption method? I.e. couldn't $f$ be used as a critic for $h$ even though $f$ uses $h'$?\n\nLine 1616 the $\\ell_\\infty$ should be on both target training and target testing as both are optimized in the two steps of the optimization. \n\nLine 1621 Couldn't the adjoint/ implicit function method  be used here?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is clear and address a perennial problem of understanding how covariate shift can affect classifiers. Overall, the paper is well written.", "weaknesses": "There are a few points that could be made more clear (questions below). \n\nAdditionally, is it possible to use the consistent form as a bound on error to create distributional robustness? I understand the adversarial attack is a step in this direction, but commenting on how this connects to making better unsupervised domain adaption algorithms would be interesting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)