Consistent Multi-Class Classification from Multiple Unlabeled Datasets
Authors: Zixi Wei
Senlin Shu
Yuzhou Cao
Hongxin Wei
Bo An
Lei Feng
Venue: ICLR 2024 spotlight (2024)
Keywords: mutli-class classification
multiple unlabeled datasets
learning consistency
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We conduct a comprehensive study for multi-class classification from multiple unlabeled datasets by proposing consistent learning methods.

Abstract: Weakly supervised learning aims to construct effective predictive models from imperfectly labeled data. The recent trend of weakly supervised learning has focused on how to learn an accurate classifier from completely unlabeled data, given little supervised information such as class priors. In this paper, we consider a newly proposed weakly supervised learning problem called multi-class classification from multiple unlabeled datasets, where only multiple sets of unlabeled data and their class priors (i.e., the proportions of each class) are provided for training the classifier. To solve this problem, we first propose a classifier-consistent method (CCM) based on a probability transition matrix. However, CCM cannot guarantee risk consistency and lacks of purified supervision information during training. Therefore, we further propose a risk-consistent method (RCM) that progressively purifies supervision information during training by importance weighting. We provide comprehensive theoretical analyses for our methods to demonstrate the statistical consistency. Experimental results on multiple benchmark datasets and various prior matrices demonstrate the superiority of our proposed methods.

Published as a conference paper at ICLR 2024
CONSISTENT MULTI-CLASS CLASSIFICATION FROM MULTIPLE UNLABELED DATASETS
Zixi Wei
Senlin Shu" !t Yuzhou Cao² Hongxin Wei
Bo An
Lei Feng"*
Chongging University 2Nanyang Technological University
Soothern University of Science and Technology 'Skywork AI
{zixiwei, senlinshul @stu.. cqu. edu, cn, yuzhoubo2@..ntu. weihxxsustechh. edu, en, boanêntu. edu. sg, Ifenggaa@@mail............... com
sg
ABSTRACT
Weakly supervised learning aims to construct effective predictive models from imperfectly labeled data. The recent trend of weakly supervised learning has fo- cused on how to learn an accurate classifier from completely unlabeled data, given little supervised information such as class priors. In this paper, consider newly proposed weakly supervised learning problem called multi-class classifica- tion from multiple unlabeled datasets, where only multiple sets of unlabeled data and their class priors (i.e., the proportion of each class) are provided for training the classifier. To solve this problem, we first propose a classifier-conse consistent method (CCM) based on probability transition function. However, CCM cannot guar- antee risk consistency and lacks of purified supervision information during train- ing. Therefore, we further propose risk-consistent method (RCM) that progres- sively purifies supervision information during training by importance weighting. We provide comprehensive theoretical analyses for our methods to demonstrate the statistical consistency. Experimental results on multiple benchmark datasets across various settings demonstrate the superiority of our proposed methods.
INTRODUCTION
Deep learning techniques have achieved great success in a variety of application domains (LeCun et al., 2015), while they heavily rely large-scale fully labeled training data. In real- world scenar- ios, collecting such strong supervision could be costly, because accurate manual annotations are ex- pensive and time-consuming. Such challenge motivated extensive research on weakly supervised learning, which aims to learn satisfactory predictive models with weak supervision. According to the different types of weak supervision, various learning problems are included in the framework of weakly supervised learning, such as supervipe learning (Miyato et al., 2018), noisy-label learning (Han et al., 2018), and partial-labor learning (Wang et al., 2022).
In this paper, we consider another challenging weakly supervised learning problem (Tang et al., 2022) called multi-class classification from multiple unlabeled datasets (MCMU in short), where the goal is to learn a multi-class classifier from multiple unlabeled datasets with only class-prior probabilities (each probability indicates the proportion of examples belonging to each class). These class-prior probabilities are essential and are the sole supervision information used in this work, without which the MCMU problem becomes fully unsupervised. The MCMU problem could be frequently encountered in many real-world scenarios. For example, it is important to predict the demographic information of users in social networks for practical policy-making (Culotta et al., 2015). But due to the data privacy, collecting the information of individual users may be prohibitive. Fortunately, it easier to obtain multiple unlabeled datasets, with their class priors collected from pre-existing census data. In this case, the studied MCMU problem can be naturally suited.
This MCMU problem stems from classical problem called learning from label proportions (LLP) (Yu al., 2014; Liu al., 2019), while there are significant differences between our work and
'Euual contribution.
*Corresponding author.

---

Published as a conference paper at ICLR 2024
Table 1: Comparisons of our proposed method with previous studies on relevant problem setrings.
Deal with
Deal with
Theoretical
No negative training risk
Risk
Methods
2+ class
2+ sets guarantee
measure
Lu et al. (2019)
x
x
Classification risk
Menon et al. (2015)
Balanced risk
Lu et al. (2020)
X
X
Classification risk
Zhang al. (2020b)
Balanced risk
Tsai & Lin (2020)
X
V
X
Proportion risk
Lu et al. (2021)
Classification risk
Tang et al. (2022)
X
Classification risk
Our proposed
Classification risk
previous L.P studies. In the problem setting of our work, the unlabeled sets are sampled from distributions with different class priors, while most previous LLP studies considered unlabeled sets sampled from the same distribution (Liu et al., 2019; Tsai & Lin, 2020). Besides, most previous deep LLP methods conducted empirical risk minimization (ERM) (Dery al., 2017; Tsai & Lin, 2020) at the proportion level, while we aim to conduct ERM at the instance level so that the learning consistency can be guaranteed. These differences make studied MCMU more applicable than LLP. For example, MCMU can learn from an extremely small number unlabeled sets, while most previous LLP methods that treat each set as a training unit cannot work well in this case.
The key challenge MCMU is how to derive effective risk estimators for conducting ERM at the instance level. To address this challenge, Tang et al. (2022) proposed unbiased risk estimator for MCMU so that the expected classification risk of fully supervised data can be unbiasedly estimated by given training data, which is also the sole work MCMU to the best of our knowledge. However, this method results in an unreasonable training objective caused by the negative empirical risk. Although partial-risk regularization term further proposed to alleviate the negative empirical risk issue, the unbiasedness of the risk estimator is actually broken, hence the theoretical guarantee cannot hold, and thus the performance still suboptimal.
To address the above limitations, we first propose flssifier-consiseee method (CCM) based on probability transition function. CCM can be considered as a multi-class extension of Lu et al. (2021) where they only studied the binary version of MCMU by solving surrogate set classification prob- lem with a probability transition function. However, CCM cannot guarantee risk consistency and fails to consider differentiating the true label of each training example, which could limit its pirical performance due to the lack any purified supervision information. Therefore, we further propose risk-consisten method (RCM) via importance weighting, which progressively pu- rify supervision information during the training process by dynamically calculating the weights to identify the true label of each training example.
The main contributions of our paper can be summarized as follows:
We propose a classifier-consistrr method (CCM) based on a probability transition function, which can be considered as multi-class extension of Lu et al. (2021).
We propose a risk-consistent method (RCM) via importance weighting. RCM is superior to CCM because it can hold risk consistency and progressively purify supervision information.
We provide comprehensive theoretical analyses for our proposed methods CCM and RCM to demonstrate their theoretical guarantees.
We conduct extensive experiments on benchmark datasets with various settings. Experimental results demonstrate that CCM works well but RCM consistently outperforms CCM.
2 RELATED STUDIES ON RELEVANT PROBLEM SETTINGS
In this section, we introduce necessary notations, related studies, and the problem setting of our work.
2

---

Published as a conference paper at ICLR 2024
2.1 MULTI-CLASS CLASSIFICATION FROM FULLY LABELED DATA
Let us begin with introducing the ordinary multi-class classification setting. Let the feature space be X' Rd and the label space be y [k], where d is a positive integer denotes the input dimension. [k] = (1.2..... ......,k .. where denotes the number of classes. Let æ E X be an instance and y E y be label, and each example (x, y) X' y assumed to be drawn from an underlying joint distribution with probability density p(z, y). The goal of multi-class classification is to learn
multi-class classifier f RR* that minimizes the classification risk defined
R(F) ((
(1)
where Bp(a.s) denotes the expectation over p(ar, v): and L I2* x y R., denotes multi-class classification loss (e.g., the softmax cross entropy loss), which measures the discrepancy between the classifier output f(x) and the true label y. Given the classifier f. the predicted label is given by
y = argmax,<(et Se (x), where fz()) is the j-th element of f(x).
2.2 LEARNING FROM LABEL PROPORTIONS
LLP (Yu et al., 2014; Liu et al., 2019) considers a problem where the supervision is given to set of data and the supervision the proportion of instances from each class in the set. This super- vision provides similar information compared with class priors. However, MCMU and LLP are significantly different from each other, and here we describe the differences between them:
From the distribution perspective: In MCMU, the unlabeled sets are sampled from distributions with different class priors, while the unlabeled sets in LLP are sampled from the same distribution.
From the generation perspective: In MCMU, the generation process of a data point is: class priors - ground truth label y - data point æ, while in LLP, the generation process is: set of data points X set of ground truth label
the proportion supervision.
From the dependence perspective: In MCMU, given the class priors, the data points in the same set independent on each other, while in LLP, given the label proportions, the data points in the same set are dependent from each other.
Most previous studies on trPtry to solve this problem by the empirical proportion risk minimization (ERPM) (Dery et al., 2017; Tsai & Lin, 2020), which aims minimize the distance between the approximated label proportion by the classification model and the truth label proportion. There are various approaches to measuring this distance, including squared error or KL-divergence for binary classification (Dery et al., 2017; Tsai & Lin, 2020) and cross-entropy for multi-class classification (Dulac-Amold al., 2019; Liu al., 2019).
2.3 PREVIOUS STUDIES ON CLASSIFICATION FROM UNLABELED DATASETS
Recent studies (Lu et al., 2019; Luo & Orabona, 2010) showed that it is possible to train binary classifier from only two unlabeled datasets with different class priors. Hence, many researchers began to investigate classification from unlabeled datasets (Scott & Zhang, 2020; Lu et al., 2021; Tang et al., 2022) and proposed effective solutions. However, compared with our study in this paper, these previous methods normally have the following limitations:
Limited to the binary classification: Most previous methods focus on the binary classification setting (Menon et al., 2015; Lu et al., 2019; Luo & Orabona, 2010; Zhang et al., 2020b; Scott & Zhang, 2020; Lu et al., 2021) and cannot deal with the multi-class classification setting.
Limited to the specific number of unlabeled sets: Some methods are limited to specific number of unlabeled sets, such as the number of unlabeled sets m 2 (Lu al., 2019; Luo & Orabona, 2010) or m = 2k (k N4) (Scott & Zhang, 2020).
Limited by the negative empirical risk: Some methods would encounter the negative empirical risk issue (Lu et al., 2019; Tsai & Lin, 2020; Tang al., 2022), i.e., the risk could empirically become negative during the training process. This poses a serious challenge to the optimization process since it is problematic to minimize objective that can be unbounded from below.
In work, focus multi-class classification from multiple unlabeled sets and the empirical risk of our proposed methods would never become negative. Table shows the comparisons of our work with previous studies relevant problem settings.
3

---

Published as a conference paper at ICLR 2024
2.4 MULTI-CLASS CLASSIFICATION FROM MULTIPLE UNLABELED DATASETS
Given m (m R 2) sets of unlabeled data == data points drawn from a mixture of class-conditional densities:
= UT_, U. where U, = ( P is a collection of ny
p(æ カ - i) Σ Oij x = j); Ui lid p.(x:)
where E mm and & Ozs & denotes the j-th class prior of the i-th unlabeled set, and y E ................................ m) denotes the index of the m sets of unlabeled instances.
We assume that these class priors form a full column rank matrix == (0t) E [0, [0.1] with the constraint - Ozj 1. Let denote the original class priors (the class priors over all m unlabeled sets), i.e., J pyy j) and Pj denote the probability of data point belonging to the i-th set, ie., Pi = p(g = i). Throughout the paper, we assume that the class priors of each unlabeled set are given, which means 0 is accessible. Then, xj and Pj could be estimated by شi n; 0.g/ >m= ni and nz/ - n, respectively. Although we can only access the unlabeled training sets U U4 our goal in this paper is to learn a multi-class classifier that can make accurate predictions on unseen individual instances.
3 THE PROPOSED CONSISTENT LEARNING METHODS
In this section, we present our two statistically consistent methods, i.e., the classiferr-cnniistet method (CCM) and the risk-consistent method (RCM). We say method is classifier-consiseent the learned classification model by this method would converge to the optimal classification model obtained by minimizing the classification risk in Eq. (1) and we say a method is risk-consistent this method holds a risk function that is exactly equivalent to the classification risk in Eq. (1), CCM can be viewed as a multi-class extension of Lu et al. (2021). I), following which we also consider the MCMU problem as surrogate set classification problem, i.e., to predict which unlabeled set instance belongs to. Then we theoretically showed that we can transform the posterior probabilities of ordinary labels to the posterior probabilities of surrogate sets, via a probability transition function. In this way, we can obtain the desired multi-class classifier from the learned surrogate set classifier. However, CCM suffers from both theoretical and practical limitations because cannot guarantce risk consistency and lacks purified supervision information.
Therefore, we further propose risk-consistent method (RCM). Concretely, we rewrite the risk shown in Eq. (1) into an equivalent form via importance weighting, which can well handle the given unlabeled datasets. RCM dynamically calculates the importance weights during the training process, which enables RCM to differentiate the true label of each training example and progressively purify supervision information during the training process. It is noteworthy that U-PRR (Tang al., 2022) is also method that holds risk consistency, which rewrites the classification risk by pseudo-inverse matrix. However, our proposed RCM is superior to U-PRR according to the following aspects: 1) RCM utilizes both the classifier information and the prior matrix information to dynamically cal- culate importance weights while U-PRR only statically calculates weights solely based on the prior matrix. 2) U-PRR suffers from the issue of negative empirical risk, while RCM intrinsically avoids this issue by using a non-negative risk estimator. 3) RCM does not involve any hyper-paramen parameters in the training objective while U-PRR needs tune several syper-pprameters for better training perfor- mance. 4) RCM consistently exhibits superior performance across various settings and demonstrates a substantial performance advantage in random matrix settings.
In many popular WSL (Weakly Supervised Learning) problems (such as partial-label learning (Wang al., 2022), noisy label learning (Han al., 2018), and multiple-instance learning (Zhou et al., 2009)), we could usually have access to weakly supervised labels. However, in the MCMU problem, neither a ground-trui trrth label nor a weakly supervised label is accessible for each training example, which makes the classification risk in Eq. (1) cannot be easily recovered from the unlabeled sets. To deal with this challenge, Lu et al. (2021) treated the indexes of the m sets as surrogate labels, which would be convenient for deriving meaningful training objective.
Following this strategy, by treating y as a surrogate label, we could transform the m sets unlabeled data Uh" 24 into D = ((x("), ((")))" where n is the total number of data points. Then, we could bridge the two posterior probabilities ply a:) and p(y ax) by the following lemma:
4

---

Published as a conference paper at ICLR 2024
Lemma 3.1. Let mzx)) and nfxx) be k-dimennsonal and m-dimensional probabilistic vectors spectively, where ()) and ()())) denote plu = j x) and p(ù x) respectively. Then we have
Pi 1_ j-1 Ozj 7)(0)
Pi ax m(x)
(x))
(2)
1 Li-1 Pi 12 Oij 2:(w)
B (2))
where a, = [a....... amk and auj
du and B = Di Ps ax.
The detailed derivation of Lemma 3.1 is provided in Appendix A.
3.1 CLASSIFIER CEELLFEER--CNSSTTEN CONSISTENT METHOD VIA PROBABILITY TRANSITION FUNCTION
For the classifier-consistett method, aim solve the surrogate classification problem by standard multi-class classification method. We use Ty (a) to denote the probability p = x),
which can be approximated by the softmax output of the classification model. As shown in Eq. (2),
(2) could be obtained by substituting næ). We define T(.) RR - R" as a transition function
represent this transformation, i.e., (7))) (=))) is noteworthy that the coefficients in T:(-) are all constant as shown in Eq. (2) and T(-) is deterministic. Then the learning objective of CCM
could be defined as
Reem (J) Pp(,,g) [()())))
(3)
worth noting that the loss function C here needs to handle probability vectors (e.g.. the cross entropy loss without the softmax processing). In this way, the empirical version of Reem(f] can be expressed as
Remm(() - n
Σ ((T(x()), g())
1=
The pscudo-code of the CCM is provided in Algorithm
Then, in order to prove that this method is classifier-consisten,, we introduce the following lemmas: Lemma 3.2. Let 0ig # Oie- Vi E [1....,m] m] and Vj.s s [1....,k]. Then, the transition function T()) is an injective function the domain [0. 1].
The proof is provided Appendix B.1. similar proof can also be found in Lu et al. (2021). Lemma 3.3. If certain loss functions are used (e.g., the softmax cross entropy loss), by minimizing the expected risk R(f)), the optimal mapping g" satisfies g, (x) p(y i|z>).
The proof is provided Appendix B.2. The same proof can also be found in (Yu al., 2018; Feng al., 2020). Then, have the following theorem.
Theorem 3.4. When the conditions in Lemma 3.2 and Lemma 3.3 are satisfied, the minimizer Seam = arg min sEF Room (f) is also the true minimizer f arg min R(J), ie., Soom S (classifier consistency).
The proof is provided in Appendix B.3.
Let feom = arg min ser Reem (f) be the empirical risk minimizer, and f = arg min the true risk minimizer. Besides, we define the function space Hy for the label E y as {h (x) f E F). Let R,, be the expected Rademacher complexity (Bartlett & Mendelson, 2002) of Hly with sample size n, then we have the following theorem.
feF R(f) be
Theorem 3.5. Let the loss function L(T(m(()), 7) be I' L'-Lipschitz with respect f(x) (0 L' c0) and bounded by C₁ i.e., SUPPex,,eeF.ett probability at least 8,
(T((())), & Cj Then for any ô > 0, with
&h Recun (eam)) Ream (f*) 4 >,,,, R. (H,y) + 20/
log 2
2n
The proof is provided in Appendix B.4. Generally, Rt, (Hyy) can be upper bounded by CH/ /n for
a positive constant Cr (Lu al., 2020; Golowich al., 2017). Theorem 3.5 demonstrates that the empirical minimizer from learned by CCM would convergent to the minimizer f learned from clean data the training sample size approaches infinity.
5

---

Published as a conference paper at ICLR 2024
3.2 RISK- CONSSSNNTTT METHOD VIA IMPORTANCE WEIGHTING
For the risk-consistent method, our strategy is to solve the MCMU problem by risk rewriting (Gret- ton al., 2009), i.e., transforming the classification risk into an equivalent form that be accessi- ble from multiple unlabeled sets with class priors.
Theorem 3.6. The classification risk R(f) in Eq. (1) can be equivalently expressed as follows:
* Rrem(S) Ep(a..) 1_,,, ply - j V. (.)
(5)
The proof of Theorem 3.6 is provided in Appendix C.I. worth noting that the loss function L here needs to handle logit vectors before the softmax processing (e.g., the softmax cross entropy loss). It can be observed that the Rrem works as an importance weighting loss due the probability function p(y
y, æ), and p(y belonging to class j.
D. x) indicates the probability of in ÿ-th unlabeled set
Here, p(y j 5, æ) can be calculated by
ply = j x) = p(ø y = j.0)p(y = j.
p(a y = j)p(y = j g)p(z)
p(..
P(U, a))
p(y=)(æ) ply-j)
ply - 1))(())
)2(m)) m,
0g:ps
xx)
0 3 n(x))
(6)
plū x)
7i (x)
y 17
The above derivation uses the fact that p(a | y = p(> y J. 7). since we could obtain the underlying class-conditions distribution independent from the surrogate label, given the true label. After obtaining the formulation of Rrem: its empirical version Ryom can be expressed
k Rera Σn_ (E, p(y = (0)
ox (0)) (((()(((())))))))
Now, the problem becomes how accurately estimate p(u j 8, v, since cannot not be di- rectly accessible from the unlabeled datasets. We apply the softmax function on the outputs of the
classification model (xx to approximate 7xx), concretely, we use (xp(f((x)) E exp( (x))) to approximate n) (a>). Then, by substituting the approximated vy (e) into Eq. (6). we could obtain the estimated p(y = j J. æ)) due to Eq. (6). The pseudo-code of RCM is shown in Algorithm 2.
From the theoretical perspective, RCM tries to recover the ordinary classification risk defined in Eq. (1) by using the estimated probability function p(y j æ). Hence we do not impose any restric- tions on the loss function C and the classification model f. and we could utilize classification mod- els in RCM. From the practical perspective, RCM works in importance-weighting manner. RCM synthesizes the surrogate label information and the classification model information to approximate the distribution of the ground truth label y. Specifically, when the estimated p(y = J g.x) is small, the label j is unlikely to be the ground truth label of the instance æ, then the weight ply = j 8, x) on the loss (() is small. In this way, the weights help the classification model identify the ground truth label and purify supervision information while the classification model also helps the method to obtain better estimated weights. These two procedures work alternately and reciprocate each other. We further provide a more detailed theoretical analysis of the influence between weights and classification models based on the EM algorithm. The analysis provided in Appendix C.2.
Furthermore, we derive a generalization error bound to theoretically analyze our RCM. Let frem = arg min Rrom (f) be the empirical risk minimizer. Besides, we define the function space H. for the label y E ) as (h : x - [y(x)) J F). Let (Hyy) be the expected Rademacher complexity (Bartlett & Mendelson, 2002) of H. with sample size n, then we have the following theorem.
Theorem 3.7. Let the used multi-class classification loss function ((((()), y) be L-Lipschitz with respect to [(x) (0 < ()) and bounded by Ct, iee, SuP (()()),)) v) & Ct. Then for any 8 > 0, with probability at least 1 1 6,
log 1
B Rremm (frem)) [] Ream (from) & 2V22L >",, Rr (H,,) + C
2n
6

---

Published as a conference paper at ICLR 2024
Algorithm 1 CCM Algorithm
Algorithm 2 RCM Algorithm
Input: Model f. class prior matrix 0, origi- nal class prior æ, surrogate class prior p. epoch Emax. iteration /ax unlabeled training set D
Input: Model f. class prior matrix 0, origi- nal class prior л, surrogate class prior p. epoch Emax. warmup epoch Ewam- iteration I un- labeled training set = ((x((), (((x)))(()))))) )(
((x=(), )=
1: for e e= 1, Emax do
1: Warmup f by CCM for Ewarm epochs;
2: Shuffle the unlabeled training set D
2: Initialize estimated p(y) ( g(") by
)()
Eq. (6);
3: for j 1, max do
3: for e 2,...... Fmax do
4: Fetch mini-batch D from D;
4: Shuffle D {(x(1)) )())) >
5: Calculate estimated ())) by sub-
for j 1,.... Imax do
Fetch mini-batch D, from Dj
stituting estimated ())))) into Eq. (2)
6: Update model f by minimizing the
7:
Update model f by Rrem in Eq. (7):
empirical risk estimator Reom in Eq. (4);
8:
Update estimated p(y|æ!0) 5) by
7: end for
Eq. (6);
8: end for
9:
end for
Output: f.
10:
end for Output: f.
The proof of Theorem 3.7 is provided in Appendix C.3. Theorem 3.7 demonstrates that the training error Brem (frem) would convergent to the generalization error EJ FLBrrom [fram] as the the training sample size approaches infinity.
Comparisions Between RCM and CCM. From theoretical perspective, RCM could approximate or simulate the distribution of real clean data by utilizing the data distribution from the unlabeled set (by the importanee-wiighting schema). This means that RCM attempts to infer latent distribution patterns similar to those of real clean data from the unlabeled data. In contrast, CCM aims to better fit the distribution of the unlabeled set by maximizing log- ligeliikldooo object. With sufficient number of samples, RCM is more accurate in predicting the labels of unseen samples because it considers the restoration of the distribution of real clean data when modeling unlabeled data. This enables RCM to exhibit better generalization performance when facing unknown data, making more precise predictions for unseen samples. More detailed descriptions and explanations of RCM and CCM are provided in Appendix D.
EXPERIMENTS
4.1 EXPERIMENTAL SETUP
Datasets. We use 5 popular benchmark datasets including MNIST (LeCun et al., 1998), Kuzushiji- MNIST (Clanuwat et al., 2018), Fasion-MNIST (Xiao et al., 2017), CIFAR1O (Krizhevsky al., 2009) and SVHN (Netzer et al., 2011). In the experiments, the number of data points in all sets the same, and the total number of training data points fixed, i.c., ni n2 = -h and m n. is equal to the size of the training dataset. The n. data points contained in i-th unlabeled set were randomly sampled according 0 02,2, ... 00.m without replacement. Since our methods is flexible on classification models, we apply 5-layer MLP on MNIST, Kuzushiji-MNIST and Fashion- MNIST and ResNet (He et al., 2016) is used on CIFARIO and SVHN. For fair comparison, we apply the same classification model on the same dataset for each method. More training details are reported in Appendix 1.
Class prior matrix. To better analyze the performance of our proposed methods, we construct different class prior matrices 0 in experiments. Previous studies on MCMU conduct experiments on the diagonal-dominated matrix or the matrix conducted by two diagonal-dominated matrices. For the m sets generated according to such a matrix, there exists at least one set U4, that the class accounts for the largest portion in U4 However, this setting is hard to apply in real-world scenarios. To better simulate real-world situations, we conduct experiments on both the diagonal-don dominated matrix and the non-diagonal-dominat random matrix.
7

---

Published as a conference paper at ICLR 2024
Table 2: Classification accuracy (mean+std) for each methods and Random in the table refer to Symmetric diagonal-dominatee matrix, Asymmetrie diagonal- dominated matrix, and Random matrix respectively. The best and comparable methods based on the paired t-test at the significance level 5% are highlighted in boldface.
10. Symmetric, Asymmetric,
Matrix
Datasets
MNIST
Fashion
Kuzushiji
CIFAR-10
SVHN
Supervised
98.15 0.05%
0.18%
0.18%
70.21 1: 0.43%
92.68
0.29%
Unbiased
25.34 22.65%
29.40 + 10.39%
15.81 + 12.21%
13.32 + 11.71%
11.35 + 16.07%
U-Stop
81.41 + 6.91%
71.40 5.100:554477 5.10%
54.16 8.27%
31.72 + 5.61%
25.01 = 11.06%
U-Correct
86,20 1 6.21%
76.82 3.98%
66.89 6.25%
39.14 +: 3.32%
68.09 9.85%
Symmetric
U-Flood
83.93 t 1.93%
17.33 3.36%
66.71 # 5.23%
36.31 + 3.00%
08:16 7.18%
Prop
85,99 1 5.84%
75.16
5.022
T3.32 4.97%
51.21 +: 4.12%
74.12 7.43%
U.PRR
80.37 6.98%
72.30
6.97%
67.79 1 7.54%
43.39
5.42%
69.08 8.51%
CCM
94.03 1.47%
83.37
1.88%
79.06
3.73%
60.06 + 5.01%
80.80
5.81%
RCM
94.28 +: 2.26%
82.81
3. 13%
78.91 : 3.87%
65.68 :: 4.88%
84,22 6.96%
Supervised
98.24 0.15%
88.68
0.12%
91.03 0.20%
71.91 1 0.85%
92.89
Unbiased
82.82 + 2.01%
70.53 1.45%
57.70 4.52%
18, + 1.04%%
09.37 2.41%
U-Stop
89.08 t 18%
79.51 0.59%
68.38 1 4.61%
48.38 +: 0.43
65.99 42%
U-Correet
94.56 + 0. 0.199%
83:43 0.27%
79.11 0.74%
19.80 + 1.87%
87.77 0.62%
Asymmetric
U-Flood
92.85 t 0.266%
82.41 0.59%
76.56 1.24%
50.60 + 0.93%
83. 14.14-1 0.58%
Prop
96.13 + 0. 0.22%
86.46 0.37%
$4.48 0.95%
61.60 1.33%
85. S1.14 0.63%
U-PRR
91.41 +: 0.36%
85.15 0.28%
81.91 1 0.47%
56.34 +: 1.1.1.1... 1.16%
81.91 0.74%
CCM
96.05 0.22%
85.24 0.43%
65.01 0.28%
67.73 +: 1.84%
88.25 0.77%
RCM
96.75 = 0.11%
85.87 0.13%
85.65 = 0.31%
74.55 =: 0.27%
92.03 0.40%
Supervised
97.97 0.13%
0.10%
0.13%
70.86 1:
92.43 0.22%
Unbiased
14.25 +: 4.55%
13.04 2.16%
11.9 + 0.825%
12.56 + 2.01%
10.11 1 1.70%
U-Stop
22.67 t 4.81%
46,70 + 23.55%
24.92 + 14.76%
18.63 + 2.341%
8.49 + 1.20%
U-Correct
25.23 9 9.32%
28.45 + 10%
17.48 4.44%
14.21 + 3.53%
11.13 2.92%
Random
U-Flood
78.93 16. 06%
71.79 38%
53.08 + 16.12% 12%
25.88 + 63%%
13. 4.50%
Prop
89.09 + 7.76
79.26 2.25%
67.12 2.58%
37.38 2.73%
59.56 8.%
U-PRR
26.56 3.79%
14.25 3.53%
21.79 1 2.45%
17.71
2.37%
10.05 2.31%
CCM
91.92 1.19%
78.07
4 6.38%
72.62 2.33%
42.31
2.99%
72.73 4.70%
RCM
95.04 1: 0.58%
81.11 2.13%
78.60 1: 2.61%
50.51 1 4.59%
78.70 7.88%
Symmetric diagonal-dominated square matrix: In this matrix, the largest element in each row is the element on the diagonal, and the rest elements in the same Concretely, the elements 8g are uniformly sampled from [1/k, 1] when = j. and set 0,y = (k, 1) when
completely identical.
Asymmetric diagonal-dominated square matrix: In this matrix, the elements on the diagonals of 0 are larger than the elements in the same row, i.c., 0g,, > Bzj. 1 & i,j & m, i * j and the non-diagonal elements in the same row may be not identical. Concretely, the class priors 0,g are uniformly generated from [1, 1/m] when * j. and 0z.; = 1 Ejes Ozj.
This matrix is a totally random matrix. Firstly, we uniformly generate each element in the matrix from [0, 17. then we assign each element 8ig the value oig/ >*m O. to ensure the summation of each row is equal to
Random matrix:
We conduct experiments not only on the square matrix but also the non-square matrix when m > Specifically, we set m = 2k and the non-square class- class-prior matrix is constructed by concatenating two squared matrices described above.
Compared methods. We compared our proposed methods with the following methods including Unbiased (Tang al., 2022), U-Stop (Tang et al., 2022), U-Correct (Tang et al., 2022), U-Flood (Tang et al., 2022), Prop (Yu et al., 2014), U-PRR (Tang et al., 2022). More detailed descriptions of the compared methods are shown in Appendix E.2.
4.2 EXPERIMENTAL RESULTS
The experimental results in Table. and Table. 3 respectively. To verify the robustness of the methods against the noisy prior matrix 8, variant set numbers and variant set sizes, we also provide additional experimental results in Appendix F. From Table 2 and Table 3, we could observe that our proposed RCM achieves the best performance and outperforms the other methods in most cases. In addition, RCM and
10 and 20 based on the 3 class prior matrices are shown
8

---

Published as a conference paper at ICLR 2024
Table 3: Classification accuracy (mean+ for each methods and Random in the table refer to Symmetric diagonal-dominatee matrix, Asymmetrie diagonal- dominated matrix, and Random matrix respectively. The best and comparable methods based on the paired t-test at the significance level 5% are highlighted in boldface.
20. Symmetric, Asymmetric,
Matrix
Datasets
MNIST
Fashion
Kuzushiji
CIFAR-10
SVHN
Supervised
98.20 0.22%
0.16%
90.64
0.39%
70.89 1: 1.17%
92.45
0.25%
Unbiased
57.02 + 13.03%
51.02 + 9.17%
36.42 + 6.45%
11.81%
40.87 # 17.06%
U-Stop
88, + 1.60%
80.03 1.38%
65.75 1.11%
12.82 + 236%
11.58 f: 11.35%
U-Correct
92.41 1.41%
82.06 1.51%
T4.10 3.83%
46.35 +: 3.15%
78.43 5.3%%
Symmetric
U-Flood
90.07 + 2.59%
81.16 1.44%
71.80 +: 3.13%
14.60 + 2.93%
78.13
5.2
Prop
$8.36 1 4.70%
79.71 3.59%
T4.12 5.16%
54.18 +: 4.54%
81.66 2.09%
U.PRR
85.75 1 4.74%
3.79% 78:23
70.08 1 6.05%
47.14 1 5.41%
74.96 5.34%
CCM
94.66 0.90%
84.07
1.19%
80.51 2.37%
59.71 + 2.33%
81.95
5.14%
RCM
95.47 = 0.72%
0.70% 84.54
81.56 1 2.17%
66.99 :: 3.28%
90.24 0.93%
Supervised
98.09 1 0.06%
98.36 0.11%
00.9910.3225
71.34 0.98%
92.45 0.63%
Unbiased
85.21 t 5.27%
72.69 2.13%
62.25 1.26%
18. 68.69- + 1.01%
09. 09.23 2.61%
U-Stop
90.92 + 0.11%
81.47 0.90%
69 69 1 0.56%
48.49 + 0.92%
61.75 2.30%
U-Correet
94.30 + 0. 22%
83.59 037%
78.74 1.01%
19.67 + 1.57%
81.89 0.89%
Asymmetric
U-Flood
93.43 1: 0.499%
82.68 0.50%
76.51 1 0.95%
51.72 +: 1.44%
82.24 1.2%%
Prop
95.81 t 0.41%
85.68 0.21%
82.51 0.641%
00.22 + 1.17%
58.73 0.67%
U-PRR
92.72 1: 0.86%
84.9 0.80%
76.98 1.36%
51.32 1: 2.50%
75.85 +: 3.06%
CCM
95.92 1: 0.35%
85.18 0.87%
63.28 0.41%
65.18 1: 3.47%
86.99 1.33%
RCM
96.33 = 0.145%
85.37 0.28%
84.10 0.55%
69.72 = 0.55%
91.54 0.19%
Supervised
98.11 1 0.06%
0.17%
0.20%
70.73 1: 1.16%
0.46%
Unbiased
26.46 +: 3.68%
31.36
2.06%
17.36 +: 1.98%
15.46 + 4.45%
16.46 + 5.51%
U-Stop
55.70 12.81%
71.08
2.71%
31,20 + 19.28%
31.09 + 6.1%%
51.59 8.16%
U-Correct
51.31 + 4.19%
6U.76 2.45%
68 2.67%
25.29 +: 2.63%
17.51 3.13%
Random
U-Flood
89.01 + 0.73%
78.85
1.11%
43 0.37%
31.32 + 28%
08. 3.11
Prop
86.73 1.12%
79.11 2.11%
60.49 1.50%
33.26 2 2.50%
53.15 4.31%
U-PRR
26.82 1.74%
1.88% 27.45
16.11 1 2.84%
23.32 1.36%
11.01 2.40%
CCM
92.21 0.25%
81.46
0.54%
74.08 1.07%
46.23 + 1.79%
66. 16 26.68%
RCM
95.37 1: 0.18%
83.48
0.23%
80.68 : 0.81%
55.71 11: : 5.93%
88.99 : 1.01% %
CCM outperform the compared methods with large gap in the random matrix, which verifies the effectiveness of our proposed method in complex scenario.
Compared to the performance between RCM and CCM, RCM demonstrated superior performance in most settings. When utilizing the same prior matrix, RCM exhibits a larger performance gap over CCM in CIFAR-10 and SVHN, indicating that when applying deeper models, RCM can achieve even more remarkable results. When trained on the same dataset, compared to two diagonal- d-ominated matrices, RCM demonstrates larger performance gap CCM on the Random matrix. This highlights the ability of RCM to handle complex prior matrices more effectively.
On the variation of set size. We also conduct experiments to verify the performance of our proposed method on different sizes. Concretely, we randomly select c n, data points from the i-th set. The experimental results are provided in Fig. in Appendix F.2. As shown in Fig. 1, RCM and CCM achieve better performance with larger e. Moreover, CCM achieves better performance than RCM when is small and RCM outperforms CCM when increases, which demonstrates that CCM is more robust when few data points are provided.
expedrime
5 CONCLUSION
In this paper, we studied an interesting problem called multi-class classification from multiple un- labeled datasets (MCMU), where the only supervision the class priors for unlaheled sets. To solve this problem, we first proposed a classifier-consisteni method based on a probability transition function. Nevertheless, CCM cannot guarantee risk consistency and neglects to differentiate the true labels of training examples. Hence, we further proposed a risk-consistent method (RCM) based on importance weighting. RCM can progressively purify supervision information during training. In addition, provided comprehensive theoretical analyses of the two methods to show the theoretical guarantees. We conducted comprehensive experiments on various settings, and experimental results demonstrated the effectiveness of our proposed methods.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
Lei Feng is supported by the Chongqing Overseas Chinese Entrepreneurship and Innovation Sup- port Program. Bo An is supported by the National Research Foundation Singapore and DSO Na- tional Laboratories under the AI Singapore Programme (AISGAward No: AISG2-GGC-003--009) Hongxin Wei is supported by Shenzhen Fundamental Research Program JCYI2003088000
REFERENCES
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. JMIR, 3(11):463-482 2002.
Tarin Clanuwat, Mikel Bober-Irizar, Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical Japanese literature. arXiv preprint 1rXhv:1812.01118, 2018.
Aron Culotta, Nirmal Ravi Kumar, and Jennifer Cutler. Predicting the demographics of twitter users from website traffic data. In AAAI, 2015.
Lucio Mwinmaarong Dery, Benjamin Nachman, Francesco Rubbo, and Ariel Schwartzman. Weakly supervised classification in high energy physics. Journal of High Energy Physics, 2017(5):1-11, 2017.
Gabriel Dulac-Amold, Neil Zeghidour, Marco Cuturi, Lucas Beyer, and Jean-Philippe Vert. Deep multi-class learning from label proportions. arXiv preprint arXiv: 1905. 1905.12099, 2019.
Lei Feng, Jia-Qi Lv, Bo Han, Miao Xu, Gang Niu, Xin Geng, Bo An, and Masashi Sugiyama. Provably consistent partial-label learning. In NeurIPS, 2020.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size- iizeenndepnndent sample complexity of neural networks. arXiv preprint arXiv:1712.065411 2017.
Arthur Gretton, Alex Smola, Jiayuan Huang, Marcel Schmittfull, Karsten Borgwardt, and Bernhard Schölkopf. Covariate shift by kernel mean matching. Dataset Shift in Machine Learning, 3(4):5, 2009.
Bo Han, Quan-Ming Yao, Xing-Rui Rui Yu, Gang Niu, Miao Xu, Wei-Hua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In NeurlPS, pp. 8527-8537, 2018.
Kai-Ming He, Xiang- Yu Zhang, Chao-Qing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pp. 770-778, 2016.
Takashi Ishida, Ikko Yamane, Tomoya Sakai, Gang Niu, and Masashi Sugiyama. Do we need zero training loss after achieving zero training error? In ICML, pp. 4604 4614. PMLR, 2020.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 1):2278-2324, 1998.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436 444, 2015.
Jiabin Liu, Bo Wang, Zhiquan Qi, Yingjie Tian, and Yong Shi. Learning from label proportions with generative adversarial networks. In NeurlPS, 2019.
Nan Lu, Gang Niu, Aditya K. Menon, and Masashi Sugiyama. On the minimal supervision for training any binary classifier from only unlabeled data. In ICLR, 2019.
Nan Lu, Tian-Yi Yi Zhang, Gang Niu, and Masashi Sugiyama. Mitigating overfitting in supervised classification from two unlabeled datasets: A consistent risk correction approach. In AISTATS, 2020.
10

---

Published as a conference paper at ICLR 2024
Nan Lu, Shida Lei, Gang Niu, Issei Sato, and Masashi Sugiyama. Binary classification from multiple unlabeled datasets via surrogate set classification. In /CML. pp. 7134-7144. PMLR, 2021.
Jie Luo and Francesco Orabona. Learning from candidate labeling sets, In NeurIPS, pp. 1504-1512, 2010.
Andreas Maurer. A vector-contraction inequality for rademacher complexities. ALT, pp. 3-17, 2016.
Colin McDiarmid. On the method of bounded differences. In Surveys in Combinatorics, 1989.
Aditya Menon, Brendan Van Rooyen, Cheng Soon Ong, and Bob Williamson. Learning from cor- rupted binary labels via class- ptobabiir estimation. In ICML, pp. 125-134, 2015.
Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii Virtual adversarial training: regularization method for supervised and semi-supervised learning. IEEE Transactions on Pattern Recognition and Machine Intelligence, 1189)1997-1193,, 2018.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning- MIT Press, 2012.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Read- ing digits in natural images with unsupervised feature learning. In NeurIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. In NeurlPS, pp. 0026-8037, 2019.
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 CVPR, pp. 1944-1952, 2017.
Clayton Scott and Jianxin Zhang. Learning from label proportions: A mutual contamination frame- work. In NewrlPS, pp. 22256222222222 22266-2226, 2020.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of Statistical Planning and Inference, 90(2):227-244, 2000.
Yuting Tang, Nan Lu, Tianyi Zhang, and Masashi Sugiyama. Learning from multiple unlabeled datasets with partial risk regularization. In ACML, 2022.
Kuen-Han Tsai and Hsuan-Tice Lin. Learning from label proportions with consistency regulariza- tion. In ACMI, pp. 513-528. PMLR, 2020.
Haobo Wang. Ruixuan Xiao, Yixuan Li, Lei Feng, Gang Niu, Gang Chen, and Junbo Zhao. Pico: Contrastive label disambiguation for partial label learning. In ICLR, 2022.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist marking machine learning algorithms. arXiv preprint (70..0/770.0775 2017.
novel image dataset for bench-
Felix X Yu, Krzysztof Choromanski, Sanjiv Kumar, Tony Jebara, and Shih-Fu Chang. On learning from label proportions. arXiv preprint arXiv: 1xXx::140..5902 2014.
Xi-Yu Yu Yu, Tong-Liang Liu, Ming-Ming Gong, and Da-Cheng Tao. Learning with biased comple- mentary labels. In ECCV, pp. 68 83, 2018.
Yiyang Zhang, Feng Liu, Zhen Fang. Bo Yuan, Guangquan Zhang, and Jie Lu. Clarinet: A one-step approach towards budget-friendee unsupervised domain adaptation. arXiv preprint arXiv:2007.14612. 2020a.
Yiyang Zhang, Feng Liu, Zhen Fang, Bo Yuan, Guangquan Zhang, and Jie Lu. Learning from complementary-laber source domain: Theory and algorithms. arXiv preprint 4rXiv:2008.01454 2020b.
Zhi-Hua Zhou, Yu- Yin Sun. and Yu-Feng Li. Multi-instance learning by treating instances as non-iid samples. In ICML., pp. 1249-1256, 2009.

---

Published as a conference paper at ICLR 2024
A PROOF OF LEMMA 3.1
Vi (1.....)) we have
m)
12 Oeg p( y = j)]
(x)) p(a, y = p(x))
p( y i) p 1)
L p ()(x))
- P: 1-0 Ozg p( y = j]]
where P((x)) is used to denotes the mixture probability densities function of And by Bayes' rule we have
p(u x)) p(x))
(3())) p(z))
p(æ y-
p
J
Then we can obtain
Pi 12 j= 0i.
(1((2)
Pi ax. m(x))
Tx()))))
E1=1 Pi [_}_1 Oij 1:(1)
33 (2))
where a; = (ooi,...,,auu and ogj = my
and B m
Ps O04.
B PROOFS OF
METHOD
B. PROOF LEMMA 3.2
We proceed the proof by firstly showing that the denominator of each function Tī(t), i [l.....m) m],
strictly greater than zero for all E [0, 1 and then showing that Ti(t, = TT((2) if and only tz. For all E [1,.... mm and denominator of each function T,(t), i E [1, ... m), is strictly greater than zero for all t E [0, 1]
[1.... k), Ps 0, Oij 0 and ßy 0. Then we have the
Next, assume that there exist é, t2 E [0. 1] such that t1 # t2 but T(t,) T(22), which indicates that (1(t)) (t2)), Vi [1....; m]. For all we have
P: a t1
Pi a t2
(1 T.(t2)
T
a t
af 12
Pi
B
B
0.
Since Oij # Pis. Vi [1..... m] and Vj.s e [1,...,k] k), have ai aiss Vi [1,..., m]
and Vj, [l....,k]] kl.. Therefore, t2 = At,, X e R. Since t1.t2 E [0,1]* Σ tu = and Σ l2 1, we have À 1, which indicates that (41)) Ti(12) if and only if la.
B.2 PROOF OF LEMMA 3.3
the cross entropy loss is used, we have the following optimization problem:
((g) - Et p(y = i|æ) (og()(())
s.t. Lx_ f(xx)= 1.
By using the Lagrange multiplier method, we can obtain the following non-constrained optimization problem:
((g) - >'-- ply log(((())))))
g((x)) 1).
The derivative of ((g) with respect to g is
2
p(y
1 [x))
ply k|az)
>, A,...,
+ A]T
0g
g1(x))
Ih xx)
12

---

Published as a conference paper at ICLR 2024
By setting this derivative 0 we obtain
1
(x p(y = i|æ)), Vi [L.....,k] k] and V e X.
Since Σi-1 ((())) and D -i-1 ply i|ır) we have 1
k 1,,19% = - joly i100)
Therefore, we can easily obtain À In this way, 9f (x))) ply =/2),, which concludes the proof.
B.3 PROOF OF THEOREM 3.4
According to Lemma 3.3, by minimizing Recm(() with the cross entropy loss, we can obtain
(x) p(ğ f/2z), [I...., m).
Let introduce p [p(Ø 1|x)........ ..... p( m m|x)] and [p(y 11x)).... k/x)]]-
We have p T(p). Since q" (x) and g" (x) = p. we have o- (x) 'T (x)) where
(x= softmax(f*(xx))
On the other hand, we can obtain Jerm (a) by minimizing (eCm(() (i.e., Jeem (x) softmax (fcm(())) Then, we can obtain q" (a()) ((eem()))) which further ensures T(g (x)) T(yeem (x)). Therefore, according to Lemma 3.2, we obtain g'(x) = (x), i.c. (x) fe)m(
B.4 PROOF THEOREM 3.5
We define function space for our CC method
Goem = [g (x, D) - [(T(((=)), If fe F},
where
Σx Σー Prags exp(f) (z))
C(T(m(x)). log
By exp(ff
f (ax) denotes the j-th element of the output. Then have the following lemmas.
Lemma B.1. Let the loss function L(T(n(a)), 9) be L'-Lipschitz with respect to f(x)) (0 L' < co) and bounded by C₁ i.e. SuPeexX.eF..setm ((T(n(())),)) & C₁. Then for any 8 0, with probability least 8.
log 2 3
sur Recm(f) Reem (f)l 22 Ex R Rn (H₂) CN
2n
Proof. We first show that the direction sup Roem (f) Reom (f). The change of
supjer Romm(f) Rf is no greater than C if example is replaced with arbitrary example z/. By applying McDiarmid's inequality (McDiarmid, 1989), for any > O, with proba- bility at least - 2
log a 2n
sup Recm Reem (f) & E[sup R Reem (f) Oip.
Then it is routine (Mohri al., 2012) show
E[supjeF Roem(() (f) Ream(s)) (1)) & 22,, (Crom)
< 2222' Σx ---1 RR, (HLy)
13

---

Published as a conference paper at ICLR 2024
where the last inequality is due to the vector-contractiion inequality for Rademacher complexities (Maurer, 2016).
By further taking into account the other side sup jeF Room (f) - Room (f), we have for any O, with probability at least
6,
log a
suD Room(s) - Room (f) 22/22222/ E,,,, Rr (m((H)) + CAN
2n
which concludes the proof.
Lemma B.2. Let f be the empirical minimizer (i.e., f= arg mir R(f)) and f be the true risk minimizer (i.e., f = arg min jeF R(f)), then the following inequality holds:
R(f) - R(f*) & sup [R(f) - R(f)).
Proof. We have
RC)- R(T)= R(()) p(()*)+++++) RCJ) Pe( + P(()) R(()
+ JE ((()) R()).
which concludes the proof.
By combining Lemma B.1 and Lemma B.2, Theorem 3.5 can be proved.
C PROOF OF RISK-CONSISTENT METHOD
C.1 PROOF THEOREM 3.6
The classification risk could be rewritten
R(f) E p( [C(f()).)) y)1
j-1 ply= = ((f(() dæ
j=1 E ply = i.)
i= L/ *
ply==
Σ m
plū i, Σx- j-ز pリ==ia))
p i,
L [(f(x),
X 1-1 p(ū = i, x)) Σ " P(U
En m
i,
E 1=1 ply j J. (z)) Rfom
E E
(9)
C.2 EM ALGORITHM
In this section, we show that the training process of RCM works in an expecaaioon-maximzaaton manner and aims maximize the likelihood p(ū, x; with respect y when the widely used cross entropy loss employed. Here, 7 denotes the parameters of the classification model and
p(::7) denotes the probability function approximated by the classification model. w/(i) is used to
represent the weight corresponding the j-th class for the v-th example, and 0 w/) 1,
Σ W (v) 1. Then, the following equations hold:
14

---

Published as a conference paper at ICLR 2024
(g((p((() ,10) Σ log( Σ p(g(t), y00) J. ;0))))))))
log w p y( 2. x0) 77)
w
(0) log( p(gl)) y j. x ,0)
The last inequality is based on Jensen's inequality and the properties of the weights: 0 & w/ & 1,
-بك -ويt) = 1. The inequality holds equality when p(g"") (ft) =j my) is constant, which means
pig - - C' and C is a constant when v is fixed. Then, we have
w
p(g(") ,y(()) (x(())))))
(w)
C
p(y(t), y(u)=s (7)
k
(v)
w
C
5=1
, (.(1))))))
1,
, C.
In this way, the value of ( could be calculated by
(0) p(g()),
_y(x) ,
J. 20)1; 7)
C
(0) p( ,y(0)) x (1)
p(7("), 77)
(0) - pl j (r), xz ,0()))y))
Therefore, the E-step of RCM is to set w/)0 plylo)
g( ox 20(0)))) make the inequal-
ity holds with equality, which means to maximize E. Ej= w log( p(g = my)
with fixed p(7("), ,y(0) = J. x)) For the M-step, RCM is to maximize
En D w/) log( p0 pr " - with fixed w/"). We have the following equations with the fixed :
with
log( () v() j, [1)))
(v)
())( (v) 1/ (0)
j, j, 11;))) - lo)(
log(p(æ: x ((()) y -0)= = -): + log(p()()) ()) (())= = -)):7)-log(()
- ())
log(p(æ: (n) = -j:))) + (og(p()("), ()) j:>)) log(u(("))
log( ((y(0) = -i x: ;;;))({;)))
p(m)) + + (l)( (0), (g(() = -): 7) - log(w)"))
ply(o) j:>)
p(=: 7)
= (o) = x; x) + log(
(()(1) j:r) ) + log(p()()) ,(()))))))))))))))) = j: r)) log(w(())
is noteworthy that log( p(a:7) )))r) + log(p(((()) (y(") = j:>)) - log(w(")) could be treated as a p(any) constant term with respect to y (i.e., log( p()l)))))) ) + (log(p(g()) (") (0(() = jin)) log( p(yl=
15

---

Published as a conference paper at ICLR 2024
log(p(g')) (/ = )]) since the role of classification model is to approximate the probability func- tion pyy z). When the cross entropy loss function is employed, ((f()),)) = log(p(y = x); 7), which means maximizing log(p(y = j x): 7) is equivalent to minimizing [(f(z),)).
In summary, the E-step of the RCM is to maximize the lower bound of p(ū. æ; 7) and the M-step of RCM is to maximize the improved lower-bound by updating the parameters Y of the classification model.
Based on the above analysis, the M-step of RCM is minimize _ 2 w/ [(f(x(()), with fixed
w (o)
C.3 PROOF OF THEERRE 3.7
We define a function space for our RCM method as
Grem {g g) _ (()==))..))(((((),))))
where (a. 5) is randomly sampled from p(æ,, 7) Let (Grmm)) be the expected Rademacher com- plexity of 9rem Then, to prove Theorem 3.7, introduce the following lemmas.
Lemma C.1. Let the used multi-class classification loss function (()(()), y) be bounded by Ce. i.e,
SUPaeX (z)())))) 3) < Ce. Then, for any 8 > O, with probability at least 1
E e[Rrem [frm)) R & (9 + Cet
log g
2n
Proof. Since Σ P(y j F. and [(f()),)) is bounded by Ct, the change of E [[Brem((rcm) Rrem (Fro)) is no greater than Ce an example æ; replaced with an arbi- trary example x/,. By applying McDiarmid's inequality (MeDiarmid, 1989), for any 8 0, with probability at least 1 6.
E [(erem(Frem)) - (rem((rrm)) & sup E[ Rrem (f) (f)
feF
log 1 à 2n
<
Elsup E Rrem (ʃ) Rrom + C.p fEF
Then we can bound the expectation of the right-hand side as follows:
Elsup E Rremm(M) (f) Prem (f) & (9rem))
JEF
which concludes the proof.
Lemma C.2. Let the loss function L(f(x),)) be L-Lipschitz with respect f(x) L co).
The following inequality holds:
(Grem) & V2L E,,, Rn (Hly;
where
Hy (h: fy(x)] E F},
1 En 1:- ozh(2r)]
R. (Hyy E.,x (supueee
Proof. Since Σ1- ply j v. and 0 & ply j x) & Vy E V, we can obtain Rg & R., (C) where LcF denotes [of f and the loss function is L-Lipschitz, by using the vector contraction inequality for Rademacher complexities (Maurer, 2016), we have (C F) & VēL R. (H,,), which concludes the proof Lemma C.2.
f F). Since H, = {h : x - (x) f F}
By combining Lemma C.I and Lemma C.2, Theorem 3.7 can be proved.
16

---

Published as a conference paper at ICLR 2024
D DETAILED DESCRIPTIONS/EXPPAANNI
OF RCM AND CCM
In our paper, we present two loss functions to solve the MCMU problem: RCM and CCM. These two methods stem from different conceptual frameworks.
The main idea of CCM is to design a loss function by converting the problem of classifying mul- tiple classes into multiple unlabeled datasets. This conversion is based on our built connection relationship between p(y(z) (the probability that an instance a belongs to a label) and p(zlæ) (the probability that an instance æ belongs to unlabeled set) in Eq. (2), which is further represented
as a transition function (i.e., r7(x)) T(m(x)) where ()x) = p(y ()) and 77(2) = p(y(z)). As
aim to approximate p( p()(z) by T()(=)),
infer that p(y xz) can be approximated by g(x)
(where we use ((x) to denote the Softmax output of the model), because T is an injective function. The detailed proof can be found in Appendix B.3.
The main idea of RCM is risk rewriting. We rewrite the risk function on clean data (Eq. (1)) into an equivalent form for MCMU (Eq. (5)) that can be accessible from unlabeled sets, since the ordinary classification risk cannot be obtained from unlabeled sets, Concretely, we rewrite the risk function via the crertaance-wegghiin strategy, i.e. assign the weight p(y j|æz) to loss ((f())))) RCM could recover the distribution of clean data by combining the information of unlabeled sets and the learned classifier. Then we could achieve the optimization Eq (1) by minimizing Eq. (5).
E DETAILED INFORMATION OF EXPERIMENTS
E. TRAINING DETAILS
In the experiments, Adam (Kingma & Ba, 2015) was used for optimization and we adopt the cross entropy function as the loss function for CCM and adopt softmax cross entropy for RCM. We ran trials on each dataset for each method and recorded mean accuracy and standard deviation (ttd. We trained the classification model for 100 epochs all datasets. We recorded the average test accuracy of the last ten epochs as the accuracy for each trial except for U-Stop, in which recorded the test accuracy of the epoch where stop training the accuracy for each trial. The learning rate was chosen from {10-5, 10 10-3 10-2 1002,1001 10 and the batch size was chosen from 128 and 256. The weight decay was set as 10 The hyper-parametes for compared methods were searched according to the suggested parameters by respective papers. We used PyTorch (Paszke al., 2019) to implement our experiments and conducted the experiments on NVIDIA 3090 GPUs.
E.2 COMPARED METHODS
In this section, we provide detailed descriptions of the compared methods.
Unbiased (Tang et al., 2022): This method aims to minimize an unbiased risk estimator derived from by using the backward correction technique (Patrini et al., 2017). However, this method suffers from the unreasonable training objective caused by the negative empirical risk.
U-Stop (Tang et al., 2022): It aims to minimize an identical unbiased risk estimator as the Unbiased method but stops training when the empirical risk goes negative to prevent suffering from the optimization obstacle caused by unbounded losses.
U-Correct (Tang et al., 2022): It takes the absolute value of partial risks corresponding to each class in the Unbiased method to correct the partial risks be non-negative.
U-Flood (Tang et al., 2022): It aims to apply the flooding method (Ishida et al., 2020) to the Unbiased method to maintain the empirical risks at certain levels.
Prop (Yu et al., 2014); It treats class priors as weak supervision to the set and minimizes the difference between the true class priors and the class priors predicted by the classification model. KL. divergence is applied to measure the difference.
U-PRR (Tang et al., 2022): It aims to utilize a partial risk regularization that maintains the partial risks corresponding each class in the Unbiased method to certain levels.
17

---

Published as a conference paper at ICLR 2024
F ADDITIONAL EXPERIMENTS
F.1 ROBUSTNESS AGAINST NOISY PRIOR MATRIX
We conducted experiments that add noise the true class prior matrix θ on m 10 (m denotes the number of sets). Specifically, we train the classifier on the MNIST dataset and the class prior matrix we used is the random matrix as we described in Section 4.1. We design two procedures to perturb the class prior matrix with the noise rate and the class number k.
Random noise: we obtain the noisy class prior matrix by right-multiplying the truth class prior matrix with noise matrix N, i.e. Onise θ N where N; = _ and No, i where * j. This noise procedure typically only changes the numerical values of the elements of the prior matrix, without significantly altering the relative order of magnitude between elements in the same row. The experimental results are reported in Table 4.
Order disturbance: we aim to disrupt the relative order of class priors in the same row. For example, given the i-th row of prior matrix be [0.1. 0.2, 0.7] and the relative order is 0,3 > 0,2 > 0n1- The noisy version [0.12, 0.18, 0.7] only changes the numerical values while the noisy version [0.18, 0.12, 0.7] changes both numerical values and the relative order (i.e., changes the relative order to 0 > 0,1 > 0.2). Concretely, we perturb to the i-th row of θ by the following step. Firstly, we generate an arithmetic sequence l according to c, i.e., I = {1, 1+.1+0 G, c...., + (k- 1)c]. Secondly, we randomly shuffle the elements in L. Thirdly, we divide the elements in the ith row by the corresponding element in I, i.c. 0,j = 0. Finally, we normalize the i-th row, i.c., 0z 01s/ ΣE= Dtg. The experimental results of this case are reported in Table 5.
To our surprise, in Table 4, all methods other than CCM works well and were not significantly affected by the random noise. Additionally, our proposed RCM model achieves the best performance on the inaccurate prior matrix. We observe that CCM tends to overfit in cases of high noise rates, which leads to poorer performance.
From Table 5, we can observe in order disturbance, the noise rate increases, the performance of all models decreases. However, our proposed RCM method still achieves the best performance in almost all cases.
By comparing the experimental results on random noise and order disturbance, it appears that the inaccurate elements in the prior matrix may not have substantial impact the performance of methods. What appears to be a more influential factor is the disturbance of the relative order of the prior matrix. In addition, RCM performs well even in the presence of noise in the prior matrix. This can be attributed to the label correction effect of the importance weighting scheme RCM, which could leverage the model's capability refine the labeling information in surrogate labels.
Table 4: Classification performance of each method on the MNIST dataset with 10 trained on random prior matrix with random noise
Noise Rate
0
0.1
2
0.3
0.5
0.7
Unhiased
14.10
2.94%
12.89 : 1.89%
14.58
0.91
15.52 + 1.28%
18.68 = 1.90%
19.16
0.98%
U-Stop
25.39
5.52%
20.49
6.58%
18.99
3.80%
26.73
5.84%
21.27
4.10%
24.72
6.98%
U-Corret
27.32 + 7.07%
27.29
5.95%
27.15
6.37%
26.70
+ 6.20%
26.78 = 6.97%
25.48
6.32%
U-Flood
1.31%
1.21%
2.43%
85.87
15.08
Prop
88.64
1.93%
88.85 :: 1.50%
89.78
1.48%
89.66
1 0.84%
88.99
: 0.92%
87.88
1.49%
U-PRR
23.17
1.50%
23.86
1.75%
25.57
2.75%
26. 2.26%
24.61 2.06%
22.19
1.70%
CCM
91.46
1.22%
91.11
1.56%
37.49 4: 37.88%
10.31 1.45%
43.15 23. 79%
11.68
1.82%
RCM
94.80 0.64%
96.25 0.58%
95.41
0.53%
95.56 + 0.48%
96.45 = 0.53%
91.92
1.69%
F.2 ROBUSTNESS AGAINST VARIANT SET NUMBERS
We conducted additional experiments with different numbers of sets with fixed data points (i.e. with fixed set number times the set size) the MNIST dataset. Random matrix and asymmetric matrix are adapted as the class prior matrix. The experimental results are shown in Table and Table 7. Our proposed RCM and CCM demonstrate stable performance with the increase in the number
18

---

Published as a conference paper at ICLR 2024
Table 5: Classification performance of each method the MNIST dataset with random prior matrix with order disturbance
10 trained
Noise Rate
Unbiased
14.10 + 2.94%
17.22
+ 4.02%
15.84
3.00%
9.87 + 7.11%
9.87
7.11%
8.34 1: 1.80%
Slop
25.39
5.5%%%%
19.97
20.61
3.36%
5.08
4.24%
U-Correct
27.32 + 7.07%
30.18 + 6.56%
18.63 + 5.92%
14.01
4: 2.87%
15.47 +: 4.76%
15.23 4 3.78%
86.83
1.31%
87.70 0.79%
85.06
0.34%
58.28 28.31%
54.10 31.16%
55.00
19.91%
Prop
88.61 1.93%
86,98
2.06%
80.55 3.3. 3.90%
73.96 +: 1.39%
61.53 3.71%
50.93 5.51%
U-PRR
23.17
1.59%
21.92
2.60%
20.55
2.13%
14.12 1 3.43%
9.96
4.16%
11.32 4.26%
CCM
91.46
1.22%
89.27
12%
86.99
2.62%
82.03 + 0.88%
74.84 + 4.57%
68.91
5.94%
RCM
91.80 + 0.61%
93.09 + 1.98%
87.50 +: 1.51%
83.78 + 1.28%
75.83 + 5.25%
67. 79.99 7.02%
of sets and still outperform the baseline methods. When the number of sets becomes excessively large, some baseline methods may achieve poorer performance. This is because in such case, the distribution p(z) on training data might shift from testing data. Some papers Zhang et al. (2020a); covariate shift, which would lead to degraded performance.
Shimodaira (2000) refer this
Table 6: Classification performance of each method on the MNIST dataset using asymmetric prior matrix with variant set numbers.
Methods
m=30
m=
m=300
m=1000
Unbiased
84. 30.2.55%%
86.85=1 066
86, 7420 88%
87.75=0.47%
88,17=0.666 68%
87 17.46+0..415
62.78=5 07%
U-Stop
89.69+1.21%%
89.79=1.559
91.05=0.42%%
89.47+0.209
85.23+0.6554
U-Crreet
94.0740.188
94.16=0.235
87.00==0.30P
78. 18.94x1.869.
63.33+16.. 18%
27 27.04488.39%
26,80s7 755%
U-Flood
93.2920.3448
90.5520.533%
79.46220.8
68.43210.755%
56.7013.33%%
Prop
82.98&1.555
79 19.%%
75.4621 23%
72.77=t1 770%
72.62e0.6755
71.6110.511%
71 71.9020.33
U-PRR
91.1 1+0.29%
89. 19.32+0.899
79. 20.28= 328+1.334 1.34%
70. 7..66442.36%
67. 10.80+0 69%
62.76+2.53%%
67,28+2.1
CCM
95.7740. 12%
95.66 17%
95.66+0.08%
95 1..40000.49 14%
95.69+0. 14%
95 05.5740.20%
95,91=01 17%
RCM
95.94s0.23%
96.02=0.08%%
95.95a0.155%
95.70=0.239
95.88+0.08%%
95.8240.07%
95.77=0.22%
Table 7: Classification performance of each method on the MNIST dataset using random prior matrix with variant set numbers.
Methods
m=30
m=
m=100
m==00
m=300
m=500
m=1000
Unhiased
14. 1441, 15%
15.64el 48%
13,90+0 70%
11.18=2.0 30%
15. 12:2222.644
16.36 3.366615394 533%
13.31 95%
Utopop
53.124 13.1223.76%
71.61=0.522 52%
38.41=18.4495
40.62+24.600
18.3346.658.
18.27=2.322B
25.89b3..77%
U-Correet
63.8424.61%
66.64a1.214
75.0010.500%
64.2420.34%
64.85&1.51%%
71.5910.2099
77.0120.83%%
U-Flood
89.1420.9669
88 98.91=0.92%
85. 85.8720.42%9
75.59=0.72%
69.92+1.47%
59.8242.388%
50.5425.44 4.%
Prop
77.29=1.50 51%
652.3%
57,96=1
54.38+1.124
53,38+ 2.66
51,44=
U.PRR
23.92+0.56%
19.62=1.155
19.30
18.15=1.225 25%%
14.97+0.47%
17.98+ 16%
13.69=0.53%%
92.90=0.29%%
92.49=0.
92.37=0.20%
93.27440.7%%
93.00+00.88%
93.06=0.20%
RCM
93.69200.25%
95.6320.1125
95.4920.1755
95.38
95.4920.07%
95.462(0.15%
95.7820.14%
19

---

Published as a conference paper at ICLR 2024
RDM
CCM
RCM
CCM
RZN
CCM
RCM
CCM
AAXU 100 990
6-4
01
02
Fachion, mi 20
KuzusHi =0
CFAR-10, m0
SVNNN 20
Accuracc (5)
3.5
3.5
0.
02
Figure Mean accuracy over trials percentage for our proposed RCM and CCM tested on different set sizes on the random class prior matrix.
20


Reviews:
[{"review_id": "lRLaDXGb3D", "reviewer": "Reviewer_x6yh", "summary": "The authors study the challenge of weakly supervised learning with a focus on multi-class classification from multiple unlabeled datasets. They propose two methods: the Classifier-Consistent Method (CCM), which utilizes class priors and a probability transition function for training, and the Risk-Consistent Method (RCM), which aims to enhance the CCM by ensuring risk consistency through importance weighting to refine supervision during training. The study claims the superiority of these methods, supporting them with comprehensive theoretical analyses for statistical consistency and positive experimental results across multiple benchmark datasets.", "questions": "Seen weaknesses.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper presents a novel approach based on statistical learning theory to solve the problem of multi-class classification from multiple unlabeled datasets and the theoretical guarantees of the estimation error bounds strengthen the claims regarding its effectiveness.\n2. The authors provide a clear and comprehensive description of their methodology, which enables other researchers to reproduce their results.", "weaknesses": "1. The methods and the corresponding theory presented in the paper are sound and relevant, but the lack of sufficient originality and novelty compared to a previously published work [1,2] could be a limitation. Therefore, the authors should carefully consider these points and take the necessary steps to distinguish their work and demonstrate its original contributions.\n\n   [1] Feng, L., Lv, J., Han, B., Xu, M., Niu, G., Geng, X., ... & Sugiyama, M. (2020). Provably consistent partial-label learning. Advances in neural information processing systems, 33, 10948-10960.\n\n   [2] Kobayashi, R., Mukuta, Y., & Harada, T. (2022). Learning from Label Proportions with Instance-wise Consistency. *arXiv preprint arXiv:2203.12836*. \n\n2. Employing the direct outputs of a network to estimate the posterior probabilities $p(y=j∣x)$ can be imprecise, particularly under the extreme weak supervision scenario where only class prior probabilities serve as supervisory signals. In such a setting, the network predictions may not align well with the true posterior distributions, leading to suboptimal performance.\n\n3. In Theorems 3.5 and 3.7, the assumptions regarding the Lipschitz continuity of the loss function present an indeterminable strength which could affect the assessment of the model's robustness. Furthermore, the generalization error bound incorporates a summation over $k$ categories of the Rademacher complexity, which may result in a rather loose bound. \n\n4. The use of subscripts $i$ and $j$ appears to be somewhat confusing and may lead to difficulty in understanding for the reader. Specifically, the subscripts switch between $i$ and $j$, which could introduce ambiguity in distinguishing between the elements associated with the k-dimensional vector $\\eta(x)$ and the m-dimensional vector $\\bar{\\eta}(x)$. Clarity in the mathematical notation is crucial for the precise communication of such theoretical results.", "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": "", "extra_scores": {}}, {"review_id": "nexTVP9arW", "reviewer": "Reviewer_vMrL", "summary": "This paper proposes two algorithms (CCM and RCM) to classify multiple classes from multiple datasets using only class proportion information. They provide theoretical guarantees on the accuracy of their methods and show some experimental results.", "questions": "-\tThe author’s state that Section 2.2 that in MCMU has the data generating process P(X|y) P(y|c) P(c) which seems reasonable, but that the generating process of LLP is P(y|X)? That would make sense as the modelling distribution (learning a discriminative function), but not as a data generating process? Also where is the class priors in the data generating process of LLP?\n-\tWhat are the class priors? The proportion of y_i for each of the k classes?\n-\tSection 2.4 is kind of randomly there without any introduction and it could be “cleaned up”. \n-\tWhat is WSL?\n-\tThe proposed method is extremely unclear. The paper needs to explain more of its proposed approach instead of spending large parts of the text comparing to other papers e.g. Lu et al. and describing their approach as an extension / variation of other papers. (Note: this also unintentionally make it sound less novel)\n-\tThe main idea of CCM seems to be that by converting the problem from classifying multiple classes in multiple datasets, it can be simplified into classifying which dataset the X sample comes from? And this equivalency is due to a deterministic transition function T() which is based on \\rho the probability a datapoint belongs to a dataset, \\theta the proportions of each class for each dataset, and \\pi the proportion of each “class” over all datasets? \n-\tThe problem setup seems very restrictive / artificial. There has to be the same number of classes for each dataset and the classes are “ordered” / aligned across multiple datasets? Also while the problem of classifying which dataset a sample belongs intuitively is “easier”, it is not clear how that solves the problem of which class within which dataset a sample belongs to. Multiplying by the proportions of dataset size and class size will “on average” get you probabilities on the latter problem, but this is just a math trick to achieve a bound. It is not clear how this works practically. The experiments seems to indicate it works, it is just extremely unintuitively how / explained badly.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "I am not familiar with the related work. e.g. LLP, but the overall proposed method seems interesting and sufficiently novel. The proofs in the appendix seem reasonable and the additional experiments there exhaustive enough.", "weaknesses": "- See questions\n-\tThere is typo / the sentence got broken up here: “where d is a positive integer denotes the input dimension. [k] = “\n-\tThis is not grammatically correct / does not make sense “multiple-instance learning (Zhou et al., 2009)) could usually have access to weakly supervised labels.”\n\nHowever, the paper is badly written (there is barely any explanation of anything; the appendix in some ways is more clear than the main paper!) and very difficult to understand. This is the biggest flaw of the paper, and makes it difficult to evaluate the paper accurately.", "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": "", "extra_scores": {}}, {"review_id": "QuGkgFd7Yh", "reviewer": "Reviewer_3iq5", "summary": "This paper focuses on a newly proposed weakly supervised learning problem called multi-class classification from multiple unlabeled datasets (MCMU), where only multiple sets of unlabeled data and their class priors are provided in the training process. To solve this problem, this paper proposes two methods, including a classifier-consistent method (CCM) based on a probability transition function and a risk-consistent method (RCM) based on importance weighting. Additionally, theoretical analyses of the proposed methods and experimental results on multiple benchmark datasets are provided.", "questions": "I have listed the questions in the weaknesses above. Please address them.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. This paper studies a newly proposed weakly supervised learning problem called multi-class classification from multiple unlabeled datasets (MCMU), and proposes two effective methods, which could avoid the negative risk issue commonly encountered by previous unbiased risk estimator methods.\n2. Theoretical analyses are provided to show the theoretical guarantees of the proposed methods.\n3. Comprehensive experimental results on multiple benchmark datasets across various settings demonstrate the effectiveness of the proposed methods.\n4. The paper is well organized and well written, which makes it easy to follow.", "weaknesses": "1. There is a lack of descriptions of Theorem 3.5 and Theorem 3.7. Additionally, could we compare RCM and CCM from a theoretical perspective?\n2. The analysis in section 4.3 is interesting. However, there is a lack of discussion about the observation from Fig. 1. So, could the authors provide more details of why CCM is more robust when few data points are provided?\n3. I noticed that in all experimental settings, the number of sets is greater than or equal to the number of classes. Could the authors provide a discussion where the number of sets is less than the number of classes?", "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": "", "extra_scores": {}}, {"review_id": "w0B0QPfT1n", "reviewer": "Reviewer_S73G", "summary": "This paper investigates an interesting weakly supervised learning problem called multi-class\nclassification from multiple unlabeled datasets, where only multiple sets of unlabeled data and their\nclass priors (i.e., the proportions of each class) are provided for training the classifier. To tackle this\nproblem, this paper first gives a multi-class extension of a previous work on binary classification from\nmultiple unlabeled datasets. However, this paper says that such a method still has several\ndisadvantages that limit the performance. So this paper further proposes a risk-consistent method that\ncan avoid those disadvantages and maintain theoretical guarantees. Experimental results support the\nclaim of this paper.", "questions": "- What can we learn from Theorem 3.5 and Theorem 3.7?\n- What is the relationship between the studied problem and the unlabeled-unlabeled learning problem\n[Lu et al. (2019)]?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- Problem. This paper investigates the problem of multi-class classification from multiple unlabeled\ndatasets, which is interesting problem.\n- Method. To solve the problem, this paper proposes two methods. The first one is a classifierconsistent method, which is a multi-class extension of a previous work on binary classification. The\nsecond one is a risk-consistent method that can address the shortcomings of the first one.\n- Theory. This paper gives theoretical analysis for the two methods proposed in this paper.\n- Performance. From the experimental results, we can find that the classifier-consistent method can\nachieve good performance compared with previous methods, and the risk-consistent method\noutperforms all the methods. Some ablation studies also support the risk-consistent method.", "weaknesses": "- This paper has proposed two methods (CCM and RCM) to solve the problem and showed that the\nsecond method is better than the first method. I think that there lacks a separate paragraph that is\nspecially for describing the difference between RCM and CCM in detail.\n- This paper should give more explanations for the theoretical findings. For example, there are no\ndiscussions or descriptions on Theorem 3.5 and Theorem 3.7.", "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": "", "extra_scores": {}}, {"review_id": "VC9qQQQ5cR", "reviewer": "Reviewer_XSqD", "summary": "The paper introduces a novel approach to weakly supervised learning, specifically targeting multi-class classification from multiple unlabeled datasets with class priors. It addresses limitations identified in Tang et al., 2022, and offers two distinct approaches: a classifier-consistent method using a probability transition matrix and a risk-consistent approach employing importance weighting. However, certain areas require further clarification and empirical investigation.", "questions": "1. The paper could further investigate the impact of small m (few unlabeled sets) and significant variations in label proportions across sets on the generalizability of its results with respect to m and n_i.\n   \n2. A clarification regarding the difference between Lemma 3.1 in the paper and Theorem 1 in Lu et al., ICML 2021, would be valuable for readers.\n\n3. Given that label proportions in real-world scenarios may only slightly differ, the paper should outline constraints on parameters m and n for practical significance, especially considering that a large m may be necessary for the method's effectiveness.\n\n4. A discussion on the practical relevance of the derived upper bound in Theorem 3.5 and its connection to the actual classification task involving class labels would provide valuable insights.\n\n5. The observation that the proposed approach performs significantly worse under certain settings, such as a random class prior matrix and non-constrained m, should be supported by clearer details on how test accuracies were computed, whether test data were balanced, and if class size variations in datasets played a role.\n\nOther suggestions:\n\n\"In MCMU, given the class priors, the data points in the same set are independent from each other, while in LLP, given the label proportions, the data points in\nthe same set are dependent from each other.\"\n\nThe second part of the sentence should clearly state whether data points are \"independent from each other\" or \"dependent on each other.\" If it implies independence, it raises a significant ambiguity regarding how MCMU and LLP fundamentally differ, as class priors and label proportions are practically equivalent concepts. Moreover, there appears to be a conceptual misuse in the paragraph. Data points within each class are typically assumed to be independent, conditioned on their class labels. The statement in question uses \"class priors\" in place of \"class labels\", which could introduce confusion and should be clarified. Overall, given that label proportions and class priors are practically the same thing in the context studied by the papers it is hard to see any difference from a dependence perspective between the two approaches. \n\nI think using the term \"label proportions\" when referring to class priors within each set would be more appropriate. In fact what the paper denotes as the j-th class prior of the i-th unlabeled set can be denoted as the label proportion of class j in dataset i. This would distinguish label proportions from class priors estimated using data from all available unlabeled sets.\n\n\nIn Section 4.1. \"The ni data points contained in i-th unlabeled set were randomly generated according to ...\" Isn't this supposed to be \"randomly sampled\" or \"drawn\".  Data already exists... nothing is supposed to be generated.\n\nIt would greatly enhance the paper if, within the related work section, an early explanation were provided regarding the reasons behind the possibility of negative empirical risk in these methods (Lu et al., 2019; Tsai & Lin, 2020; Tang et al., 2022). This proactive approach would help readers anticipate and better understand the issues related to negative empirical risk that the paper seeks to address.\n\nIn page 4 i is used for indexing both the sets and data points. It may cause confusions. \n\nIn Theorem 3.6 the paper defines this probability p(y=j|\\bar{y},x)as the probability of x in \\bar{y}-th unlabeled set whose ground-truth label is j. Isn't this supposed to be the probability of x in \\bar{y}-th unlabeled set belonging to class j? x may or may not belong to class j. x's ground truth label is not necessarily j. \n\nTheorem 3.6 also considers p(x|y=j)=p(x|y=j,\\bar{y}) as a fact. However, this is not necessarily true. The first one is the conditional distribution of class j estimated using all data belonging to class j whereas the second one is the conditional distribution of class j estimated using only data from unlabeled set \\bar{y}. So, from an empirical standpoint these distributions are not equal. Please clarify.\n\n\nAfter Rebuttal:\n\nThanks for taking the time to do those extra comparisons I mentioned. It’s helpful to see how your method holds up with different 'm' values and varying levels of class imbalance. Based on these new results,  I'm happy to bump up my score by one.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper successfully addresses limitations observed in the MCMU method and presents an alternative solution, expanding the landscape of weakly supervised learning.\n- The introduction of a novel approach focusing on empirical risk minimization (ERM) at the instance level, treating individual data points, stands out as a significant strength.", "weaknesses": "- The experimental comparison is somewhat limited, primarily featuring methods from Tang et al., 2022. While justified due to MCMU's novelty, including additional weakly supervised methods could provide valuable reference points. Moreover, presenting accuracies for fully supervised learning on the same train/test splits would enhance the evaluation.\n- The paper lacks a comprehensive study of the method's limitations, particularly with regards to constraints on parameters such as m (the number of unlabeled sets) and n_i (the number of data points in each set), which are crucial for practical applicability.\n- Theoretical results like Theorem 3.5, which establishes an upper bound for the difference between true and empirical risk, would benefit from discussion regarding their practical implications and their relationship to the actual classification task involving class labels.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)