A Holistic View of Label Noise Transition Matrix in Deep Learning and Beyond
Authors: LIN Yong
Renjie Pi
WEIZHONG ZHANG
Xiaobo Xia
Jiahui Gao
Xiao Zhou
Tongliang Liu
Bo Han
Venue: ICLR 2023 notable top 25% (2023)

Abstract: In this paper, we explore learning statistically consistent classifiers under label noise by estimating the noise transition matrix T. We first provide a holistic view of existing T-estimation methods including those with or without anchor point assumptions.  We unified them into the Minimum Geometric Envelope Operator (MGEO) framework, which tries to find the smallest T (in terms of a certain metric) that elicits a convex hull to enclose the posteriors of all the training data. Although MGEO methods show appealing theoretical properties and empirical results, we find them prone to failing when the noisy posterior estimation is imperfect, which is inevitable in practice. Specifically, we show that MGEO methods are in-consistent even with infinite samples if the noisy posterior is not estimated accurately. In view of this, we make the first effort to address this issue by proposing a novel T-estimation framework via the lens of bilevel optimization, and term it RObust Bilevel OpTimzation (ROBOT). ROBOT paves a new road beyond MGEO framework, which enjoys strong theoretical properties: identifibility, consistency and finite-sample generalization guarantees. Notably, ROBOT neither requires the perfect posterior estimation nor assumes the existence of anchor points. We further theoretically demonstrate that ROBOT is more robust in the case where MGEO methods fail. Experimentally, our framework also shows superior performance across multiple benchmarks.

Published as a conference paper at ICLR 2023
A HOLISTIC VIEW OF LABEL NOISE TRANSITION MA- TRIX IN DEEP LEARNING AND BEYOND
Yong Lin Renjie Pil
Weizhong Zhang? Xiaobo Xia
Jiahui Gao*
Xiao Zhou'
Tongliang Liu Bo Han
TTee Hong Kong University of Science and Technology Fudan University
Syydney Al Centre, The University of Sydney
"The University of Hong Kong
'Hong Kong Baptist University
ABSTRACT
In this paper, we explore learning statistically consistent classifiers under label noise by estimating the noise transition matrix (7). We first provide holistic view of existing T T-estimation methods including those with or without anchor point assumptions. We unified them into the Minimum Geometric Envelope Op- erator (MGEO) framework, which tries to find the smallest T (in terms of cer- tain metric) that elicits convex hull to enclose the posteriors of all the training data. Although MGEO methods show appealing theoretical properties and em- pirical results, we find them prone to failing when the noisy posterior estimation is imperfect, which inevitable in practice. Specifically, we show that MGEO methods are in-consistent even with infinite samples if the noisy posterior is not estimated accurately. In view of this, we make the first effort to address this is- sue by proposing novel T-estimation framework via the lens of bilevel opti- mization, and term it RObust Bilevel OpTimzzation (ROBOT). ROBOT paves a new road beyond MGEO framework, which enjoys strong theoretical properties: identifibility, consistency and sinite-sample generalization guarantees. Notably, ROBOT neither requires the perfect posterior estimation nor assumes the exis- tence of anchor points. We further theoretically demonstrate that ROBOT is more robust in the case where MGEO methods fail. Experimentally, our framework also shows superior performance across multiple benchmarks. Our code is released at https://gituub.com/pppuuuuu
INTRODUCTION
Deep learning has achieved remarkable success in recent years, owing to the availability of abundant computational resources and large scale datasets to train the models with millions of parameters. Unfortunately, the quality of datasets can not be guaranteed amount of mislabelled data in real world datasets, especially those obtained from the internet through crowd sourcing (Li et al., 2021; Xia et al., 2019; 2020; Xu et al., 2019; Wang et al., 2019; 2021; Liu et al., 2020; Collier et al., 2021; Bahri et al., 2020; Li et al., 2022a; Yong et al., 2022; Lin et al., 2022; Zhou et al., 2022b). This gives rise to the interest in performing learning under label noise.
practice. There are often a large
Our task is to learn function fo with parameter 0 to predict the clean label Y E y {1, ..., K} based the input X E X TRd. However, only observe noisy label Y which is generated from Y by (oracle) noisy transition matrix T (x: whose element (xx
P(Ý jJY
i, X x). We consider class-dependent label noise problems which assume that T is independent of x. i.e., (x) = T Given T we can obtain the clean posterior from the noise posterior by P(Y - x) P(p = æ). With the oracle T" we can learn a statistically consistent model on the noisy dataset which collides with the optimal model for the clean dataset. Specifically, denote the 8" as the minimizer of the clean loss Ex.y (éx. (X),, Y)] where é is the cross entropy loss. Then minimizing the Ex [( fo (X), Y)] also leads to 0-. Therefore, the effectiveness of such methods heavily depends on the quality of estimated T.
'Equal Contribution, correspondence to Renjie Pi (rpi appi@conncttuut.hk. Code relcased https//gittubbcom//ppiij//OOO

---

Published as a conference paper at ICLR 2023
To estimate T", earlier methods assume that there exists anchor points which belong to certain class with probability one. The noisy posterior probabilities of the anchor points are then used to construct T (Patrini et al., 2017; Liu & 2015). Specifically, they fit model on the noisy dataset and select the most confident samples as the anchor points. However, as argued in (Li et al., 2021), the violation of the anchor point assumption
lead to inaceurate estimation of T. To overcome this limitation, Li et al. (2021); Zhang et al. (2021) then try to develop anchor-free free methods that are able to estimate T without the anchor point assumption (See Appendix C for more discussion on related work).
Since P = ==))=TP(([) = x) and Ei P(Y = i|Xx = x) = 1, we know that for any x. P = =) is enclosed in the convex hull conv(TT)) formed by the columns of T". Therefore, both anchor- based and anchor-free methods try to find a T whose conv(T) encloses the noisy posteriors of all data points, under the assumption that all the noisy posteriors are perfectly estimated. To identify T from all the Ts satisfying the above condition, they choose the smallest one in terms of certain positive metrics, e.g., anchor-based methods adopts equation 2 and minimum volume (anchor-free) adopts equation 3. Therefore, we unify them into the framework of Minimum Geometric Envelope Operator (MGEO), the formal definition of which is in Section 2. Though MGEO- based methods achieve remarkable success, we show that they are sensitive to noisy posteri- ors estimation errors. Notably, neural networks can easily result in inaccurate posterior estimations due to their over-confidence (Guo et al., 30.7). If some posterior estimation errors skew the smallest convex hull that encloses all the data points, MGEO can result in an unreliable T reesiimationn returned (as illustrated in Fig. 1 (a)). We theoretically show that even if the noisy posterior is accurate except for a single data point, MGEO-bon based methods can result in a constant level error in T-estimation. We further provide supportive experimental results for our theoretical findings in Section 2.
In view of this, we aim to go beyond MGEO by proposing a novel framework for stable end-to-end T-estimation. Let ((T) be the solution of 0 to minimize y [f(T) (X), Y)] when T is fixed. Here Ö(T) explicitly shows the returned 0 depends on T. If the clean dataset is available, we can find T* by checking whether T induces a (T)) that is optimal for Ex (e(Ja(X), Y)] (this is ensured by the consistency of forward correction method under suitable conditions (Patrini al., 2017), which is discussed in Appendix A.3). Then the challenge arises, as we do not have the clean dataset in practice. Fortunately, we have the well established robust losses (denoted as (vo)), e.g., Mean Absolute Error (MAE) (Ghosh et al., 2017) and Reversed Cross Entropy (RCE) (Wang et al., 2019) whose minimizer on E x, (foos(((())) Y)] collides with that on LE y (offooo(oo (X), Y)]. Therefore, we search for T by checking whether T minimizes Ex y (looo(ffrrr) (x), F)], which only depends on the noisy data. This procedure can be naturally formulated as a bilevel problem as follows: in the inner loop, T is fixed and we obtain ((T) by training 0 to minimize E y ( fe(X), Y)]. In the outer loop, we train T to minimize E Ex (X), 8)). We named our framework as RObust Bilevel OpTiization (ROBOT).
Notably, different from MGEO, ROBOT is based sample mean estimator which is intrinsically consistent by the law of large numbers. In Section 3.2, we show the theoretical properties of ROBOT: identifiablilty, finite sample generalization and consisteney. Further, ROBOT achieves O(1/n) bustness to the noisy posterior estimation error in the case where MGEO methods lead to a constant level T T-estimation error. In Section 4, we conduct extensive experiments on both synthetic and real word datasets. Our methods beat the MGEO methods significantly both in terms of prediction accuracy and Tesstmmation accuracy.
Contribution.
We provide the first framework MGEO to unify the existing T-estimation methods includ- ing both anchor- and anchor-free methods. Through both theoretically analysis and empirical evidence, we formally identify the instability of MGEO-based methods when the noisy posteriors are not estimated perfectly, which is inevitable in practice due to the over-confidence of large neural networks.
To break through the limitation of MGEO-bar -ased methods, we propose a novel framework ROBOT to estimate T that only relies on sample mean estimators, which is consistent by the law of large numbers. ROBOT enjoys strong theoretical guarantees including identifi- bility, consistency and finite sample generalization without assuming perfect noisy posteri-
2

---

Published as a conference paper at ICLR 2023
ors the existence of anchor points. Further, when the posterior estimation is imperfect, the error of ROBOT is bounded ((1nn) while that of MGEO is in constant level.
Extensive experiments over various popular benchmarks show that ROBOT improves over MGEO-base based methods by large margin in terms of both test accuracy and T estimation error. For instance, ROBOT increases 10% accuracy and decreases 40% Tessimmation error over MGEO-based methods on CIFAR100 with uniform noisy.
2 MINIMUM GEOMETRIC ENVELOPE OPERATOR (MGEO)
Preliminaries. Throughout this paper, we use upper cased letters, i.e., X, to denote random vectors, use æ to denote deterministic scalars and vectors. For any vector v, we use v(i] or v; to denote the ith element of u. The LI norm of e is |1| = Ei = |oyl- Let T denote the oracle noise transition matrix as introduced in Section 1. Let T, and T. be the ith row and jth of T column, respectively.
Denote the feasible region of T T [T denote the unit vector where e []] samples, respectively; let D and D denote D(oo) and D(o)) for short. The risk on dataset D(n) is C(,,, D(m) == ((.))))(n) (e(fo(==).)) v)] where f is the loss function. By default, we use cross entropy as f. Denote the noisy posterior P( x) as g(x) for short. Let g(xr) denote the fitted posterior that we obtain. Let (n) denote the set of the fitted posteriors, i.c., ((n) = {g(x;)){=r
0, [T,y1 1, j [K]]. Let e' e R ((n) and D(n) denote the clean and noisy dataset with
2.1 MGEO AND ITS LIMITATION
In this section, we first unify the existing works of T-sstimation by MGEO. Denote the convex hull induced by the columns T as cTnv(T) = {E]e = Σ act,, >i a; = 1, 0; > 0}, where T = [t]. Notably, conv(T) is the feasible region of ī(x) generated by T because g(æ) = P(Y
x) TP(Y æ) and |P x)}1 1. Existing methods assume that we can fit the posteriors perfectly, i.e., g(x) = O(x) for all x. They then try to find a T whose conv(T) encloses ((n) (Patrini et al., 2017; Zhang al., 2021; Xia et al., 2020; Li et al., 2021; Zhang et al., 2021; Liu & Tao, 2015). Since there are infinitely many T satisfying this conditions, they chose the smallest one in terms of certain positive metries. We name them as the Minimum Geometric Envelope Operator (MGEO) and present the unified definition of them as follows:
Definition 1 (Minimum Geometric Envelope Operator). An operator Q BK xn + T on a set (n) = {g(x,)) is said to be Minimum Geometric Envelope Operator (MGEO) if it solves
TIMGEO arg min M(T), s.t. (() C &conv(T) (T), TET
where T = [t...tk] and CT)v(T) = {t = EK act, EK a; = 1, > 0}. We denote it as T.GGO = (GG())) for short.
Now we proceed to show how MGEO takes anchor-based and anchor-free methods as special cases (a brief description of these methods is included in Appendix A.
Example 1 (anchor-based), For each class j E [K]. anchor-based methods assumes that there exists an anchor point x with P(Y X = x²) = e². So T., = g(x') ) and [[]))]] 2 [()) for all æc Anchor methods first fit g(-) on the noisy data and then find the most confident sample a in ((n) for class j. Then they set T.j g(x²). This is equivalent to solving equation I with the following metric:
M(T) Σ (TH + min [T.,, - g(xx))12).
sEin]
jE[R]
The intuition is as follows: because equation requires ((n) to be contained in conv(T), we must have T2 g( [[] otherwise g(x") will be outside of conv(T). At the same time, have mingejm] [|T, g(x;) ||| > 0 for all T and j. So choosing T. = g(x²) can minimize equation because Т₁ = g(x)) [b] and [T. g(xx)) l|2 0.
Example 2 (Minimum Volume, freee. The Minimum Volume method proposed by Li et al. (2021) uses the volume of T the metric:
M(T)- Vol(T).
(3)
3

---

Published as a conference paper at ICLR 2023
The MGEO-baseee methods can work well if the posterior is perfectly estimated. i.e. g(z) = g(z) for all 2. In this case, MGEO methods can identify T" under suitable conditions. However, it is common that g(x) + g(x) for some in practice because of DNN's over-confidence. An error in the posterior estimation can easily skew the smallest convex hull which encloses all data points as illustrated in Figure I. Then MGEO methods lead to inaccurate T-estimation in this case. To understand the sensitivity of the MEGO methods to the posterior estimation error, we consider a simple case where g(x:) agrees with g(x) almost everywhere except from a single point x' ((n):
ge, (x) = [((x) + if x - x', ())r), otherwise.
(4)
where e is the error of the estimated posterior x' and it needs to satisfy that g(x²) + e has all non-negative elements which sum up to 1, i.c., e e E == {elle + 5(z')1 = = 1, (E ((x')) 2
0, Vi E [K]]. Let Ge (n) == (0.,
be set of the fitted posteriors by Je. (-). Similarly, we denote (n)) = () - Further, let T.MGEO and T.GGO be the solution of MGEO on (()) and Ge (n), i.e., M.GEO (()(n)) and TMGEO ((Ge,xr We have T.MG T" under suitable conditions (Patrini et al., 2017; Li et al., 2021). We then interested in the T Testimaation error due to e in terms of the Frobenius norm, i... | lE. Following are the results:
c,
Proposition 1. Under assumptions specified in Appendix A.4, suppose that we obtain an imperfect estimation of the noise posterior ge (.) as described in equation Then MGEO-bass methods lead to a T-estimation error whose minimax lower bound is: supecz |
T |F Z 92(1).
See Appendix A.4 for the proof. Proposition 1 shows that MEGO methods can lead to a constant level of T-estimation error under the fitted posterior -e.x² (.). This is in analogy to Figure 1 (left) that a single outlier caused by e can skew the smallest convex hull that encloses all samples. Note that Proposition shows that the error caused by the inaccurate posterior estimation does not shrink to zero as the sample size increases. Thus MGEO methods can be in in-consistent in this case. In the following corollary of Proposition 1, we formally state the in- in-oosiitt of MEGO:
Corollary 1 (In-consistency of MGEO), Under assumptions specified in Appendix A.4, suppose that we obtain an imperfect estimation of the noise posterior ge (-) as described in equation 4. Then MGEO-based. methods can be inconsistent, i.e., there exists an 6 such that TMGEO f T as c,a"
+
Proof. In the proof of Proposition 1, we already show that there exists an such that |TMCCO The 2 ((1). Since this result holds for any simple size If lim T.MGE does not exists the
claim holds immediately. Otherwise if lim TIMGE exists, we have || |imim
T.MGEO TM
>
c,
2(1), which leads to lim e,00'
+ T So we conclude that T.MGEO A T as + 00.
2.2 EMPIRICAL FINDINGS
Unfortunately, due to the tendency of Deep Neural Network to make over-confident prediction, there inevitably outliers due to erroneous posterior estimation. Because MGEO methods attempts to find the smallest T that convers all the samples, those outliers can severely skew the T and degrades the estimation accuracy. We observe this phenomenon widely exists in existing methods. In Figure 1 (b), we illustrate the T estimation results of the Minimum Volume method. The red triangle is the oracle T* We can see that there are lots of samples whose estimated posteriors are out of the red triangle. The purple triangle are the fitted T by the Minimum Volume method, which is highly skewed by the outliers. Refer to Appendix B. for experimental details.
ROBUST BILEVEL OPTIMIZATION (ROBOT)
In the last section, we discussed the instability of MGEO methods when the noisy posterior estima- tion is imperfect. Proposition shows that even if the estimated posterior differs from ğ(-) at single point, MGEO can lead to a constant level of Tessimmation error. This is because the Tesstimation of MGEO depends on finding convex hull to enclose all samples and such convex hull is determined by the the outermost samples. Therefore, if there is an outlier due to inaccurate posterior estimation, the resulting convex hull can be easily skewed.
4

---

Published as a conference paper at ICLR 2023
x
T
San (T)
Reingte
0,0.0
1.00
Clea
Co
X7
Dobate
(a) Illustration
(b) Results MGEO
(c) Results of ROBOT
Figure 1: (a) Illustration of how the posterior estimation enror lead to T-estimation error in a 3-class classification task. The posteriors of the blue points are accurately estimated and they all in conv(T"). There an error on the noisy posterior of æ', which is denoted in red. Because P x') + e lies outside of conv(T"), MGEO needs find larger T enclose it. (b) Visualization of MGEO (Minimum Volume) method in a 3-class MNIST classification task. ) is denoted by the red triangle. There are many outliers whose estimated posteriors are out of cT*)(T") due to overfitting. MGFO methods result in leads to inaccurate T because they try to enclose all the samples, including the outliers. (c) ROBOT obtains more accurate T than MGEO.
Then natural question to ask is, can we go beyond Geometric Envelope Operator to obtain a robust and consistent T estimattion ? As thought experiment, let's use a simple case for example. Sup- pose ((x,) [[] = 0.5 for all i. We aim to estimate the T by the anchor point method. If g()) = g(-), we have Tj = [mx g(x;))
= 0.5. Now suppose that we obtain inaccurate posterior with 7() + where & ~ (O,, o²) for some small a. We then have E = EE [m [(x:)]]] + [ - 0.5 - a ov (ogg(() for large n (Ho & Hsing, 1996). So this method is inconsistent
some small Gaussian error, i.e., g()
with infinite samples. On the other hand, it is well known that the sample mean estimator is consistent by Lin> ((x + 0.5 as n - co. This toy example shows that the sample mean estimators are consistent while MGEO methods are not because they depends on the maximum of the samples. In light of this, we provide the framework ROBOT as the first attempt to estimate T based on the sample mean estimators.
3.1 METHODS
Denote the optimal parameter that minimizes the cross entropy loss on the clean dataset as 0 = arg ming L(Je, D). A popular method is to minimize following forward correction loss on the noisy dataset (Patrini et al., 2017):
Q arg min So. D)
(5)
T,8
Patrini et al. (2017) shows that the forward correction is consistent, i.e., 0 0" if T", under suitable conditions. These conditions are mainly on the sufficiently large function space of fo and proper composite loss functions. We discuss these conditions in Appendix A.3 for completeness. Though equation 5 is consistent, solving equation 5 can not uniquely identify T* and 0". This is because if T T2 and fo, (-) Tofo- (-), Ti and 0, can also achieve the optimal loss. In order to make T identifiable, MGEO tries to find the minimum T whose conv contains all data points. Now we try to go beyond MGEO and aim to identify T by seeking for some sample mean estimators.
Since the solution of 0 in equation 5 depends on if T fixed, we then use ((T)) to explicitly denote such dependency, i.e., ((T) = arg ming C(T D). By the consistency of the forward correction, we already know Ö(T*) Therefore,
0r under suitable conditions described in Appendix A.3. seek for good T by evaluating (T)) If we have the clean dataset DD this would be straightforward by checking whether (TT) minimizes the clean loss L(farry: D). Specifically, combining 8" ((T") and 6" arg min, D(fa,D), we can uniquely identify T* by T" arg miny L(JāT): D). Notably, [(Jarr) D) depends on the sample mean of the losses, which is consistent according to the law of large numbers. Now the new challenge arises: we do not have the clean dataset D in practice. Can we find sample mean estimator only based on the noisy dataset D which is minimized by 0r (which is also ( ))?
5

---

Published as a conference paper at ICLR 2023
Readers familiar with the noise robust losses may already guess next proposal. Existing works have proposed several losses robust to label noise, e.g., Mean Absolute Error (MAE) and Reversed Cross-entropy (RCE), whose minimizer is the same the noisy dataset with that the clean dataset under suitable conditions (Wang et al., 2019; Ghosh et al., 2017). These conditions are described in Appendix A.2. Let fub be the noise robust losses and Labb be the corresponding risk on datasets. Then we have the following:
arg min (fo, D) = arg min Cuo (fo. D).
(6)
Therefore, we can use [fo. D) to measure the optimality of ((T). This property enables us to seek for T = T by checking whether T minimizes (forry D). The above-mentione proce- dure can be naturally formulated into a bi-level problem: We split the noisy dataset into a training set Dir and validation set D... In the inner loop, T is fixed and we obtain ((T) by minimizing the forward correction loss on the training set over 0, i.c., ((T) ;= arg ming [(T Drr). In the outer loop, we optimize the robust loss of fūrT) on the validation dataset by minimizing over T, i.e.,
minr Loob (f D.). We summarize the bilevel procedure as follows:
min (Foer)) D.))
s.t. ((T) = arg min C( Drr)
We name it as RObust Bilvel OpTmization (ROBOT), Remarkably, both L and Lrsh are consistent estimators by the law of large numbers without requiring perfect noisy posteriors (Jeffreys, 1998). We also include the convergence of ROBOT in Appendix A.9 for completeness, which is appli- cation of standard bilevel optimization.
Remark 1. A curious reader may wonder it is possible to use two-step procedure instead of the bilevel framework: first learn Ô by minimizing equation 6 and then plug the Ô into equation to obtain T. From the statistical property view (ignoring the optimization difficulty). we may have i l" with infinite samples and then it can further leads to T = T". However, existing works show that robust losses are very hard to optimize (Zhang & SSbuncu, 2018; Wang et al., 2019), indicating that directly optimizing equation on 0 can hardly lead to the optimal 0 in practice. Our ROBOT in equation 7 transforms the optimization from the space of neural network parameters to the space of T when minimizing LoabJ D) over T. The experimental results in Appendix B.4 show that training ROBOT can significantly decrease the training robust loss while directly optimizing the robust loss fails to do so. This indicates that the reparametrization of ROBOT may have better convergence property on minimizing the robust loss. We will investigate the in-depth mechanism of this interesting phenomenon in the future.
3.2 THFORETICAL ANALYSTS OF ROBOT
In this section, we analyze the theoretical properties of ROBOT in equation 7. First we show the identifiability of I with infinite noisy samples. Then we provide the finite sample generalization bound together with the consistency. We first start with some mild assumptions:
Assumption 1. The optimal 0= for the cross entropy on the clean dataset also minimizes the robust losses on the clean dataset DD i.e., (0 D) < (o for all 0 + 0-.
This assumption is natural because fo- (x) P(Y x) is supposed to be optimal for both cross entropy and robust losses on the clean dataset. Further, Ghosh et al. (2017) shows that these losses are class-calibrated, and minimizing them leads to the decrease 0-1 error. We assume d* is unique, or otherwise we can also concern ourselves with the one with the minimum norm and the identifiability results are the same. Notably, robust losses are more difficult to optimize and they often lead to under-fitting when applied on deep neural networks (Wang et al., 2019; Zhang & Sabuncu, 2018). So it is quite difficult to obtain 0" in practice by minimizing (0, D) over 0. ROBOT prevents this issue by using bilevel optimization. Refer to Remark for more discussion. Assumption 2. The mapping (T) is injective, i.e,, ((T)) + ((T)) &T2
Then we present the identifiability result given infinite samples follows:

---

Published as a conference paper at ICLR 2023
Table 1:
A comparison between MGEO methods with ROBOT. MGEO methods contain anchor-
based (Liu & Tao, 2015; Patrini et al., 2017) and anchor-free free (Li et al., 2021; Zhang et al., 2021)
methods. *The consistency considered here refers to the setting where we do not assume the noisy posterior is perfectly estimated since posterior estimation errors are inevitable in practice.
No anchor point assumption
Identifialiility
Consistency"
Finite sample generalization
Fmor under 9.,x'
MGEDtAnchor-bascc)
x
XCol 1) X(Col
X 7(hm 2)
[(11 (Prop 1)
MGEOAAnchorrfriee) ROBOT
R( (Prop
4(Thm 1)
7(Thm 2)
011/a] (Prop 2)
Theorem 1 (Identifiabilitt)) Suppose Condition 1 -3 (in Appendix A.2 and A.3) and Assumption 1- 2 holds, our framework in equation 7 can uniquely identify T with infinite noisy samples, i.e,,
L (0(T)) (O))( for all T + T
See Appendix A.5 for the proof. Theorem I shows ROBOT can uniquely learn T based on infinite noisy samples. Notably, we neither require the existence of anchor points, nor assume that the noisy posterions are perfectly estimated, which distinguishes ROBOT from MGEO based works Li et al. (2021); Zhang et al. (2021). We further present the finite sample generalization results as follows:
Theorem 2 (Finite Sample Generalization and Consistency). Suppose we have (,(n) with sam- ples. Assume the loss function is bounded by E(.,-) S M. Let the function class be F == (e(ferr(()i-) X x x + Rt VT T}. Fix any 0, assume obtain e-approximated solution T that satisfies Coub (T()), D.()) S Lub (0 (n))) +e, VE, ET Let, (1xc) be the c-cover ofF. F. Then with probability at least 8,
2 2ln(2N Fr, 1kx)
(ro)) D) S inf Lub (oml(((()))))))) (((T), + 20 V
(8)
TET
Further, if equation 7 is well solved (e - 0), then T -. T -> xC.
The full proof of Theorem is included in Appendix A.6. We also add additional results on the convergence of T T-estimation error in Appendix A.11. Due to the instability of MGEO methods, the finite sample guarantees have been missing in MGEO methods. The consistency of our method is direct consequence of finite sample property. Notably, the consistency of existing works (e.g., Theorem 2 of Zhang et al. (2021)) requires that the noisy posterior is perfectly estimated, which does not hold in more realistic settings we consider. We then analyze the stability of ROBOT under the inaccurate noisy posterior Je,x' as defined in equation 4.
Proposition 2 (Stability). Consider we obtain an inaccurate posterior ge (-) as defined in equa- tion 4, the T Testimaation error of ROBOT upper bounded as: sup, | T S ((1nn)
See Appendix A.7 for proof. Comparing Proposition 2 with Proposition 1, we achieves an (11/n) robustness to the posterior estimation error in the case where MEGO leads to an constant error. Finally, we summarize the comparison between ROBOT with MGEO in Table 1.
that ROBOT
EXPERIMENTS
In this section, we conduct extensive experiments to demonstrate the effectiveness of ROBOT. Our method demonstrates superior performances compared with other state of the art approaches base on loss correction. In particular, we try two robust losses for the outer loop loss function of ROBOT, namely MAE (Ghosh et al., 2017) and RCE (Wang et al., 2019) losses.
Benchmark Datasets. We experiment our proposed method on three synthetic datasets: MNIST, CIFAR10 and CIFAR 100. In addition, we also conduct experiments on three real world datasets, namely CIFAR10-N CIFARTON 100N and Clothing IM. For synthetic dataset experiments, we run ex- periments with two types of commonly used noise generation processes: symmetric and fair-flip noises. The experiments were repeated for 5 times, we report both the mean and standard deviation of our results. The results of the baseline approaches are derived from Li et al. (2021). For more details about the datasets and noise generation, please refer to the appendix.
Baseline Methods, Network Architectures and Training. We compare our ROBOT with the following baselines: Decoupling (Malach & Shalev-Shware 2017), Co-teaching Han et al. (2018), T--eeisioon Xia et al. (2019), MentorNet (Jiang et al., 2018), Forward (Patrini et al., 2017),MAF
7

---

Published as a conference paper at ICLR 2023
Test accuracy of experiments on MNIST, CIFARIO and CIFARI00 with different noise types and noise ratios. Our method significantly outperforms the counterparts by a large margin across all experiment settings. Notably, the superiority of our method becomes more evident under challenging scenarios, such as CIFARI00 dataset with flip noise.
Table 2:
Datasets
MNIST
CIFARIO
CIFARI00
Uniform 20%
Uniform 50%
Uniform 20%
Uniform 50%
Uniform 20%
Uniform 50%
Decoupling
97.04
94.58=0.08
77.32=0.35
54.07=0.446
41.92=00.49
22.63=0044
MentorNet
97.21=:0.06
95.56:10.15
81.35=0023
73.47::0.15
42.88:10.44
32.66:20.40
Co Co-leaching
97.07.10.10
95.20.10.23
82.27-00007
75.55.10.07
48,48 1.666
36.77.10.52
Forward
98.60-10.19
97.77=10.16
85.20=0080
74.82:10078
54.90:10.74
41.85
T-Revision
98.72.10.10
98.23.10.10
87.95
80.01:10.62
62.72.10.69
49.12:10,22
MAF
97.13-4-0.13
95.30-10.15
83.28=0.39
82. 03.10--10
55.67 003
43.53-1 1.11
RCE
97.02+0.19
95.56==0.30
85.63=0.64
82.79=00.96
53.21=1.100 .10
44,24+1.20 1.31
DMI
98.70==0.02
98.12=0.221
87.54=0.20
82.68+00221
62.65=00.39
52.42=0.644
Dual T
98.43:1:0005
98. 18.15
88.35 0.33
82.54:10.19
62.16:10..88
52.49.10.37
TVD
98.56:1:0.09
98. 16.11110.16
0.28
83.21:10.13
63.52.10.40
$2.54:1 1.33
VolMinNet
98.74:10.08
98.23:20.16
89.58:00.26
83.37:20.25
64.94:::.00
53.89 1,26
ROBOT (MAR)
99.01:1:0.03
98.50-1...0P
92.13--0.00
88.75-10.10
72.52.10.15
64.69 0.332
ROBOT (RCE)
99.05:1:006
0.154:00.4
92.09=0.00
88,45:10115
73.03:10.12
0..11
Datasets
MNIST
CIFAR10
CIFAR100
Flip 20%
Flip 45%
Hipp
Plip
Flip 20%
Flip
Decoupling
96.93110.07
77.13-1..30
53.71
40.12.100.6
27.97.10.12
MentorNet
96.89--0.00
91.98=0.46
77.42=0.00
61.033+:0:20
39.22 +0047
06.48=00337
Co leaching
97.00.10.06
96.25
80.65
73.02 1.0.33
42.79 0.079
27.97
Forward
98.84:10.110
95.06-12.66
20.41
77 44.44:16889
56.12:10.54
36. 2..32
T-Revisioo
98.89
84.56 18
90.33=0.52
78. 78.94-22.58
64.33:t0049
01.55=00.55
MAE
97.43-1-0220
95.45=0.566
79.30=0.13
57.13-15.61
12.15::1.22
19.56=1..50
RCE
97.10.1...18
94.60.00.54
82.53
59.65 1.223
53.10.1.1.3
40,02 1.47
98.84-1-0.00
97.92-10.76
89.89=0.45
73.15-47.31
59.56.1-0.73
17::2.02
Dual T
98. 78.86+20.00
96.71=0.22
89.77 +0.25
76.53 #2.51
67.21=00443
47,60==0443
TVD
98.98 98.98:10.04
99.12.10.09
90.01 0.223
88. 18.15:10.10 10
67.65.10.89
56.51-10.16
VolMinNet
99.01=:0.07
99. 99.00=20.07
90.37=0.30
88.54:10:21
68.45:t0.69
08.90=20.9
ROBOT (MAE)
99.39-1-.00
99.19-10.10
0.07
92.52:10.11
75.55-10.39
70.20-10..8
ROBOT (RCE)
99.34=10.22
99.23==0.10
93.62=0003
92.44:10023
75.79:10.51
70.17=00.40
loss (Ghosh et al., 2017), RCE loss (Wang et al., 2019), DMI loss (Xu et al., 2UAL) Yao et al. (2020),Tota) Variation Regularization (Zhang al., 2021) and VolMinNet (Li et al., 2021). I). We follow the experiment setting as in Li et al. (2021) and report the baseline results given in their paper. We point that, similar to Xia et al. (2019; 2021); Li et al. (2021); Wei et al. (2021), the aggregation methods such as SELF (Nguyen et al., 2019) and DivideMix (Li et al., 2020) are not compared in our paper, because such methods incorporate tricks such as semi-supervised training, which can be sensitive to the choice of hyper-parameters We use the same network architectures as in Li al. (2021). The experimental details are included in Appendix B.3.
Experiments on Synthetic Label Noise. We compare our method with other approaches on com- monly used datasets with synthetic label noise as described in Section 4. The results in shows that ROBOT consistently outperforms baselines by a large margin across all datasets and types of label noise. Remarkably, the advantage of our method becomes more evident when the task gets more challenging. For instance, our method outperforms the previous SOTA T estimation approach VolMinNet Li et al. (2021) by 11.22% and 11.27% in test accuracy for CIFARI00 with 50% Uni- form noise and 45% pairflip noise, respectively.
Estimation Error of Transition Matrix. We compare the T-estimation error with other approaches on variety of datasets with different settings. Note that with synthetic label noise, have the ground truth T", and therefore able to calculate the estimation error. The results in Table show that ROBOT achieves lower Tessimattion error than MGEO- based methods. Note that the comparison between ROBOT and the two-stage methods supports the argument in Remark 1.
Experiments on Real World Label Noise. To furthur verify the ability of our method to han- dle label noise learning, we conduct experiments with datasets containing real-world label noise. Specifically, we showcase the performance of our method on CIFARIO-N, CIFAR 100-N (in Table 4) and Clothing LM (in Table 5) datasets. Note that in this paper, we mostly focus on the estimation of transition matrix T that is robust to outliers, therefore, we mainly compare with approaches based on loss correction for faimess. We can observe that our method outperforms other basclines by noticeable margin, which verifies ability to handle real world label noise.
8

---

Published as a conference paper at ICLR 2023
Table 3: We compare the noise transition matrix estimation errors between various methods across multiple datasets. Note that Two-stage methods correspond to the alternative approach mentioned Remark 1. We can see that ROBOT consistently achieves the lowest estimation error.
MNIST
CIFARIO
CIFARIOO
Uniform 20%
Uniform 50%
Uniform 20%
Uniform 50%
Uniform 20%
Uniform 50%
Forward
0.33==0.09
0.56=00.0
0.39::0.02
1.05+:0.21
0,50=00,10
1.11:0.25
Revissoon
0.17.10.04
0.16.10.05
0.23.1.0.99
0.30:10.10
0.46.10.09
0.6110.112
Twa-stage (MAF)
0.1710.11
0.19:10.18
0.23::::20
0.324:0.11
0.48
0.70=10.23
Twa-stage (RCE)
0.16=#0.10
0.21
0.35::0.18
0.40:t0.12
0.49:20.19
0.61
0.25:1:.04
0.30:1:0055
0.77:4:034
0.48:10.14
1.02.40.25
VolMinNet
0.07=0002
0.09=00.33
0.21
0.12+:0.05
0.47=0.10
0.50=20.13
ROBOT (MAR)
0.03:10.01
0.03:10.01
0.10:1:0011
0.10-1:0.03
0.18:10.06
0.02:110.6
ROBOT (RCE)
0.03=20001
0.03:10.02
0.07:::0033
0.09:1:.02
0.20:20.05
0.31
Datasets
MNIST
CIFARIO
CIFARI00
Flip 20%
Flip 45%
Flip 20%
Flip 45%
Flip 20%
Flip 45%
Forward
0,31
0.77:20.15
0.45::0.09
0,97.:0112
0.48:20.12
0.96:20.15
T-Revision
0..022002
0.25::0.04
0.20:+:.10
0.29:t0.12
1.
0.92:20.34
Twa-stage (MAE)
0.16=20.10
0.22::0.09
0.20:t:.112
0.32+:0.11
0.50::0.23
0.90=20.44
Twa-stage (RCE)
0.13
0.24:10010
0.19::0.15
0.40:10.12
0.47:10.30
0.95:10.50
Dual T
0.10.10.02
0.45.10.09
0.32 10.00
0,75 1.0.20
0.45
0.98.10.2
VolMinNer
0.04+0001
0.04::0.01
0.12:4:003
0.13::0.04
0.13200.4
0.25
ROBOT (MAE)
0.02.10.01
0.00110.01
0.09.10.02
0.11.1.001
0.11:10.03
0.22.1
ROBOT (RCF)
0.02::0001
0.03:10.01
0.07:1:001
0.10:1:003
0.12::0.05
0.19::0.05
Table 4: Test accuracy of experiments on CIFAR10-N and CIFAR 00-N with different noise types. For fair comparison, we only compare against the approaches that are designed based on transition matrices. Our method consistently outperforms the counterparts across all experiment settings.
CIFARIO-N Random 2
CIFAR100 Noisy
Aggregate
Random
Random 3
Wonst
CE
87.77.10.38
85.02 0.65
86.46.11.79
85.16:10.61
77.6911..5
50.50:10.66
MAE
85.63-10.55
04.38-10.34
84.64:1...0
85.05
77.34. 1.56
$1.24 1.35
RCE
85.02-10.67
04.80
84.23-:0.50
84.03-20.33
77.43:+:097
51.80=t .4
GCE
87 07.05:00.70
87.61=20.28
87.70:+:0.56
87 07.5820:229
80.66:2:0.53
56.73:20.30
Backward-T
88.13:10.29
87.14::0.34
86.28:10.80
86.86:10.41
7.061::..05
57.14:10.994
Forward-T
88. 88.24_10.22
86.88110.50
86.14:10.21
87.04.10.35
79.49.10.46
57.01
T-Revision
88.52-40.17
88.33-20.32
87.71:11.022
87.79:10.67
80.48:1:1.2
51.55::0.31
TVD
88.96.10.15
88.11
88.35.10.11
88.01
80.15:10.255
10.32
VolMinNet
89.70:1:012
88.30:10.12
88.27:1:0.99
88. 19:10.41
80.53:::0.20
$7.80:10.31
loss
90.75:t:.255
89.06:20111
88.76::0.19
88.57=0.199
82.53::0.52
57.59:#0.61
(MAF) ROBOT (RCE)
91.14:10.12 91.35:20.03
90.35-10.14
90.30-1-0.16
90.34:00116
84.08:1-0.22 84.05:+0.33
61.14:10.29 61.25=00.26
90.46=0.188
90.37-+0.15
90.31=0.211
Table 5: Test accuracy of experiments on Clothing M. We only adopt noisy data during training.
Decoupling $4,53
MentorNet $6.79
Co-teaching 60.15
Forward 69.91
Dual 71.49
T-Revision 70.97
DMI
PTD 70.12
TVD 71.67
VolminNer 72.42
ROBOT (MAE) 72.64
ROBOT (RCE)
70.97
72.70
CONCLUSION
In this paper, we investigate the problem of learning statistically consistent models under label noise by estimating T. We first propose the framework MGEO unify the existing T-estimation methods. Then we provide both theoretical and experimental results to show that MGEO methods are sensitive the error in noisy posterior estimation. To overcome the limitation of MGEO, we further propose ROBOT, which enjoys superior theoretical properties and shows strong empirical performance.
REPRODUCIBILITY STATEMENT
The experiments in the paper all conducted using public datasets. The hyperparameters and network choices for the experiments are elaborated in Section 4 and Appendix B. We submit the source code with the ICLR submission. The code will be make public upon acceptance of the paper.

---

Published as a conference paper at ICLR 2023
For the theory part, the assumptions and full proof included in Section 3.2, Appendix A.4, A.5, A.6 and A.6.
ACKNOWLEDGEMENT
BH was supported by NSFC Young Scientists Fund No. 62006202, Guangdong Basic and Applied Basic Research Foundation No. 2022A151501 1652, RGC Early Career Scheme No. 22200720, CAAI-Huawei MindSpore Open Fund and HKBU CSD Departmental Incentive Grant. XBX was supported by Australian Research Council Project DE-190101473 and Google PhD Fellow- ship. TLL was partially supported by Australian Research Council Projects IC- IC-190100031, LP- 220100527, DP-220102121, and FT-220100318.
REFERENCES
Dara Bahri, Heinrich Jiang, and Maya Gupta. Deep k-nn for noisy labels. In International Confer- ence on Machine Learning, pp. 540-550, PMLR, 2020.
George Cazenavette, Tongzhou Wang, Antonio Torralba. Alexci A Efros, and Jun-Yan Zhu. Dataset distillation by matching training trajectories. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 4750-4759, 2022.
Mark Collier, Basil Mustafa, Ef Kokiopoulou, Rodolphe Jenatton, and Jesse Berent. Correlated input-dependent label noise large-scale image classification. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 1551-1560, 2021.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. International Conference on Machine Learning, pp. 1126-1135. PMLR, 2017.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning. pp. 1165-1173, PMLR, 2017.
Jiahui Gao, Hang Xu, Xiaozhe Ren, Philip LH Yu, Xiaodan Liang, Xin Jiang, Zhenguo Li. et al. Autobert-zero: Evolving bert backbone from scratch. arXiv preprint arXiv:2107.07444 2021.
Jiahui Gao, Yi Zhou, Philip LH Yu, Shafiq Joty, and Jiuxiang Gu. Unison: Unpaired linsslln image captioning. 2022.
Aritra Ghosh, Himanshu Kumar, and PS Sastry. Robust loss functions under label noise for deep neural networks. In Proceedings of the AAAI conference artificial intelligence, volume 31, 2017.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International conference on machine learning, pp. 1321-1330. PMLR, 2017.
Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. Advances in neural information processing systems, 31, 2018
Hwai- Maaii-Chngg Ho and Tailen Hsing. On the asymptotic joint distribution of the sum and maximum of stationary normal random variables. Journal of applied probability, 33(1): (3(1):38-1455) 1996.
Jinchi Huang, Lie Qu, Rongfei Jia, and Binqiang Zhao. O2u-net: A simple noisy label detection approach for deep neural networks. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 3326-3334, 2019.
Harold Jeffreys. The theory of probability. OUP Oxford, 1998.
Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. Mentornet: Learning data- driven curriculum for very deep neural networks on corrupted labels. International conference machine learning, pp. 2304-2313, PMLR, 2018.
10

---

Published as a conference paper at ICLR 2023
Youngdong Kim, Juseung Yun, Hyounguk Shon, and Junmo Kim. Joint negative and positive learn- ing for noisy labels. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9442-943 2021.
Junnan Li, Richard Socher, and Steven CH Hoi. Dividemix: Learning with noisy labels as semi- supervised learning. arXiv preprint arXiv:2002.07394 2020.
Shikun Li, Xiaoho Xia, Shiming Ge, and Tongliang Liu. Selective-supervised contrastive learning with noisy labels. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 316-325, 2022a.
Shikun Li, Xiaobo Xia, Hansong Zhang. Yibing Zhan, Shiming Ge. and Tongliang Liu. Estimating noise transition matrix with label correlations for noisy multi-label learning. In Advances in Neural Information Processing Systems, 2022b.
Xuefeng Li, Tongliang Liu, Han, Gang Niu, and Masashi Sugiyama. Provably end-to-end label- noise learning without anchor points. In International Conference on Machine Learning, pp- 6403-6413. PMLR, 2021.
Yong Lin, Hanze Dong, Hao Wang, and Tong Zhang. Bayesian invariant risk minimization. In Pro- ceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 16021- 16030, 2022.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv:1806.0900 2018.
Sheng Liu, Jonathan Niles Weed, Narges Razavian, and Carlos Fernandez-Granda. Early-learning regularization prevents memorization of noisy labels. In Advances neural information process- ing systems, pp. 20331-20342, 2020.
Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. JEEE Transactions pattern analysis and machine intelligence, 38(3):447 461, 2015.
Yang Liu and Hongyi Guo. Peer loss functions: Learning from noisy labels without knowing noise rates. In International conference on machine learning, pp. 0226-6236. PMLR, 2020.
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International Conference on Artificial Intelligence and Statistics, pp- 1540-1552. PMLR, 2020.
Xingjun Ma, Hanxun Huang, Yisen Wang, Simone Romano, Sarah Erfani, and James Bailey. Nor- malized loss functions for deep learning with noisy labels. In International conference machine learning, pp. 6543-6553, PMLR, 2020.
Matthew MacKay, Paul Vicol, Jon Lorraine, David Duvenaud, and Roger Grosse. Self-tuning net- works: Bilevel optimization of hyperparameters using structured best-response functions. arXiv preprint
2019.
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient- based hyperparameter optimiza- tion through reversible learning. In International conference on machine learning, pp. 2113-1122. PMLR, 2015.
Eran Malach and Shai Shalev-Shwartz. Decoupling" when update" from" how to update". Ad- vances in neural information processing systems, 30, 2017.
Duc Tam Nguyen, Chaithanya Kumar Mummadi, Thi Phuong Nhung Ngo, Thi Hoai Phuong Nguyen, Laura Beggel, and Thomas Brox. Self: Learning to filter noisy labels with self- ensembling, arXiv preprint 1rXiv:1910.01842, 2019.
Alex Nichol and John Schulman. 1rXiv:1803.02999 2(3):4, 2018.
Reptile: a scalable metalearning algorithm. arXiv preprint
Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu. Making deep neural networks robust to label noise: A loss correction approach. Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1944-1952, 2017.

---

Published as a conference paper at ICLR 2023
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International con- ference on machine learning, pp. 737-746. PMLR, 2016.
Hieu Pham, Melody Guan, Barret Zoph, Quoe Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In International conference on machine learning. pp. 4095 4104. PMLR, 2018.
Renjie Pi, Weizhong Zhang, Yueqi Xie, Jiahui Gao, Xiaoyu Wang, Sunghun Kim, and Qifeng Chen. Dynafed: Tackling client data heterogeneity with global dynamics. arXiv preprint arXiv:2211.10877 2022.
Geoff Pleiss, Tianyi Zhang, Ethan Elenberg, and Kilian Q Weinberger. Identifying mislabeled data using the area under the margin ranking. In Advances in neural information processing systems, pp. 17044-17056, 2020.
Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In International conference on machine learning, pp. 4334 4343. PMLR, 2018.
Franco Scarselli and Ah Chung Tsoi. Universal approximation using feedforward neural networks: A survey of some existing methods, and some new results. Neural networks, 11(1):15-37 1--17, 1998.
Clayton Scott. A rate of convergence for mixture proportion estimation, with application to learning from noisy labels. In Artificial Intelligence and Statistics, pp. 838-846. PMLR, 2015.
Clayton Scott, Gilles Blanchard, and Gregory Handy. Classification with asymmetric label noise: Consistency and maximal denoising. Conference on learning theory, pp. 489-511. PMLR, 2013.
Han Shi, Renjie Pi, Hang Xu, Zhenguo Li, James Kwok, and Tong Zhang. Bridging the gap between sample-based and one-shot neural architecture search with bonas. Advances in Neural Information Processing Systems, 33:1808-188 1819, 2020.
Han Shi, Jiahui Gao, Xiaozhe Ren, Hang Xu, Xiaodan Liang, Zhenguo Li, and James Tin- Yau Kwok. Sparsebert: Rethinking the importance analysis in self-attention. In International Confer- ence on Machine Learning, pp. 9547-9557 PMLR, 2021.
Jun Shu, Qi Xie, Lixuan Yi, Qian Zhao, Sanping Zhou, Zongben Xu, and Deyu Meng. Meta- weight-net: Learning explicit mapping for sample weighting. Advances in neural information processing systems, 32, 2019.
Ankur Sinha, Pekka Malo, and Kalyanmoy Deb. A review bilevel optimization: from classical to cvolutionary approaches and applications. IEEE Transactions on Evolutionary Computation, 22 (2):276-295, 2017.
Paul Vicol, Luke Metz, and Jascha Sohl-Dickstein. Unbiased gradient estimation in unrolled com- putation graphs with persistent evolution strategies. In International Conference on Machine Learning, pp. 10553-10563. PMLR, 2021.
Tongzhou Wang, Jun- Yan Zhu, Antonio Torralha, and Alexei Efros. Dataset distillation. arXiv preprint 181 1..99 2018
Xinshao Wang, Yang Hua, Elyor Kodirov, David A Clifton, and Neil M Robertson. Proselflc: Progressive self label correction for training robust deep neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 752-761, 2021.
Yisen Wang, Xingjun Ma, Zaiyi Chen, Yuan Luo, Jinfeng Yi, and James Bailey. Symmetric cross entropy for robust learning with noisy labels. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 322-330, 2019.
Hongxin Wei, Lei Feng, Xiangyu Chen, and Bo An. Combating noisy labels by agreement: A joint training method with co-regularization In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13726-13735. 2020.
12

---

Published as a conference paper at ICLR 2023
Jiaheng Wei, Zhaowei Zhu, Hao Cheng, Tongliang Liu, Gang Niu, and Yang Liu. Learn- ing with noisy labels revisited: A study using real-world human annotations. arXiv preprint arXiv: 10..1088,, 2021.
Songhua Wu, Xiaobo Xia, Tongliang Liu, Bo Han, Mingming Gong, Nannan Wang. Haifeng Liu, and Gang Niu. Class2simi: A noise reduction perspective on learning with noisy labels. In International Conference on Machine Learning, pp. 11285-11295. PMLR, 2021.
Xiaobo Xia, Tongliang Liu, Nannan Wang, Bo Han, Chen Gong, Gang Niu, and Masashi Sugiyama. Are anchor points really indispensable in label-noise learning? Advances in Neural Information Processing Systems, 32, 2019.
Xiaobo Xia, Tongliang Liu, Bo Han, Nannan Wang. Mingming Gong, Haifeng Liu, Gang Niu, Dacheng Tao, and Masashi Sugiyama. Part-dependent label noise: Towards instance-dependent label noise. Advances in Neural Information Processing Systems, 33:7597-7610, 2020.
Xiaobo Xia, Tongliang Liu, Bo Han, Chen Gong, Nannan Wang, Zongyuan Ge, and Yi Chang- Robust early-leaming: Hindering the memorization of noisy labels. In International conference on learning representations, 2021.
Xiaobo Xia, Bo Han, Nannan Wang, Jiankang Deng, Jiatong Li, Yinian Mao, and Tongliang Liu. Extended T: Learning with mixed closed-set and open-set noisy labels. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Tong Xiao, Tian Xia, Yi Yang, Chang Huang, and Xiaogang Wang. Learning from massive noisy labeled data for image classification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2691-2699, 2015.
Yilun Xu, Peng Cao, Yuqing Kong, and Yizhou Wang. L_dmi: A novel information-theorree loss function for training deep nets robust to label noise. Advances in neural information processing systems, 32, 2019.
Lewei Yao, Renjie Pi, Hang Xu, Wei Zhang, Zhenguo Li, and Tong Zhang. Joint-detnas: Upgrade your detector with nas, pruming and dynamic distillation. In Proceedings of the IEEE/CVF Con- ference on Computer Vision and Pattern Recognition, pp. 10175-10184, 2021a.
Yazhou Yao, Zeren Sun, Chuanyi Zhang, Fumin Shen, Qi Wu, Jian Zhang, and Zhenmin Tang- Jo-src: A contrastive approach for combating noisy labels. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5192-5201, 2021b.
Yu Yao, Tongliang Liu, Bo Han. Mingming Gong, Jiankang Deng, Gang Niu, and Masashi Sugiyama. Dual Reducing estimation error for transition matrix label-noise learning. In Advances in neural information processing systems, pp. 7260-7271, 2020.
LIN Yong, Shengyu Zhu, Lu Tan, and Peng Cui. Zin: When and how to learn invariance without environment partition? Advances in Neural Information Processing Systems, 2022.
Yivan Zhang, Gang Niu, and Masashi Sugiyama. Learning noise transition matrix from only noisy labels via total variation regularization. In International Conference on Machine Learning. pp- 12501-12512. 12. PMLR, 2021.
Zhilu Zhang and Mert Sabuncu. Generalized cross entropy loss for training deep neural networks with noisy labels. Advances in neural information processing systems, 31, 2018.
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. arXiv preprini S0t1:22006.59222 2020.
Xiao Zhou, Yong Lin, Renjie Pi, Weizhong Zhang, Renzhe Xu, Peng Cui, and Tong Zhang. Model agnostic sample reweighting for out-of-distribution learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.). Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 27203 27221. PMLR, 17-23 Jul 2022a. URL hotps: : battps://proceeeeeeeeee http////pceeeeeeeeeeeeeee mlr. press/vil 62 zhou22d. html.
13

---

Published as a conference paper at ICLR 2023
Xiao Zhou, Yong Lin, Weizhong Zhang, and Tong Zhang. Sparse invariant risk minimization. In International Conference on Machine Learning, pp. 27222-27244. PMLR, 2022b.
Xiao Zhou, Renjie Pi, Weizhong Zhang, Yong Lin, Zonghao Chen, and Tong Zhang. Probabilistic bilevel coreset selection. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pp. 27287-27300 PMLR, m.l..press / zhou22h html.
17-23 Jul 2022c. URL https: : http///ooeedigggee
Xiong Zhou, Xianming Liu, Junjun Jiang. Xin Gao, and Xiangyang Ji. Asymmetric loss functions for learning with noisy labels. In International conference machine learning, pp. 12846 12856. PMLR, 2021.
Zhaowei Zhu, Tongliang Liu, and Yang Liu. A second-order approach to learning with instance- dependent label noise. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 10113-10123, 2021.
A PROOFS
A.1 INTRODUCTION OF EXISTING METHODS
In Section 2, show that the framework MEGO takes anchor-based and anchor-free (the minimum volume method) methods as special cases. In this section, we briefly introduce the anchor-based method (Patrini et al., 2017; Liu & Tao, 2015) and the minimum volume method Li et al. (2021) for completeness. Here we assume that the fitted posterior g(x) matches the noisy posterior, e.g., ((x) = X = æ). for all æ.
The anchor-basee based method. For each class j E [K]. anchor- based methods assumes that there exists an anchor point T with P(Y B)) = el. Anchor based method first find the most confident sample for each class:
n² arg max [i])
where [i] is the probability of the class j of the sample æ given by ā(x).. By the anchor point assumption, we have
T- Te' = TP(Y = x²) 7 (²)),
(10)
where T. is the jth column of T. By repeating equation 9 and equation 10 for each class, anchor points methods obtain the estimation of the whole T.
The anchor-based method (the minimum volume method). Since the posterior g(x) = TP(Y|X = æ;), then ğ(z) is enclosed in the convex hull formed by the columns of T. How- ever, there are still infinite number of T whose conv(T') encloses all the samples. When the samples sufficiently scattered, Li et al. (2021) shows that T is the one with the minimum volume. So the solve the following problem:
min vol(T) TET
(11)
8.1. fo(x)) = ī(xx), Var,
(12)
where vol(T) is the volume of T.
A.2 THE CONDITIONS FOR THE ROBUST LOSSES
The robust losses can work well (i.e., equation holds) when the noise ratio not too large. As shown in the Theorem of Wang et al. (2019), we need the noise ratio to satisfy the following condition:
Condition 1 (Restate of Theorem in Wang et al. (2019)). equation 6 holds 1) under symmetric or uniform label noise if noise rate 1) < 1/ K. where K the class number; 2) under asymmetric or class-dependent label noise when noise rate Qyk Tly with Ekep 1ykk Tl
14

---

Published as a conference paper at ICLR 2023
A.3 THE CONDITIONS FOR THE CONSISTENCY OF FORWARD CORRECTION METHOD
The conditions of forward correction is presented in the Section 4.2 of Patrini et al. (2017). We discuss these conditions briefly in this section for completeness. Recall the risk on dataset ((n) is C(6, D(n)) == 1/4 ((a.y)e((o) (z), (2),,)) y)] where is the loss function. We discuss the cross entropy loss as E in this section since we focus on classification tasks. Here we consider the loss function l endowed with a link function 6: A AK-1- + RK, where K is the class number. In the case of cross entropy, the softmax is the inverse link function, i.e.
fo(x) - (ha))> (ha(x)) ((Fo(z) v) (ho((())))
The first condition is that the function space parameterized by 0 is large enough, i.e. Condition 2. The function class is sufficiently large such that there exists 6 and for (x) Flylz].
Notably, by the universal approximation property of neural networks (Scarselli & Tsoi, 1998), Con- dition 2 can be satisfied by using a deep and wide neural network. In this work, we use Lenet for MNIST dataset, R for CIFARIO and LIFARIO-N, ResNet34 for for CIFAR 100 and CIFAR 100-N, and ResNet50 for Clothing IM (the same with existing works). The second condition condition that the composite losses are proper as follows:
Condition 3. Suppose Condition 2 holds, the composite loss is proper as follows.
arg min (o(h)(x), v) o(p(y)z)) bg
Notably, cross entropy and square loss are examples of proper composite losses.
Theorem 2 of Patrini et al. (2017) shows that if Condition 2 and 3 hold, minimizing the forward correction loss on the noisy data leads to the optimal function which minimizes the loss on the clean data.
A.4 ASSUMPTIONS AND PROOF OF PROPOSITION
Assumption 3. Assume the follows are true:
(a) There exists label noise that is constant level, i.e.
max (1 - Twa) 2 C 2(1).
[E|K]
(b) Let μ denotes the Lebesgue measure, for any Tı. T. E V if Conv(Ti) y Conv(T2), then M(T2) - M(Ti) 2 M(((Conv(TT) \ (on)(T2)))
(c) MfT(TT) > M(T2), then
- 2 ((M(Ti) - M(T)).
(d) g(x') does not lies in the boundary of Conv(T) such that g(x') ΣK only and < ag 1,
The first assumption is natural for noisy data problems that the noise ratio is larger than 0. The intuition for the Assumption 3(b) that the difference in metric should be the same order with the difference in the measure of the convex hulls. For example, if Conv is larger than Conv(T2) one by a constant level in Lebesgue measure, the metric of Ti is also larger than that of T3 by a constant level. The Assumption 3(c) requires that if two matrix Ti and T2 is different in terms of the measure M, there should be difference between their elements, which is captured by the Frobenius norm. One can easily check these assumptions holds for anchor points and minimum volume methods illustrated in Example and 2. The Assumption 3(d) also a mild assumption because holds almost surely.
15

---

Published as a conference paper at ICLR 2023
Proof. Denote uy vector with 1 at the kth index and 0 at the other index, i.e.,
Uk {0,
1 if k;
0, otherwise
Let
T-MGO0 ;= arg min M(V), s.t. (m) C Conv(V),
VEV
and
TIMEOO E,
==
arg min M(V), s.t. g c) C Conv(V).
VEV
Under the assumptions of anchor points Patrini et al. (2017) or sufficiently scattered Li et al. (2021),
T-MGEO T.
(13)
Take j = arg min, T. and Ej = -9(x') + ej. In this case, we claim
Te Tey where To Ce,,te..ee...t tx] This is because 1) we have g(n, c) C Conv(Te,) because ((n) C
(14)
Conv and ge, E Conv (Te,) 2) One can easily check Conv tz..tt e,]) =
Conv(Tag) (Ty)) and Conv([L,, (2...lj..(xxee)) hull that contains both Conv([t), (2..l)..((x)) and {ej} in terms of measure M. Further Conv(tt, te..t...t...tt eşl) is the smallest convex hull containing ((n). With Assumption (d)
Conv( (Li, 12... (j..(x))
is the smallest convex
we know Conv (Te,) is the smallest convex hull that contains ((n, c).
Further, given any ag (Th 1]. we can see Ve. a,e, EiTs(( ayt, & Conv(T) for any Σ 93 = 1--aa a and aj 2 O. This is because for all v E Conv(T), vs I Ts but the ith element of Ve, is larger than T. On the other hand, one can easily see that Conv(T) C Conv(Te:). So we have
((Conv(Te.)) \\ (Cnv (T))
2n((v/0 d;e,+ +
Σ
agly, 0s E (Ta,
Σ SE(KTN()
ag = 1 06 02 2 20)
ME
=Ω(1 - Tit),
(15)
Then we have
sup MGEE - MMEO I|:
2 sup ITAOOO T ||:
= _IT,. - -TIIF
2 20(M(Te,,) - M(T))
20 (M(Conv(Te,) \ Conv(T)))
2 22(1 (T;;)
21(
The first inequality is due to taking as ej; the first inequality is due to equation 13 and equation 14; the second inequality is due to Assumption 3 (c); the third inequality is due Assumption 3 (b) and the last inequality is due to equation 15.
A.5 PROOF OF THBOREM
1
Proof. First there exists a T that can induce 6* in the inner loop. This is due the consistency of forward/backward correction: when T T 0(T)) + 0* as - co. Then by Assumption 1, we know Look Cro((fer>) D) < Lroh D), 04 + 0*. As verified in Ghosh et al. (2017); Wang have Loob Se, , D)
al. (2019); Xu al. (2019), fixed constant. We then have Lrob( (f((T.) D) Lov D). 40 + 6*. Finally, we further have VT Losh (O(T*)) < Loos (O(T)) VT # T by Assumption 2.
Loob(fo D) for any 0, where is
16

---

Published as a conference paper at ICLR 2023
A.6 PROOF OF THEOREM 2
Proof. Recall the definition of covering, we can find T; for T in the covering set such that ((0(T)); - ((((T);X,Y)) ( &' x V, then we have:
Loob (TT),)
Cobb (8(T)) D) +
(2N((,,FF) (lo))/))
( D + M
+
2n
In(2N(e, F,
11oo)/0)
(c.) MN
2e
2n
In(2N((e, F,
11x)/8)
(c., M
+
2n
In(2/8)
(2,2N(c, 11oo
((TT))(()),) MV ( + M
+ MV
+
2n
2n
In F, ||- 1lo) + 3c
n
The first and third inequalities are by the definition of c covering, the second inequality is to apply Hoeffding inequality all elements of the covering sets, the forth inequality is due to T is approximated solution on the dataset D the fifth incquality is to apply Hoeffding inequality on T and the last incquality in because N(e, (100) 1.
A.7 PROOF OF PROPOSITION 2
Assumption 4. Assume the first and second derivatives involved have bounded above and the inverse matrices have all positive eigenvalues:
(a) min
8h (fo. D
(P).(T)
Q1 O.
80
8T
('.C(TTo.
(b) mii
2Q2 > 0,
8830
(c)
||
00(T)
112 Q3.
(d)
(Can(Ja. 86
1| 5 Q5.
0 Co DD)
(e)
S Q6
898T
(f)
@k(6,,T.a
1/2 S Q7.
09
(g)
S Qs-
0930
We imediately have
@DCrol DD)) (T)
@fo DD) 020
d
< d
<
00
8T
00
8T
Q
Lemma 1 (Cauchy, Implicit Function Theorem, Theorem of Lorraine et al. (2020)). for some
(0, T) such that f..
O and regularity conditions are satisfied, then surrounding
80
TT
(0', T') there exists a function 0r (T) such that (C(T(..D)
0 and we have
06
(-(T).T
00 (T)
CC D)
82 LL D
8T
0000T
T00T
("")'''
17

---

Published as a conference paper at ICLR 2023
We consider that the noisy posterior perfectly fit the dataset (e) == D'-1 U''' yf +c), which is equivalent to the inaccurate poster Je,x''
0. (T) arg min L(T D=-
C( (z' +
n
n
arg min CoT D 1
(o + +c)) (T
0
1
arg min So, D + k00 T, x! ,))
n
fo.T/o. 80
Because
0, we have
Ok(0c, T, T, ,)
00
AC(T fo.; D
00
OC(T fe.: D
OC fa, D")
ae
00
8 fo. D
10 - 02) + o(0 0.)
0000
Then
00,
(
C.. (c))
8 C(T Dz
08(T)
OT
0T
0000T
TOOT
OT
8 CPT Jo, D
O0 T, ,.) 0000T
8 DPL D
1 10 T, T,'',v's v
(0(T)
0000T
ÖBOT
T00T
0T
8 fo. DM))
((.. T, x... .V. 0 fo, D")
0000
0000T
008T
1
CC DD)
8 L(T S0,
Lo, D
+ o(1nn)
n
0000
800T
1 J o(1/n),
where
8 LL DD)
k²
e) 0 ((T() fo. Dm)
( So. DDn) (
82 CT fo, Dm T08T
=
0000T
00001
800T
0000
By Assumption we have
Q6Qs
Qs
| <
+
Q2
Q2
Then we have
8 L(T DD))
Ok(O,, T, x' v
(0 0z)
8000
00
Then we have the following by omitting the higher order terms:
(fa,, (e))
00
HLab (Jo, DD
1 Ok:(0. T T.
+
00
n
@Cro (fo. D
82 Cnah (fo, D
Ōk(0, T, x' v','''e)
(0. 0) +
+ o(1/n)
00
820
00
18

---

Published as a conference paper at ICLR 2023
And further:
(T.)
8T
00, (T.)
(0.(T)
(8.(T)
T
(
0T
0T
0T
OT
8T
(T)
1
08 T
(T T)
-
J
((1/n)
0T
11
0T
On the other side, we have
Oloo (fa(T). (c))
0T
OLrh (Ja. (c)) (T.)
00
OT
Ocob (fo., 1 (e)) (T.)
00
(f.. D
1 ( +c)) E(T fo('') (2)))())))
(T.)
00
00
OT
DLob (So, D
8 (So. DDm)
0k(0, T, ",,',3',
(0. 10,-0) + n
00
0000T
00
(T)(T)
(T,(T)
x
+
(Te TT) + J o(1/m))
OT
OT
Denote
2 Lob (Se, Dm)
8 L(T Dm
Ok(A., T, r, . I,
K
T0AAT
0000
00
With Assumption 4, we have
Q5Q7 +1
| S
Q2
Recall that
aC (fo, Dz)
00 00(T)
0,
00
OT
then we have following by omitting high order terms:
( Dr)
J dLoo D
0 (T)
1
T
(T.
T)
K
00
00
8T
OT
Then finally have
(T. T)
K (T: - T2
K
dCrs (fo. D²) (T)
K (8
e (fo, Dr
+
0A
8T
ØT
00
K
(fo DD) (T)
TT(T)
CLob Drn)
K
00
8T
ØT
00
K 1
00 (T)
3Lmh (fo. D
K
+
Q1
OT
00
K 1
(1o0l
QsQs
Q6
+ +1)0s + Qs(
+
Q
Q2
Q₂
Q
where Q 1
(209z + 1)Q2 + Qs(
OoQs
+
2a
and Q
Qs are specified in Assumption 4.
19

---

Published as a conference paper at ICLR 2023
A.8 ALGORITHM OF ROBOT
Usually the neural network parameters 0 is of high dimension, and the number of samples in the training dataset Drr is huge, which makes exactly solving the inner problem infeasible. Therefore, in practice, solve the inner problem and the outer problem alternativlyy at each update step to alleviate the computational burden Shu et al. (2019); Ren et al. (2018), We provide detailed explanation of how our ROBOT works in practice.
Forward Correction with Noise Transition Matrix T. With the noise transition matrix T, the procedure one-step update in forward correction method the inner loop can be formulated as:
1 Σ
Oloe fo(
0 =
(16)
30
1=1
where n is the number training samples in a mini-batch, 1 is the learning rate.
Approximately Solving the Inner Problem. Due to the high time complexity for exactly solving ((T) arg min, C(T fe, Drr), previous literature and shown to be effective Shu et al. (2019); Ren et al. (2018). The approximation the H can be formulated follows:
one-step update to approximate it, which is widely used in
Olee (o(.)) vc)
²(T) 6r
(17)
00
Update T the Outer Loop. With the approximate solution from the inner loop, we establish a mapping from T to ( with which we can calculate the gradient of the outer loss w.r.t T. Therefore, the update in the outer loop can be formulated as:
Mr (fōr)) (2:),
T T
(18)
m
8T
Algorithm Algorithm of ROBOT
Require:
Noisy training dataset D.r, noisy validation dataset D.,, batch size n and m, outer update frequeney K, total iterations E.
1: Initialize transition matrix with an identity matrix.
2: for training iteration & 1. do
3: {Iu, yo SampleBatch(D.,nn)
4: (I1,, }r <- SampleBatch(DD..m m)
5: if't K is 0 (# update T once each K iteration.) then
6:
Solve the approximation for inner problem 17 7: Update T by Equation 18
8: end if
9: Update 0 by Equation 16
10: end for
Output: Optimized T and 0*
Discussion about the Algorithm. In practice, the noisy training dataset D., and the noisy val- idation dataset D,, can be the same, which achieves similar performance. Our method is able to scale because the one-step approximation used in our implementation. Besides, the frequency the outer loop updates can be set lower for better efficiency. With these approximation technique, framework can be efficiently trained on large-scale datasets, c.g., Cloth IM with million samples. The overall computational cost is about 1.6 times the cost for regular training M.
A.9 CONVERGENCE OF ROBOT
The convergence of the bilevel optimization using approximated solution of inner loop was first established in Pedregosa (2016). We restate it here for completeness.
20

---

Published as a conference paper at ICLR 2023
Theorem 3 (Convergence, Theorem 3.3 of Pedregosa (2016)). Suppose Luo (fōgr; D) is smooth w.r.t. T, L(T D) is B-smooth and o-strongly convex w.F.t. 0. We solve the inner loop by unrolling steps, choose learning rate in the outer loop as 1/r 1/ VT. then we arrive at a approximately stationary point as follows after R steps:
Thr
Trob Berr
D)
S Só 6 2+1
E
Σ
(19)
Σm=
VR
where Ô absorbs constants and logarithmic terms and (1 a/3)
A.10 IMPLEMENTATION OF ROBUT LOSSES
We provide the details about the robust loss functions used in ROBOT.
Reverse Cross Entropy Loss (RCE)
Lace (fe(f(r,))))))
Σ fx, 0) log (kk)a)
(20)
Mean Absolute Error (MAE)
K Σ lff(()) -(kk>)l
mma (f(x,
(21)
We denote the ground-truth distribution over labels by (kk(z)), and ΣK (A(2z) = 1. Given ground-truth label is y. then ((y[z)) 1 and ((k[z)) = for all # y. For the RCE loss, approximate l0)(0) to constant 10.
A.11 CONVERGENCE OF
In Theorem 2, we provide the uniform convergence of ROBOT in terms of the outer loss. We also able to direct bound the deviation of T from T follows:
Corollary 2. Define (e, llo)). T the same with Theorem 2. Assume Lro (OT)), D) is y-strongly-conve w.r.t T, then with probability at least 8, we have
2E + M In 18
I - 12
TT-
(22)
Proof. By Theorem 2 and the fact T" = arg ming Lob ( D), we have with probability at least 1 the following holds
2 lnn(2N 1oo)/0)
Loo (O(T), s (ooT 2 M
(23)
By the strong convexity, we have
Loob (0(T), 2 Loo (0 T") + ? L T
(24)
By the optimality of T we have
V (Ô(T), D) 0.
(25)
Combining equation 23-25, we know that with probability at least 1 - 8, the following holds:
2 Inn2N 1100)/8)
- T 5e Mv
(26)
n
We finish the proof by rearrangement.
21

---

Published as a conference paper at ICLR 2023
B EXPERIMENTAL DETAILS
B. PLOT DETAILS
We choose 3 classes from MNIST (namely, class 2, 4 and 6), and apply uniform noise with noise rate 0.4. For ease of illustration, we randomly sample 100 points for each class, We first 3-laryer MLP h((=) on the noisy dataset. Then we the Minimum Volume method (Li et al., 2021) to find the minimum T whose (T)v(T) encloses all samples. We then train ROBOT on the same setting. To make fair comparison with minimum volme method, we use h(x) as the soft noisy label for ROBOT to ensure that the noisy posterior for ROBOT cannot be more accurate than the minimum volumn method.
B.2 DATASET DETAILS
CIFARIO-N and CIFAR100-N Wei et al. (2021) is a recently proposed dataset, which was created with the Amazon Mechanical Turk (M-Turk) by posting the CIFAR- 10 and CIFAR- 100 datasets as the annotation Human Intelligence Tasks (HITs). The human annotations are then used as labels for the training data. Clothing IM is a dataset proposed in Xiao al. (2015). The dataset contains million images with noisy labels obtained from the web. We follow the same setting as in Li et al. (2021) and only use the noisy dataset to jointly train both the neural network and the noise transition matrix T.
B.3 EXPERIMENTAL DETAILS
Specifically, we train Lenet with 5 layers for MNIST, SGD with batch size 128, weight decay 10-3 momentum 0.9 and learning rate 10-2 is used to optimize the neural network parameters, while Adam with learning rate 10 and batch size 128 is used to optimize T in the outer loop; for CIFAR1O, we experiment on ResNet18, trained using SGD with batch size 128, weight decay 5 x 10-4 momentum 0.9 and learning rate 5 10-2; for CIFAR100, we experiment on ResNet34, trained using SGD with batch size 128, weight decay 1 x 10-3, momentum 0.9 and learning rate x 10-2, for both CIFARIO and CIFAR Adam with learning rate x 10-3 and batch size 256 is used din the outer loop to train T; for CIFARIO-Y and CIFAR CIFARIOO-N, 100-N, ResNet34 is training using SGD with learning rate 0.1, momentum 0.9 and weight decay x 10 10-4, following the official syper-parameters, while T is optimized using Adam with learning rate 5 10- 33, for Clothing M, we follow Li et al. (2021) to finetune an ImageNet pre-trained ResNet50 using SGD with learning rate 2 10-3, momentum 0.9 and weight decay x 10-3, batch size is set 32.
B.4 BILEVEL FORMULATION LEADS TO EASIER OPTIMIZATION
0.30
0.38
0.06
0.06
0.34
ROBOT
(o-0.))
0.30
One RCE Hr-0.001 Dra-lncee DC2 (kw0.0001)
Figure 2: Comparison RCE loss values on the training dataset achieved by one-level training (directly optimizing the robust loss) and our ROBOT. We can see that directly training the network with RCE leads to difficulty in optimization. On the other hand, ROBOT decreases the training loss quickly since as ROBOT transforms the optimization optimization from the space of neural networks to the space of T).
much smaller space (transform the
22

---

Published as a conference paper at ICLR 2023
We conduct the following two experiments CIFAR100 verify that the bilevel formulation in ROBOT leads to easier optimization of the robust loss function: 1) directly using the reverse cross entropy loss to train the network (referred one-level method in the following discussion); 2) execute the bilevel procedure in our ROBOT (for fair comparison, we use the training dataset for both the inner loop and outer loop in equation 7). In Figure 2, we can see that direct optimizing the robust loss (one level) can hardly decrease the training loss, which is consistent with the findings in Zhang & Sabuneu (2018). On the other hand, the robust training loss optimized the outer loss of ROBOT decreases rapidly.
Implementation Details In ROBOT, we set K = 1 for the algorithm described in Appendix A.8 for ROBOT, which iterate between inner and outer loop by performing one step gradient descent each time, in the inner loop, SGD with momentum 0.9 and learning rate 0.1 is used; in the outer loop, Adam with learning rate 0.001 is used. For directly training the model using the reverse cross entropy loss, we have tried different learning rate ((0.1. 0.01, 0.001, 0.0001)) with Adam optimizer. The learning rate is decayed at 40 and 70 epochs in all runs. For each experiment, we record the value of the reverse cross entropy loss on the training dataset, which is the training loss in the one- level case and is the outer loss in ROBOT, respectively. The results are shown in Figure 2. Each iteration of ROBOT needs two times of gradient evaluations, one for the inner loop and one for the outer loop. Each iteration of direct optimizing robust loss (one-level) needs a single time of gradient evaluation.
B.5 EXPERIMENTS w/wo SEPARATE VALIDATION SET
In the implementation of equation 7 described in Appendix A.8, split the noisy dataset into training and validation dataset. The training dataset used in the inner loop and validation set used for the outer loop. Actually loops (with out splitting it into a training and validation set). We conduct experiments on CIFARIO dataset with 20% and 50% uniform noise to compare these two schemes. Table 6 reports the test performances and estimation error rate. The outer objective adopts RCE loss. Other configurations follow the same settings as the main experiment. Table shows that the two schemes lead similar performance.
also the same noisy dataset for both the inner and outer
Table 6: Comparison between whether using separate validation set in the outer loop.
Method
Noise rate=0.2
Noise 0ate=0.5
Separate Validation
92. 92.13=0.07
88.75 =0.10
No Separate Validation
92.09-10.09
88.63 10.12
C
RELATED WORK
In this section we categorize previous noisy label learning approaches into two types: heuristic methods and statistically consistent methods, and further provide brief introduction.
Heuristic Methods. Due to the empirical observation that the neural networks tend to learn easy (correct) samples first, and then starts to fit onto the hard (corrupt) samples in the later phase of training. many algorithms are designed based on the training samples' loss values (Han et al., 2018; Wei al., 2020; Huang et al., 2019; Pleiss et al., 2020; Yao et al., 2021b). Specifically, the samples with small loss values are presumed to be correctly labelled, while those with large loss values are considered corrupted. Even though these methods demonstrate strong empirical results, they typically lack thcoretical guarantees and hence make their reliability questionable.
Loss Correction Methods. Algorithms belonging to this category attempt to train a statistically consistent classifier under label noise with theoretical guarantees by utilizing the noise transition matrix (T) to correct the loss during training. The majority of previous methods rely on the anchor point assumption, which means there is at least one data belonging each specific class with prob- ability one (Patrini et al., 2017; Xia et al., 2020; Liu & Tao, 2015; Scott, 2015; Scott et al., 2013; Yao al., 2020; Zhu et al., 2021; Wu et al., 2021; Xia et al., 2022; Li et al., 2022b). However, the
23

---

Published as a conference paper at ICLR 2023
anchor point assumptions are unfavorable (Xia et al., 2019). Recently, (Li et al., 2021; Zhang al., 2021) make the attempt to estimate without relying on the anchor point assumption. Even though promising results are achieved, we point out that these methods prone to inaccurate posteriors estimation (Section 2) and suffer unreliable performances especially when training data is scarce (Section 4). In comparison, method overcomes the above mentioned issues and demonstrates superior performances.
Robust Loss Functions. Several noise-robust loss functions are proposed to train the network (Ghosh et al., 2017; Liu & Guo, 2020; Xu et al., 2019; Wang et al., 2019; Ma et al., 2020; Zhou al., 2021; Kim et al., 2021), such that when the number of training data approaches infinity, the optimal weights derived from noisy training data is the same as the weights derived from clean data. Despite they learn a robust classifier in theory, they are typically difficult to train the DNNs and result require more Hyppe-ppramette tuning (Wang et al., 2019). Our method utilizes the robust loss functions to optimize the noise transition matrix T instead of the model parameters, the learnt T is then used to correct the loss during training to learn statistically consistent classifier.
Bilevel Optimization Bilevel optimization Sinha et al. (2017) has achieved a lot of successes in recent years, which is able to solve hicrarchical decision making processes. Bilevel optimization is adopted in broad areas of research, such as hyper-paramter optimization Lorraine et al. (2020); Maclaurin et al. (2015); Pedregosa (2016); MacKay et al. (2019); Franceschi al. (2017); Vicol et al. (2021), neural architecture search Pham al. (2018); Liu et al. (2018); Pham et al. (2018); Shi et al. (2020); Yao et al. (2021a); Gao et al. (2022; 2021); Shi et al. (2021), meta learning Finn et al. (2017); Nichol & Schulman (2018), dataset condensation Wang et al. (2018); Zhao al. (2020); Cazenavette et al. (2022); Pi et al. (2022) and sample re-weighting Ren et al. (2018); Shu et al. (2019); Zhou et al. (2022a;c).
24


Reviews:
[{"review_id": "wz0QRgXWfw", "reviewer": "Reviewer_FXEG", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new method for deep learning with noisy labels. The method is based on the independent noise transition assumption, i.e., the label noise is independent of the input data. Existing methods, either with or without anchors, attempt to find a minimum enclosing convex hull for the noise transition matrix T. However, the authors show that this approach is vulnerable to errors in posterior estimation. To resolve this issue, the authors propose to bypass this problem using a bilevel formulation; Now, we are minimizing a robust loss function that can give the same parameter (theta) for both noisy labels and clean labels, but the parameter itself is defined based on another forward-correction-based optimization problem, where T is the variable. The authors claim that this can also alleviate the difficulty of minimizing the robust loss function directly with theta. The experiments show that the proposed method achieves state-of-the-art results for various benchmark sets.", "summary_of_the_review": "The main idea for bypassing two difficulties (one for robust loss functions, another for vulnerability of the MGEO problem) at once is novel and interesting. However, the justification that the proposed method can alleviate the former difficulty is not clearly given in the paper. The performance is good, which makes the method convincing.\n\n[After rebuttal] I'm satisfied with the authors' answers and maintain the original score.", "strength_and_weaknesses": "The main motivation of the paper is valid, i.e., MGEO methods are vulnerable to errors in posterior estimation. The authors provide this with a proposition, and the main reason for this vulnerability is the strict inequality constraint for the \"enclosing convex hull\" part. The idea for resolving this issue is novel, i.e., combining robust loss functions with the estimation of T in a bilevel formulation. The upper-level problem finds theta (the parameter) based on the robust loss function while the lower-level problem defines theta based on T with a forward-correction-based problem. The authors claim that this kills two birds with one stone in that (i) the difficulty of direct optimization for theta with the robust loss can be alleviated and (ii) the vulnerability of T estimation in MGEO can be bypassed (since now T is determined by the robust loss function through theta). This is quite an interesting approach, and the good performance makes it more convincing.\n\nAlthough the approach is interesting, it seems some of the positive effects of the proposed method are not fully justified. Among the above two advantages, the benefits of (ii) are clear: Now T is not defined based on the strict convex hull inequality constraint, so it is less sensitive to errors in posterior estimation as also shown in Proposition 2. However, (i) is somewhat unclear. The authors argue that reparametrizing theta with T as in (7) will make the optimization of the robust loss function easier, but the exact mechanism for this is not explained. A clear justification is needed for this part.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "b19oX_iqoRN", "reviewer": "Reviewer_5YUk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "To construct the noise probability matrix, existing methods assume that there exists anchor points which belong to a certain class probability one or assume a perfect posterior estimator for the noisy examples. A new transition matrix estimation is proposed that utilizes an alternate optimisation routine of the neural network and the transition matrix parameters. ", "summary_of_the_review": "The paper shows enough theoretical evidence of the method. However, some parts will not be easy to be accessible by non-expert readers. ", "strength_and_weaknesses": "Strength\n\n* The paper is backed by enough theoretical evidence. \n* Results are strong. \n\nWeakness \n\n* In the last sentence in page-5, text(T) was used with out defining the term. \n* If I understood the eq 7 correctly, one needs to optimise the objective and the constraint in an iterative manner.  The neural network parameters are optimised using the noisy training set and the current estimation of the transition matrix. The transition matrix is then updated using the validation set. It is not clear why one would need to divide the set into training and validation and why can not we use the same noisy annotation to estimate both iteratively? \n* The theorem 2 is valid if eq-7 is well solved. I could not find any convergence guarantees of eq-7. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "NrozIbi8SOr", "reviewer": "Reviewer_nwAC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The contributions of this paper are two-fold: firstly, a unifying view of the noise transition matrix is presented which combines both anchor-based and anchor-free methods into a single framework called MEGO which is based on the minimum-volume convex hull. The authors then propose an improved bi-level optimization method called ROBOT which improves the performance of the method in the presence of imperfect posterior estimation. The results show that the method outperforms the baselines by some margin.\n\n", "summary_of_the_review": "Overall, this paper makes a good contribution both in terms of providing a unified view of existing noise transition matrix estimation approaches and proposing a new effective method for dealing with noisy posterior estimation. The only major weakness is there is no evaluation of the significance of the approach on real-world large scale datasets.", "strength_and_weaknesses": "Strengths\n\n1. Handling label noise in deep learning is a significant and practically important problem as it is well-known that obtaining good posteriors from deep learning models is a challenge.  The propsed method is therefore a welcome contribution in this direction.\n\n2. The unified view of anchor-based and anchor-free, MEGO, methods provides some interesting insights into the existing approaches for handling noisy labels and is a good way of summarizing these approaches.\n\n3. The proposed method for overcoming the limitations of MEGO has good theoretical guarantees which are described in great detail in the paper. \n\n4. The empirical results show that the method consistently outperforms existing approaches across a range of datasets. \n\nWeaknesses\n\n1. While the proposed method is quite simple, the paper itself is a bit difficult to read and follow. For example, there is no summary of the approach and some implementation details aren’t mentioned. How is $\\mathcal{L}_{rob}$ computed?\n\n2. The evaluation is on rather small datasets that don’t really have much practical significance in the era of large models. How does the method scale in terms of dataset size and how computationally expensive is the method? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HMc8Yd3MYb", "reviewer": "Reviewer_NebR", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In spite of my efforts I am unable to provide an acceptable review of this paper.", "summary_of_the_review": "In spite of my efforts I am unable to provide an acceptable review of this paper.\n", "strength_and_weaknesses": "In spite of my efforts I am unable to provide an acceptable review of this paper.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "7lJ3odBCtk5", "reviewer": "Reviewer_Ukut", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of estimating instance independent noise transition matrix ($T$), which is utilized in learning with noisy labels. They unify existing methods for $T$ estimation, under a framework called Minimum Geometric Envelope Operator and show that these methods are prone to failing ( they are in-consistent estimators) when the noise posterior estimation is imperfect. To address this issue, they propose a novel T-estimation framework (ROBOT) based bilevel optimization and show that their proposal has nice theoretical properties like identifiably, consistency and finite-sample generalization guarantees. They also argue that unlike the MEGO methods their method doesn't require assumptions on the existence of anchor points. Empirical evaluation on multiple benchmarks shows the superiority of the proposed method. ", "summary_of_the_review": "Overall a good paper. It provides an abstraction and highlights issues with existing methods for estimation of noise transition matrix and also proposes a solution to fix those issues. ", "strength_and_weaknesses": "Strengths:\nThe paper addresses an important problem of learning with noisy labels. Though I am not super familiar with the literature on noise transition matrix estimation, the characterization of existing works under a simple framework (MGEO) seems nice. Then, they highlight the problems with existing works -- anchor point assumptions and in-consistency when noise posterior estimation is imperfect. In addition the paper also gives a new solution to this problem and it is shown that the proposed solution has nice properties like identifiability, consistence and generalization. Empirical evaluation on multiple datasets shows significant improvement over the other baselines. \n\nWeaknesses/Questions:\nCould you please provide some background/preliminaries on the methods that are being put under MGEO? For the readers who are not super familiar with this line of work. I could see a formal statement on the in-consistency of MGEO methods, it is discussed using an example in section 4. Is it possible to have an exact statement on the in-consistency -- even restating previous results could be helpful. In Theorem 2 why are the results in terms of the covering number of $\\mathcal{F}$? Can't the standard generalization error bounds be instantiated here? What is $\\epsilon$ in Theorem 2? Is there a bound on the estimation error of $T$  and do you need any assumptions on the noise level (original $T$) for the method to work? I believe if the noise level is too high then the estimation might be hard, is it true?\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%