Year: 2020

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

text: In ordinary-label learning, the correct label is given to each training sample. 1 Similarly, a complementary label is also provided for each training sample in 2 complementary-label learning. A complementary label indicates a class that the 3 example does not belong to. Robust learning of classifiers has been investi- 4 gated from many viewpoints under label noise, but little attention has been paid 5 to complementary-label learning. In this paper, we present a new algorithm of 6 complementary-label learning with the robustness of loss function. We also pro- 7 vide two sufficient conditions on a loss function so that the minimizer of the risk 8 for complementary labels is theoretically guaranteed to be consistent with the min- 9 imizer of the risk for ordinary labels. Finally, the empirical results validate our 10 method’s superiority to current state-of-the-art techniques. Especially in cifar10, 11 our algorithm achieves a much higher test accuracy than the gradient ascent algo- 12 rithm, and the parameters of our model are less than half of the ResNet-34 they 13 used. 14

heading: 1 INSTRUCTION 15
text: Deep neural networks have exhibited excellent performance in many real-applications. Yet, their 16 supper performance is based on the correctly labeled large-scale training set. However, labeling 17 such a large-scale dataset is time-consuming and expensive. For example, the crowd-workers need 18 to select the correct label for a sample from 100 labels for CIFAR100. To migrate this problem, 19 reachers have proposed many solutions to learn from weak-supervision: Noise-label learning Li 20 et al. (2017); Hu et al. (2019); Lee et al. (2018); Xia et al. (2019), semi-supervised learning Zhai 21 et al. (2019); Berthelot et al. (2019); Rasmus et al. (2015); Miyato et al. (2019); Sakai et al. (2017), 22 similar-unlabeled learning Tanha (2019); Bao et al. (2018); Zelikovitz & Hirsh (2000), unlabeled- 23 unlabeled learning Lu et al. (2018); Chen et al. (2020a;b), positive-unlabeled learning Elkan & Noto 24 (2008); du Plessis et al. (2014); Kiryo et al. (2017), contrast learning Chen et al. (2020a;b), partial 25 label learning Cour et al. (2011); Feng & An (2018); Wu & Zhang (2018) and others. 26
We investigate complementary-label learning Ishida et al. (2017) in this paper. A complementary 27 Label is only indicating that the class label of a sample is incorrect. In the view of label noise, 28 complementary labels can also be viewed as noise labels but without any true labels in the training 29 set. Our task is to learn a classifier from the given complementary labels, predicting a correct label 30 for a given sample. Collecting complementary labels is much easier and efficient than choosing a 31 true class from many candidate classes precisely. For example, the label-system uniformly chooses a 32 label for a sample. It has a probability of 1k to be ordinary-label but k−1 k to be complementary-label. 33 Moreover, another potential application of complementary-label is data privacy. For example, on 34 some privacy issues, it is much easier to collect complementary-label than ordinary-label. 35
Robust learning of classifiers has been investigated from many viewpoints in the presence of label 36 noise Ghosh et al. (2017), but little attention paid to complementary-label learning. We call a loss 37 function robust if the minimizer of risk under that loss function with complementary labels would be 38 the same as that with ordinary labels. The robustness of risk minimization relies on the loss function 39 used in the training set. 40
This paper presents a general risk formulation that category cross-entropy loss (CCE) can be used to 41 learn with complementary labels and achieve robustness. We then offer some innovative analytical 42 results on robust loss functions under complementary labels. Having robustness of risk minimization 43
helps select the best hyper-parameter by empirical risk since there are no ordinary labels in the44 validation set. We conclude two sufficient conditions on a loss function to be robust for learning45 with complementary labels. We then explore some popular loss functions used for ordinary-label46 learning, such as CCE, Mean square error (MSE) and Mean absolute error (MAE), and show that47 CCE and MAE satisfy our sufficient conditions. Finally, we present a learning algorithm for learning48 with complementary labels, named exclusion algorithm. The empirical results well demonstrate the49 advantage of the theoretical results we addressed and verify our algorithm’s superiority to the current50 state-of-the-art methods. The contribution of this paper can be summarized as:51
• We present a general risk formulation that can be view as a framework to employing a52 loss function that satisfies our robustness sufficient condition to learn from complementary53 labels.54
• We conclude two sufficient conditions on a loss function to be robust for learning with55 complementary labels.56
• We prove that the minimizer of the risk for complementary labels is theoretically guaran-57 teed to be consistent with the minimizer of the risk for ordinary labels.58
• The empirical results validate the superiority of our method to current state-of-the-art meth-59 ods.60
2 RELATED WORKS61
Complementary-label refers to that the pattern does not belong to the given label. Learning from62 complementary labels is a new topic in supervised-learning. It was first proposed by Ishida et al.63 (2017). They conduct such an idea to try to deal with time-consuming and expensive to tag a large-64 scale dataset.65
In their early work Ishida et al. (2017), they assume the complementary labels are the same prob-66 ability to be selected for a sample. And then, based on the ordinary one-versus-all (OVA) and67 pairwise-comparison (PC) multi-class loss functions Zhang (2004) proposed a modifying loss for68 learning with complementary labels.69
Even though they provided theoretical analysis with a statistical consistency guarantee, the loss70 function met a sturdy restriction that needs to be symmetric (`(z) + `(−z) = 1). Such a severe71 limitation allows only the OVA and PC loss functions with symmetric non-convex binary losses.72 However, the categorical cross-entropy loss widely used in the deep learning domain, can not be73 employed by the two losses they defined.74
Later, Yu et al. (2018a) assume there are some biased amongst the complementary labels and75 presents a different formulation for biased complementary labels by using the forward loss cor-76 rection technique Patrini et al. (2017) to modify traditional loss functions. Their suggested risk77 estimator is not necessarily unbiased and proved that learning with complementary labels can the-78 oretically converge to the optimal classifier learned from ordinary labels based on the estimated79 transition matrix. However, the key to the forward loss correction technique is to evaluate the tran-80 sition matrix correctly. Hence, one will need to assess the transition matrix beforehand, which is81 relatively tricky without strong assumptions. Moreover, in such a setup, it restricts a small com-82 plementary label space to provide more information. Thus, it is necessary to encourage the worker83 to provide more challenging complementary labels, for example, by giving higher rewards to the84 specific classes. Otherwise, the complementary label given by the worker may be too evident and85 uninformative. For example, class three and class five are not class one evidently but is uninforma-86 tive. This paper focuses on the uniform (symmetric) assumption and study random distribution as a87 biased assumption (asymmetric or non-uniform).88
Based on the uniform assumption, Ishida et al. (2019) proposed an unbiased estimator with a general89 loss function for complementary labels. It can make any loss functions available for use, not only90 soft-max cross-entropy loss function, but other loss functions can also be utilized. Their new frame-91 work is a generalization of previous complementary-label learning Ishida et al. (2017). However,92 their proposed unbiased risk estimator has an issue that the classification risk can attain negative93 values after learning, leading to overfitting Ishida et al. (2019). They then offered a non-negative94 correction to the original unbiased risk estimator to improve their estimator, which is no longer95
guaranteed to be an unbiased risk estimator. In this paper, our proposed risk estimator is also not 96 unbiased, but the minimizer of the risk for complementary labels is theoretically guaranteed to be 97 consistent with the minimizer of the risk for ordinary labels, both uniform and non-uniform. 98

heading: 3 PRELIMINARIES 99
text: 3.1 LEARNING WITH ORDINARY LABELS 100
In the context of learning with ordinary labels, let X ⊂ Rd be the feature space and Y = {1, · · · , k} 101 be the class labels. A multi-class loss function is a map: L(fθ(x), y) : X × Y → R+ . A classifier 102 can be presented as: 103
h(x) = arg max i∈[k]
f (i) θ (x) , (1)
where fθ(x) = (f (1) θ (x), · · · , f (k) θ (x)), θ is the set of parameters in the CNN network, f (i) θ (x) is 104 the probability prediction for the corresponding class i. Even though h(x) is the final classifier, we 105 use notation of calling fθ(x) itself as the classifier. Given dataset S = {(xi, yi)}Ni , together with a 106 loss function L, ∀fθ ∈ F (F is the function space for searching), L-risk is defined as: 107
RSL(fθ) = ED [L(fθ(x), y)] = ES [L(fθ(x), y)] , (2)
Some popular multi-class loss functions are CCE, MAE, MSE. Specifically, 108
` (fθ(x), y) = ` (u, y) =  ∑k i=1 e (i) y log 1 µy = log 1µy CCE, ‖ey − u‖1 = 2− 2µy MAE,
‖ey − u‖22 = ‖u‖ 2 2 + 1− 2µy MSE,
(3)
where u = fθ(x) = (µ1, · · · , µk), and ey is a one-hot vector that the y-th component equals to 1, 109 others are 0. The goal of multi-class classification is to learn a classifier fθ(x) that minimize the 110 classification riskRSL with multi-class loss L . 111
3.2 LEARNING WITH COMPLEMENTARY LABELS 112
In contrast to the ordinary-label learning, the complementary-label (CL) dataset contains only labels 113 indicating that the class label of a sample is incorrect. Corresponding to the ordinary labels dataset 114 S, the independent and identically distributed (i.i.d.) complementary labels dataset denoted as: 115
S̄ = {(x, ȳ)}Ni , (4) where N is the size of the dataset S̄, and ȳ represents that pattern x does not belong to class-ȳ . 116 The general labels’ distribution of dataset S̄ is as: 117
P (ȳ|y) =  0 p12 . . . p1k p21 0 . . . p2k
... ...
. . . ...
pk1 . . . pk(k−1) 0  k×k,
(5)
where pij denotes that the probability of the i-th class’s pattern x labeled as j, ∑k j=1 pij = 118 1, pij 6=0, j 6= i. Supposing that the label system uniformly select a label from {1, · · · , k} \ {y} 119 for each sample x, then the Eq. (5) becomes 120
P (ȳ|y) =  0 1k−1 . . . 1 k−1 1 k−1 0 . . . 1 k−1
... ...
. . . ...
1 k−1 . . . 1 k−1 0  k×k .
(6)
Yu et al. (2018b) make a strong assumption that there are some bias in Eq. (5), while Ishida 121 et al. (2017; 2019) focus on the assumption of Eq. (6). In this paper, we study both kinds of distri- 122 bution. 123
4 METHODOLOGY124
In this section, we firstly propose a general risk formulation for leaning with complementary labels.125 And then prove that some loss functions designed for the ordinary labels learning are robust to126 complementary labels with our risk formulation, such as categorical cross-entropy loss and mean127 absolute error.128
4.1 GENERAL RISK FORMULATION129
The goal of learning with complementary labels is to learn a classifier that predicts a correct label for130 any sample drawn from the same distribution. Because there are not ordinary labels for the model,131 we need to design a loss function or model for learning with complementary labels. The key to learn-132 ing a classifier for ordinary label learning is to maximize the true label’s predict-probability. One133 intuitive way to maximize the true label’s predict-probability is to minimize the predict-probability134 of complementary labels. In this paper, with little abuse of notation, we let135
u = fθ(x) = (µ1, · · · , µk) v = 1− fθ(x) = (1− µ1, · · · , 1− µk) .
(7)
Definition 1. (CL-loss) Together with loss function ` designed for the ordinary-label learning, the136 loss for learning with complementary-label is as:137
¯̀(fθ(x), ȳ) = ¯̀(u, ȳ) = `(v, ȳ) . (8)
4.2 THEORETICAL RESULTS138
Definition 2. (Robust loss) In the framework of risk minimization, a loss function is called robust139 loss function if minimizer of risk with complementary labels would be the same as with ordinary140 labels, i.e.,141 RS̄¯̀ (fθ∗)−RS̄¯̀ (fθ) ≤ 0⇒ RS` (fθ∗)−RS` (fθ) ≤ 0 . (9) Theorem 1. Together with `, ¯̀ is a robust loss function for learning with complementary labels, if ¯̀142 satisfies:143
∂ ¯̀(u, ȳ)
∂µȳ > 0,
∂ ¯̀(u, ȳ)
∂µi = 0, ∀i ∈ {1, · · · , k} \ {ȳ} . (10)
Note that, in Eq. 10, it means that ¯̀ is a monotone increasing loss function only on u(ȳ).144
Proof. Recall that for any fθ, and any `,145
RS` (fθ) = E(x,y) [` (fθ(x), y)] = 1 |S| ∑
(x,y)∈S
` (fθ(x), y) . (11)
For any complementary-label distribution in Eq. (5), and any loss function `, we have146 RS̄¯̀ (fθ) = E(x,ȳ) [ ¯̀(fθ(x), ȳ) ] = 1
|S̄| k∑ i=1 ∑ x∈Si k∑ j 6=i pij ¯̀(fθ(x), j) , (12)
where pij is the component of complementary labels distribution matrix P , S1 ∪ · · · ∪ Sk = S .147 Supposing that fθ∗ is the optimal classifier learns from the complementary labels, and ∀f ∈ F ,148 where F is the function space for searching, we have149
RS̄¯̀ (fθ∗)−RS̄¯̀ (fθ) = 1
|S̄| k∑ i=1 ∑ x∈Si k∑ j 6=i pij ( ¯̀(fθ∗(x), j)− ¯̀(fθ(x), j) ) ≤ 0, (13)
where pij 6= 0. If ∃x ′ ∈ S̄, s.t., ¯̀(fθ∗(x ′ ), ȳ) > ¯̀(fθ(x ′ ), ȳ), let fθ′ satisfying150
fθ′ (x) =
{ fθ∗(x) x ∈ S̄ \ {x
′}, fθ(x) x = x ′ ,
(14)
then according to Eq. 12 and 13, RS̄¯̀ (fθ′ ) < RS̄¯̀ (fθ∗), fθ∗ is not the optimal classifier. This 151 contradicts the hypothesize that fθ∗ is the optimal classifier. 152
Thus, ∀ȳ ∈ {1, · · · , k} \ {y}, we have 153 ¯̀(fθ∗(x), ȳ) ≤ ¯̀(fθ(x), ȳ) . (15)
According to Eq. (10), ¯̀ is a monotone increasing loss function only on u(ȳ), then we have 154
∀ȳ ∈ {1, · · · , k} \ {y}, f (ȳ)θ∗ (x) ≤ f (ȳ) θ (x) . (16)
Thus, 155
f (y) θ∗ (x) ≥ f (y) θ (x), f (y)θ (x) = 1−∑ ȳ 6=y f (ȳ) θ (x)  (17) and then, 156 `(fθ∗(x), y) ≤ `(fθ(x), y), (18) thus, 157
RS` (fθ∗)−RS` (fθ) ≤ 0 . (19)
158
Theorem 2. Together with `, ¯̀ is a robust loss function for learning with complementary labels 159 under symmetric distribution or uniform distribution, if ¯̀satisfies: 160
∂ ¯̀(u, ȳ)
∂µȳ > 0, k∑ i=1 ¯̀(u, i) = C, (C is a constant) . (20)
It should be noted that, in Eq. 20, it means that ¯̀ is a symmetric loss ( ∑ `(u, i) = C), and ¯̀ is a 161 monotone increasing loss function on any ȳ. 162
Proof. For any complementary-label distribution in Eq. (6), and any loss function `, we have 163 RS̄¯̀ (fθ) = E(x,ȳ) [ ¯̀(fθ(x), ȳ) ] = 1
|S̄| k∑ i=1 ∑ x∈Si k∑ j 6=i 1 k − 1 ¯̀(fθ(x), j)
= 1
|S̄| k∑ i=1 ∑ x∈Si 1 k − 1 ( C − ¯̀(fθ(x), i) ) = C
k − 1 −RS¯̀ (fθ),
(21)
where S1 ∪ · · · ∪ Sk = S . 164 Supposing that fθ∗ is the optimal classifier learns from the complementary labels, and ∀f ∈ F , 165 where F is the function space for searching, we have 166
RS̄¯̀ (fθ∗)−RS̄¯̀ (fθ) = RS¯̀ (fθ)−RS¯̀ (fθ∗) ≤ 0, (22) According to the first constraint in Eq. (20), we then have 167
¯̀(fθ(x), y) ≤ ¯̀(fθ∗(x), y), ( f (y) θ (x) ≤ f (y) θ∗ (x) ) (23)
and then, 168 `(fθ∗(x), y) ≤ `(fθ(x), y), (24)
thus, 169 RS` (fθ∗)−RS` (fθ) ≤ 0 . (25)
170
Algorithm 1 Learning from complementary labels by exclusion

heading: Require:
text: S̄ = {(xi, ȳi)}Ni : The given dataset; Ensure: Classifier fθ (x) 1: Randomly initialize a group parameter θ for fθ (x); 2: Randomly split S̄ into a training set S̄train and a valid-set S̄valid; 3: for (e = 1; e ≤ Epochs; e+ +) do 4: for (xi, ȳi) in S̄train do 5: fθ(xi) = (µ1, · · · , µk); 6: u = 1− fθ(xi) = (1− µ1, · · · , 1− µk); 7: loss = `(u, ȳi); 8: w = w − β ∂lossw , w ∈ θ; 9: end for 10: end for 11: return fθ (x)
Together with some well known multi-class loss functions, such as CCE, MAE, MSE, the loss for171 learning with complementary labels with our definition are as follows:172
¯̀(fθ(x), ȳ) = ` (v, ȳ) =  ∑k i=1 e (i) ȳ log 1 1−µi = log 1 1−µȳ CCE, ‖eȳ − v‖1 = k − 2 + 2µȳ MAE,
‖eȳ − v‖22 = k − 3 + ‖u‖ 2 2 + 2µȳ MSE,
(26)
where eȳ is a one-hot vector that the ȳ-th component equals to 1, others are 0. As its shown in173 Eq. (26), CCE and MAE loss satisfy the Theorem 1, MAE also satisfies the Theorem 2, while MSE174 does not satisfies the two. Zhang & Sabuncu (2018) propose a GCE loss function for learning with175 label noise, their formulation is as:176
`GCE (fθ(x), y) =
( 1− µqy ) q , q ∈ (0, 1) . (27)
It is easily to know that the loss function satisfies the constraint in Theorem 1, thus, it can be used177 to learning with complementary labels.178
4.3 EXCLUSION ALGORITHM FOR LEARNING FROM COMPLEMENTARY LABELS179
Based on the loss function we designed for complementary-label learning, we present an algorithm180 to learn a classifier from complementary labels with our loss function, named exclusion algorithm181 (the label specifies that the sample does not belong to it). The algorithm details show in Alg. 1.182 Furthermore, our algorithm is easily combined with the models designed for ordinary-label learning,183 with only a minus operation, which can be view as a framework to use the loss designed for ordinary-184 label learning to learn the optimal classifier from complementary labels.185
5 EXPERIMENTS186
5.1 EXPERIMENTAL SETTINGS187
Datasets. We test our experiments on MNIST LeCun et al. (1998), FASHION-MNIST Xiao et al.188 (2017), CIFAR10 Krizhevsky (2009). Specifically, we generate two types of complementary labels:189 symmetric and asymmetric, for our experiments to verify our method’s effectiveness and the theorem190 we proved in the previous section. For symmetric complementary-label, we fix a label distribution as191 Eq. (6) to generate the complementary-label training set. The validation set is split from the training192 set, which contains none ordinary-label. Thus, the lower the validation accuracy, the better the193 classifier learns from the training set. For asymmetric complementary-label, we randomly generate194 a matrix as Eq. (5) that the pij is unknown as the complementary-label distribution and using it195
to create complementary-label for experiments. The test accuracy of all experiments is tested on a 196 clean dataset that contains only the ordinary labels. 197
Approaches. We test our loss with ¯̀CCE, ¯̀MAE, ¯̀MSE, ¯̀GCE and compare with state-of-the-art meth- 198 ods in learning with complementary labels. The loss functions we used or compare in this paper 199 are listed as follows. 1) CCE: The categorical cross-entropy loss, neither symmetric nor bounded, 200 which widely use in machine learning and deep learning due to its fast convergence speed. 2) MAE: 201 The mean absolute error, a symmetric loss and bounded, has been proved Ghosh et al. (2017) to be 202 noise-tolerant. 3) MSE: The mean square error, not symmetric but bounded, widely used in regres- 203 sion learning. 4) GCE: It uses a hyper-parameter q to tune the loss between MAE and CCE, but 204 achieve noise-robust base on its bounded, we used the standard GCE where q=0.7 . 5) GA: Gradi- 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-label learning Ishida et al. (2017). 7) Fwd: 208 Forward correction Patrini et al. (2017), Yu et al. (2018a) designed for learning with complementary 209 labels. 210
Network architecture. Following Ghosh et al. (2017), we use a network architecture that contains 211 five layers to test the above methods for all the experiments: a convolution layer with 32 filters which 212 filter size set as (3,3), a max-pooling layer with pooling-size of (3,3) and strides of (2,2), two fully 213 connected layers with 1024 units, and a fully connected layer with soft-max activated function that 214 the unit number set to the category number for prediction. Rectified Linear Unit (ReLU) is used as 215 the activated function in the network’s hidden layer. 216
Implement details. The implementation detail of our method shows in Alg. 1. We train our network 217 with stochastic gradient descent through back-propagation. Each experiment trains 200 epochs, and 218 the mini-batch size was set to 64. To exploit each loss function’s best performance, we set three start 219 learning rate for each loss function on each experiment and report the best accuracy amongst the 220 three learning rate of each loss function. CCE is set to [1e-3, 5e-4, 1e-4], while GCE, MAE, MSE 221 is set to [1.0, 0.5, 0.1]. The learning rate was halved per 50 epochs. 222
5.2 EXPERIMENTAL RESULTS 223
Robustness. As shown in Fig. 1, together with CCE, MAE, and GCE loss, our algorithm achieves 224 strong robust to both symmetric and asymmetric complementary labels, which verify that the robust- 225 ness we prove in the Theorem 1 and Theorem 2. Even though the MAE satisfies the two theorems, 226
it achieves a lower test accuracy than that of CCE and GCE due to it treats all labels the same (not227 sensitive to the labels). The subfigures in the last column of Fig. 1 shows that the MSE loss firstly228 achieves its highest test accuracy and then drop sharply over the epochs. Because MSE does not229 satisfy one of the two theorems we prove, it easily overfits the training set’s complementary labels.230 Such a trend is the same as asymmetric complementary labels learning. The results verify that the231 algorithm we design for the complementary labels is significant and confirms the theoretical results232 we analyzed in the previous section.233
Performance Comparison. The first four columns of Table. 1 show that the CCE and GCE loss234 achieve the best two test accuracies in our algorithm. In the MNIST dataset, the CCE achieves235 a little lower test accuracy than GCE, the same test accuracy in FASHION-MNIST, and a little236 higher test accuracy in CIFAR10 due to the dataset more challenge and CCE is more sensitive to237 labels. Even MAE is robust to complementary labels, and its performance is not well than others238 because it is a linear loss that is not sensitive to labels. As shown in Fig. 1, MSE is not robust to239 complementary labels, but with a small learning rate of 0.1, MSE only exhibited slight overfitting in240 Table 1. Furthermore, as shown in Table 1, together with CCE and GCE loss, our algorithm achieves241 a test accuracy higher than 95% in the MNIST dataset, which is comparable to that of learning with242 ordinary labels.243
For a fair comparison, The last three columns directly form Ishida et al. (2019) even those results244 are the max test accuracy. In the first two datasets, all loss functions with our algorithm achieve a245 higher test accuracy than GA, but they used an MLP model as their base model, simpler than ours.246 In CIFAR10, they used ResNet-34 (21.62M parameters) He et al. (2016) and DenseNet Huang et al.247 (2017) as their based model, which is much bigger than ours (8.43M parameters), but we achieve a248 much higher test accuracy than theirs. The results validate the superiority of our algorithm to current249 state-of-the-art methods.250
6 CONCLUSION251
This paper designs an algorithm for learning from complementary labels using the loss functions252 designed for ordinary-label learning. We provide theoretical analysis to show that the loss func-253 tions we design for learning from the complementary labels are robust to the complementary labels,254 i.e., the optimal classifier learned from the complementary labels can theoretically converge to the255 optimal classifier learned from ordinary labels. In this paper, the two theorems we present are the256 sufficient condition of a loss function robust to complementary labels. Experimental results show257 that though complementary-label learning is a new topic in supervised-learning, it offers excellent258 competitiveness. More methods should be studied to improve the performance of complementary259 learning in our future works, such as Amid et al. (2019b) and Amid et al. (2019a).260
REFERENCES 261
Ehsan Amid, Manfred K. Warmuth, and Sriram Srinivasan. Two-temperature logistic regression 262 based on the tsallis divergence. volume 89 of Proceedings of Machine Learning Research, pp. 263 2388–2396. PMLR, 2019a. 264
Ehsan Amid, Manfred K. K Warmuth, Rohan Anil, and Tomer Koren. Robust bi-tempered logistic 265 loss based on bregman divergences. In Advances in Neural Information Processing Systems, 266 volume 32, pp. 15013–15022, 2019b. 267
Han Bao, Gang Niu, and Masashi Sugiyama. Classification from pairwise similarity and unlabeled 268 data. volume 80 of Proceedings of Machine Learning Research, pp. 452–461, Stockholmsmässan, 269 Stockholm Sweden, 10–15 Jul 2018. PMLR. 270
David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A 271 Raffel. Mixmatch: A holistic approach to semi-supervised learning. In H. Wallach, H. Larochelle, 272 A. Beygelzimer, F. Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information 273 Processing Systems 32, pp. 5049–5059. Curran Associates, Inc., 2019. 274
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for 275 contrastive learning of visual representations. arXiv preprint arXiv:2002.05709, 2020a. 276
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey Hinton. Big self- 277 supervised models are strong semi-supervised learners. arXiv preprint arXiv:2006.10029, 2020b. 278
Timothee Cour, Ben Sapp, and Ben Taskar. Learning from partial labels. The Journal of Machine 279 Learning Research, 12:1501–1536, 2011. 280
Marthinus C du Plessis, Gang Niu, and Masashi Sugiyama. Analysis of learning from positive and 281 unlabeled data. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger 282 (eds.), Advances in Neural Information Processing Systems 27, pp. 703–711. Curran Associates, 283 Inc., 2014. 284
Charles Elkan and Keith Noto. Learning classifiers from only positive and unlabeled data. In 285 Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and 286 Data Mining, pp. 213–220. Association for Computing Machinery, 2008. 287
Lei Feng and Bo An. Leveraging latent label distributions for partial label learning. In IJCAI, pp. 288 2107–2113, 2018. 289
Aritra Ghosh, Himanshu Kumar, and P. S. Sastry. Robust loss functions under label noise for deep 290 neural networks. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 291 AAAI’17, pp. 1919–1925. AAAI Press, 2017. 292
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- 293 nition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition 294 (CVPR), June 2016. 295
Mengying Hu, Hu Han, Shiguang Shan, and Xilin Chen. Weakly supervised image classification 296 through noise regularization. In Proceedings of the IEEE/CVF Conference on Computer Vision 297 and Pattern Recognition (CVPR), June 2019. 298
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected 299 convolutional networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern 300 Recognition (CVPR), July 2017. 301
Takashi Ishida, Gang Niu, Weihua Hu, and Masashi Sugiyama. Learning from complementary 302 labels. In Advances in neural information processing systems, pp. 5639–5649, 2017. 303
Takashi Ishida, Gang Niu, Aditya Menon, and Masashi Sugiyama. Complementary-label learning 304 for arbitrary losses and models. In International Conference on Machine Learning, pp. 2971– 305 2980. PMLR, 2019. 306
Ryuichi Kiryo, Gang Niu, Marthinus C du Plessis, and Masashi Sugiyama. Positive-unlabeled307 learning with non-negative risk estimator. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach,308 R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing309 Systems 30, pp. 1675–1685. Curran Associates, Inc., 2017.310
A Krizhevsky. Learning multiple layers of features from tiny images. Master’s thesis, University of311 Tront, 2009.312
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to313 document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998.314
Kuang-Huei Lee, Xiaodong He, Lei Zhang, and Linjun Yang. Cleannet: Transfer learning for315 scalable image classifier training with label noise. In Proceedings of the IEEE Conference on316 Computer Vision and Pattern Recognition (CVPR), June 2018.317
Yuncheng Li, Jianchao Yang, Yale Song, Liangliang Cao, Jiebo Luo, and Li-Jia Li. Learning from318 noisy labels with distillation. In Proceedings of the IEEE International Conference on Computer319 Vision (ICCV), Oct 2017.320
Nan Lu, Gang Niu, Aditya Krishna Menon, and Masashi Sugiyama. On the minimal supervision for321 training any binary classifier from only unlabeled data. In International Conference on Learning322 Representations, 2018.323
T. Miyato, S. Maeda, M. Koyama, and S. Ishii. Virtual adversarial training: A regularization method324 for supervised and semi-supervised learning. IEEE Transactions on Pattern Analysis and Machine325 Intelligence, 41(8):1979–1993, 2019.326
Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu. Making327 deep neural networks robust to label noise: A loss correction approach. In Proceedings of the328 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.329
Antti Rasmus, Mathias Berglund, Mikko Honkala, Harri Valpola, and Tapani Raiko. Semi-330 supervised learning with ladder networks. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama,331 and R. Garnett (eds.), Advances in Neural Information Processing Systems 28, pp. 3546–3554.332 Curran Associates, Inc., 2015.333
Tomoya Sakai, Marthinus Christoffel du Plessis, Gang Niu, and Masashi Sugiyama. Semi-334 supervised classification based on classification from positive and unlabeled data. volume 70335 of Proceedings of Machine Learning Research, pp. 2998–3006, International Convention Centre,336 Sydney, Australia, 06–11 Aug 2017. PMLR.337
Jafar Tanha. A multiclass boosting algorithm to labeled and unlabeled data. International Journal338 of Machine Learning and Cybernetics, 10(12):3647–3665, 2019.339
Xuan Wu and Min-Ling Zhang. Towards enabling binary decomposition for partial label learning.340 In IJCAI, pp. 2868–2874, 2018.341
Xiaobo Xia, Tongliang Liu, Nannan Wang, Bo Han, Chen Gong, Gang Niu, and Masashi Sugiyama.342 Are anchor points really indispensable in label-noise learning? In H. Wallach, H. Larochelle,343 A. Beygelzimer, F. Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information344 Processing Systems 32, pp. 6838–6849. Curran Associates, Inc., 2019.345
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark-346 ing machine learning algorithms. arXiv 1708.07747, 2017.347
Xiyu Yu, Tongliang Liu, Mingming Gong, and Dacheng Tao. Learning with biased complementary348 labels. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 68–83,349 2018a.350
Xiyu Yu, Tongliang Liu, Mingming Gong, and Dacheng Tao. Learning with biased complementary351 labels. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 68–83,352 2018b.353
Sarah Zelikovitz and Haym Hirsh. Improving short text classification using unlabeled background 354 knowledge to assess document similarity. In Proceedings of the seventeenth international confer- 355 ence on machine learning, volume 2000, pp. 1183–1190, 2000. 356
Xiaohua Zhai, Avital Oliver, Alexander Kolesnikov, and Lucas Beyer. S4l: Self-supervised semi- 357 supervised learning. In Proceedings of the IEEE/CVF International Conference on Computer 358 Vision (ICCV), October 2019. 359
Tong Zhang. Statistical analysis of some multi-category large margin classification methods. Journal 360 of Machine Learning Research, 5(Oct):1225–1251, 2004. 361
Zhilu Zhang and Mert Sabuncu. Generalized cross entropy loss for training deep neural networks 362 with noisy labels. In Advances in neural information processing systems, pp. 8778–8788, 2018. 363

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

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.