Learning from Label Proportions: Bootstrapping Supervised Learners via Belief Propagation
Authors: Shreyas Havaldar
Navodita Sharma
Shubhi Sareen
Karthikeyan Shanmugam
Aravindan Raghuveer
Venue: ICLR 2024 poster (2024)
Keywords: Learning from Label Proportions
Belief Propagation
Pseudo-Labeling
Embedding Learning
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: Pseudo-labeling through BP leveraging unsupervised covariate information for LLP

Abstract: Learning from Label Proportions (LLP) is a learning problem where only aggregate level labels are available for groups of instances, called bags, during training, and the aim is to get the best performance at the instance-level on the test data. This setting arises in domains like advertising and medicine due to privacy considerations. We propose a novel algorithmic framework for this problem that iteratively performs two main steps. For the first step (Pseudo Labeling) in every iteration, we define a Gibbs distribution over binary instance labels that incorporates a) covariate information through the constraint that instances with similar covariates should have similar labels and b) the bag level aggregated label. We then use Belief Propagation (BP) to marginalize the Gibbs distribution to obtain pseudo labels. In the second step (Embedding Refinement), we use the pseudo labels to provide supervision for a learner that yields a better embedding. Further, we iterate on the two steps again by using the second step's embeddings as new covariates for the next iteration. In the final iteration, a classifier is trained using the pseudo labels. Our algorithm displays strong gains  against several SOTA baselines (upto **15%**) for the LLP Binary Classification problem on various dataset types - tabular and Image. We achieve these improvements with minimal computational overhead above standard supervised learning due to Belief Propagation, for large bag sizes, even for a million samples.

Published as a conference paper at ICLR 2024
LEARNING FROM LABEL PROPORTIONS: BOOTSTRAP- PING SUPERVISED LEARNERS VIA BELIEF PROPAGA-
TION
Shreyas Havaldar
Navodita Sharma
Shubhi 2areen2
Karthikeyan Shanmugam! GGoogle India
Aravindan Raghuveer'
'Google Research India
ABSTRACT
Learning from Label Proportions (LLP) is a learning problem where only aggregate level labels are available for groups of instances, called bags, during training, and the aim is to get the best performance at the instance-level on the test data. This setting arises in domains like advertising and medicine due privacy considera- tions. We propose a novel algorithmic framework for this problem that iteratively performs two main steps. For the first step (Pseudo Labeling) in every iteration, we define a Gibbs distribution over binary instance labels that incorporates a) covariate information through the constraint that instances with similar covariates should have similar labels and b) the bag level aggregated label. We then use Belief Propagation (BP) to marginalize the Gibbs distribution to obtain pseudo labels. In the second step (Embedding Refinement), we use the pseudo labels to provide supervision for a learner that yields a better embedding. Further, we iterate on the steps again by using the second step's embeddings next iteration. the final iteration, a classifier is trained using the pseudo labels. Our algorithm displays strong gains against several SOTA baselines (upto 15 (5) for the LLP Binary Classification problem on various dataset types tabular and Image. We achieve these improvements with minimal computational overhead above standard supervised learning due to Belief Propagation, for large bag sizes, even for a million samples.
covariates for the
INTRODUCTION
Learning from Label Proportions (henceforth LLP) has seen renewed interest in recent times due to the rising concerns of privacy and leakage of sensitive information (Ardehaly & Culotta, 2017; Busa-Fekete et al., 2023; Zhang et al., 2022; Kobayashi al., 2022; Yu et al., 2014; Chen al., 2023). In the LLP binary classification setting, all the training instances are aggregated into bags and only the aggregated label count for a bag is available, i.e. proportion of 1's a bag. Features of all instances are available. This can be seen as form of weak supervision compared to providing instance-level labels. The main goal is learn an instance wise predictor that performs very well on the test distribution.
There are two sources of information that can help in predicting the instance wise label on the training set. One is the bag level label proportions that are provided. The other source of information is indirect and comes from the fact that any smooth true classifier would likely assign similar labels to instances with similar covariates feature vectors. Covariate information of instances belonging to the bags are explicitly given. Some of the current methods (Yu et al., 2014; Ardehaly & Culotta, bag, predicted by deep neural network (DNN)
2017) propose fit the average soft scores classifier, to the given bag label proportion. There another class of approaches that seek to train a classifier on instance level loss obtained using some form of pseudo labeling (Liu et al., 2021; Zhang et al., 2022).
Our work builds on the idea of forming pseudo labels per instance. Our key observation is that one could utilize two types of information: bag level constraints and covariate similarity information in
"qqual Contribution. Correspondence (shreyas navodi tasha rma @googge.........o...o e com

---

Published as a conference paper at ICLR 2024
Psseudo-Labeling
2
Embadding Leaming
PsoudoiLabeb Bolcl Pappagtioon
Aggrogati Lubul Hoad
toitag
Σ
Fieed t1 pocudt looels
Edges induodd
Pi Po-ccaloulite grap by cang new umboddd from Blap-2
Figure I: 12 instances placed equally into bags. Step-1: On the k-nn graph induced by the covariate embeddings we perform belief propagation to obtain pseudo-labels that respect edge constraints and bag constraints. Then Step-2 we fit a MLP to the instance pseudo-labels and bag aggregate label. Embedding learned in an intermediate layer is used to further refine the k-nn graph in Step-1. (Figures best viewed in colour)
an explicit way. To realize this, we take inspiration from coding theory for communication systems (MacKay, 2003; Kschischang et al., 2001), where one of the fundamental problems is to decode an unknown message string sent by the encoder using only parity checks over groups of bits from the message. Parity checks provide redundancy that battles against noise/corruptions in the channel. The state of the art codes (MacKay, 2003) are decoded using Belief Propagation (Pearl, 1988) on a factor graph where message bits are variable nodes (whose "label" is to be learnt) and parity checks form factor nodes (that constrain the sum of bits in the parity checks to be odd or even). Sum-product belief propagation is used to learn the marginal soft score the each of the message bits.
Motivated by the above connection, we propose a novel iterative algorithm that has two stages: We use an existing embedding to learn pseudo-labels and then use the learnt pseudo labels refine embeddings and we iterate this procedure with new embeddings. Our central approach is described in Figure 1. We outline our contributions in detail below:
1) We draw parallel between the LLP problem and the parity recovery problem for pseudo labeling. The labels of instances are bits of the message and parity checks are the bag level counts (more general than just parity). We adapt this analogy naturally to form a Gibbs distribution that enforces the bag constraints. To obtain further redundancy, we exploit covariate information, where, for every pair of instances that are in the K-nearest neighborhood of each other, we force their binary labels to be similar, i.e. another "parity constraint" is added to the Gibbs distribution. As can be seen in a cartoon depiction in step 1 of Fig. 1, the nearest neighbors induce similar labels (colors). Then, we do a sum product Belief Propagation (BP) to obtain marginal pseudo labels. To the best of our knowledge, ours is the first work at making this connection between the information theoretic approach of recovering messages from parity and the L.PP problem.
2) Our novelty in the second stage is to utilize thresholded soft pseudo labels to provide full super- vision to learn a new embedding. However, we observe that after marginalization thresholded soft labels may violate bag constraints. Therefore, we use novel Deep Neural Network architecture that has an 1) instance head giving rise to an instance level loss involving the thresholded soft pseudo label and 2) bag level head formed by pooling the penultimate layers's representations of instances within a bag giving rise to a loss between bag proportions and predicted bag level proportion. We call the final loss as Aggregate Embedding loss. This loss is used train the penultimate layer embedding.
3) We iterate the above two steps by using the embedding obtained in the previous step as features. We show that our iterative two stage algorithm, finally produces instance level predictions that outperform a number of LLP baselines including DLLP (Ardehaly & Culotta, 2017) by wide margins. Improvements obtained are upto 15% on standard UCI classification datasets. We outperform the baselines by upto 0.8% on a large, challenging Criteo dataset and upto % on image datasets. Our methods mostly outperform most baselines in the large bag regime (upto 15 % gains for bag size 2 512) ) where supervision is very weak. It is worth noting that on bag size of 2048 there are only maximum of -20 bags on the datasets and yet our method does not display significant degradation in performance. Our ablations show that remarkably 1-NN achieves most of the gains relative to using k-NNs in the pseudo labeling step (Section 1.1.1). ). We find that reducing percentage of KNN constraints (to 50%) registers a significant drop in test metries underscoring the importance of parity checks' from covariate nearness (Section 6.2) We provide many other ablations that validate different components of our approach (Section and Section A.1).
2

---

Published as a conference paper at ICLR 2024
2 RELATED WORK
Learning from Label Proportion (LLP): Quadrianto et al. (2008) use kemnel methods under the assumption of class conditioned independence of bags. Yu et al. (2013) were one of the first to tackle the problem and present theoretically backed xSVM, non-convex integer programming solution. This is computationally infeasible on large sized datasets we use. Patrini et al. (2014) introduced a fast learning algorithm that estimates the mean operator using a manifold regularizer while providing guarantees on the approximation bounds. Scott & Zhang (2020) provide an approach that use Mutual Contamination Models which provides some form of weak supervision. The method does not scale to large number of training instances. Several recent methods have been introduced to learn from bagged data. Poyiadzi al. (2018) propose an algorithm that uses label propagation, i.e. iterative damped averaging of neighbors labels where neighbors are decided based on some similarity measure. Every node is set to the proportion of ones from the bags they participate at the beginning. This is closest in spirit to ours. However, we always impose bag level constraints and covariate information through a joint Gibbs distribution and use BP to marginalize it followed by an embedding refining step. Poyiadzi et al. (2018) provide results Size-3 Bags and Size- 100 Datasets and their algorithm requires extensive compute for inversion of a kernel matrix. Ardchaly & Culotta (2017) use deep neural networks to tackle the LLP problem show very good empirical performance. When bag size is large their method degrades significantly. Tsai & Lin (2020) use covariate information in the form of consistency regularizer that modifies the decision boundary. The work does not perform well at larger bag sizes and is computationally expensive for large datasets. Zhang et al. (2022) use forward correction loss to draw parallels to learning from label noise. The method does not converge well for smaller bags. Busa-Fekete et al. (2023) is a very recent work approaching the problem by providing a surrogate loss. We further elaborate on our baselines in section A.4.
Belief propagation in decoding error correcting codes has a long history. There is related problem of learning from pooled data which has group testing flavor. We review these in the supplement.
3 PROBLEM SETTING AND OVERVIEW OF OUR SOLUTION
Consider a supervised learning dataset D {xx 3) where x, E Fd I4 E [0, The instance wise labels 's are not explicitly revealed to the learning agent. There are a set of "bags" = (S1-. (S } that contains subsets S, S [mm] (thus denoting the indices that correspond to the instances present in that "bag") and for each S,, bag level counts yS,) = Ejes. V In this work,
0. Let the vector of bag level counts be [v(S))... ySS).) = BB).. In this work, we consider the following problem:
will consider the case of disjoint bags, i.c. S.
Given the covariates (= information about bag compositions (B) and bag level counts of labels (B(B)), our aim is to learn classifier f IRd + {0, 1}, I E Fuch test distribution B( (xx)) y)] is minimized. Here, F is the set of classifiers we would like to optimize over. We term this learning from label proportions problem.
such that the loss E(-) on the
Our main contribution to this above problem is an iterative procedure that repeats two steps: a) Pseudo Labeling obtained through Sum-Product Belief Propagation that uses Gibbs distribution capturing covariate information and bag level constraints and b) Learning a better embedding that uses training signals from an instance level predictor on top of the embedding that fits pseudo labels while using the same embedding over multiple instances to simultaneously predict bag level proportions. Then, in the next iteration we use the embedding learnt in the second step instead of original covariates and perform the two steps again. In the last iteration, we simply obtain an instance level predictor to score on the test dataset. Our complete approach is given in Algorithm
4 DETAILS OF OUR ALGORITHM
4.1 STEP 1: OBTAINING PSEUDO-LABER THROUGH BELIEF PROPAGATION (BP)
Now, describe the first step that involves obtaining soft labels from the bag constraints and covariate information. To this end, we form a Gibbs distribution whose energy function captures two-fold information: a) bag level constraints and b) label similarity when two points that are nearby.
3

---

Published as a conference paper at ICLR 2024
Algorithm Iterative Embedding Refinement with BP and Aggregate Embedding
Input: Covariates D { Bag Information B
Bag Label Counts
{S()) Parameters hay λo, L, L' da k(.,)),(::;))
Output: Soft Classifier f.)
Set Covariates {2+ < {xa}
for t 0 to do (Pseudo Labeling ing Step)
Initialize node and Pairwise potentials hs, Ji, for Belief Propagation as in equation using {2+). (M)) D-SUM-PRODUCT-BRPP
(41)).
Obtain Hard Labels: yf ())))
(Train embedding with instance and bag losses)
Train the DNNs gn. (. (-nistannce and bag loss heads) using hard labels {uf and bag level labels using L Emb loss as equation
Set Covariates { + (x:)) (Update Embedding)
end for
Output: Return the function fI()). (Obtain instance label predictor)
Gibbs Distribution from Bag level constraints and covariate information: The bag level con- straints are penalized using a least squares loss between sum of all labels in the bag and the count given by (Ejes, Mj y(S)))² When two points are close in some distance measure, we would like make sure their labels are close. In order capture this, for every point x; we form k-nearest neighbor set (x4, with respect to given distance function d(æ, x²), with Iy added to NN(2,) if d(zy,, x.) < 5g. If zry E (a;)), we use the least squares penalization (yi - y5)². We also use a kernel function ((r,, a()) that scales the least square penalization due nearness. In most of experiments,
we fix d(x, ) to be the cosine distance or euclidean distance. Choices of k(-) are Matern Kernel and RBF kernels.
We define the Gibbs distribution below for the entire dataset DD given by:
P PA (y)) exp
- Σ リー 2SS)) S,EB jES,
Σ
k(a,, y;)²
This is an Ising model with pairwise potentials and node potentials (external field). We note that both the terms are invariant upto a shift in y; by constant. Therefore, transformation to {+1, -1} through 1/4 = 2y, would only scale Ab, Xa by a factor 4. Therefore, the energy function in terms of 1+,, -1) upto universal scaling is identical to that of {0, 1}. Hence, we will remain in {0, 1} and state the pairwise and node potentials.
Observing that y²² yı and the fact that constant terms in the energy function would not affect the distribution (due to normalization), we can rewrite equation as:
PAN,A (31... ... (.))) x exp
Σ
Σ SEBIES
(e - -
Σ
k(
+
ie(m]
xENx(a.)
Σ U:Ul 22,
+ Ln,EN((a))) 24 B: (1.5) E si]
(2)
Remark: 1- denotes size of the set satsifying the condition. We note that not all pairwise terms are present. If two points are not in K-NN neighborhood of each other and if they don't belong together in any bag, then there would be no pairwise term corresponding to it. In our experiments, we consider the case where Bags disjoint and non overlapping. Therefore, every instance participates in only one bag. Use of K-NN and small disjoint bags creates only linear number of terms in the Gibbs distribution.
4

---

Published as a conference paper at ICLR 2024
Pairwise and Node potentials: This is Ising model P(y) exp(E yih + Eits 3g)) with node potentials and pairwise potentials given by:
h4 = Σ X0(2((S) - 1) X
Σ
2(
(3)
SEBNES
(EN((
J.
ENN, I2,EN((E))) 22 B: (G,))
(4)
Obtaining Pseudo Labels using sum-product Belief Propagation (BP): We use the classical sum- product Belief Propagation (MacKay, 2003) on equation 2 to approximate the marginal distribution Px Pr (1i). We briefly describe the algorithm, At every round node i passes the following message
m (Vt), y E {0, } to every node j : J., # 0 given by:
(())( = Σ
exp(ysha) exp(Jr,((15)
II ,
m (Us)
(5)
Here, (.) represents the message passed in the previous iteration. After 7 rounds of message passing, we marginalize by using the following (and further normalizing it):
(y.) x exp(y:h.)
II my-:(1i
(6)
J:Ja,
{hr}) to be the sum product belief prop- agation function that implements T rounds of equation 5 and equation 6. We use PGMax package (Zhou et al., 2022) implemented in JAX (Bradbury et al., 2018) 8) where we just need to specify the potentials Jıj and h4
Implementation: We denote PRW-PRRDDCI-BP((14
4.2 STEP 2: EMBEDDING REFINEMENT LEVERAGING PSEUDO LABELS
We observe that equation uses covariate information by exploiting nearness using nearest neighbors induced by a distance function d(x,, x²) and using kernel k(r,, x'),.))) We now provide an iterative method to refine representation 2; such that points with true labels are brought together progressively although only bag level labels are available. We start with the original features {æt} given to the algorithm (this could already be embedding obtained from another self-supervised module or any other unsupervised training method like auto encoding).
Learn marginal Pseudo Labels: We first identify pseudo labels Ax by applying
COM-PRODUCT-E2 on h, Jig obtained from {x,}'s. ss. We expect the pscudo labels not to be perfect since it operates only bag level information and covariate similarity information.
Learning Embedding using Pseudo Labels: Let us consider a deep neural net (DNN) classifier (with L layers) of the form given below:
(x) (o/
(WT + b1)) bb- + bz)
(7)
where ag represents coordinate wise non-linearity (like Relu function), We E Rdexde-1, [1 L] represents weight matrix at the f-th layer that multiplies the representation from the E 1 layer of dimension de-1 and by represents the biases added coordinate wise to the output which de dimensional. In work, focus on binary classification where dj 1 and do d (input feature dimension). We call f-). the instance loss head.
One option is just fit (zz) to the information from Pseudo labels PA, A (31) the instance level. However, it may not be consistent with the bag level labels in the expected sense. So we impose bag level constraints by first average pooling third to last layer output fı.-((x) across instances E S where S is bag of instances. Then, we have one more hidden layer on top of this pooled representation to finally produce soft score for the bag proportion. We call this the bag loss head and it produces the following soft score for bag of instances S C B:
(S) = or. (V (OL-1 (o (VE-rAvg Pooling((/s-2(x)))) + br..)) + +br))
(8)
We define two loss functions that learns fz. representation to simultancously be consistent with 1) the bag label proportion through the average pooling operation in equation and 2) the other
5

---

Published as a conference paper at ICLR 2024
one that makes it consistent with hard labels obtained by thresholding soft pseudo labels given by v 1 (16)2>7 where 1g is the indicator function when event E holds.
The composite loss function is given by:
CE (Jr(z)) (v(3) + CB gr((),, v(S)
L CARR- Emb (S) - Σ
|S]
iES
Here, CE is the cross entropy loss. We call this composite loss function LARR- Emb the aggregate embedding loss function.
4.3 ITERATIVE REFINEMENT
We take the representation computed at some layer L' < L (denoted by fL.(x) and apply the belief propagation (SUM- (SUU--RRODUSHCCOO PRODUCT-BBI -B) again where covariates are given by {z+ = fr (1,)). We
typically use L' = L - 2. Then, let the new pseudo labels obtained be P A. (Ui) using {2i} as covariates. We obtain hard labels from thresholding pseudo labels by T to obtain y 11 II. (m)sr
We again fit similar DNNs (fI. 9r.) by using LAgg- Emu to the new hard labels {v6) and the bag level labels {y())) In principle, we could iterate it several times to refine embeddings progressively but stop when the new iteration does not clearly improve performance to the section A.2.2 for analysis on convergence of our method in 1-2 iterations. When we test on instances, we always remove the bag level head gr. (-) and test with just the soft score fí We describe the iterative procedure in Algorithm 1.
validation set. Refer
5 EXPERIMENTS
We perform extensive experimentation on four datasets. We follow the standard procedure of creating disjoint random bags where we sample instances without replacement from the training set, and keep repeating this for each bag, bag-size: k number of times.
1. Adult Income (Dua & Graff, 2017) (Kohavi al., 1996): Classification task is predict whether a person makes over $50K a year based on the provided census data of 14 features. The dataset is split 90- 10 train-test and 10% of train is used hold out validation following Yoon et al. (2020)
2. Bank Marketing (Dua & Graff, 2017) (Moro et al., 2011): The task here it to predict if the client will subscribe term deposit from 16 features. Data is split as 3 train-test split. We further use of the training set as a hold-out validation set.
3. Criteo (Krizhevsky, 2009): 1 week of ad click data predict CTR with 39 features. We sample non-overlapping sets of 1 million, 200k and 250k instances to form train, validation and test datasets. Note that Criteo is very challenging benchmark with only +2% AUC improvement shown in the last 7 years (cri, 2023)
4. CIFAR-10 Jean-Baptist Tien, 2014) 60K images with 10 classes. CIFAR-B: We assign label / to all Machine classes 1,,1, and label 0 to all Animal classes (2,6,4,5,6,7). In this dataset, 40% of all instances belong the positive class. CIFAR-S: All instances belonging to the class Ship are assigned label 1 and all other instances are assigned label O. This dataset has 10% positive instances. We use the standard Train-Tes Test splits for these datasets. We use 10% of the data from the Train Set as Validation Set to tune our hyperparameters.
We compare our method against several top LLP Baselines; namely DLLP (Ardehaly & Culotta, 2017), Ea (Busa-Fekete et al., 2023), GenBags (Saket et al., 2022), LLP-FC (Zhang et al., 2022) and LLP-VAT (Tsai Lin, 2020) described in detail appendix section A.4
5.1 EXPERIMENTAL SETUP
We optimize our algorithm, using hyperparameters Xoa As E |10-4, 200), k E [1, 30). T
[50, 100, 200], 5 E 10, E [10- -1:0-6,70 1], MLPWD E [10-12 10 [10-4, 1]. BatchSizerras achieve the best Validation AUC score. Illustrative values of best hyperparameters for various ex- periments given in appendix section A.6. We then report the corresponding Test AUROC %
Aa E [0, 10, 8d E
12, 4, 8 ... 4096, 8192], tuned using Vizier (Song et al., 2022) to

---

Published as a conference paper at ICLR 2024
Table 1: Performance (Test AUROC) on UCI Tabular Datasets on Bag Sizes 8, 32, 128, 512, 1024, 2048 against major baselines. Instance-MLP performance on Adult is 90.30 (0.08) and on Marketing is 86.62 (0.06)
Bag Size:
32
128
512
1024
2048
Dataset:
Adult
DLLP
89.19 m0:3)
87.52 (0:60)
85.87 (0.91)
82.95 (1:3
63.48 (241))
62.58 (2.18)
EasyLLP
88.68 m=a::
87.51
(0:76)
75.59 (0.54)
66.02 (1.7)
61.65 (1.1)
63.21 (3.55)
GenBags
89.22 muz
87.72
(0:34)
86,43
(0.28)
84,00 (126)
83.52 (01)
80,07 (0.0)
Ours-Itr1
89.32 m220)
87.75
(0.32)
86,70 (0.30)
84.97 (0.3)
83.61 (aa9)
84,69 (0.76)
Ours-Itr-2
89.47
87.82
86.87 (0.39)
84.01
83.88 (1.5))
84,95
Dataset:
Marketing
DLL.P
84.49 (0:0
82.65 (0:94)
79.69 (105))
70.36 (164))
66.39 (2.41)
65.60 (X21)
EasyLLP
83.63 m.34)
82.87 (0:72)
75.05
(3.29)
68.97 (2.75)
50.23 (1.11)
50.12 (0.55
GenBags
85.26 m:42)
83.15 (0.34)
79.74 (0.50)
69 (0.92)
64.82 (3.10)
58.43 (4.31)
Ours-Itra Itr-1
85,76 (.20)
84,18
(0.35)
82.71
(9.40)
77.71 00.00
80.56 (1.5)
78,63
(0.3)
Ours-Itr- 86.26 (0.11)
84.23 (0:45)
82,46 (0.35)
81.68 (0.77)
81.66 (MA1)
81.01
(0.2)
averaged over 3 trials and report the sample standard deviation in parenthesis throughout our tables. We perform the same setup for all our baselines. Best number is reported in bold and 2nd best is reported in underline.
We also run the same MLP on true instance labels. This provides an upper bound to the performance that we reach using aggregated labels. We report this number for each dataset at the table heading. We use an MLP with 5 Hidden Layers with relu activation and the following number of hidden units: [5040, 1280, 320, 128, 64] for our 2nd Step. The final layer has sigmoid activation. We use Adam optimizer and Binary Cross Entropy Loss for all our datasets. We use the same MLP for all relevant baselines well. We report main results using k(;,)) = Matern and d(:--) Cosine.
We perform experimentation on bag sizes: 8, 32, 1 128, 512, 1024, 2048. All experiments were performed on single NVIDIA V100 GPU. We provide further implementation details and the experimental details for the baselines in the supplementary section A.5
5.2 PERFORMANCE ANALYSIS
We compare the performance of our method with several baselines on all the datasets. Ours-Itr-n refers to our method run for n iterations.
We use the original features as is for the 2 UCI Datsets with 14 features for Adult Dataset, and 16 features for Marketing Dataset respectively.
Table 1 shows the performance of our method on the two UCI datasets across 6 bag sizes. We make four observations. First, for lower bag size (8.32) our method almost bridges the gap with the instance level performance. Second, the second iteration of our method almost always improves performance over the first iteration across both datasets. Third, we are able consistently outperform all the baselines across all bag sizes in both datasets. Finally, in large bag regime, our methods perform even better. For instance, with bag sizes 1024 and 2048, we are close to 15 % better compared to the nearest baseline DLLP.
In Table 2 we compare our method with other basclines on the Critco dataset.' 1 We use the self- supervised method MET (Majmundar et al., 2022) generate embeddings for Criteo dataset obtain better initial embeddings. This is because most of the features in Criteo are categorical and some of them have large number of categories rendering naive one-hot encoding very intractable. For fairness and consistency we use MET embeddings as input for all the baselines we compare against as well.
Our method scales really well for 1 million samples with negligible computational cost for the sum- product BP step. Criteo is an inherently harder dataset to work with due to high feature dimensionality and most of them being categorical. Over the last 7 years, the dataset has seen 2% improvement in AUC while our method is able to produce a 0.8% improvement over DLLP. Similar to the previous tabular datasets, we also observe here that the iteration seems help improve performance.
We were not able to run BP on Criteo for large bag sizes since we ran into integer- overfflw issues. It will take some time and perhaps even involved changes the underlying PGMax library code to resolve them to accommodate large number of factors
7

---

Published as a conference paper at ICLR 2024
Table 2:
Performance (Test AUROC
scores) on Criteo-IM on Bag Sizes 8, 32,
10%
128 against major baselines. Instance-
52%
MLP performance on Criteo is 75.86 (0.04)
1004
Bag Size:
8
32
128
Dataset:
Crieeo
Figure 2: Comparison of the performance on adding different percentage of neighbours on Marketing on bag- size 8 and 512
DLLP
74.11 oumo
72.80 ous)
70,99 own
EasyLLP
70.77 oum
68.42 ous
62.87 0.m0
GenBags
73.34 mnn
71.32 mm
70.39 no
Ours-Itr-1
74.96 m..
73.36 m0.3)
70.45
Ours-Itr-2
74.97 (..00
73.43 mus))
70.81
Table Performance (Test AUROC scores) on Image Datasets on Bag Sizes 8, 32, 128, 512, 1024, 2048 against major baselines. denotes SVD) did not converge error (while obtaining noisy labels), ! denotes Out of Memory Error. &: Validation performance of first iteration of our algorithm was
clearly superior. Instance-MLP AUROC on CIFAR-B is 96.58 (oan) and on CIFAR-S is 95.06 (0.7))
Bag Size:
32
128
512
1024
2048
Dataset:
CIFAR-B
DLLP
95.49 (.18)
94.05 (0,0))
90,90 (U.0)
86.18 (4U7)
76.65 (2.2))
68.19 (1:75)
GenBags
95.32 mus)
93.40 (0.17)
88.97 (0.33)
84.30 (0.00)
82.73 (1.0)
75.22 (075)
EasyLLP
91.33 m.4)
84.67 (.35)
81.37 (2:28)
58.07 (3.91)
65.34 (5.50)
55.37 (062)
LLP-FC
90.19 0.32)
88.53 (0.31)
82.46 (0.49)
80.12 (1.34)
78.89 (0.51)
73.25 (2.66
LLP-VAT
93.79 0.29)
91.38 (0.15)
88.22 (0.
Ours-Itra I
95.39 m2z))
93.89 (0.18)
89.28
(0.35)
85,55 (0.55)
80.43 0.5D &
70.06
Ours-Itr Itr
95.54 (022))
93.97 (0.21)
90.37
(0.27)
85.92 (0.45)
&
Dataset:
CIFAR-S
DLLP
93.87 1..11
92.12 (0.24)
88.63 (0.51)
79.58 (1.34)
52.01 (5.50)
57.21 (0.50)
GenBags
92.36 (150)
90.10 (0.99)
86.78 (131)
82.69 (10
68.45 (1.99)
60).43 (4 (4:09)
EasyLLP
85.54 (1006))
74.79 (2.17)
65.26 (551)
61.57 (9.00
62.46 (520
52.32 (300)
LLP-FC
85.58 (0.31)
80,59 (1.5))
75.62 (1.2
65.75 (2.00)
63.76 (1200)
LLP-VAT
90.10 10 (0.90)
83.20 (0.16)
64.76 (3.66)
Ours-Itr-1
93.53 (0.90
91.29 (0.96)
88.17 (0.5%)
83.49 (1.5))
74.45 (2.58)
71.01 (2:11)
Ours-Itr-2
93.64 (031)
91.31 (0.39)
88.31 (0:4))
84.30 (1.28)
&
71.17 (2.13)
In Table 3 we report performance on the CIFAR image dataset. We use the SimCLR (Chen et al., 2020) contrastive learning method obtain unsupervised embeddings for our experiments on the Image Datasets. We use SimCLR embeddings as input for the relevant baselines we compare. Among the 2 image datasets, CIFAR-S has large label skew. Our methods outperforms all baseline for CIFAR-S in the large bag size regime (BagSize 2 512), where the performance of all other methods drop significantly. Specifically, we outperform DLLP by upto 20 % and GenBags by upto 7 7%. For small bags, our method performs comparable to the best baseline. Only for CIFAR-B that has label balance, GenBags is better than our method for larger bag sizes while DLLP outperforms slightly for lower bag sizes. However, even in this case, method is competitive (close second mostly) with the best across bag sizes.
We justify our chosen hyper-parameters in our experiments via approximate convergence analysis in the supplementary section C providing theoretical backing for our strong empirical results.
Note:
6 ABLATIONS
Here we provide ablations regarding the two most important ideas in our algorithm: 1) Nearest neighbor based nearness constraints and 2) Aggregate Embedding, Due to space constraints, we do provide a number of other ablations in the appendix regarding adding noise to embeddings (A. (A.1.2), hard soft thresholding of BP labels (A.1.3), performance change with different choice of kernels (A.1.5) and distance functions 1.4) among others. In the supplement, we further report various performance metrics of our algorithm such as performance of BP pseudo labels in itself compared to ground truth (Section A.2.3) and convergence in very few iterations (typically 1-2) (Section A.2.2).
6.1 TIME COMPLEXITY
For the problem we consider in the paper, we have two terms in the BP formulation: KNN based nearness constraints and bag constraints. There are m/ B bags each having B² pairwise terms giving
8

---

Published as a conference paper at ICLR 2024
Table 4: Time for various parts of our algorithm compared to time taken by other methods on Criteo
Dataset. All time values are in seconds. Note that Data Setup time common All Methods
Critcs ~m Samples
Bag Sive
Training
LasTLLP Training
GenHags Training
Data Sctup
Ours BP
Ours MLP
Ours Total
125.22 (112.59)
[617.7 (1397,19)
176033 (1077005)
1993.47 (96.03)
695 31 1266.71 71
679.2 (213 35)
3568.07 (166.31)
735.09 (207.50)
911.86 (553.21)
957.65 (497.01)
1970.05 (104.65)
1279 83 (278.75)
624.55 (187.30)
3874.43 (469.92)
568.00 (79.14)
777.2 (530.75)
729.41 (502.12)
2192.4 90)
3590.73 (528.85)
588.00 (157.84)
6371.57 (727.31)
rise mB pairwise terms (here is the dataset size and B is the bag size). Similar analysis gives mk pairwise terms for the KNN constraints. So we have an Ising Model with (m + k)) pairwise terms. Drawn an undirected graph, the degree is linear in only B k BP message passing complexity per node per iteration is also O B + k). Any implementation will only have this much complexity per node per iteration of BP. JAX (Bradbury et al., 2018) implementation in PGMax (Zhou et al., 2022) does an efficient update for all nodes. This is line with increase in complexity of the BP step (Column 3) for Criteo in Table 4. Additional wall clock time results and discussion (that shows linear scaling in bag size for Adult dataset) is in the supplement section A.2.1, Table 5. This establishes the feasibility of our method on larger datasets and larger bag sizes as well.
6.2 IMPORTANCE OF NEAREST NEIGHBOR CONSTRAINTS FOR BP
One of the main contributions in our algorithm is the usage of nearness of covariates to impose label similarity constraints in the Gibbs distribution is an unsupervised manner. We show how essential it by removing a certain percentage of those constraints and studying degradation.
A good fraction of KNN constraints is necessary: As depicted in figure 2, we show how for good fraction of instances neighbourhood information essential for good performance of the pseudo labeling step using the Marketing dataset. By simply retaining only 10% of the pairwise covariate similarity constraints, we lose around 18% performance compared to when we use the entire set of pairwise covariate factors. This highlights the importance of the covariate information usage in our BP formulation.
6.3 LEARNING AGGREGATE EMBEDDINGS HELPS
As we highlight in figure 3, the addition of the additional bag loss head in our Aggregate embedding loss in equation 9 pipeline helps improve performance across both smaller and larger bags. Our choice of average pooling of different instances at bag level during the supervised learning provides the best performance. We also note that we experiment with much more complex choice for aggregation of instances within a bag like using Multi Multi-Head--e Head-Attention (MHA). This leads to slight degradation in the instance wise performance. We describe the architecture for this choice in the supplement.
90
85
80
WeB Mase Pooking
MCDA Vieas Faeling
WID. Vier Pool
Waa Maus Pooking
M0th Viers Faeling
95
75
AUROC %
AUROC X
80
AUROC %
AUROC %
20
80
70
90
AUROC
88
Adult
Marketing
Cnooo
80
CIFAR-B
CIFARS
Figure Comparison of the performance on different types of the pooling for the aggregate- embedding loss across different datasets for bag-size 512 for Adult and Marketing and bag-size 32 for Criteo, CIFAR-B and CIFAR-S the end of iteration 1.
7 CONCLUSION
Thus we have provided a highly generalizable algorithm to perform efficient learning from label proportions. We utilised Belief Propagation on parity like constraints derived from covariate infor- mation and bag level constraints to obtain pseudo labels. Our unique Aggregate Embedding loss used instance wise pseudo labels and bag level constraints to output a final predictor. We have also provided theoretical insight into why our approach works through varied ablations different components and extensive experimental comparisons against several SOTA baselines across various datasets of different types.

---

Published as a conference paper at ICLR 2024
ETHICS STATEMENT
The algorithm we propose is implementable over datasets of various kinds, including but not limited to tabular and vision and demonstrate the efficacy of our approach via comparisons several such datasets while beating several strong LLP methods. To the best of our knowledge, our work does raise any ethical concerns.
REPRODUCIBILITY STATEMENT
We have described in detail the implementation details for the reproducibility of the experiments in the main paper Section 5.1 supplementary material Section A.5. We provide the hyperparameter ranges and experimental methodology in section 5.1 and additional information, including that for the baselines in supplementary section A.5. We have provided extensive set of hyperparameters in A.6 reproduce our algorithm's numbers. We will soon publicly release the source code.
REFERENCES
Criteo lcaderboard, 2023.
teaet-rrtee-rreeeee wwt.-rr-eeedddiicoooooooo------- https//paperssitthocb..ccm con/sota/ clicckthrough-
URL
sota/
Early stopping 2023. URL
Ehsan Mohammady Ardehaly and Aron Culotta. Co-training for demographic classification using deep learning from label proportions. 2017 IEEE International Conference on Data Mining Workshops (ICDMW), pp. 1017-1024. IEEE, 2017.
James Bradbury, Roy Frostig. Peter Hawkins, Matthew James Johnson, Chris Leary Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL
http:/ httttbb.bbug/ggg com/ homg//ooll/////oooooooooooome jax.
Robert Istvan Busa-Fekete, Heejin Choi, Travis Dick, Claudio Gentile, et al. Easy learning from label proportions. arXiv preprint arXiv:2302.03//5 15, 2023.
Lin Chen, Thomas Fu, Amin Karbasi, and Vahab Mirrokni. Learning from aggregated data: Curated bags versus random bags. arXiv preprint urXiv:2305.09557, 2023.
Mayee F Chen, Daniel Y Fu, Dyah Adila, Michael Zhang, Frederic Sala, Kayvon Fatahalian, and Christopher Ré. Shoring up the foundations: Fusing model embeddings and weak supervision. In Uncertainty in Artificial Intelligence, pp. 357-367, PMLR, 2022.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pp. 1597-1607. PMLR, 2020.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL htlhhttp///achht ics. uci. www.....w...ww.........wwww edu/ml.
Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze gauss: optimal bounds for privacy-preserving principal component analysis. In Proceedings of the forty-sixth annual ACM symposium Theory of computing, pp. 11-20, 2014.
Ahmed El Alaoui, Aaditya Ramdas, Florent Krzakala, Lenka Zdeborová, and Michael Jordan. De- coding from pooled data: Phase transitions of message passing. IEEE Transactions on Information Theory, 65(1):572-585. 2018.
Brendan Frey and David MacKay. A revolution: Belief propagation in graphs with cycles. Advances in neural information processing systems, 10, 1997.
Robert Gallager. Low-density parity-check codes. IRE Transactions on information theory. 8(1): 21-28, 1962.
10

---

Published as a conference paper at ICLR 2024
Olivier Chapelle Jean Can-taatiste joycenv. Display advertising challenge, 2014. URL https:
/ //kaggle-. com/ http://copettiiiiii wtt.::iiiiiiooiiieedeeeeeaaaaaaa ad-pppaaaaa---alalaaaaaaaaa
Giannis Karamanolakis, Subhabrata Mukherjee, Guoqing Zheng, and Ahmed Hassan Awadallah. Self-training with weak supervision. arXiv preprint arXiv:2104.055/1 05.0444,, 2021.
JinHyung Kim and Judea Pearl. A computational model for causal and diagnostic reasoning in inference systems. In International Joint Conference Artificial Intelligence, pp. 0-0, 1983.
Ryoma Kobayashi, Yusuke Mukuta, and Tatsuya Harada. Risk consistent multi-class learning from label proportions. arXiv preprint arXiv:2203. 12836, 2022.
Ron Kohavi al. Scaling up the accuracy of naive-hayes classifiers: A decision-tree hybrid. In Kdd, volume 96, pp. 202-207, 1996.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Frank R Kschischang, Brendan Frey, and H-A Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on information theory, 47(2):498-519, 2001.
Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set trans- cotiuuttttooniivvrrian neural networks. In International
former: framework for attention-based conference on machine learning, pp. 3744-3753, PMLR, 2019.
Jiabin Liu, Bo Wang, Xin Shen, Zhiquan Qi, and Yingjie Tian. Two-stage training for learning from label proportions. arXiv preprint arXiv:2105.1063: 2021.
David JC MacKay. Information theory, inference and learning algorithms. Cambridge university
press, 2003.
Kushal Majmundar, Sachin Goyal, Pranceth Netrapalli, and Prateek Jain. Met: Masked encoding for tabular data. arXiv preprint arXiv:2206. 21t.:22200.88644,, 2022.
Joris M Mooij and Hilbert Kappen. Sufficient conditions for convergence of the sum-product algorithm. IEEE Transactions on Information Theory, 53(12):4422 4437, 2007.
Sergio Moro, Raul Laureano, and Paulo Cortez. Using data mining for bank direct marketing: An application of the crisp-dm methodology. 2011.
MEJ Newman. Message passing methods complex networks. Proceedings of the Royal Society A, 47902270) 2023.
Nicolas Papernot, Martín Abadi, Ulfar Erlingsson, Ian Goodfellow, and Kunal Talwar. Semi- supervised knowledge transfer for deep learning from private training data. arXiv preprint arXiv:1610.05755. 2016.
Giorgio Patrini, Richard Nock, Paul Rivera, and Tiberio Cactano. (almost) no label no cry. Advances in Neural Information Processing Systems, 27, 2014.
Judea Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan kaufmann, 1988
Judea Pearl. Reverend bayes on inference engines: A distributed hierarchical approach. In Proba- bilistic and Causal Inference: The Works of Judea Pearl, pp. 129-138. 2022.
Rafael Poyiadzi, Raul Mantos-Rodriguce and Niall Twomey. Label propagation for learning with label proportions. In 2018 IEEE 28th International Workshop Machine Learning for Signal Processing (MLSP), pp. 1 1-6. IEEE, 2018
Lutz Prechelt. Early stopping-be but when? In Neural Networks: Tricks of the trade, pp. 55-69, Springer, 2002.
Rattana Pukdee. Dylan Sam, Maria-Florina Balcan, and Pradeep Ravikumar. Label propagation with weak supervision. arXiv preprint 14..5:2200.03594 2022.

---

Published as a conference paper at ICLR 2024
Novi Quadrianto, Alex J Smola, Tiberio S Cactano, and Quoe V Le. Estimating labels from label proportions. In Proceedings of the 25th international conference on Machine learning, pp. 776-783, 2008.
Alexander Ratner, Stephen H Bach, Henry Ehrenberg, Jason Fries, Sen Wu, and Christopher Ré. Snorkel: Rapid training data creation with weak supervision. In Proceedings of the VLDB Endowment. International Conference on Very Large Data Bases, volume 11, pp. 269, NIH Public Access, 2017.
Thomas J Richardson and Rüdiger L Urbanke. The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on information theory, 47(2):599-618, 2001.
Rishi Saket, Aravindan Raghuveer, and Balaraman Ravindran. On combining bags to better learn from label proportions. In International Conference Artificial Intelligence and Statistics, pp- 5913-5927. PMLR, 2022.
Jonathan Scarlett and Volkan Cevher. Phase transitions in the pooled data problem. Advances in Neural Information Processing Systems, 30, 2017.
Clayton Scott and Jianxin Zhang. Learning from label proportions: mutual contamination frame- work. Advances in neural information processing systems, 33:22256-2221 2020.
Xingyou Song, Sagi Perel, Chansoo Lee, Greg Kochanski, and Daniel Golovin. Open source vizier: Distributed infrastructure and api for reliable and flexible black-box optimization. In Automated Machine Learning Conference, Systems Track (AutoMI.-Con) Systems), 2022.
Kuen- Han Tsai and Hsuan- Tien Lin. Learning from label proportions with consistency regularization. In Asian Conference on Machine Learning, pp. 513-528. PMLR, 2020.
Jinsung Yoon, Yao Zhang, James Jordon, and Mihaela van der Schaar. Vime: Extending the success of self-and semi semi-supervised learning to tabular domain. Advances Neural Information Processing Systems, 33:1 11033-11033, 2020.
Felix X. Yu, Dong Liu, Sanjiv Kumar, Jebara Tony, and Shih-Fu Chang. \proptosvm for learning with label proportions. In International Conference on Machine Learning, pp. 504-512. PMLR, 2013.
Felix X. Yu, Krzysztof Choromanski, Sanjiv Kumar, Tony Jebara, and Shih-Fu Chang. On learning from label proportions. arXiv preprint arXiv: /002.590,, 2014.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint arXiv:1605.07144 2016.
Jianxin Zhang, Yutong Wang, and Clayton Scott. Learning from label proportions by learning with label noise. Advances in Neural Information Processing Systems, 15:26933--29422 2022.
Guangyao Zhou, Nishanth Kumar, Antoine Dedieu, Miguel Lázaro-Gredill Shrinu Kushagra, and Dileep George. Pgmax: Factor graphs for discrete probabilistic graphical models and loopy belief propagation in jax. arXiv preprint arXiv:2202.d0 10, 2022.
12

---

Published as a conference paper at ICLR 2024
A ADDITIONAL ANALYSIS
A.1 ADDITIONAL ABLATIONS
A. I-NEAREST NEIGHBOR CAPTURES A LOT OF THE GAINS
We now show that using Nearest Neighbour Information for the SUM-PRODUCT-BE is empirically close enough to the best performance we get on the best & chosen for k-nearest neighbors used in SUNN-PODDCTT-O
by hyperparameter search. From Figure 4, we that across multiple datasets test metrics are very close for the two settings. This shows lower & which reduces time complexity of the BP step (see section 6. 6.1) does not affect the performance greatly.
Crnso
CIFAR-B
CIFAR-S
Adst
Marioting
AM
88
8500
1MM
73.0
Bag
Deg
Eeg
Figure 4: Change in values of Test AUROC when using only nearest neighbour for the covariate factor creation, v/s when using an optimal higher & for the covariate factor creation.
A.1.2 NOISY EMBEDDINGS AS INPUT
We add noise variables sampled from (0, Ta) to our features input to the first iteration and report the numbers obtained in Ind-tteration supervised learning step in figure 5. Medium Noise regime corresponds to = 0.05 and High Noise regime corresponds to a = 0.1. As is clearly visible our method is able to recover performance even when using noisy inputs. We would like to note that there is some degradation at bag size level 512. We point out that this is case where there about 100 bag level labels in total. Covariate information is rather crucial to make any progress. Hence noise addition has the most impact in this regime. This also suggests importance of using covariate information for large bag sizes due to very weak supervision available. The drop in performance due to noisy embeddings is significantly higher for the Marketing dataset than the Adult dataset. This shows that the coariates are very important for the Marketing datasets and our method exploits very well. We posit thatt his could be the reason our method significantly outperforms others on the Marketing dataset (See Table 1).
Adult
Marketing
No Notse Midium High
85
AUC %
86
AUC %
84
70
Nois
High
80
65
32
128
512
8
32
128
512
Bag
Bag Size
Figure 5: Recovered performance on adding noise to the initial embeddings.
A.1.3 SOFT WEIGHTED HARD THRESHOLD v/s VANILLA HARD THRESHOLD
In figure 6 we report the numbers obtained on using the soft-labels from the BP-Marginals as opposed to hard thresholding them. We use the soft labels in two ways, directly to train the MLP using sigmoid cross entropy loss formulation as opposed to the usual binary cross entropy loss, and the other for weighing the hard-labels by ip -| where p is the soft label and 7 the threshold for creating the hard labels. We do not notice any consistent improvements on using the soft labels in either form across datasets and bag sizes and thus stick to hard labels for our setup.
13

---

Published as a conference paper at ICLR 2024
90
85
AUC %
80
Hard Thresholded Marginal
Direct Soft Marginal
Soft Weighted Hard Thresholding
75
8
32
128
512
Bag Size
Figure 6: Change in values of MLP AUC when using Soft Weighted Hard Thresholding for the conversion of BP-Marginals pseudolabels v/s Directly using the soft marginals v/s using Hard Thresholding on Adult Dataset for 2nd Iteration.
A.1.4 DISTANCE METRIC: COSINE v/s L2
As mentioned earlier, experiment with using Cosine and L2 distance, d(:,.) for the construction of our neighbour graph. While we don't 't find significant differences on using the two methods, using Cosine led to better downstream performance across datasets and bag sizes. This be interpreted to be due to the better neighbour graph construction as depicted in Figure for Adult, by better Test Score (Accuracy) of the kNN constructed by the two distance metrics for varying number of neighbours (k) for the construction of the neighbour graph.
Adult
Cosine
84
L2
Test Score %
83
82
81
80
3
7
9
Figure 7: Variation in the kNN Score across bag sizes compared for the two popular distance metrics, Cosine and L2 on Adult Dataset as d(-,-) for the neighbour graph creation.
A.1.5 SIMILARITY KERNEL: RBF v/s MATERN
As discussed earlier, we tried both the RBF Kernl and Matern Kernel for our experiments and note as in figure 8 for Criteo, that the Matern Kernel resulted slightly better Test AUC Scores across various datasets and bag sizes. While there is substantial increase in performance the marginally better numbers can be attributed to the fact that the Matern Kernel a generalization of the RBF Kernel and might capture the similarity information between the embeddings aptly.
14

---

Published as a conference paper at ICLR 2024
Criteo
80
Matern
RBF
75
AUC
70
65
8
32 Bag Size
128
Figure 8: Variation in the Test AUC % of the MLP after 1st Iteration on using RBF Kernel v/s on using Matern Kernel k(--)) for similarity caleulation during formation pairwise factors on Criteo.
A.1.6 OPTIMAL VALUES OF Aa
As observed in Figure 9, it is clear that the bag-loss head plays more important role when the bag sizes are smaller. The optimal value of Xa is dependent on the requirement of the reinforcement the hag constraint via the bag-loss head. For small bags, the bag constraints hold much more information than that for large bags, and hence are more usefuul In the case of small bags, during aggregation of embeddings, more information is retained and utilized downstream since fewer embeddings are pooled. We pool 8 embeddings per bag for bag size 8 and 512 embeddings are pooled for bag size 512, clearly there is stark divide the information summarized across bag sizes. This trend is consistently noticed across multiple datasets. We also notice that the optimal values of X are comparatively lower for the 2nd Iteration our method. We think this might be due to the refined embeddings and neighbour graph in the 2nd iteration of Belief Propagation.
Criteo
CIFAR-S
10.0
Iteration
Iteration
Optinal Volue for Ax
7.5
Optimal Vilus A
7.5
5.0
5.0
2.5
2.5
0.0
0.0
8
32 Bag Size
128
8
32
128
512
Bag Size
Figure 9: Variation the Test AUC the MLP after 1st Iteration on using RBF Kernel v/s on using Matern Kernel k(.,-) for similarity caleulation during formation of pairwise factors Criteo.
A.2
EXTENDED EXPERIMENTATION
A.2.1 WALL CLOCK TIMES ON ADULT DATASET
We have wall clock time reported in Table 4 (main paper) and Table 5 for Criteo and Adult respectively. Criteo has 1 million samples in total in the training. For bag size 32, the wall clock time of the entire BP stage is only 1279s for millions of factors in the factor graph inclusive of the creation and iteration. For smaller datasets like Adult with 50k samples, even bag size large 2048, the BP
15

---

Published as a conference paper at ICLR 2024
stage takes only 1054s NVIDIA P100 GPU, which is minimal computational overhead above standard supervised learning. It also conventionally known that BP on sparse graphs is very fast and our sparsity is controlled by using K-NN instead of all pairs in imposing nearness constraints. We reiterate that the number of factors in the factor graph is thus only linear in the number of samples allowing for faster iterations. The time taken in the entire BP section, right from creation of the factor graph to message passing for 100 iterations happens in the order of (bag size) seconds for the Adult dataset which is exceptionally fast as simple MLP training itself takes O112)) seconds.
Table Time for various parts of our algorithm compared to time taken by other methods on Adult Dataset. All time values are in seconds. Note that Data Setup time is common to All Methods
Adolt ~50k Samples
Bag
Training
Ea Trinnngg
Gen Triining
Sctup
MLP
52.25 381
(28.93)
256.99
650.8 (827.63)
(8.37)
33.03
128.21 69)
45.4 (69.04)
26.51 (12.67)
125.67 (102.99)
523.59 (449.37
21.11 (14.55)
54.38 (77.15)
599.00 (458.12)
128
73.79 (125.96)
21.38 (15.99)
88.72 (76.21)
623,20 (458. 23)
(8.88
54.34 (3))55
748.71 (459.86)
512
25.11 (40.
18.84 (9.42)
85.52 (74.49)
767.58 (431 50)
269 (32.52)
65.07 (158.34)
1102.53 (459.
26.39
20:93 (14.51)
95.79 (103.85)
(674
580.32 (113:28)
32.42
1221.78 (756.34)
2048
24.34 (28.52)
18.77 (6.69)
(71.80)
612.87 (539.07)
1054.47 (73.71)
49.93 (78.34)
1717.27 (534.88)
A.2.2 CONVERGENCE OF THE TWO STEP METHOD
In Table 6 empirically demonstrate that method converges in iterations by looking relative improvements between iterations 2 and 3. We demonstrate that two iterations of our algorithm suffice empirically.
Table 6: Empirical Convergence: The % AUC scores for varying bag sizes for 2 Iterations and Iterations of our algorithm.
Adult
Marketing
Bag Size
8
32
128
512
8
32
128
512
Itr-2
89.47
87.82
86.87
84.01
86.26
84.33
82.46
81.68
Delta
-0.29
-1.26
0.49
0.71
-0.26
-0.94
-0.13
-1.05
Itr-3
89.18
86.56
87.36
84.72
86.00
83.39
82.33
80.63
As visible, performance gains from 2nd to 3rd iterations are not consistently better. Thus there is no clear reason run higher iterations of the algorithm, maximum of 2 iterations suffice to achieve significantly consistent performance.
A.2.3 GOODNESS OF PSEUDO LABEL OF BP
We report the AUROC of BP after the first iteration with respect to the true labels in Table 7. It is considerable indicating that it has good ordering information (ranking of samples belonging to class above class 0). The effect of high quality pseudo labels is reflected in the downstream performance.
Table 7: The % AUC scores of the pseudo labels obtained from the Belief Propagation algorithm when compared to the ground truth labels for iteration of the algorithm
Bag Size
8
32
128
512
1024
2048
Adult
86.34
79.63
75.25
75.02
67.88
63.54
Marketing
88.53
78.26
75.5
75.66
74.9
74.64
While Table 7 only reports after Step of iteration 1 to showcase value of the BP step, the second aggregate embedding loss based MLP training Step 2 boosts performance of Step further and we do it expected in Table 1. Refer to Section 4, subsection 4.1 I.1 for Step 1, and subsection 4.2 for description of these steps in our algorithm.
Step 2 is necessary because information from pseudo labels may not satisfy bag constraints exactly. So we have a composite loss that again imposes the bag constraint through an aggregate embedding loss (see Equation and Equation 9 in the paper in Section 4.2)
16

---

Published as a conference paper at ICLR 2024
A.2.4 NOISY LABELS AND PRIVACY
In this section we explore utility-privacy tradeoff of our algorithm when we add noise to label proportions for every bag by Gaussian Mechanism to achieve target label differential privacy of (c, 6) by using the following result:
Theorem (Theorem 2 in (Dwork et al., 2014)). Let : - RR be real-valued function. Let The Gaussian Mechanism, which adds independently drawn random r?) to output of fAA, ensures (c, -diffferreett privacy.
т = Aʃ
noise distributed as NO,
We take A to the set of true labels of instances in bag S B, f(-) = ) the label proportion. We observe that sensitivity of the label proportion to change in single label is As B. where B denotes the bag size. Standard deviation of the noise added is proportional to 1/B for fixed e,
We demonstrate the following interesting privacy-utility tradeoff: utility degradation, as measured by Test AUC, due to Gaussian Mechanism is much more in smaller bags compared to larger bags for a target privacy level. Through this, we empirically verify the intuition that points to the fact that larger bags offer better privacy. We that our algorithm performs much better in large bags regime compared to baseline and we conjecture that this is crucial to utilize the better privacy utility degradation tradeoff's at larger bag sizes.
We experiment with 2 sets of differential privacy parameters, Medium Noise: (6, c) = (10-5,1 10) and High Noise: (6, = (10 1), both popular choices in literature (Papernot et al., 2016) Note that, bag size B takes values in (8,32, 32, 128, 512}. Our results are reported in Table 8.
Table 8: Test AUROC scores after Iteration-1 I of our method across different bag sizes for varying
levels of lobel-noise.
Dataset:
Criteo
CIFAR-B B
CIFAR-S Medium
Noise:
Noiseless
Medium
High
Noiseless
Medium
High
Noiseless
High
8
74.96 mam
74,83 mm
71.06 aus))
95.39 gun
94,80 oue
90.99 o.1)
93.53 811)
93.28
87.07 (000)
32
73.36
72.43 mi
70.40
93.89
93.36
90.25
91.17
91.07
86.08
128
70.45 nasi
69.45 m20
69.53 mzu
89.28 yeu))
88.92 0.1
87.79 jum
88.17 17 0219
87.39 ousc)
85.17 9229
512
85.55 1075)
83.29 0133)
84.65 mmm
82.97 0135)
81.32 oum
79.39 3500
We also want to highlight that under the effect of both medium and high noise our method recovers performance up to a reasonable degree, especially for larger bag sizes which as stated earlier are more important from privacy perspective.
A.2.5 MAP DECODING
Table and Table 10 denote the Test AUC on performing Max Product BP on the Gibbs Distribution, and highlight the noisy nature of the performance. This establishes the superiority of Sum Product BP, that our approach, to obtain consistently good performance across bag sizes and datasets. On the other hand, the single label configuration obtained from the Max Product approach is noisy and does not consistently retrieve the same performance as the Sum Product approach across bag sizes.
One plausible reason is that given the nature of the weak supervision, i.c. aggregate labels being available only the level of bags, better find out uncertainty in a label for an instance (marginalize) rather than commit to MAP configuration with respect to a Gibbs distribution that is uncertain.
Table 9: MaxProduct BP on Adult Dataset
Bag Size
Test AUC Itr-1
Test AUC Itr-2
8
89.15
88.92
75.29
87.9
128
76.08
84.67
512
73.77
73.82
1024
80.43
76.65
2048
74.45
68.69
17

---

Published as a conference paper at ICLR 2024
Table 10:
MaxProduct BP Marketing Dataset
Bag Size
Test AUC Iter
Test AUC Iter
8
85.55
85.73
32
83.99
83.67
128
82.64
82.39
512
72.29
80.66
1024
72.48
73.03
2048
72.49
80.42
A.2.6 EXTENSION TO THE MULTICLASS PARADIGM
We adapted the Gibbs measure the multi class setting follows. Every point has & labels y/ ...y. v corresponding to k classes.
We have three main types of terms in the Gibbs measure. We impose soft one hot constraint with the term: (Ep v 1)²
Nearness terms get modified follows: K K (,),,,)) E,, (v/ ", i.c. Euclidean distance between the vector labels of two points is small if they are nearby.
Aggregate Bag level constraints have counts ...b.. Then we simply impose least squares constraint: Ep (ZiB v/" bp
All these terms are scaled by temperature hyper parameters which we search over during training. Essentially these are vectorized least squares constraints.
The results on CIFARIO as provided in Table 11 depict that our method is slightly better or comparable the SOTA.
Table 11: % Accuracy of our method against high performing baselines on CIFARIO multiclass classification.
Bag Sizes
8
32
LLP-VAT
66.91 (1.23)
60.85 (2.45)
LLP-FC
66.52 (2.12)
62.35 (1.32)
DLLP
68.14 (0.48)
62.87 (0.88)
Ours-Itr-
68.05 (0.23)
61.83 (0.21)
Ours-Itr-2
69.23 (0.12)
61.92 (0.43)
A.3. ANALYSIS OF 1-NN GRAPHS
Section A.1.1 shows that running our algorithm with 1-NN for the BP step captures most of the performance terms of the final Test AUC score. We show that many parts the factor graph the case of 1-NN are cycle free.
Consider the bi-partite factor graph K(V,BUF E) where variable nodes = [1: N] representing {x,) form one partition and bag factor nodes B and I-NN factor nodes F ( (f, (f.j) E, Ir, E (1,))) V I E N1 (x;))) are on the other partition. Edges between a bag factor node S and variable node exists if i (z; belong to bag S).
In our setup (experiments), all bag factor nodes have disjoint neighbors since bags are formed randomly without replacement. Therefore, the bi-partite factor graph between B and V is forest. Now, consider the bi-partite factor graph between F and V. We now show that this also a forest. Since every factor node connects only pair of distinct nodes it is enough show that the undirected 1-NN graph does not have any cycles.
We show that the 1-NN graph does not have any undirected cycles. Recall that N1(x) is the nearest neighbor of point s.
Lemma 1. For a set of points {a;) consider the following undirected graph G(V, E) where V [1 N) and F ((i.)) E N1())) V xy E N₁ (I.)).. For every node i, if the edge is
18

---

Published as a conference paper at ICLR 2024
formed by choosing amongst manty equivalent nearest neighbors of appropriately (f.e. N1 (2:) chosen to be a singleton), then G does not have any cycles.
Proof. Let define a directed graph Ga. where the outgoing edge (i - j) exists if zj is the closest neighbour of ži where ties are broken arbitrarily. Thus every node has out-degree However, note that the in-degree of any node can be > 1. Note that, G can be obtained by replacing oriented edges in Ga by undirected edges. Further, if (i + j), (i i) both exists, we replace by one undirected edges (i, E G.
at-most 1.
There are 3 types of cycles in Ga:
1. Directed cycle with at least 3 distinct elements (except end point which is repeated). An example of this kind (of length 3) is illustrated in Figure 11.
2. Cycle with collider whose undirected skeleton forms a cycle in G of length at least 3 with distinct elements. This is illustrated in Fig. 12.
3. Directed cycle + i. This illustrated in Figure 10.
Now, we proceed to show that the first two cycles are not possible, Since bi-directed edge in Ga (Figure 10) will get replaced single un-directed edge in G, this proves the Lemma.
b
b
d2
Figure 10: Cycle of Type 3
Case 1: We deal with the directed cycle by first proving a claim about a directed path in Ga-
Claim 1. Consider directed path in Ga of the form 01 di a2 d2, ag ds, as a.... an with distinct elements. Here, di notes the distance d(Fa, Bo,-)) Then, d1 2 d2 2 d3 dn-1-
Proof. Let us prove this by contradiction. Say this was not true, then without loss of generality suppose di < de+1- We know that the outgoing edge represents the nearest neighbour of node. indeed true, then the nearest neighbour of a++1 would have been ag and a,-2
d; d:+1
det1, a--2 exists in Ga. We get contradiction and
which is clearly not the case since the edge a,+1 therefore the claim is proven.
Now, we consider the directed cycle aj di, a2 di, ag... an day ai where all elements a; are distinct.
b
b,
d
b
Figure 11: Cycle of Type 1
19

---

Published as a conference paper at ICLR 2024
From, Claim 1 we have d1 d2 d3 d, 2 d1 applying on two directed paths an 01, d2 and a1. 02 ... an. This is only possible if d1 = d2 = dn. In this case, one can form an alternate GJ by breaking the cycle where one can have d2
instead of d2 + 0g.
Therefore, this type a cycle cannot exist. If it exists, it can broken by re-assigning an equivalent nearest neighbor.
Consider configuration that is a undirected cycle in G' but not a directed cycle in Ga. Then, it is cycle consists of paths 1 02 ...... ans a1 d1,b,,00 n all nodes 04, by are distinct. An Example is the collider Cq in Fig. 12. Other orientations are left unspecified in this cycle. For this to there must exist a; * on or by that has 2 outward edges in this cycle. However, out - degree 2 2 is clearly cannot be possible as we are only dealing with I-NNs and each node can have at-most one outward edge. Therefore such cycle is not possible. In the Figure 12, the edge 0 + C4 c + C2 cannot exist as Ga is directed 1-NN graph and thus such cycle cannot exist.
Case 2:
On where they collide at an. Here
C₂
d2
C
C3
dg
C4
Figure 12: Cycle of Type 2
Thus, we have shown that no cycle can exist in the neighbour graph G.
A.4 BASELINES
We compare methods with the following baselines.
1. DLLP: We use the DLLP method from Ardehaly & Culotta (2017) as a baseline for both Tabular and Image Datasets. This method fits the prediction score averaged over bag of a deep classifer to bag level proportions.
2. EasyLLP: This was proposed in Busa-Fekete et al. (2023) and on all our datasets. They define a surrogate loss function based on the global label proportion.
this competitive baseline
3. GenBags: Introduced in Saket et al. (2022) is another popular algorithm for tabular datasets. The algorithm combines bag distributions, if possible, into good generalized bag distributions, which are then trained on by using standard proportion loss.
LLP-FC: This methods was introduced in Zhang et al. (2022) where LLP problem was reduced to learning from label noise problem. We use this for image datasets on which it applied in Zhang et al. (2022).
Image Datasets. This method is inspired by consistency regularization to produce decision and approach LLP from a semi remi-supervised angle. boundary that better describes the data manifold
5. LLP-VAT: Method from Tsai & Lin (2020) that
A.5 IMPLEMENTATION DETAILS
In most of our experiments, we fix d(x, to be Cosine Distance: 1
~ or Euclidean
2-
Distance:
(Minkowski Distance with p=2) (En jx; - -) and we choose k( x²) to be one of RBF Kernel: exp( (? d(xxx')3)) or Matern Kernel: (a generalization of RBF kernel)
K.
V (( where d(...) is the Fuclidean distance, K,(-)
modified Bessel function and r(.) is the gamma function. We justify our choice via the slightly
20

---

Published as a conference paper at ICLR 2024
superior performance observed on using Cosine Distance and Matern Kernel as discussed in ablations in A.1.4 and A.1.5 respectively.
The bags are batched into batches of size max BatchhSzzttriin Tags) We always the second step, the MLP training for max 100 epochs, using Adam Optimizer with MLPLn M LPWD learning rate and weight decay respectively. We the Early Stopping criterion decide when to stop training. According to this, we stop training if the validation AUC does not increase for 20 consecutive epochs, and then restore the model with the best validation AUC. Such a validation- early stopping technique is quite popular in literature and well described in Prechelt (2002). Attached the tensorflow callback code that we implement for the same, based on documentation provided in ker (2023):
tf keras. Tbacks Barackks.arlyttoopiinn
menitor=' valoo===vaa_uus
patience=20,
restore__estt_eeigeee min_delta=0, verbose=1,
mode=' maxi=
We use the official GitHub Implementations of Saket al. (2022), Zhang et al. (2022) and Tsai & Lin (2020) and perform a grid search over relevant mentioned parameters in their readme. We use WideResNet-lee
(Zagoruyko Komodakis, 2016) as the backbone for LLP-VAT and LLP-FC methods as it provides the best performance. For methods described in Busa-Fekee et al. (2023). Ardehaly & Culotta (2017) we implement the algorithm described in the paper with the same MILP as described in 5.1 and sweep the appropriate hyperparams as described in the respective papers.
For Pooling with SalttHHeadAtteention we use the standard MultiHeadAAttenin Transformers (Lee et al., 2019) using d = 128 dimensional embeddings as input (the 2nd last hidden layer of our MLP), heads, seed vector, and row-wise feedforward layers each of size d.
framework from Set
A.6 ILLUSTRATIVE BEST HYPER-PARAMETE VALUES
Here we provide the set of hyperparameters to reproduce the numbers obtained the first iteration of our algorithm across all datasets and bag sizes in Table 12, Table 13, Table 14, Table 15 and Table 16.
Table 12:
The set of hyperparameters for various bag sizes for Adult Dataset for the first iteration.
Bag Size
X
A
Ao
MLPIR
MLPwD
k
T
T
2048
0.0001
0.0184
0.0001
0.0007
1.00E-12
0.03558
100
1028
0.0001
0.0576
0.0001
0.0012
1.00E-12
1
0.01
100
512
0.003
0.0796
0.0001
0.00033
0.00025
1
0.03
100
125
0.0001
0.3422
10
0.00028
0.1
1
0,0216
0.01
100
32
186
0.1659
7.5
0.00014
2.12E-11
17
0.3327
0.6
100
0.0001
0.4427
10
0.001
1.00E-12
1
0.3515
100
Table 13:
The of hyperparameters for various bag sizes for Marketing Dataset for the first iteration.
Bag Size
Ag
As
A
M LLPR
MLPwD
T
2048
1.928
7,6986
0.0136
0.0002
3.70E-07
0.5311
0.1489
100
1028
0.0001
0.02227
0.000167
0.00005
0.06129
28
0.03077
0.4963
100
512
0,00287
0.2676
0.00053
0.0825
7
0.0815
100
125
200
26.058
10
0.0027
0.0007735
28
0.03357
0.01
100
32
200
200
9.661
0,00058
4,54E-12
29
0.0111
100
8
4.146
2
0.0001
0.00085
9.20E-11
2
0.2023
1
100
21

---

Published as a conference paper at ICLR 2024
Table 14:
The set of hyperparameters for various bag sizes for Criteo Dataset for the first iteration.
Bag Size
A
Ao
MLPLR
MLPwD
k
6g
T
128
0.4359
0.2265
0
0,000001
0.0000078
11
0.14294
0.00288
200
32
0.0003
0,2502
9.9885
0.00002368
0.000547
23
0.5335
0.1326
200
8
0.00015
0.1884
9.716
0.00006
0.0009567
29
0.4104
0.9996
200
Table 15:
The set
hyperparameters for various bag sizes for CIFAR-S
Dataset for the first iteration.
Bag Size
X,
Ab
A
MLPLs
MLPwD
7
T
2048
0.057
0.02646
0.000156
0.000589
0.0000018
0.02687
0.6339
200
1024
0.00015
0.0175
0.00169
0.0006
0.000025
15
0.1214
0.9697
200
512
34.32
0,0338
0
0.00038
0.000014
0.267
0,2614
200
128
0.3674
0.105
0
0.0016
0.00476
0.31
0.01823
200
32
12.43
1.2541
10
0.000068
0.000336
0,4934
0.3727
200
8
0.0001
0.8555
10
0.0002
0.00001
28
0.1961
0,4421
200
Table 16:
The set of hyperparameters for various bag sizes for CIFAR-B Dataset for the first iteration.
Bag Size A
As.
A
MLPLR
MLPwD
k
T
8x
T
2048
0.00043
0.8279
0.0002
0,000001
0,000001
2
0.5936
0.2771
200
1024
0.0001
0.003556
0.00695
0.00032
0.000001
4
0.435
0.6544
200
512
0.1289
0.00754
0
0.0116
0.0011
14
0.4337
0.407
200
128
0.0001
0.016
0
0.00214
0.00002
25
0.4508
0.0001
200
32
0.000192
0.0968
8.8918
0.000096
0.000723
1
0.4294
0.00385
200
8
0.0008
0.099
10
0.0000013
0,000009
0.4856
0.2427
200
B EXTENDED RELATED WORK
Belief Propagation: Belief Propagation (BP) has been used to compute marginals and find MAP estimates in standard sparse graphical models, like Bayesian networks and Markov random fields (Pearl, 2022) by message passing across edges on an appropriate graph. Sum-product BP algorithm is used for computing marginals and is known to converge on trees. It was also extended polytrees (Kim & Pearl, 1983). It is also an effective approximate algorithm on general graphical models (Pearl, 1988). More relevant our work is the fact that sum product Belief Propagation has found widespread in communication system, where it is used to soft-decode binary string message from their parity checks as in LDPC (low-density parity-check) codes (Richardson & Urbanke, 2001; Gallager, 1962), iterative decoding of turbo codes (MacKay, 2003; Kschischang et al., 2001). In communication codes, parity checks are designed so as to have nice properties on the graphical models they induce. In our problem, the bag levels constraints can be thought of as parity checks but are given and we add additional constraints from covariate information that is also given. We public scalabale and efficient implementation PCMax (Zhou al., 2022) of the sum-product message passing algorithm.
Decoding from Pooled Data: Another very relevant area of work learning from pooled data paradigm Scarlett & Cevher (2017); El Alaoui et al. (2018) where the aim to identify the categorical labels of a large collection of items from histogram information at the bag level. El Alaoui al. (2018) present an approximate message passing algorithm for decoding discrete signal of categorical variables from several histograms of pooled subsets of data. This line of work is also largely aimed at the regime of very large bags (Scarlett & Cevher, 2017) (~ O w and there is no covariate information available. In our problem, bags are constant in size and they are disjoint.
There has been recent interest in exploring training of models under weak supervision, where complete label information is not available. Though these methods do not exactly map to the learning from label proportions setup, the idea of using pseudo labels to train a model with pre-trained representations has been explored before in Chen et al. (2022), Pukdee et al. (2022), Ratner et al. (2017), Karamanolakis et al. (2021), which creatively bypass the lack of labels, by either using covariate information, label propagation based on the few available labels, heuristically creating new labels or even using student-teacher models. While such approaches are designed to work in the case of lack of all instance labels, none of them deal with the specific case of weak supervision
Weak Supervision:
22

---

Published as a conference paper at ICLR 2024
concern ourselves with, namely learning only from the aggregate bag labels and no instance labels whatsoever. This is what makes the LLP setup even harder and sparser in terms of information available for the learner.
C APPROXIMATE CONVERGENCE ANALYSIS
Loopy Belief Propagation in the literature: We would like to point out that even classical literature from the past Frey & MacKay (1997) has pointed out that while loopy belief propagation in graphs with cycles don't have known convergence guarantees, in many applications like error correction for communicating over noisy channels, belief propagation based decoding perform extremely well (abstract of Frey & MacKay (1997) makes exactly this case). Even considering very recent work on message passing on complex networks Newman (2023), the conclusion remains that loopy belief propagation is effective in practice but not very easily amenable to analysis. Although showed the edges due to the similarity constraints form a cycle free graph for 1-NN based Gibbs distribution, bag constraints introduce cycles. However, Newman (2023) offers an approximate analysis based on linearized version of sum- uum-product-Bi -PP that we adopt and we show that the inverse temperature parameters chosen for Adult Dataset (Table 12) are roughly orderwise within the stability region for an approximate linearized version of BP with the same graph structure in the Gibbs distribution we define.
Sufficient conditions for convergence of the Sum-Produet Algorithm (Mooij & Kappen, 2007):
We refer to Corollary from (Mooij & Kappen, 2007) for sufficient condition such that message updates from Loopy BP is contraction. We substitute the values of Jıj. from our Gibbs Distribution For the case using
to evaluate this condition which is: max[([N (1) - 1) max (anh([J;;])
jEN((e
1-NN constraints, [i) discussed above and as observed from Table 12.
B (B is the bag size). Now note that [Jyl] S 2 + 4h, as
And we observe that for entries in Table 12 for example for bag size 8, for Corollary 1, the condition (Eq. 15 from the paper) is satisfied and thus our LBP is a conntracti and converges to a unique fixed point, irrespective of the initial messages.
For larger bags, we offer approximate linearized BP analysis below.
Stability analysis of the approximate linearized BP: Now, we offer some approximate analysis on convergence of the Belief Propagation step for some simpler cases (like the Adult Dataset). In what follows, we follow the recipe given in Newman (2023) to linearize the BP. We have a Gibbs distribution over binary variables {-1, given by:
Pyy) & exp Σ Elaae + Σ JiSKeN
h; forms the external field that biases the variables away from 1/2. However, we will analyze the Gibbs distribution without h; as this external field can be taken to be the prior bias for each of the variables.
{Jiz} } is very sparse and is non zero only if j are in each others 1-NN neighborhood or i,j belong to the same bag. Jty in our formulation could be negative but we actually, analyze the ferromagnetic version with only the correct adjacency matrix, i.e.
PV)) x exp( 3 Σ [
For the above Ising model over y, we have the following normalized update rule (this from Newman (2023)):
23

---

Published as a conference paper at ICLR 2024
(1 + {t-s) = 1
II
(exp(3) + tz++)) + - sz+x
2
Ziri kEN(j)-
Zi-s= =
E II
(exp( +xp(- cg-
(10)
1=(+1-1)-EN()))
Here, (j) is the neighborhood of according to the graph obtained from the 1-0 adjacency matrix 11 This is equivalent to the BP iterations quoted Section 4.1 (except for the normalization
Za-j and setting (++)(++))
Gr-j. m-- = 1 Gt-j due the normalization.
Again following Newman (2023), and ignoring the second order terms in O we have the following linearized Belief Propagation:
Giej tanh 3
Σ AEN())-i
Ej+b
(1I)
We have an edge incidence matrix H of size 2 x 2| where |b| is the set of edges in the graph indexed by valid oriented edges i + j. For the row i j. all columns corresponding to j k # i, E N(j) have and all other entries are O.
Essentially, the messages if the linearized BP converge, then it is fixed point of the equation: X () Therefore, convergence is exponentially fast tanh(3) H| < 1 as the linear operator becomes contraction. Here, H ||2 is the spectral norm of H.
Computation of inverse temperature threshold for Adult Dataset: For the full Adult dataset, the edge incidence matrix even for 1-NN graph is of the order of 100k. Hence, computing the largest singular value of this is a time consuming operation. However, we randomly subsampled 5k: points from the distribution and analyze the spectral norm of the edge incidence matrix obtained from this.
We found that ||2 6.344. This means that inverse temperature is at most tanh (1 0.158 for the linearized BP to converge. We observe from Table 12 that |Jal S 2 + 4X, is much smaller than this threshold for larger bags.
Exact loopy BP updates are shown to be contraction based sufficient conditions in Mooij & Kappen (2007) for smaller bag sizes for Adult Dataset. With an approximate linearized BP analysis of the ferromagnetic model with the same graph structure, for subsampled set of data points i.i.d from the original Adult Dataset without replacement, we show that for large bags the chosen hyperparameters for inverse temperatures are well within the convergence threshold.
Key Takeaway:
D LIMITATIONS AND FUTURE WORK
There are several unexplored interesting directions that we wish to pick up future work. Notably, one of the primary ones to explore alternate energy potentials for the Gibbs distribution other than quadratic terms simple proposition like BP works on such scale efficiently converging to marginals proving highly useful in supervised learning even with 1-NN based covariate information. A complete theoretical understanding behind the success of BP for the target task would be an interesting direction building on the theoretical pointers in the supplement.
now. It might also be of independent interest to further investigate why such
24


Reviews:
[{"review_id": "EdIptndI9T", "reviewer": "Reviewer_Svbj", "summary": "This paper provided an algorithm to perform efficient learning from bag-level label proportions. The author utilized Belief Propagation on parity-like constraints derived from covariate information and bag-level constraints to obtain pseudo labels. Next, the Aggregate Embedding loss used instance-wise pseudo labels and bag-level constraints to output a final predictor. In the end, the authors also provided  experimental comparisons against several SOTA baselines across various datasets of different types.", "questions": "1. What's the performance of the proposed algorithm on real bag-level data?\n\n2. What's the time performance of other baseline algorithms?\n\n3. Are there any stopping rules to decide when to stop the iteration and ensure the convergence?\n\n4. What's the distribution and bagging assumption required for the proposed algorithm?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. Learning from bag-level Label Proportions (LLP)  is an interesting and valuable topic in the learning community. Privacy of data is one crucial consideration in this area.\n2. The literature part is clear.\n3. The structure of the paper is easy to follow.\n4. There is extensive experiment analysis on the algorithm performance.", "weaknesses": "Major\n1. In the setup section (section 3, p3), it lack the assumptions and descriptions on the data distribution (x,y), and bag distribution.\n1.1 For example, for distributions,  the proposed algorithm may not work and or could not converge\n1.2 Without data distribution assumptions, it will limit the guidance for practitioners. \n\n2. There is no analysis of the theoretical guarantee of the algorithm's performance.\n\n3. The proposed algorithm is much slower than the baseline algorithm, and the running time is about one order slower Table 4. However, the performance of the proposed algorithm in Table 2 and 3 are not significantly better in many setups.\n\n4. The 4 datasets in the experimental analysis are not real data on the bag-level. The bags are manually created.\n\n5. Some notations are not reader-friendly. \n5.1 For example, in formula (2), the meaning of  | | is not defined. \n5.2 3rd line in section 3 of p3, [m] is not defined.\n\nMinor\n1. In section 6.1, there is only time for one baseline algorithm, and it lacks time for other algorithms.\n\n2. Near all parameters are tuned. There is no guidance on how to choose them in practice for quick application. For example, there is no guideline for the stopping rule of the algorithm to ensure convergence.\n\n3. In the proposed algorithm, the pair-wise calculation could lead to a high order time complexity. For example, capturing k-nearest neighbors for every point x_i is a very slow process when the data size is large.", "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": "AaZEuUR5rT", "reviewer": "Reviewer_c8fH", "summary": "The paper proposes a novel algorithm for supervised learning from label proportions. One first builds a Gibbs measure that enforces the labels proportions within each bag and incentivizes nearby samples to have the same label. Then belief propagation (BP) is run on this measure, obtaining the marginals for each label. The marginals are converted to hard labels via thresholding. These new labels are then used to train a deep neural net. The network is trained on a double objective: one one side fitting the BP generated labels, on the other preserving the actual proportions of the labels in each bag. One of the internal representations of the network is then used as new covariates from which the BP and training are repeated. This algorithm achieves performances which are competitive with or superior to those of competing algorithms.", "questions": "1. To enforce the label proportions directly in the BP have you tried sending $\\lambda_b\\to\\infty$ and then doing MAP decoding (i.e. instead of thresholding each marginal, you take the configuration of labels that maximizes the BP approximation to the Gibbs measure)?\n\n2. Can you provide some intuition into the architecture of the network g_L? For example what is the function of the average pooling and how it is applied.\n\n3.This is more of a comment: BP is supposed to be more precise on sparse factor graphs. Your factor graph is not sparse due to the term with $\\lambda_b$ coupling all the variables within one bag. Do you think there is a way to modify the Gibbs measure to keep the desired properties but having a sparse factor graph?\n\n4. Can you comment on the convergence of the BP iterations? Did BP converge? did the convergence time change with the size of  the training set? Did you use some trick to make it converge?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well written\nThe proposed algorithm is interesting and novel. \nThe experimental presented experimental evidence appears complete and compelling.\nThe algorithm achieves a good performance compares to other existing methods.", "weaknesses": "The proposed algorithm is slower than other algorithms it is comapred to.", "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": "eEYvpwUf2e", "reviewer": "Reviewer_TNZ1", "summary": "In this paper, the authors propose a method for the problem of Learning from Label Proportions (LLP), where only aggregate level labels are available for groups of instances. The proposed method incorporates both bag-level and instance-level constraints to address the LLP problem. Then, the Belief Propagation (BP) algorithm is utilized to solve the problem. Finally, the authors verify the proposed method for the  LLP Binary Classification problem.", "questions": "1. Why do you introduce the Gibbs distribution in the modeling? The reasons should be detailedly clarified.\n2. Are the instances in each bag all labeled? If yes, then the bag level counts will equal the size of the bag.\n3. Is the size of each bag in this paper equal? What if the sizes of each bag are not equal?\n4. In Table 2, why not report the results of large size (512, 1024, 2048) as other tables do?\n5. According to the results of Tables 1-3, it is weird that the performance of DLLP(published in 2017) is better than that of GenBags(published in 2022) and EasyLLP(published in 2023). Please explain these.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The topic of this paper is interesting and important. Learning from Label Proportions (LLP) is a weak-supervised learning paradigm, which is beneficial for privacy protection.\n2. The proposed method exhibits good performance on large bag sizes.", "weaknesses": "1. The writing of this paper needs great improvement, e.g., the connection between the LLP problem and the parity checks should be clearly elaborated. The intuition behind this should be clarified.\n2. The bag-level and instance-level constraints are commonplace, making the novelty quite limited.\n3. The experiments were only conducted on Binary Classification problems, while the multi-class classification is a more general case.\n4. The formulation of the equations should be carefully checked, e.g., in Eq.(1), according to the definition of $y(S_i)$ (the third row in Section 3), the first term equals 0. Besides, the derivation from Eq.(1) to Eq.(2) should be provided for clear understanding.\n5. The proposed method performs well on large bag sizes, but the authors do not give explanations why this is the case.\n6. According to the results of Tables 4 and 5, the running time of the proposed method is far more than that of DLLP, besides, the running time of other methods is not reported.\n7. According to the results of Tables 9-13, the parameters seem to need very careful fine-tuning, and the sensitivity studies of these parameters are missed.", "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": "89DaUD9Dpf", "reviewer": "Reviewer_XP46", "summary": "This paper studies the setting of learning from label proportions (LLP), where we have access to aggregate labels over bags (i.e., grouped instances). The authors provide an approach that (1) implements belief propagation to assign pseudolabels to similar data points and (2) iteratively trains supervised classifiers with the pseudolabels (and the previous classifiers learned embeddings).", "questions": "* See first point in the weakness section. Are there any particular intuitions as to why DLLP outperforms your method (somewhat consistently) over small bag sizes?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The authors provide a new scheme (based on Ising models and belief propagation) to propagate pseudolabels across datapoints taking into account bag constraints and covariate similarity.\n* They also derive a new architecture and objective during bootstrapping their supervised model on the produced pseudolables. This involves an additional hidden layer that produces soft scores over the bag to maintain correct bag proportions.\n* Good experimental gains over existing LLP baselines with large bag sizes.", "weaknesses": "1.  Lack of explanation/intuition about results. Are there any hypotheses as to why the results of your method are worse in cases with small bag sizes but better in cases with large bag sizes?\n\n\n2. Lack of discussion about work from the field of weak supervision, where there have been similar problems studied in the context of combining weak supervision (labels similar to aggregate labels over bags) and covariate information via clustering [1] and via label propagation [2]. In both cases, a model is trained after pseudolabels are generated (although no iterative refinement is done as these methods start from pretrained representations and supervised models are directly fit on the pseudolabels).\n\n\n3. A few typos that I noted (that don’t overall affect my score):\n* Last line of page 7: “the iteration seem to help improve performance”, should be “iteration seems to help improve performance”\n* “Bag constraints” in section 6.1 shouldn’t be capitalized\n\n[1] Chen, Mayee F., et al. \"Shoring up the foundations: Fusing model embeddings and weak supervision.\" Uncertainty in Artificial Intelligence. PMLR, 2022.\n[2] Pukdee, Rattana, et al. \"Label Propagation with Weak Supervision.\" The Eleventh International Conference on Learning Representations. 2022.", "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": "pzKunYlL2H", "reviewer": "Reviewer_hQ1X", "summary": "This paper proposes an effective and efficient approach to the problem of Learning from Label Proportions. The proposed approach has two main steps. In the first step, it uses Belief\nPropagation to marginalize the Gibbs distribution to obtain pseudo labels. In the second step, it uses the pseudo labels to provide supervision for a learner. The paper conducted experiments to show the usefulness of the proposed approach.", "questions": "The paper should discuss theoretical aspects of the proposed approach. For example, I am interested in the time and space complexity of the proposed approach since the proposed approach has rather complex framework. What are the computational and memory costs of the proposed approach?\n\nThe graph structure has a significant impact on the proposed approach. How do you determine the number of nearest neighbors? Is there any theoretical background to determine the graph structure?\n\nAs shown in Algorithm 1, the proposed approach uses the iterative computations. Does the proposed approach have a theoretical property to converge? How do you determine the number of iterations, R?\n\nAs shown in Table 1 and 2, for UCI and Criteo datasets, the proposed approach is competitive to the previous approaches. On the other hand, the proposed approach does not work well for CIFAE dataset, as shown in Table 3. Please theoretically justify the experimental results. \n\nSince the proposed approach uses a k-NN graph, it needs a high computational time to construct the graph. In Section 6.1, the paper shows the processing time of only the proposed approach. Is the proposed approach more efficient than the previous approaches?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The problem of Learning from Label Proportions could be useful. \n- This paper is well structured and easy to follow.\n- The proposed approach outperforms state-of-the-art approaches.", "weaknesses": "- The proposed approach is complex; a simple framework is desirable. \n- The proposed approach assumes the case of disjoint bags; it cannot handle non-disjoint bags.\n- The paper lacks theoretical aspects of the proposed approach.", "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)