Robust Loss Functions for Complementary Labels Learning
Authors: Defu Liu
Guowu Yang
Venue:  (2021)
Keywords: Complementary Labels
Robustness
Machine Learning

Abstract: In ordinary-label learning, the correct label is given to each training sample. Similarly, a complementary label is also provided for each training sample in complementary-label learning. A complementary label indicates a class that the example does not belong to. Robust learning of classifiers has been investigated from many viewpoints under label noise, but little attention has been paid to complementary-label learning. In this paper, we present a new algorithm of complementary-label learning with the robustness of loss function. We also provide two sufficient conditions on a loss function so that the minimizer of the risk for complementary labels is theoretically guaranteed to be consistent with the minimizer of the risk for ordinary labels. Finally, the empirical results validate our method’s superiority to current state-of-the-art techniques. Especially in cifar10, our algorithm achieves a much higher test accuracy than the gradient ascent algorithm, and the parameters of our model are less than half of the ResNet-34 they used.

Under review as a conference paper at ICLR 2021
ROBUST Loss FUNCTIONS FOR COMPLEMENTARY LABELS LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
In ordinary-label learning, the correct label is given each training sample. Similarly, a complementary label is also provided for each training sample in complementary-labee learning. complementary label indicates a class that the example does not belong to. Robust learning of classifiers has been investi- gated from many viewpoints under label noise, but little attention has been paid to complementary-labee learning. In this paper, we present a new algorithm of complementary-lakee llbel learning with the robustness of loss function. We also pro- vide two sufficient conditions on a loss function so that the minimizer of the risk for complementary labels is thcoretically guaranteed to be consistent with the min- imizer of the risk for ordinary labels. Finally, the empirical results validate our method's superiority to current state-of-the-ane art techniques. Especially in cifar 10, our algorithm achieves a much higher test accuracy than the gradient ascent algo- rithm, and the parameters of our model are less than half of the ResNet-34 they used.
9
11
13
INSTRUCTION
15
Deep neural networks have exhibited excellent performance in many real-application.. Yet, their supper performance based on the correctly labeled large-scale training set. However, labeling such a large-scale dataset is time-consuming and expensive. For example, the crowd-workers need
16
17
18
select the correct label for sample from 100 labels for CIFAR100. To migrate this problem, reachers have proposed many solutions to learn from weak-supervision: Noise-label learning Li jt al. (2017); Hu al. (2019); [ee al. (2018): Xia et al. (2019), semi-supervised learning /hai et al. (2019); Berthelot et al. (2019); Rasmus et al. (2015); Miyato et al. (2019); Sakai et al. (2017) |Bo unlabeled learning Lu al. (2018) y Chen et al. (2020a b). unlablee learning Elkan & Noto
19
21
similar-unlabeled learning Tanhal (019); Bao et (2018) Zelikovitz & Hirsh (2000), unlabeled-
20
2008); du Plessis et al. (2014); Kiryo et al. (2017), 1), contrast learning Chen et al.) (2020a bj, partial
label learning Cour al. (201) Feng & An 2018): Wu & Zhang (2018) and others.
We investigate complementary-llbll learning Ishida et al. (2017) in this paper. A complementary Label is only indicating that the class label of sample incorrect. In the view of label noise, complementary labels can also be viewed as noise labels but without any true labels in the training set. Our task is to learn classifier from the given complementary labels, predicting a correct label for a given sample. Collecting complementary labels is much easier and efficient than choosing a true class from many candidate classes precisely. For example, the label-system uniformly chooses a label for sample. It has probability of to be ordinary-labed but k-1 to be complementary-lan Moreover, another potential application of complementtry--labe some privacy issues, it is much easier to collect complementary-lan than ordinary-label.
30
32
& privacy. For example, on
34
Robust learning of classifiers has been investigated from many viewpoints in the presence of label noise Ghosh et al. (2017). but little attention paid to complementary-labe learning. We call loss function robust the minimizer of risk under that loss function with complementary labels would be the same that with ordinary labels. The robustness of risk minimization relies on the loss function used in the training set.
36
38
40
This paper presents general risk formulation that category cross-entropy loss (CCE) can be used to learn with complementary labels and achieve robustness. We then offer some innovative analytical results on robust loss functions under complementary labels. Having robustness of risk minimization
42

---

Under review as a conference paper at ICLR 2021
44 helps select the best hyper-parameter by empirieal risk since there no ordinary labels in the validation set. We conclude two sufficient conditions on a loss function to be robust for learning with complementary labels. We then explore some popular loss functions used for ordinary- learning, such as CCE, Mean square error (MSE) and Mean absolute error (MAE), and show that CCE and MAE satisfy our sufficient conditions. Finally, we present learning algorithm for learning with complementary labels, named exclusion algorithm. The empirical results well demonstrate the advantage of the theoretical results we addressed and verify our algorithm's 's superiority to the current state-of-tie of-tho methods. The contribution of this paper can be summarized as:
45
47
49
50
51
52
We present a general risk formulation that can be view as a framework to employing a loss function that satisfies our robustness sufficient condition to learn from complementary labels.
53
54
55
We conclude two sufficient conditions on a loss function to be robust for learning with complementary labels.
56
57
We prove that the minimizer of the risk for complementary labels theoretically guaran- teed to be consistent with the minimizer of the risk for ordinary labels.
58
59
The empirical results validate the superiority of our method to current state-of-ther the-the-rtt meth- ods.
80
61
2
RELATED WORKS
62
Complementary- refers to that the pattern does not belong to the given label. Learning from complementary labels is a new topic in supervised-learnin It was first proposed by [Ishida et al. (017). They conduct such an idea to try to deal with time-consuming and expensive to tag a large- 64
65
scale dataset.
66
In their early work Ishida et al. (017)) they assume the complementary labels are the same prob- ability to be selected for sample. And then, based on the ordinary one-versus-all (OVA) and pairvise-comparison (PC) multi-class loss functions Zhang (2004) proposed a modifying loss for learning with complementary labels.
67
68
69
70
Even though they provided theoretical analysis with a statistical consistency guarantee, the loss function met a sturdy restriction that needs be symmetric (E(z) + f(-2) =). Such severe limitation allows only the OVA and PC loss functions with symmetric non-convex binary losses.
71
72
73 However, the categorical cross-entropy loss widely used in the deep learning domain, can not be
74
employed by the two losses they defined.
75 Later, Yu al. (0188)) assume there are some biased amongst the complementary labels and presents a different formulation for biased complementary labels by using the forward loss cor- rection technique Patrini et al. (0017) to modify traditional loss functions. Their suggested risk estimator is not necessarily unbiased and proved that learning with complementary labels can the- oretically converge to the optimal classifier Iearned from ordinary labels based on the estimated transition matrix. However, the key the forward loss correction technique is to evaluate the tran- sition matrix correctly. Hence, one will need to assess the transition matrix beforehand, which is relatively tricky without strong assumptions. Moreover, in such setup, it restricts a small com- plementary label space to provide more information. Thus, it is necessary to encourage the worker provide more challenging complementary labels, for example, by giving higher rewards to the specific classes. Otherwise, the complementary label given by the worker may be too evident and uninformative. For example, class three and class five are not class one evidently but is uninforma- tive. This paper focuses on the uniform (symmetric) assumption and study random distribution as biased assumption (asymmetric or non-uniform).
76
77
79
80
81
82
83
84
85
86
87
88
89
Based on the uniform assumption. Ishida et al. (2019) proposed an unbiased estimator with general loss function for complementary labels. It can make any loss functions available for use, not only soft-max cross-entropy loss function, but other loss functions can also be utilized. Their new frame- learning Ishida et al. (2017). However, their proposed unbiased risk estimator has an issue that the classification risk can attain negative
90
91
92
work is a generalization of previous complementary-
94 values after learning, leading to overfitting Ishida et al. (2019). They then offered a non-ne non-negative correction to the original unbiased risk estimator to improve their estimator, which is no longer
95
2

---

Under review as a conference paper at ICLR 2021
guaranteed to be unbiased risk estimator. In this paper, our proposed risk estimator is also not unbiased, but the minimizer of the risk for complementary labels theoretically guaranteed to be consistent with the minimizer of the risk for ordinary labels, both uniform and non-uniform.
97
3 PRELIMINARIES
3.1 LEARNING WITH ORDINARY LABELS
100
In the context of learning with ordinary labels, let &' I2 be the feature space and {1, be the class labels. A multi-class loss function is map: [(fo(()),)) v) X x y + R A classifier can be presented as:
k}
101
102
103
h(x)) = arg max fe (x) [E(R]
(1)
where fo(æ) (x), -1 (z)) θ is the set of parameters in the CNN network, fx) is the probability prediction for the corresponding class i. Even though h(x) is the final classifier,
(x)
104
105
use notation of calling fa( itself as the classifier. Given dataset = {(xr, y: together with a loss function C. Vffe (F is the function space for searching), C-risk is defined as:
106
107
(fe
ED [C(fo (z)) v)] LEs [C(fo(x)). v)],
Some popular multi-class loss functions are CCE, MAE, MSE. Specifically,
108
Σ By
k log Byy = log
CCE,
= e
|le, =//
224
MAE,
(3)
||e, u 112 = |u 2pl
MSE,
where (o = (Mi,'. ). and ey is one-hot vector that the y-th component equals to 1, others are The goal of multi-class classification is to learn classifier fo( that minimize the classification risk R with multi-class loss L.
110
3.2 LEARNING WITH COMPLEMENTARY LABELS
In contrast to the ordinary- label learning, the complementary-label (CL) dataset contains only labels indicating that the class label of sample is incorrect. Corresponding the ordinary labels dataset S, the independent and identically distributed (i..d.) complementary labels dataset denoted as:
113
115
S = { g)
where is the size of the dataset S, and represents that pattern does not belong class-ū.
116
The general labels' distribution of dataset S is as:
117
0
P12
Pik
P21
0
P2k
P(ily)
(5)
PRi
Pk(k-1)
kxk.
where Pij denotes that the probability of the i-th class's pattern x labeled as j. Σi=1 =1 Pij
118
1, Paj # i. Supposing that the label system uniformly select label from -1. k}] \ {v} for each sample æ, then the Eq. (5) becomes
120
P(uly) =
k k-1
(6)
kx
Yu et al. (018b) make strong assumption that there are some bias in Eq. (5). while Ishida
et al. (201) 2019) focus on the assumption of Eq. (6). In this paper, we study both kinds distri- bution.
122
3

---

Under review as a conference paper at ICLR 2021
4
METHODOLOGY
125 In this section, we firstly propose general risk formulation for leaning with complementary labels. And then prove that some loss functions designed for the ordinary labels learning robust to complementary labels with our risk formulation, such as categorical cross-entropy loss and mean absolute emror.
127
4.1
GENERAL RISK FORMULATION
130
The goal of learning with complementary labels is to learn a classifier that predicts a correct label for any sample drawn from the same distribution. Because there are not ordinary labels for the model, we need to design loss function or model for learning with complementary labels. The key to learn- ing classifier for ordinary label learning is maximize the true label's predict-probabilig One is to minimize the predict-probabiliy of complementary labels. this paper, with little abuse of notation, we let
132
133
134
intuitive way to maximize the true label's predict-probablle
135
u fo(x) (11.-..... V -- 1-11-f(m)=(1 = fl, pkk
(7)
Definition 1. (CL-loss) Together with loss function & designed for the ordinary-label learning, the loss for learning with complementary-laten is as:
137
{(fo(z). = E(u, E(v,
(8)
138
4.2
THEORETICAL RESULTS
Definition 2. (Robust loss) In the framework of risk minimization, loss function is called robust loss function if minimizer of risk with complementary labels would be the same as with ordinary labels, i.e.,
140
R$ (fo-) (F)) 5 (f-r)) (fo) 00. Theorem 1. Together with e, f. is robust loss function for learning with complementary labels, if
(9)
143
satisfies:
@E( 1)
ae(u, 3) O, Vie .k) (0)
O,
(10)
0pi
0p
Note that, in Eq. 10 it means that is monotone increasing loss function only on u())
144
Proof. Recall that for any fe. and any l, R (So) = E(m.w) [E (fo(x) = S
Σ
(fa(x)))))
(11)
(T.a)ES
146
For any complementary-label distribution in Eq. (5) and any loss function e, we have
R (fo) B( [[(fo())
M (f)()))))
k
(12)
#ES, jØs
where Pij is the component of complementary labels distribution matrix P, U... US = S. 148 Supposing that fe- the optimal classifier learns from the complementary labels, and Vf E F, where F is the function space for searching, we have
k
(So-) - R$ (Jo)
1
- Σ Pi ( so, (13)
S
#+i
where Più * 0. If 3x' E S, s.t., ē( (x (z'). > {(folx)) (. let fo satisfying
150
for (z)
x x SES) fx x x=
Jor (x)
(14)
fa(x)
4

---

Under review as a conference paper at ICLR 2021
then according Eq. 12 and 13
(f
(fo-)). for is not the optimal classifier. This
contradicts the hypothesize that Jø- is the optimal classifier.
162
Thus, Ay E (1.-.. .k} {y}, we have
E(for (x), S {(folz).)).
(15)
According to Eq. (10). f a monotone increasing loss function only on u(0), then we have
154
vy E -1, ,A \ (u), 1 (x) - (x)
(16)
Thus,
( (x) 2 (x)), (z) =1 -.--1 r
11
0do0 (x)
(17)
and then,
S {(Jo(x))))),
(18)
thus,
157
(fo-) - RS (fo) 0..
(19)
158
Theorem 2. Together with E, E. is robust loss function for learning with complementary labels under synmetric distribution or uniform distribution, if l satisfies:
160
Selu. 5)
O,
Σ E(u,
C, (C is a constant).
(20)
0pg
should noted that, in Eq. 20 it means that is a symmetric loss E(,,)) = C). and i
161
monotone increasing loss function any ÿ-
Proof. For any complementary-label distribution in Eq. 66), and any loss function L, we have
163
R$ (Jo) ((, (fo(())) 1)
1
{(f((z)..)
S mES;
(21)
(C [(f(()))
mES:
C
(fo),
k
where S₁ U... U S.
Supposing that fa- the optimal classifier learns from the complementary labels, and Vf E F, where F the function space for searching, we have
165
166
R$ (Jo.)
R (So) = RS (Jo) - (S-))
(So.) S 0,
(22)
According to the first constraint in Eq. 20 we then have
167
[(fo(z).
(()e (16 (x) < f/ (x)
(23)
and then,
(fo-()))))) v) S {(fo())))), RS (fo-) R$ (fo) 0
(24)
thus,
(25)
5

---

Under review as a conference paper at ICLR 2021
Algorithm Learning from complementary labels by exclusion
Require:
S ((, {.);; The given dataset;
Ensure: Classifier So (2:)
Randomly initialize a group parameter for So (a:);
2: Randomly split & into training set Strain and a valid-set Svalid;
3: for (e = e S Epochs; + +) do
4: for (Et, ) in Surain do
5: fo(x;; = (f11, ... 11k));
6:
fo(x))) (1 p1, .. 1 pk);
7:
loss = f(u, Mi):
8:
w = w 3 Closs w E E
9:
end for
10: end for
return fo (x)
Together with some well known multi-class loss functions, such as CCE, MAE, MSE, the loss for learning with complementary labels with our definition are as follows:
172
Gi=l Cg log 1 = -log 1-Ps
CCE,
1-p;
E(fo()).)=
lleg - v/1 = -- - 2 2/10
MAE,
(26)
|1og - v12 = 3 ||u||3 + 2/g
MSE,
where ey is one-hot vector that the ÿ-th component equals to 1, others are 0. As its shown in 2 while MSE
174 Eq. (26). CCE and MAE loss satisfy the Theorem [ MAE also satisfies the Theorem does not satisfies the two. Zhang& & Sabuncul (2018) propose GCE loss function for learning with
176 label noise, their formulation is as:
lACE (fo(z),y) (1-18) (C)
G (0,1).
(27)
It is easily to know that the loss function satisfies the constraint in Theorem thus, it can be used to learning with complementary labels.
178
179
4.3
EXCLUSION ALGORITIMM FOR LEARNING FROM COMPLEMENTARY LABELS
Based the loss function designed for complementary-lun label learning, present algorithm to learn a classifier from complementary labels with our loss function, named exclusion algorithm (the label specifies that the sample does belong it). The algorithm details show in Alg. [ Furthermore, our algorithm is easily combined with the models designed for ordinary learning,
181
182
183
184
with only a minus operation, which can be view as framework to use the loss designed for ordinary- label learning to learn the optimal classifier from complementary labels.
5
EXPERIMENTS
187
5.1
EXPERIMENTAL SETTINGS
188
Datasets. We test our experiments on MNIST LeCun al. (199). SIHHION-NNIST Xiao et al. (017), CIFAR10 Krizhevsky (2009). Specifically, we generate two types of complementary labels: symmetric and asymmetric, for our experiments to verify our method's 's effectiveness and the theorem proved in the previous section. For symmetric complementary-late, we fix a label distribution as Eq. (6) to generate the complementary-len label training set. The validation set is split from the training ordinary-label. Thus. the lower the validation accuracy, the better the classifier learns from the training set. For asymmetric complementary-Bee matrix Eq. (5) that the Pij is unknown the complementary-lakke label distribution and using it
190
192
which contains
194
we randomly generate

---

Under review as a conference paper at ICLR 2021
to create complementary label for experiments. The test accuracy of all experiments is tested clean dataset that contains only the ordinary labels.
197
Approaches. We test our loss with ECCE. EMAE. ÊMSE, ÊOCE and compare with otate-of-the-art meth- ods in learning with complementary labels. The loss functions we used or compare in this paper listed follows. 1) CCE: The categorical cross-entropy loss, neither symmetric which widely use in machine learning and deep learning due to its fast convergence speed. 2) MAE:
199
bounded,
200
201
The mean absolute error, a symmetric loss and bounded, has been proved Ghosh al. (2017) to be noise-tolerant. 3) MSE: The mean square error, not symmetric but bounded, widely used in regres-
202
203
sion learning. 4) GCE: It uses hyper-parameter 9 tune the loss between MAE and CCE, but achieve noise-robust base on its bounded, we used the standard GCE where q=0.7 5) GA: Gradi-
204
205
ent ascent, a learning algorithm for complementary-label learning, is used to tackle the overfitting
206
problem of the unbiased estimator they proposed in Ishida et al. (2019). 6) PC: Pairwise compar-
207
ison (PC) with ramp loss designed for complementary-laber learning Ishida et al.) (2017). 7) Fwd:
208
Forward correction Patrini et al. (017)) Yu et al.
2018a) designed for learning with complementary
labels.
210
Network architecture. Following Ghosh et al. (2017). we use a network architecture that contains five layers to test the above methods for all the experiments: a convolution layer with 32 filters which filter size set as (3,3), a max-pooling layer with pooling-side size of (3,3) and strides of (2,2), two fully connected layers with 1024 units, and a fully connected layer with soft-max activated function that the unit number set the category number for prediction. Rectified Linear Unit (ReLU) is used as the activated function in the network's 's hidden layer.
211
212
213
214
215
216
Implement details. The implementation detail of our method shows in Alg. | We train our network with stochastic gradient descent through back-propagation. Each experiment trains 200 epochs, and the mini-batch size was set to 64. To exploit each loss function's best performance, we set three start learning rate for each loss function on each experiment and report the best accuracy amongst the three learning rate of each loss function. CCE set to [le-3, 5e-4, le-4], while GCE, MAE, MSE is set to [1.0, 0.5, 0.1] 0. The learning rate was halved per 50 epochs.
217
218
219
220
221
222
5.2 EXPERIMENTAL RESULTS
223
SCL
SCL
SCL
SCL
0.50
0.305
0.4
0.25
0.3
0.2
vald_,00 200
1est_ac
2.05
2.30
0.15
0,0521
0.1
0.045
0.1
0.2
0.1228
0.0
0.0388
0.0
0.0a22
0.0
0.0
50
120
:20
50
100
150
202
50
120
23.
0
50
100
150
202
Froene
Eporss
Froche
Eporss
ACL
ACL
ACL
ACL
10:0000
0.35
0.50
0.30
0.3
0.25
0.20
0.2
0.20
0.35
0.1558
0.15
0.30
0,0332
0.063
2.08
0.0505
0.05
0.055.4
0.0
0.00
6.00
50
15a
150
0
5.
100
150
202
50
150
15.
0
50
100
150
202
Esecis
Spochs
Esecis
Spocks
Figure 1: Accuracy for CCE, MAE, GCE, MSE loss functions over epochs, for CIFARIO dataset with symmetric complementary labels (SCL) and asymmetric complementary labels (ACL). Leg- ends are shown in the first sub figures on the first row.
Robustness. As shown in Fig. I together with CCE, MAE, and GCE loss, our algorithm achieves strong robust to both symmetric and asymmetric complementary labels, which verify that the robust- ness we prove in the Theorem and Theorem Even though the MAE satisfies the two theorems,
224
225
226
7

---

Under review as a conference paper at ICLR 2021
Table I: The test accuracy and standard deviation (5 trials) on experiments with loss functions, under different complementary labels' distribution assumption, for datasets: MNIST, FASHION-MNIST, CIFARIO. We report the last ten percent epochs average test accuracy. For fair comparison, the last three columns' data are directly copying from Table.2 in Ishida et al. (2019), where GA Ishida ct al. (2019): Gradient Ascent, PC al. (2017): Pairwise Comparison, Fwd Yu al, (2018b):
Forward correction. The top 2 accuracies are boldface.
Loss
Dataset
Distribution
CCB
MAE
GCE
MSE
GA
PC
Fwd
Symmetric
95.66 + 0.15 93.78 + 3.66 97.46 + 0.06 91.58 + 0.60 88.1 # 2.5
79.3 +
3.3 88.7 0.3
MNIST Asymmetric
94.93 + 0.12
68.11 + 5.92
97.22 0.12
85.98
0.38
Symmetric 86.43 + 0.24
74.25 + 0.26 86.43 0.30 82.93 0.18 78.7 1.4 74.7 1.6 77.5 1.2
FASHION Asymmetric
85.22 + 0.19
54.01 + 6.21 85.55 0.12 78.93 0.22
Symmetric 44.46 + 0.31
27.78 +: 2.28 42.64 + 0.82
36.10 + 1.23
36.8 + 0.6
33.4 +: 2.0 30.8 1.6
CIFARIO Asymmetric
37.93 + 0.70
16.73 1: 0.22 36.01 + 0.96
30.98 1. 0.74
227
it achieves a lower test accuracy than that of CCE and GCE due to it treats all labels the same (not sensitive to the labels). The subfigures in the last column of Fig. shows that the MSE loss firstly achieves its highest test accuracy and then drop sharply over the epochs. Because MSE does not satisfy one of the two theorems we prove, it easily overfits the training set's complementary labels. Such a trend is the same as asymmetric complementary labels learning. The results verify that the algorithm we design for the complementary labels is significant and confirms the theoretical results we analyzed in the previous section.
229
231
233
Performance Comparison. The first four columns of Table. [ show that the CCE and GCE loss achieve the best two test accuracies in our algorithm. In the MNIST dataset, the CCE achieves little lower test accuracy than GCE, the same test accuracy in FASHION-MNIST and little higher test accuracy in CIFARIO due to the dataset more challenge and CCE is more sensitive to labels. Even MAE is robust complementary labels, and its performance is not well than others because it is a linear loss that is not sensitive to labels. As shown in Fig. I MSE is not robust to complementary labels, but with small learning rate of 0.1, MSE only exhibited slight overfitting in T Furthermore, as shown in Table together with CCE and GCE loss, our algorithm achieves a test accuracy higher than 95% in the MNIST dataset, which is comparable to that of learning with ordinary labels.
235
236
237
238
239
240
241
242
For fair comparison, The last three columns directly form Ishida al. (011 even those results are the max test accuracy. In the first two datasets, all loss functions with our algorithm achieve higher test accuracy than GA, but they used an MLP model as their base model, simpler than ours. In CIFARIO, they used ResNet-34 (21.62M parameters) He et al. (2016) and DenseNet Huang et al. 2017) as their based model, which is much bigger than ours (8.43M parameters), but we achieve a 248
244
246
much higher test accuracy than theirs. The results validate the superiority of our algorithm to current state-of-the-are methods.
250
251
6
CONCLUSION
252
This paper designs an algorithm for learning from complementary labels using the loss functions designed for ordinary-label learning. We provide theoretical analysis to show that the loss fune- tions we design for learning from the complementary labels are robust to the complementary labels, ie., the optimal classifier learned from the complementary labels can theoretically converge to the optimal classifier learned from ordinary labels. In this paper, the two theorems present are the
253
254
255
257
sufficient condition of a loss function robust to complementary labels. Experimental results show learning is new topic in supervised-leaminn
it offers excellent competitiveness. More methods should be studied to improve the performance of complementary
that though complementary-labe
259
260
learning in our future works, such as Amid et al. 2019b) and Amid al. (2019a).
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Ehsan Amid, Manfred K. Warmuth, and Sriram Srinivasan. Two-temperaturr logistic regression based on the Isallis divergence. volume 89 of Proceedings of Machine Learning Research, pp- 2388-2396. PMLR, 2019a.
262
263
Ehsan Amid, Manfred K. Warmuth, Rohan Anil, and Tomer Koren. Robust bi-tempered logistic loss based on bregman divergences. In Advances in Neural Information Processing Systems, volume 32, pp. 15013-15022, 2019b.
265
267
Han Bao, Gang Niu, and Masashi Sugiyama. Classification from pairwise similarity and unlabeled data. volume 80 of Proceedings of Machine Learning Research, pp. 452-461, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
209
David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel. Mixmatch: holistic approach semi-supervised learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. Alché-Bue, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 5049-5059. Curran Associates, Inc., 2019.
271
272
273
274
Ting Chen, Simon Korbblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. arXiv preprint urXiv:2002.05709 2020a.
275
276
Ting Chen, Simon Kormblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey Hinton, Big self- supervised models are strong supervised learners. arXiv preprint arXiv:2006. 10029, 2020b.
277
278
Timothee Cour, Ben Sapp. and Ben Taskar. Learning from partial labels. The Journal of Machine Learning Research, 12:1501-1536, 2011.
279
280
Marthinus C du Plessis, Gang Niu, and Masashi Sugiyama. Analysis of learning from positive and unlabeled data. Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 27, pp. 703-711. Curran Associates, Inc., 2014.
262
284
Charles Elkan and Keith Noto. Learning classifiers from only positive and unlabeled data. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 213-220. Association for Computing Machinery, 2008
266
Lei Feng and Bo An. Leveraging latent label distributions for partial label learning. In IJCAI, pp. 2107-2113 13, 2018.
288
Aritra Ghosh, Himanshu Kumar, and S. Sastry. Robust loss functions under label noise for deep neural networks. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, AAAI17, pp. 1919-1925. AAAI Press, 2017.
290
291
292
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
293
294
295
Mengying Hu, Hu Han, Shiguang Shan, and Xilin Chen. Weakly supervised image classification through noise regularization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
296
297
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE Conference Computer Vision and Patlern Recognition (CVPR), July 2017.
289
301
Takashi Ishida, Gang Niu, Weihua Hu, and Masashi Sugiyama. Learning from complementary labels. Advances in neural information processing systems, pp. 5639-5649, 2017.
300
Takashi Ishida, Gang Niu, Aditya Menon, and Masashi Sugiyama. Complementary label learning for arbitrary losses and models. International Conference on Machine Learning, pp. 2971- 2980. PMLR, 2019.
305

---

Under review as a conference paper at ICLR 2021
Ryuichi Kiryo, Gang Niu, Marthinus C du Plessis, and Masashi Sugiyama. Positive-unlabeled learning with non- non-negative risk estimator. In I. Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gamett (eds.), Advances in Neural Information Processing Systems 30, pp. 1675-1685. Curran Associates, Inc., 2017.
308
310
A Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, University of Tront, 2009.
312
Yann LeCun, Léon Bottou, Yoshua Bengio. and Patrick Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-233) 1998.
314
Kuang-Huse Huei Lee, Xiaodong He, Lei Zhang, and Linjun Yang. Cleannet: Transfer learning for scalable image classifier training with label noise. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
316
318
Yuncheng Li, Jianchao Yang, Yale Song, Liangliang Cao, Jiebo Luo, and Li-Jia Li. Learning from noisy labels with distillation. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), Oct 2017.
320
Nan Lu, Gang Niu, Aditya Krishna Menon, and Masashi Sugiyama. On the minimal supervision for training any binary classifier from only unlabeled data. In International Conference on Learning Representations, 2018.
322
323
324 T. Miyato, S. Maeda, M. Koyama, and S. Ishii. Virtual adversarial training: A regularization method for supervised and semi-supervised learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1199)1177911995 2019.
326
Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu Making deep neural networks robust to label noise: A loss correction approach. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), July 2017.
328
330
Antti Rasmus, Mathias Berglund, Mikko Honkala, Harri Valpola, and Tapani Raiko. Semi- supervised learning with ladder networks. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems 28, pp. 3546-3554. Curran Associates, Inc., 2015.
332
334 Tomoya Sakai, Marthinus Christoffel du Plessis, Gang Niu, and Masashi Sugiyama. Semi- supervised classification based classification from positive and unlabeled data. volume 70 of Proceedings of Machine Learning Research, pp. 2998-3006, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
336
337
338
Jafar Tanha. A multiclass boosting algorithm to labeled and unlabeled data. International Journal of Machine Learning and Cybernetics, 10(12)334773665, 2019.
339
340
Xuan Wu and Min-Ling Zhang. Towards enabling binary decomposition for partial label learning. In IJCAI, pp. 2868 0878-2874,227 2018.
342
Xiaobo Xia, Tongliang Liu, Nannan Wang, Bo Han, Chen Gong, Gang Niu, and Masashi Sugiyama. Are anchor points really indispensable in label-noise learning? In H. Wallach, H. Larochelle, A. Beygelzimer, F. Alché-Bue, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 6838-6849, Curran Associates, Inc., 2019.
344
345
346
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mniste a novel image dataset for benchmark- ing machine learning algorithms. arXiv 7708.07747, 2017.
347
348
Xiyu Yu, Tongliang Liu, Mingming Gong, and Dacheng Tao. Learning with biased complementary labels. In Proceedings of the European Conference Computer Vision (ECCV), pp. 68 68-83, 2018a.
350
Xiyu Yu, Tongliang Liu, Mingming Gong, and Dacheng Tao. Learning with biased complementary labels. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 68-83,
352
353
2018b.
10

---

Under review as a conference paper at ICLR 2021
Sarah Zelikovitz and Haym Hirsh. Improving short text classification using unlabeled background knowledge to assess document similarity. In Proceedings of the seventeenth international confer- on machine learning, volume 2000, pp. 1183-1190, 2000.
356
Xiaohua Zhai, Avital Oliver, Alexander Kolesnikov, and Lucas Beyer. S41: Self-supervised semi-
357
supervised learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), October 2019.
358
369
Tong Zhang. Statistical analysis of some multi-category large margin classification methods. Journal of Machine Learning Research, 1225:):2225-2111 2004.
360
Zhilu Zhang and Mert Sabuncu. Generalized eross entropy loss for training deep neural networks with noisy labels. In Advances in neural information processing systems, pp. 3778-8788, 2018.
363


Reviews:
[{"review_id": "V_OExJ8mev5", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents (two) simple yet insightful sufficient conditions for a usual loss to work well as a complementary label loss. Based on this, a simple training procedure, which minimally differs from usual training, is presented. Empirically it is shown that the proposal outperforms state-of-the-art.\n\nComments:\n1. I like the simple idea of CL-loss (8). Also the analysis 4.2, though simple, is elegant and insightful. For example, it helps to identify that MSE is not an ideal CL-loss.\n2. The improvement in performance over GA/PC/Fwd is impressive in table1.\n3. Overall, the write-up is well-organised; however at places I felt the presentation can be simplified a lot. sometimes it is because of grammar, sometime because of confusing notation, and sometimes because of too much reading between lines. For e.g., since (16) is an important step, more explanation seems necessary (notation further complicates the ease), e.g., in (26),(27) one-step reasons for verifying validness/non-validness as cl-loss may be helpful.\n4. Though conditions (10)/(20) are insightful for determining robustness, for a reader who is encountering them for the first time, it may help to intuitively explain the conditions.\n5. In fig1 why does training accuracy decrease with epochs?", "extra_scores": {}, "extra_text": {}}, {"review_id": "Oe0b3Sobol", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studied a new problem, that is, learning from complementary labels.  The goal is to predict a correct label for a given sample when only given complementary labels. On the basis of the ordinary-label learning, the authors defined \"robust loss functions\" for complementary-label learning:  a a loss function is called robust  loss function if minimizer of risk with complementary labels would be the same as with ordinary  labels. Then, they provided  two sufficient conditions for the robust loss function and a exclusion algorithm is provided for prediction. Experimental results show that the proposed method outperforms other methods in several datasets.\n\nOverall, the problem is interesting and important, and the proposed algorithm seems reasonable and effective. However, I think the paper could be improved from the following two aspects.\n\n1.I suggest to add ablation test to give a deep analysis about the effectiveness of the proposed algorithm.\n\n2.In Section 5.1, it is better to give more explanations about why the lower the validation accuracy, the better the classifier learns from the training set.\n\n3. What is the exact form of complementary label? Suppose there are k classes, or k labels. If we know that a sample does not belong to given k-1 classes, then we can deduce that it belongs to the rest one class.   So, it is important to specify the exact form of complementary label to show the necessity of complementary-label learning.", "extra_scores": {}, "extra_text": {}}, {"review_id": "IdSf90F0X_D", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper concerns the problem of learning from single-label supervision, when this label is known not to be the truth. This is called complementary label learning. Some loss functions are proposed that are claimed to have the same theoretical minimizer as the one for standard labelling. \n\nThe research agenda of the paper looks reasonable, even if it can be seen as a very specific instance of partial label learning (where one just considers the complement of the complementary label and tries to learn from it). A positioning with this latter approach therefore seems necessary. Also, after reading the paper, there are some unclarities left about the authors claim. Below are some more specific comments about that:\n\n* Introduction: it is claimed that getting complementary label is easier than getting true labels, however complementary labels have to be certainly false, and while there are indeed theoretically more wrong labels than right ones, it is not entirely clear whether getting certainly false labels is easier than getting true ones in practice. Are there applications or empirical studies demonstrating that? Most mentioned papers do not appear to have actually applied the setting. \n\n* Connection to partial label learning: the current framework can be seen as a peculiar case of partial label learning, as if I take a complementary label $\\overline{y}$, then its complement $\\mathcal{Y}\\setminus\\overline{y}$ is a partial label certainly containing the truth. It would then be necessary to connect the current work to this trend, for instance to Cour et al. \"Learning from partial labels\" (JMLR 2011) or the more recent works of, e.g., X Wu, ML Zhang \"Towards Enabling Binary Decomposition for Partial Label Learning.\". \n\n* Definition 2: I do not really follow definition 2. First, are \\theta^* and \\theta arbitrary parameters values? Why call it \\theta^* (suggesting some kind of optimality)? If   \\theta^* is a minimizer of one of the two losses, then either the premise or the conclusion is a tautology (making the definition kind of meaningless). \n\n* Proof of Theorem 1: I have some trouble with this definition. First, Equation (13) seems trivial if \\theta^* is the finite sample optimal model (also, why not identifying the search space with the space of parameters?). I also do not really follow the next line, as it is unclear how realistic it is to modify the parameters for just one instance? It is also unclear what is to be proven here, as \\inf \\sum \\geq \\sum \\inf, thus allowing for instance-specific parameters would always give something better than a global minimizer. In summary, I am not really convinced by this proof. \n\n* In the experiment, I wold expect a comparison with other approaches (complementary but also partial label learning), but more importantly with the optimal models obtained on learning from the initial true labels, if only to demonstrate that the proposed theorems are valid. The asymptotic accuracies displayed are also very far from state-of-art standards (less than half of it) for CIFAR 10, which seems to contradict the fact that complementary labels have the same minimizer (hence comparable performances) as the one obtained with true labels? \n\n* Finally, the paper contains an important numbers of typos or questionable grammatical structures. For instance in the first two pages only:\n- \"supper\" --> super\n- \"A complementary-label is only specific that the pattern\"\n- \"in some questions refer to private.\"\n- \"the best hyper-parameter by empirical risk since\" (by empirical risk minimisation)\n- \"can be summary as\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "4fW94VG_Hqa", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n=======\nThis paper deals with the problem of complementary label learning, that is, when we know the set of labels which a given observation does not belong to. In particular, the paper proposes a robust loss function and an algorithm for learning from complimentary labels. Results shown on MNIST and CIFAR datasets indicate the superior accuracy using the proposed loss function.\n\n\nComments:\n==========\nThe paper addresses an important problem but it is written in a hurry which makes it hard to assess its contribution. There are many typos and other writing issues in the paper. The experiments are also weak. Though, the theoretical results are interesting and improve the previous known results for complementary label learning along certain dimensions. \n\n\n1). Typically, in ML robust loss function means a loss function that is robust to outliers, e.g., the Huber Loss. However, the definition of robustness of loss function is different in this paper. However, in this paper it means if the loss function with ordinary and complementary labels has the same minimizer. I am unaware of this definition of robustness of a loss function as it seems very specific to the complementary label learning problem.\n\n\n2). The results in Table 2 are not an apples-to-apples comparison. The numbers for GA, PC, Fwd are copied directly from other papers. In order to be fair, they should also similar base models as the authors. For instance, GA used used MLP which is less complex than the model used by the authors. So, it is unclear whether the improved performance is due to the difference in base architecture or due to the proposed robust loss function. \n\n\nTypos: \n\nPage 1: \"However, label such a large-scale dataset is time-consuming...\"\nPage 1: \"In the view of label noise, complementary labels can also be view as...\"\nPage 3: \"...only complementary labels that specific the samples does not...\"\nMany others!", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: the paper undoubtedly tackles an interesting problem in the mainstream of learning with partial / unknown / weak / noisy / complementary labels. The authors have had a set of constructive suggestions and questions from the reviewers (and external comments), some positive, some negative. I find it a bit unsettling that to several major questions, the main feedback from the authors was a citation in the paper with no further action; (a) ablation tests of R2 end up in citing papers from a public comment, (b) R4 raised a key point in comment 2, with the links to partial labels learning. The authors’ answer is not satisfying as one would have hoped at least of a partial justification of the author’s approach in this context. The authors would have had time to develop at least elements of a formal comparison. Just citing the work is not enough; 

Decision: Reject