Learning from Label Proportions via Proportional Value Classification
Authors: Tianhao Ma
Wei Wang
Ximing Li
Gang Niu
Masashi Sugiyama
Venue: ICLR 2026 Poster (2026)
Keywords: Learning from label proportions
weakly supervised learning.
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning

Abstract: Learning from Label Proportions~(LLP) aims to use bags of instances associated with the proportions of each label within the bag to learn an instance-level classifier. Proportion matching is a widely used strategy that aligns the average model outputs of all instances in a bag with the label proportions in order to induce the classifier. However, simply fitting the label proportions does not encourage discriminative instance-level predictions and may cause over-smoothing problems, resulting in poor classification performance. In this paper, we propose a novel LLP approach that can mitigate the over-smoothing problems with theoretical guarantees. Rather than fitting the label proportions directly, we treat them as targets for an auxiliary proportional value classification task to induce the target classifier. Our approach only requires the incorporation of an aggregation function after the classification layer. We also introduce an efficient computational approach with a divide-and-conquer strategy. Extensive experiments on various benchmark datasets and under different bag-generation strategies demonstrate that our approach achieves superior performance compared with state-of-the-art LLP methods. The code is publicly available at https://github.com/TianhaoMa5/ICLR2026_LLP-PVC.

Published as a conference paper at ICLR 2026
LEARNING FROM LABEL PROPORTIONS VIA PROPOR- TIONAL VALUE CLASSIFICATION
Tianhao Ma
Wei Wang 1.2* Ximing Li
Gang Niu
Masashi Sugiyama 2,1
1 The University of Tokyo, Japan
2 RIKEN, Japan
3 Jilin University, China
(mat imatianha22120, 1122mmiiiiinnnee. gang. mwn.mmi..mm..mmmm ml @lgmaill.... com
wei aaaangrrienn ip sugiāk sugiakku-tokyee u-tokyo.acc. ac.
ABSTRACT
Learning from Label Proportions (LLP) aims to use bags of instances associ- ated with the proportions of each label within the bag to learn instance-level classifier. Proportion matching is widely used strategy that aligns the average model outputs of all instances in bag with the label proportions in order induce the classifier. However, simply fitting the label proportions does not en- courage discriminative instance-level predictions and may cause over-smoothing problems, resulting in poor classification performance. In this paper, we propose a novel LLP approach that can mitigate the over-smoothing problems with the- oretical guarantees. Rather than fitting the label proportions directly, we treat them as targets for an auxiliary proportional value classification task to induce the target classifier. Our approach only requires the incorporation of ag- gregation function after the classification layer. We also introduce an efficient computational approach with divide-and-conquer strategy. Extensive experi- ments on various benchmark datasets and under different bag-generation strate- gies demonstrate that our approach achieves superior performance compared with state-of ofrthe-art LLP methods. The code is publicly available at https: / //github com/ hwt.///annnaaaaaa/aaaaaaa I/CLR2022 LLP-PVC.
INTRODUCTION
Deep learning has achieved remarkable success, but its effectiveness usually relies on large, accu- rately labeled datasets, which are impractical in many real-world scenarios. To address this problem, various weakly supervised learning paradigms have been explored recent years, including semi- supervised learning (Zhu & Goldberg, 2009; Sohn al., 2020), noisy label learning (Han et al., 2018; Wei et al., 2022), partial-label learning (Wang et al., 2022; 2025), and similarity-base based classi- fication (Hsu et al., 2019; Bao et al., 2022).
Learning from label proportions (LLP) is an emerging weakly supervised learning paradigm that has recently attracted much attention (Quadrianto et al., 2009; Busa-Fekete al., 2023; Li al., 2024b). In LLP, the training dataset consists of bags of instances annotated with the class propor- tions in each bag, while the instance-level labels are inaccessible to the learning algorithm. The goal of LLP is to learn an instance-level classifier that assigns correct labels to test instances, as ordinary multi-class classification. Collecting bags of instances with label proportions is much easier and cheaper than collecting individual labels, which greatly reduces annotation costs. Further- more, I.LP provides an effective alternative when individual labels are inaccessible due to privacy concerns (Diemert et al., 2022). For example, in election polling, individual votes remain confi- dential, but aggregated results (such as regional support rates) are publicly available. By leveraging such bag-level data, LLP enables privacy-preserve trends) without accessing sensitive individual ballots. The need to learn from such inexact super- vision arises widely in real-world applications, including high energy physics (Dery et al., 2017),
analysis (e.g., predicting demographic voting
Corresponding author.

---

Published as a conference paper at ICLR 2026
Random bag SVHN
Random bag CIFAR10
Cluster bag SVHN
o-First bag CIFAR10
tetrog
0.8
0.6
Entrrep
60
Accurscy
Ertogg
0.5
pocuracy
Ca
Accuracy
04
0.0
9.0
0.0
Exech
Epach
Spach
Epoch
LUMPVC Acouracy
PM Accuracy
LLP PVC Entropy
PM Entropy
Figure I: Curves of the average normalized entropy values of unlabeled instances in the training set and the test accuracy (Acc) for PM (Yu et al., 2014), and LLP-PVC (proposed) with bag size of 128.
image classification (Li & Taylor, 2015; Ding al., 2017), medical data analysis (Bortsova al., 2018), and election prediction (Sun et al., 2017).
The most common strategy for LLP is proportion matching (Yu al., 2014; Ardehaly & Culotta, 2017; Li et al., 2024b), which aligns the average value of the model predictions of all the instances in the bag with the label proportion. 'he proportion-matching strategy has been shown be both concise and theoretically sound (Busa-Fekete et al., 2023; Li et al., 2024b) under the assumption that instances and labels are generated i..d. and then randomly grouped into bags. It has been widely adopted as the most common base loss in many LLP approaches, often combined with more sophisti- cated regularization techniques (Tsai & Lin, 2020; Ma et al., 2025). However, when applied deep neural networks, proportion matching does not promote discriminative instance-level predictions and often suffers from the over-smoothing problem. A typical failure mode is that the model may collapse to trivial solution where the model predictions of all instances approximate the same label proportion without distinction, which still fulfills proportion matching. Figure shows the curves of the average entropy of training instances and the test accuracy for different LLP approaches. We can observe that the proportion matching approach similarly exhibits inferior model performance, with high entropy values throughout the training process. This suggests that the proportion match- ing strategy merely enforces that the average bag prediction matches the label proportions and does not encourage discriminative instance-level predictions. This will produce inaccurate instance-level predictions, resulting in poor classification performance.
To overcome this problem, we introduce novel LLP approach with theoretical guarantees. In- stead of using the label proportions as targets for direct fitting, we use them as targets for a novel classification problem. We observe that there exists a relationship between the pos- terior probabilities of the discrete label proportion and those of the instances in the bags. This motivates us to induce target classifiers by solving an auxiliary proportional value classification (PVC) task, where we only need to add an aggregation function af- ter the classification layer of the original neural network to approximate the posterior probabilities of the propor- tional values. Figure shows that the model predictions of our proposed approach have lower entropy values than proportion matching strategies. This shows that our ap- proach mitigates over-smoothing problems and achieves better classification performance. Since the space of la- bel sequences is very large, we use the one-versus-rest strategy to simplify the computational process. Further- more, divide-anddconquee method is adopted to reduce the computational complexity by using the fast Fourier transform. Compared with the dynamic programming (DP) method (Shukla et al., 2023) with a time complexity of O(m²). achieve time complexity of O(m log m.)
Runtime (seconds)
14
10
K. K-NIIST: LUM-PG (DP)
CTEAR-10) I.P-PVC
CIFAR-10: 1L.P-PVC (DF)
64
120
236
512
Bag size
Figure 2: Runtime comparison of LLP- PVC and LLP-PVC (DP). The val- report the mean per-epoch runtime, computed by averaging over 30 epochs.
The superior efficiency of our proposed solution clearly demonstrated in Figure 2. Besides, our approach enables end-to-end training with comparable memory and efficiency requirements, and is flexibly compatible with any neural network architectures and optimizers.
Our contributions can be summarized as follows:
2

---

Published as a conference paper at ICLR 2026
Methodologically, propose novel LLP approach that works by solving auxiliary PVC problem to induce the classifier. We also introduce a wride-and-conquer method to improve computational efficiency.
Theoretically, we prove that the model predictions induced by our approach mitigate over- smoothing problems under certain assumptions. We also prove the convergence rate of the pro- posed risk estimator by providing an estimation error bound.
Empirically, our approach achieves superior classification performance over other state-of-the-art LLP methods across various datasets and different segggeneration strategies.
2
PRELIMINARY
Ordinary multi-class classification. Let X' S IR denote d-dimensional feature space, and Y' = {1.....g) 9} the label space with classes. Let p(x. y) be the joint density over (x, y) e X x y. The goal of multi-class classification is induce classifier f X V. which minimizes the following classification error:
Ro-1()) ( = Ep(a,)) [T((())) * y)],
where E is the expectation, and I is an indicator function that returns if the predicate holds; other- wise it returns However, since the 0-1 loss is difficult to optimize, we usually replace the 0-1 loss surrogate loss function L such the cross-entropy loss. The risk
with clasification-calibraa can be then written as follows:
R(f)
v)].
One-versus-rest (OVR) strategy. The OVR strategy is widely used multi-class classification method that decomposes the original multi-class problem into multiple binary classification sub- tasks (Rifkin & Klautau, 2004; Zhang, 2004). Specifically, the OVR risk is formulated as follows:
fe... = -Ep(n))))
(lfozz).)+
E ((fa(z).0) ke)
(3)
where each fE X' [0. a binary classifier that outputs the predicted probabilities for the positive class, and distinguishes class & from all the other classes and & is a binary loss function. The OVR risk can also be expressed as the sum of the bassswiiee risks (fx):
................................ fa) I== Ra(fa),
where Ra(fk) = Ep(aas) [Tl = k) ((f((a))) + D(y + ()((f(()))))
(4)
Learning from label proportions. In LLP, we are given a training set consisting of bags of in- stances, where each bag is associated with label proportion indicating the proportion of each label the bag. Specifically, we are given a training set = {(B', { i.i.d. drawn from a joint density p(B, ax.. Following Li al. (2024b). B [x1.... Fmml denotes bag consisting of m unlabeled instances, where the ground-truth -ran label sequence y = [y1..... yml is inaccessible to the learning algorithm; and
[a].... a,1 denotes the label proportion associated with B, where each element O% calculated as ag Σ T(y; = k)/m and we have Σi Og 1. In this paper, we consider the traditional LLP setting where bags B are generated i.i.d., while allowing the instances within each bag to be non-i.i.d.. The goal of LLP is to induce instance-level classifier f: y that can predict the labels of individual test instances.
METHODOLOGY
In this section, first present proposed approach via proportional value classification for learn ing from label proportions. Then, we present the theoretical analyses. Finally, we present an efficient solution of proposed approach.

---

Published as a conference paper at ICLR 2026
3.1 PROPORTIONAL VALUE CLASSIFICATION
The goal of our proposed approach is to induce an instance-level classifier by training an auxiliary classifier to assign label proportion vectors input bags. However, we find that the space of pos- sible label proportion vectors and their corresponding ground-truth label sequences is too large to be computationally tractable. In particular, according the stars and bars theorem in combina- torics (Brualdi, 2004), there are ("*+9-1) possible label proportion vectors for our problem. More-
over, for each possible label proportion vector a there are total of (m!)/ ( possible label sequences. Therefore, we use the OVR strategy to simplify the computation process. Without loss of generality, we present how to induce the binary classifier for class & e } in Section 3. Specif- ically, examples from class lc are regarded as positive w.r.t. class and examples from all the other classes are regarded as negative. In this way, the unknown ground-truth label sequence [V1,..., 3m) can be transformed as follows:
1. yj = K DTh where 07
(5)
0, Yj # k.
Note that ag in the original label proportion can also represent the proportion of positive ex- amples after using the OVR strategy w.r.t. class k, i.e., 0g " and we have ou
{0. 1/m, 2/m,.... 1}. Because of the discrete nature of the proportional values, we introduce the PVC problem to train a classifier to classify the bag as one of the proportional values.
Definition (Proportional value classification (PVC)). Without loss of generality, we consider class k. Let (B,āg) denote a pair of random variables with a joint density p (B, åt), where B is the random variable bag defined in Section 2. Also,
0% mog e
m m
(6)
is defined as the random variable of the corresponding proportional value label, which is determined by the label proportion a of the bag B. While proportional values naturally admit an ordinal formu- lation, in this work we adopt simpler (m + 1)-class multiclass approach: PVC trains a bag-level classifier gx (B) [9k, (B). (B).... Ik. [B)] that assigns each bag to one proportional value, with (B. denoting the probability of the 1-th proportional value. The goal achieved by minimizing the following PVC risk for class k:
Rd (gx) = (p(.a..) (B),
In particular, PVC can be seen as a special case of multi-class classification, the difference being that each example for PVC is associated with bag of instances instead of single instance in the input space. Furthermore, by using the OVR strategy for each of the classes and summing up every loss value, the total risk is
- E Rg(gg) = E Ep(B,au) (gx, āw)]
(8)
By transforming the original label proportions proportional values defined in Definition for the original training set, we can obtain a new training set Dj = {(B', a for class k. Since the data generation process of Dr is in accordance with that of the random variables (B, âg), we can consider DA as sampled i.i.d. from p (B, âr). We generate the data for each class and conduct empirical risk mininization to approximate Eq. (8) as
Th E 1= (g (B') aa))
Before introducing how to compute ga. we first clarify an implicit relationship between the posterior probabilities of the proportional values and those of the instances in the bags.
3.2 BRIDGING THE POSTERIOR PROBABILITIES OF PROPORTIONAL. VALUES AND INSTANCE-LEVEL LABELS
Obviously, there are 2d possible binary label sets corresponding to the labels of the instances in a bag. We introduce a posterior probability vector p (B) e [0, where the r-th dimen- sion represents the posterior probability of the r-th possible label sequence. Let Bin(r, m)
4

---

Published as a conference paper at ICLR 2026
669 bin) denote the m-bit binary representation of decimal number r. Here, bin is the least
significant bit while b/() is the most significant bit. For convenience, we consider the r-th possible label sequence to be the binary representation of (r-1) 1). For example, we have Bin(3, 3) 10, 1. 11, which is the 4-th possible label sequence within the 8 possible label sequences in total. Specifically, for the r-th label sequence, we assign
y [ii.....
] Bin(r 1, m)
66
b(--1)
(10)
which indicates that the label of each instance equals the corresponding bit of the binary representa- tion of (r 1). Then, based the independence of the instances in the bag, the r-th dimension of B) can be computed as
(g Bin(r 1, m) BB II
Th p(us of
22)), 12g), (1, 2"...
(11)
Furthermore, we introduce a matrix Q 10r.1]mmxmm+>
10 ((m+1), Here, each element dr.t = p(āz = 4 Bin(r - 1, m)) indicates the conditional probabilities proportional values given a binary label sequence. For ease of presentation, we introduce the Hamming weight function HW) which returns the number of the bits of ones in a binary number (Wei, 2002). Then, gr.t can be determined as
1, I HW (Bin(r 1, 1,)) + 1;
Vr
(1,2,..., 13, br.1 =
(12)
0, otherwise.
Based on the above definitions, introduce the following lemma.
Lemma 1. The posterior probability of the proportional value (ā)(B) and the posterior probabil- ities of the ground-truth labels of the instances pl PO (z.)) in the bag satisfy
pāaz -[BB -1B)= - 2
9r IT,-,
(p (p = 1|2,)) 1 6/--1)
p (0) = 0/2,,) (1-19-11)
(13)
The proof can be found in Appendix B. Lemma bridges the posterior probabilities of the propor- tional values and those of the ground-truth labels of instances. We provide an illustrative example to facilitate the understanding of the relationship of posterior probabilities.
[ x2] for m 2. Then, there are 4 possible label sequences {[o, 0], [0, 11, [1, 0J, [1, 1}} and 3 possible proportional values {1, 2, 3}. Based on Eqs. (11 and (12), we have Q and the following equations:
Example 1. Consider a bag
plā= BBB "p (j [0. BB = p (ūf 0/æ²) (ih 0/æ²2):
p(ā== 2[ =p (g = [0. B] + p (g² [1, [1,0]B] BB]
0
0
Q
0
=p (vt = 0/21) p (ih = 1|x2) + p (यt = 1|x,) ) p (5h = 0 0/22)
0
0
1
(p(ā= 3|B) =p (i+ = []] = (ūt = 1 (0t [x2)
Example 1 not only provides more intuitive understanding of the relationship of the posteriors of the proportional values and instance-level labels, but also further verifies Lemma 1. Based on the above observations,
binary classifier f& to approximate the instance-level posterior probabilities (i)² 1|z;) by using the sigmoid function. Then, we attempt to approximate the posterior probabilities of proportional values p(āx B) by using the bag-level classifier 9& (B) = (B., (B.) .km............. (B)], which is calculated as
I [B) = > g. II, m
(2,))
1) (1- fa (z (2,,))
,LE (1, m m+1. (14)
Here, Ir and 1f)-1) are constants that can be calculated in advance before the whole training pro- cess. Therefore, our approach does not introduce any hyperparameters. By taking the instantiation of gs into Eq. (8), we can relate the proposed classification risk with the introduced binary classifiers.
Let iR( .2, fq) and Í( f2,..., fa) denote the classification risk in Eq. (8) and empirical risk in Eq. (9) associated with binary classifiers, respectively. Then, we can train binary classifiers
fk. & (1, q). by minimizing R(,fa, f2..... fa) in Eq. (9) with datasets DR- The algorithmic details are summarized in Algorithm 1. We share the representation learning layers and use specific classification layers for different labels, which allows simultancous training of all binary classifiers effectively and efficiently.
5

---

Published as a conference paper at ICLR 2026
Algorithm LLP-PVC
Require: Binary classifiers f fa with shared represen- tation layers, LLP dataset D; maximum epochs Tax: maximum itcrations Imix.
Neural network
Ensure: Trained classifiers fi....:
(x) fu [mmm
1: for , Tim do
Shuffle
3: for L,..., max do
Computed using Eq (14)
4:
Fetch mini batch D, from D;
5:
Forward D, and get the outputs of fi....,
6:
Compute the output of g based on Algorithm 2; Update g. which induces an update on fi..... fq:
8:
end for
f(g: (B), az)
9:
end for
Figure 3: Pipeline of LLP-PVC.
3.3 THEOREEICAL ANALYSIS
Mitigation of over-smoothing problems. We show that the induced classifier can mitigate over- smoothing issues under certain assumptions. First, we show that the output of the bag-level multi- class classifier gı: and the set of outputs of the instance-level binary classifier Sy. have one-lo-one correspondence.
Theorem 1. The bag-level classifier gs. is an invertible aggregation of the instance-level binary classifier Ir in the following sense: The model output of the bag-level classifter gt: ( calculated by Eq. ( (14) uniquely determines the set of the instance-level model outputs (fx( [1, for B.
Proof Sketch (the full proof is given in Appendix B.3). Firstly, fu ( E (1...., m):
introduce
binomial for
Fx. fa(2x)) (1 fa(z)))
(15)
Then, define m-order polynomial as the product of all binomials:
m Gx(z) - II,-,, FR.(())
-
(f<(o))) (,"
fi(,))))))) _mm Cket
(16)
where Ck is the coefficient of 2¹. We have the following lemma.
Lemma For E {0, (,,..,.,,m) the coefficient cx.t in Eq. (16) coincides with the (t + 1)-th dimension of the model output of the bag-level classifier g, i.e., CK,t (B).
The proof is given in Appendix B.2. Lemma indicates that when the bag-level model output gB) is given, the m-order polynomial (x(z) can be determined. Notably, G₂(z) has m roots [1-1/f((z;)) and each root has a one-to-one correspondence to the model output of the mnstance-level classifier for instance. When G+(2) is uniquely determined, the roots uniquely determined correspondingly. Then, we can prove by contradiction that the set of model outputs of the instance-level classifier is also determined uniquely since an m-order polynomial most has m different roots.
Theorem 1 illustrates the one-to-one relationship between instance-level model outputs and bag- level model outputs based on Eq. (14). Once the model output of the bag-level classifier given, then the set of the model outputs of the instance-level classifier can be determined. Let g arg ming. R2 (gk) denote the optimal classifier that minimizes Eq. (7). Then, the following theorem holds.
Theorem 2. Assume that the cross-entropy loss or the mean squared error (MSE) loss is used to instantiate L, and that the hypothesis class G for learning g& is sufficiently flexible so that 9 G. Let f denote the optimal binary classifier induced by g then have (f2(2,) {r(0) 1 x,) 25) If we further assume that the instance labels are deterministic, then it follows that f (n,) (0,1).

---

Published as a conference paper at ICLR 2026
The proof can be found in Appendix B.4. According to Theorem 2. when the labels are deterministic, the outputs of the minimizers will be 0 or if the proposed risk in Eq. (7) is minimized. This suggests that our approach mitigates the over-smoothing problems of proportion matching strategies, where the model outputs of different instances in the bag may indiscriminately fit the given label proportion values. Furthermore, we observe that the set of outputs of f coincides with the set of posterior probabilities of class k for the instances. We leave for future work the investigation of the role of this property in training instance-level classifiers.
f.) arg fi R(Si, f2 f2...., fu) denote the optimal classifiers by minimizing Eq. (9). Let d denote the diuuddddmmnnionn of the model class F.!
Estimation error bound. Let f2....
Theorem 3. Assume that the cross-entropy loss MSE loss is used to instantiate L. The following inequality holds with probability at least - 6:
dm3 n
RR, K.f.......... fa) -
O,
a
(17)
where Op hides logarithmic factors log m and logn, n, and the subscript p denotes the order in prob- ability.
The proof is given in Appendix B.5, Theorem 3 shows an estimation error bound for the proposed risk estimator. When the number of bags tends to infinity, the risk of the classifiers obtained by minimizing Eq. (9) converges to the risk of the optimal classifiers. The former works "Busa-Fekets al., 2023; 2025) differ from ours two respects. First, they impose stronger within-bag i.i.d. assumption on instances. Under this stronger assumption, they can recover instance-level poste- rior probabilities, whereas under our weaker assumption we can only recover bag-level posterior probabilities. Consequently, their bounds are not directly comparable with ours.
3.4 AN EFFICIENT COMPUTATIONAL SOLUTION
Computing I (B) is equivalent to computing the coefficients CK,1-1 in Eq. (16), which involves the product of m binomials. The time complexity of computing Eq. (16) is 2nh which is intractable for large bag sizes. To solve this problem, we propose a novel, significantly more efficient method that leverages the fast Fourier transform (FFT). 2 The Convolution Theorem (Oppenheim, 1999; Cormen et al., 2022) states that the coefficients of the product of two polynomials can be obtained by taking the inverse Discrete Fourier Transform (DFT) of the pointwise product of their DFT-transformed coefficient vectors. Since the time complexities of the product computation can be greatly reduced in the frequency domain, this inspires us to use the DFT to compute Eq. (16). We use a divide-and conquer approach by calculating the product of polynomials pairwise with multiple iterations of repetitive procedure. First, we group the m binomials pairwise in sequence and pad the coefficient vector for each binomial as
j [A__j.o- Pk..
Am.jj.m = [1 fu((z)) fa()), 0, 0] R--1
where h denotes the t-th order coefficient for the j-th binomial. Then we transform h2 into its
frequency-domain representation HD. = HD [ HD k.j.1>..... Specifically, we have
HD k.j.m by the (m + 1) 1)-point DFT.
m Ex 1.j. exp (-2ri 2 m + =
tt'
Hh
10.,,2....,,)?
(18)
Then, in the s-th iteration, the goal is to compute the product of N, polynomials grouped pairwise, and we have N₁ = m. By the Convolution Theorem, the frequency representation of the coefficients for the polynomial of the product each group can be determined as the elementwise product of the frequency representations of each polynomial, i.e.,
O k.2j' jE 21,2.....
H
(19)
H 11
N.+1 and N₂ is odd,
Psscudodimmnssoon extends VC dimension to real-valued classes (Anthony & Bartlett, 2009). Phtpps: / /i thub. com wttp...o//ptooretttecoooo cowmpyytorrcppytrrttt http://o///mm//mot///////e/e
7

---

Published as a conference paper at ICLR 2026
where Q denotes elementwise product and |-| denotes rounding down the nearest integer. Here, when N, is an odd number, we leave the last polynomial unchanged for the next iteration. Then, Higj is used the frequency-dond domain representation of the polynomials for the product in the (s + 1)-th iteration. After [log2(m) 1)] iterations, arrive the target single frequency-doman representation H H H (m=+ 1)] where [-] denotes rounding up to the nearest integer. Notably, H is the sequuency-dmaalle representation of the coefficients of the polynomial in Eq. (16). Then, we recover the coefficients from H by applying the (m + 1)-point inverse DFT. Specifically, for r re {0, 10.11........ we have
8.1
m 21== H exp +2Ti rt
1
Chr
(20)
m
Finally, according to Lemma 2, we have (B) Ck,l-1-
Proposition 1. For a bag B of size m, computing the model output (B) via the divide-and- conquer-based algorithm on graphics processing unit (GPU) has runtime of O(m log m).
The proof is given in Appendix B.6. Compared with the dynamic programming- method (Shukla al., 2023) with a time complexity of O(m²), our lower time complexity ben- efits from the efficient execution of operations in Eqs. (18), (19), and (20) on GPUs.
EXPERIMENTS
In this section, we first present the experimental setup. Then, we present the experimental results and the execution time analysis.
4.1 EXPERIMENTAL SETUP
We used four widely used datasets, including Kuzushiji-MNIST (K-MNIST). Fashion-MNIST (F- MNIST), SVHN, and CIFAR-10. We adopted three different bag generation strategies: Random bag: the dataset is randomly shuffled and then randomly assembled into bags; ii) Cluster bag 3: first cluster the dataset into predefined number of clusters, and then form bags by sampling instances from these cluster-based groups; iii) a-First bag 4: for each bag, we first sample a bag- level class proportion from Dirichlet distribution, and then draw instances from each class pool to match the sampled proportions. For all bag generation strategies, the bag size m is varied as powers of two, i..., {4.8, 128).
We compared our approach against five state-of-the-art L.PP methods: PM (Yu et al., 2014; Ardehaly & Culotta, 2017), DSQ (Li al., 2024a), EasyL.LP (Busa-Fekete et al., 2023), FasyL.LP-food and ROT (Dulac-Arnold et al., 2019). Here, FasyLLPP-looo refers to EasyL.LP enhanced with the flooding regularization technique (Ishida al., 2020). To ensure fair comparisons, all methods shared the same hyperparameter settings. More details can be found in Appendix D.
4.2 EXPERIMENTAL RESULTS
Tables 1, 2, and 3 present the experimental results for various datasets and bag generation strategies, showing that LLP-PVC consistently achieves state-of-the-art performance across different bag sizes. First, LLP-PVC can recover an optimal set of instance-level predictions; together with the represen- tation learning capability of neural networks, the model can further assign these predictions to the correct instances across bags. Second, LLP-PVC learns more discriminative instance-level decision functions, rather than merely fitting bag-level label proportions, as standard proportion-matchin approaches do. Third, our formulation is straightforward to optimize in practice and avoids known optimization pitfalls of some prior methods (e.g., the negative-risk issue in EasyLLP), leading to stable training and strong performance. Fourth, our method does not rely on the within-bap i.i.d. assumption and remains robust across diverse gagggeneration mechanisms.
4.3 EXECUTION TIME ANALYSIS
Because computing the loss requires an extra processing step, we report the corresponding run- time in Table 4. We additionally evaluate two methods, UUM (Wei al., 2023) and Count
8

---

Published as a conference paper at ICLR 2026
Table 1: Accuracy results (mean std) under Random Bag construction. The best-performing method for each bag size is highlighted in bold.
Dataset
Method
128
PM
93.19 = 0.99
90.88 0.87
83.52 1.01
11.10
2.07
51.05 + 4.22
28.30 + 1.29
0.85
0.73
2.26
1.21
2.52
EasLLP
72.56 2.32
67.40 4.28
63.48
5.33
56.93
1.36
50.60
1.46
48.56
2.84
K-MNIST
PasyL.LP.food
86.47 0.21
83.89
0.99
81.03
0.56
75.99
1 2.12
70.48
2.13
63.87
1.26
ROT
96.40 = 0.41
96.21
0.24
94.29 : 0.31
90.14
0.51
73.00
4.23
43.37 2.37
LLP-PVC
96.55 0.09
96.62 0.29
0.22 96.68
0.15 96.10
96.76
0.15
0.16 96.36
PM
88.36 0.57
86.87 0.55
84.44 0.73
80.21 1.08
75.81
0.68
66.78 5.29
DSQ
77.82 0.76
77.91 0.43
77.73 0.77
77.22 0.80
77.14 0.42
75.82 0.82
EasyLLP
74.31 2.22
73.59 1,83
72.27 4.71
71.75 1.57
68.13 0,39
66.27 0.84
F-MNIST
85.89 0.11
0.29 85.89
83.45 0.18
82.06 0.85
79.22 4: 0.37
73,69 0.35
ROT
0.60
LLP-PVC
91.39 0.33
91.84 0.15
91.70 0.28
90.32 0.42
89.28 0.02
87.17 0.16
PM
92.50 = 0.10
91.36 0.07
0.34
0.77
43.18 0.72
DSQ
78.22 0.12
77.77 0.23
76.61
0.07
73,97 0.65
65.79 1.37
50,03 1.50
EasLLLP
76.95 1.27
68.87 1.10
39.77 = 1.10
51.49 +: 1.02
37.76
2.31
32.62 + 2.18
SVHN
EasoLLP-dood
0.44
81.06 0.58
0.62
67.77 0.49
57.97 0.81
47.80 3.16
1.45
LLP-PVC
94.30 0.05
94,50 0.06
94,56 0.14
94.61 0.08
94.27 0.15
93.60 0.76
PM
82.03 0.34
80.23
0.51
0.42
68.51
60.47 0.20
49.21 0.38
DSQ
69.50 0.43
69.32 0.27
67.99 0,50
0.22 65,74
60.70 + 0.16
51.35 + 0.64
EwsLLP
66.89 0.18
63.47 0.59
56.92 0.75
51.81 0.52
44.19 0.94
37.36 1.87
CIFAR-10
FasyL.LP.loon
0.19
0.37
ROT
83,76 0.25
82,02 0.18
80,37 0.09
77.09 0.07
69.59 1.28
33.70
8.02
LLP-PVC
84.34 0.26
84.43 0.33
84.50 0.22
82.44 0.29
78.90
0.44
76.01 + 0.97
Table Accuracy results (mean std over seeds) under Cluster Bag construction. The best method for each bag size is in bold.
Dataset
Method
4
8
16
32
64
128
PM
92.89 0.15
91.05
0.41
86.94
0.11
81.60
1.11
76.56
1.25
72.49 + 1.61
DSQ
67.92 3.03
72.32
0.79
74.57
1.04
75.19
1.06
2.12 75.56
75.24 2.31
EasyLLP
0.66
1.25
K M-NISTT
EasyLLP-food
60.95 0.68
57.08
0.01
50.42
1.13
41.85
2.96
35.27 + 2.77
26.72 + 0.63
ROT
94.64 0.19
93.68
0.09
91.62
0.33
87.35 +: 0.25
82.51 + 1.22
77.04 + 0.95
PM
88.25 0.30
86.75 - 0.31
84.44 0.12
81.88 + 0.48
79.23 + 1.02
77.60 0.41
0.52
F-MNIST
EasLLPP
26.82 1.40
16.24 4.76
12.64 3.68
10.04 0,00
10.04 0.00
10.04 0.00
EasyLLP food
73.07 0.62
71.33
0.03
63.54 0.78
$3,03 3,80
46.88 1.55
40.91 2.68
ROT
89.93 0.26
88.48
0.20
86.77 = 0.10
84.18 0.46
81.62 + 1.13
79.41 0.63
LLP-PVC
91.47 0.06
0.06 91.68
91.39 0.20
90.51 - 0.12
89.16 0.23
87.15 0.29
PM
92.50 0.09
91.34 + 0.06
88.75 0.08
81.93 0.31
66.84 4 1.25
48.69 1.24
0.15
SVHN
EasyLLP
70.54 = 0.71
53,57 0.48
36.18 1018==00
27.16 1116-000 0.75
20.62 1.07
19.86 0.48
FasyI.LPPAlw
84.86 0.03
81.32 0.14
75,84 0.53
67.29 0.61
60.04 + 0.10
48.79 4.00
ROT
0.15 94.84 0.23
PVC
94.34 0.09
94.43 0.15
94.61 0.15
94.54 0.02
93,89 0.65
0.28
0.60
0.52
0.59
0.53
DSQ
69.97 0.33
69.59 0.21
68.64 0.35
66.35
0.51
63.28 0.47
59.55 0.45
EasyLLP
55.32 0.26
43.72 0.91
33.71
0.61
24.92 2: 0.97
19.57 2.38
16.46 +: 0.33
CIFAR-10
PastoLLP
0.51
0.53
52.67
1.02
42.12 1.93
34.10 0.99
29 0.45
ROT
82.11 0.57
80.31
0.17
63,94 0.25
I.I.P.VC
84.63 0.09
84.61 0.06
83.97
0.04
82.00 0.38
79.94 + 0.19
78.36 0.50
Loss (Shukla et al., 2023). For Count Loss, we directly extend the original count-based formula- tion to the multiclass classification setting. As shown in Table 4, our method achieves nearly the same runtime full parallelism. Due to the high time complexity, UUM and Count-Loss are not suitable for large bags, limiting their practical applicability. As shown in Figure 2, the execution time of LLP-PVC remains consistently low as the bag size increases, while LLP-PVC (DP) increases significantly with larger bag sizes, becoming ten times slower when the bag size is large.
-t1m baselines because the loss can be computed entirely the GPU with

---

Published as a conference paper at ICLR 2026
Table Accuracy results (mean std over seeds) under a-First Bag construction. The best method for each bag size is in bold.
Dataset
Method
128
PM
93.07 0.28
90.25
0.82
71.58 +: 1.62
43.23
2.39
37.03 + 2.77
33.16 + 3,89
3.39
59.19
EasLLPP
63.66 1.21
78.26
1.72
74.43
1.52
67.08
1.67
60.56
2.87
36.78
2.15
K-MNIST
PasyL.LP.food
82.58 0.20
81.07
1.26
74.59
2.33
66.92
1.83
62.28
1.65
64.41 4: 2,03
ROT
94.84 0.18
93.58
0.32
82.85
2.00
68.31
3.27
59.21
4.17
54.59 1 2:10
LLP-PVC
95.29 1.26
0.37
0.43 96.50
0.14
96.61
0.13
96.33
PM
88.59 0.18
86.66 0.09
79.50 0.62
75.34 +: 0.33
72.46 13.66:0000
70,02 +
DSQ
0.31
76,91
0.27
71.21 1,70
71.28 2.23
75.33 +.20
76.76 0.49
EasyLLP
69.23 0.97
81.83 0.62
81.64 0.23
78.80 0.06
74.00 + 0,74
45.69 6,23
F-MNIST
85.40 0.06
84.11 0.53
81.94 0.61
78.54 0.35
75.09 + 0.22
77.49 0.58
ROT
LLP-PVC
90.52 1.96
91.19 0.94
91.53 0.22
90.56 0,18
89.32 0.71
87.55 0.34
92.46 0.05
91.32
0.02
0.06
0.07
+ 0.18
0.21
DSQ
79.52 0.07
75.99 0.15
63.44 0.20
63,47 0.21
67.63 0.14
66.93 0.09
EasLLLP
76.77 0.41
67.45 0.66
45.81 = 0.84
39.43 1.02
35.84 + 1.06
31.98 1 2.61
SVHN
EasoLLP-dood
0.14
79.13
58.08 2.27
63.69 0.80
61,00 0.80
LLP-PVC
94.35 0.02
0.08 94.45
94,55 0.03
94,53 0.11
94.31 0.09
94,20 0.28
PM
0.19
0.14
0.39
56.77
0.65
54.08
54.65 0,92
DSQ
70.13 0.20
67.28 0.19
55.00 + 0.62
53.76
0.91
54.64 + 0.62
56.33 0.91
EwsLLP
67.22 0.13
61,02
0.16
46.23 0.61
1 0.77 41.42
41.06 0.59
40.71 0.94
CIFAR-10
FasyL.PP.loa
ROT
82.42 0.29
80,32 0.19
66.43 0.16
59.36 0.49
56.22 0.55
57.28 0.69
LLP-PVC
84.89 0.19
84.83 0.13
83.08 0.22
80.18 0.09
76.70 + 0.20
76.36 +: 0.34
Table 4: Execution time results (mean over 30 epochs) under the same settings on a single NVIDIA A 100 GPU. "GPU parallelizable" indicates whether bags within batch be processed in parallel on the GPU, indicates that results could not be obtained within reasonable time due to the combinatorial explosion of bag size. t denotes the number of iterations used when computing the optimal transport (e.g., in the Sinkhorn algorithm).
K-MNIST
CIFAR-10
Time Complexity (per bag)
GPU Parallelizable
Method
16
32
4
16
32
PM
2.59
2.63
2.45
2.49
3.63
3.46
3.86
2.97
O(1)
DSQ
2.53
2.72
2.04
2.08
3.28
3.67
3.59
2.88
0(1)
EasyLLP
2.89
2.87
1.81
1.62
3.07
3.01
2.91
2.66
0(1)
V
EasyLLP-
1.67
3.13
2.78
2.33
O(1)
ROT
20.92
11.63
5.85
3.56
17.83
10.82
6.68
4.55
( m ()
X
UUM
35.88
55.62
28.37
44.25
O (mm)
X
Count Loss
119.23
172.34
98.01
139.52
O (mr!
X
LLP-PVC
2.77
2.91
1.78
1.80
3.02
3.01
3.48
2.93
O l)gm) m)
V
CONCLUSION
In this paper, we proposed a novel approach for L.P by solving an auxiliary proportional value classification problem. We demonstrated that our approach can mitigate the over-smoothing issues of the proportion matching strategies both theoretically and empirically. We also introduced an efficient computational approach with divide-and-conques strategy. Extensive experiments with different bag construction strategies validated the effectiveness of the proposed approach. future work, aim to extend framework such dynamic environments, guided by novel metrics like OpenworldAUC (Hua et al., 2025), and to incorporate differential privacy (Dwork et al., 2006) to protect instance-level data.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
WW was supported by the Junior Research Associate (JRA) program of RIKEN. MS supported by JST ASPIRE Grant Number JPMJAP2405.
ETHICS STATEMENT
This paper presents work that focuses on the methodology of weakly supervised machine learning and does not raise any ethical concerns.
REPRODUCIBILITY STATEMENT
The details of the experimental setup can be found in Appendix D. The code implementation can be found at https: /ttp//gitttta com hww.raaaaaaaaaaaaaaaaaa PPV..
REFERENCES
Martin Anthony and Peter Bartlett. Neural network learning: Theoretical foundatiooo cambridge university press, 2009.
Lorne Applebaum, Travis Dick, Claudio Gentile, Haim Kaplan, and Tomer Koren. Optimal learning from label proportions with general loss functions. arXiv preprint 4rXiv:2509.15145, 2025.
Ehsan Mohammady Ardehaly and Aron Culotta. Co-training for demographic classification using deep learning from label proportions. In ICDMW, pp. 1017-1024, 2017.
Han Bao, Takuya Shimada, Liyuan Xu, Issei Sato, and Masashi Sugiyama. Pairwise supervision can provably elicit decision boundary. In AISTATS, pp. 2618-2640, 2022.
Dimitri P Bertsekas. Nonlinear programming. Journal the Operational Research Society, 48(3): 334-334, 1997.
Gerda Bortsova, Florian Dubost, Silas Ørting, Ioannis Katramados, Laurens Hogeweg, Laura Thom- sen, Mathilde Wille, and Marleen de Bruijne. Deep learning from label proportions for emphy- sema quantification. In MICCAI, pp. 768-776. Springer. 2018.
Anand Brahmbhatt, Rishi Saket, and Aravindan Raghuveer. Pac learning linear thresholds from label proportions. In NeurIPS, pp. 66610-66646, 2023.
Richard A. Brualdi. Introductory Combinatorics. Pearson Education India, 2004.
Róbert Busa-Fekete, Heejin Choi, Travis Dick, Claudio Gentile, and Andrés Muñoz Medina. Easy learning from label proportions. In NeurlPS, pp. 14957-14968, 2023.
Robert Busa-Fekete, Travis Dick, Claudio Gentile, Haim Kaplan, Tomer Koren, and Uri Stem- Nearly optimal sample complexity for learning with label proportions. arXiv preprint arXiv:2505.05335, 2025.
Lin Chen, Gang Fu, Amin Karbasi, and Vahab Mirrokni. Learning from aggregated data: Curated bags random bags. arXiv, 2023.
J. W. Cooley and J. W. Tukey. An algorithm for the machine calculation of complex fourier series. Mathematics of Computation, 19(90):27-331,, 1965.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022.
Lucio Mwinmaarong Dery, Benjamin Nachman, Francesco Rubbo, and Ariel Schwartzman. Weakly supervised classification in high energy physics. Journal of High Energy Physics, 2017(5) 2017.
Eustache Diemert, Romain Fabre, Alexandre Gilotte, Fei Jia, Basile Leparmentier, Jérémie Mary, Zhonghua Qu, Ugo Tanielian, and Hui Yang. Lessons from the AdKDD'21 MI. challenge. In WwW. pp. 2026-2035, 2022.

---

Published as a conference paper at ICLR 2026
Yongke Ding, Yuanxiang Li, and Wenxian Yu. Learning from label proportions for sar image clas- sification. Eurasip Journal on Advances in Signal Processing, 2017:1-12, 2017.
Gabriel Dulac-Amold, Neil Zeghidour. Marco Cuturi, Lucas Beyer, and -han-philippe Vert. Deep multi-class learning from label proportions. arXiv preprint urXiv: /2909, 2019.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, pp.
2006.
Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels, In NeurlPS, pp. 8536-8546, 2018.
Yen-Chang Hsu, Zhaoyang Lv, Joel Schlosser, Phillip Odom, and Zsolt Kira. Multi-class classifica- tion without multi-class labels. In ICLR, 2019.
Cong Hua, Qianqian Xu, Zhiyong Yang, Zitai Wang, Shilong Bao, and Qingming Huang. Open- worldAUC: Towards unified evaluation and optimization for open-world prompt tuning. In ICML, pp.
2025.
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, 2020.
Ryuichi Kiryo, Gang Niu, Marthinus du Plessis, and Masashi Sugiyama. Positive-unlabeled learning with non-negative risk estimator. In NeurIPS, pp. 1674-1684, 2017.
Changehun Li, Yuanchao Dai, Lei Feng, Ximing Li, Bing Wang, and Jihong Ouyang. Positive and unlabeled learning with controlled probability boundary fence. In ICML. pp. 27641-27652, 2024a.
Fan and Graham Taylor. Alter-CNN: An approach to learning from label proportions with appli- cation to ice-water classification. In Proceedings of the Neural Information Processing Systems Workshops on Learning and Privacy with Incomplete Data and Weak Supervision, pp. 100-106, 2015.
Gene Li, Lin Chen, Adel Javanmard, and Vahab Mirrokni. Optimistic rates for learning from label proportions. In COLT, pp. 3437-3474, 2024b.
Jiabin Liu, Bo Wang, Zhiquan Qi, Yingjie Tian, and Yong Shi. Learning from label proportions with generative adversarial networks. In NeurlPS, pp. 7167-7177, 2019.
Jiabin Liu, Bo Wang, Xin Shen, Zhiquan Qi, and Yingjie Tian. Two-stage training for learning from label proportions. In IJCAI, pp. 2737-2743, 2021.
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, pp. 6717-6734, 2019.
Nan Lu, Tianyi Zhang, Gang Niu, and Masashi Sugiyama. Mitigating overfitting in supervised classification from two unlabeled datasets: A consistent risk correction approach. In AISTATS, pp. 1115-1125, 2020.
Nan Lu, Zhao Wang, Xiaoxiao Li, Gang Niu, Qi Dou, and Masashi Sugiyama. Federated learning from only unlabeled data with maas-conditional-sharngg clients. In ICLR, 2022.
Tianhao Ma, Han Chen, Juncheng Hu, Yungang Zhu, and Ximing Li. Forming auxiliary high- confident instance-level loss to promote learning from label proportions. In CVPR, pp. 20592- 20601, 2025.
Hamed Masnadi-Shirazi and Nuno Vasconcelos. On the design of loss functions for classification: theory, robustness outliers, and SavageBoost. In Daphne Koller, Dale Schuurmans, Yoshua Bengio, and Léon Bottou (eds.), NeurIPS, pp. 1049-1056, 2008
Alan V. Oppenheim. Discrete-time signal processing. Pearson Education India, 1999.
12

---

Published as a conference paper at ICLR 2026
Novi Quadrianto, Alex J Smola, Tibério S Cactano, and Quoe V Le. Estimating labels from label proportions. Journal of Machine Learning Research, 10:2349-2374, 2009.
Ryan Rifkin and Aldebaro Klautau. In defense of one-vs-all classification. Journal of machine learning research, 5(Jan):101-141, 2004.
Rishi Saket. Learnability of linear thresholds from label proportions. In NeurlPS, pp. 6555-6566, 2021.
Rishi Saket. Algorithms and hardness for learning linear thresholds from label proportions. In NewrlPS, pp. 1267-1279, 2022.
Clayton Scott and Jianxin Zhang. Learning from label proportions: A mutual contamination frame- work. In NeurIPS, volume 33, pp. 22256-22267, 2020.
Vinay Shukla, Zhe Zeng, Kareem Ahmed, and Guy Van den Broeck. A unified approach to count- based weakly supervised learning. In NeurlPS, pp. 38709-38722, 2023.
Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A. Raffel, Ekin Dogus Cubuk, Alexey Kurakin, and Chun-Liang Li. FixMatch: Simplifying semi-supervised learning with consistency and confidence. In NeurlPS, pp. 996-608. 2020.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Optimistic rates for learning with smooth loss. arXiv preprint arXiv: 1009.3896, 2010.
Masashi Sugiyama, Han Bao, Takashi Ishida, Nan Lu, Tomoya Sakai, and Gang Niu. Machine learning from weak supervision: An empirical risk minimization approach. MIT Press, 2022.
Tao Sun, Dan Sheldon, and Brendan O'Connor. A probabilistic approach for learning with label proportions applied to the us presidential election. In ICDM, pp. 445 454. IEEE, 2017.
Kuen-Han Tsai and Hsuan- Tien Lin. Learning from label proportions with consistency regulariza- tion. In ACML, pp. 513-528, 2020.
Vladimir Vapnik. Statistical learning theory. John Wiley & Sons, 2, 1998.
Haobo Wang, Ruixuan Xiao, Sharon Li, Lei Feng, Gang Niu, Gang Chen, and Junbo Zhao. PiCO: Contrastive label disambiguation for partial label learning. In ICLR, 2022.
Wei Wang, Dong-Dong Wu, Jindong Wang, Gang Niu, Min-Ling Zhang, and Masashi Sugiyama. Realistic evaluation of deep partial-label learning algorithms. In ICLR, 2025.
Jiaheng Wei, Zhaowei Zhu, Hao Cheng, Tongliang Liu, Gang Niu, and Yang Liu. Learning with noisy labels revisited: A study using real-world human annotations. In ICLR, 2022.
Victor K. Wei. Generalized hamming weights for linear codes. IEEE Transactions on Information Theory, 3715):1112-1118, 2002.
Zixi Wei, Lei Feng, Bo Han, Tongliang Liu, Gang Niu, Xiaofeng Zhu, and Heng Tao Shen. A universal unbiased method for classification from aggregate observations. In ICML, pp. 36804 36820, 2023.
Zixi Wei, Senlin Shu, Yuzhou Cao, Hongxin Wei, Bo An, and Lei Feng. Consistent multi-class classification from multiple unlabeled datasets. In ICLR, 2024.
Haoran Yang, Wanjing Zhang, and Wai Lam. two-stage training framework with feature-label matching mechanism for learning from label proportions. In ACML, pp. 1461-1476, 2021.
Felix X Yu, Krzysztof Choromanski. Sanjiv Kumar, Tony Jebara, and Shih-Fu Chang. On learning from label proportions. arXiv preprint arXiv:1402.500 2014.
Jianxin Zhang, Yutong Wang, and Clayton Scott. Learning from label proportions by learning with 2022.
label noise. In NeurIPS, pp.
Tong Zhang. Statistical analysis of some multi-category large margin classification methods. Journal of Machine Learning Research, 5(0ct): 1251, 2004.
Xiaojin Zhu and Andrew B. Goldberg. Introduction to semi-supervised learning. Synthesis Lectures Artificial Intelligence and Machine Learning, 3(1):1-130, 2009.
13

---

Published as a conference paper at ICLR 2026
A RELATED WORK
To train an instance-level classifier from unlabeled bags with label proportions, several related works build on the moppotion-mmtccing loss and enhance it with additional regularization components, such as consistency regularization (Tsai & Lin, 2020; Yang et al., 2021), generative adversarial networks (Liu et al., 2019), and pseudo-labeling (Liu et al., 2021; Ma et al., 2025). Notably, these components are widely used across weakly supervised learning in general, often independently of the LLP setting.
A large body of existing methods assumes that instances within each bag are i.i.d., and under this as- sumption, variety of algorithms with theoretical guarantees have been developed. Wei et al. (2023) proposed UUM, a risk-consistent approach using the importance weighting technique. Although UUM has solid theoretical guarantees, the computational complexity of the posterior probabilities grows exponentially as the number of instances in each bag increases. FasyL.LP (Busa-Fekete et al., 2023) and GeneralUPM (Applebaum al., 2025) both derive an unbiased risk estimator for the instance-level classification risk, yielding a method that is simple to implement yet theoretically well-founded. However, the potentially negative terms in the risk estimator can often lead vere overfitting problems and performance degeneration (Li et al., 2024b), which is a common phenomenon other weakly supervised learning problems (Kiryo al., 2017: Lu al., 2020; Sugiyama et al., 2022). Li et al. (2024b) proposed DSQ, a variant of the proportion matching strat- egy. DSQ enjoys the optimistic convergence rate under both feasible and agnostic cases. However, DSQ restricts the loss function to the mean squared loss, which may be suboptimal in many clas- sification cases. The latest study (Busa-Fekete et al., 2025) considers only the binary setting and developed specifically for the mean squared loss. The count loss (Shukla et al., 2023) does not rely on the within-bag instance i.i.d. assumption. It adopts a maximum-likeliiaen provides a synaaic-programmiin based procedure compute the posterior probability of the label proportion within a bag. However, it is formulated for binary classification, and a straightforward extension to the multiclass setting would incur prohibitively high computational cost. These draw- backs make them less useful in real-world LLP applications where requirements are difficult to meet. Table 5 summarizes the characteristics of different sate-of-the-ar LLP approaches and our proposed approach.
formulation and
In addition, we adopt the traditional LLP setting where bags are sampled i.i.d., while allowing the instances within each bag to be potentially non-i.i.d. This is arguably more practical, since in real- world applications bags are often constructed by heuristic grouping (Chen et al., 2023; Tsai & Lin, 2020), which can induce within-bag correlations. Simultaneously, we do not include approaches from related but different settings for comparison, since they are often tailored to more specialized assumptions problem formulations. unlabeled-unlabelee (UU) learning (Lu et al., 2019; 2022; Wei et al., 2024) considered the class priors different bags to be different and we do not include related approaches for comparison (Scott & Zhang, 2020; Zhang et al., 2022). Saket (2021; 2022) allow the same instances to appear in multiple bags simultaneously. Brahmbhatt et al. (2023) further assume that instances are sampled from a Gaussian distribution.
Table 5: Comparison of different LLP approaches.
Dealing with 2+ classes
No negative loss risk
Compatible with large hag
Computible with any loss function
No Lid. assumpsion about within-bag instances
Appreach
PM (Yu al, 2014)
/
UUM (Wei et 2023)
EasyLLP FeuettFFkete et al, 2023)
Count Loss (Shukla et al. 2023)
DSQ al., 2024b)
Busa- FaketFokkic et al. (2025)
x
X
PM (Applebaum al., 2025)
X
L.P.PVC
14

---

Published as a conference paper at ICLR 2026
B PROOF
B.1 PROOF OF LEMMA
plān B P
m (-,n
13 -1BB
[HH (Bin(r 1, m,m 1 1) ||
m
p (1z =b- 1/00111223 (x))
-- drd1 IT (p(Uf- -1/0,)) 0/--1 (3) 0/25;) (1-0
which concludes the proof.
B.2 PROOF OF LEMMA 2
For each r (,....,2)), we have
Bin(r 1, m) (b(--1)
bin-1)),
S. S, = {j 15 (1 1) [m]]
It is obvious that |S,| 2ÿ-1 03 1(--1)
Since 4rd1 p(āx 111" Bin(r-1,m)) T[[S,] 1-1),
have
[B. = Σ
-= Ard IT, fx(2e) 1/-
2
10"00011 (1- fx((x)) 1-6
2
I([SrI - 1) 11 II,es. fx( 11 Ljes, (1- fx(2,))
(21)
jES,
8m(m] II 11-1-1
jES fx((z)) IT fx(2x)).
We use the elementary identity
IT Th
(a b,)
(b))+bb)==+
b Es (Il as) (I
Taking = fx(z)) = and by = 1 fa(w)), we have
Ga(z)= = Σ sg/mm (TTes (i((z)) (IT
(ITyes/ (1 f((z))
(22)
Σ m
11- Ckee
where
CK.t
Σ S=|m [m] [S|=t
f&r (zz))
(esss (1-((()())
(23)
jEs
Based on (21) and (23), setting
l 1- shows that
C = I
te (0....,m]
The proof is completed.
B.3 PROOF THEOREM 1 Firstly, we introduce binomial for fu(x)), {1...., m!)
(x.((2) fa(xx)2 (1 fa(x)))
Then, we define an m-order polynomial as the product of all m binomials:
Gx(z) = IT. I (x) = IT," m (f((z))= + (1 fu(),))) = > Cket
where Ck.t is the coefficient of z", which can be determined by Lemma 2. The m-order polynomial Gz(()) have roots (1 1/fx(a,))) y- Suppose there exist another different set of model outputs
15

---

Published as a conference paper at ICLR 2026
of the Instance-level classifier (f)() that can lead to the same model output of the bag-level classifier, i.c.
m 2 Σ 9rd IT
(f(az))) (1- fo (2x,)) (x,)) (1
AI e 21. m+ 13. (k.
IT m
(1 (1- (1-Sih 16 (x,,)) (1-0)-11)
We also introduce binomial for f {1, (1,...,mi; m]:
(2) f((x,) (1- fl (z,))
We also define an m-order polynomial as the product of all m binomials:
Gk((2) II Fk (z) IT [x))) 2 (1 f(,())))))
En 2,22"
We have C,,t = d/e by Lemma 2. Therefore, the roots of Gz(z)) are the same as G2 (2), i.e.,
1/fa(a;)) [1-1/f((2,))};--
Then, we can obtain
(f((z))]ī= {f(()))}
which contradicts the condition that (2,)) is a different set. Therefore, the set of model outputs of the instance-level classifier (mx))) is also determined uniquely, which concludes the proof.
B.4 PROOF THEOREM 2
Before giving the proof, we introduce the following lemma.
Lemma 3. Suppose that a proper loss function, e.g., the cross-entropy loss or the MSE loss is used, then have 9h pl a = (B).
Proof. Cross-entropy loss. Since the cross-entropy loss is always non-negative, minimizing Rg(gk) can be achieved by minimizing the conditional risk Eptāy/B) [ (B), for every B (Masnadi-Shirazi & Vasconcelos, 2008). The conditional risk can be expressed as
Σx m++ p(ān = IBB) log (B)), s.t. Σ I = 1.
We consider solving 9 (B) by using the Lagrange multiplier method (Bertsekas, 1997), which indicates minimizing
m+1
m- (B)-1)
1- p(āu= ([B) log (Bn,
The partial derivative of 6 w.r.t. It. (B. is
dΦ
plan = =[(B)
(k.
By setting the partial derivative to zero, we have
p(u =(BB)
g (B)
A
Besides, since
>T1 ( -
m
m++ p(āz IB)
1
1,
we have 1. Therefore, we have (
(B) p( IB).
MSE loss. In similar way, minimize the conditional risk for every B:
R=1 (Bk,((B) -p(āa ) s.t. Σ m++
1= 9k.1 (B)
(B) 1.
16

---

Published as a conference paper at ICLR 2026
By using the Lagrange multiplier method, we aim minimizing
m+1
(gr.(B) p(ān - j
111 gk. -1).
m++
The partial derivative of 6 w.r.t. (B):(B)ii is
O
(B.,
2p(āx 1(B) X.
0g.. (B)
By setting the partial derivative to zero, we have
( (B) 2p(xx 1|B) X
2
Besides, since
E -- (B) 2 2 p(as= -|B) (m + 1)
2 (m + 1)A
1
2
we have À = 0. Therefore, we have (B) = p(ā = BBB). The proof is completed.
The we give the proof of Theorem 2.
Proof of Theorem 2. To begin with, we have
p(ā = I(B) do 1, (0 1|zx,) 10 (
P0J = 0122,) (1-05-1)) (
Ird TT f (my) (5-)))--1)) (1
(Ir,)) (1-0
(B)
By Lemma 3 and Theorem 1, we have (5 (a;)) )= (0) 1 1,0)) j=1 When the labels are deterministic, we have p(ū = 1|r,)) E {0, 1). Therefore, we have f (xx)) {0, 1}, which concludes the proof.
B.5 PROOF OF THEOREM 3
First, we introduce an upper bound for loss C. Assume that there exist constants a and b such that
the model outputs of the binary classifier satisfy that Yk E (1,2..... J.. (1, m.. 0 < a & fmzz) & <
Lemma Assume that there exist constants and such that the model outputs of the binary classifier satisfy
Vk e (1,2,.....)) .9h j m). 0 0<a <b<1.
When either the cross-entropy (CE) loss or the mean-squared-error (MSE) loss is used, we have
((g( 0(m).
(24)
Proof. We prove the statement separately for the cases.
17

---

Published as a conference paper at ICLR 2026
Cross-entropy loss.
LCn (gu (B), (ik)
log (gk: an (B))
Σ
2m Unau I1
L (2x,))) 10 (1 La (2x (-:)))(-03-1)
log
1=
2m
<
log
1=
r=1 Grsör log (MT- le (2,,)) (1 (1- fa (2x;) (1) (1-08-11)
2
mr Gr
r= grids D t
2m
(og- (fg (x,)) (1- (1- -1 log (1 fa (ax)))
1- Vr,ā
211=1 (0) (0)-11) log (a) (1- b log -))
m
2
r=1 Grsur
1r=1 fr.āe
2 Σmm1 Gr.a, m log(min(a, 1- b))
Dr=1 fr,āc
m (og(min(a,) b)) = O(m).
Here, the first inequality follows from Jensen's 's inequality.
MSE Loss.
m++
m+1
LMSE (gn (B), Σ
(āku (B)) Σ [ān.s(1 (B)9) (1 āk.i)gk.. (B)
j=1
m+1
1a-c((11))))) = (m + 1) max ((1-a)))))) - a)) = 0(m)
Combining both cases above, we conclude that the proof is completed.
Lemma 5. Assume that there exist constants and b such that the model outputs of the binary classifier satisfy
Vk (1,2..... 9), j (1.2.....
m.), 0 a a fa( < b < 1.
For any two bag-level predictions (B), (B), (B) and the same one-hot target âg the bound for the cross-entropy (CE) loss
(B),)((B),an) ax) - CeE(gi āx) & a (gx(B) (B)ll
thus, the Lipschitz constant for is
The bound for the mean-squared-error (MSE) loss is [CMse(g((B) āx) LMSE (B), āx) & 2v ( g(((
thus, the Lipsehitz constant for MSE is 2
Proof. We prove the loss functions separately. Cross-entropy loss.
(CE(g)(B), log Ik.& (B)
log Σ Graān II fa(w;) 6--") 11 (1- [x(x))) 1-10-11)
2
j=1
Since each instance-level prediction satisfies fx( > a and the weights graa sum to one, it follows that
9k.ā. (B) Σ 9rin 1 f6(,)) 1r-1) (1 fc(2x)) a
18

---

Published as a conference paper at ICLR 2026
Hence
VgLcE|
& a m
Gk, (B)
and for any two bag-level predictions gt (B) Cce(gx o.) - LcElg' (B)
& m [ (B)
Thus the I Lipschitz constant for the CE loss is am MSE Loss.
m
MMEE (asse99 (B), āzk Σ (o -áx.)² (B) axx12
8=
Its gradient is VgLuSE gg (B)
0z so
V NyLeslll2 2 (B) 0xl2 < 2/2,
because the maximum Fuclidean distance between a probability vector and a one-hot vector in the simplex 22. Therefore.
Lxssa[g (B). âs) - LMSE (B)) <
2v gi (B) - (B)
Hence the Lipschitz constant for the MSE loss is 2 Both desired bounds are now established. n
Definition (Rademacher complexity). Let D. = {BB', denote n i.idd bags with propor- tional value labels drawn from joint probability distribution p āg). Let (01, o .x) denote Rademacher variables taking values from (+1,-1] uniformly. Besides, let denote a class of binary classifiers. We introduce
Σ 2
G B - g(B) g(B) [9i (2), ..... #m++1 (B)),9((B)
--- 4r
(( (1- fx ")) ff f f
Notably, the marginal density of Dr, E (1.2.....g) . is the same. The (expected) Rademacher complexity of under distribution Dj is defined as
R 9) -E,, Eo
Σ" i-1 ofC (g(B),,))))
sup g n
For of notations, introduce D -.D.UU.U.. lemma.
Then, we introduce the following
Lemma 6. The following inequality holds with probability at least 8, where C is a constant:
9 In (2/8)
J2....2...... Ru... fe.,,,
Σe lk- R 9) + Ciny
sup fo
2n
Proof. In the following proofs, consider general case where all the datasets Dj are mutually independent. When a bag (B, āx) from Dj, & 21. ... q) ... according Lemma 4, the value of sup//./a...... R(fi, f2........... .........) R(fi.f2....... fq) changes at most Cm/nn According to the McDiarmid's inequality, for any å 0, the following inequality holds with probability least 1 - 5/2:
is substituted by another bag (B', ag))
sup fe.... .fo) fe....e......))
[R(fi,2, .......... S.) R( f2, fe)..,)))) [2l)
9 In (2/0) +Cm
<BD sup finfamiifee
2n
19

---

Published as a conference paper at ICLR 2026
By symmetrization (Vapnik, 1998), it is routine work to have
f( fu) R(fi, Ea))
$2 k== R. ( 9).
B fe.F
sup
Therefore, the following inequality holds with probability at least 8/2:
In (2/6)
(2, .....-.44 S4)
12 Sa)
>
R (C 9) + Cm
sup
2n
In the same way, we have the following inequality with probability at least 1 -6/2:
In (2/5)
ft)) f2. ..) f..............
..)......))))))))))
D -= Ri(L () + Cmyy
sup fE
2n
Therefore, the following inequality holds with probability at least 6:
f2..,f......f R(f,, f2.... [2) 2 -i- fuJaa..nne
Ri( 9) + Cm
In (2/6)
sup
2n
Definition 3 (Covering number). Let S { Øm) be set of m iid. samples from X and define the empirical Lp metric
V - plp.s: - 1sx)) -(x)))))))))) 1/P
p3l. I.
WES
An E-cover of F (with respect to || (lp.s) finite set C F such that for every f F there exists g e with |f - glp.s & e. The empirical Lp covering number is the minimum size of such a cover, Ng(FFe,S) = min[[C]:
an E-cover of under lp.s).
and the worst-case (over samples) covering number of size m
(p) :- sup S
Nf,(Fee,))
Lemma 7 (Refined Dudley's Inequality, Lemma A.I from Srebro al. (2010)). For any function class X R,
Sup E. 1
N2(F,
(F) & inf inf 4 120
12
ds
Lemma 8 (Theorem 18.4 Anthony Bartlett (2009)). Let be a nonempty set of real func- tions mapping from domain X into the real interval [0. 1] and suppose that F has finite pseudo- dimension Then for all
0,
M((F,,,) & Mi((Fe,m) edd+11 +
2c
Corollary 1. Let be a nonempty set of real functions mapping a domain into the interval [o, 1], and assume that F has finite pseudo-dimension d. Then, for every O and any sample size 1,
2x d
Na(F,e,m) & ( + 1)
Proof. Because function values lie in [0. 1]. for any f.g E F we have the point-wise bound [f(x) |2z)]2 [f(x) g(z)]- Averaging this inequality over an arbitrary set S of m i.d. instances and then taking square roots yields:
|| - - || gli.s
I 9l22.5 & VIS gl1.s.
(25)
20

---

Published as a conference paper at ICLR 2026
If C is a d-cover of F in L1, meaning that for every f F and every S x there exists a g C such that |l - olli,s & 8, then by (25) the same center g satisfies |l glla.s & vó.Hence, any ô-cover in Lı induces a vō-cover in L2:
(2 Vo, (F
(26)
Choose ò = c² in (26) and invoke Lemma 8, we have
()) & (F(F,eem c 1) ())
which is exactly the claimed inequality.
Lemma 9. Let F [0, 1]x be class of real-valued functions with pseudo-dimension d and let C be any loss function whose range is contained within [0, T and with Lipschitz constant X with respect g. Denote by Lo G the composition of L and the class G defined in Definition 2. Then, for any sample of n bugs under the distribution Dr.
( () =) = = d(m + log A)
where (-)) hides universal constants and all polynomial dependencies on log and log n.
Proof. For any pair of functions f and f", and their corresponding bag-level mappings g and g", we first note that for every bag B and each according to the definition of g, we have:
(B') of (B*)
f(x1.))
- f(ar))))
E
(((1-(((a)))) ((as)))
sc m
jES
JES
8c(m]
JES
JES
|!|
Σ
f(x)))) - f3(2,)))
mc
[(a.,s) (x)
m
m2m
[x...)) ((
22m m
Σ - -
22th m
(f(w:s)- (((s))
m
The first inequality applies the triangle inequality. The second inequality uses the bound on indi- vidual differences due to each term being at most 1, leveraging the boundedness on f( and f' (*(z))). The fourth incquality employs the combinatorial bound (m) & 2n Finally, the fifth inequality applies the Cauchy-Sehwarz Schwarz inequality to convert from the & norm to the norm
Consequently, taking the & norm over the entire (m+11 1) dideensoii output vector and then apply- ing the standard relation ||u||2 & vm +
woooo we obtain
(B' (B & +m+1lm (B') ( & 2
Σ 1=1
(f(m..)) - l (x(o))))
21

---

Published as a conference paper at ICLR 2026
in the last inequality deliberately absorbed the polynomial factor into the exponential term. Hence, for the empirical &g metricss over the sample we have the compact bound
1/2
1 Σ (g((B)) (lg
lg(B') (B 1/2
Σ Σ - ) 1/2
X 2m
-
nm
Then, we can directly derive the following relationship between covering numbers:
log.N2 (c n, & log Nog.N2(9, é =n) & log.V2 (F xImm nm
Applying Corollary to the hanh covering number:
l2 n,E,n) < log(e(d 1)) d log 2e 2=222m 2m
Because the outputs of C lie in [0, 77, we can apply Lemma 7, which yields:
log(e(d + 1)) + 2d log 2ex 2
( o000) 9)
inf 4n 12 m 7=0
de
n
Choosing - V(TV/2d//)) gives
2d + 12T
6dm + dlog À + dlogg
( g) & 47
n
We absorb the log n and log À factors into the Ô notation and, using m 1, obtain
* 9) = - d(m + log A)
which concludes the proof.
Corollary 2. Suppose we use either the cross-entropy (CE) loss or the mean-squared-ervo (MSE)
loss. Then, under the assumptions stated in Lemma 9, we have for any sample of n bags under the distribution Dr,,
(
dm3
B (C 9) Ō
where Ö(-) hides universal constants and polynomial dependencies on log m and log n.
Proof. The corollary can be obtained by combining Lemmas and 5.
Finally, we provide the proof of Theorem 3.
Proof of Theorem 3.
R(f1, .
fq) R(st, ...
f2. Ru S2 f2.... fa) Rucs, f..f............. iis SdfttJ2..... .2....: S7)
+ +R ,..., ST) N( 15, ......,
ER(h..f.. fe.............. - f2...., + Rift,f5
Pe(s ((.,,f......)) f2....,fal fa)
$2 sup f..
(27)
The first inequality is deduced because (fi. f f.) is the minimizer of R .2,..., combining Inequality (27) with Lemma 6 and Corollary 2, the proof is completed.
fq). By
n
22

---

Published as a conference paper at ICLR 2026
B.6 PROOF OF PROPOSITION
We denote Tarihh as the arithmetic-operation complexity and 7 as the wall-clock-time complexity.
ii) Initial forward transforms (GPU batch). All zero-padded binomials undergo one batched discrete Fourier transform call. Since each discrete Fourier transform requires Om log m) time (Cooley & Tukey, 1965), we have:
T = (m + 1) (( + 1) log(m + 1)) = Om log m),
Tiit = O log m))
because a single batched call executes all vectors in parallel on GPU, leveraging the high-throughput parallelism provided by modern GPU-accelerated FFT libraries.
(ii) Layer-i merges in the frequency domain. After i recursions the list length is N = [[m + 1)/2']. For each even N; we set
H = H k.2g
H k,2
t ....,,m,
which costs m + (m) arithmetic operations per pair. Launching the [2,/2] pairs of layer as single GPU kernel yields the wall-clock cost
T. O(m).
Therefore
[oga(m 1)]- T,rall O(m logm).
Twaall merge
whereas the arithmetic count
Trrith
log,
N. ((m) O(m²).
0-0
(iii) Final inverse transform (GPU). A single length-(m + 1) inverse discrete Fourier transform (IDFT) yields (cR.0..... Ch,m and hence ge.l Ck.l-1- Since the inverse transform has the same complexity as the forward transform (Cooley Tukey, 1965), we have:
T
Twail
(m log m).
(iv) Overall wall-clock time.
Towall
T.wall
T-wall
+ final O(m log m) + Omm log m) + logm) Om Amllg m).
With fixed (ength-(m 1) padding and batched GPU kernels that keep all merges the frequency domain, the procedure runs in O(m logmm) wall-clock time, and returns the desired coefficients Ck. and probabilities 9k.1 Ck,--1-
C MORE ALGORITHMIC DETAILS
The algorithmic details of LLP-PVC, the FFT-based computation of model outputs, the cluster bag generation process, and the proportion first bag generation process shown in Algorithms through 4. The pipeline of LLP-PVC and a toy example of FFF-based calculation of posterior prob- abilities for proportion values is shown in Figures 3 and 4, respectively.
23

---

Published as a conference paper at ICLR 2026
Algorithm 2 FFT-based computation of gb. (B) (Algorithm 2)
Require: Bag B (#)..... [ W: per-class instance posteriors ([(())))z=1: N
Ensure: 9t: [B) [9x,1 (B)..... N (B)] with gx,, (B) Ck,--1-
1: for J = 1 to m do
Initialize [ [1 fe(2;), fa(m)), O, O......) 00 R (according to Eq. (15))
3:
(0) DF)(()))
(0) using Eq. (18)
4: end for
5:
N1
while > 1 do
7:
for j 1 to |N./2 do
8:
H H k,2-1 2 H2.
using Eq. (19)
end for
10:
if N. is odd then
11:
H. No+1
H 1-1 N,N,
as in Eq. (19)
12:
end if
13: 8 s s ++1 N. - |
14: end while
15: H H (1og((m+1)) according to Eq. (16)
16: CA - IDFFTTH using Eq. (20)
17: for = 1 to N do
18: 9k.1 (B) Chii-1 by Lemma
19: end for
20: return gk (B)
DFT
ho
O
H k,
DFT
h k22
h k.2
H
DFT
h
Hro k.3
Inverse
H1 k.2
DFT
H
h
DFT
h k,4
H k,4
DFT
0 k,5
H k.5
H k.3
H2 k.2
Figure 4: A toy example of FFF-bbased calculation of posterior probabilities for proportion values.
24

---

Published as a conference paper at ICLR 2026
Algorithm 3 Cluster bag generation
Require: Labeled datasct ((x,, vo) with y (1,...,g)} bag size m; number of clusters K; Dirich-
let parameter E R++
Ensure: LLP dataset D = ((B,, a,))__ where /m/.
1: [N/m]: ; N' nm; keep the first N' samples.
2: Partition (a:, ) into K clusters; let clu(r) (i & N" cluster(i) = r) for 1,..., K.
Initialize - Ø
4: iori=1 to n do
5: Draw cluster proportions
DTrichlet(Tr).
PPEAK-
6: end for
for to z do
Obtain an index list 1' by drawing m indices from U clu[r] without replacement, such that the
cluster compesition of 7 fallows p. and the global usage exhausts each clu[r]. I' is the list of selected sample indices for bag
9:
Form the bag B, = [=a..... Dim from indices l" Compute label proportions
10:
[aa..... ckig] where 2j=1 I(yas k) for k 1, 1.....9
11:
Add (B., ax)) to D.
12:
end for
13: return
Algorithm a-First bag generation
Require: Labeled dataset ((x;, y)]] ] with yi E y (I..... g): bag size Dirichlet parameter v IR
Ensure: LLP dataset D {(B,, o.)].. where [N /m].
I: n [N/m]: N' nm; keep the N' samples.
2: Build class pools pool[k] - (i & N = k) for I,....g.
3: Initialize - Ø
4:
to de
5: Draw target proportions a, Dirichlet(T)..
end
7: for to r do
8: Obtain an index list I' by drawing indices from Ui-1 pool[k] without replacement, such that the
class composition of /' follows a; and the global usage exhausts each pool. is the list of selected sample indices for bag
9:
Form B. [..1,..., Fimm from indices T'.
10: Add (B,, to D.
end
12:
return
D MORE EXPERIMENTAL DETAILS AND RESULTS
D.1 MORE EXPERIMENTAL. DETAILS
The hyperparameters used for K-MNIST, F-MNIST, SVHN, and CIFAR-I0 are described in Table 6. Furthermore, for numerical stability, clip the probabilities in Eq. (14) by enforcing minimum value during optimization, where e E {10-1 12 10
10-30 30
10 10-50
50 10 10020000000 10-200)
25

---

Published as a conference paper at ICLR 2026
Table 6: Hyperparameters for datasets (K-MNIST, F-MNIST, SVHN, CIFAR-10). SVHN and CIFAR-10 backbones ResNet-18 18 are pretrained on ImageNet.
Dataset
K-MNIST
F-NNIST
SVHN
CIFAR-10
Model
LeNet-5
ResNet-18
Epoch
1024
500
Learning Rate
2.5 x 10-3
5 x 10
Weight Decay
5 10-5
1 x 10
Optimizer
SGD (momentum 0.9)
Data Augmentation
Random crop horizontal flip
Batch Size
1024
Scheduler
7/0 COS
Tak
T6k
D.2 ADDITIONAL EXPERIMENTS WITH LARGE BAG SIZES
We also evaluate method under large bag sizes, and experimental results shown in Table 7. While prior LLP studies typically consider even larger bags, mainly in binary settings (e.g., up to m=2048), extending to multi-class classification substantially more challenging. In our exper- iments, meaningful performance is achieved at m = 256, whereas for larger m, most baselines quickly collapse toward trivial solutions, rendering further increases in bag size less informative.
Table Accuracy results (mean + std over seeds) under Random Bag construction with large bag sizes.
CIFAR-10
Method
256
512
1024
256
512
1024
PM
35.17
4.30
21.20
4.46
9.82
2.52
28.14
1.40
20.65
1.62
15.64
1.52
DSQ
42.35
2.45
32.83
+ 2.96
10.39 = 3.12
35.16 + 0.63
25.97 + 0.08
13.63 + 2.11
ELsyLLP
0.93
21.82
19.59
LLsyL.PPffoo
39.07
1.62
28.22
0.91
10.76
0.93
36.02
2.07
25.20
1.05
19.59
0.00
ROT
37.17
1.56
22.60
2.98
8.39
+: 0.11
32.79 + 0.52
21.40 + 1.99
15.04
1.16
LLP-PVC
69.21
1.65
28.46
5.82
12.92
1.98
90.74
2.32
21.03 1 1.23
19.62
0.04
26


Reviews:
[{"review_id": "YHygrzghru", "reviewer": "Reviewer_cMjG", "summary": "This paper proposed a novel LLP approach that can mitigate the longstanding over-smoothing problem with only the incorporation of an aggregation function after the classification layer. An efficient computational approach with a divide-and-conquer strategy was also proposed.", "questions": "1.\tWhat is the reason of the results with larger bag sizes are higher than that of smaller bag sizes for the proposed method, for example, results on K-MNIST in Table 2.\n2.\tIs there any hyperparamters sensitivity and ablation study should be investigated?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1.\tThe proposed method is simple to implement, only involves with an auxiliary proportional value classification task.\n2.\tA divide-and-conquer method is adopted to reduce the computational complexity by using the fast Fourier transform, which largely reduces the computational cost.\n3.\tThe theoretical work guarantees that the model outputs can mitigate over-smoothing problems under certain assumptions. It also analyses the convergence rate of the proposed risk estimator by providing an estimation error bound.", "weaknesses": "1.\tThe datasets and bag sizes for the image classification in the empirical study seems to be small. The authors should consider larger datasets with larger bag sizes, for example, CIFAR-100 and bag sizes of 32, 64, and 128.\n2.\tThe actual running time reported in Table 3 is not consistent to the time complexity results.\n3.\tThe reported results seem to be inferior to that is reported in former work. For example, CIFAR-10 in Table 2.\n4.\tMost of the compared methods are not state-of-the-arts.\n5.\tConclusion is too weak and there is no limitation indicated.", "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": "jtkQKp9SZ3", "reviewer": "Reviewer_QG4B", "summary": "This paper proposes a novel approach for Learning from Label Proportions (LLP) that may mitigate the over-smoothing problem common in proportion matching strategies with theoretical guarantees. The core contribution is to treat label proportions as labels for an auxiliary proportional value classification (PVC) task, which is then used to induce the instance-level classifier. The authors also introduce a \"divide-and-conquer\" computational method using FFT to solve the problem with an efficient time complexity. Experiments on text and image datasets show that the method achieves better performance against other LLP methods in settings with random bags with fixed size.", "questions": "1. Could you clarify the intended scope of LLP-PVC? The motivation (Section 1) suggests broad use, but the experiments (Section 4.1) use only random fixed-size bags. Do you expect this performance to generalize to non-random settings (e.g., clustered bags [3])?  \n2. Why were experiments limited to small bag sizes (max 128)? Was there another bottleneck? Can you provide insight into the expected performance as bag size grows significantly?  From the literature, we expect the performance to decrease with the bag size increase.\n3. Could you provide a brief conceptual comparison to recent baselines [4, 5, 6, 7], especially [5] (ICLR 2024)? What are the key methodological differences and trade-offs versus [5]?\n4. Can you justify using a single fixed LR for all methods? This choice may unfairly disadvantage baselines. Is there evidence this choice doesn't create a confound, or that this LR is a reasonable default for all?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- **Novelty**: The core idea to solve a different, auxiliary problem, PVC, is creative and new for this field.\n- **Efficiency**: The paper introduces a clever and practical solution using the FFT to make the computationally complex aggregation step efficient.\n- **Theoretical quality**: The paper provides strong theoretical backing for the PVC approach. It includes formal guarantees showing how the method mitigates over-smoothing and connects the bag-level task back to the instance-level classifiers.\n- **Clarity**: The paper is well-written and clear", "weaknesses": "1. **Mismatch between motivation and experimental setup**: The authors motivate the LLP problem with real-world applications like election polling (Section 1), which often involve complex, non-random bag generation (see [1] for a real-world application of LLP in election). However, the experimental setup (Section 4.1) relies exclusively on bags generated randomly with a fixed size. This setup only addresses one variant of LLP (termed \"Naive\" in the taxonomy proposed by [2]) and is unlikely to represent the more complex scenarios used as motivation. Even though using real-world data such as [1] is unfeasible, other works have explored more realistic bag creation methods, such as or clustering [3] to create dependence structures that are more realistic. The paper's claims would be significantly strengthened by testing against these more challenging and representative settings.\n\n2. **Limited bag size exploration**: Even within the chosen random setting, it is known that LLP performance often degrades as bag size increases. The bag sizes tested in the paper are relatively small (a maximum of 128 for text and 32 for images, per Section 4.1). The claims about the method's robustness would be better supported by an analysis of its performance with much larger bag sizes, as seen in other recent work (e.g., up to 2048 in [5]).\n\n3. **Missing baseline comparisons**: The evaluation is missing comparisons against several important and recent baselines, such as [4], [5], [6], and [7]. These methods are highly relevant to the task, and their omission makes it difficult to assess the proposed method's performance in the context of the current state-of-the-art. Notably, [5] is a recent ICLR 2024 publication, making its absence in the comparison tables particularly significant.\n\n4. **Potentially unfair hyperparameter selection**: The paper states that \"all methods shared the same hyperparameter settings\" (Section 4.1) to ensure fairness. While using the same network architecture is reasonable, fixing hyperparameters like the learning rate (LR) for all methods (detailed in Tables 5 and 6) can unfairly disadvantage baselines, as different optimization methods often have different optimal LRs. A more robust comparison would involve minimal tuning (e.g., testing a small set of LR values) for each baseline and reporting its best performance. This would provide a stronger guarantee that the proposed method's superiority is not an artifact of a single, fixed hyperparameter choice that favors it over others.\n\n**Minor details**: \n- $m$ is used in line 98 before its definition (line 142).\n- Figure 1 labels are a bit confusing. I would suggest to have entropy and accuracy as two different colors, and have different methods with different markers.\n\n\n[1]: Assessing Candidate Preference through Web Browsing History: https://dl.acm.org/doi/pdf/10.1145/3219819.3219884  \n[2]: Dependence and Model Selection in LLP: The Problem of Variants: https://dl.acm.org/doi/pdf/10.1145/3580305.3599307  \n[3]: (Almost) no label no cry: https://proceedings.neurips.cc/paper_files/paper/2014/file/d3313de3f431fd64513431c4326d237c-Paper.pdf  \n[4]: Learning from Label Proportions with Consistency Regularization: https://proceedings.mlr.press/v129/tsai20a/tsai20a.pdf  \n[5]: Learning from Label Proportions: Bootstrapping Supervised Learners via Belief Propagation: https://openreview.net/pdf?id=KQe9tHd0k8  \n[6]: MixBag: Bag-Level Data Augmentation for Learning from Label Proportions: https://openaccess.thecvf.com/content/ICCV2023/papers/Asanomi_MixBag_Bag-Level_Data_Augmentation_for_Learning_from_Label_Proportions_ICCV_2023_paper.pdf  \n[7]: Learning from label proportions by learning with label noise: https://proceedings.neurips.cc/paper_files/paper/2022/file/ac56fb3fab015124b541f6299016a21c-Paper-Conference.pdf", "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": "LeAFlX0KKB", "reviewer": "Reviewer_B5vC", "summary": "The paper introduces a method to solve the learning from the label proportions (LLP) problem, where we'd like to obtain an instance-level classifier given aggregated bag-level data. The proposed method claims to mitigate the oversmoothing problem in the proportion matching strategy. This work introduces a new algorithm for LLP accompanied by theoretical analysis and empirical validations.", "questions": "1. How important is it for different bags to have the same size m? I don't think Theorems 2 and 3 depend on a fixed m across all bags (Theorem 3 will probably have a different form due to different bag sizes). Can the authors confirm my observations?\n\n2. While Theorem 2 is acceptable, I'm wondering if an excess risk bound like the styles in [1] can be developed. An excess risk bound could illustrate the sensitivity between $f_k$ and $g_k$ in Theorem 2. To be precise, if we obtained a $g_k$ that is not equal but very close to $g_k^\\*$, would $f_k$ also stay close to $f_k^\\*$?\n\n3. How would the accuracy look if you fix the number of bags and keep increasing the bag sizes? If (17) is tight, you should not get better convergence.\n\n4. See other questions in weaknesses.\n\nI'm open to increasing the score if some of the concerns and questions can be addressed.\n\n\n## References:\n\n[1] Steinwart, I. How to Compare Different Loss Functions and Their Risks. Constr Approx 26, 225–287 (2007). https://doi.org/10.1007/s00365-006-0662-3", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The method reduces LLP to a bag-level classification problem, while prior work on proportion matching typically maps it to a bag-level classification problem.\n\n2. Theorem 2 points out that the optimal solution of the proposed bag-level objective leads to an optimal instance-level classifier. Theorem 3 shows that the optimizer of the empirical objective converges to the optimizer of the objective as the number of bags grows. Theorem 2 and 3 essentially prove that the proposed algorithm indeed solves the LLP problem under the posed assumptions.\n\n3. The theoretical framework is mapped to an implementable algorithm by an efficient computational strategy to identify some coefficients. Empirical evidence suggests that the proposed method outperforms several baselines on the benchmark datasets.", "weaknesses": "1. This work assumes all bags are i.i.d.. I don't think this is a realistic approximation of real-world problems. For example, in the election polling application in the introduction, I think the label proportions of two voting districts in the same city can be highly correlated. \n\n2. It is not clear to me how over-smoothing is mitigated by Theorem 1. Is there a 1-1 relationship between group-level and instance-level outputs, held for other proportion matching methods?\n\n3. The bound (17) seems counterintuitive to me due to the presence of m in the numerator. If you have a fixed number of bags but with an increasing number of instances in each bag, the bound does not get tighter. This is basically saying you're not getting better convergence with more data allocated into a fixed number of bags. Does this reveal certain caveats of the proposed method? \n\n4. Only synthetic datasets are used in the experiments. While many LLP papers used to run experiments on synthetic datasets due to the lack of benchmarks, I think the situation is different with the new LLP benchmarks published in [1].\n\n5. The bag size used in experiments is too small to demonstrate the scalability of the proposed algorithm. The largest bag size in [1] is 512. Papers like [2] even push the largest bag size to 2048. In the tables of [2], the accuracy of some methods rapidly drops after the bag size goes over a certain threshold; I'm wondering if this could also happen to the proposed algorithm.\n\n6. It looks like all instances in the same bag must be pushed to the GPU simultaneously to compute the loss and backpropagate. This seems to be a huge computational disadvantage, especially if the bag sizes are large.\n\n## References: \n\n[1]Brahmbhatt, A., Pokala, M., Saket, R., & Raghuveer, A. (2024). LLP-Bench: A large scale tabular benchmark for learning from label proportions. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management (CIKM '24) (pp. 4374–4381). Association for Computing Machinery. https://doi.org/10.1145/3627673.3680032\n\n[2] Zhang, J., Wang, Y., & Scott, C. (2022). Learning from label proportions by learning with label noise. In A. H. Oh, A. Agarwal, D. Belgrave, & K. Cho (Eds.), Advances in Neural Information Processing Systems. https://openreview.net/forum?id=cqyBfRwOTm1", "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": "aFEidu2h0Q", "reviewer": "Reviewer_n3aR", "summary": "This paper proposes a novel approach for LLP, a weakly supervised learning paradigm where the training data consists of bags of instances annotated only with the overall proportion of each label within the bag, and the goal is to learn an instance-level classifier. The authors identify a limitation in prevailing proportion matching strategies: over-smoothing problem, where the model outputs for all instances in a bag converge indistinguishably towards the proportion value, resulting in poor instance-level classification performance. To address this, the paper introduces PVC, a method that reframes the LLP problem. Instead of fitting the proportions directly, the label proportions are treated as targets for an auxiliary multi-class classification task. This auxiliary task involves predicting the specific proportional value from the bag of instances.", "questions": "1. Could you please provide a more detailed explanation of the physical insights behind Theorems 1 and 2, clarifying how they theoretically demonstrate that PVC mitigates the over-smoothing problem?\n\n2. Could you please elaborate on the comparative advantages of PVC over direct temperature scaling, and include an experimental analysis of whether their performance difference is significant?\n\n3. Could you please supply additional experimental evidence demonstrating how PVC alleviates over-smoothing, and present results on metrics such as precision and recall?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper establishes a theoretical bridge between the posterior probabilities of the bag-level proportional values and the instance-level labels, enabling the induction of the target instance-level classifier. \nThe computational algorithm based on a divide-and-conquer strategy is efficient, achieving a time complexity of $O(m \\log m)$, which is significantly more efficient than a dynamic programming baseline with $O(m^2)$ complexity.\n- The authors prove that under specific conditions, particularly when labels are deterministic, the outputs of the optimal instance-level classifier will converge to 0 or 1. The authors claim this property reveals that the proposed PVC mitigates the over-smoothing problem. I have checked the overall logical soundness of the proofs but have not delved into a detailed verification of the specific derivations.", "weaknesses": "1. The core claim of this paper is that PVC mitigates the over-smoothing problem. The authors present Theorems 1 and 2 as the theoretical foundation for this claim. While Theorem 1 establishes a one-to-one correspondence between the bag-level and instance-level classifier outputs, and Theorem 2 states that the optimal instance-level classifier outputs will be 0 or 1 under deterministic labels, the logical connection from these theorems to the concrete mitigation of over-smoothing remains inadequately articulated. It is unclear how these theoretical results, in a step-by-step manner, directly lead to the conclusion that PVC prevents the over-smooth. \n\n2. The output layers of neural network classifiers typically employ sigmoid or softmax functions to obtain label probabilities. Directly increasing the temperature coefficient in these functions can also make the model more inclined to output extreme values of 0 or 1. This straightforward strategy appears to offer an alternative approach to addressing the over-smoothing problem. So, compared to the temperature-based method, the merits of PVC is not clear.\n\n3. The experimental validation is insufficient to robustly support the authors' central claim. Although the method demonstrates competitive accuracy, the claim of effectively alleviating over-smoothing is not thoroughly verified. The evidence for alleviation of over-smooth is primarily limited to the four figures presented in the introduction. Besides, relying solely on accuracy as the primary evaluation metric is also insufficient for a classification problem.", "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 (Poster)