Title: PEER LOSS FUNCTIONS: LEARNING FROM NOISY LA-BELS WITHOUT KNOWING NOISE RATES

Abstract: Learning with noisy labels is a common problem in supervised learning. Existing approaches require practitioners to specify noise rates, i.e., a set of parameters controlling the severity of label noises in the problem. The specifications are either assumed to be given or estimated using additional approaches. In this work, we introduce a technique to learn from noisy labels that does not require a priori specification of the noise rates. In particular, we introduce a new family of loss functions that we name as peer loss functions. Our approach then uses a standard empirical risk minimization (ERM) framework with peer loss functions. Peer loss functions associate each training sample with a certain form of "peer" samples, which evaluate a classifier' predictions jointly. We show that, under mild conditions, performing ERM with peer loss functions on the noisy dataset leads to the optimal or a near optimal classifier as if performing ERM over the clean training data, which we do not have access to. To our best knowledge, this is the first result on "learning with noisy labels without knowing noise rates" with theoretical guarantees. We pair our results with an extensive set of experiments, where we compare with state-of-the-art techniques of learning with noisy labels. Our results show that peer loss functions based method consistently outperforms the baseline benchmarks, as well as some recent new results. Peer loss provides a way to simplify model development when facing potentially noisy training labels, and can be promoted as a robust candidate loss function in such situations.

1. INTRODUCTION:

The quality of supervised learning models depends on the training data {(x n , y n )} N n=1 . In practice, label noise can arise due to a host of reasons. For instance, the observed labels ỹn s may represent human observations of a ground truth label. In this case, human annotators may observe the label imperfectly due to differing degrees of expertise or measurement error, see e.g., medical examples such as labeling MRI images from patients. Many prior approaches to this problem in the machine learning literature aim to develop algorithms to learn models that are robust to label noise (Bylander, 1994; Cesa-Bianchi et al., 1999; 2011; Ben-David et al.; Scott et al., 2013; Natarajan et al., 2013; Scott, 2015) . Typical approaches require a priori knowledge of noise rates, i.e., a set of parameters that control the severity of label noise. Working with unknown noise rates is difficult in practice: Often, one must estimate the noise rates from data, which may require additional data collection (Natarajan et al., 2013; Scott, 2015; Van Rooyen et al., 2015) (e.g., be a redundant set of noisy labels for each sample point, or a set of ground truth labels for tuning these parameters) and may introduce estimation error that can affect the final model in less predictable ways. Our main goal is to provide an alternative that does not require the specification of the noise rates, nor an additional estimation step for the noises. This target solution might help when the practitioner does not have access to reliable estimates of the noise rates (e.g., when the training data has limited size for the estimation tasks, or when the training data is already collected in a form that makes the estimation hard to perform).

In this paper, we introduce a new family of loss functions, peer loss functions, to empirical risk minimization (ERM), for a broad class of learning with noisy labels problems. Peer loss functions operate under different noise rates without requiring either a priori knowledge of the embedded noise rates, or an estimation procedure. This family of loss functions builds on approaches developed in the peer prediction literature (Miller et al., 2005; Dasgupta & Ghosh, 2013; Shnayder et al., 2016) , which studies how to elicit information from self-interested agents without verification. Typical approaches in the peer prediction literature design scoring functions to score each reported data using another noisy reference answer, without accessing ground truth information. We borrow this idea and the associated scoring functions via making a connection through treating each classifier's prediction as an agent's private information to be elicited and evaluated, and the noisy label as an imperfect reference from a "noisy label agent". The peer loss takes a form of evaluating classifiers' prediction using noisy labels on both the targeted samples and a particular form of constructed "peer" samples. The evaluation on the constructed peer sample encodes implicitly the information about the noises as well as the underlying true labels, which helps us offset the effects of label noises. The peer sample evaluation returns us a favorable property that expected risk of peer loss turns to be an affine transformation of the true risk of the classifier defined on the clean distribution. In other words, peer loss is invariant to label noises when optimizing with it. This effect helps us get rid of the estimation of noise rates.

The main contributions of this work are:

1. We propose a new family of loss functions that can easily adapt to existing ERM framework that i) is robust to asymmetric label noises with formal theoretical guarantees and ii) requires no prior knowledge or estimation of the noise rates (no need for specifying noise rates). We believe having the second feature above is a non-trivial progress, and it features a promising solution to deploy in an unknown noisy training environment.

2. We present formal results showing that performing ERM with a peer loss function can recover an optimal, or a near optimal classifier f * as if performing ERM on the clean data (Theorem 2, 3, 4).

We also provide analysis for peer loss functions' risk guarantees (Theorem 5 and 7).

3. We present extensive experimental results to validate the usefulness of peer loss (Section 5 and Appendix). This result is encouraging as it is able to remove the long-standing requirement of learning error rates of noises (or estimating transition matrices as used in many relevant papers) before many of the existing methods can be applied. We also provide preliminary results on how peer loss generalizes to multi-class classification problems.

4. We will contribute to the community by publishing our codes and implementations.

1.1. RELATED WORK:

Learning from Noisy Labels Our work fits within a stream of research on learning with noisy labels. A large stream of research on this topic works with the random classification noise (RCN) model, where observed labels are flipped independently with probability e ∈ [0, 1 2 ] (Bylander, 1994; Cesa-Bianchi et al., 1999; 2011; Ben-David et al.) . Recently, learning with asymmetric noisy data (or also referred as class-conditional random classification noise (CCN)) for binary classification problems has been rigorously studied in (Stempfel & Ralaivola, 2009; Scott et al., 2013; Natarajan et al., 2013; Scott, 2015; Van Rooyen et al., 2015; Menon et al., 2015) . For a more thorough survey of classical results on learning with noisy data, please refer to (Frénay & Verleysen, 2014) .

Symmetric loss:

For RCN, where the noise parameters are symmetric, there exists works that show symmetric loss functions (Manwani & Sastry, 2013; Ghosh et al., 2015; 2017; Van Rooyen et al., 2015) are robust to the underlying noises, without specifying the noise rates. It was also shown that under certain conditions, the proposed loss functions are able to handle asymmetric noises. Our focus departs from this line of works, and we will exclusively focus on asymmetric noise setting, and study the possibility of an approach that can ignore the knowledge of noise rates.

Follow-up works (Du Plessis et al., 2013; van Rooyen et al., 2015; Menon et al., 2015; Charoenphakdee et al., 2019) have looked into leveraging symmetric conditions and 0-1 loss with asymmetric noises, and with more evaluation metrics, such as balanced error rate and AUROC. In particular, experimental evidences are reported in (Charoenphakdee et al., 2019) on the importance of symmetricity when learning with noisy labels.

More recent works More recent developments include an importance re-weighting algorithm (Liu & Tao, 2016) , a noisy deep neural network learning setting (Sukhbaatar & Fergus, 2014; Han et al., 2018; Song et al., 2019) , and learning from massive noisy data for image classification (Xiao et al., 2015) , robust cross entropy loss for neural network (Zhang & Sabuncu, 2018) , loss correction (Pa-trini et al., 2017) , among many others. Loss or sample correction has also been studied in the context of learning with unlabeled data with weak supervisions (Lu et al., 2018) . Most of above works either lacks theoretical guarantee of the proposed method against asymmetric noise rates ( (Sukhbaatar & Fergus, 2014; Zhang & Sabuncu, 2018) ), or requires estimating the noise rate (or transition matrix between noisy and true labels, (Liu & Tao, 2016; Xiao et al., 2015; Patrini et al., 2017; Lu et al., 2018) ). A good number of the recent works can be viewed as derivatives or extention of the unbiased surrogate loss function idea introduced in (Natarajan et al., 2013) , therefore they would naturally require the knowledge of the noise rates or transition matrix. We do provide thorough comparisons between peer loss and the unbiased surrogate loss methods.

Mostly relevant to us is a recent work (Xu et al., 2019) that proposes an information theoretical loss (an idea adapted from an earlier theoretical contribution (Kong & Schoenebeck, 2018) ) that is also robust to asymmetric noises rate. We aimed for a simple-to-optimize loss function that can easily adapt to existing ERM solutions. (Xu et al., 2019) involves estimating a joint distribution matrix between classifiers and noisy labels, and then invokes computing a certain information theoretical measure based on this matrix. Therefore, its sample complexity requirement and the sensitivity to noises in this estimation are not entirely clear to us (not provided in the paper either). We do provide calibration guarantees and generalization bounds. We provide conditions when the loss functions are convex. In general, we do think computationally peer loss functions are easy to optimize with, in comparing to information theoretical measures. Experiments comparing with (Xu et al., 2019) are also given in Section 5.

Peer Prediction Our work also builds on the literature for peer prediction (Prelec, 2004; Miller et al., 2005; Witkowski & Parkes, 2012; Radanovic & Faltings, 2013; Witkowski et al., 2013; Dasgupta & Ghosh, 2013; Shnayder et al., 2016; Liu & Chen, 2017) . (Miller et al., 2005) established that strictly proper scoring rule (Gneiting & Raftery, 2007 ) could be adopted to elicit truthful reports from self-interested agents. Follow-up works that have been done to relax the assumptions imposed (Witkowski & Parkes, 2012; Radanovic & Faltings, 2013; Witkowski et al., 2013; Radanovic et al., 2016; Liu & Chen, 2017) . Most relevant to us is (Dasgupta & Ghosh, 2013; Shnayder et al., 2016) where a correlated agreement (CA) type of mechanism was proposed. CA evaluates a report's correlations with another reference agent -its specific form inspired our peer loss.

2. PRELIMINARIES:

Notations and preliminaries: For positive integer n, denote by [n] := {1, 2, ..., n}. Suppose (X, Y ) ∈ X × Y are drawn from a joint distribution D, with their marginal distributions denoted as P X , P Y respectively. We assume X ⊆ R d , and Y = {-1, +1}, that is we consider a binary classification problem. Denote by p := P(Y = +1) ∈ (0, 1). There are N training samples (x 1 , y 1 ), ..., (x N , y N ) drawn i.i.d. from D.

Instead of observing y n s, the learner can only collect a noisy set of training labels ỹn s, generated according to y n s and a certain error rate model, that is we observe a dataset {(x n , ỹn )} N n=1 . We assume a uniform error model for all the training samples we collect, in that errors in ỹn s follow the same error rate model: denoting the random variable for noisy labels as Ỹ and we denote e +1 := P( Ỹ = -1|Y = +1), e -1 := P( Ỹ = +1|Y = -1) such that 0 ≤ e +1 + e -1 < 1. e -1 + e +1 < 1 is not unlike the condition imposed in the existing learning literature (Natarajan et al., 2013) , and it simply implies that the noisy labels are positively correlating with the true labels (informative about the true labels). Label noises are conditional independent from the features, that is the error rate is uniform across x n s: P( Ỹ = y |Y = y) = P( Ỹ = y |X, Y = y), ∀y, y ∈ {-1, +1}. Denote the distribution of the noisy data (X, Ỹ ) as D.

f : X → R is a real-valued decision function, and its risk w.r.t. the 0-1 loss is defined as

E (X,Y )∼D [1(f (X), Y )].

The Bayes optimal classifier f * is the one that minimizes the 0-1 risk:

f * = argmin f E (X,Y )∼D [1(f (X), Y )]

. Denote this optimal risk as R * . Instead of minimizing the above 0-1 risk, the learner often uses a surrogate loss function : R × {-1, +1} → R + , and find a f ∈ F that minimizes the following error: E (X,Y )∼D [ (f (X), Y )]. Denote the following measures:

R D (f ) = E (X,Y )∼D [1(f (X), Y )], R ,D (f ) = E (X,Y )∼D [ (f (X), Y )].

When there is no confusion, we will also short-hand

E (X,Y )∼D [ (f (X), Y )] as E D [ (f (X), Y )].

Using D to denote a dataset collected from distribution D (correspondingly D := {(x n , ỹn )} N n=1 for D), the empirical risk measure for f is defined as R ,D (f ) =1 |D| (x,y)∈D (f (x), y) .

2.1. LEARNING WITH NOISY LABELS:

Typical methods for learning with noisy labels include developing bias removal surrogates loss function methods to learn with noisy data (Natarajan et al., 2013) . For instance, Natarajan et al. (2013) tackle this problem by defining an "un-biased" surrogate loss functions over to help "remove" noise, when e -1 + e +1 < 1: ˜ (t, y) :=

(1-e-y)• (t,y)-ey• (t,-y)

1-e-1-e+1

, ∀t, y. ˜ is identified such that when a prediction is evaluated against a noisy label using this surrogate loss function, the prediction is as if evaluated against the ground-truth label using in expectation. Hence the loss of the prediction is "unbiased", that is ∀ prediction t, E Ỹ |y [ ˜ (t, Ỹ )] = (t, y) [Lemma 1, (Natarajan et al., 2013) ].

One important note to make is most, if not all, existing solutions require the knowledge of error rates e -1 , e +1 . Previous works either assumed the knowledge of it, or needed additional clean labels or redundant noisy labels to estimate them. This becomes the bottleneck of applying these great techniques in practice. Our work is also motivated by the desire to remove this limitation.

2.2. PEER PREDICTION: INFORMATION ELICITATION WITHOUT VERIFICATION:

Peer prediction is a technique developed to truthfully elicit information when there is no ground truth verification. Suppose we are interested in eliciting private observations about a binary event y ∈ {-1, +1} generated according to a random variable Y . There are K agents indexed by [K] . Each of them holds a noisy observation of y, denoted as y(i) ∈ {-1, +1}, i ∈ [K]. We would like to elicit the y(i)s, but they are completely private and we won't observe y to evaluate agents' reports. Denote by r(i) the reported data from each agent i. It is completely possible that r(i) = y(i) if agents are not compensated properly for their information. Results in peer prediction have proposed scoring or reward functions that evaluate an agent's report using the reports of other peer agents. For example, a peer prediction mechanism may reward agent i for her report r(i) using S(r(i), r(j)) where r(j) is the report of a randomly selected reference agent j ∈ [K]\{i}. The scoring function S is designed so that truth-telling is a strict Bayesian Nash Equilibrium (implying other agents truthfully report their y(j)), that is, ∀i E y(j) [S(y(i), y(j))|y(i)] > E y(j) [S(r(i), y(j))|y(i)], ∀r(i) = y(i).

Correlated Agreement (Shnayder et al., 2016; Dasgupta & Ghosh, 2013 ) (CA) is a recently established peer prediction mechanism for a multi-task setting 1 . CA is also the core and the focus of our subsequent sections on developing peer prediction based loss functions. This mechanism builds on a ∆ matrix that captures the stochastic correlation between the two sources of predictions y(i) and y(j). Denote the following mapping function: g(1) = -1, g(2) = +1, ∆ ∈ R 2×2 is then defined as a squared matrix with its entries defined as follows:

∆(k, l) = P y(i) = g(k), y(j) = g(l) -P y(i) = g(k) P y(j) = g(l) , k, l = 1, 2

The intuition of above ∆ matrix is that each (i, j) entry of ∆ captures the marginal correlation between the two predictions. M ∈ R 2×2 is defined as the sign matrix of ∆: M := Sgn(∆), where Sgn(x) = 1, x > 0; Sgn(x) = 0, o.w. Define the following score matrix

EQUATION

where g -1 is the inverse function of g. CA requires each agent i to perform multiple tasks: denote agent i's observations for the N tasks as y 1 (i), ..., y N (i). Ultimately the scoring function S(•) for each task k that is shared between i, j is defined as follows: randomly draw two other tasks

k p 1 , k p 2 , S y k (i), y k (j) :=M S y k (i), y k (j) -M S y k p 1 (i), y k p 2 (j) , k p 1 = k p 2 = k

Note a key difference between the first and second M S terms is that the second term is defined for two independent peer tasks k p 1 , k p 2 (as the reference answers). It was established in (Shnayder et al., 2016) that CA is truthful and proper (Theorem 5.2, Shnayder et al. (2016) .)2 ; in particular, if y(j) is categorical w.r.t. y(i): P(y(j) = y |y(i) = y) < P(y(j) = y ), ∀i, j ∈ [K], y = y then S(•) is strictly truthful (Theorem 4.4, Shnayder et al. (2016) ).

3. LEARNING WITH NOISY DATA: A PEER PREDICTION APPROACH:

In this section, we show that peer prediction scoring functions, when specified properly, will adopt Bayes optimal classifier as their maximizers (or minimizers for the corresponding loss form).

3.1. LEARNING WITH NOISY DATA AS AN ELICITATION PROBLEM:

We first state our problem of learning with noisy labels as a peer prediction problem. The connection is made by firstly rephrasing the two data sources, the classifiers and the noisy labels, from agents' perspective. For a task y ∈ {-1, +1}, say +1 for example, denote the noisy labels Ỹ as r(X), X ∼ P X|Y =1 . In general, r(X) can be interpreted as the agent that observes ỹ1 , ..., ỹN for a set of randomly drawn feature vectors x 1 , ..., x N : ỹn ∼ r(X). Suppose the agent's observations are defined as follows (similar to the definition of e +1 , e -): P(r(X) = -1|Y = +1) = e +1 , P(r(X) = +1|Y = -1) = e -1 . Denote another agent whose observations "mimic" the Bayes optimal classifier f * . Again denote this optimal classifier agent as r * (X) := f * (X):

P X (r * (X) = -1|Y = +1) = e * +1 , P X (r * (X) = +1|Y = -1) = e * -1

Elicited report as the classifier prediction

Max reward = Min loss:

Reference report as the noisy label

Figure 1: Illustration of our idea. S is the peer prediction function; our peer is to "evaluate" a classifier's prediction using a noisy reference.

Suppose we would like to elicit predictions from the optimal classifier agent r * , while the reports from the noisy label agent r will serve as the reference reports. Both r and r * are randomly assigned a task x, and each of them observes a signal r(x) and r * (x) respectively. Denote the report from agent r * as r * . A scoring function S : R × R → R is called to induce strictly truthfulness if the following fact holds: E X S r * (X), r(X) > E X S r * , r(X) , ∀r * = r * (X). Taking the negative of S(•) (changing a reward score one aims to maximize to a loss to minimize) we also have E X -S r * (X), r(X) < E X -S r * , r(X) , ∀r * = r * (X), implying when taking -S(•) as the loss function, minimizing -S(•) w.r.t. R will return us the Bayes optimal classifier f * . Our idea can be summarized easily using Fig. 1 .

3.2. "PROPER" PEER PREDICTION FUNCTION INDUCED BAYES OPTIMAL CLASSIFIER:

When there is no ambiguity, we will shorthand r(X), r * (X) as r, r * , with keeping in mind that r, r * encode the randomness in X. Suppose S(•) is able to elicit the Bayes optimal classifier f * (agent r * ) using r, we have the following theorem formally:

Theorem 1. f * = argmin f E (X, Ỹ )∼ D -S(f (X), r) .

This proof can be done via showing that any non-optimal Bayes classifier corresponds to a misreporting strategy, thus establishing its non-optimality. We emphasize that it is not super restrictive to have a strictly truthful peer prediction scoring function S. We provide discussions in Appendix.

Theorem 1 provides a conceptual connection and can serve as an anchor point when connecting a peer prediction score function to the problem of learning with noisy labels. So far we have not discussed about a specific form of how we construct a loss function using ideas from peer prediction, and have not mentioned the requirement of knowing the noise rates. We will provide the detail about a particular peer loss in next section, and explain its independence of noise rates.

4. PEER LOSS FUNCTION:

We now present peer loss, a family of loss functions inspired by a particular peer prediction mechanism, the correlated agreement (CA), as presented in Section 2.2. We are going to show that peer loss is able to induce the minimizer of a concept class F, under a broad set of non-restrictive conditions.

In this Section, we do not restrict to Bayes optimal classifiers, nor do we impose any restrictions on the loss functions' elicitation power.

4.1. PREPARATION: EXPLAINING CA IN OUR CLASSIFICATION PROBLEM:

To give a gentle start, we repeat the setting of CA for our classification problem.

∆ and scoring matrix First recall that ∆ ∈ R 2×2 is a squared matrix with entries defined between r * (the f * ) and r (i.e., the noisy labels Ỹ ):

∆(k, l) = P f * (X) = g(k), Ỹ = g(l) -P f * (x) = g(k) P Ỹ = g(l) , k, l = 1, 2

Recall g(•) is simply a mapping function: g(1) = -1, g(2) = +1. ∆ characterizes the "marginal" correlations between the optimal classifier' prediction and the noisy label Ỹ . Then the following scoring matrix M ∈ R n×n , sign matrix of ∆, M := Sgn(∆) is computed.

Example 1. Consider a binary class label case: P(Y = -1) = 0.4, P(Y = +1) = 0.6, the noises in the labels are e -1 = 0.3, e +1 = 0.4 and e * -1 = 0.2, e * +1 = 0.3. Then we have ∆(1, 1) = 0.036, ∆(1, 2) = -0.036, ∆(2, 1) = -0.036, ∆(2, 2) = 0.036. And:

∆ = 0.036 -0.036 -0.036 0.036 ⇒ M = Sgn(∆) = 1 0 0 1 .

Peer samples For each sample (x i , ỹi ), randomly draw another two samples

EQUATION

2 ) as i's peer samples. After pairing x i p 1 with ỹi p 2 (two independent tasks), the scoring function S(•) for each sample point x i is defined as follows: S(f

(x i ), ỹi )) = M S f (x i ), ỹi -M S f (x i p 1 ), ỹi p 2 . Recall M S (•)

is a sign score matrix defined for ∆ (Eqn. (1)). Define loss function ˜ (•) as the negative of S(•):

(Generic Peer Loss) ˜ f (x i ), ỹi := 1 -M S f (x i ), ỹi -1 -M S f (x i p 1 ), ỹi p 2 .

(2)

The first term above evaluates the classifier's prediction on x i using noisy label ỹi , and the second "peer" term defined on two independent tasks i p 1 , i p 2 "punishes" the classifier from overly agreeing with the noisy labels. We will see this effect more clearly. According to Theorem 1, minimizing ˜ (•) is going to find the Bayes optimal classifier, if Ỹ and f * are categorical, which is easily satisfied: Lemma 1. When e -1 + e +1 < 1 and e * -1 + e * +1 < 1, r and r * ( Ỹ and f * ) are categorical.

e * -1 + e * +1 < 1 means that the optimal classifier is at least informative ((Liu & Chen, 2017)) -if otherwise, we can flip the classifier's output to obtain one.

4.2. PEER LOSS:

We need to know Sgn(∆) in order to specify M S and ˜ , which requires certain information about f * and Ỹ . We show that for the cases that the literature is broadly interested in, Sgn(∆) is simply the identify matrix (same condition as stated in Lemma 1): Lemma 2. If e -1 + e +1 < 1, e * -1 + e * +1 < 1, then Sgn(∆) = I 2×2 , i.e., the identity matrix.

This is basically stating that for ∆(k, k), k = 1, 2, f * and Ỹ are positively correlating, so the marginal correlation is positive; while for off-diagonal entries, they are negatively correlating.

Peer loss When Sgn(∆) = I 2×2 , M S (y, y ) = 1 if y = y , and 0 otherwise. ˜ (•) defined in Eqn.

(2) reduces to the following form:

1 peer (f (x i ), ỹi ) = 1(f(x i ), ỹi ) -1(f(x i p 1 ), ỹi p 2 ) (3) To see this, for instance 1 -M S f (x i ) = +1, ỹi = +1 = 1 -M (2, 2) = 1 -1 = 0 = 1(f(x i ) = -1, ỹi = +1).

Replacing 1(•) with any generic loss (•) we define:

(Peer Loss) : peer (f (x i ), ỹi ) = (f (x i ), ỹi ) -(f (x i p 1 ), ỹi p 2 ) (4)

We name above loss as peer loss. This strikingly simple form of peer (f (x i ), ỹi ) implies that knowing e -1 + e +1 < 1, e * -1 + e * +1 < 1 hold is all we need to specify peer .

Why do we not need the knowledge of noise rates explicitly? Both of the terms 1(f(x i ), ỹi ) and 1(f(x i p 1 ), ỹi p 2 ) encoded the knowledge of noise rates implicitly. The carefully constructed form as presented in Eqn. 3 allows peer loss to be invariant against noises (Lemma 3, a property we will explain later). For a preview, for example if we take expectation of 1 peer (f (x i ) = +1, ỹi = +1) we

will have E [1 peer (f (x i ) = +1, ỹi = +1)] = P(f (X) = +1, Ỹ = +1) -P(f (X) = +1) • P( Ỹ = +1

), the marginal correlation between f and Ỹ , which is exactly capturing the entries of ∆ defined between f and Ỹ ! The second term above is a product of marginals because of the independence of peer samples i p 1 , i p 2 . Using the sign of ∆ is all we need to recover this information measure in expectation. In other words, both the joint and marginal distribution terms encode the noise rate information in an implicit way. Later we will show this measure is invariant under label noises, which gives us the property of peer loss being invariant to label noises and the ability of dropping the requirement of knowing noise rates. We will instantiate this argument formally with Lemma 3 and establish a link between the above measure and the true risk of a classifier on the clean distribution.

The rest of presentation focuses on peer (Eqn. ( 4)), but peer recovers 1 peer via replacing with 1.

ERM with peer loss f:

* peer = arg min f ∈F R peer , D (f ) = arg min f ∈F 1 N N n=1 peer (f (x n ), ỹn

). Note again that the definition of peer does not require the knowledge of either e +1 , e -1 or e * +1 , e * -1 .

4.3. PROPERTY OF PEER LOSS:

We now present a key property of peer loss, which shows that its risk over the noisy labels is simply an affine transformation of its true risk on clean data. We denote by E D [ peer (f (X), Y )] the expected peer loss of f when (X, Y ), as well as its peer samples, are drawn i.i.d. from distribution D.

Lemma 3. E D [ peer (f (X), Ỹ )] = (1 -e -1 -e +1 ) • E D [ peer (f (X), Y )].

The above Lemma states that peer loss is invariant to label noises in expectation. We have also empirically observed this effect in our experiment. Therefore minimizing it over noisy labels is equivalent to minimizing over the true distribution. The Theorems below establish the connection between E D [ peer (f (X), Y )], the expected peer loss over clean data, with the true risk: Denote

f * 1peer = arg min f ∈F R 1peer, D (f ).

With Lemma 3, we can easily prove the following:

Theorem 2. [Optimality guarantee with equal prior] When p = 0.5, f * 1peer ∈ arg min f ∈F R D (f ).

The above theorem states that for a class-balanced dataset with p = 0.5, peer loss induces the same minimizer as the one that minimizes the 0-1 loss on the clean data. Removing the constraint of 

F, i.e., f * 1peer = arg min f R 1peer, D (f ) ⇒ f * 1peer = f * .

-|∆p| . Then |R D ( f * 1peer ) -min f ∈F R D (f )| ≤ 2 ( ¯ -), ∀ ≤ |∆ p |/2

, if is bounded with ¯ , denoting its max and min.

Condition (1) is a well-adopted assumption in the literature of learning with noisy labels. When e +1 , e -1 > e, we have conditions ( 2 When |∆ p | is small, i.e., p is closer to 0.5, this condition becomes weaker, as we will afford to have a small but also a small e.

Multi-class extension Our results in this section are largely generalizable to multi-class setting. Suppose we have K classes of labels, denoting as {1, 2, ..., K}. We denote by Q a transition matrix that characterizes the relationships between noisy label Ỹ and the true label Y . The (i, j) entry of Q is defined as Q ij = P( Ỹ = j|Y = i). We write Q ij = q ij . For many classes of noise matrices, the M (•) matrix is simply a diagonal matrix. Consider the following case: suppose the noisy labels have uniform probability of flipping to a wrong class, that is, we pose the following conditions: q ij = q ik , for all j = k = i. This condition allows us to define K new quantities e i = q ij for all i = j, and q ii = 1j =i e j . We show that M (•) is a diagonal matrix when K j=1 e j < 1, a similar condition as e -1 + e +1 < 1. Adapting from our proof for Lemma 3, we also have (derivation provided in Appendix)

E D [1 peer (f (X), Ỹ )] = (1 - K j=1 e j ) • E D [1 peer (f (X), Y )].

The above again will help us reach the conclusion that minimizing peer loss leads to the same minimizer on the clean data. We provide experiment results for peer loss with multi-class labels in Section 5.

4.4. α-WEIGHTED PEER LOSS:

We take a further look at the case with p = 0.5. Denote by R +1 (f ) = P(f (X) = -1|y = +1), R -1 (f ) = P(f (X) = +1|y = -1). It is easy to prove:

Lemma 4. Minimizing E[1 peer (f (X), Ỹ )] is equivalent to minimizing R -1 (f ) + R +1 (f ). However, minimizing the true risk R D (f ) is equivalent to minimizing p•R +1 (f )+(1-p)•R -1 (f ), a weighted sum of R +1 (f ) and R -1 (f ).

The above observation and the failure to reproduce the strong theoretical guarantee when p = 0.5 motivated us to study a α-weighted version of peer loss, to make it robust to the case p = 0.5. We propose the following α-weighted peer loss via adding a weight α ≥ 0 to the second term, the peer term:

EQUATION

Denote 1 α-peer as α-peer when replacing with 1, f * 1α-peer = arg min f ∈F R 1α-peer, D (f ) as the optimal classifier under 1 α-peer , and ∆ p = P( Ỹ = +1) -P( Ỹ = -1). Then we have:

Theorem 4. Let α = 1 -(1 -e -1 -e +1 ) • ∆p ∆p . Then f * 1α-peer ∈ arg min f ∈F R D (f ). Denote α * := 1 -(1 -e -1 -e +1 ) • ∆p ∆p .

Several remarks follow: (1) When p = 0.5, we have α * = 1, we recover the earlier definition of peer . ( 2) When e -1 = e +1 , α * = 0, we recover for the clean learning setting. (3) When the signs of P(Y = 1) -P(Y = -1) and P( Ỹ = 1) -P( Ỹ = -1) are the same, α * < 1. Otherwise, α * > 1. In other words, when the noise changes the relative quantitative relationship of P(Y = 1) and P(Y = -1), α * > 1 and vice versa. (4) Knowing α * requires certain knowledge of e +1 , e -1 when p = 0.5. Though we do not claim this knowledge, this result implies tuning α * (using validation data) may improve the performance.

Theorem 2 and 4 imply that performing ERM with 1 α * -peer : f * 1 α * -peer = arg min f R1 α * -peer , D (f ) will lead to a classifier converging to f * :

Theorem 5. With probability at least 1 -δ, R D ( f * 1 α * -peer ) -R * ≤ 2(1+α * )

1-e-1-e+1 log 2/δ 2N .

4.5. CALIBRATION AND GENERALIZATION:

So far our results focused on minimizing 0-1 losses, which is hard in practice. We provide evidences of peer 's, and α-peer 's in general, calibration and convexity with a generic and differentiable calibrated loss. We consider a that is classification calibrated, convex and L-Liptchitz.

Classification calibration describes the property that the convergence to optimality using a loss function would also guarantee the convergence to optimality with 0-1 loss: Definition 1. is classification calibrated if there ∃ a convex, invertible, nondecreasing transformation Ψ with

Ψ (0) = 0 s.t. Ψ (R D ( f ) -R * ) ≤ R ,D ( f ) -min f R ,D (f ).

Denote f * ∈ arg min f R ,D (f ). Below we provide sufficient conditions for α-peer to be calibrated. Theorem 6. α-peer is classification calibrated when either of the following two conditions holds:

(1) α = 1 (i.e., α-peer = peer ), p = 0.5, and f * satisfies the following:

E[ (f * (X), -Y )] ≥ E[ (f (X), -Y )], ∀f.

(2) α < 1, max{e +1 , e -1 } < 0.5, and (t, y) = (t, -y).

(1) states that f * not only achieves the smallest risk over (X, Y ) but also performs the worst on the "opposite" distribution with flipped labels (X, -Y ).

(2) (t, y) = (t, -y) is satisfied by some common loss function, such as square losses and logistic losses, as noted in (Natarajan et al., 2013) , Under the calibration condition, and denote the corresponding calibration function for α-peer as Ψ α-peer . Denote by f *

α-peer = arg min f ∈F R α-peer, D (f ) := 1 N N n=1 α-peer (f (x n ), ỹn ).

We have the following generalization bound: Theorem 7. The following generalization bound holds for α * -peer with probability at least 1 -δ:

RD( f * α * -peer ) -R * ≤ 1 1 -e-1 -e+1 • Ψ -1 α * -peer min f ∈F R α * -peer , D (f ) -min f R α * -peer , D (f ) + 2(1 + α * )L • (F) + 2 log 4/δ 2N 1 + (1 + α * )( ¯ -) ,

where (F) is Rademacher complexity of F.

Convexity In experiments, we use neural networks which are more robust to non-convex loss functions. We provide sufficient conditions for R α-peer, D (f ) to be convex in Appendix (Lemma 8).

5. EXPERIMENTS:

We implemented a two-layer ReLU Multi-Layer Perceptron (MLP) for classification tasks on 10 UCI Benchmarks and applied our peer loss to update their parameters. We show the robustness of peer loss with increasing rates of label noises on 10 real-world datasets. We compare the performance of our peer loss based method with surrogate loss method (Natarajan et al., 2013) (unbiased loss correction with known error rates), symmetric loss method (Ghosh et al., 2015) , DMI (Xu et al., 2019) , C-SVM (Liu et al., 2003) and PAM (Khardon & Wachman, 2007) , which are state-of-the-art methods for dealing with random binary-classification noises, as well as a neural network solution with binary cross entropy loss (NN). We use a cross-validation set to tune the parameters specific to the algorithms. For surrogate loss, we use the true error rates e -1 and e +1 instead of learning them on the validation set. Thus, surrogate loss could be considered a favored and advantaged baseline method. Accuracy of a classification algorithm is defined as the fraction of examples in the test set classified correctly with respect to the clean and true label. For given noise rates e +1 and e -1 , labels of the training data are flipped accordingly. 1 . A full table with all details can be found in Appendix. Equalized Prior means that we pre-sample the dataset to guarantee p = 0.5. For this case we used peer without α (or rather α = 1 as in α-peer ). For p = 0.5, we use validation dataset (using noisy labels) to tune α. Our method is competitive across all datasets and is even able to outperform the surrogate loss method with access to the true error rates in a number of datasets, as well as symmetric loss functions (which does not require the knowledge of noise rates when error rates are symmetric) and the recently proposed information theoretical loss (Xu et al., 2019) . Fig. 2 shows that our method can prevent over-fitting when facing noisy labels. 

Preliminary results on multi-class classification:

We now provide some preliminary results on CIFAR-10 in Table 2 . We followed the setup in (Xu et al., 2019) and used ResNet (He et al., 2016) as the underlying optimization solution. However, different from (Xu et al., 2019) whose noise only exists between specific class pairs, our noise is universal. For each class, we flip the label to any other label with a probability of /9, where is the error rate and 9 is the number of other classes. We do show peer loss is competitive against Cross Entropy and DMI (Xu et al., 2019) . More results and complete details are available in the Appendix.

Conclusion:

This paper introduces peer loss, a family of loss functions that enables training a classifier over noisy labels, but without using explicit knowledge of the noise rates of labels. We provide both theoretical justifications and extensive experimental evidences. 

ILLUSTRATION OF OUR IMPLEMENTATION OF PEER LOSS:



OTHER PEER PREDICTION FUNCTIONS:

Other notable examples include quadratic and logarithmic scoring function, defined as follows: Example 2. Quadratic scoring function:

S r(i), r(j) := 2P y(j) = r(j)|y(i) = r(i) - s∈{-1,+1} P y(j) = s|y(i) = r(i) 2 ,

Example 3. Logarithmic scoring function:

S r(i), r(j) := log P y(j) = r(j)|y(i) = r(i) .

We know the following is true: Lemma 5 (Miller et al. (2005) ). S defined in Example 1 & 2 induce strict truthfulness when y(i) and y(j) are stochastically relevant.

with defining stochastic relevance as follows: Definition 2. y(i) and y(j) are stochastically relevant if ∃ s ∈ {-1, +1} s.t.

P y(j) = s|y(i) = +1 = P y(j) = s|y(i) = -1 .

Similarly we conclude that when r and r * are stochastic relevant, the correlated agreement scoring rule, quadratic scoring rule and logarithmic scoring rule are strictly truthful. This stochastic relevance condition essentially states that the optimal classifier is statistically different from the noisy data source r on some signals. Stochastic relevance is further satisfied in the binary classification setting when e * -1 + e * +1 = 1, under the assumption that e -1 + e +1 < 1, as similarly imposed in learning with noisy labels literature (Scott et al., 2013; Natarajan et al., 2013; Scott, 2015) . Lemma 6. r and r * are stochastically relevant if and only if e * -1 + e * +1 = 1.

Proof. Since r * can be written as a function of X and Y , due to conditional independence between r and X (conditional on Y ), by chain rule

P(r * = -1, r = +1) = P(Y = +1)(1 -e +1 )e * +1 + P(Y = -1)e -1 • (1 -e * -1 ) Since P(r = +1) = P(Y = +1)(1 -e +1 ) + P(Y = -1) • e -1 P(r * = +1) = P(Y = +1)(1 -e * +1 ) + P(Y = -1) • e * -1

We have

EQUATION

For the binary signal case, the condition for stochastic relevance writes as follows:

P(r = +1|r * = +1) = P(r = +1|r * = -1) ⇔ P(r = +1, r * = +1) P(r * = +1) = P(r = +1, r * = -1) P(r * = -1) ⇔P(r = +1, r * = +1)P(r * = -1) = P(r = +1, r * = -1)P(r * = +1) ⇔P(r = +1, r * = -1) = P(r = +1) • P(r * = -1) ⇔P(r = +1, r * = -1) = P(r = +1) • P(r * = -1) ⇔e * -1 + e * +1 = 1,

where the last step is a consequence of Eqn.( 6).

PROOF FOR THEOREM 1

Proof. It is equivalent to prove f * = argmax f E (X, Ỹ )∼ D S(f (X), r) . First S(•)

is able to elicit the Bayes optimal classifier f * (r * ) using r implies that:

E D|Y =+1 S(r * , r) > E D|Y =+1 S r * , r , ∀r * = r * E D|Y =-1 S(r * , r) > E D|Y =-1 S(r * , r) , ∀r * = r *

First note that the expected score of a classifier over the data distribution further writes as follows:

E D S(f (X), r) = p • E D|Y =+1 S(f (X), r) + (1 -p) • E D|Y =-1 S(f (X), r]

Denote by f a sub-optimal classifier that disagrees with f * on set X + dis = {x|Y = +1 : f (x) = f * (x)}. By sub-optimality of f we know that := P X (X ∈ X + dis ) > 0, as a zero measure X + dis does not affect its optimality. Construct the following reporting strategy that r * = r * , w.p. 1 --r * , w.p.

Not hard to check that

E D|Y =+1 S(f (X), r) = E D|Y =+1 S(r * , r)

Yet we have the following fact that

EQUATION

where the inequality is due to strict truthfulness of S and the fact that > 0. We similarly conclude that

EQUATION

Combine Eqn. ( 7) and ( 8) we conclude the proof. +1 -e * -1 ) >0 when 1 -e +1 -e -1 > 0, 1 -e * +1 -e * -1 > 0. Interestingly this coincides with the condition imposed in (Natarajan et al., 2013) . Similarly we can prove that P(r * = +1, r = -1) -P(r * = +1)P(r = -1) = -P(Y = +1)P(Y = -1)(1 -e +1 -e -1 )(1 -e * +1 -e * -1 ) <0

The other entries for P(r * = -1, r = -1) -P(r * = -1)P(r = -1) and P(r * = -1, r = +1) -P(r * = -1)P(r = +1) are symmetric. Therefore the sign matrix of above score matrix is exactly the diagonal matrix.

PROOF FOR LEMMA 3:

Proof. We denote by X i p 1 , Ỹi p 2 the random variable corresponding to the peer samples

x i p 1 , ỹi p 2 . First we have E[ peer (f (X), Ỹ )] = E[ (f (X), Ỹ )] -E[ (f (X i p 1 ), Ỹi p 2 )

] Consider the two terms on the RHS separately.

E[ (f (X), Ỹ )] =E X,Y =-1 P( Ỹ = -1|Y = -1) • (f (X), -1) + P( Ỹ = +1|Y = -1) • (f (X), +1) + E X,Y =+1 P( Ỹ = +1|Y = +1) • (f (X), +1) + P( Ỹ = -1|Y = +1) • (f (X), -1) =E X,Y =-1 (1 -e -1 ) • (f (X), -1) + e -1 • (f (X), +1) + E X,Y =+1 (1 -e +1 ) • (f (X), +1) + e +1 • (f (X), -1) =E X,Y =-1 (1 -e -1 -e +1 ) • (f (X), -1) + e +1 • (f (X), -1) + e -1 • (f (X), +1) + E X,Y =+1 (1 -e -1 -e +1 ) • (f (X), +1) + e -1 • (f (X), +1) + e +1 • (f (X), -1) =(1 -e -1 -e +1 ) • E X,Y (f (X), y) + E X e +1 • (f (X), -1) + e -1 • (f (X), +1)

And consider the second term:

E[ (f (X i p 1 ), Ỹi p 2 )] =E X [ (f (X), -1)] • P( Ỹ = -1) + E X [ (f (X), +1)] • P( Ỹ = +1) =E X (e +1 p + (1 -e -1 )(1 -p)) • (f (X), -1) + ((1 -e +1 )p + e -1 (1 -p)) • (f (X), +1) =E X (1 -e -1 -e +1 )(1 -p) • (f (X), -1) + (1 -e -1 -e +1 )p • (f (X), +1) + E X (e +1 p + e +1 (1 -p)) • (f (X), -1) + (e -1 (1 -p) + e -1 p) • (f (X), +1) =(1 -e -1 -e +1 ) • E X [ (f (X j ), Ỹk )] + E X e +1 • (f (X), -1) + e -1 • (f (X), +1) Thus, E[ peer (f (X), Ỹ )] = E[ (f (X), Ỹ )] -E[ (f (X j ), Ỹk )] = (1 -e -1 -e +1 ) • E[ peer (f (X), Y )]

Multi-class extension Notice the following facts:

E[1(f (X), Ỹ )] -E[1(f (X i p 1 ), Ỹi p 2 )] = P(1(f (X) = Ỹ )) -P(f (X i p 1 ) = Ỹi p 2 ) and K k=1 P(Y = k)q jk = P(Y = j)(1 - k =j e k ) + (1 -P(Y = j))e j = (1 - k e k )P(Y = j) + e j P(1(f (X) = Ỹ )) = K k=1 P(Y = k) K j=1 P(f (X) = j|Y = k)q jk = K j=1 K k=1 P(f (X) = j|Y = k)P(Y = k)q jk = K j=1 P(f (X) = j|Y = j)P(Y = j)(1 - k =j e k ) + K j=1 k =j P(f (X) = j|Y = k)P(Y = k)e j = K j=1 P(f (X) = j|Y = j)P(Y = j)(1 - k =j e k ) + K j=1 e j (P(f (X) = j) -P(f (X) = j|Y = j)P(Y = j)) =(1 - k e k ) K j=1 P(f (X) = j|Y = j)P(Y = j) + K j=1 e j P(f (X) = j)

PROOF FOR THEOREM 3:

Proof. Our proof is inspired by our argument for p = 0.5. We ask the following question: if it is possible to show that Ỹ corresponds an error-flipped distribution of another distribution Ŷ whose marginals pY is close to or equal to 0.5. Observe the following: randomly flipping Y with probability e uniformly, we will have a new distribution of labels Ŷ that satisfies:

pY := P( Ŷ = +1) = P(Y = +1) • (1 -e) + P(Y = -1) • e = p(1 -2e) + e.

Denote by the tolerance of pY : = |p Y -0.5|. When e sets to be: 1 -2e = |∆p| , we have |p Y -0.5| = . The next question we ask: is it possible to find parameters ê-1 , ê+1 :

P( Ỹ = +1| Ŷ = -1) = ê-1 , P( Ỹ = -1| Ŷ = +1) = ê+1 Note that P( Ỹ = -1|Y = +1) =P( Ỹ = -1| Ŷ = +1) • P( Ŷ = +1|Y = +1) + P( Ỹ = -1| Ŷ = -1) • P( Ŷ = -1|Y = +1) =(1 -e) • ê+1 + e • (1 -ê-1 ) Similarly P( Ỹ = +1|Y = -1) = (1 -e) • ê-1 + e • (1 -ê+1 ).

Jointly we need the following equations to hold:

(1 -e) • ê+1 + e • (1 -ê-1 ) = e +1 (1 -e) • ê-1 + e • (1 -ê+1 ) = e -1

Solving above equations we have

ê-1 = (1 -e) • e -1 + e • e +1 1 -2e - e 1 -2e

For a feasible solution to ê-1 , ê+1 , the conditions need to satisfy that (1) ê-1 , ê+1 ≥ 0 and (2) ê-1 + ê+1 < 1. First of all, from (2) we have

e • 1 -(ê -1 + ê+1 ) = e -1 -ê-1 Then a necessary condition for ê-1 + ê+1 < 1 is e -1 -ê-1 > 0 ⇔ e -1 < 1 2 + e -1 2(1 -2e)

This condition holds as long as e -1 , e +1 < 0.5. From ê-1 , ê+1 ≥ 0 we have

EQUATION

This above jointly proves that R α-peer , D (f ) is equivalent to a peer loss defined over the noisy distribution of ŷ with error parameters ê-1 , e +1 .

Denote by f:

EQUATION

Note ∀f :

EQUATION

) Combining Eqn. (10, 12, 13) we have

R D ( f * 1peer ) -R D (f * F ) ≤p Y • E X [ (f (X), +1)] + (1 -pY ) • E X [ (f (X), +1)] -0.5 • E X [ (f (X), +1)] -0.5 • E X [ (f (X), -1)] + ( ¯ -) ≤2 ( ¯ -)

PROOF FOR LEMMA 4

Proof.

E[1 peer (f (X), Ỹ )] =(1 -e -1 -e +1 ) • (P(f (X) = -1, Y = +1) + P(f (X) = +1, Y = -1) -P(f (X) = -1)P(Y = +1) -P(f (X) = +1)P(Y = -1)) =(1 -e -1 -e +1 ) • (pR +1 + (1 -p)R -1 -p • P(f (X) = 1) -(1 -p) • P(f (X) = -1)) =(1 -e -1 -e +1 ) • (pR +1 + (1 -p)R -1 -p • pR +1 + (1 -p)(1 -R -1 ) -(1 -p) • p(1 -R +1 ) + (1 -p)R -1 ) =2(1 -e -1 -e +1 ) • p(1 -p) • (R -1 + R +1 -1) PROOF FOR THEOREM 4 Proof. E[1 α-peer (f (X), Ỹ )] =E[1(f (X), Ỹ )] -α • E[1(f (X i p 1 ), Ỹi p 2 )] =E[1 peer (f (X), Ỹ )] + (1 -α) • E[1(f (X i p 1 ), Ỹi p 2 )] -1 =E[1 peer (f (X), Ỹ )] + (1 -α) • P(f (X) = -1) • P( Ỹ = -1) + P(f (X) = +1) • P( Ỹ = +1) -1 =E[1 peer (f (X), Ỹ )] + (1 -α) • p • (1 -R +1 ) + (1 -p) • R -1 • P( Ỹ = -1) + pR +1 + (1 -p)(1 -R -1 ) • P( Ỹ = +1) -1 =E[1 peer (f (X), Ỹ )] + (1 -α) • (P( Ỹ = +1) -P( Ỹ = -1)) • (pR +1 -(1 -p)R -1 ) + C =2(1 -e -1 -e +1 ) • p(1 -p) • (R -1 + R +1 -1) + (1 -α) • (P( Ỹ = +1) -P( Ỹ = -1)) • pR +1 -(1 -p)R -1 + C =R +1 • 2(1 -e -1 -e +1 ) • p(1 -p) + (1 -α)p • (P( Ỹ = +1) -P( Ỹ = -1)) + R -1 • 2(1 -e -1 -e +1 ) • p(1 -p) -(1 -α)(1 -p) • (P( Ỹ = +1) -P( Ỹ = -1)) + C ,

where C, C are constants: PROOF FOR LEMMA 7

C = (1 -α) • (1 -p) • P( Ỹ = +1) + p • P( Ỹ = -1) -1 C = C -2(1 -e -1 -e +1 ) • p(1 -p) R D ( f * α * -peer ) -R * = 1 1 -e -1 -e +1 R 1 α * -peer , D ( f * α * -peer ) -R 1 α * -peer , D (f * ) (Proposition 8) = 1 1 -e -1 -e +1 R 1 α * -peer , D ( f * α * -peer ) -R 1 α * -peer , D ( f * 1 α * -peer ) (Theorem 3) ≤ 1 1 -e -1 -e +1 Ψ -1 α * -peer min f ∈F R α * -peer , D (f ) -min f R α * -peer , D (f ) (Calibration of 1 α * -peer ) + R α * -peer , D ( f * α * -peer ) -R α * -

Proof. Due to the random sampling, via Hoeffding inequality we first have there exists some pỹn ∈ (0, 1), with probability at least 1 -δ, In above R α-peer , D (f ) = R ϕ, D (f ) because α-peer and share the same expected risk by construction. Plug in the fact that α-peer is linear in and an easy consequence that α-peerα-peer ≤ (1 + α)( ¯ -), let δ := δ/2, we conclude the proof.

PROOF FOR LEMMA 8:

Nonetheless, despite the fact that α-peer (•) is not convex in general, [Lemma 5, (Natarajan et al., 2013) ] informs us that as long as R α-peer , D (f ) is close to some convex function, mirror gradient type of algorithms will converge to a small neighborhood of the optimal point when performing ERM with α-peer . A natural candidate for this convex function is the expectation of R α-peer , D (f ) as R α-peer, D (f ) → R α-peer , D (f ) when N → ∞. Lemma 8. When α < 1, max{e +1 , e -1 } < 0.5, and (t, y) = (t, -y), R α-peer, D (f ) is convex.

Proof. This was proved in the proof for Theorem 6, when proving the classification calibration property of α-peer under condition (2).

EXPERIMENT IMPLEMENTATION DETAILS:

We implemented neural networks (LeCun et al., 2015) for classification on 10 UCI Benchmarks and applied our peer loss to update their parameters. For surrogate loss, we use the true error rates e -1 and e +1 instead of learning them on the validation set. Thus, surrogate loss could be considered a favored and advantaged baseline method. On each benchmark, we use the same hyper-parameters for all neural network based methods. For C-SVM, we fix one of the weights to 1, and tune the other. For PAM, we tune the margin.

RESULTS:

The full experiment results are shown in Table .??. Equalized Prior indicates that in the corresponding experiments, we resample to make sure P(Y = +1) = P(Y = -1) and we fix α = 1 in these experiments. Our method is competitive in all the datasets and even able to outperform the surrogate loss method with access to the true error rates in most of them. C-SVM is also robust when error rates are symmetric, and is competitive in 8 datasets.

From Figure.4, we can see our peer loss can prevent over-fitting, which is also part of the reason of its achieved high robustness across different datasets and error rates.

:

We provide other examples of peer prediction functions in the Appendix.

To be precise, it is an informed truthfulness. We refer interested readers to(Shnayder et al., 2016) for the detailed differences.

Figures and Tables:

In practice we can balance the dataset s.t. p → 0.5. When p = 0.5, denote ∆ p = P(Y = +1) -P(Y = -1), we have the following theorem: Theorem 3. [Approximate optimality guarantee with unequal prior] When p = 0.5, suppose the following conditions hold: (1) e -1 , e +1 < 0.5; (2) (1-e)•e -1 +e•e +1 > e; (3) (1-e)•e +1 +e•e -1 > e, where e := 1 2

) and (3) hold: (1 -e) • e -1 + e • e +1 > (1 -e) • e + e • e = e, (1 -e) • e +1 + e • e -1 > (1 -e) • e + e • e = e.

Figure 2: Accuracy on test set during training

Figure 3: Illustration of peer loss method.

Being categorical means P(r = -y|r * = y) < P(r = -y), y ∈ {-1, +1} which further implies P(r = -y, r * = y) < P(r = -y)P(r * = y), y ∈ {-1, +1} and P(r = y, r * = y) > P(r = y)P(r * = y), y ∈ {-1, +1}.Consider the following factP(r = +1, r * = +1) =P(Y = +1)P(r = +1, r * = +1|Y = +1) + P(Y = -1)P(r = +1, r * = +1|Y = -1) =P(Y = +1)P(r = +1|r * = +1, Y = +1) • P(r * = +1|Y = +1) +P(Y = -1)P(r = +1|r * = +1, Y = -1)• P(r * = +1|Y = -1) Since r * can be written as a function of X and Y , due to conditional independence between r and X (conditional on Y ) we haveP(r = +1|r * = +1, Y = +1) = P(r = +1|Y = +1) = 1 -e +1 , P(r = +1|r * = +1, Y = -1) = P(r = +1|Y = -1) = e -1 Therefore P(r = +1, r * = +1) = P(Y = +1)(1 -e +1 )(1 -e * +1 ) + P(Y = -1) • e -1 •e * -We also have P(r = +1) = P(Y = +1)(1 -e +1 ) + P(Y = -1) • e -1 P(r * = +1) = P(Y = +1)(1 -e * +1 ) + P(Y = -1) • e * -Then we have P(r = +1, r * = +1) -P(r = +1)P(r * = +1) =P(Y = +1)P(Y = -1)(1 -e +1 -e -1 )(1 -e * +1 -e * -1 ) >0 when 1 > e * +1 + e * -1 . PROOF FOR LEMMA 2 Proof. Again recall that P(r * = +1, r = +1) = P(Y = +1)(1 -e +1 )(1 -e * +1 ) + P(Y = -1)e -1 • e * -1 P(r = +1) = P(Y = +1)(1 -e +1 ) + P(Y = -1) • e -1 P(r * = +1) = P(Y = +1)(1 -e * +1 ) + P(Y = -1) • e * -Then we have P(r * = +1, r = +1) -P(r * = +1)P(r = +1) =P(Y = +1)P(Y = -1)(1 -e +1 -e -1 )(1 -e *

peer , D (f * α * -peer ) peer , D (f ) -min f R α * -peer , D (f ) + 2 max f ∈F | R α * -peer , D (f ) -R α * -peer , D (f )| ≤ 1 1 -e -1 -e +1 Ψ -1 α * -peer min f ∈F R α * -peer , D (f ) -min f R α * -peer , D (f ) (Lemma 7) + 2(1 + α * )L • (F) + 2 log 4/δ 2N (1 + α * -peerα * -peer ) ,with probability at least 1 -δ.

x n ), ỹn ) -α • pỹn (f (x n ), ỹn ) -α • (1 -pỹn ) (f (x n ), -ỹ n )) ≤ log 2/δ 2N • ( α-peerα-peer )Define the following loss function:˜ (x n , ỹn ) := (f (x n ), ỹn ) -α • pỹn (f (x n ), ỹn ) -α • 1 -pỹn ) (f (x n ), -ỹ n )Via Rademacher bound on the maximal deviation we have with probability at least 1 -δmax f ∈F R˜ , D (f ) -R ˜ , D (f ) ≤ 2 • ( ˜ • F) + log 1/δ 2N(17)Since is L-Lipschitz, due to the linear combination, ˜ is (1+α)L-Lipschitz. Based on the Lipschitz composition of Rademacher averages, we have( ˜ • F) ≤ (1 + α)L • (F)Therefore, via union bound, we know with probability at least 1 -(f (x n ), ỹn ) -R˜ , D (f ) + R˜ , D (f ) -R α-peer , D (f ) (f (x n ), ỹn ) -R˜ , D (f ) + R˜ , D (f ) -R α-peer , D (f ) ≤ log 2/δ 2N • ( α-peerα-peer ) + | R˜ , D (f ) -R ˜ , D (f ) ≤ log 2/δ 2N • ( α-peerα-peer ) + (1 + α)L • (F) + log 1/δ 2N ≤(1 + α)L • (F) + log 2/δ 2N • 1 + α-peerα-peer

Figure 4: Accuracy on test set during training

Experiment results on 10 UCI Benchmarks (N+, Nare the numbers of positive and negative samples). Surr: surrogate loss method(Natarajan et al., 2013); DMI:(Xu et al., 2019); Symm: symmetric loss method(Ghosh et al., 2015). Entries within 2% from the best in each row are highlighted in bold. All results are averaged across 8 random seeds. Neural-network-based methods (Peer, Surrogate, NN, Symmetric, DMI) use the same hyper-parameters. Full table with complete set of comparisons is in Appendix.

Table content: <table><tr><td>Task</td><td/><td colspan="5">With Prior Equalization p = 0.5</td><td>Without Prior Equalization p = 0.5</td></tr><tr><td>(d, N + , N -)</td><td colspan="2">e -1 , e +1 Peer</td><td colspan="3">Surr Symm DMI</td><td>NN</td><td>Peer</td><td>Surr Symm DMI</td><td>NN</td></tr><tr><td/><td colspan="7">0.1, 0.3 0.977 0.968 0.969 0.974 0.964 0.977 0.968 0.969 0.974 0.964</td></tr><tr><td>Twonorm</td><td colspan="7">0.2, 0.4 0.976 0.919 0.959 0.966 0.911 0.976 0.919 0.959 0.966 0.911</td></tr><tr><td colspan="8">(20,3700,3700) 0.4, 0.4 0.973 0.934 0.958 0.936 0.883 0.973 0.934 0.958 0.936 0.883</td></tr><tr><td/><td colspan="7">0.1, 0.3 0.919 0.878 0.851 0.875 0.811 0.925 0.885 0.868 0.889 0.809</td></tr><tr><td>Splice</td><td colspan="7">0.2, 0.4 0.901 0.832 0.757 0.801 0.714 0.912 0.84 0.782 0.81 0.725</td></tr><tr><td colspan="8">(60,1527,1648) 0.4, 0.4 0.819 0.754 0.657 0.66 0.626 0.822 0.755 0.674 0.647 0.601</td></tr><tr><td/><td colspan="7">0.1, 0.3 0.833 0.78 0.777 0.797 0.756 0.856 0.802 0.803 0.83</td><td>0.75</td></tr><tr><td>Heart</td><td colspan="7">0.2, 0.4 0.812 0.768 0.717 0.788 0.679 0.856 0.758 0.725 0.797 0.693</td></tr><tr><td>(13,165,138)</td><td>0.4, 0.4</td><td colspan="6">0.75 0.729 0.654 0.69 0.595 0.785 0.728 0.686 0.711 0.554</td></tr><tr><td/><td colspan="7">0.1, 0.3 0.745 0.707 0.674 0.72 0.667 0.778 0.75 0.738 0.729 0.727</td></tr><tr><td>Diabetes</td><td colspan="7">0.2, 0.4 0.755 0.681 0.634 0.682 0.596 0.739 0.705 0.695 0.707 0.672</td></tr><tr><td>(8,268,500)</td><td colspan="7">0.4, 0.4 0.719 0.645 0.619 0.637 0.551 0.651 0.685 0.68 0.633 0.583</td></tr><tr><td/><td colspan="7">0.1, 0.3 0.639 0.563 0.507 0.529 0.519 0.727 0.645 0.709 0.666 0.648</td></tr><tr><td>Breast</td><td>0.2, 0.4</td><td colspan="6">0.63 0.534 0.482 0.496 0.538 0.73 0.674 0.666 0.58 0.672</td></tr><tr><td>(9,85,201)</td><td colspan="7">0.4, 0.4 0.596 0.519 0.504 0.526 0.471 0.677 0.628 0.545 0.537 0.529</td></tr><tr><td/><td colspan="7">0.1, 0.3 0.928 0.922 0.924 0.934 0.873 0.956 0.949 0.943 0.954 0.92</td></tr><tr><td>Breast</td><td>0.2, 0.4</td><td colspan="6">0.93 0.885 0.844 0.89 0.844 0.933 0.898 0.898 0.918 0.831</td></tr><tr><td>(30,212,357)</td><td colspan="7">0.4, 0.4 0.928 0.867 0.819 0.746 0.824 0.908 0.839 0.817 0.795 0.673</td></tr><tr><td/><td colspan="7">0.1, 0.3 0.701 0.624 0.614 0.637 0.581 0.68 0.693 0.603 0.605 0.6</td></tr><tr><td>German</td><td colspan="3">0.2, 0.4 0.664 0.59</td><td>0.6</td><td colspan="3">0.618 0.572 0.676 0.681 0.537 0.573 0.535</td></tr><tr><td>(23,300,700)</td><td colspan="7">0.4, 0.4 0.606 0.55 0.573 0.573 0.556 0.654 0.632 0.549 0.611 0.553</td></tr><tr><td/><td>0.1, 0.3</td><td colspan="6">0.89 0.895 0.892 0.856 0.868 0.893 0.898 0.883 0.785 0.863</td></tr><tr><td>Waveform</td><td colspan="7">0.2, 0.4 0.881 0.89 0.828 0.835 0.81 0.884 0.884 0.745 0.761 0.837</td></tr><tr><td colspan="2">(21,1647,3353) 0.4, 0.4</td><td colspan="6">0.87 0.866 0.867 0.773 0.835 0.853 0.852 0.852 0.672 0.828</td></tr><tr><td/><td colspan="3">0.1, 0.3 0.906 0.9</td><td>0.89</td><td colspan="3">0.87 0.909 0.943 0.909 0.897 0.811 0.93</td></tr><tr><td>Thyroid</td><td colspan="7">0.2, 0.4 0.863 0.862 0.85 0.784 0.822 0.905 0.898 0.865 0.759 0.881</td></tr><tr><td>(5,65,150)</td><td colspan="7">0.4, 0.4 0.762 0.738 0.859 0.788 0.764 0.769 0.818 0.876 0.738 0.738</td></tr><tr><td/><td colspan="7">0.1, 0.3 0.856 0.875 0.843 0.896 0.866 0.796 0.835 0.903 0.896 0.878</td></tr><tr><td>Image</td><td colspan="7">0.2, 0.4 0.836 0.862 0.719 0.845 0.832 0.672 0.755 0.722 0.86 0.599</td></tr><tr><td>(18,1320,990)</td><td colspan="7">0.4, 0.4 0.741 0.72 0.788 0.763 0.732 0.806 0.803 0.823 0.762 0.8</td></tr><tr><td/><td/><td colspan="2">Model</td><td colspan="4">Error Rate = 0.2 Error Rate = 0.4</td></tr><tr><td/><td/><td colspan="2">Cross Entropy</td><td/><td>86.67</td><td/><td>82.09</td></tr><tr><td/><td colspan="3">DMI (Xu et al., 2019)</td><td/><td>85.11</td><td/><td>81.67</td></tr><tr><td/><td/><td colspan="2">Peer Loss</td><td/><td>87.72</td><td/><td>83.81</td></tr></table>

Accuracy on CIFAR-10.

Table content: <table/>

Peer review (iclr2020):
The paper studies the label noise problem with the motivation of without estimating the flip rate or transition matrix. This is an interesting direction for dealing with label noise. Most of the previous studies need either estimate the transition matrix or put restrictions on it, e.g., to be symmetric. A very related work to this paper: L_{DMI}: A Novel Information-theoretic Loss Function for Training Deep Nets Robust to Label Noise, where no restrictions have been made on the class-dependent transition matrix and the proposed method does not need to estimate the transition matrix. The authors may need to discuss the paper. The paper is not well-presented. I tried several times to go through the details but failed. The reasons are, e.g., (1) notation is not clear, e.g., R(X). 	ilde{Y}, and R have been abused. (2) Intuitive explanations are limited. (3) Lots of details can be put on the appendix, keeping the main part to have a strong and clear logic. It seems the theories of the paper depends on a very strong assumption, i.e., *Suppose S(.) is able to elicit the Bayes optimal classifier f^**. By quickly go through the proofs in the appendix, it seems there is a strong connection to the paper L_{DMI}. Some claims are strong. In the literature, with a mild assumption, the class-dependent transition matrix can accurately be estimated just from noisy data with theoretical guarantees. There are also methods proposed for this. Estimating class-dependent transition matrix is not a bottleneck. I think the challenge is about how to learn instance-dependent transition matrix. Overall, this is an interesting paper but needs to be improved.