Year: 2019

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.

heading: 1 INTRODUCTION
text: The quality of supervised learning models depends on the training data {(xn, yn)}Nn=1. In practice, label noise can arise due to a host of reasons. For instance, the observed labels ỹns 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.

heading: 1.1 RELATED WORK
text: 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, 12 ] (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 (Fré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.

heading: 2 PRELIMINARIES
text: 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 PX ,PY respectively. We assume X ⊆ Rd, 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 (x1, y1), ..., (xN , yN ) drawn i.i.d. from D. Instead of observing yns, the learner can only collect a noisy set of training labels ỹns, generated according to yns and a certain error rate model, that is we observe a dataset {(xn, ỹn)}Nn=1. We assume a uniform error model for all the training samples we collect, in that errors in ỹns follow the same error rate model: denoting the random variable for noisy labels as Ỹ and we denote e+1 := P(Ỹ = −1|Y = +1), e−1 := P(Ỹ = +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 xns: P(Ỹ = y′|Y = y) = P(Ỹ = y′|X,Y = y),∀y, y′ ∈ {−1,+1}. Denote the distribution of the noisy data (X, Ỹ ) 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∗ = argminf 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:
RD(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 ED[`(f(X), Y )]. Using D to denote a dataset collected from distribution D (correspondingly D̃ := {(xn, ỹn)}Nn=1 for D̃), the empirical risk measure for f is defined as R̂`,D(f) = 1|D| ∑ (x,y)∈D `(f(x), y) .

heading: 2.1 LEARNING WITH NOISY LABELS
text: 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, EỸ |y[˜̀(t, Ỹ )] = `(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.

heading: 2.2 PEER PREDICTION: INFORMATION ELICITATION WITHOUT VERIFICATION
text: 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) 6= 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 Ey(j)[S(y(i), y(j))|y(i)] > Ey(j)[S(r(i), y(j))|y(i)], ∀r(i) 6= 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, ∆ ∈ R2×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 ∈ R2×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
MS : {−1,+1} × {−1,+1} → {0, 1} : MS(y, y′) =: M(g−1(y), g−1(y′)), (1)
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 y1(i), ..., yN (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 kp1 , k p 2 ,
S ( yk(i), yk(j) ) :=MS ( yk(i), yk(j) ) −MS ( ykp1 (i), yk p 2 (j) ) , kp1 6= k p 2 6= k
Note a key difference between the first and second MS terms is that the second term is defined for two independent peer tasks kp1 , k p 2 (as the reference answers). It was established in (Shnayder et al.,
1We provide other examples of peer prediction functions in the Appendix.
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′ 6= y then S(·) is strictly truthful (Theorem 4.4, Shnayder et al. (2016)).

heading: 3 LEARNING WITH NOISY DATA: A PEER PREDICTION APPROACH
text: 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).

heading: 3.1 LEARNING WITH NOISY DATA AS AN ELICITATION PROBLEM
text: 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 Ỹ as r(X), X ∼ PX|Y=1. In general, r(X) can be interpreted as the agent that observes ỹ1, ..., ỹN for a set of randomly drawn feature vectors x1, ..., xN : ỹ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):
PX(r∗(X) = −1|Y = +1) = e∗+1, PX(r∗(X) = +1|Y = −1) = e∗−1
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: EX [ S ( r∗(X), r(X) )] >
EX [ S ( r̃∗, r(X) )] , ∀r̃∗ 6= r∗(X). Taking the negative of S(·) (changing a reward score one aims to maximize to a loss to minimize) we also have EX [ −S ( r∗(X), r(X) )] < EX [ −S (
r̃∗, r(X) )] , ∀r̃∗ 6= 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.

heading: 3.2 “PROPER” PEER PREDICTION FUNCTION INDUCED BAYES OPTIMAL CLASSIFIER
text: 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∗ = argminf E(X,Ỹ )∼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.
2To be precise, it is an informed truthfulness. We refer interested readers to (Shnayder et al., 2016) for the detailed differences.

heading: 4 PEER LOSS FUNCTION
text: 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.

heading: 4.1 PREPARATION: EXPLAINING CA IN OUR CLASSIFICATION PROBLEM
text: To give a gentle start, we repeat the setting of CA for our classification problem.
∆ and scoring matrix First recall that ∆ ∈ R2×2 is a squared matrix with entries defined between r∗ (the f∗) and r (i.e., the noisy labels Ỹ ):
∆(k, l) = P ( f∗(X) = g(k), Ỹ = g(l) ) − P ( f∗(x) = g(k) ) P ( Ỹ = 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 Ỹ . Then the following scoring matrix M ∈ Rn×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 (xi, ỹi), randomly draw another two samples (xip1 , ỹip1 ), (xip2 , ỹip2 ) such that ip1 6= i p 2 and i p 1, i p 2 6= i. We will name (xip1 , ỹip1 ), (xip2 , ỹip2 ) as i’s peer samples. After pairing xip1 with ỹip2 (two independent tasks), the scoring function S(·) for each sample point xi is defined as follows: S(f(xi), ỹi)) = MS ( f(xi), ỹi ) −MS ( f(xip1 ), ỹi p 2 ) . Recall MS(·) is a sign score matrix defined for ∆ (Eqn. (1)). Define loss function ˜̀(·) as the negative of S(·):
(Generic Peer Loss) ˜̀ ( f(xi), ỹi ) := ( 1−MS ( f(xi), ỹi )) − ( 1−MS ( f(xip1 ), ỹi p 2 )) . (2)
The first term above evaluates the classifier’s prediction on xi using noisy label ỹi, and the second “peer” term defined on two independent tasks ip1, 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 Ỹ 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∗ (Ỹ 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.

heading: 4.2 PEER LOSS
text: We need to know Sgn(∆) in order to specify MS and ˜̀, which requires certain information about f∗ and Ỹ . 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(∆) = I2×2, i.e., the identity matrix.
This is basically stating that for ∆(k, k), k = 1, 2, f∗ and Ỹ are positively correlating, so the marginal correlation is positive; while for off-diagonal entries, they are negatively correlating.
Peer loss When Sgn(∆) = I2×2, MS(y, y′) = 1 if y = y′, and 0 otherwise. ˜̀(·) defined in Eqn. (2) reduces to the following form:
1peer(f(xi), ỹi) = 1(f(xi), ỹi)− 1(f(xip1 ), ỹip2 ) (3)
To see this, for instance 1−MS ( f(xi) = +1, ỹi = +1 ) = 1−M(2, 2) = 1− 1 = 0 = 1(f(xi) = −1, ỹi = +1). Replacing 1(·) with any generic loss `(·) we define: (Peer Loss) : `peer(f(xi), ỹi) = `(f(xi), ỹi)− `(f(xip1 ), ỹip2 ) (4)
We name above loss as peer loss. This strikingly simple form of `peer(f(xi), ỹ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(xi), ỹi) and 1(f(xip1 ), ỹip2 ) 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 1peer(f(xi) = +1, ỹi = +1) we will have E [1peer(f(xi) = +1, ỹi = +1)] = P(f(X) = +1, Ỹ = +1) − P(f(X) = +1) · P(Ỹ = +1), the marginal correlation between f and Ỹ , which is exactly capturing the entries of ∆ defined between f and Ỹ ! The second term above is a product of marginals because of the independence of peer samples ip1, 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 1peer via replacing ` with 1.
ERM with peer loss f̂∗`peer = arg minf∈F R̂`peer,D̃(f) = arg minf∈F 1 N ∑N n=1 `peer(f(xn), ỹn). Note again that the definition of `peer does not require the knowledge of either e+1, e−1 or e∗+1, e ∗ −1.

heading: 4.3 PROPERTY OF PEER LOSS
text: 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 ED[`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. ED̃[`peer(f(X), Ỹ )] = (1− e−1 − e+1) · ED[`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 ED[`peer(f(X), Y )], the expected peer loss over clean data, with the true risk: Denote f̃∗ 1peer = arg minf∈F R1peer,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 minf∈F RD(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 minf R1peer,D̃(f) ⇒ f̃ ∗ 1peer = f∗. In practice we can balance the dataset s.t. p→ 0.5. When p 6= 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 6= 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 := 12 − |∆p| . Then |RD(f̃ ∗ 1peer
) − minf∈F RD(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) 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. 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 Ỹ and the true label Y . The (i, j) entry of Q is defined as Qij = P(Ỹ = j|Y = i). We write Qij = qij . 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: qij = qik, for all j 6= k 6= i. This condition allows us to define K new quantities ei = qij for all i 6= j, and qii = 1− ∑ j 6=i ej . We show that M(·) is a diagonal matrix when ∑K j=1 ej < 1, a similar condition as e−1 + e+1 < 1. Adapting from our proof for Lemma 3, we also have (derivation provided in Appendix) ED̃[1peer(f(X), Ỹ )] = (1− ∑K j=1 ej) · ED[1peer(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 6= 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[1peer(f(X), Ỹ )] is equivalent to minimizing R−1(f) +R+1(f).
However, minimizing the true riskRD(f) is equivalent to minimizing p·R+1(f)+(1−p)·R−1(f), a weighted sum ofR+1(f) andR−1(f). The above observation and the failure to reproduce the strong theoretical guarantee when p 6= 0.5 motivated us to study a α-weighted version of peer loss, to make it robust to the case p 6= 0.5. We propose the following α-weighted peer loss via adding a weight α ≥ 0 to the second term, the peer term:
(α-Peer Loss) : `α-peer ( f(xi), ỹi ) = `(f(xi), ỹi)− α · `(f(xip1 ), ỹip2 ) (5)
Denote 1α-peer as `α-peer when replacing ` with 1, f̃∗1α-peer = arg minf∈F R1α-peer,D̃(f) as the optimal classifier under 1α-peer, and ∆p̃ = P(Ỹ = +1)− P(Ỹ = −1). Then we have: Theorem 4. Let α = 1− (1− e−1 − e+1) · ∆p∆p̃ . Then f̃ ∗ 1α-peer ∈ arg minf∈F RD(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(Ỹ = 1)−P(Ỹ = −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 6= 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 minf R̂1α∗ -peer,D̃(f) will lead to a classifier converging to f∗:
Theorem 5. With probability at least 1− δ, RD(f̂∗1α∗ -peer)−R ∗ ≤ 2(1+α ∗) 1−e−1−e+1
√ log 2/δ
2N .

heading: 4.5 CALIBRATION AND GENERALIZATION
text: 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. Ψ`(RD(f̃)−R∗) ≤ R`,D(f̃)−minf R`,D(f).
Denote f∗` ∈ arg minf 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 minf∈F R̂`α-peer,D̃(f) := 1 N ∑N n=1 `α-peer(f(xn), ỹ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).

heading: 5 EXPERIMENTS
text: 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.
A subset of the experiment results are shown in Table 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 6= 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.

heading: ILLUSTRATION OF OUR IMPLEMENTATION OF PEER LOSS

heading: OTHER PEER PREDICTION FUNCTIONS
text: 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) ) := logP ( 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 ) 6= 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 6= 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 6= 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
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) (6)
For the binary signal case, the condition for stochastic relevance writes as follows:
P(r = +1|r∗ = +1) 6= P(r = +1|r∗ = −1)
⇔P(r = +1, r ∗ = +1) P(r∗ = +1) 6= P(r = +1, r ∗ = −1) P(r∗ = −1) ⇔P(r = +1, r∗ = +1)P(r∗ = −1) 6= P(r = +1, r∗ = −1)P(r∗ = +1) ⇔P(r = +1, r∗ = −1) 6= P(r = +1) · P(r∗ = −1) ⇔P(r = +1, r∗ = −1) 6= P(r = +1) · P(r∗ = −1) ⇔e∗−1 + e∗+1 6= 1,
where the last step is a consequence of Eqn.(6).

heading: PROOF FOR THEOREM 1
text: Proof. It is equivalent to prove f∗ = argmaxf E(X,Ỹ )∼D̃ [ S(f(X), r) ] . First S(·) is able to elicit the Bayes optimal classifier f∗ (r∗) using r implies that:
ED̃|Y=+1 [ S(r∗, r) ] > ED̃|Y=+1 [ S ( r̃∗, r )] , ∀r̃∗ 6= r∗
ED̃|Y=−1 [ S(r∗, r) ] > ED̃|Y=−1 [ S(r̃∗, r) ] , ∀r̃∗ 6= r∗
First note that the expected score of a classifier over the data distribution further writes as follows: ED̃ [ S(f(X), r) ] = p · ED̃|Y=+1 [ S(f(X), r) ] + (1− p) · ED̃|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) 6= f∗(x)}. By sub-optimality of f ′ we know that := PX(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 ED̃|Y=+1 [ S(f ′(X), r) ] = ED̃|Y=+1 [ S(r̃∗, r) ] Yet we have the following fact that
ED̃|Y=+1 [ S(r̃∗, r) ] =(1− ) · ED̃|Y=+1 [ S(f∗(X), r)
] + · ED̃|Y=+1 [ S(−f∗(X), r)
] <ED̃|Y=+1 [ S(f∗(X), r) ] (7)
where the inequality is due to strict truthfulness of S and the fact that > 0. We similarly conclude that
ED̃|Y=−1 [ S(r̃∗, r) ] < ED̃|Y=−1 [ S(f∗(X), r) ] (8)
Combine Eqn. (7) and (8) we conclude the proof.

heading: PROOF FOR LEMMA 1
text: Proof. 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 fact P(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 have
P(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∗−1 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∗−1 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.

heading: PROOF FOR LEMMA 2
text: 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∗−1
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 > 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.

heading: PROOF FOR LEMMA 3
text: Proof. We denote by Xip1 , Ỹip2 the random variable corresponding to the peer samples xip1 , ỹip2 .
First we have E[`peer(f(X), Ỹ )] = E[`(f(X), Ỹ )]− E[`(f(Xip1 ), Ỹip2 )] Consider the two terms on the RHS separately.
E[`(f(X), Ỹ )] =EX,Y=−1 [ P(Ỹ = −1|Y = −1) · `(f(X),−1) + P(Ỹ = +1|Y = −1) · `(f(X),+1) ] + EX,Y=+1 [ P(Ỹ = +1|Y = +1) · `(f(X),+1) + P(Ỹ = −1|Y = +1) · `(f(X),−1)
] =EX,Y=−1 [ (1− e−1) · `(f(X),−1) + e−1 · `(f(X),+1)
] + EX,Y=+1 [ (1− e+1) · `(f(X),+1) + e+1 · `(f(X),−1)
] =EX,Y=−1 [ (1− e−1 − e+1) · `(f(X),−1) + e+1 · `(f(X),−1) + e−1 · `(f(X),+1)
] + EX,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) · EX,Y [ `(f(X), y) ] + EX [ e+1 · `(f(X),−1) + e−1 · `(f(X),+1)
] And consider the second term:
E[`(f(Xip1 ), Ỹip2 )]
=EX [`(f(X),−1)] · P(Ỹ = −1) + EX [`(f(X),+1)] · P(Ỹ = +1) =EX [ (e+1p+ (1− e−1)(1− p)) · `(f(X),−1) + ((1− e+1)p+ e−1(1− p)) · `(f(X),+1) ] =EX [ (1− e−1 − e+1)(1− p) · `(f(X),−1) + (1− e−1 − e+1)p · `(f(X),+1)
] + EX [ (e+1p+ e+1(1− p)) · `(f(X),−1) + (e−1(1− p) + e−1p) · `(f(X),+1)
] =(1− e−1 − e+1) · EX [`(f(Xj), Ỹk)] + EX [ e+1 · `(f(X),−1) + e−1 · `(f(X),+1)
] Thus, E[`peer(f(X), Ỹ )] = E[`(f(X), Ỹ )]− E[`(f(Xj), Ỹk)] = (1− e−1 − e+1) · E[`peer(f(X), Y )]
Multi-class extension Notice the following facts: E[1(f(X), Ỹ )]− E[1(f(Xip1 ), Ỹip2 )] = P(1(f(X) = Ỹ ))− P(f(Xip1 ) = Ỹip2 )
and K∑ k=1 P(Y = k)qjk = P(Y = j)(1− ∑ k 6=j ek) + (1− P(Y = j))ej = (1− ∑ k ek)P(Y = j) + ej
P(1(f(X) = Ỹ ))
= K∑ k=1 P(Y = k) K∑ j=1 P(f(X) = j|Y = k)qjk
= K∑ j=1 K∑ k=1 P(f(X) = j|Y = k)P(Y = k)qjk
= K∑ j=1 P(f(X) = j|Y = j)P(Y = j)(1− ∑ k 6=j ek) + K∑ j=1 ∑ k 6=j P(f(X) = j|Y = k)P(Y = k)ej
= K∑ j=1 P(f(X) = j|Y = j)P(Y = j)(1− ∑ k 6=j ek) + K∑ j=1 ej (P(f(X) = j)− P(f(X) = j|Y = j)P(Y = j)) =(1− ∑ k ek) K∑ j=1 P(f(X) = j|Y = j)P(Y = j) + K∑ j=1 ejP(f(X) = j)
Now consider the following
P(f(Xip1 ) = Ỹip2 )
= K∑ j=1 P(f(X) = j)P(Ỹ = j)
= K∑ j=1 P(f(X) = j) K∑ k=1 P(Y = k)qjk
= K∑ j=1 P(f(X) = j)
( (1−
∑ k ek)P(Y = j) + ej ) Therefore
E[1(f(X), Ỹ )]− E[1(f(Xip1 ), Ỹip2 )]
=P(1(f(X) = Ỹ ))− P(f(Xip1 ) = Ỹip2 )
=(1− ∑ k ek) K∑ j=1 (P(f(X) = j|Y = j)P(Y = j)− P(f(X) = j)P(Y = j))
For clean labels we have
E[1(f(X), Y )] = K∑ j=1 P(f(X) = j|Y = j)P(Y = j)
For the second term we have
E[1(f(Xip1 ), Yip2 )] = K∑ j=1 P(f(X) = j)P(Y = j)
Therefore
E[1(f(X), Y )]− E[1(f(Xip1 ), Yip2 )]
= K∑ j=1 P(Y = k) (P(f(X) = j|Y = j)P(Y = j)− P(f(X) = j)P(Y = j))
We finish the proof.

heading: PROOF FOR THEOREM 2
text: Proof. From Lemma 3 we know
E[`peer(f(X), Ỹ )] =(1− e−1 − e+1) · E[`peer(f(X), Y )]
=(1− e−1 − e+1) · ( E[`(f(X), Y )]− E[`(f(Xip1 ), Yip2 )] ) =(1− e−1 − e+1) · E [ `(f(X), Y )]− 0.5 · EX [`(f(X),−1)]− 0.5 · EX [`(f(X),+1)]
) When ` is the 0-1 loss we have `(f(X),−1) + `(f(X),+1) = 1,∀x, and therefore
E[`peer(f(X), Ỹ )] = (1− e−1 − e+1) · ( E[`(f(X), Y )]− 1 ) With above we proved f̃∗
1peer ∈ arg minf∈F RD(f).

heading: PROOF FOR THEOREM 3
text: Proof. Our proof is inspired by our argument for p = 0.5. We ask the following question: if it is possible to show that Ỹ corresponds an error-flipped distribution of another distribution Ŷ whose marginals p̃Y 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 Ŷ that satisfies:
p̃Y := P(Ŷ = +1) = P(Y = +1) · (1− e) + P(Y = −1) · e = p(1− 2e) + e.
Denote by the tolerance of p̃Y : = |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 ê−1, ê+1:
P(Ỹ = +1|Ŷ = −1) = ê−1, P(Ỹ = −1|Ŷ = +1) = ê+1 Note that
P(Ỹ = −1|Y = +1) =P(Ỹ = −1|Ŷ = +1) · P(Ŷ = +1|Y = +1)
+ P(Ỹ = −1|Ŷ = −1) · P(Ŷ = −1|Y = +1) =(1− e) · ê+1 + e · (1− ê−1)
Similarly P(Ỹ = +1|Y = −1) = (1 − e) · ê−1 + e · (1 − ê+1). Jointly we need the following equations to hold:
(1− e) · ê+1 + e · (1− ê−1) = e+1 (1− e) · ê−1 + e · (1− ê+1) = e−1
Solving above equations we have
ê−1 = (1− e) · e−1 + e · e+1 1− 2e − e
1− 2e For a feasible solution to ê−1, ê+1, the conditions need to satisfy that (1) ê−1, ê+1 ≥ 0 and (2) ê−1 + ê+1 < 1. First of all, from (2) we have
e · ( 1− (ê−1 + ê+1) ) = e−1 − ê−1
Then a necessary condition for ê−1 + ê+1 < 1 is
e−1 − ê−1 > 0⇔ e−1 < 1
2 + e−1 2(1− 2e)
This condition holds as long as e−1, e+1 < 0.5. From ê−1, ê+1 ≥ 0 we have
(1− e) · e−1 + e · e+1 > e, (1− e) · e+1 + e · e−1 > e (9)
This above jointly proves that R`α-peer,D̃(f) is equivalent to a peer loss defined over the noisy distribution of ŷ with error parameters ê−1, e+1.
Denote by f∗F ∈ arg minf∈F RD(f). From the optimality of f̃∗1peer we have
RD(f̃ ∗ 1peer )− p̃Y · EX [`(f̃∗1peer(X),+1)]− (1− p̃Y ) · EX [`(f̃ ∗ 1peer (X),+1)]
≤ RD(f∗F )− p̃Y · EX [`(f∗F (X),+1)]− (1− p̃Y ) · EX [`(f∗F (X),+1)] (10)
Note ∀f : ∣∣p̃Y · EX [`(f(X),+1)] + (1− p̃Y ) · EX [`(f(X),+1)] (11) − 0.5 · EX [`(f(X),+1)]− 0.5 · EX [`(f(X),−1)]
∣∣ =|p̃Y − 0.5| ·
∣∣EX [`(f(X),+1)]− EX [`(f(X),−1)]∣∣ ≤ (¯̀− `) (12)
Notice that RD(f̃ ∗ 1peer )− p̃Y · EX [`(f̃∗1peer(X),+1)]− (1− p̃Y ) · EX [`(f̃ ∗ 1peer (X),+1)]
≤ RD(f∗F )− p̃Y · EX [`(f∗F (X),+1)]− (1− p̃Y ) · EX [`(f∗F (X),+1)] ≤ RD(f∗F )− 0.5 · EX [`(f∗F (X),+1)]− 0.5 · EX [`(f∗F (X),+1)] + (¯̀− `) (13)
Combining Eqn. (10, 12, 13) we have
RD(f̃ ∗ 1peer )−RD(f∗F ) ≤p̃Y · EX [`(f(X),+1)] + (1− p̃Y ) · EX [`(f(X),+1)] − 0.5 · EX [`(f(X),+1)]− 0.5 · EX [`(f(X),−1)] + (¯̀− `) ≤2 (¯̀− `)

heading: PROOF FOR LEMMA 4

heading: Proof.
text: E[1peer(f(X), Ỹ )] =(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)

heading: PROOF FOR THEOREM 4

heading: Proof.
text: E[1α-peer(f(X), Ỹ )] =E[1(f(X), Ỹ )]− α · E[1(f(Xip1 ), Ỹip2 )]
=E[1peer(f(X), Ỹ )] + (1− α) · E[1(f(Xip1 ), Ỹip2 )]− 1 =E[1peer(f(X), Ỹ )] + (1− α) · ( P(f(X) = −1) · P(Ỹ = −1) + P(f(X) = +1) · P(Ỹ = +1) ) − 1
=E[1peer(f(X), Ỹ )] + (1− α) · (( p · (1−R+1) + (1− p) ·R−1 ) · P(Ỹ = −1)
+ ( pR+1 + (1− p)(1−R−1) ) · P(Ỹ = +1) ) − 1
=E[1peer(f(X), Ỹ )] + (1− α) · (P(Ỹ = +1)− P(Ỹ = −1)) · (pR+1 − (1− p)R−1) + C =2(1− e−1 − e+1) · p(1− p) · (R−1 +R+1 − 1)
+ (1− α) · (P(Ỹ = +1)− P(Ỹ = −1)) · ( pR+1 − (1− p)R−1 ) + C
=R+1 · ( 2(1− e−1 − e+1) · p(1− p) + (1− α)p · (P(Ỹ = +1)− P(Ỹ = −1)) )
+R−1 · ( 2(1− e−1 − e+1) · p(1− p)− (1− α)(1− p) · (P(Ỹ = +1)− P(Ỹ = −1)) ) + C ′,
where C,C ′ are constants: C = (1− α) · ( (1− p) · P(Ỹ = +1) + p · P(Ỹ = −1) ) − 1
C ′ = C − 2(1− e−1 − e+1) · p(1− p)
Let
p
1− p = 2(1− e−1 − e+1) · p(1− p) + (1− α) · p · (P(Ỹ = +1)− P(Ỹ = −1)) 2(1− e−1 − e+1) · p(1− p)− (1− α) · (1− p) · (P(Ỹ = +1)− P(Ỹ = −1)) .
that α = 1− (1− e−1 − e+1) ·
∆p ∆p̃ .
we obtain that
E[1α-peer(f(X), Ỹ )] = (1− e−1 − e+1)E[1(f(X), Y )] + C ′, (14)
concluding our proof. The last equation Eqn.(14) also implies the following proposition:
Proposition 8. For any f, f ′, we have
ED̃[1α-peer(f(X), Ỹ )]−ED̃[1α-peer(f ′(X), Ỹ )] = (1−e−1−e+1)
( E[1(f(X), Y )]−E[1(f ′(X), Y )] ) .

heading: PROOF FOR THEOREM 5
text: Proof. ∀f , using Hoeffding’s inequality with probability at least 1− δ
|R̂ 1α-peer,D̃ (f)−R 1α-peer,D̃(f)| ≤ √ log 2/δ
2N (1α−peer − 1α−peer) ≤(1 + α) √ log 2/δ
2N
Note we also have the following:
R 1α-peer,D̃ (f̂∗ 1α-peer )−R 1α-peer,D̃ (f∗ 1α-peer )
≤R̂ 1α-peer,D̃ (f̂∗ 1α-peer )− R̂ 1α-peer,D̃ (f∗ 1α-peer ) + (R1α-peer,D(f̂ ∗ 1α-peer )− R̂ 1α-peer,D̃ (f̂∗ 1α-peer ))
+ (R̂ 1α-peer,D̃ (f∗ 1α-peer )−R 1α-peer,D̃ (f∗ 1α-peer ))
≤0 + 2 max f |R̂ 1α-peer,D̃ (f)−R 1α-peer,D̃(f)|
Now we show
RD(f̂ ∗ 1α∗ -peer )−R∗
=RD(f̂ ∗ 1α∗ -peer )−RD(f∗1α∗ -peer) (Theorem 4)
= 1 1− e−1 − e+1 ( R 1α∗ -peer,D̃ (f̂∗ 1α∗ -peer )−R 1α∗ -peer,D̃ (f∗ 1α∗ -peer ) ) (Proposition 8)
≤ 2 1− e−1 − e+1 max f |R̂ 1α∗ -peer,D̃ (f)−R 1α∗ -peer,D̃ (f)|
≤ 2(1 + α ∗)
1− e−1 − e+1
√ log 2/δ
2N .
We conclude the proof.

heading: PROOF FOR THEOREM 6
text: Proof. We start with condition (1). From Lemma 3, E[`peer(f(X), Ỹ )] =(1− e−1 − e+1) · ( E[`(f(X), Y )]− 0.5 · E[`(f(X),−1)]− 0.5 · E[`(f(X),+1)] )
The above further derives as
E[`peer(f(X), Ỹ )] =(1− e−1 − e+1) · ( E[`(f(X), Y )]− 0.5 · E[`(f(X), Y )]− 0.5 · E[`(f(X),−Y )] ) =
1− e−1 − e+1 2
· ( E[`(f(X), Y )]− E[`(f(X),−Y )] ) Denote by c := 21−e−1−e+1 we have
E[`(f(X), Y )] = c · E[`peer(f(X), Ỹ )] + E[`(f(X),−Y )]
Then
E[`(f(X), Y )]− E[`(f∗` (X), Y )]− (E[`(f(X),−Y )]− E[`(f∗` (Y ),−Y ))] =c · (E[`peer(f(X), Ỹ )]− E[`peer(f∗` (X), Ỹ )]) ≤c · (E[`peer(f(X), Ỹ )]− E[`peer(f∗`peer(X), Ỹ )])
Further by our conditions we know
E[`(f(X), Y )]−E[`(f∗` (X), Y )]− (E[`(f(X),−Y )]− E[`(f∗` (Y ),−Y ))] ≥ E[`(f(X), Y )]− E[`(f∗` (X), Y )].
Therefore we have proved
E[`peer(f(X), Ỹ )]− E[`peer(f∗`peer(X), Ỹ )] ≥ 1
c
( E[`(f(X), Y )]− E[`(f∗` (X), Y )] ) .
Since `(·) is calibrated, and according to Proposition 8 and Theorem 2:
ED̃[1α-peer(f(X), Ỹ )]− ED̃[1α-peer(f ∗ ` (X), Ỹ )] =(1− e−1 − e+1) ( E[1(f(X), Y )]− E[1(f∗` (X), Y )] ) ≤(1− e−1 − e+1) ·Ψ−1` (E[`(f(X), Y )]− E[`(f ∗ ` (X), Y )]) ≤(1− e−1 − e+1) ·Ψ−1` (c · (E[`peer(f(X), Ỹ )]− E[`peer(f ∗ `peer(X), Ỹ )])).
Therefore Ψ`peer(x) = 1 cΨ`( x 1−e−1−e+1 ). It’s straight-forward to verify that Ψ`peer(x) satisfies the conditions in Definition 1. We conclude the proof.
Now we check condition (2). Again, from previously, we know the following holds for a certain p̂y = py(1− ey) + (1− py)e−y where p+1 = p, p−1 = 1− p:
E[`α-peer(f(X), Ỹ )] =E[`(f(X), Ỹ )− α · `(f(X), Ỹk)]
=E [ (1− eY )`(f(X), Y ) + eY `(f(X),−Y )− α · p̂Y `(f(X), Y )− α · (1− p̂Y )`(f(X),−Y ) ] =E [ (1− eY − αp̂Y )`(f(X), Y ) + (eY − α · (1− p̂Y ))`(f(X),−Y )
] Let φ(f(X) · Y ) := `(f(X), Y ), we have
E[`α-peer(f(X), Ỹ )) =E [ (1− eY − αp̂Y )φ(f(X) · Y ) + (eY − α · (1− p̂Y ))φ(−f(X) · Y ) ] :=E[ϕ(f(X) · Y )]
We first introduce a Theorem:
Theorem 9 (Theorem 6, (Bartlett et al., 2006)). Let ϕ be convex. Then ϕ is classification-calibrated if and only if it is differentiable at 0 and ϕ′ < 0.
We now show that ϕ is convex:
ϕ′′(β) =(1− eY − αp̂Y ) · φ′′(β) + (eY − α · (1− p̂Y ))φ′′(−β) =(1− eY − αp̂Y ) · φ′′(β) + (eY − α · (1− p̂Y ))φ′′(β) =(1− eY − αp̂Y + eY − α · (1− p̂Y ))φ′′(β) =(1− α)φ′′(β) > 0
when α < 1. The last inequality is due to the fact that ` is convex.
Secondly we show the first derivative of ϕ is negative at 0: ϕ′(0) < 0:
ϕ′(0) =(1− eY − αp̂Y ) · φ′(0)− (eY − α · (1− p̂Y ))φ′(0) =(1− 2eY + α(1− 2p̂Y ))φ′(0) (15)
Note that
p̂y = py(1− ey) + (1− py)e−y
Plug back to Eqn. (15) we have
ϕ′(0) =(1− eY − αp̂Y ) · φ′(0)− (eY − α · (1− p̂Y ))φ′(0) = ( 1− 2eY + α(1− 2p̂Y ) ) φ′(0)
= ( (1− αpy)(1− 2ey) + α(1− py)(1− e−y) ) φ′(0) (16)
Since (1 − αpy)(1 − 2ey) + α(1 − py)(1 − e−y) > 0 and φ′(0) < 0 (due to calibration property of `, Theorem 6 of Bartlett et al. (2006)), we proved that ϕ′(0) < 0. Then based on Theorem 6 of Bartlett et al. (2006), we know ``α-peer is classification calibrated.

heading: PROOF FOR THEOREM 7
text: Proof. We first prove the following Rademacher complexity bound
Lemma 7. Let <(F) denote the Rademacher complexity of F . L denote the Lipschitz constant of `. Then with probability at least 1 − δ, maxf∈F |R̂`α-peer,D̃(f) − R`α-peer,D̃(f)| ≤ (1 + α)L · <(F) +√
log 4/δ 2N (1 + `α−peer − `α−peer).
Note we also have the following ∀α:
R`α-peer,D̃(f̂ ∗ `α-peer)−R`α-peer,D̃(f ∗ `α-peer)
≤R̂`α-peer,D̃(f̂ ∗ `α-peer)− R̂`α-peer,D̃(f ∗ `α-peer)
+ (R`α-peer,D̃(f̂ ∗ `α-peer)− R̂`α-peer,D̃(f̂ ∗ `α-peer))
+ (R̂`α-peer,D̃(f ∗ `α-peer)−R`α-peer,D̃(f ∗ `α-peer))
≤0 + 2 max f∈F |R̂`α-peer,D̃(f)−R`α-peer,D̃(f)|
Then apply the calibration condition we have
RD(f̂ ∗ `α∗ -peer )−R∗
= 1 1− e−1 − e+1 ( R 1α∗ -peer,D̃ (f̂∗`α∗ -peer)−R1α∗ -peer,D̃(f ∗) )
(Proposition 8)
= 1 1− e−1 − e+1 ( R 1α∗ -peer,D̃ (f̂∗`α∗ -peer)−R1α∗ -peer,D̃(f̃ ∗ 1α∗ -peer ) )
(Theorem 3)
≤ 1 1− e−1 − e+1 Ψ−1`α∗ -peer ( min f∈F R`α∗ -peer,D̃(f)−minf R`α∗ -peer,D̃(f) (Calibration of 1α ∗-peer)
+R`α∗ -peer,D̃(f̂ ∗ `α∗-peer )−R`α∗ -peer,D̃(f ∗ `α∗ -peer ) ) ≤ 1
1− e−1 − e+1 Ψ−1`α∗ -peer ( min f∈F R`α∗ -peer,D̃(f)−minf 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)−minf R`α∗ -peer,D̃(f) (Lemma 7)
+ 2(1 + α∗)L · <(F) + 2 √ log 4/δ
2N (1 + `α∗-peer − `α∗-peer)
) ,
with probability at least 1− δ.

heading: PROOF FOR LEMMA 7
text: Proof. Due to the random sampling, via Hoeffding inequality we first have there exists some p̂ỹn ∈ (0, 1), with probability at least 1− δ,
∣∣∣∣ 1N N∑ n=1 `α-peer(f(xn), ỹn)− 1 N N∑ n=1 (`(f(xn), ỹn)
− α · p̂ỹn`(f(xn), ỹn)− α · (1− p̂ỹn)`(f(xn),−ỹn)) ∣∣∣∣
≤ √ log 2/δ
2N · (`α−peer − `α−peer)
Define the following loss function:
˜̀(xn, ỹn) := `(f(xn), ỹn)− α · p̂ỹn`(f(xn), ỹn)− α · 1− p̂ỹn)`(f(xn),−ỹ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− 2δ:∣∣∣∣ 1N N∑ n=1 `α-peer(f(xn), ỹn)−R`α-peer,D̃(f) ∣∣∣∣
= ∣∣∣∣ 1N N∑ n=1 `α-peer(f(xn), ỹn)− R̂˜̀,D̃(f) + R̂˜̀,D̃(f)−R`α-peer,D̃(f) ∣∣∣∣
≤ ∣∣∣∣ 1N N∑ n=1 `α-peer(f(xn), ỹ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 ) In aboveR`α-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.

heading: PROOF FOR LEMMA 8
text: 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).

heading: EXPERIMENT

heading: IMPLEMENTATION DETAILS
text: 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.

heading: RESULTS
text: 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.

Review summaries:
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.

This paper studies the problem of learning classifiers from noisy data without specifying the noise rates. Inspired by the literature of peer prediction, the authors propose peer loss. First, a scoring function is introduced, minimizing which we can elicit the Bayes optimal classifier f*. Then the authors use the setting of CA to induces a scoring matrix, and then the peer loss. Moreover, this paper explores the theoretical properties of peer loss when p=0.5. In particular, the authors propose \alpha weighted peer loss to provide strong theoretical guarantees of the proposed ERM framework. The calibration and generalization abilities are also discussed in section 4.3. Finally, empirical studies show that the propose peer loss indeed remedies the difficulty of determining the noise rates in noisy label learning.