Easy Learning from Label Proportions
Authors: Robert Istvan Busa-Fekete
Heejin Choi
Travis Dick
Claudio Gentile
Andres Munoz medina
Venue: NeurIPS 2023 poster (2023)
Keywords: learning with partial information
unbiased loss
classification
proportion matching
TL;DR: We propose a simple and flexible method for learning with label proportions and investigate applications to widely used learning methods, like ERM and SGD.

Abstract: We consider the problem of Learning from Label Proportions (LLP), a weakly supervised classification setup where instances are grouped into i.i.d. “bags”, and only the frequency of class labels at each bag is available.  Albeit, the objective of the learner is to achieve low task loss at an individual instance level.  Here we propose EASYLLP, a flexible and simple-to-implement debiasing approach based on aggregate labels, which operates on arbitrary loss functions. Our technique allows us to accurately estimate the expected loss of an arbitrary model at an individual level.  We elucidate the differences between our method and standard methods based on label proportion matching, in terms of applicability and optimality conditions. We showcase the flexibility of our approach compared to alternatives by applying our method to popular learning frameworks, like Empirical Risk Minimization (ERM) and Stochastic Gradient Descent (SGD) with provable guarantees on instance level performance.  Finally, we validate our theoretical results on multiple datasets, empirically illustrating the conditions under which our algorithm is expected to perform better or worse than previous LLP approaches

Easy Learning from Label Proportions
Robert Busa-Fekete Google Research musarobi@googee... com
Heejin Choi' Coupang Inc
Travis Dick Google Research tdi tdick@google.c com
hechoo15@coupang.. com
Claudio Gentile Google Research cgentilek@googe com
Andres Munoz Medina
Google Research
ammmedina@goggle.. com
Abstract
We consider the problem of Learning from Label Proportions (LLP), weakly supervised classification setup where instances are grouped into i..dd. "bags", and only the frequency of class labels each bag is available. Albeit, the objective of the learner is to achieve low task loss at an individual instance level. Here we propose EASYLLP, flexible and simple-toimmplemen debiasing approach based on aggregate labels, which operates on arbitrary loss functions. Our tech- nique allows us accurately estimate the expected loss of an arbitrary model an individual level. We elucidate the differences between our method and stan- dard methods based on label proportion matching, terms of applicability and optimality conditions. We showcase the flexibility of our approach compared to alternatives by applying our method to popular learning frameworks, like Empirical Risk Minimization (ERM) and Stochastic Gradient Descent (SGD) with provable guarantees on instance level performance. Finally, we validate our theoretical results multiple datasets, empirically illustrating the conditions under which our algorithm expected to perform better or worse than previous LLP approaches.
Introduction
In traditional supervised learning problems, learner has access a sample labeled examples. This collection of labeled examples is used to fit model - to name a few, decision trees, neural networks, random forests - by minimizing loss over the observed sample. By contrast, the problem of Learning from Label Proportions (LLP), the learner only observes collections of unlabeled feature vectors called bags, together with the proportion of positive examples each bag. The LLP problem is motivated by number of applications where access to individual examples is too expensive or impossible to achieve, or available at aggregate level for privacy-preservee reasons. Examples include e-commerce, fraud detection, medical databases [20], high energy physics prediction (30), medical image analysis remote sensing
66, election
As weakly supervised learning paradigm, LLP traces back to at least motivated there by learning scenarios where access individual examples often not available. paradigmatic example is perhaps a political campaign trying to predict the preference of the electorate. Since voting anonymous, political analyst may be able observe individual votes, yet, they have access to aggregate voting preferences at the district level.
19 22
23
32 and was
The problem has received renewed interest recently (e.g.. 88 17 24
driven by the desire to provide more privacy to user information. For instance the ad conversion reporting
Work done while at Google.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

system proposed by Apple, SKAN, allows an ad tech provider to receive information about the conversions (e.g., purchases) from customers only aggregated across multiple impressions. This aggregation is intended to obfuscate the individual customer's is activity. A similar API has also been proposed by Google Chrome and Android to report aggregate conversion information (e.g., [.) Given the importance of conversion modeling for online advertising, learning how to train a model using only these aggregates has become a crucial task for many data-intensive online businesses.
Research in LLP can be coarsely divided into two types of goals: Learning a bag classifier that correctly predicts label proportions, and learning an individual classifier that can correctly predict instance labels. The former has been the focus of most of the literature in this area. Representative papers include [5] 19] 32] [33]. While training classifiers match label proportions is an obvious heuristic, little work has been done in trying to understand under which conditions these classifiers would be accurate when generating event level predictions. Yu et al. 33 provide guarantees that suggest that, under the absolute loss, predicting label predictions to very high accuracy can result in good predictions at event level. On the other side of this research area, finding good instance level predictor using only label proportions has so fär remained elusive and under-explored in its generality. The solutions introduced so far require either making some assumptions on the data generation process
26
M4
or on the model class 22 Other solutions involve solving complex
combinatorial problems or require that an example belongs to multiple bags [24 25].
In this work we provide two pronged approach towards making LLP on randomly generated bags better theoretical understanding of well-known label proportion
seamless. First, we contribute prediction algorithm. This algorithm simply trains a model whose average prediction on bag is as close as possible to the label proportion in that bag. This straightforward algorithm referenced (either explicitly or implicitly) in multiple past works (e.g., [19 23 2), yet is hardly analyzed theoretically, or even considered as a baseline for experimental comparisons. Here, we show under what conditions this folklore algorithm can produce good event level predictions. Moreover, we show through extensive experimentation that when those conditions are met this algorithm seems to outperform previous baselines tailored to generating event level predictions. On the flip side, when such conditions are not met, we also show that the quality of this algorithm quickly deteriorates as the bag size increases.
more robust and flexible approach to LLP that operates at the instance level is EASYLLP,, a reduction method virtually applicable to any machine learning task. Unlike many algorithmic proposals in this space, the implementation of EASYLLP requires trivial modifications to current machine learning training pipelines. We elucidate the flexibility of our approach by applying it to two widely interesting algorithmic techniques, Empirical Risk Minimization (ERM) and Stochastic Gradient Descent (SGD). Our findings are complemented by an extensive experimental investigation on a diverse suite of benchmark datasets.
Main contributions. The contribution of our paper can be summarized as follows.
1. We provide a theoretical analysis of a popular label proportion matching algorithm, that is suggestive of the conditions under which this algorithm is expected to work in practical scenarios. Despite its relative simplicity, the scope of this analysis is broad and, to the best of our knowledge, original.
2. We provide a general debiasing technique for estimating the expected instance loss (or loss gradient) of an arbitrary model using only label proportions, and thoroughly quantify the variance of this estimator.
3. We provide a reduction of ERM with label proportions to ERM with individual labels, and show that when the learner observes bags of size k, the sample complexity of ERM with label proportions increases only by a factor of k. Likewise, we provide an analysis of SGD using only label proportions and show that for bags of size k its regret increases by only factor of k.
4. We carry out an extensive set of experiments comparing the proportion matching method and EASYLLP to known methods available in the LLP literature. The experiments are designed to encompass diverse combinations of datasets and learning models. We identify general trends in the relative performance of the tested methods when evaluated at the instance level. To the best of our knowledge, in spite of its folklore status, this is the first thorough investigation that involves the proportion matching algorithm and its comparison to event

---

level classifiers. We believe the latter is by itself an important contribution on its own, as proportion matching turns out be a strong baseline in a number of cases.
Related work. Interest in LLP traces back to at least [5] 19 22 recent years has become quite voluminous, so we can hardly do justice of it here. In what follows, we comment on and contrast to the references from which we learned about LLP problems.
23 29 32 20 The literature in
In [S] the authors consider a hierarchical model that generates labels according to the given label proportions and proposed an MCMC-based inference scheme which, however, is not scalable to large training sets. [19] shows how standard supervised learning algorithms (like SVM and k-Nearest Neighbors) can be adapted LLP by a reformulation of their objective function via label proportion matching. Yet, no experiments are reported on classification tasks. In [22] the authors propose a theoretically-grout groounddd way of estimating the mean of each class through the sample average of each bag, along with the associated label proportion. The authors make similar assumptions to ours, in that the class-conditional distribution of data is independent of the bags. However, their estimators rely on very strong assumptions, like conditional exponential models, which are not a good fit to nowadays Deep Neural Network (DNN) models. Similar limitations are contained in (20). (33 proposes an top of proportion matching. Yet, this turns out to be restricted to linear models in some feature space. Similar limitations are in the a-SVM method proposed in [22 the non-parallel SVM formulation of (21), and the pinball loss SVM in 28). The original a-SVV formulation was extended to other classifiers; e.g., [15] extends the formulation
adaptation of SVM to the LLP setting through scheme which can be seen calibration
CNNs with generative model whose associated maximum likelihood estimator is computed via Expectation Maximization, which turns out not to be scalable to sizeable DNN architectures.
(29) proposes a method based on k-means to identify clustering of the data which is compatible with the label proportions, but their method suffers from an extremely high computational complexity.
Many of these papers are in fact purely experimental in nature, and their main goal is to adapt the standard supervised learning formulation to LLP formulation as to obtain a bag level predictor.
On the learning theory side. besides the already mentioned 22 20 are the efforts contained in
24 25., the task of learning from multiple unlabeled datasets considered in 16), and the statistical learning agenda pursued in [26] 34 (and references therein from the same authors). In (24 25) the author is essentially restricting to finear-threshold functions and heavily relies on the fact that an example can be part of multiple bags, while we are working with non-overlapping i.i.d. bags and general model classes. In [17 [6] the authors consider problem akin to LLP. Similar to our paper, the authors propose a debiasing procedure via linear transformations. Yet, the way they solve the debiasing problem forces them to impose further restrictions
the bags, like the separation of the class prior distributions across different bags. It is this diversity that allows the authors to construct unbiased estimates and then derive consistency results. On the contrary, the bags proposed in our setup are drawn i..dd from the same prior distribution, a scenario where many of these algorithms work under the assumption that we cannot handeraft diverse bags out of our samples, as the aggregation into bags is done without having access to the class conditional distributions (which [17 16] and related papers heavily rely upon). Moreover, the convergence results to the event level performance are only proven in those papers with specific families of loss function (e.g., proper loss functions). See Section 5 for further in-context discussion.
would fail. Hence,
The work (26] introduced a principled approach to LLP based on a reduction to learning with label noise. As in [17], their basic strategy is to pair bags, and view each pair task of learning with label noise, where label proportions are related to label flipping probabilities. The authors also established generalization error guarantees at the event level, we do here. [34] extend their results to LLP for multiclass classification. From a technical standpoint, these two papers have similar limitations as [6]. Besides, the risk measure they focus is balanced risk rather than classification risk, do here.
we empirically compare EASYLLP to folklore label proportion matching method, to the MeanMap method from 22), and to a label generation approach from [ the latter viewed as representative of recent applications of DNNs to LLP.
In our experiments (Section 7
3

---

2 Setup and Notation
Let X' denote feature (or instance) space and y {0,1) be binary label space. We assume the existence of a joint distribution 'D on A' x y, and let p = (x(x)))=(( = 1) denote the probability of drawing a sample (a,y) E X x y from D with label y 1. For natural number n, let [n] {i E N: i n).
labeled bag of size l is sample B {I1,..., zkk together with the associated label proportion aBB) = : وド= Vj. where (#1, y1)...., (Ix: yie are drawn i.d. according to D. We assume the learner has access to collection S = {(B,, a.), i E [n]] of n labeled bags of size k, where 1j=1 Vij is the label proportion of the i-th bag, and all the involved samples (mzy, wiy) drawn i.i.d. from D. In words, the learner receives information about the nk labels Yiy of the nk instances 23y only in the aggregate form determined by the n label proportions a associated with the n labeled bags (B, a;) in collection S. Notice, however, that the instances Zij are individually observed.
B; { E [k]), a (BB)
Given a hypothesis set H of functions h mapping X' to a prediction space V. and loss function e: E: 5 x y - RR+ the learner receives collection S, and tries to find hypothesis h H with the smallest population loss (or risk) (hh = ((z,a)=D(((h(
y)] with high probability over the random draw of S. When clear from the surrounding context, we will omit subscripts like "(x, y) ~ D or "D" from probabilities and expectations.
We shall consider two broadly used learning methods for solving the above learning problem, Empirical Risk Minimization (ERM, Section 5 or regularized versions thereof, and Stochastic Gradient Descent (SGD, Section 6). this latter context, we will consider a parameter space W and consider a learner that tries to optimize a loss f: W x X' ) + R iteratively over collection of bags. Before that, we find it instructive to delve into the theoretical properties of an approach to LLP which is by now belonging to folklore.
3 Proportion Matching Algorithm
We now introduce simple and very well known algorithm for learning from label proportions. Yu et al. 33 refers to this algorithm as Empirical Proportion Risk Minimization but different versions of the algorithm are discussed in the LLP literature without clear reference to its origin.
Definition 3.1. Given a loss function é R x R + RR. a hypothesis set of functions H. and a collection S = {(B,,,:) E [n]} of labeled bags of size k the PROPMATCH algorithm minimizes the empirical proportion matching loss, i.e. it solves the following optimization problem
min NEW
(1)
That is, the PROPMATCH algorithm creates bag level prediction by simply averaging the predictions of model the bag's individual examples. Yu et al. (33) prove a uniform convergence guarantee implying that, given enough data, the minimizer of the empirical proportion matching loss is an approximate minimizer of the population level proportion matching loss:
min E R B.a
Mxx),
ZEB
In general, the minimizer of the population level proportion matching loss may not produce accurate event-level predictions. However, Yu et al. (3) small population level proportion matching loss also leads to a classifier with small population level event loss.
further show that when É is the absolute loss, achieving
We now strengthen those results and show that under some general conditions on the loss function, and if the function class H. expressive enough, minimizing the population level proportion matching loss is equivalent to minimizing the population level event loss
2 multiclass extension of all our results is also possible see Appendix
Due to lack of space, all proofs are given in the appendix.

---

Theorem 3.2. Assume H is such that the function h² + P(y is
in H. Let E : R
be such that, for any random variable Z, 9 = B| the unique solution of min,ez Exl((r,22 Then, he is minimizer of (2) Moreover, every other minimizer h satisfies (x)(
Corollary 3.3. Let H satisfy the conditions of Theorem
3.2 Then he as defined above is the unique minimizer for the proportion matching loss when E is the square loss or the binary cross-entropy loss.
The above corollary provides with conditions for the proportion matching loss minimizer to also minimize the event level loss. It is natural to ask ourselves, what the hehavior of the proportion matching loss would be when those conditions problem. However, the following example shows that if the model class 7 is not expressive enough, then using the proportion matching loss can in fact lead to arbitrarily bad event level predictor.
violated. To knowledge, this remains an open
Let X' I and y {0, 13. We define a latent variable 77 uniformly distributed in {- {-1.1}. 1]. We gen- erate a distribution D over pairs (x, y) as follows: first sample latent variable 17. then sample x accord- ing to the Gaussian distribution N N((1,))) T), where R2x2 is the identity matrix. Finally, sample et y such that Pyy = 1) = क if = -1 and सम Using SGD, we attempt to fit a logistic regression model parametrized by w E R²² where Pu (y = 1|z) I+e Crucially the hypothesis class used to model D does not include the true con- ditional probability distribution. For the experiment we generate 100000 examples from distribution D, and group them randomly into bags of size 500. Fig- ure | shows the effect of training a model using proportion matching loss vs, event level loss. Note that even though the empirical proportion matching loss is decreasing, the test loss (on events) increases.
8.2
um Harch
Dasy LLJ Thiiig Lem
8.7
Eiiit lur cast Eay Lur bed Lou
5.9
Figure 1: Left: Training loss for different learning approaches. PROPMATCH (using (I). EASYLLP (using (3, Section D. and event level using regular cross-entropy loss. Right: Test loss using event level labels to measure cross-entropy loss for all methods. Notice how the PROPMATCH training loss decreases but the test loss continues to increase. EASYLLPP tracks the event level loss suggested by the- ory.
if 1
To summarize, we have shown that PROPMATCH can, for the most popular classification and regression losses and under some assumptions on H. recover very good instance level classifier. Nonetheless, when those assumptions are violated the performance of PROPMATCH can drastically degrade. We believe these observations pave the way for new exciting research in fully understanding this simple algorithm.
4 Easy LLP
Based on the results of the previous section, interested in defining robust, theoretically founded algorithm for learning from label proportions. We now introduce the main tool for our approach.
Definition 4.1. Let X' y - Rd be any (measurable) function, for some output dimension 2 1. Let also p E'y] be the probability of observing a positive label. We define g: X' [0, 1] Rd the soft-label corrected function associated with g. as
0(2, a) = (K(a= p) + p(( 1) + (kip a) + (1 (1-p))g(22) p)) 0)
The main property of J. which is relevant LLP, is that it is as unbiased estimator of ((xy))> (1xx, v)], as next show.
Proposition 4.2. Given a sample (c1,8),.... (Ix. Wb) drawn i..d according to D. let (B, a) be
the corresponding labeled bag of size k. for some k 2 1. Let g: X x y > Rd be any (measurable) function, for some oulput dimension d 2 1, and ğ: X x [0, 1] + Rd be its associated soft-label corrected function. Then for every element xjj E B we have
E (8,a)
19(,, = E (2.8)~
[g(2, y)]
For empirical risk minimization (ERM), we shall apply Proposition 4.2 with the function g that computes the per-example loss of given model, so that we obtain unbiased estimates of the model's
5

---

population level loss. Similarly, for gradient- gradient-based optimization, we take g to be the function that computes the per-example gradient of the loss w.r.t. the model parameters so that we obtain an unbiased gradient estimate. More details of our application of Proposition 4.2 are given at the end of this section.
Proposition 4.2 shows that we can easily obtain an unbiased estimate of the expectation of any function g by applying simple linear transformation the output of g(z, y). for y = We would like to highlight the importance of this simple proposition. Whereas there has been lot of research in LLP, our knowledge this is the first expression that shows that one can recover an unbiased estimate of an arbitrary function using only information from label proportions.
While the above result provides us with a straightforward way to estimate the expectation of function (which can for instance be specialized to a loss function), note that the variance of increases as the number of elements in each bag grows. Indeed, since all terms in the definition of have factor of k; we might expect the variance of the estimator to grow as k.²,, which could be prohibitively large even for moderate values of k. Notice however that because
=j=1% Vjj and each yj ~ Bernoullipp). we expect by standard concentration arguments that k(a - p) E O(Vk) which should imply that the variance scales like k. The following theorem shows that indeed, the variance of these estimates is of order & and not k In addition, since j(z,, a) unbiased for all j E [k]. is Y/2 Σÿ= H(z, a). The same theorem also shows that the variance of the latter estimator is always smaller than the variance of the former. That is, using all k samples in a bag is always better (in terms of variance) than using any single sample.
Σ Ej=1
Theorem 4.3. Let g: X x 3' + Rd be such that supz.y 11g(2, w)1l S M, and denote by I its associated soft labeled corrected function. Also, set for brevity go g(ar, 0) and 91 g(x, 1) and, for each j E [k), .3 = ā(æ,,a). Then, for any size & 2 1 and any j E [Ai].
1116,1121 = [ u. 1P + (k- 1)p(1 p) E |190 91 113
E
Σ
9
S
(4)
Moreover, there exists a universal constant such that
pa|LElo0 - 91l [|
E
91
S C + kp(1 -1--p)))
where p P(eey))D(y = 1).
The bound in the above theorem confirms our intuition. Moreover, it shows that the variance grows slower for datasets where p is close or This intuitively clear, for very skewed datasets, we expect label proportions to provide better description of the true labels. In the extreme cases where p 0 or p = LLP becomes equivalent learning from individual examples.
The results of this section have demonstrated that for any function g. one can obtain an estimator of its expectation using only label proportions. More importantly the variance of this estimator only scales linearly with the bag size.
Note about knowledge of population level positive rate. At this point the reader is aware that the definition of the soft label corrected function requires knowledge of the population level positive rate p. While the exact value of p unknown, one can easily estimate it from the label proportions itself. Indeed, using the fact that the generated bags are i.i.d. it is easy to see that P n >E 0g nk E,, Bij is a very good estimator for p.
We now have all elements to introduce the EASYLLP framework for learning from label proportions. The framework consists of specializing the function g for particular learning tasks. Two notable instantiations of EASYLLP which we will analyze in further sections are ERM and stochastic gradient descent (SGD). For ERM, given a hypothesis h and loss function, we let g)) = ((h(x), y) and the corresponding soft label corrected loss E(h(z). ax) Gk (2r, a). To provide regret guarantees using SGD over bags in parameter space W and loss function
EASYLLP.

---

E: W x X' x 3 - R. we use EASYLLP to estimate the gradient of the loss function with respect to a parameter w E W by letting Iw (z. y) Vw 2, y) and its corresponding soft label corrected function Ow (z, ax) = V((w, x.)).
ERM with Label Proportions
Given hypothesis space H. let E be loss function defined in Section 2 Given collection of bags S = (B,, ax), i E [n]}} of size k, our learning algorithm simply finds E H that minimizes the empirical risk constructed via the soft label corrected loss from Eq. (3):
((h(rig),
(5)
The main advantage of our algorithm lies in its simplicity and generality. Indeed, our algorithm can be used for any loss function and any hypothesis set. This is in stark contrast, e.g., to the works of [22 20). whose framework is only applicable to the logistic loss and (generalized) linear models. From practical standpoint, our approach can also leverage existing learning infrastructures, as the only thing that needs to be specified a different loss function - which in frameworks like Tensorflow, JAX and PyTorch requires only minimal coding. This differs from other approaches to assigning surrogate labels which may require solving combinatorial optimization problems (or relaxations thereof) like, e.g.. [32 []
The following theorem provides learning guarantees for minimizing the above empirical loss. Our guarantees are given in terms of the well-known Rademacher complexity of class of functions.
Definition 5.1. Let be an arbitrary input space and let G C {g: + R } be a collection of functions over Z. Let DD be a distribution over Z and S = {z 7m be an i.i.d. sample. The Rademacher complexity of G' is given by (G) = 1 Es,o (supgeo Ei=1 {(1))r)) o = (oI,...,0,) E 1)" is uniformly distributed.
where
((B,, E [n]} be collection of bags of size k Let supg.y () B, and C² 2k 1). Then the following bound holds uniformly for all h E H with probability at least 1 8:
Theorem 5.2. Let 8
((h)
1
Σ
((h(x:s), an) ch (P1 Ren (H,,0)
4B + 4B
k llog(2/8)
nk 6,3
2n
where H = fo + ((h(z), he h H. and H = fI ( ((h(z),)) h E H.).
Corollary 5.3. With the notation of the previous theorem, let h denote the minimizer of 5 Then with probability at least 1 5 over the sampling process we have
((h) min L(h) + (c# hEh
+ Rea (H.
4B n
4BV
k llg((2/5)
2n
Comparison to event level learning. We can now compare the bound from Theorem 5.2 to standard learning bounds for instance level learning like that of [18] Assuming we had access to a labeled i.i.d. sample (Zzja of size kn. Theorem 3.3 in (18) ensures that with probability least 1 - the following bounds holds for all E H:
((h) - 1
Σ nk: 1
(1(11,5,16))) < 29 (HH)) + BV
(2g(2/5)
(6)
2nh:
where HA = ()x, - {(h(z),)) y) h E H}. Note that under the weak assumption that the Rademacher complexities Rem (H, (H)
). r 1), are of the same order as (Hle, the main
*Our results can easily be extended the case where bags have different sizes, provided the items are still i..dd The equal size assumption made here mainly for notational convenience. If the bag sizes are constant with the number of bags then a rate of the form i/vn can still be obtained. On the contrary, if the bag sizes scale with n, the actual rate will depend on the interplay between the bag sizes and n itself.
7

---

difference between the bound in Theorem 5.2 and 6 is simply an extra factor C E Ö(vk) in the complexity term and factor k multiplying the confidence term. That is, we achieve similar guarantees to event level learning by increasing the sample size by factor of roughly k.
It is worth stressing the difference in flavor of the consistency result contained in Theorem 5.2 above and those in [17 [6]. For instance, in [16] (even with m = 2 bags) the consistency limit has to be interpreted "as the bag size Mar = ni + r22 goes infinity".. In our case, the bag size k has remain constant, and it is the number of bags n that goes to infinity. This further strengthens our claim that the stream of literature that those papers are representative of are by no means subsuming our results. Moreover, unlike our paper, all results in these previous works, as presented, make assumptions about the loss function (e.g., square loss or cross entropy for [16]. saurin--bssed losses for (17].. The fact that we make no assumptions allows us to apply our debiasing procedure to any function g(x, y) of two variables, hence we can debias, e.g., also the gradient of a loss function, enabling the principled usage of stochastic gradient descent procedures with only label proportion information. This is illustrated in the next section.
SGD with Label Proportions
We now focus on understanding the effect of label proportions on another very popular learning algorithm: stochastic gradient descent (SGD).
Proposition 4.2 delivers an unbiased estimate of the gradient which can be naturally plugged into any SGD algorithm (e.g.. (27)), and one would hope for upper bound on the excess risk if the learning task at hand leads to a convex optimization problem. The difficulty is that, even if each gradient in given bag is individually unbiased, the gradients are correlated since they depend on the label proportion computed on the bag. A simple way around is to pick a single item uniformly at random from the bag to update the model parameters. This is slight departure from what considered for ERM, but it both makes our SGD analysis easier and does not affect asymptotic performance.
In order to devise an SGD algorithm that can handle bagged data, first note that the debiasing technique introduced in Proposition 4.2 is very general and it applies to any measurable function, including the gradient of any loss function. Let denote the gradient of the loss on example (z, v) by (w, y) where w is the parameter vector of the model and let its soft-label corrected version be Gw. We study version of projected SGD that picks one example per bag and uses the soft-label corrected gradient estimates (pseudocode is given in in Algorithm[]] in the Appendix). The excess risk of this algorithm depends the squared norm of the debiased gradients, which is at most k times larger than the variance of the original instance-level gradient based on Theorem 4.3 This observation results in the following risk bound.
Theorem 6.1. Suppose that F(w) = Bll (z, y)] is convex, E[llsw. (x,, x) S G2 for all & E [n]. and sup w. w'ew |ww- w'll S D. Consider Algorithm ! run with step size = 1/Vk.b Then for any n. > 1 we have
2 + +lo(())
B[F((..) F(w*)] S Vic VD² + 502)
Vn
This theorem quantifies the deterioration in the excess of the risk in terms of bag size when the algorithm is applied with LLP data. Recall that the error of SGD with kn individually labeled samples decreases like O Vkn). Compared with the above bound, and similar to the ERM case, the regret bound increases by a factor of k.
The most predominant learning frameworks used today fit deep models to data using SGD- methods. Even though these problems are typically non-convex, we remark that Proposition 4.2 guarantees that the expected gradient steps of Algorithm I Jare equal to the expected steps of SGD using an instance-level loss. Moreover, Theorem 4.3 guarantees that the variance of the gradient estimates used by Algorithm not much larger than that of the instance-level case. In particular, it follows that whenever SGD an effective algorithm for learning from instance-level data, Algorithm should also be effective at learning from LLP data, provided that we have enough data to overcome the increased variance. This thoroughly demonstrated in the next section. Finally, the only required modifications any gradient-based training infrastructure to use EASYLLP are replace the original labels yik by label proportions and to implement the soft-label corrected loss. Taken together, these properties of EASYLLP make it especially well suited modern machine learning pipelines.
8

---

7 Experiments
In this section we empirically evaluate EASYLLP, PROPMATCH, and two baseline methods to characterize how their performance depends on the bag size for a range of different learning tasks and underlying learning models.
LLP Methods. We evaluate EASYLLP, PROPMATCH, and two baselines 5 The first baseline is MEANMAP (22), which is a method specialized for learning linear logistic regression models from label proportions. We also compare against the method described in Section 3.2 of [8). which we denote by DA. The DA method computes a loss for each bag by creating synthetic labels for the examples that optimize a combination of the model's loss the synthetic labels, and divergence between the label proportion of the synthetic labels and the bag's 'g label proportion. The DA method has an additional hyperparemeter, a, which controls the weights these two objectives. Full details of our DA implementation are in Appendix A.3
Datasets. We carry out experiments four (binary classification) datasets: Binarized versions of MNIST [33 and CIFAR-10 10 [12], as well as the Higgs [3] and UCI adult datasets [T]. The labels in MNIST are replaced by labels indicating whether the digit is even or odd, and the CIFAR-10 labels are replaced by whether the original class is an animal or machine, The MNIST images are resized have shape 32 32 x to match CIFAR- 10. For both image datasets, we normalize the images to have fg norm equal to one. No preprocessing is performed on the Higgs dataset. Finally, on UCI Adult, we rescale numerical features the range [0, 1] and one-hot encode categorical features.
Models. We evaluate each LLP method on every dataset using linear model. Additionally, for the image datasets we also evaluate using small ConvNet, large ConvNet, and Resnet-11 (9. On Higgs we also use the DNN proposed by (3. which has 4 hidden layers, each with 300 units. Finally, on UCI Adult, we also use a NN with one hidden layer. Since the MEANMAP baseline is only applicable to learning linear models, we do not include it in the neural network experiments. Full details of the architectures are provided in Appendix A.2
A.2
Experimental Setup. For each combination of LLP method, dataset, model, and bag size, train the model 10 times with different seeds and report the average test accuracy. To generate the label proportion data, on each run we shuffle the training data, partition it into consecutive bags of the desired size, and replace the original labels with label proportions computed from the bags. To tune the learning rate for each method, we report the highest accuracy achieved for learning rates in (0. 00.00001, 0.0001, 0.0005, 0.001, 0.005, 0.01, 0.05). For DA, we tune the learning rate and a using grid search with the same learning rates and a E (0.0, 0.0001, 0.001, 0.01, 0.1, 0.5). Note that DA is sensitive to the choice of a, and it is unclear how to tune a without access to event-level data. In all cases we use the Adam [10] optimizer, binary crossentropy loss, minibatches of size 512, and 20 training passes through the data. Finally, for the two image datasets, we decay the learning rate after 40%, 60%, 80%, and 90% of the training passes by factors 10, 100, 1000, and 5000, respectively.
Results. Figure 2 depicts the accuracy achieved by each method on selection of datasets and models for a range of bag sizes. The selected dataset and model combinations are representative of the full set of experimental results, which are included in Appendix A.5 Across all datasets, either EASYLLP or PROPMATCH ATCH achieves the highest test accuracy for large bag sizes. In agreement with our theory, the performance of EASYLLP decreases predictably with the bag size (due to the increased variance of gradient estimates). On the other hand, we find that DA often performs very well for small bag sizes, but accuracy drops rapidly at dataset-dependent threshold. PROPMATCH is a competitive baseline, specifically when the underlying learning model is well specified for the task, which is in line with our finding in Section 3 For instance, when using the Resnet-1 I model, PROPMATCH has a higher performance than EASYLLP on both MNIST and CIFAR-10. A partial explanation is due to Theorem regression become overconfident on their predictions. However, our theory suggests that the variance of the gradient increases proportional to [[g(,, 0) g(z, 1)ll which rapidly becomes unbounded as
Indeed, it is well known that models trained under logistic
'Due to the differences in problem setup between our work and that of other papers, like 17 16 it is unclear how a fair experimental comparison to those papers should be performed. For this very reason, we have deliberately avoided to experimentally compare the algorithms in those papers.

---

0.4
UCC AdvE
0.0
Hige DNN
CHAR: 1D Go Wis DWAT
CH Astinaa Machaae Resret.
044
022
400
400
Destp
0.72
475
6.5
TayyLiP
6:5
Loy
0.00
0.60
Becyl Free
649
SayyL MSE
21
27
27
37
27
Figure 2: Average test accuracy for each LLP method on selected datasets and models. Error bars show one standard error in the mean.
the model becomes more confident. To test this hypothesis, we trained a model using double-sided hinge loss, labeled "EASYLLP DHL." (details in Appendix (A). This loss induces small variance term in Theorem 4.3 and indeed we see that this partially closes the gap to PROPMATCH. On the other hand, PROPMATCH's performance degrades more rapidly than EASYLLP's the bag size increases in the presence of model mis-specification or higher noise in the data (first three plots in Figure 2
Loss tracking. Another strength of EASYLLP is that the loss estimates computed during training are unbiased estimates the true training loss. In comparison, the losses minimized by all other methods we consider do not have clear connections to the true training loss and it is unclear how to monitor training performance. In Appendix A.6 we demonstrate this empirically.
8 Conclusions and Limitations
We have studied the problem of learning from label proportions in the case where bags are drawn ii.d. We have introduced EASYLLP, novel and flexible approach to LLP for classification that is widely applicable and has well-developed theory. In particular, we have shown how to use EASYLLP to estimate the expected value of any function of (z,, y) pairs from labeled data, and applied these results to proving ERM sample complexity guarantees and convergence guarantees for SGD. In both cases, have shown that the LLP performance of EASYLLP is only factor k worse than when learning from event-level data. We have also elucidated important theoretical properties of the folklore PROPMATCH algorithm which are suggestive of the practical scenarios where it is advisable to make use of it. Finally, we have carried out an extensive empirical evaluation of EASYLLP PROPMATCH, and two baseline methods diverse tasks and learning models, and identified relative performance trends.
The results in this work are limited to the special case of LLP where the examples in each bag drawn i.d.d from an underlying distribution. While this is a common and important special case, in future work would like extend our results to handle cases where the bags need not be i.i.d. Similarly, we hope to study the theoretical properties of EASYLLP more fully in the multiclass case, and have complete characterization of when PROPMATCH is consistent. We also believe that it may be possible to further decrease the variance of EASYLLP estimates by replacing the label marginal p in 3 with bag-specific predictions. Finally, while the LLP framework provides an intuitive form of privacy protection, we would like to explore connections with differential privacy where, for example, each bag's label proportion computed by differentially private mechanism.
References
[1] Private aggregation API, 2022.
URL
https://devvlloper. chrome. com.
[2] E. M. Ardehaly, and A. Culotta. Co-training for demograpiieSeaassiiaatiin using deep learning from label proportions. In 2017 IEEE International Conference Duta Mining Workshops, pages 1017-1024, 2017.
[3] Pierre Baldi, Peter Sadowski, and Daniel Whiteson. Searching for Exotic Particles in High- Energy Physics with Deep Learning. Nature Commun., 5:4308, 2014. doi: 10. 1038/ nc0mms5308.
10

---

[4] G. Bortsova, F. Dubost, S. Orting, I. Katramados, L. Hogeweg, L. Thomsen, M. Wille, and M. de Bruijne. Deep learning from label proportions for emphysema quantification. In Medical Image Computing and Computer Assisted Intervention MICCAI 2018, pages 768-776, 2018. 8.
[5] N. de Freitas and H. Kuck. Learning about individuals from group statísties. In Proceedings of the 21 Conference in Uncertainty in Artificial Intelligence (UAI 2005), pages 332-339, 2005.
[6] L.M. Dery, B. Nachman, F. Rubbo, and A. Schwartzman. Weakly supervised classification for high energy physics. Journal of Physics: Conference Series, 1085:042006, 2018.
[7] Y. Ding, Y. Li, and W. Yu. Learning from label proportions for sar image classification. EURASIP Journal on Advances in Signal Processing, 2017.
[8] Gabriel Dulac-Arnold, Neil Zeghidour, Marco Cuturi, Lucas Beyer, and Jean-Philipee Philippe Vert. Deep multi-class learning from label proportions. arXiv preprint 1rXiv:1905.12000 2019.
[9] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In CVPR, 2016.
[10] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- tional Conference on Learning Representations (ICLR), 2015.
[11] R. Kohavi and B. Becker. UCI adult data set. UCI Machine Learning Repository, 1996.
[12] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
[13] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.lecum wwwwe..co//e./////eeeeee
2, 2010.
[14] Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes, volume 23. Springer Science & Business Media, 1991.
[15] F. Li and G. Taylor. Alter-enn: to ice-water classification. In NIPS workshop on Learning and privacy with incomplete data and weak supervision, 2015.
An approach to learning from label proportions with application
[16] Nan Lu, Shida Lei, Gang Niu, Issei Sato, and Masashi Sugiyama. Binary classification from multiple unlabeled datasets via surrogate set classification. In Proceedings of the 38th International Conference on Machine Learning, pages 71 7134-7144, 2021.
[17] Niu G. Menon A. K. Lu, and M. Sugiyama. the minimal supervision for training any binary classifier from only unlabeled data. In Proc. ICLR, 2019, 2019.
[18] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[19] D. Musicant, J.M. Christensen, and J.F. Olson. Supervised learning by training aggregate outputs. In Proceedings of the 7th IEEE International Conference on Data Mining (ICDM 2007), 2007.
[20] G. Patrini, R. Nock, P. Rivera, and Caetano. (Almost) no label no ery. In Proc. NIPS, 2014.
[21] Z. Qi, B. Wang, F. Meng, and L. Niu. Learning with label proportions via npsvm. JEEE Transactions Cybernetics, 47(10):3293 2017.
[22] Novi Quadrianto, Alexander J. Smola, Tibério Caetano, and Quoe V. Le. Estimating labels from label proportions. In ICML, volume 307 of ACM International Conference Proceeding Series, pages 776-783. ACM, 2008
[23] S. Rueping. SVM classifier estimation from group probabilities. In ICML, Proceedings of the 27th International Conference Machine Learning, pages 911-918, 2010
[24] Rishi Saket. Learnability of linear thresholds from label proportions. Advances in Neural Information Processing Systems, volume 34, pages 6555-6566. Curran Associates, Inc., 2021.

---

[25] Rishi Saket. Algorithms and hardness for learning linear thresholds from label proportions. In Proc. NeurlPS'22, 2022.
[26] C. Scott and J. Zhang. Learning from label proportions: mutual contamination framework. In Advances in Neural Information Processing Systems 33; Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, 2020.
[27] Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, volume 28 of JMLR Workshop and Conference Proceedings, pages 71-79. JMLR.org, 2013.
[28] Y. Shi, L. Cui, Z. Chen, and Z. Qi. Learning from label proportions with pinball loss. Interna- tional Journal of Machine Learning and Cybernerics, 10(1):187-208) 2019.
[29] Marco Stolpe and Katharina Morik. Learning from label proportions by optimizing cluster model selection. Machine Learning and Knowledge Discovery in Databases, pages 349-364. Springer Berlin Heidelberg, 2011.
[30] T. Sun, D. Sheldon, and B. O'Connor. A probabilistic approach for learning with label proportions applied to the us presidential election. IEEE International Conference on Data Mining (ICDM), pages 445 454, 2017.
[31] Kuen-Han Tsai and Hsuan-Tien Lin. Learning from label proportions with consistency regular- ization. Asian Conference on Machine Learning, 2020.
[32] F. Yu, D. Liu, S. Kumar, T Jebara, and S.F. Chang, a-svm for learning with label proportions. In ICML, Proceedings of the 30th International Conference Machine Learning, pages 504-512, 2013.
[33] Felix X. Yu, Krzysztof Choromanski, Sanjiv Kumar, Tony Jebara, and Shih-Fu Chang. On learning from label proportions, 2015.
[34] J. Zhang, Y. Wang, and C. Scott. Learning from label proportions by learning with label noise. In Proc. NeurlPS222 22, 2022.
12


Reviews:
[{"review_id": "jOe3TCwCCZ", "reviewer": "Reviewer_xq8A", "summary": "The authors start by providing a theoretical analysis of the proportion matching algorithm, a standard algorithm from the literature that simply minimizes the loss over the average instance-level predictions. ", "questions": "- Could you please say more regarding the sentence starting line 166? While the objective being approximation by equation (1) is clear to me, I'm not clear own what it means for equation (1) to \"correctly approximate\" it.\n\n- In Figure 1, left plot, why does the prop matching loss start out much lower compared to other methods?\n\n- Could you please elaborate on the statement of Theorem 3.2? In particular, I've been trying to conclude how strong of an assumption it is that the minimizer of the expected loss the average of $Z$ (I do believe it is very strong, and seldom holds in any realistic setting) \n\n- In definition 4.1:\n  - Is $p$ as defined in the notation section or Theorem 3.2?\n  - I find the use of $\\alpha$ here confusing, as my first instinct was to think of it as a label proportion, but in the notation section you only define $\\alpha$ as a function of a bag. I then noticed that it is any real-valued parameter in $\\[0,1\\]$.\n  - Why does this definition make sense? I interpret this as somehow correcting the bias introduced by using bags instead of instances. If that is true, why does this correction term make sense?\n  - I think this definition requires some notion of distribution due to the presence of $p$?\n\n- In proposition 4.2:\n  - the notation does not make it clear how $x_j$ is related to $\\mathcal{B}$. I think something along the lines of $\\mathbb{E}_{(x_j, \\alpha) \\sim (\\mathcal{B}, \\alpha)}$ would perhaps better convey your intent? But then I'm confused again, because somehow $\\tilde{g}$ is a function of an individual instance and $\\alpha$? But $\\alpha$ is a function of the entire bag?\n  - Am I correct in reading the equations as saying that the soft-label corrected function averaged over all bags and proportions is simply equal to $g$ averaged over the instance-level data distribution? If so, then it is my opinion that this needs be framed and discussed since, from what I understand, your entire approach hinges upon this result, and it is by no means easy to see.\n\n- I'm very confused by Equation 5,", "limitations": "Adequately addressed ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I find the way the authors approach to the problem of learning from label proportions, and the goal they set out to achieve to be very worthwhile. I also believe the theoretical results therein might of interest to the community. I did, however, struggle at times in managing to follow the paper. Therefore, in my opinion, the authors really need to spend some effort polishing and refining the exposition to make it accessible to the broader community.", "weaknesses": "- My main gripe with the paper is that I would've liked to see more discussion, or intuition following each Theorem, corollary or proposition. For instance, I really would've liked the authors to spend some time discussing the assumption upon which Theorem 3.2 hinges, and if such an assumption is expected to hold in practice (although I do appreciate them giving an example for when it fails due to the model class not containing the true conditional distribution)\n\n- Empirical evaluation seems to suggest improvement only with large bag sizes (2^7), and on some dataset not at all, compared to the baselines.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for pointing out a number of places where further discussion and intuition would improve the presentation, and we will add additional discussion to the paper.\n\n> “Empirical evaluation seems to suggest improvement only with large bag sizes…”\n\nYes, we agree that EasyLLP only sees empirical improvements for large bag sizes (and sometimes we do not outperform PropMatch at all). However, given that the LLP problem becomes more difficult as the bag size grows, we expect differences between methods to become more pronounced at larger bag sizes. In the complete set of experiments in appendix section A.5, EasyLLP is the only method that is consistently competitive with other methods at every bag size (e.g., in Figure 4 we see that PropMatch and DA have relatively poor performance even at bag size $k = 8$ for the two ConvNet models). We also know that there are cases (e.g., the synthetic example from Section 3) where PropMatch converges to a high loss model and will not improve even with access to more data.\n\n> “Could you please say more regarding the sentence starting line 166…”\n\nWe mean that if you find a classifier that minimizes the empirical proportion matching loss (Equation 1), then as long as you have enough data, it will also approximately minimize the population level loss (Equation 2). We will clarify the language.\n\n> “In Figure 1, left plot…”\n\nUnlike EasyLLP, the proportion matching loss has a different meaning (i.e., it is a measure of how close the model’s average prediction on a bag is to the bag’s label proportion). On the other hand, EasyLLP is an estimate of the *event* training loss (not averaged over the bag), so we should expect the EasyLLP training loss to track the event training loss, but for the proportion matching loss to be somewhat unrelated. This behavior is indeed what we observe in Figure 1. \n\n> “Could you please elaborate on the statement of Theorem 3.2?”\n\n* Theorem 3.2 has two key assumptions: 1. The function $h^* : x \\mapsto P(y=1\\mid x)$ is an element of the hypothesis class $\\mathcal{H}$ (realizability assumption) and 2. The loss function $\\ell$ has the property that for any random variable $Z$, $E[Z]$ minimizes the function $\\rho \\mapsto E_Z[\\ell(\\rho, Z)]$.\n\n* The assumption about the loss is relatively mild, and in Corollary 3.2 (Line 181) we show that this holds for two commonly used losses: the binary cross-entropy and the squared losses.\n\n> **Questions about Definition 4.1:**\n\n> “Is $p$ as defined in the notation section or Theorem 3.2?”\n\n$p$ is as defined in the notation section, which is the marginal probability that $y = 1$. We will change the symbol used in Theorem 3.2 to avoid the conflict.\n\n> “I find the use of $\\alpha$ here confusing…”\n\nThe soft-label corrected function takes as input a feature vector $x$ and a label proportion $\\alpha$. The intended interpretation is that $x$ will be a feature vector from a bag $B$ of examples, and alpha will be the label proportion (which is a random variable) for that bag. We have somehow overloaded the notation by viewing $\\alpha$ as both a random variable (notation section) and its value (Def. 4.1). \n\n> “I think this definition requires some notion of distribution…”\n\nYou are right, this definition depends on the value $p$, which is the marginal probability that $y = 1$ for the underlying data distribution. We will clarify this.\n\n> “Why does this definition make sense?”\n\nThe soft-label corrected function $\\tilde g$ is defined this way so that the subsequent Proposition 4.2 (unbiasedness) holds.\n\n\n> **Questions about Proposition 4.2**\n\n> “The notation does not make clear how $x_j$ is related to $B$”\n\nIn the proposition there is a sample $(x_1, y_1), \\dots, (x_k, y_k)$ drawn i.i.d. from the data distribution. Bag $B = (x_1, \\dots, x_k)$ contains the feature vectors, and $\\alpha = \\frac{1}{k} \\sum_{i=1}^k y_i$ is the proportion of the labels in the bag that are positive. The claim is that if we fix index $j \\in [1, \\ldots, k]\\ $ and consider the $j$-th element $x_j$ in the bag, the expected value of $\\tilde g(x_j, \\alpha)$ (the expectation being w.r.t. the random draw of the labeled bag $(B,\\alpha)$ or, equivalently, w.r.t.  the random sample $(x_1, y_1), \\dots, (x_k, y_k)$) is equal to the expected value of $g(x,y)$, where the expectation is w.r.t. a fresh sample $(x,y)$ from the data distribution.\n\n> “But then I’m confused again because somehow $\\tilde g$ is a function of an individual instance and $\\alpha$?”\n\nYes, $\\tilde g$ is a function of one feature vector $x_j$ from the bag, and the label proportion $\\alpha$ of the bag. So, in a sense, $\\tilde g$ is a function of the entire sample $(x_1,y_1), \\ldots, (x_k,y_k)$ (via $x_j$ and $\\alpha$).\n\n> Am I correct in reading the equations as saying…”\n\n* Yes, your interpretation is essentially correct. For any data distribution $D$ over $(x,y)$ pairs, there is a corresponding distribution over bags with label proportions (i.e., $B = (x_1, …, x_k)$ and $\\alpha$). Proposition 4.2 shows that it is possible to estimate the expected value of $g$ on the distribution $D$ given sample access to the bag and proportion distribution by using the soft-label corrected function. We will add more discussion to the paper to better elucidate the correct interpretation.\n\n* The paragraph on lines 252-260 was meant to outline how the soft-label corrected loss is applied in learning contexts, but we will certainly include some additional discussion following Proposition 4.2, as the reviewer suggests.\n\n> “I’m very confused by Equation 5”\n\n* Normally in empirical risk minimization, we find the classifier $h$ from a hypothesis space $\\mathcal{H}$ that minimizes the loss on the training data. Equation 5 is the estimated training loss on a dataset of bags, where $x_{i j}$ is the $j$-th point of the $i$-th bag, and $\\alpha_i$ is the label proportion for that bag.\n\n* The rest of Sect. 5 studies how much worse it is to minimize Equation 5 compared to the actual training loss.\n"}, {"review_id": "HEqbAXKm8L", "reviewer": "Reviewer_c8Fj", "summary": "The paper presents a debiasing approach called EASYLLP for Learning from Label Proportions (LLP), where only class label frequencies in bags are available. The authors provide theoretical analyses of a label proportion matching algorithm and propose a general debiasing technique for estimating instance loss. Experimental results demonstrate the effectiveness of their approach compared to existing methods in various learning frameworks.", "questions": "Compare with [16] and other works such as On the Minimal Supervision for Training Any Binary Classifier from Only Unlabeled Data (ICLR19), what are the fundamental differences of the current paper?\n\n---------------------\nAfter rebuttal, I am satisfied with the answer on the two key differences, and would like to raise my score.", "limitations": "yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The proposed method in the paper has several advantages. Firstly, it is described as simple and straightforward, making it easy to implement. This aspect can be beneficial for practitioners and researchers looking for an accessible solution to the problem of Learning from Label Proportions (LLP). Additionally, the paper is praised for being well-written, indicating clear and concise explanations of the concepts and methods presented.", "weaknesses": "My main concern is its relationship with previous works, such as [16] and references therein. Both of the papers assume data are generated at random, and propose a debiasing procedure via linear transformations, with similar theoretical results on consistency. It is difficult to see any fundamental innovation in the current work compared to previous works, especially given that all theoretical results are straightforward after confirming the consistency of the proposed risk. \n\n\nFor [16] and a more fundamental work On the Minimal Supervision for Training Any Binary Classifier from Only Unlabeled Data (ICLR19), they require separation of the class prior distribution, as argued in the paper, because they have a /theta-/theta' in the reweighting denominator, which could be reduced by multiplying them. The difference seems to be that the ICLR19 paper is calculating the expectation of risk using two sets, but the current paper is using one set; other derivatives are similar.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> On originality: Comparison to [16], and other papers like “On the Minimal Supervision…”\n\n* We thank the reviewer for stimulating a more thorough discussion of the related literature. The papers the reviewer is mentioning are related to ours, but they are by no means subsuming our results. For instance, both [16] and the “minimal supervision…” paper (as well as other papers in this stream of literature), rely on two or more $U$ sets, which are assumed to be diverse in the prior mixture. It is this diversity that allows the authors to construct unbiased estimates and then derive consistency results. In our case, the bags have the same prior $p$, and we work under the assumption that we cannot handcraft diverse bags out of our samples, as the aggregation into bags is done without having access to the class conditional distributions $p(x|y=1)$ and $p(x|y=-1)$. This setting is largely motivated by practical scenarios where the learner may not have any control on how bags are generated. The difference between the two settings can also be observed in the different flavor of the consistency results. E.g., in [16] (even with $m = 2$ bags) the consistency limit has to be interpreted ``as the bag size $n_{tr} = n_1+n_2\\ $ goes to infinity”. In our case, the bag size $k$ has to remain constant, and it is the number of bags that goes to infinity. \n\n* One more thing that we also found different is that, unlike our paper, all results in these previous works, as presented, make assumptions about the loss function (e.g., square loss or cross entropy for [16], margin-based losses for the “minimal supervision…” paper). The fact that we make no assumptions allows us to apply our debiasing procedure to any function g(x,y) of two variables, hence we can debias, e.g., also the *gradient* of a loss function, enabling the principled usage of stochastic gradient descent procedures with only label proportion information. This is something that comes for free in our approach, that we have not seen in the literature. Moreover in Appendix C we have an extension to the multiclass case.\n\n* We will add more detailed discussion in the related work section of the paper.\n"}, {"review_id": "rw3xpZUMcv", "reviewer": "Reviewer_z2CW", "summary": "The paper aims to advance the theoretical understanding behind the LLP problem, and provide the conditions under which the algorithm is expected to work. They propose a theoretically founded algorithm for learning from label proportions called EasyLLP. In particular, they have shown how to estimate the expected value of any function of (x, y) pairs from labeled data. They have also shown complexity guarantees for ERM and convergence guarantees for SGD.\n\nThe authors have also evaluated their proposed approach against PropMatch and 2 baseline models, on 4 datasets: MNIST, CIFAR-10, UCI Adult, and Higgs. For all the datasets, the authors have considered the corresponding binary classification variant, if they were multi-class.\nThe results show", "questions": "Concerns already listed under Weakness.", "limitations": "n/a", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors have clearly described their approach, and demonstrated the results against baselines on 4 datasets. Understanding the theoretical nature of LLP models is important given the application of the domain. The paper is a good step in that direction.", "weaknesses": "In order to improve the reproducibility of the approach, it will be helpful if the authors can either share their code or provide pseudocode for using EasyLLP. \n\nThe evaluation is limited to fairly broad datasets such as MNIST, CIFAR and Higgs. The LLP problem is applied to various real world problems, including those rightfully noted by the authors, such as advertising. The datasets in such domains have additional challenges such as a more complex feature space and class imbalance. It will be great if the results can be shown with such complexities taken into account.\n\nI'd encourage the authors to consider more recent approaches in LLP for comparing their results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> On reproducibility\n\nWe find EasyLLP quite simple to reproduce, even without pseudocode. In any event, we will happily make the code for our experiments available.\n\n> Limited experimental evaluation\n\nWe have strived to do as thorough an evaluation as possible by considering different datasets with different class proportions. Using advertising datasets can prove challenging, as there are no standard datasets we are aware of (for privacy and proprietary reasons) that can allow us to test the efficacy of our methods at predicting event level labels. \n\n> Comparison to more recent approaches in LLP\n\nWe appreciate the suggestion and would find it very helpful if the reviewer could point us to the more recent approaches they are alluding to in their review.\n"}, {"review_id": "RR78sHyVqD", "reviewer": "Reviewer_YhoX", "summary": "This paper focuses on the problem of learning from label proportions. It addresses the performance degradation issue of the EPRM method when the hypothesis class lacks sufficient expressiveness. To overcome this problem, the paper introduces EasyLLP as a solution. In practice, EasyLLP differs from EPRM (or PropMatching) in the calculation process. EasyLLP first calculates the corrected instance-level loss and then takes the average, whereas EPRM first takes the average of the bag-level predictions and then calculates the loss. This simplifies the implementation of the learning algorithm: just utilize a corrected loss function and approach the problem as a regression task.\n\n\n\n\n", "questions": "See weaknesses part.", "limitations": "n/a", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper studies the problem of LLP, which is an important problem to the community. The proposed method is based on a novel loss correction method, which could be useful for some related problems.\n\nThe paper points out and analyzes the limitation of EPRM. This finding is interesting and novel.\n\nThe proposition 4.2 with its proof seem to be a significant contribution. Based on proposition 4.2, the proposed EasyLLP is sound and easy to implement. Experimental results show the effectiveness of the proposed EasyLLP.", "weaknesses": "There are some minor issues:\n1. Literature [16] is also a method based on unbiased risk estimation, and is very related to the proposed method. How's the comparison between EasyLLP and [16]? It should be compared and discussed in the experiments.\n2. In section 3 the paper discussed the limitation of EPRM. However, why EasyLLP solves this problem is unclear. Please add some discussion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> On originality: Comparison to [16], and other papers in this literature.\n\n* A similar point was raised by Reviewer c8Fj. Thanks for stimulating a more thorough discussion of the related literature. The paper Reviewer YhoX is mentioning is related to ours, but it is by no means subsuming our results. For instance, [16] (as well as other papers in this stream of literature), rely on two or more $U$ sets, which are assumed to be diverse in the prior mixture. It is this diversity that allows the authors to construct unbiased estimates and then derive consistency results. In our case, the bags have the same prior $p$, and we work under the assumption that we cannot handcraft diverse bags out of our samples, as the aggregation into bags is done without having access to the class conditional distributions $p(x|y=1)$ and $p(x|y=-1)$. This setting is largely motivated by practical scenarios where the learner may not have control over the way bags are generated. The difference between the two settings can also be observed in the different flavor of the consistency results. E.g., in [16] (even with $m = 2$ bags) the consistency limit has to be interpreted ``as the bag size $n_{tr} = n_1+n_2\\ $ goes to infinity”. In our case, the bag size $k$ has to remain constant, and it is the number of bags that goes to infinity. \n\n* One more thing that we also found different is that, unlike our paper, all results in these previous works, as presented, make assumptions about the loss function (e.g., proper losses like square loss or cross entropy for [16], margin-based losses for Lu et al. “On the minimal supervision” ICLR 2019 paper). This flexibility allows us to apply our debiasing procedure to any function g(x,y) of two variables, hence we can debias, e.g., also the *gradient* of a loss function, enabling the principled usage of stochastic gradient descent procedures with only label proportion information. This is something that comes for free in our approach, that we have not seen in the literature. Moreover, in Appendix C, we have an extension to the multiclass case.\n\n* We will add more detailed discussion in the related work section of the paper.\n\n\n> Limitations of EPRM and why EasyLLP overcomes them.\n\nThe main difference between EPRM (aka Proportion Matching) and EasyLLP seems to be that the former can be catastrophically bad in non realizable settings (i.e., when the function $h^* : x \\mapsto P(y=1\\mid x)$ is not an element of the function class $\\mathcal{H}$). On the other hand, EasyLLP is not relying on this assumption. When confronted with a non realizable setting, the EasyLLP solution will simply converge to the best in class solution within class $\\mathcal{H}$. Yet, it should be added that Thm 3.2 and Cor 3.3 only provide *sufficient* conditions for EPRM to perform well. We do not know to what extent these conditions are also necessary, and in lines 192-201 we give an example (only verified empirically) where, if these conditions are not satisfied, the EPRM minimization criterion can cause learning to go completely off trail.\n\n"}]

Author rebuttal:

Meta-review: All reviewers are positive on this work. I agree with the authors’ response regarding why they do not compare to [16]. Also convinced was at least one of the two reviewers raising this point. This paper is a joy to read, well-motivated, and progresses very naturally to the easy-to-implement (and very clearly defined, in my view) method EasyLLP. The authors have given good theoretical guarantees which avoid the need to assume that the infamous “Bayes-in-class” assumption. The technical results do not look to be overly sophisticated, but overall this is a nice work. Another advantage, noted by the authors in the discussion period, is that their work has the flexibility of transcending proper losses, unlike many previous works. I recommend this work to be accepted to the conference.
Decision: Accept (poster)