Learning from Noisy Labels via Conditional Distributionally Robust Optimization
Authors: Hui Guo
Grace Yi
Boyu Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: noisy label
conditional distributionally robust optimization (CDRO)
crowdsourcing
Primary area: learning_theory

Abstract: While crowdsourcing has emerged as a practical solution for labeling large datasets, it presents a significant challenge in learning accurate models due to noisy labels from annotators with varying levels of expertise. Existing methods typically estimate the true label posterior, conditioned on the instance and noisy annotations, to infer true labels or adjust loss functions. These estimates, however, often overlook potential misspecification in the true label posterior, which can degrade model performances, especially in high-noise scenarios. To address this issue, we investigate learning from noisy annotations with an estimated true label posterior through the framework of conditional distributionally robust optimization (CDRO). We propose formulating the problem as minimizing the worst-case risk within a distance-based ambiguity set centered around a reference distribution. By examining the strong duality of the formulation, we derive upper bounds for the worst-case risk and develop an analytical solution for the dual robust risk for each data point. This leads to a novel robust pseudo-labeling algorithm that leverages the likelihood ratio test to construct a pseudo-empirical distribution, providing a robust reference probability distribution in CDRO. Moreover, to devise an efficient algorithm for CDRO, we derive a closed-form expression for the empirical robust risk and the optimal Lagrange multiplier of the dual problem, facilitating a principled balance between robustness and model fitting. Our experimental results on both synthetic and real-world datasets demonstrate the superiority of our method.

Learning from Noisy Labels via Conditional Distributionally Robust Optimization
Hui Guo
Grace Yi
Department of Computer Science University of Western Ontario hguo288Guwo.co ca
Department of Statistical and Actuarial Sciences Department of Computer Science University of Western Ontario gy gyi5ßuwo.co ca.
Boyu Wang
Department of Computer Science University of Western Ontario
bwang@csd. www.geesdd.wo...oo uwo.
Abstract
While crowdsoureing has emerged practical solution for labeling large datasets, it presents a significant challenge in learning accurate models due to noisy labels from annotators with varying levels expertise. Existing methods typically esti- mate the true label posterior, conditioned on the instance and noisy annotations, to infer true labels or adjust loss functions. These estimates, however, often overlook potential misspecification in the true label posterior, which can degrade model per- formances, especially high-noise scenarios. To address this issue, we investigate learning from noisy annotations with an estimated true label posterior through the framework of conditional distributionally robust optimization (CDRO). We propose formulating the problem as minimizing the worst-case risk within distance-based ambiguity set centered around a reference distribution. By examining the strong duality of the formulation, we derive upper bounds for the worst-case risk and develop an analytical solution for the dual robust risk for each data point. This leads to novel robust pseudo-labeling algorithm that leverages the likelihood ratio test to construct a probability distribution in CDRO. Moreover, devise efficient algorithm for CDRO, we derive a closed-form expression for the empirical robust risk and the optimal Lagrange multiplier of the dual problem, facilitating principled balance between robustness and model fitting. Our experimental results on both synthetic and real-world datasets demonstrate the superiority of our method.
distribution, providing a robust reference
Introduction
Recent advancements supervised learning have spurred a growing demand for large labeled datasets 2 However, acquiring accurately annotated datasets is typically costly and time-consuming often requiring a pool of annotators with adequate domain expertise manually label the data. Crowdsourcing has emerged as an efficient and cost-effective solution for annotating large datasets. On crowdsoureing platforms, multiple annotators with varying levels of labeling skills are employed to gather extensive labeled data. However, this approach introduces a significant challenge: the labels collected through crowdsourcing are often subject to unavoidable noise, especially in fields
Coorresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

requiring substantial domain knowledge, such as medical imaging. Consequently, models trained on noisy labels are prone to error, including overfitting, since deep models can memorize vast amounts of data 3 In addition to statistical research on label noise (often termed response measurement ( ) a growing body of recent machine learning literature has focused on developing effective algorithms capable of training accurate classifiers using noisy data, e.g., [7H10] Many of these methods seek to approximate the posterior distribution of the underlying true labels using the observed data.
error, e.g.,
Let X be an instance, Y denote the unobserved true label for X, and Y represent a vector of crowdsourced noisy labels for X. The data data-generating distribution, Px,, xx.y.y can be factorized in two ways: P P ylx P y 5ix.y or " with P denoting the (conditional) distribution for the variables indicated by the corresponding subscripts. These factorizations have inspired research that trains models by estimating the posterior distribution of the true labels, 5 in the latter factorization.
Previous work [2-22] introduced various algorithms for estimating the annotator confusions, also known as noise transition probubilities, which yield an approximated conditional distribution of Y, given Y and X, denoted Pyly.x For ease of reference, we use P* and P to denote the true distribution and an approximate distribution for the variables indicated by the corresponding subscripts. Given the observed data X and Y, along with an approximated conditional distribution pyly.x and a prior for Y given X, denoted Prix- the true label posterior is then computed as P. x.. X Pylx Pyly. by Bayes's 's theorem [10 [3]. This estimated true label posterior is often used to infer the underlying true labels or weight the loss functions 7
However, accurately computing the posterior of the true label is challenging, and the estimated posterior Py/x.y may deviate from the underlying true distribution Pa y due to potential misspec- ifications in the prior belief and the conditional noise transition probabilities [15]. To address this issue, we introduce a robust scheme for handling crowdsourced noisy labels through conditional distributionally robust optimization (CDRO), as discussed in [16]. Specifically, we frame the problem as minimizing the worst-case risk within a distance-based ambiguity set, which constrains the degree of conditional distributional uncertainty around a reference distribution. By leveraging the strong duality in linear programming, we derive the dual form of the robust risk and establish informative upper bounds for the worst-case risk. Additionally, for each data point, we develop an analytical solution to the robust risk minimization problem, which encompasses existing approaches as special cases 9 This solution presented in likelihood ratio format and inspires robust approach that assigns pseudo-labels only to instances with high confidence, with uncertain data filtered out. These pseudo-label, also enable us to construct pseudo -ecurricm distribution that serves as a robust reference probability distribution in CDRO under potential model misspecifications. Moreover, we derive a closed-form expression for the empirical robust risk by identifying the optimal Lagrange multiplier in the dual form. Building on this, we ultimately develop an algorithm for learning from noisy labels via conditional distributionally robust true label posterior with an adaptive Lagrange multiplier (AdapiCDRP).
Our contributions are summarized as follows: (1) We formulate learning with noisy labels as CDRO problem and develop its dual form to tackle the challenge of potential misspecification in estimating the true label posterior from noisy data. (2) We derive an analytical solution to the dual problem for each data point, and propose novel algorithm that constructs a robust reference distribution for this problem. (3) By deriving the optimal Lagrange multiplier for the empirical robust risk, we develop an efficient one-step update method for the Lagrange multiplier, allowing for principled balance between robustness and model fitting. Code is available at bttpp::/github..om///
1728/ AdP
Notations. We use [k] to denote {I...., k} for any positive integer k, and 1(-) to denote the indicator function. For a vector v, Uy stands for its jth element, and v denotes its transpose. For v- = (Vi,..,,
and E [oo). the L norm is defined as ||0||, = ( (ug19)//9 if
1 1 q < co, and ||0||~~ = max, |0y| if q +oo. For a matrix V. we use Vi,, to represent its (i,j) element. Furthermore, let (52, G, 14) denote the measure space under consideration, where 12 is a set, G is the -felld of subsets of $2, and is the associated measure. For > 0, let [*(H)) represent the collection of Borel-measurable functions f f2 + R such that [[]]ddu < xc. Let d(.;) -) denote a metric on Ω. We call f L-Lipschitz with respect to d(.,) -) if [f()) - [(w2)] < L- d(ui, u2) for all "1, U2 E 2, where L is a positive constant.
2

---

2 Proposed Framework
2.1 Problem Formulation
Consider a classification task with feature space X C R and label space V where d is the feature dimension. Here Y/ is taken {0, 1} for binary classification and [K] for multi-class classification with K > 2. Let X X' denote an instance and Y E y denote its true label. Let V denote the considered hypothesis class consisting of functions v defined over X, which, for example, can be neural networks that output predicted label probabilities for each x E X. Specifically, for binary classification, vo : X + [0, 1), with (x) representing P(Y 1 x), and the classified value is given by (xx(x) > 0.5). For multi-class classification, &) : X' + A K with K > 2 and K-1 denoting the K-simplex, where the jth component of (x)), denoted v/ x)
(b(x),; represents the conditional probability P(Y = j| = x) for j E [K], with the classified value defined as arg maxje[K] (x)))-
In applications, the true label Y is often unobserved, and instead, set of crowdsourced noisy labels is collected, where ((r) y² denoting the label provided by annotator out of R annotators. Let D - (X,, y.).=_ denote the observed data of size n, where Y, contains noisy labels provided by R annotators for instance X,, which may differ from the true label Y; for each i E [n]. Our goal is to train a classifier using D to accurately predict the true label for a future instance.
Y (
R
rr
common assumption in supervised learning is that the data points (X Y,, Y.) for i E [m] are independently drawn from a probability measure P for {X, Y, Y). defined over the space 2 A X x y yRR Under this assumption, many existing methods aim to approximate the posterior distribution of the underlying true label Y, given the observed data X and Y 7 I. The estimated true label posterior, denoted Py|x.5- is then applied to either infer the true labels or to weight the loss functions. For example, 99] utilized Pyjx.y as a weight in the loss functions, without considering potential misspecification of the associated model. However, such strategies typically ignore the variability induced in estimating the true label posterior.
To mitigate the effects of potential misspecificatiins, we propose a conditional distributionally robust risk optimization problem:
sup inf Re (1b; Pylx,)) with R. (vbs (15.5) A Ex, ET NEW
Eo ((((()))
(1)
where ((..) a loss function, the expectation Fxx,y taken with respect to the joint distribution of the observed data X and Y, and the expectation Egyn, is evaluated under the conditional distribution model, denoted Qylx.y. of the true label Y, given X and Y. Here, (pyl))))) x) is an ambiguity set of probability measures centered around the reference probubility distribution P Pvix.y- indexed by e 0 [16-T8] For instance, Ie (Pyy v/..)) can be conceptualized as the radius, where elements in the ball represent possible distribution models for P x.5 and the
"ball" with Pyix.8 at its center and
distance between two points is measured using a standard metric for distributions. Specifically,
(Pylx.)) {Qykx.8 P())) d (Q Py1x,)) <e).
(2)
where P())) denotes all Borel probability measures on V and d. is discrepancy metric of probability measures. In this paper, we employ the Wasserstein distance in Definition 2. to define the ambiguity set. By taking the supremum in T over the ambiguity set (2) we aim to minimize the worst-case risk around the reference distribution, thereby mitigating the impact of potential model misspecifications.
One main obstacle in solving [ is constructing a reliable reference distribution Pylx.y. which typically depends on an empirical distribution that requires true labels in conventional distributionally robust optimization (DRO). We address this issue by investigating the dual form of the robust risk presented in (I.. which enables to create a robust pseudo- empirical distribution using a likelihood ratio test, as detailed in Section 3.1 An additional advantage of our approach is that it provides informative upper bounds for the worst-case risk in Section 2.3 via the dual formulation.
Remark 2.1. For simplicity in theoretical presentation, we assume access to all annotations from all R annotators. However, the theoretical framework presented in this paper is applicable to both single-annotator (R- = 1) and multiple-annotator (R > 1) scenarios. In our experiments in Section 4 we also consider the scenario of sparse labeling, where we generate total of R annotators and then randomly select one annotation per instance from these R annotators. We also conduct experiments with varying numbers of annotators for comprehensive analysis.
3

---

2.2 Duality Result and Relaxed Problem
To derive the pseudo-labe generation algorithm and establish reliable reference distribution, we analyze the dual form of [ We first define the Wasserstein distance of order p for p E to)).
Definition 2.1 (p- (o-Wasserstein distance, [7]. For Polish space S (i.e., a complete separable metric space) endowed with a metric e : S x S + Rz0, also called cost function, let P(S) represent the set of all Borel probability measures on S. where R20 represents the set of all nonnegative real values. For 2 1, let (S(()) stand for the subset of (PS)) with finite pth moments. Then, for P1; P2 E (S()), the Wasserstein distance of order p is defined as
inf [E (s) (2))] 1/p WP,,,, (P,
where Cpi P2) comprises all probability measures on the product space S x S such that their marginal measures are (-) and P2(.). Here, c..).) represents (e(:s
In 2). using the Lagrange formulation, and then establish the strong duality result for ① follows.
we set d(:, :) as the p- Wasserstein distance and incorporate the constraint d d Pyxxs) S
Proposition 2.1 (dual problem), Assume that for every given x E X, y E R and sb E W,
())(x)))) (yyix)), where (-) is defined in Section Consider d(,,)) in as the Wasser-
stein distance of order p. Then, for any > O. ( p//x.) ) in (7) becomes:
sup (e(v(X), gc -c mnl) y'YY
Re( Py)xs) = Ex,5 inf (220
7c" (ee +
(3)
To avoid solving nested optimization problems, we consider an alternative formulation by swapping the infimum and the first expectation operations:
Re(i Ps p))x)) A inf Ex.y
(se² + EPSMS sup vey
- -o" ..l))
(4)
720
which is an upper bound of (v;;; py(x5) according to Proposition 2.1 and hence, is given by
(4 can be regarded
as an relaxation of (3) The empirical counterpart of R, Py yx,,))
inf E ppdn (7ee + -Ep sup (((v) - -d -ndW..))) 720
(ih Pylx,)
(5)
y'EY
where p(n) x.y
E 8x x,, Y, is the empirical distribution of (X, Y) based on the dataset D defined in Section 2.1 Here, for any v E X' yR & represents the Dirac measure on X' x y defined as (A) A I(v E A} for any c X' DRR
Remark 2.2. The Lagrange multiplier in (4) and (5) captures the trade-off between robustness and model fitting in the presence of label noise and potential model misspecifications When the solution in is large, the inner supremum tends to favor y' = Y, thus encouraging the minimization of the natural risk using the reference distribution directly. In contrast, a small solution 7 introduces perturbations to the data, pushing the classifier away from the sample instances weighted by the reference distribution.
Remark 2.3. When p 1, 5 represents the dual form of the following problem:
sup
Eppi 2.5
[Bqjiu. (f(v(X),)))
(6)
Sy x.5)
where (Pyl))))) (Qylas E P(V) E Eppg d(Qy1x.3 Pyxx,) S } The proof of this statement
is deferred to Appendix[A.3. This result indicates that the empirical robust risk in the relaxed problem (5) corresponds the worst-case risk within an ambiguity set that constrains the size of the average
conditional distributional uncertainty.
2.3
Generalization Bounds
With the duality result in Proposition 2.1 and the derivations of the alternative formulations
and 5 now characterize the difference between R Py p)) and its population counterpart
R. (v. P)

---

Theorem 2.2. Consider the loss function E(..-) in Proposition 2.1 and let the cost function c(y. y/)
ky + for y. s V, where is a positive constant. Assume that there exists positive constant M such that ()) y) E [0, M] for all x E X, y E y, and ub E V, and that ((p(()))) y) is L.- Lipschitz in the second argument with respect to the cost function c).,)). Then, there exists a positive constant Cj such that for any given > 0, 1/ E V, and 0 < < 1, with probability at least 1 1)
CL
log(L/n)
Re(v: PyXx Re( Poiss) - cP- Vn + MM
2n
Theorem 2.2 suggests that the empirical counterpart, Re (v;; Pybx,y), is a useful approximation for the risk function ( py)x,)), as their disparity is bounded and cannot grow indefinitely large. For a finite sample size this disparity is upper bounded by finite value depending of the cost and loss functions, as reflected by n. L. and M. As the sample size n + oc, the difference tends to zero with high probability, and specifically, the difference is of order On
the characteristics
Next, we establish an informative bound for the empirical robust risk minimizer. For 11, 122 E 1i and for any given norm -I. let || 1/2 lo A su x 1| (x) - 4)2(x)) Here, || can be taken as any specific norms, including the L norm with q 2 1 that defined in Section I
Corollary 2.3 (Empirical Robust Minimizer). Let Ve,n E infwev R1(r Pyxx.5) Under the assump- tions in Theorem 2.2 if we further assume that the loss function ((.,)) is L'-Lipschitz in terms of the first argument with respect the supremum metric || lloc then there exists positive constant C2 such that for any >> and O < minimizer Venn satisfies:
7 < 1. with probability at least - 7, the empirical robust risk
Re (Ve,ni Pyxx5) S Re (Ve,ii Py(x,)
{
Lnd
Vlog Nss; - los }.
1
log(1/n)
inf R. (v; P3(x,s C2 pp-1 1 NEW
+ 2M
vn
2n
where N(s; V (loo) denotes the s-covering number of T with respect to the supremum metric.
3 Implementation Algorithm
In Section 3.1
we derive the analytical solution to the dual robust risk minimization problem in (). which leads to the development of novel approach for assigning pseudo-labels using the likelihood ratio test. These pseudo-labels facilitate the construction of a pseudo-empirical distribution, serving as robust reference distribution in using (5). In Section 3.2 we derive the optimal value in for the empirical robust risk (5) and establish its closed-fone
expression. This analysis provides a principled framework for balancing the trade-off between robustness and model fitting and also motivates an efficient one-step update technique in solving the robust empirical risk minimization problem.
3.1 Optimal Solution for Single Data Point
In this subsection, we determine the optimal value of (x) in (5) for single data point (x, y). To simplify the analysis, we first focus on the binary classification problem with y = {0, 1} and consider broad family of loss functions of the form:
él {(b(x),)) = (1 (1-31) (1- + (x)(xxx)),
where (x) represents the conditional distribution P(Y = 1|X = x) as described in Section 2.1 T Jo. 1] I is bounded, decreasing, and twice differentiable function, and I is compact subset of R.
For any given x E X' and y E VR, let (, & x for j 0, With the loss function in (7) and the metric el.,)) considered in Theorem 2.2 minimizing 5 with respect to
d E V becomes:
inf inf [7e" + Po(xx mmx v(x)), (x)(x)) yx*)
NEW 720
+ Px max (x)) - 7xP. (.P,T(((x)))))
(8)
5

---

and let 1i*h denote the solution of 8 For and k described in Theorem 2.2 let ø(e) _ el e"/n², The following theorem shows that has a closed-form solution, with its form varying based on whether
T is concave or convex.
Theorem 3.1 (Optimal Action for Single Data Point: Binary Case). Letx E X' and y E yR be given. Then, for concave function T, the optimal solution for is given by:
{ J. Px 2 e(e) + wi for j = 0,
3³ (x)
1 1/2,, otherwise,
with 인 = T (()))/(/2)//T000 - (()) E 10,; and convex function T, the optimal
solution of given by:
j, (x,,))) 2 g(c) + for j j=0,1,
(x)
'9, if e(t)) + +122 < (x, < e(E) + 22 2o = 0, 1,
1/2, otherwise,
where =2 = (T(())/(T'()) + T(1)) E [1/2,1) to is the unique solution of {Po(x. e(e))T'(( ((()
(0, 2), and e is the unique solution of [Po (1 (( (P((x.)) (1)) for E (5,
Remark 3.1. The optimal solution (x) in Theorem 3.1 can also be expressed in likelihood ratio
format, which naturally leads novel algorithm for assigning robust pseudo-labels Specifically,
when T is concave. the optimal solution can be expressed as: x0 (x) = 0 if Po(x. J) (x. 2
GG (x) = if (x. f)/Po y) 2 C1 and 1 (x) 1/2 otherwise, where C₁ - (e(e) w1)/(1 - (o(e) + w1) > serves as a threshold for the likelihood ratio test. Consequently. for a data point (x. y). if Pi (x, P)x 2 C1, we assign robust pscudo-label y* = 1; if Po(x, Px, y) 2 C1, we assign y = Leveraging the likelihood ratio format also facilitates extending the robust pseudo-label selection method to the multi-class case by considering pairwise comparisons. Specifically, if Px- /// max V)) 2 C1, we assign the pseudo-labed
y" = 1e to the instance.
Remark 3.2. Existing pseudo-labele methods 9 19 typically identify the underlying true label as the one with the highest probability in the approximated true label posterior. contrast, the proposed approach in Remark 3.1 considers both the highest and second- highest predicted probabilities. A pseudo-label is assigned only if the ratio of these probabilities exceeds specified threshold. This strategy ensures that pseudo-labels are assigned to instances with high confidence, effectively filtering out uncertain data.
Remark 3.3. In the special case where Px x (ý: (x)),, with (F; P'(Ý = -
i x) denoting the noisy label transition probability and (,(x) representing a proper prior for Y == j conditional
x for j 0, 1, previous studies have indicated the existence of a Chernoff information-type bound on the probability of error for robust pseudo-label selection, as described in Remark 331
[10 20) Specifically, for a fixed instance x, let a pseudo-label Y* be generated as described Remark 3.1 which depends on x and the corresponding noisy label vector Y. Consider the Bayes error, defined as RByyes Ex=a,1 P3 (x)) P* (Y* * fJ = j.x). According to Section 11.9 of (20), Rayes < expl (C(() (;;x)));)) where C(.,)) represents the Chernoff information between two distributions.
Remark 3.4. In practice, one can use either uninformative priors, such as a uniform prior for each class, or informative priors derived from pre-trained or concurrently trained models for Px(x) as discussed in Remark 3.3 [10 [3). Moreover, the estimation of P, (x, y) is not limited to Bayes's s rule. For example. [ proposed aggregating data and noisy label information by maximizing the f-mutual information gain.
Remark 3.5. Theorem 3.1 is developed based on the assumption that the function T is convex or the cross-entropy loss for L, meaning T(t) = - llg f for forf 0.
concave. In our experiments, To meet the required conditions, we clip its input to [0.01, 1 - 0.01] to ensure T--) remains bounded.
Next, extend the preceding development for binary classification to multi-class scenarios with KS 2. Letting T(-) in (7) be specified as T(t) = 1 1-t. t, we extend loss function form (7) to facilitate the worst-case misclassification probability in multi-class scenarios: {(b(x),)) = EØ= 1
i) }. For ease of presentation, sometimes omit the dependence x and y in the

---

notation. Specifically, for j E [K], we let P, - Px(X & P(Y j|x and by _ x(x)) In
manner similar to deriving (8
given x, minimizing (5) with respect to (xx) can be expressed as:
K
inf inf NEW 220
yee
Pj max 4/1 -Ix..
-
j=l
1 1- w/. 15+1 - .......... 1 1/x TmmP}
(9)
Theorem 3.2 (Optimal Action for Single Data Point: Multi-class Case). Let {PI,...,PA Pk} be arranged in decreasing order, denoted p(1) 2... 2 P(K), with the associated indexes denoted x(1), X(K). Let 1 denote the solution of the outer optimization problem in ( For j [K],
let wi-(5) denote the xli)-th component of xx(x) corresponding p(), Then, the elements of s/² are given as follows:
(a). 2 p() - ee(e) for all E [K- - 1}, then wi-(() R for all j E [K].
(b). If there exists some kn E [K - 1] such that
1 ho p(d) No e(r) >
K. and
1
No
Rg Σド p()) 1 Ky o(e) 2 k p() for j E [ka] and vb*6)= = 0 for j ko + ...... :. K.
1
for all E [K- - 1]. then (5(()) 1 for kg
Remark 3.6. The robust pseudo-labeling method described in Remark 3.1 can also be extended from Theorem 3.2 Specifically, by Theorem 3.2 if p(1) 2 max K + @(c). p + e())), then the optimal solution is: (b)(1) = and (b) = 0 for j = 2,..., ., K, which can also be expressed in a likelihood ratio format and applied assign robust pseudo-labels.
3.2 Closed-Form Robust Risk
We investigate the empirical robust risk 5 by examining its closed form expression. For i E [K] and j E [K], we let P., - (x; y.) a P(Y j = x, Y = ÿ,) and th.,; & (xx)), For simplicity,
we denote the Wasserstein robust loss in and the nominal loss respectively as:
1 +
R. = inf ye"
P. max (T( -yx", ..... ((bis-1) 7MP
720
n1
1=1
1=1
T(Wi,)), (ooi.)))((((,,,))) ((V1,+1)) - yNO" " T(bb,,))
-(bb,,))~+*)) -n0²
for e > 0;
(10)
K P(Wba))
9
(11)
j=1
For given X,, we sort ( d in decreasing order, denoted as (1) ... 2 vi
(K) Let
agjj (k) - T(Wis) for i E [n] and j E [K], and sort {as,, : i E [n].] E [K]} in decreasing order, denoted as (1) > 2 (nk), Correspondingly, the P.s values with the associated indexes are denoted as p())
p(nk), For any g(c). define an associated positive integer
s* E [nK 1] follows: if 1 p(1) e(c) < Σnk p(t), then there exists s {2, ... nK} n
such that 1/2 Di= P(O) e(e) for s < 8", and 1 Σ p(t) 2 e(e) for s 2 s*: if e(e) S 1 p(1),
m
then 8" is set as if e(e) 2 1. En
nk p(0) then s" is set nk + 1.
Let 2h denote the optimal value of y in R. in 10 where its dependence on c is implicit, but its dependence on is explicit. The following theorem presents this value, based on which demonstrate that the Wasserstein robust loss Ri can be expressed as the nominal loss plus an additional term Di'1' -1 (t)) 1's" > 1) that prevents the classifier from becoming overly certain on the data.
Theorem 3.3 (Closed-Fool Form Robust Risk). The optimal value of in 10) is given by v - (11)) (18")//²
and the resulting robust risk expressed as
5. = ウ
plo) 1900 1 (0)))
7

---

Remark 3.7. Theorem 3.3 shows that minimizing the Wasserstein robust loss R. in (10) effectively minimizes the nominal loss R in [ip while simultancously penalizing terms associated with |ay] values exceeding certain threshold |a weighted by the corresponding reference probability values. This minimization prevents the classifier from becoming overly confident in certain data points, particularly when there are potential misspecifications in the approximated true label posterior.
Remark 3.8. As suggested by Remark 2.2 Theorem 3.3 provides a guideline for balancing robustness and model fitting by deriving the optimal value for y in (TO.. In Section 3.3 update method for determining Tip
we develop a one-step
3.3 Training using Conditional Distributionally Robust True Label Posterior
In this subsection, we outline the steps for approximating the true label posterior. constructing the eseudo-empirice distribution as the reference distribution for solving the robust risk minimization problem (5) and subsequently training classifiers robustly. The pseudo code for the training process provided in Algorithm [ in Appendix [ Here we elaborate the details.
Approximating noise transitions probabilities. We begin by warming up the classifiers on the noisy training data, denoted D y where y; represents the majority vote label for instance x;, determined by the label that receives the highest number of votes from the annotators. After warming up the classifiers for 20-30 epochs, we sort the dataset by the cross-entropy loss values and collect subset of size m. with the smallest losses, denoted as Dÿ = {xi, Vs ) 1= where m < n, and the ratio of m to n is set to minus the estimated noise rate. Next, we estimate the noise transition probabilities by (y) = Σn 1 y:. j)/E>> (y; j) for y E [K] and j E [K] (Line 1 of Algorithm D. With (y), we then itcratively update the approximated true label posterior, construct the eecpriceai distribution, and robustly train the classifiers (Lines 2-13 of Algorithm requency-counting method for noise transition estimation for simplicity. However, our approach is versatile and can be integrated with various methods for estimating the noise transition matrices or the true label posterior. Additional experimental results using more advanced transition matrix estimation methods are provided in Appendix B
D. Here, we employ the straightforward
Constructing a pseudo-empirical distribution. We train two classifiers, e)(1)) and 2)(2), in parallel each serving as an informative prior for the other. In the 4th epoch, the approximated true label poste-
rior with prior vi(0) is updated as PJ (x. 3) A pl)(Y = =jl = y, x = x) x v5 (0) (X) (Line
of Algorithm D. where w/(h) (x) denotes the jith element of the vector-valued function (6(0 (x) for E
[K] and y = 2. As described in Remark 3.1 for E [v]]. if P (x., maxj p(0) (x, 2 e for a pre-specified threshold e > 1, we assign the robust pscudo-label y = k* to the instance and collect it into Di,, (Lines 5-7 of Algorithm Tp. The pseudo-empirical distribution Pt. is updated based on D (Line of Algorithm
Robustly training the classifiers. For = 1, let \. if = 2; and \v A 2f 1. With the updated
distribution, the classifier zb(*) is then trained by minimizing the empirical robust risk b with the reference distribution P. (Line 9 of Algorithm D. After updating the
classifier (60 with 7: from the previous iteration, we take one step to update the value 7/%) In particular, suggested by Theorem 3.3 we use Yo, = |a(*))/ R2 as reference value for (Lines
11-12 f Algorithm
1.. We then update ?t
(c) by minimizing [7(ee Ep;, c'(y', Y)) + 2 - 7o)3 ]
(Line 13 of Algorithm with respect to 7. where yf' is determined by (5) after updating v((,), and > 0 is a positive constant that determines the learning rate of 7.
4 Experimental Results
Datasets and model architectures. We evaluate the performance of the proposed AdaptCDRP on two datasets, CIFAR-10 10 and CIFAR- (1I, by generating synthetic noisy labels (details provided
below), as well as four datasets, CIFAR- ION 22), CIFAR-10ON (22], LabelMe 23 24], and Animal- 1ON [25] which contain human annotations. For all datasets except LabelMe, we set aside 10% of the original data, together with the corresponding synthetic or human annotated noisy labels, to validate the model selection procedure. We use the ResNet-18 18 architecture (26) for CIFAR- 10 and
8

---

Table Average accuracies (with associated standard errors expressed after the + signs) for learning the CIFAR-10 and CIFAR- 100 datasets (R = 5).
CIFAR-I0
CIFAR-100
Method
IDN-LOW IDN-MID IDN-HIGH IDN-LOW IDN-MID IDN-HIGH
CE (Clean)
88.60
58.75
CE (MV)
20.90
76.05+0.70 70
69.6541.73
50.96-0.42
44.80+0.90
38.51 30.51
CE (EM) 7
01.15
75.84+0.97
69.85.1.43
11.29=1.00
45.2440.41
38.01=0.00
Co-teaching 30
83.08=0.52
80.58+0.36
81 81.30=0.62
53.10
47.25:10.82
44.11
Co-teaching
31
81.17:0.55
78.23
71.8411.13
53. 53.10.0.64
47.9210.76
01.33::0.61
CoDis 32
80.33=0.39
82.0240.41
78.67
58.
68.66.0.44
52.27
46.12=20.66
LogitClip
33
85.39
80.87
75.36:10.79
57.79-0.77
53.1440.37
49.00=0.35
DoctorNet
34
01.85=0.41
78.69
76.26
50.61
47.80
43.50
MBEM 9
82.37
78.05
71.43+2.48
52.20=0.07
45.26
38.9240.69
CrowdLayer
27
83.98-4.35
77.76+1.06
67.77+1.69
51.28
45.28
38.93
TraceReg [12
80.72:00.79
11.36
67.8611.77
51.43
45.08
38.6911.01
Max-MIG
81.00=0.72
75.90+0.52
70.96+0.96
51.76+1.11
44.93+0.71
38.70
CoNAL [35
81.60.0.82
76.02+0.79
60.50+1.89
51.61+1144
44.1940.62
38.24 38.2440.29
CCC [36]
84.8120.89
81.29
17.28
56.65=0.65
50.68
43.94_00.96
Ours (AdapiCDRP) 88.09 87.37
86.6220.45
60.20
56.65+1.00
54.24=2099
CIFAR- ION, and the ResNet-34 architecture [26] for CIFAR- 100 and CIFAR-100N Following 277. we employ a pretrained VGG-16 model with a 50% dropout rate for the LabelMe dataset. In line with (25,, the VGGI9-BN architecture [28 is used for the Animal-10W dataset. Further details on the datasets and experimental setup are provided in Appendix B.I
Noise generation. We generate synthetic annotations on the CIFAR-10 and CIFAR-100 datasets using Algorithm 2 from (29). Three groups of annotators, labeled as IDN-LOW, IDN-MID, and IDN-HIGH, are considered, with average labeling error rates of approximately 20%, 35%, and 50%, respectively, representing low, intermediate, and high error rates. Each group consists of R annotators. To assess the algorithms in incomplete labeling setting, we randomly select only one annotation per instance from the annotators for the training dataset rather than using all available annotations [10]. Further details noise generation are provided in Appendix B.I]
Comparison with SOTA methods. We compare our method with a comprehensive set of state-of-
the-art approaches, including: (1) CE (Clean) with clean labels: (2) CE (MV) with majority vote
labels; (3) CE (EM) 7 (4) Co-teaching [30; (5) Co-teaching+ : (6) CoDis 32); (7) LogitClip
333; (8) DoctorNet 34 (9) MBEM 9 (10) CrowdLayer (27]: (11) TraceReg 12: (12) Max-MIG
11: (13) CoNAL
35 and (14) CCC 36.. We report the average test accuracy over five repeated
experiments, each with a different random seed, synthetic datasets, CIFAR-10 10 and CIFAR- 100, with instance-dependent label noise introduced low, intermediate, and high error rates. Standard errors shown following the plus/minus sign (=), and the two highest accuraries are highlighted in bold. Table 2 presents evaluation results on four real-world datasets. As shown, our AdaptCDRP consistently outperforms competing methods across all scenarios. To further explore the impact of annotation sparsity, we conduct additional experiments with the number of annotators ranging from to 100, with each instance labeled only once. Figure iillustattes the average accuracy across different numbers of annotators on CIFAR-10, 10, highlighting the advantages of the proposed method under diverse settings. The results for the CIFAR- 100 dataset are shown in Figure 3 in Appendix B.2
Hyper-parameter analysis. We investigate the impact of the hyperparameter e the empirical robust risk 5b. Under our experiment setup, should be chosen within (0. 1/K) for K-class classification problem with K 2 2 as demonstrated in the proof of Theorem 3.3 in Appendix(A.. AA.8 Hence, we take E 00,0.1) for CIFAR-10 10 and E (0, 0.01) for CIFAR- 100, with the results presented in Figure 2 The results suggest that setting near zero leads to relatively low test accuracies, highlighting the importance of CDRO under model specification when handling noisy labels. Furthermore, continually increasing c eventually results in a drop in accuracy due to excessive noise injection into the data.
Additional experimental results. To further evaluate the performance of the proposed method across various scenarios, we conducted additional experiments, detailed in Appendix B.2 Specifically, we compare different annotation aggregation methods, present average test accuracies and robust pseudo-label accuracies during training, assess sensitivity to the number of warm-up epochs, explore different noise transition estimation methods, and examine the impact of sparse annotation.

---

Table 2: Average accuracies (with associated standard errors ex- pressed after the + signs) for learning the CIFAR-ION, CIFAR- 100N, LabelMe, and Animal- ION datasets.
0051 B005 0.31
1/R
030 U.
505
Method
CIFAR-ION CIFAR-10ON
LabelMe
Animal-10N
CE (MV)
82.82
0..26
79.49
79.88
CHARIOLOW CHPIRIOMIH CHARIOEGGH
CE (EM)
83.14
69
50.6420.55
80.1840.34
Tesl Ansurncy
Co-tcaching
85.66+0.54
52.34=0.31
+9.71
81. $1.9644o.4 48
Co-teaching+ 31
82.25:1.:1
50.52 40
81.55
81.24:10.22
CoDis 32
87 27.44-40.45
04.46
$1.85
73.0840.35
LogitClip
33
86.37
51.50=0.59
01.75
70.89 6.665
DoctorNet
34
84.5210.69
40.21
79.09=0.40
79.96110.55
MBEM 9
85. 40.494
46. 06.74
10.10
76 76.17
54
CrowdLayer
27
82.8440.24
47.43
02.2
79.70
TraceReg
12
82.94+-0.27
40.71
83. #0.15
80.34440.66
82
Max-MIG
15.32
46.5620.61 64
83, 83.25.10.20
79.78.10.80
50
CoNAL [35
83.01+0.21
=9.37=0.48
82.96
80.45++0.49
typerparameeer (CFARR
CCC
[6
60.55
48.57 0..58
83.18 0.38
78.36++0.35
Figure 2: Average accuracy the
CIFAR-I0 and CIFAR-100 datasets
Ours (AdaptCDRPP) 88 88.25+4..3
53.42
83.36
83.08.um 088.0.33
(R 5) for different values.
EX001
No
Tramr
384
Good Apa
Norbor A'reebare
Munber ddrrarann
Namber alannaetee.
(a) IDN-LOW
(b) IDN-MID
(c) IDN-HIGH
Figure I: Average test accuracy on the CIFAR-10 dataset with varying numbers of annotators. The shaded areas are constructed using the associated standard deviations.
5 Conclusion
In this paper, we address the challenge of learning from noisy annotations by estimating true label posteriors using the CDRO framework. We formulate the problem as minimizing the worst-case risk within distance-based ambiguity set, which constrains the conditional distributional uncertainty around a reference distribution. By deriving the dual form of the worst-case risk and finding the analytical solution to the robust risk minimization problem for each data point, propose novel approach for determining robust pseudo- labells using the likelihood ratio test. This approach further leads to the construction of pseudo-empirical distribution that serves robust reference probability distribution in CDRO. We also derive closed-form expression of the empirical robust risk and identify the optimal Lagrange multiplier for the dual problem. This leads guideline for balancing robustness and model fitting in a principled way and inspires an efficient one-step update method for the Lagrange multiplier.
Limitations and Extensions. Our development here does not focus on precisely estimating the noise transition matrix or the true label posterior. Further research may be conducted to address the sparse annotation problem and improve estimates of the true label posterior. This can be accomplished through several approaches: (1) employing regularization techniques to mitigate the impact of small sample sizes by smoothing estimates and reducing sensitivity to outliers; (2) leveraging subgroup structures among annotators to capture additional nuances; and (3) directly modeling the true label posterior by integrating both data and noisy label information, moving beyond the limitation of purely applying Bayes's 's rule.
10

---

Acknowledgements
Yi is the Canada Research Chair Data Science (Tier 1). Her research was supported by the Canada Research Chairs Program and the Natural Sciences and Engineering Research Council of Canada (NSERC).
References
[1] lan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT press, 2016.
[2] Jürgen Schmidhuber. Deep learning in neural networks: An overview. Neural Networks, 61:85-117, 2015.
[3] Devansh Arpit, Stanislaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kan- wal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, al. A closer look memorization in deep networks. Proceedings of the 34th International Conference on Machine Learning, volume 70, pages
2017.
[4] Raymond J Carroll, David Ruppert, Leonard Stefanski, and Ciprian M Crainiceanu. Measurement Error in Nonlineur Models: A Modern Perspective. Chapman and Hall/CRC, 2006.
[5] Grace Y Yi. Statistical Analysis with Measurement Error Misclassification. Springer, 2017.
[6] Grace Y Yi, Aurore Delaigle, and Paul Gustafson. Handbook of Measurement Error Models. CRC Press, 2021.
[7] Alexander Philip Dawid and Allan M Skene. Maximum likelihood estimation observer error-rates using the em algorithm. Journal of the Royal Statistical Sociery: Series C. 28(1):20- 1):20-28., 28, 1979.
[8] Jacob Whitehill, Ting-fan Wu, Jacob Bergsma, Javier Movellan, and Paul Ruvolo. Whose vote should count more: Optimal integration of labels from labelers of unknown expertise. In Advances in Neural Information Processing Systems, volume 22, pages 2035-2043, 2009.
Ashish Khetan, Zachary C Lipton, and Anima Anandkumar. Learning from noisy singly-labeled data. arXiv preprint arXiv:1712.045777 2017.
[10] Hui Guo, Boyu Wang. and Grace Y Yi. Label correction of crowdsourced noisy annotations with an instance-dependent noise transition model. In Advances in Neural Information Processing Systems, volume 36, pages 347-386, 2023.
[11] Peng Cao, Yilun Xu, Yuqing Kong, and Yizhou Wang. Max-mig: an information theoretic approach for joint learning from crowds. arXiv preprint arXiv:1905.1344 2019.
[12] Ryutaro Tanno, Ardavan Saeedi, Swami Sankaranarayanan, Daniel C Alexander, and Nathan Silberman. Learning from noisy labels by regularized estimation annotator confusion. Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 11244,1253, 2019.
[13] Ravid Shwartz-Ziv, Micah Goldblum, Hossein Souri, Sanyam Kapoor, Chen Zhu, Yann LeCun, and Andrew G Wilson. Pre-train your loss: Easy bayesian transfer learning with informative priors. In Advances in Neural Information Processing Systems, volume 35, pages 27706-27715, 2022.
[14] Xiaoho Xia, Tongliang Liu, Nannan Wang, Bo Han, Chen Gong, Gang Niu, and Masashi Sugiyama. Are anchor points really indispensable in lahel-noise learning? In Advances in Neural Information Processing Systems, volume 32, pages 6838-66 9838-6849, 2019.
[15] Hisham Husain and Jeremias Knoblauch. Adversarial interpretation of bayesian inference. In Proceedings of The 33rd International Conference Algorithmic Learning Theory, volume 167, pages 553-572. Proceedings of Machine Learning Research, 2022.
[16] Alexander Shapiro and Alois Pichler. Conditional distributionally rohust functionals. Operations Research, 2023.
[17] Jose Blanchet and Karthyek Murthy, Quantifying distributional model risk via optimal transport. Mathe- matics of Operations Research, 44(2):565-666 2019.
[18] Rui Gao and Anton Kleywegt. Distributionally robust stochastic optimization with Wasserstein distance. Mathematics of Operations Rexearch, 48(2):033-65 2023.

---

[19] Daiki Tanaka, Daiki Ikami, Toshihiko Yamasaki. and Kiyoharu Aizawa. Joint optimization framework for learning with noisy labels. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5552-5560, 2018.
[20] Thomas M. Cover and Joy A. Thomas. Elements Information Theory. Wiley-Interscience,, 2006.
[21] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[22] Jiaheng Wei, Zhaowei Zhu, Hao Cheng, Tongliang Liu, Gang Niu, and Yang Liu. Learning with noisy labels revisited: A study using real-world human annotations. In International Conference on Learning Representarions, 2022.
[23] Filipe Rodrigues, Mariana Lourenco, Bernardete Ribeiro, and Francisco C Pereira. Learnnng supervised topic models for classification and regression from crowds. IEEE Transactions on Pattern Analysis and Machine Intelligence, (9(12):2409-244 2017.
[24] Antonio Torralba, Bryan C. Russell, and Jenny Yuen. Labelme: Online image annotation and applications. Proceedings of the IEEE, 98(8): 16771144, 2010.
[25] Hwanjun Song, Minseok Kim, and Jac-Gil Lec. SELFIE: Refurbishing unclean samples for robust deep learning. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 5907-5915,201 2019.
[26] 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, pages 770-778, 2016.
[27] Filipe Rodrigues and Francisco Pereira. Deep learning from crowds. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, pages 161 1611-1618, 2018
[28] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recogni- tion. In International Conference on Learning Representations, 2015.
[29] Xiaobo Xia, Tongliang Liu, Bo Han, Nannan Wang. Mingming Gong. Haifeng Liu, Gang Niu, Dacheng Tao, and Masashi Sugiyama. Part-dependent label noise: Towards pustance-depender label noise. In Advances in Neural Information Processing Systems, volume 33, pages 7597-7610. 2020.
[30] Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co- teachchhing: Robust training of deep neural networks with extremely noisy labels. In Advances in Neural Information Processing Systems, volume 31, pages -237, 2018.
[31] Xingrui Yu, Bo Han, Jiangehao Yao, Gang Niu, Ivor Tsang, and Masashi Sugiyama. How does disagreement help gencralization against label corruption? In Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 7164-7173, 2019.
[32] Xiaoho Xia, Bo Han, Yibing Zhan, Jun Yu, Mingming Gong, Chen Gong, and Tongliang Liu. Combating noisy lahels with sample selection by mining high-discrepancy examples. In Proceedings of the IEFF/CVF International Conference on Computer Vision, pages 1833-1843, 2023.
[33] Hongxin Wei, Huiping Zhuang, Renchunzi Xie, Lei Feng. Gang Niu, Bo An, and Yixuan Li. Mitigating memorization of noisy labels by clipping the model prediction. In Proceedings of the 40th International Conference on Machine Learning, volume 202 pages 36868-36886, 2023.
[34] Melody Guan, Varun Gulshan, Andrew Dai, and Geoffrey Hinton. Who said what: Modeling individual labelers improves classification. In Proceedings of the AAAI conference on artificial intelligence, volume 32, pages 3109-30 3118, 2018
[35] Zhendong Chu, Jing Ma, and Hongning Wang, Learning from crowds by modeling common confusions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5832-5840, 2021.
[36] Hansong Zhang, Shikun Li, Dan Zeng, Chenggang Yan, and Shiming Ge. Coupled confusion correction: Learning from crowds with sparse annotations. In Proceedings the AAAI Conference Artificial Intelligence, volume 38, pages 16732-16740. 2024.
[37] David G Luenberger and Yinyu Ye. Linear and Nonlinear Progranming, volume 2. Springer, 1984.
[38] Stephen P Bradley, Arnoldo C Hax, and Thomas L Magnanti. Applied Mathematical Programming. Addison-Wesley Publishing Company, 1977.
12

---

[39] Martin J Wainwright. High- DithtniDimmmii Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2019.
[40] Jacho Lee and Maxim Raginsky. Minimax statistical learning with wasserstein distances. In Advances in Neural Information Processing Systems, volume 31, pages 2687-2696. 2018.
[41] John Hunter. The supremum and infimum. pdf
www...a.t...mmm www.:/aatt.uddviiisss.mmmmm ucdavis edu/ http://uttee/tt///hhhhee
[42] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2018.
[43] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 14Xiv:1412.698// 1412.6980, 2014.
[44] Hongwei Li and Bin Yu. Error rate bounds and iterative weighted majority voting for crowdsourcing. arXiv preprint arXiv:1411. 1406, 2014.
[45] Maria Sofia Bucarelli, Lucas Cassano, Federico Siciliano, Amin Mantrach, and Fahrizio Silvestri. Leverag- ing inter-rater agreement for classification in the presence of noisy labels. In Proceedings of the IEFF/CVF Conference on Computer Vision and Puttern Recognition, pages 3439-344 3448, 2023.
[46] Songzhu Zheng, Pengxiang Wu, Aman Goswami, Mayank Goswami, Dimitris Metaxas, and Chao Chen. Error-bounded correction noisy labels. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pages 1447-11157, 2020.
[47] Shahana Ibrahim, Nguyen, and Xiao Fu. Deep learning from crowdsourced labels: Coupled cross- entropy minimization, identifiability, and regularization. In The Eleventh International Conference on Learning Representations, 2023.
13

---

SUPPLEMENTARY MATERIAL
A Technical Details
A.1 Preliminaries about Linear Programming and Concentration Bounds
linear program (LP) an optimization problem of the form
max C x
x
s.t. Ax <
(A1)
X 0,
where e E R" and b R. are given, and elementwise inequality for vectors. The expression с x is called the objective function, and the set {x E R" Ax b, x 2 0} defines the feasible region the linear program. By introducing slack variables, any linear program can be converted to the following standard form:
specified m x n matrix. Here, "S" represents
max C X xE
s.t. Ax b
(A2)
x 2 0.
We begin by introducing the concept of extreme point of related properties.
Definition A.1 (37 Chapter 2)). A point in convex set θ is called extreme point of θ if there do not exist two distinct points z', z" E and scalar v/ with 0 < v < such that z = vzz (1 1/2z".
The following lemma shows that optimal solutions of a linear program are located among the extreme points.
337 Chapter 21). If linear programming problem has a finite optimal solution (i.e., feasible solution that optimizes the objective function), then there is finite optimal solution that is an extreme point of the constraint set.
Lemma 1
The following lemma on strong duality in linear programming will be used in the proof of Proposition 2. and Remark 2.3
Lemma 2 (Duality Theorem of Linear Programming: 38 Chapter 4)), Let (ct,..., CT) and T be given vectors, and let A = [a:y] be given m X matrix with a.j being its (i.j) element. Define the primal problem as:
= (bi....,be )m)
P, with P A
21 21 ER
s.t.
Σ aijoy S for E [m],
1=1
Iÿ 2 for j E [n].
or equivalently written in compact form:
max P, with A T x and x = (xI,..., 2n)
XER
s.l. Ax b,
X
The corresponding dual linear problem is:
min
D. with D A
bayi
1I y.
s.f.
aijl 2 oj for j E [n].
yi 2 0 for E [m].
14

---

or equivalently,
min D, yEk
with D 2 y T and y = (y),.... Mm)
s.t. y Att.'Asc Ac'
2 0.
If the primal (or dual) problem has a finite optimal solution, then the dual (or primal) problem also has finite solution, and the optimal values of the primal and dual problems are equal.
Next we introduce concentration bound along with associated concepts, which will be used in the proof of Theorem 2.2
Let S denote a subset of R and f : S2" + R. We say that a function ff satisfies the bounded difference with parameters {I,,..., In] } for any k E [m]].
inequality
39
sup
[f Sk..... Sk.
sn) f(s1,..... , sk...,, sn)) S Lx
(A3)
EE
That is, for any k E [n). if we substitute 8% with s while keeping other 8y fixed for all j A k; the function f changes by at most Li-
Lemma (Bounded Differences Inequality; 39 Corollary 2.21I). Let = (Si...., Sw)T represent random vector with independent components defined sample space Ω2, and f(S) & f(Si...., Sn) for function -2" R. Suppose that f satisfies the bounded dif- ference property with parameters (II...., L,}- Then, for any Z 0.
21
P(S(S) B(S(S)) 2 exp
Σ1=1 1.2
212
[[((S) - B(f(s)) < -t] S exp
>
L.
We also introduce the following definitions and lemmas, which will be used to characterize the complexity of the function class.
Definition A.2 (Covering number; 39 Definition 5.1]). Let O denote a set and p metric on Ô. For
t >> 0, t-cover of è with respect to is set {0; O : ,.....N7 .N} such that for each E O, there exists some E [N] such that p(0. 0,) S The t-covering number (t; θ p) the cardinality of the smallest t-cover.
Lemma 4. Let Gj be set equipped with metric Pj for = 1,2, and define Q = O, x O2.
Given 01, 02 > O, define the metric p on θ as p(0,0) 0') & aIPi(0) ,00) + a2p2 (02, (02,00 02 for any
0 A (0) ( and of & (0", 0²') E O. Then for O,
O) & N(t/(2a)); pi) x N(t/(2a2); 02,
Proof. For j = 1,2, let θ 10 0x denote the smallest
of θ with respect
Pj. Then, by Definition A.2 (tt/(2a,); G, p.) Ny for j 1. For any 0 (0 02) θ
by definition A.2 there exists [Nr] and d2 E [Na] such that p1(0), 00,)) I t/((a1) and
p2(02, 022) < 12(2). Then, 0, 2 (0), 0g θ x O₂ C O, and and
000,0) = app(( 0%,) + a0 ..))) St.
Hence, by Definition A.2 θ Q a of θ with respect to p and (tt 0, < 1 θ2 N1 N₂ = ((t/(2a1): O1, x (2t)(2a2): O2, P2), where represents the cardinality of set.
Lemma 5. Let I b] C IR denote closed interval on IR with < b. Define the metric on I as p(x,x')= = | - x'1 for any x, x' E I. Then, for any & > 0, II; N(::I,p) 1 ift > b-
<
b-a
+ 1
b-a and 2
2t
15

---

Proof. Let = =1-20 where |.] represents the floor function. To prove the first result for b- 2 2t,
construct the following subset I I:
I I a +t, + 4t ................................ a+t+ (ne 1). 2t, min(b, a + t nt -21)
Clearly, I C Uk + 21(k - 1),a + 2th U la + 2tn bj. Next, we verify that I is t-cover of I with respect to metric p. Specifically, for any 2 I. there exists & [nc] such that [a + 2t (l- - 1), a + 2t k), or x E (a + 2tn, bj. For the former case,
px. a t 2t (K 1)) t;
and for the latter case,
p(z, min(b, a + + nt. 2()) S t.
Hence, by Definition A.2 first result is then established.
a l-cover of Z, therefore (I; p) s [Z] = The + 1
b-a 2
+ 1. The
The second result for b S follows from the fact that {a + b-a is f-cover of since p(z, a b-a 2
2
I b-a
2 < for any E.
Definition A.3
39 Definition 5.16)). A collection of zero-mean random variables {So θ is sub-Gaussian process with respect to a metric on θ if, for all 01, 0g E θ and t E IR,
t (0,,
E /exp {t(Se, Sp,)]] S exp
Lemma (Dudley's Entropy Integral Bound; modified from Theorem 5.22 of (39)). Let (So 0} be a zero-mean aab-Gaussian process with respect metric p on O. Then,
8V2 [
E
sup So LEE
Vlgg NI;
where ((;; θ p) represents the 1-covering number of O with respect to
A.2 Proof of Proposition 2.1
Strong duality can be established using Theorem 1 in [8] by capitalizing the discrete nature of the sample space V, can present more concise result. To see this, here we provide an alternative proof of strong duality using the duality principle in fiite-dimensional linear programming, detailed below.
which applies to general cases. However,
For every fixed x X, ÿ E yR, & e V, by re-writing the the constraint Qyxx. (e((ysss)) in using Definition 2.1 we re-express the primal problem as:
// ((((x) П)P()²) { sup
d ftt.:///a...../////////a//a..aa (( s e", II))-) = Py)os().
P A
Given the discrete nature of the sample space V, P. can be reformulated as the following finite- dimensional linear program:
{(((x),5)7T)) )
Σ
Ry with j.KE(K]
j.EEKK
Σ c(i Se,
s.t.
P
j.kE[K]
K
Σ Jik = Pylx,((1) (k) for & E [K],
j=1
Z5 2 0 for j. k E [K].
16

---

where ТÿA = II(Y =.Y f, dual variable. Introducing the dual variables y and for le E [K], the dual linear program for P, is then expressed as
[K]. By Lemma 2 each primal constraint corresponds to
K {re* Σ
min T.REE with
(
kE[x]
D.
(A4)
s.t. (j.k) T ((v((x)) for j. & E [K],
7 2 0,
where first constraint can be written as The 2 [ (((W((x,)) (j) Therefore, to minimize the objective function in (A4), the value of the dual variable Tr should be taken as maxje[K] {((v(x).)) - -c (i,k)} for each y 2 and [K]. Hence, the proof established.
A.3
Proof of Remark 2.3
As in the proof of Proposition 2.1 the optimization problem in 66) can be written as
P. A sup
E B (((((x))
d d(Q Px)x, {
Σ / ((v((;) (y.y):
Σ>/
/ cltyy' y (y. (y.y') Sc
sup n se)
n Pylx.s (-) for E [m]
where the first step is due the definition of the empirical distribution p(a) and the second step "x."*
holds by re-writing the constraint 1 Ei= d(Q x 3. sy) S using the definition the the Wasserstein distance d(- (.,;) given in Definition 2.1
P. can be further expressed as the finite- dimensional linear program:
((b(()))))) (4)
max "jk ER with KE[m),J.EEIR
n 1=1 A.
8.l. Σ Σ
c(ikk) Se,
P
(ml
j,kE(K)
K
Σ
(8)
= P. (k) for E [n] and &: E [K],
jik
J=1
(
2 0 for i [n] and j, k [K],
Tjk
(1) 11 (Y j' = k) for i [nd] and j. k [K]. where jjk
( By Lemma 2 and introducing dual variables and Th with E [m] and A E [K], the dual linear program for P. is expressed as
K
min
7c
P (k)
(K)
7ork
(1) ER for &E(n) and KE[K]
i=1 k=1
D.
8.1. Y k)) + -k
(2)
2
E (x: for E [m] and j, [K],
n
7 220,
n rc+
Ps (b) }.
min Tir (4) ER for tE(n) and kE[K]
n
i=1k=
8.l. volj.k k) 7(0
{(v((x)))) for [m] and j. & E [K],
? 2 0,
17

---

where we let 7(6) - = for i E [n]] and & E [K] in the second step. Thus, the proof is completed.
A.4 Proof of Theorem 2.2
We begin by demonstrating that, for various choices of the reference distribution, the optimal value for in the relaxed dual problem, as stated in (4), is constrained to a compact set. The proof techniques in [40] are used.
Specifically, for a given é > 0 and eé E V, let
> E arg inf Ex.9 yee + ERASS 720
sup {(()()).)) - ( (i]))))))))
D'EY
Noting that for any x E X' and y E V. sup, {e(eb(x), ((v((x))))) 3 cd(((ll))) 2 (E(b(x),,)) - {(b(xx,,)) 7 c"' (1V'
(V). y) gy = 0. we obtain that for any y 2 0, (v/ {)}
Ne Ep l + Ex.y
Bryxs sup (((v(X), ((((x), yEY
EpynS sup (((*()), 1/) - (((()),))))))))))))))))()))))))- - 700 (.)))))))))) mn1))
Sye + -x.v
VEY
(L. - -0' m111
Sye + Ex.y
Ep, Epyin
sup vEY
SyeP + sup Idl y1²)
(A5)
120
where the second inequality is due to the definition of y"; the third inequality comes from the Lipschitz property the assumption; and the last inequality holds because c(y'. Y) = m1l * Y) takes values in {0, k), leading supyeyy { {L. cly', Y) - y.. cy (Y) SUP(E(D.N) {Ll - (I-->1P) S
sup:20 Lt yt"), which is a constant.
Now, we show that
7" S Le Le (p-1) M
(A6)
Indeed, when p = 1, then taking L in A5 shows A6 When p > 1, then Lt ytt in A5
takes its maximum value at 1" = (I/(p>))
1), and hence, A5) yields that for any 2 0,
Ee SYEp + L /L/ (m 1/ 7/ (LL(p/)))////1) =ye- + -PPLP--//)))))-- 1/(p-1)) 1--1))pppp--00
p((p p/(p->)( (p- 1).
Therefore, taking 7 L/(pet-1 leads to -- Le, i.e., (A6) holds.
Next, let b,, (x) A Epyny supyey (e(1((),,)) (') - Y)} For every & E V we have that
for any (x,5) E X x yR.
R. (bb: py) - R.: Pylxss)
= inf Ex.5 yee SeP++EP EPSINS V'EY
sup (E(v(X), v/) - -20() x11))
720
sup (E(v(X), 70 y31)) y'ey'
inf E p(o) 720
YEP + PEPPs
inf US"SM
Exi { TE + (X, 8)} - USTSM
inf E Epnn {reP exo {x)
|BR.s { (on 8 Epi (x,
< sup
(X,
0SY5M
(D)
(A7)
where the first equality comes from 4 and 5 the second equality follows from (A6) and the definition of Engi. and the third step is due to the fact that iinfee f(v) - infren g()) S
suP (f()) g(v) for bounded functions f.g A + R [1 Proposition 2.18].
18

---

In (A7 we use D to stress the dependence of B ppny (X, })} on the observed data of size n, as x.
defined in Section 2.1 and let & represent the resulting function mapping from (x' )utt " to I., with (D) being the value for data D, where (Xt x ) is the Cartesian product of multiplying X' x y a times. The function Φ : (X' x ) - IR defined in (A7 satisfies the bounded difference property Mf J. where M represents the upper bound of the loss function in the assumption of Theorem 2.2 Indeed, for any l E [n],
A3 with parameters { 4
sup 21 Saa E ExxyR
(22,,..., ,k....., 2n) (21 2 ,....., zn)
Ex,ÿ (x, 81 -
sup 2 EXxyR
sup 05YSM*
E vvv (zi)
i=1
sup M
Ex.8 { ( (X,Y) 8)} Σ
(xp((z))
w. + 1
1=1
Ex, { (, (X, 8)} - 1 Σ Ex (z))
sup
xXXx 0S
71
Ex,S { (er 87}
Σ fo
1
n (
n
n
1 (. (nl
1
sup d R
DSYSM"
n
n
M
n
where the second step holds since sup.c A f(v) suupwe g(v)| S suP [f(v)-g(1)) for bounded functions f.g : A + R [41 Proposition 2818], the third step due to the triangle inequality for absolute values, and the last step holds since e, E [0, M] by definition.
Thus, by letting t My / log(1/n) in lemma have that, with probability at least 2n
7
log( (1g(1/))
(DD <Ex, (o(D) MV
(A8)
2n
Similar to the derivations for (3.8)- in the proof of Theorem 3.3 in 42
we obtain that
n (X, Y.)
Ex.ÿ (o(D)) S 2E
sup ME(0, n
Σ
oz (X,
(A9)
where {a,}%= are independent random variables chosen from (-1, +1} with equal probability, and the expectation is taken with respect to all involved random variables.
Applying
A8 and (99 to (A7) gives that with probability at least 1 - 77
log(1 (1/(
RV Pylx,) (:: Py Pyxxs))
S 2E
sup TE(O.M
Σ
oz v (X, Y.)
+ +MV
2n
(A10)
Now identify entropy based upper bound for the right-hand side of A9) using the proof techniques in [40] and Example 5.24 of [39]. Specifically, for given t), we define the random pro-
cess { S, VR E of XX, Y,) 7 E [0, ] By using I[(a.) 0 and the independence
between and (X,, Y:), we obtain that B(S,) = J Enn EE e, (X, Y.} = 0. For any
19

---

71, E [),
L (x,8) 2 (x,
= =EEpy sup {((V(x), 3/) - -nd' (o/,Y)) Y)} -Byss sup ((((()))))) - (2/, v'Ey
N'EY'
<Bprins
sup {e(v(x), 1/) m (e/,,))))) Y)} y'EY'
sup ((((x)))/)) - -2
y'ey
sup y'Ey
mic (y'; Y) - '20 Y)
= m - 7
(A11)
where the second inequality is due to the fact that s f supa gl S supa If gl for bounded functions f.g A + R [4T] Proposition 2.18], and the last step due to the fact that cly/, Y) can only take values in (0.
Hence, for E R, we have that
E Beel -11))
}
=E
exp
t
{
(X, Y1) (a x.)1
vn
(X,, Y.) - Ga, Y.
exp
Vn
(<x2 m1 - ?2))
exp
(A12)
2
where the inequality is due to Hoeffding's ' lemma and A11 Thus, {S,, : [0, Mr] is zero- mean sub-Gua Sabb-Gassian process with respect to metric py, defined as (71 72) = kP1n 7/2 for any Ti, 72 E [0, M*). Therefore, by Lemma 6 we obtain
Σ 1=1
ogly (Xi, x.)
E
sup (0.MM
sup M-
Sy
vn
8/2 0
Viog.N(t: [0, M Px
Vn
Jn
8/2
VlogN(t/w0 (0, M
1)tt
VT
J
8/2KP 100
/lgg N(; 10, M 1,1
ds
Vn
8/2KP
12
M
log
+
ds
Vn
2s
2
M'
M
log
ds
Vn
8/2
1/2
M RPP
v / 1/u)du
Vn
Av2l + Vieeffll Vlog 2)}
MP
(A13)
Vn
where the third step comes from the fact that, by the definition of py, Pr (71,72) S / if and only I/ 72/ t/k²; the fourth step holds by letting t/ kP; the fifth step follows from Lemma 5 the
20

---

sixth step comes from the fact that < M +1=
22
I M for E [0, 10,M/22; the penultimate
2a
step holds by letting u s/M' and the last step arises from the fact that
1/2
Vlog(1/u)de L/" 1/2
log udu L
1/2 log(u)
1
V-
-log
dsdu
2/5
log
/1/2
00
vlog2
00
e
2/8
duds
+
1og2
2/8
duds
2
log
2/88"
ds
vlog2
pc
vlog
VT
2wddw
+
erfe(
20
2
Vlog2
2w
2
where erfc(x)
Jar
E u²
dw.
/
Applying (A13) and A66) to A10 gives that with probability at least 1 - 77
8v2(vlog2 + Virerfel (Voge))
Ln
log(1/n) 2n
(v; (1:11))))))) - (v; Pybx,)
e + MM
Vn
15
log(1/n)
+ M
Vn
2n
where the last step is due to the fact that 8v2(vlog2 + Vweefc(yloog)) = 14.2 < 15. Hence, the proof is completed.
A.5 Proof of Corollary 2.3
By the definition of infwew (v;; Pypx)), for any Ç > O, there exists vhe E v such that R, (ybe; Pyix.) S inf R. (w:: Pyxx,) + Ç. Therefore,
R. (Veni Py(x,5)
inf Ri (v) Py(x.5)
Dev
<R. (Veni Ps Py1x,j) ( Pyix.s) ) + C
RM, (We.ni Py|x,5 Ri (wemn p))x5) + R. Pyxx,) -R (y(ss) + C
< sup (vi Py|x,5) - (v; Pylxx) +c.
NEW
Since the inequality above is true for all >> O, we have that
R. R. Pyix,) inf R. (1:; Pyx
NEW
<2 sup New
Rv(: Pyixs) RR. (.) Py/xss)
Ex,y { (X, 80) - E Epin (x,
<2
sup NEw M
(A14)
where the second inequality arises from A7
Similar to the proof of Theorem 2.2 in Appendix A.4 we can derive that
sup NEW M-
Exy fero(X 8)}
E Epint x5
(nr (
80)
log(1/n)
<2E
sup >
Σ
asyy. Y.)
-M
(A15)
2n
21

---

For any 71, 72 E MM and 1/1, 22 E V,
fn (x. 3) - sa (x, 3)
= =Bppyx.s sup N'EY
(x(()()),,)) - 7n1 " Y)} - Byyxs sup (((v2(x), - 22' Y)H
y'Ey
sup (((11(x),)) m sup y'Ey
(((v2(x)),) (2',
y'EY
<Bryyn
sup y'EY'
[nc Y) -2c Y) + (((1(())))) ( ((02(x),)))
51 + L' 1'1/4/ 2221
where the first step is due to the definition of &, defined after (A6). the second step due to Jensen's inequality, and the last step is due to the Lipschitz property with respect to the cost function c(:;))
defined in Theorem 2.2 in the assumption, and || 0/2ll0o - supxex' |/ (x) +x(()) for some
norm || ||-
Allowing de to vary, we modify the discussion for the random process {S,, : E [0, M*] in Appendix A.4. and consider the collection of random variables { (S A I
v Ei= ofly, X;, Y:):
E [0, M ab E }. Clearly, 1B(S),y)) = 0. Modifying the metric (7, 72) in Appendix A.4 we
define the metric ((y) 101,, (72, th2 xPIn - 72/ + L/Ils/ - vo2ll for any 71, 72 [0, M*) we obtain that for / E R.
and 1 1/2 E V. Similar to deriving A12
t (p 11), (72, b2))
E SeefStins-Sraann S exp
Thus,
{Sy : E [0, E V is zero-mean sub-Gaussian process with respect metric
Pr.v-
Let the Cartesian product [0, M*] x v denote the "parameter" space of (7, v). Then, by Lemma 6 we obtain
1 Σ oilnn Vii)
E sup JeD n
E
sup
Sy.00
MEDDMM-JNEE
8
V [t: x M dtt
Vn
J0
8/2
Vlg (N(1(2()))))) (0, M N(I/(21)); v, 1lx))
Vn
8/2
8v2
Nlog
1)tt +
Vlog Not((2( v, 11. 1la))d
Vn
Vn
16/2KP
16
Vlog N(:; 00, MM),
Ids
Vlgg N(:; V Ids
Vn
Vn
8v SV2(Vlog' Vieefel (oorfe(/oog2)) M"
16v2L/
Vlog N(s: V. 11 )ss (A16)
Vn
Vn
Here, for any set 9 and metric Ω2 (tt p) denotes the t-covering number for t > 0 as defined Definition A.2 In derivation of (A16), the third step is due to Lemma 4 fourth step is due Vlog(ab) (ab) & / log a + vlog for 2 and b 1; the fifth step results from a change of variable;
and the last line can be similarly proved as A13
22

---

By A14
A166
we have that, with probability at least 1 - 77
Re Pyxx,)
inf (1/; Pyix.5)
NEW
LRP 57
1
log (//))
EP-1 + +911'
Vlog | V. M 1100 ) ds
+ 2M
vn
2n
Therefore, the proof is completed.
A.6 Proof of Theorem 3.1
For ease of presentation, in this proof omit the dependence on and y in the notation. In particular,
let Po - y). Pi & Pi (x, y), and db _ (xx).. Let the objective function in ( be denoted as
((7 v) _ ye + Po max (T(1 - v) (()) - - + P. max - 1)) ykp T(b))- (A17)
To complete the proof, we begin by investigating the imner optimization problem in (8) by finding the optimal value of 7 Vg.. defined in Section 3.2 that minimizes g( v)) for each given vú and then address the outer optimization problem in ( by finding the optimal value ei* that minimizes g(T;: v). To this end, we eliminate the max operators in g(>; サ) based on the values of v. and use the assumption that T is a decreasing function in 7 As up takes its value [0, 1], we re-write the optimization problem (8) as
inf inf g(% v)) * d 1l 720
min
min inf g(v; min inf g(n; [ 120
min (0102) vi), ( v5)
(A18)
where v)) and (6g 25)) are the arguments of min e inf ( v1) and min p inf, inf (1) 2/2), respectively. We complete the proof by considering the following two cases.
Case 1: 1 E [0, H.
In this case, T(th) 2 T(H) 2 T(1 v1) 2 T(1 - 1/11 - 7KP.. Let
2o- T(+)) T(1 v21)
Consequently, have that
7e" + (o(T -
+ PIT T(b)) + +nne(e(e) - Po), if S 20:
g(y; he + PoT(1 -
(1)1))1)-1 + 111 PiT(b)) if 70-
(A19)
For given 4/1,
lim g(n lim s(n v1) e(e) (T(+)) - - T(1-41)) PoT v1) (1T())),
7-2%
7-7%
showing that g(3 vh) is continuous at "oo Therefore, for any given th (< v is continuous in ? over R
Then, for any given wh E [0, }). corresponding to the first term in (188), we obtain that
inf ((774)) = min 220
inf g(7 wh); inf 77770
ve(0.nl)
min g(7 ((rs)))) (0(101b)),
min
nejo.no
min g(7: 70(0,1))
-g(1,,
(A20)
23

---

where we use the continuity of g(;; 4/1 in the fact that g(y; 11) is increasing in when >> 7o- and the fact that a continuous function attains its infimum within any closed and bounded set IR Here,
Ve arg min p(733))) rE(0.rol
(A21)
for any 1/1 E [0. 21-
We complete the proof by the following two steps examine the range of Po-
Step 1: If Po < e(c), then, by (A19), for any given th E [0, 1 g(7; th is increasing in y over (0, n0]. showing that the optimal value in A21 is Y 0. Furthermore, because g( v1) = ( for
any t/1 [0, 1. we obtain that
min inf a(7 v) m
min 8( ((1))1)1)) 11)
min ((4))
e1e(0,8]
-1/22).
Consequently, (0,5) minimizes ((7; v)) over [0, v0] x [0, 2)) i.e. v = and 7/3 0.
Step 2: If Po o(c). then, by A119 ((;; w/1 is decreasing in y when y Yo, showing that the optimal value in A21 is
Me = 7o. with T(b)) T((1 v2))
(A22)
KP
and thus,
s (171)011) (PI + e(e)) + (P% ((e)) for any 1 E 1/2).
Consequently, the derivative of ((7;; v1) with respect to 4/1 is
= (PI (() (Po e(e)) +1))
leading o6 (1h, ~ = ((---te)))(0-----0--- (1 + 2e(c) - T T ( Solving
and s (7 (11) 10/222
s i (b))) = and 9 (7 th1 w1))
for Po leads to solutions
T'(0) T'(1) + TT and p A e(()) 2. p( A e(e)
respectively.
Next, we identify शे and Thr by examining Po relative to (()) and (22) in combination with the convexity or concavity of function T by the following two steps.
Step 2.1: Assume T is concave. Then by twice differentiability Tf (11) S 0 for t/1 [0. 1]. leading to (1( < (0) 0, and hence p(1)) < p((). Additionally, S", i = (Pr
e(e)) (vh) + (Po - (( +i) < O. and thus, d',, (16, 1b) is non-increasing in th for 4/ E []
If e(e) < Po < Pd1 then a'c, (1 ;1) S for wi E 10, }. and thus, s(7 ;v)) is non- increasing in 4/1 for 인1 [0, 2]. Therefore, infos 0 v1)) = 9(77/2 21) T()). Thus, wi 1/2 and v 0 by A22
24

---

If Po 2 p)²), then den (1g, v1)) 2 0, showing that ( 1/1 g(%6 0) = (Pi + e(c)) + (Po
1/1) ) is non-decreasing in 1/1 for
1/2 E [0.2]. Therefore, infoswisi ///2 g 8 2/11
e(e)) Thus, vi= 0 and Mog T(0)- by A22 12
If p( < Po < p then d/ (12, ; :111) ) is non-increasing in t/2 for 1/1 E [0, 2
11 with
Sy, (16, 111) )1))) 0 and oe, (7), 1 2/1)) 2)) < O. Therefore, Se, (10, v1) = 0 has unique solution on [0, 1),, denoted v/.. and furthermore, 0 i 1/1) is increasing in t/ for 1/ E [0, f/ and decreasing on [v 2). Therefore, the infimum of 9 (7 : 1/1) on th1 E [0, } is taken at 11 or 1 = 1/2 If 1/g 5) S g(6: 0), i.e., Po e(e)+ 7(0)-
-
the optimal value for 1/1 in Case 1 is v/ with Y6: O: otherwise, the optimal value is
11 0 with 35 7(0) (()) by A22)..
KP
Summarizing the discussion in Step 2.1, we obtain that when t/1 E [0, 1 and T is concave,
T(127(12) (i) if Po > e(c) + 710)-7 (vf n3 ) in A18 is given by 사t = 0 and n0t = I(0)-7(1) yielding g(18,; v1) - (Pi + ele)) (Po (()))(
KP
(ii) otherwise, 7 = 2 and J5 0, yielding -1)=;
Step 2.2: Assume T is convex. Then by twice differentiability of T, (1bb) 2 0 for 4/1 E [0. 1].
leading to (0)0)= - (1) 0, and hence p/²) S pp" Additionally, &", (1 ;11))))) = (P)
e(c))T" (1)) + (Po e(c))T vi) 2 O, and thus, d (1%, non-decreaingg in 1 for 4/1 E (0
Pf 2 (( then dh, 11) 2 0 for 1/ [0, 1 and thus, ((*,, w is non-decreasing in 1h for 4h1 E [o, 1)- Therefore, inf infogvis1/2 ( th1) = =(16: 0) = (P1 + (()))
(Po - (L).) Thus, o9 = and Yo; T(1)-T(1)
RP by A22)
If e(e) S Po S P8²) then 8'c, w S 0 for vh E [0, }. and thus, a(7 v/) ) is non- increasing in 1/1 for 1/ [0, J. Therefore, inf infogeist ((7,, = /0/1 =2) = T()). ;/)
Thus, v/ = and Pi 00hh by A22b.
If 2 < Po < (( then s',, (1 v1) is non-deereasing in en for Us E [0, z with dy (1 ;0)) 21=0 < 0 and 2yy, (7 11) w. > 0. Therefore, de (1 i vi) = o
has a unique solution on [0, 31. denoted v,. and furthermore, g(7;;; 1h1) is decreasing in th for th E vf] and increasing on [w], 1/2]. Then, the infimum of go, v9))
2/1 [0. 31 is taken at 4/2 2/f, that is, infoswis1/2 901p s/1) ((700; v9)
(Pi + e(e)) + (Po e(e)) vf). Thus, of = vif with 76g T(a))-Ta-v))
KI
by A22
Case 2: 1/2 E [ 1).
In this case, we set J2 A 1 - 22 yielding J2 E [0, 31. and the objective function 9(%; 4/2) defined in (177) can be written as
g(Y: th2) =yc" + Po max T - 422), ((22) }m²} + P1 max [T(1 1/22 - ykk" ((b2))
=76" + P1 max (1)))))),) T (w²)
>x*) Po max (Tx( v/22) 7KR, (v))))
Hence, the derivation in Case 1 for any 4h1 in [0, 5. can be applied to 12 by modifying the derivations based the range of Po to be that for PI, as outlined below.
Step 1: If P1 < e(e), then following the results for uf and T6 in Case with only e Pt. and Po there replaced by Viz. Po. and Pt, respectively, we obtain that 4/. = 1/2 and - 0. Hence, 15 is taken as 1 12 1/4 and 7/2 O. yielding ((7igg v/5) :/5) = =(00; $ T()).
25

---

T(w))-(1->))
Step 2: If P1 2 e(c), then, by A22 Vog is set as
RP
T( T(-05)-T(03)
R²
Step 2.1: Assume T is concave. We can directly derive the following result from the summary in Step 2.1 of Case 1.
1 - P S o(c) + 7(1)21 then V2 2 and V0g = 0. Hence, 2/ = 2/2 2 T(1)-T(1)
and g(0gg: 155) g0( =T(2).
If Pi > ((E) 7(0) T(1) then 2/2 0 and M5z T(0)-((1) Hence, 1/2
T(0)-((1/2
1 1- Ø2 1, and (7 152 g T(o) - 1) (Po+ele (()) (1))
Step 2.2: Assume convex. From the results on oaj and Toy in Step 2.2 of Case we
obtain the following conclusion.
Pi 2 e(c) (())++((0) then 22 0 and To: -(U) Hence, 2/. = 1-122
('())
N" =(c))T(0) + (Pi -(())T(
and g(1ūg: (5) g( (T)) 1) (Po
- If e(e) S S e(<) + 3.2 then 12 = 1 and 700 = O. Hence, 25g = =1 -1 -5- 2/2 and
g(70g : 155) = g(: 1)) = T
- If e(c) + < < e(c) +
T O0 then 22 = 2 and 133 T( 1
R²
where V12 is the unique solution to (Po + (' - (PI - e(t)) -1/2)
on [0, $1. Hence, 22 2/2 and Y/3 7(1 7(1-8)) T(V)) where 32
1/2 is the
unique solution to - (Po + (1 1/2 + (P (T) (1)) = 0 on [ 1]. Then
o(1 155) (Po + e( (5) + (PI {( (8))
In summary, we present the derived results in Tables and 4 for the scenarios where T is concave and convex, respectively.
robust risk ;(7 v5)
Case
e(c)
T10)
7101-707
Vi
70g
(1) e(c)) (Po ((c))T(1)
Po e(e)
T10) T11/2)
71)
7/
T(3)
Case
e(c)
T10- T(77))
T(0)-7(1)
7,g
(Nu e(c)) (P: e(c))((1)
Pi < o(t)
T10) T(/22
T(²)
T(0) 7
Table 3: Summarized results in two cases when T is concave.
V
robust risk ((Tge:05)
Case
Po 2 e(r)
(Pi + (()) + (Po o(r))((1)
Pb S e(c) +
$1
0
T(3)
e(e) + < Po < e(c) TT001T
T'(0)
vi %
T(
Tu -
(PI +(()))( (Po e(e)) +9)
Case
Pi 2 o(e) T'00-T'(
T':0)
1/g
T(o)
(Po + o(e)) + (P. - ((e))((1)
Pi 5 d(e) +
T(t)
e(r) + < < e(r)
T'( T' 3
1 V2 %61
T(D
(Pb + (w)) (A e(c))T( +8)
Table Summarized results in two cases when convex.
Finally, for any given input x, applying the preceding results to the optimal solution (17-1 x²)"
arg inf inf s(7, v) in A18). we obtain that the optimal action on the given instance is given below: for concave T.
if 2 e(e) + T(0) T(1)2((1)2)
T(0) -
1 (x)
T(0) T112),
1. 1f +
- -(1)
1/2, otherwise;
26

---

and for convex T,
T(O)
0, if Po 2 e(e) + +(()+
T())
40 if e()) +12 < Po < d() + T'(0) +T()))
(x))
T((0)
1, 2 g(t)+ + +(0)+T'(1)
T(())
4, if e(() + 1/2 < P < e(e) + +(()++((0)
1/2, otherwise,
where t is the unique solution of (Po
(P) e(E)) on E (0, }), and ef is the unique solution of (Po + e(e)) - r) = (Pi - (t()) on f E (g 1). Hence, the proof is established.
A.7 Proof of Theorem 3.2
For ease of presentation, we omit the dependence on x and y in the notation for now. Specifically, for j E [K]. we let P3 & (x y) P(Y = j|x, y) and 2b - x)(x), Let the objective function in p be denoted as
((:V) 2 7c + Σ P3 max 1/1 - ynp. ,..., 1 4/ 7np,
,........
- wい 1 - 1-+ 7xP
- Vx - -xkP
(A23)
We complete the proof in four steps. In Step 1, for each given sh, we investigate the inner optimization problem in (9) by finding the optimal value of 7, defined as 7 - arg min,20 g (7; v)). Then, in Step 2. by substituting T into g(1; ) we find that the outer optimization problem 99 can be written in linear programming format under certain transformations. Next, in Step 3, we hind the extreme points of the associated linear programming, and finally, in Step 4, we obtain the solution format of the optimal action t
Step 1: For any & V, finding the optimal value of % defined as n A arg min,20 ((7; v)). Given to and x, we sort {u),..... uh in an decreasing order, denoted w)(1) 2 2 ((()) and hence, - (1(1) s... < 1 - ()(K) Assume that ",o,),,,.,,,.. corresponds to (wh,... Φx via a permutation X. that is, v56)) = txxo for j E [K]. Correspondingly, the Py's with the associated indexes are denoted p(i) & Pxt) for j [K]. Then, for the x(h)-th element in the summation of A23 the maximum is taken between (k( ) - -nx and 1 v6(1)
First, for given vi, we examine the continuity of ((; vb) in γ by eliminating the max operators in A23 which is conducted by comparing - vi(k) - yuu and - w60) for j E [K] as follows.
If 1 (1(1) > vi(K) 7PR,, i.e., 7 2)(1)) -100 then bby 2 (62)) v)(K) yMP 2
1 b0') yIP for j.j E [K], and hence, A23 becomes
g(%; xb) ye
P5(1-
(A24)
which is continuous in y for 7 > w60) -8(8)
k2
On the other hand, if 1 - 25(1) < 1 - (k) - yKo, i.e., 0 0575 -(00)
then we express the
range of 7 as:
0, (6(1) (b(K)
(55(+11 - k)(K) 26(() 5(())
UsE[K-1]
RP
RP
RP
27

---

Then we consider y in each interval
for s [K 1]. In this case.
nP
1 - 15(0) < 1 - w((k) - -16 s 1 - pb(o+1), and (23 becomes
K 8(336) ye" + Σ pli(11 w5( - 7k²) + Σ
(1 - -566))
1=1
==
K
Σ 1=1
p()(11 (11-v((k))
Σ
p(
ا(tt + 7xp e(())
Σ
p }
(A25)
-=++
==1
where the last step holds by re-arranging the arguments and using the definition of g(e) given after Consequently,
lim (-((((0)) 100((00)0p000/0000 //P)) 9(1:4)
K
pl (1- - ()(K)) + Σ (1
- -b))) + (1)(0) -b000) (500)
Σ pG1
1=1
j=s+1
5=1
K
Σ p(i) (1 ()()) + Σ
pli)( - -b6)) + (99(3) (0 ( elc)
p(1)
1=1
j=s+1
y=1
-p(o) {(1 ()() - (1 - {
K
Σ p() - (5(K)) + Σ p(i (1 - -b()) + (15(0) -00 e(())
Σ pli)
==1
j=1
=g(((((0)
w/())// /nPP:
where the last step comes from the expression A25 for 907; 1b) when wofo) -b(k)
S < 1/ 1) g(
(K))
wit) -uyl--ite ((())
Thus, g(1; ) is continuous in 7/ for
with [K 1]. Consequently,
()) is continuous in y for 0 2 will
Therefore, combining the discussion regrading A24 and A25 we obtain that given 4h, g(y; +b) is continuous in for 7 2 0.
Next, for each given sh, we examine the monotonicity of g(1; (h) in y find the y that minimizes g(75 v). To this end, we consider the following three cases by the values of e(c).
Case 1: If p(1) < e(E) Σx= p(),
then there exists an s" E (2,.... K} such that Σj pli) s e(c) S Ej=1 p(i), Then, by A25
g(134) v is decreasing in y for 7 E (0, - and increasing for y 1g(0*) -p(k) 2010)
w( - Therefore, 7/ gita -piis
and by A24). (() 4) is increasing in y for 7 2
NP
Case 2: If e(e) < p(1),
g0) -(0)) RP
then by A25
(n: +) is decreasing in y for 7 [0, Therefore, 73 w(t) (10)))))
and by (A24). increasing in 7 for
(1
gix)
7
KF
Case 3: If g(c)
2 j=1 p())
(v: 1bb is increasing in y for y E [0, _(00) 7 (11)= g(x) Therefore, 7 = 0.
then by A25
and by (244), increasing in yy for
28

---

Therefore, we conclude that
16(1)
((()
e(c) S p())
KP
36(0")
(5(())
if
Σ
p()
S e(c) S Σ
plú
with s¹ 12,.... K}}
g
=
KP
==1
j=1
K o(c) 2 p6)
if
/=1
Step 2: Linear programming format.
For each fixed permutation X. we now find the optimal v that minimizes g(7,; vb) by examining the three cases in Step 1.
In Case 3 of Step 1, g(); ; 1b) = g(0; 1/) </(K)) 2 1- 1/K. Then the corresponding optimal action is v6(1) = 16(K) = 1/K.
In Case of Step 1, for a single data point (x, by substituting 75 oolo> -g000 with 8 E
K} into A25 b, we obtain that
1
K
5--1
= Σ
púi - ((()) + Σ
pb) - (8)( + (1566") - (1 -( ( e(s)) -
Σ pl5) }
1=1
jml
8-
K-1
=(1 - =(1-
))(
Σ
p(أ + p((')) (1- - 2/(07) + pix) ((OD) +
Σ
plt) (1 - +10))1(5** <K <K-1)
5=1
j=
:' p(i) } - (1 - (667) (06))) e(()) Σ pbo}}
+ (1 - +11-b((33) f((()
Σ
/=1
K-1
Σ p(t) e(c))(1 - -110)) +
Σ
pbi - x6())) < -1-
==
{pik) + (1 (8K))) -
(A26)
To find the optimal value that minimizes g(>): 1b) in A22)) we link with linear programming problem. Specifically, for j E [K], let zj A 1 - زن and (21,..., T, Define
Σ p(i) ele) if = 5*
a₂ =
p(K) + e(c) p()
if = K
if < < K when 8² * K 1.
When S- = K - 1, only the entries for j s" = K - and j = K need to be considered. Let V(z) = j= 0z2j. Then, the optimal vb that minimizes g(>5: v) in (A26) can be derived by
solving the linear programming problem:
min V(z),
K
8.l.
21-=2)) =1,
(A27)
j=1
0 S ... S2k 1
where the constraint Σx (1 11--))))) 2,) 1 is due to Σk (1-)) Σド أنو 1 by the definitions
of and vi, and the constraint 0 5 2k reflects the definition of wi0 for j E [K]
29

---

800)
Similarly, in Case 2 of Step I, by substituting vp
into A24)) we obtain that
() 12R)3 + Σ
P3(1 - xb5))
==1
K
=e(() (1 - (b()) - {1 - ]
+ Σ
P5 - -45)
/=1
K-1
=(p(t) - e(e))( - )))
Σ
pl (1 - か + (p(k). + e(e))( - 1500),
which is a form similar to (A26) if letting s" in (A26) equal 1. Hence, its optimal minimizer can be found through linear programming problem similar to (A27). Consequently, in the next step, our discussion focuses on (A26) only.
Step 3: Extreme points.
The feasible region of A27 denoted E, can be expressed as follows:
K
E
2
23) = 1, 0S 2 S 22x $1}
j=1
K
for j E [K]]
2
(1 21) = 05 Sx 11,1 - 2, S 1,,1-2,
j=1
Σ = K 05 21 S ... S 2k < و
for j E [K]]
(A28)
where the second step holds since, for j E [K], j1 24) - - 23) S Σ (1 21) S 1 as
S 2j for t E [i]. and the last step holds by rearranging the equality Σ (1 23) 1.
We next prove that the following K feasible solutions are the only extreme points of (227
(0. 1, 1,
1
32 A
,,..,,1,11
1,
2'
2'
1
A
Zj
j
K j elements
clements
2K-1
A
1
1
1
11
K
K
K
K-1
K
T
1 K
1
1
2k A
1
1
K
K
K
K
We denote En (z,,..., }
Firstly, we prove that each data point in Eu is an extreme point of (A27p. To this end, consider any zj E E.. If there exist v E (0, 1), z' ( xxx' E E, and z" = (."'..., 2²k E E, such that 2; = uz' + (1 u)z", then z' x" = 2j, as shown below. Let zj.t, 2/, and a represent the /th element of zj, x', and z", respectively.
If = j + 1 ..... K: then by uzt + (1 - v) =j,t Zi,t = 1, and 2/6 2/" S 1, we have that o 2 24,0 1:
30

---

If f j: then vzj + (1 v22y = 2/j = 1- - j. and 2/. 2 by A288). Thus, we
obtain that o/ 2 2j.j
If = 1.....J . - 1: then य S و - 3.²²" 2 S 2/ = =1- and Vz + (1 - v) Zje
J. 5. Thus, we can also obtain that =/ = z 2j,
Therefore, z' z" = kj. and hence, 2, is an extreme point of (27 by Definition A.1
Next, for any point z & (Z1,..., _ E E we prove that z is not an extreme point of (A27 by construction. Specifically, we have the following claims for Z.
Claim 1: & > 1 7 for t E [K]:
This claim can be proved by contradiction. Assume there exists to E [K] such that
J. Since tto < 1 1. As 2 E E. by (A28) and the assumption, we have Eto = to
Ag
7 c Eg. one of the following statements must hold: (1) there exists j < to such that
2/ 1 1; (2) there exists > to such that Zz < 1 for some j > to- Therefore,
Σ 3
E
Zj=to+1 3j < Dj=12 Eoo Ez=to+ -10 Eto + (K- (0)
K
K- since ž ... .K and S 1 for E [K] by (A28). where the strict inequality
arises from the fact that either statement (1) or (2) holds. This conclusion contradicts the condition that
E by (A28).
Claim 2: There exists E [K] such that ž, 2, 1:
This claim can be proved by contradiction:
On one hand, if there exists t' E [K] such that 2p-1 < 2r, then we must have & -1 for t < t' 2'-1; otherwise, by letting t" arg max(t: 2, < 2r- tta.ttt--11 we obtain that Σ,t' < 21 = Ey < and hence, I can be set as 1" ("+1. 1, which contradicts the assumption. Additionally, we have Σ, = 1 for / 2 L'; otherwise, Ep-1 < Eo < 1 and ( can be set as /', which contradicts the assumption. Summarizing the discussion for t' and & 2 t', we have E On the other hand, if ž
for all t [K], then Ž ZK E Eg-
In both cases, Ž E E.. contradicting the fact that ž Eg. Hence, Claim 2 holds.
Let l2 A max(t E [K] &/ < 1}. Then, 12 2 41. Let
A min 11
1
-1
-t -1
1 } for 1 Sh - -1} and
2
Ft - (1 t/ ) m for 4 S S15 12).
02 min
2
By Claims 1 and 2, we have that e1 and C2 O. Let e min((t) 1)01, (t2 - t1 + 1)e2h.
T A (/11 - 1), and 02 - 7/(1z - 11 + 1). Then we construct two points E:
- (ā ē ,,.... -1 ह₁ -o 02. 2, 22. Σk) and
z" P (21 δ1 -1 11 2,, + 02 2t1 + +0,
kk)
Therefore, ž = 1/ + 2z", and hence, 2 is not an extreme point of A27
Step 4: Solution format and optimal action.
By Steps 2 and 3, we obtain that for each fixed X and s*, the extreme points of the linear programming problem are given in Eg. By Lemma [ every linear program has an extreme point that is an optimal solution. Hence, by the format of the K extreme points in Eg. we obtain that at least one optimal action of vp can be found in the format:
1
for j jisk" k" and كا(ي) = for j 2 k
(A29)
k.
for some k: E [K].
If A- = by A23 we have that g(>; v) = 7eP Σj P3 (1 1)), and hence, the robust risk
is g K by taking 76 0.
31

---

If k2 < K, we obtain that
k
K
8(% =7e" +
p6) max (1 (1- 7kP,
-
+
pb),
kz
j=k++1
R² Σ plo)]
1 + mMP {e(e))
1
s. if0 S 5
k
5=1
yel + 1
p(), if Z
1
k 3=1
Hence, for h* < K, the robust risk is the minimum of g(>;: x)) = by taking T = and ((7;:4) = 1+ 1- (e(c) EØ= p(i) j by taking Y = A Additionally, we observe that we should take the highest k" values of {PI, :......: pk] as p(1) p(k*) to minimize g(755 v)). Hence, we take the permutation X such that p(1) 2... 2 p(K). In summary, the optimal action v5" that minimizes s(1;i1)) is given as below.
If 1- ΣØ= p(i) s. e(c) for all k* [K 1]. then e/ for j [K].
If there exists some ko [K- 11.
1 No Σド= p6) _ t and No Σ p6)
1 o(c) 2 1- Σラ= p(j) e(c) for all k E [K 1), then e ko kg
for j E [Ro] and
(b(()) = 0 for j = ko + K.
In particular, if (() 2 max ,े + e(c), p(2) + } then the optimal action is given as: v+(11) = 1 and (5) = 0 for j = 2.... K. Thus, the proof is complete.
A.8 Proof of Theorem
For ease of presentation, we omit the dependence on x, and ý, in the notation for now. Specifically, for
i [K] and j E [K], let Pt, A Pj (x,, V.) & P(Y j|x,, F.) and tha. P (xx)), For given x;, we
sort the K elements of (xx)), (wi,,...., ,.....,,,,, }. in a decreasing order, denoted w!!" .... 2 (K)
We first consider the difference between the Wasserstein robust loss I0 and the nominal loss 11
R. 9
K Pas max (T(i),1) - ((bLo)) - "
= inf 720
hee +
T(Wig-1) - T(Ws,)) - - OO
1=1
T( T(bis)) - ((bkk)))(((())
T(bik) - T(bis) - -nnp]]
K
= inf [TcO
P.j max (T(((K)) -T(ws)) - - ,0]]
+
720
1=1 j=1
A inf f(()), 720
where the second equality is due to the fact that (:(2 2 ... 2 (1) and that T is decreasing.
By definition, {at.s A T())())) T(be)) i E [m],j E [K]] are ordered as (1) 2... 2 (nk)) p(1).... and correspondingly, the Pa.y' 's with the associated indexes denoted P(1) ...... p(nK), Conse- quently, we obtain that
((7)) = ycp + 1 nk
plo (a pxP) > 7nP).
(A30)
32

---

Define a q(nK+1) = 0. Then, (1)) in (A30)
can be expressed as
((t) yne e(()) p(t) if (1fl==11/// /k0 S < a /wP for 8 E [nK];
A(7)=
yE" y 2 all)/²²
(A31)
Since
lim (x((--1)/10)--
A(7)) -
n Σ p()) a1) + (a(l)/(((e)) (((()))_- -
1
n Σ p(0}
-|a [e(c)
- )
||a
[((c)
p(0 (1a -10(01)
p()) a |0| + (0(0))
{ (((e))
1 - p(0)
n
=A(la()\\xe))
/R by definition (A31). so we conclude that fi(?) is continuous at |/ for s E [n.]] Hence, by AA31). ft (7) is continuous for 2 0.
and f177) is right-contimuous at 7 //
By (A31). (())) is increasing in 7 on E [a( / if ø(c) - Ei p(() > 0, and
decreasing if e(c) Σ p(t) < 0. Hence, to examine the monotonicity of fi()) and find the
that minimizes f(()). we consider the following three cases by the values of e(e).
Case 1. p()) < o(e) < E p(t); then there exists s" E {2..... ,kK} such that e(e) > Eiz p(t) for < 8*, and e(e) < Eiz p(t) for 2 st Hence, by (A31), f(7) is decreasing
in y E (0, / and increasing for 7 2 al(')/ )/mP. Consequently, 76 (=()) //RP, and
inf f())) (a(((')) /1²) 720
pl (0) + la ({ e(t) - 1 Σ pl0]
t=1
p( (0 0
1
/a/o")/
11
Here the last step holds because by the definition of s", 0 < e(e) - a Ei'1 p(() < 1 P())
1 - p(t) = p(*)) < n where the last inequality holds since p(5)) E 10.
Case 2. If o(c) < 1 p(): then, by A31 (())) is decreasing in y for y E [0, (1) [x/pp and increasing /R²". for 7 2 (1////' Therefore, 7 a (1) /kR,, and
inf (()) = fi (((l)/R²)) = el.))a"")
720
Case If e(c) 2 1 n p(0) N/ = 0 = (nk /R², and
then, by A311. f((7) is increasing in y for y 2 0. Therefore,
1 nk
inf (()) = (() 200
Σ p (1.
Hence, summarizing the discussion in the three cases above, we have that 73 a(6")//e) and the robust risk (TO) is expressed as
p(O) 10 > 1) - (15))
R.
33

---

where, to provide a unified expression, we define s¹ s" and s* nk + 1 in Case 2 and Case 3, respectively. Thus, the proof is completed.
B Experimental Details
B.1 Implementation Details
Datasets.
We evaluate the effectiveness of the proposed AdaptCDRP on CIFAR-IO and CIFAR-I00
21 with synthetic annotations, and on four real-world datasets with human annotations: CIFAR-
ION, CIFAR-IOON [22]. LabelMe [23 24], and Animal-ION [25]. CIFAR-IO has 10 classes of 32 32 3 color images, with 50,000 training images and 10,000 test images; CIFAR-ION provides three independent human annotated noisy labels per instance, with a majority vote yielding a 9.03% noise rate. CIFAR-100, with the same number and size of training and test images as CIFAR- 10, features 100 fine-grained classes; for each instance in CIFAR- 100, CIFAR-100) --ONN- provides one human annotated noisy label, with noise rate of 40.20%. LabelMe is an image classification dataset comprising 10,000 training images, 500 validation images, and 1, 1,188 18 test images. The training set includes noisy and incomplete labels provided by 59 annotators, with each image being labeled an average of 2.547 times. The Animal-10N dataset contains 10 classes of 64 x 64 x 3 color animal images; it includes pairs of similar-looking animals, where each pair consists of two animals that are visually alike. The training dataset contains 50,000 images and the test dataset contains 5,000 images. The noise rate (mislabeling ratio) of the dataset is about 8%. For all the datasets except LabelMe, we allocate 10% of the training data as validation data used for model selection, where we choose the model with the lowest validation accuracy during training. The test data is reserved for final evaluation of the model's performance on unseen data.
Noise generation. We generate synthetic instance-dependent label noise on the CIFAR-10 and CIFAR-100 datasets using Algorihtm [29]. Each annotator classified as an IDN-r annotator if their mislabeling ratio is upper bounded by т. We simulate R annotators independently, with R taking values from the set {5. 10, 30, 50, 100). For each instance, one annotation randomly selected from those provided by the R annotators' contributions, which evaluates methods under incomplete annotator labeling conditions. Additionally, for each R, we consider three groups of annotators with varying expertise levels, characterized by average mislabeling ratios of approximately 20%, 35%, and 50%. These groups are referred to IDN-LOW, IDN-MID, and IDN- IDN-HIGH, indicating low, medium, and high error rates, respectively. We manually corrupt the datasets according to the following annotator groups:
R=5:
IDN-LOW. IDN-10% annotators, 2 IDN-20% annotators, / IDN-30% annotator; IDN-MID. IDN-309 annotators, 2 IDN-40% annotators. 1 IDN-50% annotator; IDN-HIGH. 2 IDN-50% annotators, 2 IDN-60% annotators, IDN-70% annotator;
R=10:
IDN-LOW. 4 IDN-10% annotators, 4 IDN-20% annotators, 2 IDN-30% annotators:
IDN-MID. 4 IDN-30% annotators, 4 IDN-40% annotators, 2 IDN-50% annotators;
IDN-HIGH. 4 IDN-50% annotators, 4 IDN-60% annotators, 2 IDN-70% annotators;
R=30:
IDN-LOW. 11 IDN-10% annotators. 11 IDN-20% annotators, 8 IDN-30% annotators;
IDN-MID. IDN-30% annotators, 11 IDN-40% annotators, IDN-50% annotators; IDN-HIGH. 11 IDN-50% annotators, 11 IDN-60% annotators, 8 IDN-70% annotators;
R=50:
IDN-LOW. 18 IDN-10% annotators, 18 IDN-20% annotators, 14 IDN-30% annotators;
IDN-MID. 18 JDN-30% annotators, 18 IDN-40% annotators. 14 IDN-50% annotators;
IDN-HIGH. 18 IDN-50% annotators, 18 IDN-60% annotutors, 14 IDN-70% annotators;
R=100:
IDN-LOW. 35 10% annotators, 35 IDN-20% annotators, 30 IDN-30% annotators;
34

---

IDN-MID. 35 IDN-30% annotators, 35 IDN-40% annotators. 30 IDN-50% annotators;
IDN-HIGH. 35 IDN-50% annotators, 35 IDN-60% annotators, IDN-70% annotators.
Experiment setup. We employ the ResNet-18 architecture for CIFAR-10 10 and CIFAR-ION, and the ResNet-34 34 architecture for CIFAR-100 and CIFAR- --ON datasets. Following (27). use pretrained VGG- 16 model with a 50% dropout rate as the backbonn for the LabelMe dataset. For the Animal- 1ON dataset, in line with [25] batch size of 128 maintained across all datasets. We use the Adam optimizer 43 with a weight decay of 5 x 10-4 for CIFAR-10, CIFAR-100 CIFAR- 1ON, CIFAR- 100N, and MabelMe datasets. The initial learning rate for CIFAR-10. 10, CIFAR-100, CIFAR-ION, and CIFAR-1OON is set to 10-3, with the networks trained for 120, 150, 120, and 150 epochs respectively. The first 30 epochs serve as a warm-up. For the LabelMe dataset, the model is trained for 100 epochs with an initial learning rate of 10-2 and 20-epoch warm-up. For the Animal- epochs with an initial learning rate of 10-1 and a weight decay of 10-3. The learning rate is reduced by factor of 0.1 at the 50th and 75th epochs. with the first 40 epochs designated as the warm-up stage. Training times are approximately hours on CIFAR-10 and 5.5 hours on CIFAR- --00 using an NVIDIA V100 GPU.
the VGG19-BN architecture (28 as the backbone. A
dataset, the network is trained for 100
Our method addresses learning from noisy annotations, particularly when estimated true label posteriors may be misspecified. Thus, we select baselines that either use estimated transition
Baselines.
matrices or true label posteriors (MBEM [9], CrowdLayer [27). TraceReg [2]. Max-MIG [I].
CoNAL 335 ). We also include baselines that aggregate labels differently (CE (MV), CE (EM) 77.
DoctorNet Bd CCC [66).. Since our theoretical framework applies to both single- single-annotator and multiple-annotator scenarios, we also include baselines designed for single noisy labels (LogitClip
33 particularly those employing two networks (Co-teaching [30], Co-teaching+ [31) CoDis 32
as our method similarly uses two networks that act as priors for each other. Details of the baselines are given as follows.
(I) CE (Clean): Trains the network using the standard cross-entropy loss on clean datasets;
(2) CE (MV): Trains the network using majority voting labels:
(3) CE (EM) 77: Aggregate labels using the EM algorithm;
(4) Co-teaching 30 Trains two networks and cross-trains on instances with small loss values;
(5) Co-teaching+
Combines the "Update by Disagreement" with the Co-teaching method; (6) CoDis [32] Selects possibly clean data that have high-discrepancy prediction probabilities
between two networks;
(7) LogitClip [33:
Clamps the norm of the logit vector to ensure it is upper bounded by a
constant;
(8)
DoctorNet 34
Models individual annotators and learns averaging weights by combining
them;
(9) MBEM 9 Alternates between estimating annotator quality from disagreements with the current model and updating the model by optimizing a loss function that accounts for the current estimate of worker quality;
(10) CrowdLayer (27]
Concatenates the classifier with multiple annotator-specific layers and learns the parameters simultaneously;
(11) TraceReg [12: Uses a loss function similar to CrowdLayer but adds regularization to establish identifiability of the confusion matrices and the classifier;
(12) Max-MIG :IT]
Jointly aggregates noisy crowdsourced labels and trains the classifier; Decomposes the annotation noise into common and individual confusions: Simultaneously trains two models to correct the confusion matrices learned by each other via bi-level optimization.
(13) CoNAL 35
(14) CCC 36
Among these methods, Co-teaching, Co-teaching+, CoDis, and LogitClip are strong baselines for handling single noisy labels. We adapt them to the multiple annotations setting by using majority vote labels for loss computation. The results demonstrate the effectiveness of the proposed paeudo-label generation method across various scenarios. Results for CE (Clean), CE (MV), CE (EM), DoctorNet, MBEM, CrowdLayer, Max-MIG, and CoNAL in Table are sourced from [10.. Basclines (1)-(3)
35

---

Algorithm 1: Learning from Noisy Labels via Conditional Distributionally Robust True Label Posterior with an Adaptive Lagrange multiplier (AdapiCDRP)
Input:
{xi, Vi)i= E (0, (t), ). K e > I, >
Warm up classifiers v)(t) and v6(2); Approximate noise transition probabilities (y) for j E [K] using small-loss data;
2 for epoch t = I,.., do
// Update the classifiers with pseudo-empirica empirical distribution (Theorem 3.1
Update approximated true label posteriors: (!0) (x, F) v for each instance x; do if P/ (x) max D(0) () 2 C, y ks and collect (x, V.. into Di,;: end for Update the pseudo-empirical distribution Pt. based Di.ei
(x) (x) ()) for j [K];
Update vi(() by minimizing the empirical robust risk 5
with the reference distribution P.
and the Lagrange multiplier 76-1:
10
// Update the Lagrange multiplier (Theorem 3.3
Compute ass for E [nK] and s* by Theorem 3.3
Compute the reference value for the Lagrange multiplier: Yo. = =|a(-"//nx)
12
Update the Lagrange multiplier: 7 Yo.t [e Epg c'('', (() Y)}
14 end for
Output: 1 and e/2.
implemented according to their respective algorithms, while for the remaining bascline methods, we adapted the code from the GitHub repositories provided in their original papers, with further modifications to fit our setup.
Pseudo code for the algorithm. The training process described in Section 3.3 is presented in Algorithm [
B.2 Additional Experimental Results
Performance on the CIFAR-100 dataset with varying numbers of annotators. We conduct additional experiments on the CIFAR-100 dataset, varying the number of annotators from 5 to 100, with each instance labeled only once. annotator counts, highlighting the advantages of the proposed method across various settings. As the total number of annotators increases, labeling sparsity becomes more pronounced. which may lead to a performance collapse in methods that do not account for this sparsity, especially in datasets with large number of classes, such as CIFAR-100.
the average accuracy across different
13200
D2000
M0.54
MEMM
ME0M
(a) IDN-LOW
(b) IDN-MID
(c) IDN-HIGH
Figure 3: Average test accuracy the CIFAR- 100 dataset with varying numbers of annotators. The enror bars representing standard deviations are shaded.
Performance with varying numbers of annotations per instance. To further evaluate model R 30 annotators and
performance with varying numbers of annotations per instance,
36

---

randomly select / - 3,3,5, 7.9 labels from these R annotators for each instance. The test accuracies of the proposed method and other annotation aggregation methods are shown in Table
Table 5: Average test accuracies (with associated standard errors expressed after the + signs) for learning the CIFAR-10 dataset with varying numbers of annotations (denoted I) from 30 annotators.
Ours (AdapiCDRP)
CE(MV)
CE(EM) 7
IWMV 44
TAA 45
/
88.09 58.0994.37
80.902o.8s
81.15_0.74
==3 3
68.76.0.30
83.00
83.22
83.09
82.99
IDN-
= 5
89.05
85.78
85.59
84.53 86.63
LOW
1=
89.06
87.46
87.93 0.53
87.83
85.05
1= 9
89.24
88.30
88.38_0.2.
88. 88.24
85.5520.46
= =
87.37 4.229
76.05
75.84 0.99
88.47 19.19
79. o..6
79. uu.71
79.72
79.43++0.44
IDN-
= 5
88.68
81.58=0.20
81.90=0.67
82.05
81.5610.31
MID
1= 7
88.71
83.24=0.84
82.84_0.43
83.0610.47
83.2810.22
88.8910.22 1=
84.04
83.95_0.43
81.28
83.9/10.25
=
86.62.10.45
69.65
69.85=1.45
=
88.37 190.9
74.32.20.4
74.02_1.01
75.00
74.80
IDN-
88.63.1.44
1:330
78.42_0.12
17.90
10.00
HIGH
1= 7
88.64 20.37
79. 19.
80.00
29.36
79.72+0.60
1= 9
88.7840..0
80.90.a.65
81.11=0.44
80.53
80.7440.00
Accuracy of robust pseudo-labels. To enhance the assessment of the effectiveness of the proposed robust pseudo-label generation method, we present the average accuracy of the robust pseudo-labes on the CIFAR-10 and CIFAR-100 100 datasets during the training process over 5 random trials, as shown Figure Additionally, the average accuracy of the robust pseudo-labels with varying numbers of annotators on the CIFAR-10 dataset is shown in Figure
Robust Paeedoo-Laa La--aall Accuracy
100
Robuat Peeudo- waaddd---bbblll Label Accuracy
100
06.
66
CIFAR-I0 (IDN-LOW; R-5)
CIFAR-100 (INN-LOW, R-S)
CIPAR-10 MINN R-5)
60
CIFAR-100 (IDN-MID R-5)
CEAR- (DNN HIGH: R-5)
CIIAR: (DN R-5)
Iterations
Iterations
(a) CIFAR-10
(b) CIFAR-IO 100
Figure Average accuracy of robust pseudo-labels on the CIFAR- 10 and CIFAR-100 datasets (R = 5) during the training process.
37

---

Robust Pseude-L Label Accuracy
Robust Pseuddo- Label Accuracy
66
68
CIEAR-10 LOW: R-5)
CIEAR 10 (LDN LOW; R. 19)
02
CIFAR-I0 (DN-MID,
(IDN-MID,
CIAAR-O 10 HIGEL, R-
CIBAR 10 (LDN-EEGIA R-
100
202
300
520
220
300
400
500
Iterations
Iterations
CIFAR-IO (R
(b) CR 10)
Robust Psaudo-Lan Laball Accuracy
Robust Pssudo- Leeudo-Labblleee Label Accuracy
An S400 7
68
800
CHERR-1 (DD (IDN-LOW; LOW; R-100
CHARR 10 (LDN-LOW R-500
02
CIFAR
52
CIRR-10
CIFAR-10 (IDNHHGHH, R- R-30)
CIFAR-10 (IDN-EEGHH R-50)
300
520
220
400
Iterations
Iterations
(c) CIFAR-IO (R 30)
(d) CIFAR- 50)
Robust Pssudo-1 Label Accurasy
09
M
CIEAR 10 LON-LOW, R: 100)
02
CIFAR-ID R-100)
COFAR-OO 190)
200
100
Iterations
(c) CIFAR-10 100)
Figure 5: Average accuracy of robust pscudo-labels the CIFAR- 10 dataset with varying number of annotators in the training process.
Test accuracy during the training process. To further assess the effectiveness of the proposed method, we present the average test accuracy for the CIFAR-10 10 and CIFAR- 100 datasets during the training process, as shown in Figures respectively. The results indicate that the model tends to overfit during the warm-up stage, particularly under higher noise rates. This suggests that the results in Table [ are not obtained with the optimal number of warm-up epochs. However, following the warm-up up phase, the test accuracy of our method steadily improves, outperforming baseline methods across various scenarios.
Logitly
Me-
Logh
Min
Ocrach
Creelay
Easoa
Eoocha
Edsore
(a) IDN-LOW
(b) IDN-MID
(c) IDN- HIN-
Figure Average test accuracy on learning the CIFAR-10 dataset (R 55) during the training process.
38

---

That Acturey
Collt
Sotal
14.00
C2.>
Toecher
0D
Tredey
(a) IDN-LOW
(b) IDN-MID
(c) IDN HIGH
Figure 7: Average test accuracy on learning the 100 dataset (R 5) during the training process.
Impact of the number of warm-up epochs. Following [10 46), we use 30 warm-up epochs for the CIFAR-IO and CIFAR-100 datasets in our experiments. To rigorously assess the impact of the warm-up stage, we conduct additional experiments with varying numbers of warm-up epochs (10, 20, 30, 40) on both our method and baseline approaches that also incorporate warm-up. The results, presented in Figure g illustrate how different warm-up durations affect performance.
80
90
80
80
Annurayy
75
75
70
70
IDN LOW: Ous
70
MID: Ous
IDN HIGHE Ours
IDN-LOW: MDEM
DN DN-MID MID: MBEM
IDN DIN-TE MBEM
65
IDN-LOW Coodlayee
65
IN-MID Cowdlayer
IDN-HIGH Cowwdaayrr
ION-LOW: Thacooog
ID-- TacoRog
IDN HIGHH TiacsRog
60
20
40
60
20
40
50
20
30
45
Number of warm-pp epochs
(a) CIFAR-10
65
60
80
55
55
50
Accuraty
00
45
35
IDN LOW: MDEM
IDN MDD: MDCM
IDN- MDCM
IDN-LOW CooddLaye
IN-MID Cowddaayr
IDN-HHGGH Coowdlaayer
35
30
TrazeRog
TixeoRog
HIN-HIGH TraceRog
40
40
30
45
Number of warm-up epochs
(b) CIFAR-100
Figure 8: Average test accuracies for learning the CIFAR- 10 and CIFAR-100 datasets with varying numbers of warm-up epochs. The error bars representing standard deviation are shaded.
Different transition matrix estimation methods. Our work does not focus on precise estimation of the noise transition matrix; instead, use simple frequency-counting method for noise transition estimation in our experiments. Nevertheless, our approach is versatile and can be integrated with various methods for estimating the noise transition matrix or the true label posterior. Additional experiments using advanced transition matrix estimation methods are presented in Table 0 As demonstrated, integrating these methods with AdaptCDRP significantly improves test accuracies compared to directly using the estimated noise transition matrices. Furthermore, applying advanced noise transition estimation methods enhances the performance of our method on real datasets. These results highlight the robustness and adaptability of our method.
39

---

Table 6: Average test accuracies (with associated standard errors expressed after the + signs) of learning the CIFAR- 10 and real datasets with different transition matrix estimation methods.
CIFAR-10
Real datasets
Method
IDN-LOW IDN-MID IDN-HIGH CIFAR- ION CIFAR-IOON AnimalION LabelMe
TraceReg 12
80.7220.70 77.71 1 1.36 67 67.86 02.94
20.31.0.66 17.71
83.10.0.15
TraceReg+Ours
27 86. 76 85.83+0.37
88.3840.35
52.16g1.02
83.05
83.80#0.44
GeoCrowdNet (F) 47
84.73 39 81.44
77.29
87.4910.45
47.74.1.17
81.07
84.5910.119
GeoCrowdNet (F) + Ours
88.0610.33
27.43 29
16.69
88.30
51.07 20.57
83.1 83.12.0.42
86.20
GooCrowdNet (W) 47
83.82 20.33 75. 1.110 64.64
+2.28
87.3640.24
47.49
80.19 20.33
81.63
GeoCrowdNet (W)+ Ours $7.94 00.3 87.21 20.3 83.48 1..69
87.81
#0.12
52.03
82.41 10.01 83.32
BayesianIDNT 10]
86.46+1.u 1.07 85. 0.99 82.49
87.83+a.53
51.06
81.22 +0.59
83.01+0.32
BayesianIDNT + Ours
87. 07 86, 00.07 84.38
88.31
53.18
83.80 84.09
Impact of sparse annotation. To further address the issue of annotation sparsity, we increase the total number of annotators, Rt to 200, and manually corrupt the datasets according to the following annotator groups:
R=200:
IDN-LOW. 70 IDN-10% annotators, 70 IDN-20% annotators, 60 IDN-30% annotators;
IDN-MID. 70 IDN-30% annotators, 70 IDN-40% annotators, 60 IDN-50% annotators;
IDN-HIGH. 70 IDN-50% annotators, 70 IDN-60% annotators, 60 IDN-70% annotators.
The three groups of annotators, labeled as IDN-LOW, IDN-MID, and IDN-HIGH, have average labeling error rates of approximately 26%, 34%, and 42%, respectively. In this setup, we incorporate regularization techniques specifically, GeoCrowdNet (F) and GeoCrowdNet (W) penalties [47] into method. We then compare the results against those obtained using the traditional frequency- counting approach for estimating the noise transition matrices. Table 7 presents the performance of our proposed method on the CIFAR 10 (R- 200) dataset, where different approaches are used to estimate the noise transition matrices. In addition, Figure(J displays the average accuracies of the robust pseudo-labels generated by our method during the training process. These pseudo-labels play a crucial role in constructing the pseudo-empirical distribution.
Table 7: Average test accuracies (with associated standard errors expressed after the + signs) of learning the CIFAR-I0 10 dataset (R = 200) with different transition matrix estimation methods.
Mthod
IDN-LOW IDN-MID IDN-HIGH
Ours + frequency-counting
86.01 +0.07 85.48 +0.58 85.07 0.599
Ours GeoCrowdNet (F) penalty
47
90.89 20.21 90.27
40.40 89.25....0 90.99 90.2310.27 89.4220.. 20
Ours + GeoCrowdNet (W) penalty
47
Robust Pseudo Label Accurat
100
Robust Psoudo-Labbi Acourat
100
Robust Pscutoo Labol Accurat
08
CIFAR 20 JDN LOW: 2000
CIBAR (IDN LOW; 2000
CIEAR (IDN LOW, 20200)
CIEAR (OII (IDN
MIU: R-2000
52.
CHRAI 10 (IEN MID: k-200)
CHEAR 10 JIUN MID: k-2000
CIFAR: HEGIL 200)
CHBAR (IDN HIGHL
CHEAR (IDN SIGHL 200
400
30
200
400
Iterations
Iterations
Iterations
(a) Ours+ Frequency Counting
(b) Ours + GeoCrowdNet (F)
(c) Ours + GeoCrowdNet (W)
Figure 9: Average accuracy of robust pseudo-labels on the CIFAR-10 dataset (R = 200) using
different transition matrix estimation methods during the training process.
40

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract and introduction accurately reflect our contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
We discuss the limitations of the work performed by the authors in the conclusion.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model cell-speciiiaatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
41

---

Answer: [Yes]
Justification: We provide the assumptions in the main text, and the proofs can be found in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide all the experimental details.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
42

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes)
Justification:
We upload our code and use public datasets.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttp://ggu..eeeoooouuuuumbbbbi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide all the details and the code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We provide the error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
43

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the training time on different datasets.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http::////auursss.cc/opppihhhhha
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: It's not appropriate for the scope and focus of our paper, and we don't 't see any direct negative social impacts of our paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
44

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our model doesn't have a high risk for misuse or dual-use.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite the original papers.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
45

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provide the data generation details.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do not involve human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
46


Reviews:
[{"review_id": "wWMp2XN98n", "reviewer": "Reviewer_7dsE", "summary": "This work addresses learning from noisy annotations by using conditional distributionally robust optimization (CDRO). \nTo account for variability in estimating the true label posteriors, the authors propose an approach that minimizes the maximum expected risk  with respect to a probability distribution within a distance-based ambiguity set centered around a reference distribution (the posterior distribution of the true labels).\nDeriving the dual problem, the authors are able to provide upper bounds for risk. Moreover they derive generalization bounds for the upper bound of the risk.\nAdditionally, a closed-form expression for empirical robust risk and the optimal Lagrange multiplier is provided.\nAn analytical solution for dual robust risk is found for loss functions of a particular form. Starting from the analytical solution and introducing a robust pseudo-label collection algorithm. \nExperiments are performed on CIFAR-10 and CIFAR-100 introducing on synthetic and on the real-world datasets CIFAR-10N, CIFAR-100N, LabelME, animal-10N.", "questions": "- What loss function is used in the experiments, namely what function $ \\mathcal{Tau}$ is used in the loss? \n\nsee also questions in Weaknesses.\n\nSuggestions: \nWrite in the main paper the type of network used in the experiments would facilitate the reader (ResNet-18 architecture for CIFAR-10 and CIFAR-10N, and ResNet-34 architecture for CIFAR-100 and CIFAR-100N datasets. )", "limitations": "Partially. some possible improvements are shortly discussed in the conclusions.\n\nSome limitations:\n- An overlooked limitation is the need for $P_j(x,\\tilde{y}y)$, that is the posterior  $ P(Y=j| \\mathbf{X}= \\mathbf{x}, \\mathbf{\\tilde{Y}} = \\mathbf{\\tilde{y}})$ to define the optimal action. This requires the posterior distribution, which can only be obtained after training the model for some epochs. The number of epochs necessary depends on the dataset's characteristics and how quickly the model overfits, but the sensitivity to this factor is not discussed. Also the number of samples for the $\\mathcal{D}^{*}_0$ dataset are not specified. \n\n- Another limitation that is not mentioned is the fact that the method needs to classifiers.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The proposed approach is really interesting, novel and principled, with a sound theoretical foundation.\n2) The paper is clearly written, making the concepts and methodology understandable.\n3) The authors provide a generalization bound for the upper bound of the risk function they define.", "weaknesses": "1) Some results in the experiments are not fully convincing me, I would like to hear the authors feedback:\n- Regarding Figure 1. How can the accuracy change so little with an increasing number of annotators? According to Figure 1 in [7], the noise rate of aggregated labels decreases significantly as the number of annotators increases, even for high initial noise rates. How is it possible that the accuracy in Figure 1 remains almost constant despite the increase in annotators?\n\n- Why is the performance of the ResNet34 model on the clean CIFAR-100 dataset so low? The overall performances  for CIFAR 100 and CIFA10-N seem lower than those reported in ProMix [1] (Tables 1 and 2) or SOP [3] (Tables 1 and 3). Although the noise settings differ, the model trained on clean data should exhibit higher performance on CIFAR 100.\n Similarly, the results for Co-teaching method appear inconsistent with those in other studies. \n\n2) I believe a better justification for the chosen baselines is needed. For example, since Co-teaching, using two networks and which is designed for scenarios with a single label per sample is included, why not include more SOTA methods such as ProMix [1], Divide-Mix [2], and SOP [3]? \nI am also curious why these methods were not included. Additionally, for methods that aggregate labels, considering other approaches like IWMV [4], or those that train models on soft labels, such as IAA [5] and soft-labels average [6], would be beneficial.\nWhile not asking the authors to include all these methods, I would appreciate a clearer justification for the choice of baselines.\n\n3) In my opinion, the limitations are not fully discussed. Please see the Limitations section for further details.\n\n[1] Wang, Haobo, et al. \"Promix: Combating label noise via maximizing clean sample utility.\" arXiv preprint arXiv:2207.10276 (2022).\n[2] Li, Junnan, Richard Socher, and Steven CH Hoi. \"Dividemix: Learning with noisy labels as semi-supervised learning.\" arXiv preprint arXiv:2002.07394 (2020).\n[3] Liu, Sheng, et al. \"Robust training under label noise by over-parameterization.\" International Conference on Machine Learning. PMLR, 2022.\n[4] Li, Hongwei, and Bin Yu. \"Error rate bounds and iterative weighted majority voting for crowdsourcing.\" arXiv preprint arXiv:1411.4086 (2014).\n[5] Bucarelli, M. S., Cassano, L., Siciliano, F., Mantrach, A., & Silvestri, F. (2023). Leveraging inter-rater agreement for classification in the presence of noisy labels. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 3439-3448).\n[6] Collins, Katherine M., Umang Bhatt, and Adrian Weller. \"Eliciting and learning with soft labels from every annotator.\" Proceedings of the AAAI conference on human computation and crowdsourcing. Vol. 10. 2022.\n[7] Wei, Jiaheng, et al. \"To aggregate or not? learning with separate noisy labels.\" Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our manuscript. We appreciate your thoughtful comments and suggestions. We will carefully incorporate the necessary revisions to address your feedback in the new version of the manuscript. Below, we highlight our responses to each of your comments.\n### 1. About the feedback on initial experiment results\n* About accuracy with an increasing number of annotators.\n  * While we generate $R=5, 10, 30, 50, 100$ annotators, we **randomly select only one annotation per instance** for the training dataset to assess the algorithms in a partial labeling setting with sparse annotations. In contrast, Figure 1 in [7] shows the noise rates of the aggregated labels when **all the $R$ labels** are provided.\n  * To further evaluate model performance with varying numbers of annotations per instance, we use $R = 30$ annotators and randomly select $l = 1, 3, 5, 7, 9$ labels from these $R$ annotators for each instance. The noise rates of the majority vote labels are provided below. The test accuracies of the proposed method and other annotation aggregation methods are shown in **Table 1** of the attached PDF.\n\n|  | $l=1$ | $l=3$ | $l=5$  | $l=7$  | $l=9$  \n :---- | :---- | :---- | :---- | :---- | :---- \n CIFAR10: IDN-LOW | 0.20 | 0.09 | 0.04 | 0.02 | 0.01 \nCIFAR10: IDN-MID | 0.38 | 0.26 | 0.16 | 0.10 | 0.07 \nCIFAR10: IDN-HIGH | 0.51 | 0.42 | 0.31 | 0.25 | 0.20\n\n* Performances of some baselines.\n  * We followed the experimental settings used in [A-B], which differ from those in ProMix or SOP. Specifically, all models in our paper are trained on CIFAR100 for 150 epochs with a batch size of 128. In contrast, according to their source code, ProMix is trained on CIFAR100 for 600 epochs with a batch size of 256, and SOP is trained for 300 epochs. Additionally, ProMix and SOP employ further data augmentations, such as AutoAugment [C] and mixup augmentation [D], which we did not use in our setting.\n  * The discrepancy in the results for the Co-teaching method compared to other studies is due to differences in the noisy label generation method used in our paper. Specifically, for each instance, we generate $R$ instance-dependent annotators and randomly select one noisy annotation from these $R$ annotations.\n### 2. Justification for the chosen baselines\n* Our method addresses learning from noisy annotations, especially with potential misspecifications in estimated true label posteriors. We select baselines that either directly use estimated transition matrices or true label posteriors (MBEM, CrowdLayer, TraceReg, Max-MIG, CoNAL). We also consider baselines that aggregate labels in various ways (CE (MV), CE (EM), DoctorNet, CCC). Since our theoretical framework applies to both single-annotator and multiple-annotator scenarios, we include baselines designed for single noisy labels (LogitClip), especially methods that use two networks (Co-teaching, Co-teaching+, CoDis), given that our method utilizes two networks to serve as priors for each other. \n* The results for the proposed method and the baselines were obtained using simple data augmentations. As a result, we did not include baselines such as ProMix [1], Divide-Mix [2], and SOP [3], which use additional data augmentations. However, our method is compatible with these augmentations and can be adapted to incorporate them. We have now applied mixup augmentation to our method and some other baselines, with results shown in **Table 3** of the attached PDF. For a fair comparison, all results in Table 3 are based on training ResNet18 for 120 epochs, except for ProMix, which was trained for 300 epochs. This is fewer epochs than those used in the original papers for DivideMix and ProMix.\n* Methods that aggregate labels.\n   * We have selected several baselines that utilize aggregated labels, including majority voting (“CE (MV)”), the EM algorithm (“CE (EM)”), MBEM, CoNAL, DoctorNet, and Max-MIG.\n   * The algorithms proposed in IWMV [4], IAA [5], and soft-labels average [6] require multiple annotations per instance to estimate labels or the agreement matrix, which makes them unsuitable for sparse labeling scenarios. Additionally, IAA [5] assumes a common transition matrix for all annotators, which differs from the noisy annotation generation process described in our paper.\n   * To compare with these label aggregation methods, we have now conducted additional experiments by randomly selecting $l=3,5,7,9$ annotations for each instance from the $R=30$ annotators. The results are displayed in **Table 1** of the attached PDF.\n### 3. Question about the loss function\n* We use cross-entropy loss for the loss function $\\ell$, meaning that $\\mathcal{T}$ is the log function, which is concave in its argument. To meet the required conditions on $\\mathcal{T}(\\psi(x))$, we clip the predicted probabilities $\\psi(x)$ to the range $[0.01, 1 - 0.01]$ to ensure that $\\mathcal{T}(\\psi(x))$ remains bounded.\n* Thank you for your suggestion. We will include details about the type of network used in the experiments in the main paper when we prepare the revision.\n### 4. About limitations\n* Thank you for raising this point. We use 30 warmup epochs in our experiments, as adopted from existing works [E]. The learning dynamics of the algorithms are shown in **Figure 1** of the attached PDF. It can be observed that the model already overfits label noise with 30 epochs. To assess the sensitivity to warm-up epochs, we have now conducted experiments with varying warm-up epochs on our method and the baselines that also employ a warm-up stage, as shown in **Figure 2** of the attached PDF. The results indicate that performance can be further improved with an appropriate number of warm-up epochs.\n* The number of samples in $\\mathcal{D}^*_0$ is not predetermined. After the warm-up stage, we include an instance in $\\mathcal{D}^*_0$ if its predicted probability exceeds 0.5.\n* Thank you for pointing this out. We will address this limitation in our paper when preparing the revision.", "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": "bWh9BtX6rq", "reviewer": "Reviewer_xLiU", "summary": "This paper studied the issue of potential misspecification of estimated true label posterior in learning from noisy labels. To alleviate the impact of this issue,  it formulated learning from crowds as a conditional distributionally robust optimization problem, where a robust pseudo-empirical distribution is used as a reference probability distribution. Experiments on multiple crowdsourcing datasets verified the effectiveness of the proposed method.", "questions": "1. What {(·, ·)}^p means in Line 133?\n2. There is a little abuse of notations.  ψ means the classifier in Line 88, while it represents the predicted probabilities in Line 190.\n3. How to address the annotation sparse problem when approximating noise transition probabilities?", "limitations": "See above.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The proposed methodology has a solid theoretical foundation.\n2. The writing is very clear and easy to understand.\n3. The performance of the proposed method is very promising in the experiments.", "weaknesses": "1. The focused problem, i.e., the potential misspecification of estimated true label posterior, has not been defined and measured. And it is not very clear to what extent the proposed method has solved the impact of this problem.\n2. The contribution of this work is about \"learning from noisy labels\", while the context of this work seems limited to \"learning from crowds\". They are not consistent, since \"learning from noisy labels\" also includes the case with one annotator. However, this work didn't discuss and test on the case with one annotator.\n3. Although the way to construct a robust pseudo-empirical distribution has a theoretical motivation, it seems similar to the pseudo-labeling methods [1,2] in learning with noisy labels. What are the differences and advantages of the proposed way and the pseudo-labeling methods?\n4. As we know, in learning with noisy labels or learning from crowds, the estimation of noise transition probabilities is very important, while the way to approximate noise transition probabilities in this work is heuristics. Why not use those thoroughly studied methods, e.g.,  [3,4,5], or more advanced instance-dependent transition matrix estimation methods [6,7]？\n\n[1] Joint optimization framework for learning with noisy labels. CVPR 2018\n\n[2] Deep Self-Learning From Noisy Labels. ICCV 2019\n\n[3] Deep learning from crowdsourced labels: Coupled cross-entropy minimization, identifiability, and regularization. ICLR 2023\n\n[4] Learning from noisy labels by regularized estimation of annotator confusion. CVPR 2019\n\n[5] Deep learning from crowds. AAAI 2018\n\n[6] Label correction of crowdsourced noisy annotations with an instance-dependent noise transition model. NeurIPS 2023\n\n[7] Transferring annotator- and instance-dependent transition matrix for learning from crowds. TPAMI 2024", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our manuscript. We appreciate your thoughtful comments and suggestions. We will carefully incorporate the necessary revisions to address your feedback in the new version of the manuscript. Below, we highlight our responses to each of your comments.\n\n\n### 1. About the focused problem of our paper\n\n* In the problem of learning with noisy labels, many existing approaches use various algorithms to estimate the true label posterior $P^*\\_{y|x,\\tilde{x}}$, typically with a model denoted as $P_{y|x,\\tilde{y}}$. However, the estimated posterior can deviate from the true underlying distribution, a phenomenon known as model misspecification [H].\n\n* By Bayes’s theorem, the true label posterior is proportional to the noise transition probability $P^*_{\\tilde{y}|x, y}$. Existing works [F-G] demonstrate that the estimated noise transition matrix asymptotically converges to the true $P^*_{\\tilde{y}|x, y}$ under certain conditions. According to the Vitali convergence theorem [I], the associated $L_1$ Wasserstein distance converges to zero in this situation. Therefore, we consider a Wasserstein ball $\\Gamma_\\epsilon(P_{y|x,\\tilde{y}})$ centered around the estimated true label posterior (referred to as the \"reference probability distribution\"), as defined in Equation (2) in our paper. In this context, the Wasserstein distance is used to measure the misspecification of estimated true label posterior. When the sample size $n$ is sufficiently large, the true distribution $P^*_{\\tilde{y}|x, y}$ will lie within $\\Gamma_\\epsilon(P_{y|x,\\tilde{y}})$. Thus, by minimizing the worst-case risk over $\\Gamma_\\epsilon(P_{y|x,\\tilde{y}})$, we can effectively minimize an upper bound on the risk based on the true label posterior.\n\n* Note that our work does not aim to precisely estimate the noise transition matrix or alleviate the misspecification of estimated true label posteriors. Instead, we focus on **robustly training a classifier despite misspecification** by considering the worst-case risk within a Wasserstein ball. Therefore, our work complements existing methods that rely directly on the estimated true label posterior, and thus, providing a robust alternative that accounts for potential inaccuracies, as shown in **Table 4** of the attached PDF.\n\n### 2. Learning from noisy labels v.s. Learning from crowds\n\n* Thank you for highlighting this issue. The theoretical framework presented in our paper is applicable to both single-annotator ($R=1$) and multiple-annotator ($R>1$) scenarios. In our experiments, we generate a total of $R$ annotators and then randomly select one annotation per instance from these $R$ annotators. This approach underscores that our focus is on \"learning from noisy labels\" instead of \"learning from crowds\" as the latter implies a specific emphasis on aggregating multiple annotations per instance.\n\n* To thoroughly evaluate the scenario with a single annotator, we have now set $R=1$ and conducted additional experiments on both the CIFAR10 and CIFAR100 datasets. The results of these experiments are detailed in **Table 2** of the attached PDF. We will incorporate these results into our paper to address this scenario comprehensively in the forthcoming revision.\n\n### 3. About the pseudo-empirical distribution\n\n* The pseudo-labeling methods discussed in [1-2] rely solely on the highest predicted probability for each instance, assigning the label corresponding to this highest probability as the pseudo label. In contrast, our approach considers both the highest and the second-highest predicted probabilities. We assign a pseudo label only if the ratio of these probabilities exceeds a specified threshold. This strategy ensures that pseudo labels are assigned only to instances with high confidence, effectively filtering out uncertain data. The accuracies of the pseudo labels throughout the training process are detailed in Figures 3-4 in Appendix B.2 of our paper, which demonstrates the effectiveness of our robust approach.\n  \n### 4. About estimation of noise transition probabilities\n\n* Our work does not focus on precisely estimating the noise transition matrix; thus, we employ a straightforward estimation method in our experiments for simplicity. However, our approach is versatile and can be integrated with various methods for estimating the noise transition matrix or the true label posterior. We have conducted additional experiments using more advanced transition matrix estimation methods, and the results are presented in **Table 4** of the attached PDF. As shown in Table 4, incorporating these advanced estimation methods significantly improves the test accuracies of our proposed approach, which highlights the robustness and adaptability of our method.\n\n### 5. Answers to the questions\n\n* Thank you for pointing out the typo. It should indeed be ${c(\\cdot,\\cdot)}^p$. We appreciate your attention to detail and will correct this error in the revised version of the paper.\n\n* Thank you for highlighting this. We will clarify this in the revision. Specifically, we use $\\psi:\\mathcal{X}\\rightarrow \\mathcal{S}^{K-1}$ to denote the predicted probabilities, where $\\mathcal{S}^{K-1}$ represents the $(K-1)$-dimensional simplex. Consequently, the classifier is defined as $\\max_{j \\in [K]} \\psi(\\mathbf{x})_j$.\n\n* In our experiments, we generate $R=5, 10, 30, 50, 100$ annotators and select a single annotation per instance for training. As demonstrated in Figure 1 of our paper, our proposed method consistently outperforms the baselines, even as annotation sparsity increases with the total number of annotators. This robust performance highlights the effectiveness of our approach in handling varying levels of annotation density.", "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": "YK2sQSZ1tQ", "reviewer": "Reviewer_62sF", "summary": "This paper studies the problem of learning from noisy labels by using conditional distributionally robust optimization (CDRO) to estimate true label posterior. The authors formulate the problem as minimizing the worst-case risk within a distance-based ambiguity set centered around a reference distribution and derive upper bounds for the worst-case risk.", "questions": "1. Can the theoretical analyses be extended to the multi-classification case?\n2. In Algorithm 1 line 1, does the procedure of \"Warm up classifiers $\\psi^{(1)}$ and $\\psi^{(2)}$\" affect the generation of pseudo-empirical distribution? What if the warm-up is not good enough for pseudo-empirical distribution?\n3. The intuition and rationale of using the CDRO framework to improve the performance of learning from noisy labels are not clear, please explain them.", "limitations": "No, the authors do not mention the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Learning from noisy labels is an important and practical topic.\n2. This paper provides rigorous theoretical analyses of the generalization bounds for the worst-case risk.\n3. The authors offer a guideline for balancing robustness and model fitting by deriving the optimal value for the Lagrangian multiplier.", "weaknesses": "1. In section 3.1, the theoretical analyses are only conducted in the case of binary classification while multi-class classification is more common in practice.\n2. In lines 192-193 and 198, the authors make assumptions about the function $\\mathcal{T}$, however, the convexity or the concavity of $\\mathcal{T}$ may be too strict.\n3. According to Table 2, the performance improvement of the proposed method is not significant across four real datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our manuscript. We appreciate your thoughtful comments and suggestions. We will carefully incorporate the necessary revisions to address your feedback in the new version of the manuscript. Below, we highlight our responses to each of your comments.\n\n\n1. Notably, building on our initial development on binary classes, we have now extended our theoretical results to the multi-class scenario. This extension provides a comprehensive understanding of our approach's applicability across different classification settings. \n\n\n    * We extend the optimal action result in Theorem 3.1 to the multi-class scenario by identifying the extreme points of the corresponding linear programming problem. \n  \n    * Theorem 3.2 from the initial submission extends naturally to the multi-class scenario using analogous proof techniques as those employed for the binary case. \n  \n    * For brevity, we have omitted the detailed multi-class results but are prepared to include the extended proofs in the revised manuscript. The specific results for Theorems 3.1 and 3.2 can be found in the **Official Comment**.\n\n\n\n2. Our theoretical results are based on the assumption that the function $\\mathcal{T}$  is convex or concave with respect to its arguments, rather than the network parameters or the input data. In the context of our experiments, we utilize the cross-entropy loss function $\\ell$. This results in $\\ell$ being the logarithmic function, which is known to be concave in its argument. Therefore, our theoretical framework is aligned with the properties of the functions used in our experiments.\n\n3. The discrepancy may arise because real datasets often have more complex noise generation processes compared to the simplified models used for noise estimation. To address this, we have employed advanced methods for estimating noise transition matrices to better reflect the intricate noise patterns observed in real data. The results using these improved transition matrix estimation techniques are detailed in **Table 4** of the attached PDF.\n\n4. Answers to the questions\n\n\n    * (i) Yes, our theoretical analyses can indeed be extended to multi-class classification scenarios, as previously discussed. In response to your feedback, we will refine the presentation in our revision to explicitly address and integrate these multi-class scenarios, which will ensure a clearer and more comprehensive treatment of the subject.\n\n    * (ii) About the warm up stage\n\n    \n      * Thank you for this thoughtful question. In Algorithm 1, the procedure of ``warming up classifiers $\\psi^{(1)}$ and $\\psi^{(2)}$\" is intended to stabilize the classifiers before they generate pseudo-empirical distributions. In our experiments, we follow established practices [E] and use 30 warm-up epochs, selecting the model with the highest validation accuracy during this phase.\n\n\n      * Our results, shown in **Figure 1** of the attached PDF, indicate that the model tends to overfit, especially under higher noise rates. This observation suggests that the results presented in our paper are not derived under the most optimal warm-up conditions, which may affect the quality of the pseudo-empirical distributions.\n\n      * To rigorously assess the impact of the warm-up stage, we have now conducted experiments with varying numbers of warm-up epochs (10, 20, 30, 40) on both our method and baseline approaches that also rely on warm-up. These results are presented in **Figure 2** of the attached PDF, demonstrating the effects of different warm-up durations on performance.\n\n      * After the warm-up phase, classifiers $\\psi^{(1)}$ and $\\psi^{(2)}$  continue to be updated using the proposed method (as outlined in Line 8 of Algorithm 1), and the pseudo-empirical distribution is constructed using these updated classifiers. This approach ensures that the classifiers are continuously refined, which helps in mitigating any initial limitations from the warm-up stage and improves the overall reliability of the pseudo-empirical distributions.\\\\\n\n    \n    *  (iii) About the intuition and rationale of using the CDRO framework \n    \n        * The CDRO  framework addresses the challenge of noisy labels by focusing on model robustness in the presence of potential misspecifications. Many existing methods estimate the true label posterior $P^*_{y|x,\\tilde{y}}$ using a model denoted $P_{y|x,\\tilde{y}}$. However, this estimated posterior can deviate from the true distribution, known as model misspecification [H].\n    \n        * By Bayes’s theorem, the true label posterior is proportional to the noise transition probability $P^*_{\\tilde{y}|x, y}$. Existing work [F-G] shows that with large sample sizes, the estimated noise transition matrix converges to the true $P^*_{\\tilde{y}|x, y}$ asymptotically, and the Wasserstein distance between them converges to zero. Therefore, we use a Wasserstein ball $\\Gamma_\\epsilon(P_{\\tilde{y}|x, y})$ centered around the estimated posterior (referred to as the ``reference probability distribution\") to measure and mitigate misspecification, as defined in Equation (2) in our paper.\n    \n        * In this context, the Wasserstein distance is employed to measure the misspecification of estimated true label posterior. When the sample size $n$ is sufficiently large, the true distribution $P^*_{\\tilde{y}|x, y}$ lies within $\\Gamma_\\epsilon(P_{y|x,\\tilde{y}})$. Thus, by minimizing the worst-case risk over $\\Gamma_\\epsilon(P_{y|x,\\tilde{y}})$, we can minimize an upper bound of the risk based on the underlying true label posterior.\n    \n        * Our approach does not aim to precisely estimate the noise transition matrix or the true posterior but instead focuses on minimizing the worst-case risk over this Wasserstein ball. This method robustly trains the classifier despite potential misspecifications, which serves as a valuable complementary approach to traditional methods that directly apply the estimated posterior.", "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:
Dear Reviewers,

Thank you for your thoughtful feedback and for the time you dedicated to evaluating our paper. We deeply appreciate your insights and constructive comments. We are pleased to hear that you recognized the  strengths and contributions of our paper, which we would like to recap as follows.

  * Our paper addresses a significant and practical topic and proposes a novel and principled CDRO framework to tackle the challenge of potential misspecifications in the estimated true label posterior (Reviewer 7dsE, 62sF).

  * We provide rigorous theoretical analyses on the upper bound for the worst-case risk and the optimal action for constructing the pseudo-empirical distribution, which serve as valuable guidelines for designing our algorithm (Reviewers 7dsE, xLiU, 62sF).

  * The proposed method demonstrates promising performance in our experiments. The results also validate the effectiveness of our approach and its practical utility (Reviewer xLiU).
 
  * We appreciate the feedback on the clarity and ease of understanding of our paper (Reviewers 7dsE, xLiU). We will carefully prepare a revised manuscript to fully address reviewers' comments and suggestions to ensure our presentation to remain accessible and clear.


We have thoroughly reviewed each of your queries, concerns, and remarks. In response, we have prepared a **one-page PDF** detailing additional experimental results, which are designed to address your points comprehensively. The references cited in our responses are listed at the end of the document. For your convenience, the following summary highlights the key updates:

  * We appreciate your valuable insights into emphasizing the intuition and rationale behind the CDRO framework (Reviewer xLiU, 62sF). In response, we have added a more comprehensive explanation of the motivation for using a Wasserstein ball-based uncertainty set $\Gamma_\epsilon(P_{\mathrm{y}|\mathbf{x},\tilde{\mathbf{y}}})$ to address potential misspecifications.

  * Your suggestions to justify the chosen baselines (Reviewer 7dsE), examine the impact of the number of warm-up epochs (Reviewers 7dsE, 62sF), and explore different estimation methods for the noise transition matrices (Reviewers xLiU, 62sF) are invaluable. When preparing a revision, well incorporate these recommendations to better highlight the strengths and robustness of our approach.

  * We have extended our theoretical results to address the multi-class case, as questioned by Reviewer 62sF. The updated theoretical insights are detailed in the **Official Comment**. When preparing the revised manuscript, we will update the presentation to cover both the binary and multi-class cases comprehensively, and include the new proofs to support these results. This enhancement will ensure a thorough understanding of our approach across different classification scenarios.

  * We appreciate your constructive feedback on improving the clarity and presentation of our paper (Reviewers 7dsE, xLiU). We have carefully considered your suggestions and will implement effective revisions in the updated manuscript to enhance its readability and effectiveness.

We believe that our responses have thoroughly addressed all the concerns raised. However, should you require any additional details, justifications, or further results, we are more than willing to provide them to ensure all aspects are comprehensively covered.

**References**


[A] Ibrahim, Shahana, Tri Nguyen, and Xiao Fu. "Deep Learning From Crowdsourced Labels: Coupled Cross-Entropy Minimization, Identifiability, and Regularization." ICLR (2023).

[B] Yang, Shuo, et al. "Estimating Instance-dependent Bayes-label Transition Matrix using a Deep Neural Network." ICML (2022).

[C] Cubuk, Ekin D., et al. "Autoaugment: Learning augmentation strategies from data." CVPR (2019).

[D] Zhang, Hongyi, et al. "mixup: Beyond Empirical Risk Minimization." ICLR (2018).

[E] Zheng, Songzhu, et al. "Error-bounded correction of noisy labels." ICML (2020).

[F] Khetan, Ashish, Zachary C. Lipton, and Animashree Anandkumar. "Learning From Noisy Singly-labeled Data." ICLR (2018).

[G] Guo, Hui, Boyu Wang, and Grace Yi. "Label correction of crowdsourced noisy annotations with an instance-dependent noise transition model." NeurIPS (2023).

[H] Grace, Y. Yi. "Statistical analysis with measurement error or misclassification" Springer (2016).

[I] Peskir, Goran. "Vitali convergence theorem for upper integrals." Proc. Funct. Anal. IV (1993)

Meta-review: This work proposes a conditional distributionally robust optimization approach to tackle the crowdsourced noisy label learning problem.

The authors and reviewers had concrete discussions in the rebuttal phase. As a result, the reviewers were satisfied with the paper, given that the additional experiments and clarifications in the rebuttal phase will be integrated into the camera-ready version.

Overall, the reviewers all agree that the topic addressed in this work has practical significance. The reviewers are also happy with the fact that the proposed method is accompanied with rigorous risk analyses. During the rebuttal, the authors made substantial efforts to address the reviewers’ major comments. Two notable points include (1) a new theoretical result on the multi-class cases and (2) substantial experiments with new baselines/regularization, e.g., using GeoCrowdNet’s regularization to enhance the proposed method. These efforts were appreciated by the reviewers.
Decision: Accept (poster)