Nearly Optimal Sample Complexity for Learning with Label Proportions
Authors: Robert Istvan Busa-Fekete
Travis Dick
Claudio Gentile
Haim Kaplan
Tomer Koren
Uri Stemmer
Venue: ICML 2025 poster (2025)
Keywords: sample complexity
aggregate labels
empirical risk minimization
stochastic gradient descent
median of means
Primary area: theory->learning_theory
TL;DR: We study Learning from Label Proportions, and provide improved regret and sample complexity guarantees. The algorithms are also experimentally validated.

Abstract: We investigate Learning from Label Proportions (LLP), a partial information setting where examples in a training set are grouped into bags, and only aggregate label values in each bag are available. Despite the partial observability, the goal is still to achieve small regret at the level of individual examples. We give results on the sample complexity of LLP under square loss, showing that our sample complexity is essentially optimal. From an algorithmic viewpoint, we rely on carefully designed variants of Empirical Risk Minimization, and Stochastic Gradient Descent algorithms, combined with ad hoc variance reduction techniques. On one hand, our theoretical results improve in important ways on the existing literature on LLP, specifically in the way the sample complexity depends on the bag size. On the other hand, we validate our  algorithmic solutions on several datasets, demonstrating improved empirical performance (better accuracy for less samples)  against recent baselines.

Nearly Optimal Sample Complexity for Learning with Label Proportions
Robert Busa-Fekete Travis Dick Claudio Gentile"
Haim Kaplan" 12 Tomer Koren" 12 Uri Stemmer 12
Abstract
e-commerce, medical databases (Patrini et al., 2014), high energy physics (Dery et al., 2018), election prediction (Sun et al., 2017), medical image analysis (Bortsova et al., 2018), remote sensing (Ding et al., 2017).
We investigate Learning from Label Proportions (LLP), a partial information setting where exam- ples in a training set are grouped into bags, and only aggregate label values in each bag are avail- able. Despite the partial observability, the goal is still to achieve small regret at the level of indi- vidual examples. We give results on the sample complexity of LLP under square loss, showing that our sample complexity is essentially optimal. From an algorithmic viewpoint, we rely on care- fully designed variants of Empirical Risk Mini- mization, and Stochastic Gradient Descent algo- rithms, combined with ad hoc variance reduction techniques. On one hand, our theoretical results improve in important ways on the existing liter- ature on LLP, specifically in the way the sample complexity depends on the bag size. On the other hand, we validate our algorithmic solutions on several datasets, demonstrating improved empiri- cal performance (better accuracy for less samples) against recent baselines.
Though early contributions to LLP date back to the mid 2000s (e.g.. (de Freitas & Kuck, 2005; Musicant et al., 2007: Quadrianto al., 2008)), it is only more recently that we have seen general resurgence of interest in this problem (e.g.. (Dulac-Arnold et al., 2019; Lu et al., 2019; Scott & Zhang, 2020; Saket, 2021; 2022; Tsai & Lin, 2020;
Lu et al., 2021; Zhang et al., 2022: Busa-Fekete et al.. 2023; Li et al., 2024; Havaldar et al., 2024)), often related to the desire of preserving the privacy of user data/activity data- intensive online businesses.
Relevant practical scenarios where LLP has started to play a pivotal role relate to the ad conversion reporting systems pro- posed by Apple (SKAN, (app, 2025)) and Google Chrome and Android (Privacy Sandbox (chr, 2021)), where user conversions (like user purchases) are only available at the aggregate level (e.g., by ad campaign), and training a con- version model is thus forced to leverage such aggregate signals as much as possible. Still, the models trained this way are required to perform well at the level of individual conversions.
1. Introduction
This paper is inspired by two recently published works in the LLP literature (Busa-Fekete et al., 2023; Li et al., 2024), where regret guarantees are given under standard statistical learning assumptions for randomly drawn (and non-overlapping) bags of given size. In the first paper, the authors describe general debiasing technique that applies to any bounded loss function (or loss gradient) to turn aggre- gate label signal into an individual label signal at the cost of an inflated variance of the resulting estimator. This allows the authors to seamlessly adapt their technique to standard learning methods like Empirical Risk Minimization (ERM) and Stochastic Gradient Descent (SGD). In particular, the authors give regret guarantees in general non-realizable sce- narios showing that when the learner deals with bags of size k. the sample complexity of ERM and SGD with label proportions increases by a factor of roughly 1.2
Learning with Label Proportions (LLP) is a semi-supervised learning setting where the learning algorithm only observes label values of a training set at the resolution of groups of feature vectors. Specifically, the training set is partitioned into collections of unlabeled feature vectors, called bags in the literature, and only the proportion of positive labels within each hag are observed, instead of the individual labels. The motivation comes from a number of practical scenar- ios where the access to individual labels either costly or impossible to achieve, or made available learner at an aggregate level because of
concerns.
Among these practical scenarios, it is worth mentioning
'Equal contribution 'Google Research, New York, USA 'Tel Aviv University, Israel. Correspondence to: Claudio Gentile <egen- tile @ @oogglo.ooo....... Travis Dick <tdick @ google.com>.
In (Li et al., 2024), the authors improve upon (Busa-Fekete et al., 2023) when the loss function is the square loss, in that their bounds yield fast rates of convergence in realizable
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Nearly Optimal Sample Complexity for LLP
settings (unlike (Busa-Fekete et al., 2023)). Yet, this is achieved the cost of widely sub-optimal dependence on the bag size k. In this paper, we leverage variance reduction techniques to achieve essentially optimal (up to log factors) sample complexity guarantees for LLP under square loss for both ERM and SGD. For instance, a quick comparison to (Busa-Fekete et al., 2023; Li et al., 2024) for square loss reveals the following. Call / > 0 the target regret guarantee. Then our sample complexity bounds are of the form & in the non-realizable case, and & 3 in the realizable case. In contrast, FeuseeFekete et al., 2023) only contains non-realizable (i.e., slow rate) guarantees, which are of the 32, while the realizable (fast rates) guarantees from form
machine learning architectures. Rueping (2010); Yu et al. (2013) propose an adaptation of SVMs to LLP. In particular, Yu et al. (2013) propose SVM algorithm for regression which optimizes the SVM loss by matching available la- bel proportions (this general approach is called proportion matching in (Busa-Fekete et al., 2023)). Yet, their approach turns out to be restricted to linear models in some feature space. Similar limitations are contained in other SVM-based papers LLP,, like (Qi al., 2017; Shi et al., 2019). Being very natural, the proportion matching idea was extended to other classifiers. For instance, Li & Taylor (2015) extends the formulation to CNNs with a generative model where the maximum likelihood estimator is computed via Expectation Maximization. Yet, this turns out not to be scalable even to moderately large DNN architectures. Liu al. (2019) experimentally investigate multiclass LLP via Generative Adversarial Networks. Another very recent experimental paper is (Havaldar et al., 2024), where the authors adopt an iterative process with two phases, in which a Gibbs distri- bution is first defined over labels that factors in the feature vectors so as to force nearby vector to have similar labels, and then use Belief Propagation to obtain pseudo- labels that produce embedding refinements.
(Li et al., 2024) are of the form 422 We also show that in the realizable case the sample bound k is the best one can hope /
for.!
Moreover, we perform a thorough set of experiments, where we compare our algorithm to the folklore proportion match- ing algorithm, which was reported to be strong baseline in (Busa- (Busa-Fekete et al., 2023), to the debiasing method from (Li et al., 2024), and to a number of alternative methods available in the LLP literature. The general goal of these experiments was to validate our theory on improved sample complexity guarantees. On diverse combinations of datasets and learning models, experiments do indeed reveal the superior performance of our variance reduction methods over the tested baselines. The empirical performance differ- ence is particularly stunning when the training procedure is restricted to only a few training epochs, thereby showcasing a substantial enhancement in convergence speed.
Among the more theoretically-ooiintee papers LLP are (Saket, 2021; 2022; Brahmbhatt et al., 2023; Lu et al., 2019; 2021; Scott & Zhang, 2020; Zhang et al., 2022), as well as the already mentioned (Busa-Fekete et al., 2023; Li et al., 2024). In (Saket, 2021; 2022; Brahmbhatt et al., 2023) the authors are essentially restricting to thressot functions and in some cases rely on the fact that bags can be overlapping. In contrast, we are following here the learning setting of Fukate et al. (2023); Li et al. (2024), and working with non-overlapping i.i.d. bags with more general model classes
1.1. Related work
Initial interest in LLP dates back to at least (de Freitas & Kuck, 2005; Musicant et al., 2007: Quadrianto et al., 2008; Rueping, 2010; Stolpe & Morik, 2011; Yu al.. 2013; Pa- trini et al., 2014). In (de Freitas& & Kuck, 2005) the authors propose hierarchical model generating labels according to the given label proportions, and formulates an MCMC- based inference scheme which, unfortunately, does not scale to large datasets. Musicant et al. (2007) stress that standard supervised learning algorithms (like SVM and N-Nearest Neighbors) can be adapted to LLP by reformulation of their objective functions, but no experiments are reported in that paper on classification tasks. Quadrianto et al. (2008) give an algorithm to learn an exponential generative model, which was further generalized in (Patrini et al., 2014). Both papers, however, make very strong modeling assumptions, like conditional exponential models, which are often inade- quate for Deep Neural Network (DNN) and more modern
In (Lu et al., 2019; 2021) the authors tackle the problem of learning from multiple unlabeled datasets, which is similar to LLP. The authors propose a debiasing method for the loss function, and prove consistency results (which are similar in spirit to those contained here, as well as those in (Busa- Fekete et al., 2023; Li et al., 2024)), but they do so by imposing further restrictions, like the separation of the class priors over bags. This can only be done by enabling access to the class conditional distributions. In contrast, the bags proposed in our setup are drawn i.i.d. from the same prior distribution, setting where the algorithms proposed in (Lu et al., 2019; 2021) would fail.
Scott & Zhang (2020); Zhang et al. (2022) reduce LLP to learning with label noise, in that bags are paired, and each pair is seen as a problem of learning with label noise, with label proportions being treated akin to label flipping probabilities. Yet, as in (Lu et al., 2019), the bag pairing heavily relies on the statistical diversity of the bags, which
A similar statement can also be extracted from (Li et al., 2024). Their lower bound has a wider scope than ours, but at the cost of extra log ls factors.
2

---

Nearly Optimal Sample Complexity for LLP
we explicitly rule out. The kind of population loss they are interested in (balanced risk) is also bit different from the one we deal with here.
pothesis Tr E H with the smallest population loss (or risk) [(h) = (a.)))= (((h(1)), vj] with high probability over the random draw of S. In order not to clutter the paper with too many mathematical details, we shall assume henceforth that the hypothesis space H is finite. The theoretical anal- yses contained in the paper can be easily lifted to infinite hypothesis spaces via standard tools in empirical process theory (e.g.. (Bartlett et al., 2005; Boucheron et al., 2012: Vershynin, 2018)).
For the sake of fair comparison, in our experiments (Section 6) we followed prior experimental setups, like the one in (Busa-Fekete et al., 2023), and chose to compare only to methods with similar goals and settings as ours, like the folk- lore proportion matching method (e.g., (Yu et al., 2013)), the EasyLLP method by Busa-Fekete et al. (2023), the debi- ased square loss method proposed by Li et al. (2024), and the label generation approach by Dulac-Arold et al. (2019) (binary version thereof).
Given H. and D. the excess risk (or regret) R(h) of h is R(h) = ((h) - [(h"), where h = arg min (h) is the model in H having the smallest risk (sometimes called best-in-class model). We say that we are in re- alizable setting when the Bayes-optimal predictor h* arg min, [(h), the minimum being taken over all possi- ble (measurable) functions, belongs to H. and in a non- realizable setting, otherwise. Clearly enough, in the realiz- able setting, h hh*
2. Preliminaries
For a natural number nt let [n] (i E N: S n). Let X be feature (or instance) space, and y be binary Y {0, label space. Let 'D be a joint distribution on X' x V, encoding the correlation between the input fea- tures and the labels. The marginal distribution over X' will be denoted by Dx. and the conditional distribution of y given x will be denoted by Dylu- In particular, we de- note by n7(x) Py Py- (y = 1/ar) = Eyy-Dyi= [w|r] the probability of drawing label I conditioned on feature vec- tor x. When clear from the surrounding context, we shall remove the subscripts from probabilities and expectations and, e.g., abbreviate Byy-Dy [u]=:] by Ely]ær]. A dataset S = (H1, (1). ..., (Zn; Fo)) is a sequence of pairs (i), each one drawn i.i.d from D.
Our goal is to design and analyze algorithms that com- pute h E H with small R(h) in both realizable and non- realizable settings. In particular, for a given bag size k. our goal is to minimize the number of bags m (the sam- ple complexity is then n = mk) required for a particu- lar regret guarantee. We will obtain tight bounds on the sample complexity specifically for the square loss case, ((h(x). v) (v h(z))?
In a sense, if we view label aggregation as form of (label) privatization mechanism (which is not differentially private, though), this investigation aims at striking the best possi- ble tradc-off's between utility (that is, the regret R(h) as a function of the sample size n) and privacy in the form of the label aggregation level k.
In our LLP scenario, the dataset S is partitioned uniformly at random into bags of a given size k, where only feature vectors and the fraction of positive labels in each bag are available for learning, that is,
S =
ar),, ((5m. Tm..k) amm) (81.0)
As in recent investigations on LLP (Busa-Fekete et al., 2023; Li 2024), we cover two kinds of standard learning algo- rithms: Empirical Risk Minimization (ERM), and Stochastic Gradient Descent (SGD), and show that we can improve in various ways on the results of both papers.
(1mm
(1)
with = mk. where B, = {يحم i E [b]] aj =
k _i=1 Ujs is the label proportion (fraction of labels "1") in the j-th bag, and all the involved samples (1z,4: vy,4) are drawn i.i.d. from D. Thus, the learning algorithm gets infor- mation about the labels yiau of the instances Ty,i from dataset S only in the aggregate form determined by the m la- bel proportions aj. Yet, note that the feature vectors Ty are individually observed. Also, note that, for a given sample size n = mkk, the bigger is the smaller the overall amount of label information the algorithm receives.
3. Warmup: A realizable Setting with Two Functions
As a warmup, we consider the simplest possible scenario of I.P,, a realizable setting where the function space H has only two models H = {/1 ht with either 77(-) = h1 (-) or ny() = hz(+). Though the argument we are about to present here clearly applies more general loss functions, consider for definiteness the square loss. It can be easily seen that in this case the Bayes optimal predictor h² (-) coincides with ny-).
As is standard in statistical learning, are given hypoth- esis space H = (h- X + [0. }}} of functions h mapping X' to [0, 1]. where (xx can be interpreted as the probabil- ity that y = 1 given x according to model h, and a loss function f : [0, 1] x y + R In LLP the learner has access to S in the form (1) above, and tries to find hy-
Suppose the two models are significantly different from one another, in the sense that [C(h)) - L(h22) = 3 > 0. In
3

---

Nearly Optimal Sample Complexity for LLP
this case, if want achieve a regret smaller than are forced to identify h exactly. We will see momentarily that this simple problem already poses significant challenges if we want to prove optimal rates of convergence as a function of both the number of bags m, and the bag size k.
Algorithm Algorithm for the function realizable case.
Input: Sample made up of m 2 bags, each of size k z 1, bias E [[-1, separation parameter / E (0, 1].
If A
then:
2k
Our algorithm for computing h is presented as Algorithm 1. For bag (Bz, 25). and hypothesis h,, for 8 E 2), set for brevity
If [A)( [A2(S))
then: ì h
Else: h h2
J,,
= Elka,] 1B]]
Σ (x) ZEB,
h12 h1
if Q(S) 2 0
Else h
if Q(S) <
Denote by {.} the indicator of the predicate at argument, define H 2 (E1 E,,2), for j E [ml] and consider the
Output: h
statistics
m
where a probability distribution D is defined,
A
(aa B3,1)
A2
Σ (ay B2,2)
B =x)( h2(2)))1
and
and
- - E1-1,1
Q = 36 1=1
[E11 I Ey,2(kay - H4)
Let Algorithm 1 be fed with an i...d. sample of size drawn according to D, with m bags each of size k. Then, if k = 121/3), with probability at least Algorithm outpus ie = h², provided
[E E,,2(Ky kay))
Define the bias = (z) - hz(2)] E [-1, and note that, since the underlying loss is the square loss, the separation parameter B can also be written as B (1(((())) (x)) We assume here for simplicity that both A and B are known or easy to estimate. In fact, both quantities can be estimated without labels, and we can do so with an accuracy which is higher than the one allowed by the m aggregate label signals (Section B.2 contains an example of these estimates applied to the more involved scenario of Section 4).
n n= 0
-(min
1
108
log 1
A
Moreover, when A (which is the hardest case), a spe- cific setting H and D exists for which no algorithm can be correct with probability at least 8, with 8 < 1/2, unless
n 1 k(1 E(0))
B
where E(.) is the binary entropy function E(x) = x log, x - (1 x)) logz - x:). In other words, when A the sample size n must be linear k.
Intuitively, when | is large, the models in and ha are distinguishable based only on the total number of positive predictions they make. In this case, the algorithm predicts based on A₁ and Ag, which compare the observed number of positive labels to the number expected under h and h2, respectively. However, when | is small, the algorithm needs to check for agreement between h1 and h2 and the label proportion each bag, which do through Q
Algorithm can immediately be extended the case of more than two hypotheses, just by implementing an elimina- tion tournament via pairwise comparisons. We do not know, however, how to make it work in non-realizable settings.
The reader should observe that, being the decision rule Q a pairwise statistic, it cannot be expressed as the difference of two separate scoring functions (one for hi and the other for h2). Hence Algorithm 1, though sample optimal, does not easily lend itself to extensions of practical relevance. We now turn our attention more viable solutions.
The following theorem2 shows that sample complexity = Okk/)) (without hidden log factors) is both necessary and sufficient. The result improves on (Li et al., 2024) by shaving off the log k factors appearing in both the upper and the lower bounds analysis therein (see Theorem and Theorem in (Li al., 2024)).
Theorem 3.1. Let H = (h2,h2) be a hypothesis class where he is either h or hz. = X x y be the domain
4. Empirical Risk Minimization
Our proposed Empirical Risk Minimization (ERM) algo- rithm for square loss operates on bag level loss that can be
Full proofs are given the appendix.

---

Nearly Optimal Sample Complexity for LLP
seen as robust (or clipped) bag-level square loss. Specifi- cally, for bag 2j (Bj,a}) and function h E H, we set
In particular, in the realizable case (1hh", ,h1) 0), the number of bags mn that suffices is
K (h) = Σ h(H Eh(h) = (h) kB[h(=)].
(
( log
HPp
m O
log
3
Moreover, similar algorithm exists, where the quantities [[((x)] and are replaced by empirical estimates, which enjoys the same sample complexity guarantees as above.
Then we define the clipped bag-level square loss
(h, = 1 (kā, - -b)( (2(h)+ + (116(z))
where āj- = aj - p = E[hh" (x)], and
Proof sketch. Define the non-clipped version of the loss at the bag level:
2 0
G2(h) 1 1 (h)l S / 8k log
( E(h, E(h, = ( 1egy-Eyy R,(()) (F[M(T))
(2)
for a suitable value of parameter 0 > O. (Recall that (-) denotes the indicator function for the predicate at argument.)
and let (h(h) denote the expected value of E(h, 2,) over the random draw of bag 2z. The first observation we make is that this expectation is the same the expectation of the original square loss (y h(xx)), when (z, y) is randomly drawn according to D, i.e.,
Again, for simplicity of presentation, we assume in the above that [[](.z)), for h E H. and p are known. In fact, []](=]] can be easily estimated from unlabeled data, and p can be easily estimated from label proportions aj. the main point being that both quantities can be estimated at a higher resolution than the one allowed by the aggregate label signals. Appendix B.2 contains a version of the algorithm where E[h(x)) and p are themselves estimated from data. This is similar in spirit to the corresponding argument in (Li et al., 2024), but the analysis here is somewhat more involved, since special care has to be taken to ensure that fast rates are preserved even after clipping the square loss.
Cg(h) [(h)-
(3)
Then the proof essentially proceeds as a bias-variance trade- off analysis. We show that the clipping operation that turns e(h, zz) into (h, only introduces small bias while, at the same time, helping us reduce the variance substantially.
In fact, as is customary in fast rate analyses (e.g., (Massart, 2000; Mendelson, 2002; Bartlett et al., 2005)) the above varianar trade-off does not refer to the loss itself, but to the difference of losses 8 (",,, 2z) - 8 (h+,, 22),, for which can prove a bias bound of the form kf, variance bound of the form
Then we define the ERM estimator
1 Σ (h,,)))
T((S) = arg min NEH m 3=1
(h, (() log 0 + k20
and range bound of the form log 1.- In turn, for square loss,
We have the following result.
Theorem 4.1. Let H be a finte hypothesis space, Z X x y be the domain where probability distribution D is defined. Let the ERM estimator h defined above be fed with a sample of size n = mk, with m bags of size k2 drawn ii.d. according to D, and let
- 001 k²) + -(h) L(it)), -
where we recall that ((,, h²) B(((=))>N((>))
Setting
0 fa in the above makes the bias smaller than the desired regret bound (9, and yields variance bound of the form
Yhe 1²) =E((h* (S((h(()) (x) 11
(T 11) + ((h) - c(h²)) log
k
(4)
Then, for all B >>0 0, i = Tak in the clipping condition defining Gh),) and
B
B
and a range bound of the form log 4
& m O (7(00,, 11*) + B)ggg
B
|H.g]
In broad strokes, our goal in the ERM analysis is to make sure that with high probability we are able to separate any h from ht, whenever h & H.s This separation effort is made easy as the loss difference L(h) - L(h+) increases. Yet, at the same time, the bigger L(h)- L(h²) the higher the variance (4). Solving this trade-off within standard concentration inequalities, and taking a union bound over
log
32
we have
R(,i) L(h)- - L(h²) B
holding with probability at least 8. In the above,
H₂g {h H: R(h)= 2 3 3
S H.
h E Hs gives the claimed sample complexity bound.
5

---

Nearly Optimal Sample Complexity for LLP
Theorem 4.1 improves in number of ways over the existing literature. For instance, comparing (Busa-Fekete al., 2023), we have sharper sample complexity guarantees: our bound reads
Algorithm 2 SGD-based algorithm
Input: stepsize 17. clipping threshold 7 > 0 Initialize w1
(**(=((** )+)+++++))))+++) ()) which becomes n = ()) in the realizable case, while the regret guar- antees in (Busa-Fekere et al., 2023) are only of the form n = ( //32) (that is, slow rates only and, in addition, a quadratic dependence on k. instead of linear). On the other hand, the results in (Busa-Fekete et al., 2023) apply all bounded losses, not just to square loss.
for bags j 2, ... do Compute centroid F. = I 2xm1 33,5
if [| - pzl ll S Yp then
update
Wj+1
I1 - -VVV-V 2,)]
where f(w, 2ÿ) as in the main text.
The more recent paper (Li et al., 2024) also covers the square loss case, but the results contained there are widely sub-optimal when it comes to the dependence on k. For instance, the authors show fast rates for a debiased square loss algorithm, but the sample complexity therein reads (in our notation) n O(k-/B) /.). Besides, the authors consider only more restricted notion of realizability where [(h*) O and the functions in the hypothesis space H have binary output, thereby ruling out any potential noise in the labels. Needless to say, the assumption about deterministic labels particularly problematic when we want to associate any notion of privacy with the label aggregation mechanism.
else
skip update and proceed to the next step end if
end for
Output Wm = 25=1 Wi.
These are the marginal expectations under D, that can be approximated from (either individual or bagged) data in a straightforward and sample-efficient manner. We emphasize that the method we are about to present can be immediately modified to have μty and Py estimated from data instead (the modification would be similar in spirit to the one contained in Section B.2). Observe that, due to our assumptions, we have | S Pa and | S Pv-
Finally, compared to the optimal bounds in Theorem 3.1, those in Theorem 4.1 are looser only by log factors, but they clearly apply to wider settings.
The algorithm we propose and analyze for this setting in presented in Algorithm 2. The algorithm operates with the bag-level square loss
5. Stochastic Gradient Descent
In this section, we show that a similar variance reduction technique as in Section leads to improved results for Stochastic Gradient Descent methods applied to LLP tasks.
((w, 23) = l (w- (5, pxx) (a. - ny))² (by)) + (w Mh mgy)
which can be easily verified to coincide with the non-clipped bag level loss (2), upon setting h(x) = w and p Ely] Essentially, the algorithm constructs a debiased version 2() of the square loss (y w x²)² based on each bag 2j = (B), ag), and performs SGD updates on a truncated (variance-reduced) version of this loss function, defined as
For the sake of this section, the loss is still the square loss {(M(z),)) = (y- - )(x)),, but the hypothesis space is that of norm-bounded d-dimensional linear predictors,
H [h.: -> x w E TRd, |||||| S pw))
with known Per > O. We can think of the labels y E y as binary, as before, but there is no real need for this restric- tion. So, in this section, we look at the problem more as a regression problem, and assume the labels are real-valued and bounded: y {y E R |y| S Py). for some known Py > 0. The label aggregation at each bag Bj is still done via averaging: aj x Σ Vy.a- The population loss can now be conveniently expressed function of w directly:
ö(w, z,) E(w, 2;) (1l - pm S 0pn)
for some 8 > 0. The updates are projected back to the feasible set of norm-bounded models {w E Rd ||w||| < } here II denotes the Euclidean projection operator onto the latter set.
Our main result in this section is the following population excess risk bound for Algorithm 2:
[(w) = ([ (( (r), v)] B(a.)>~lyy - w-www)) =)
Theorem 5.1. Let X,Y, D. H. Pzz Pies Pzx Py be as described earlier in this section. Let a sample S of size n mk,, with m bags of size k. be drawn i.dd according to D. Set
Further, as is customary in SGD analyses, we assume that D is such that ||=||| $ Pr: almost surely, and that the constant Pe > 0 is given to For simplicity we shall also assume that the following quantities are known (exactly):
8
[9km(pupe + py)2
0
log
Px = =[
My =Ely
k
P3.p
6

---

Nearly Optimal Sample Complexity for LLP
and
6.1. Experimental Setup
(= (k02 1)p
We prepare each training dataset by shuffling the data, parti- tioning it into consecutive bags of size k, and replacing the labels within each bag by their average. Then we train mod- els on the LLP data as follows: On each training epoch (a single pass through the processed training data), we shuffle the order of the bags and group them into batches contain- ing a fixed number N of examples. The examples within each bag are the same on each epoch, only the order of the bags is permuted. On all datasets we choose batch size of N = 1024 and use bag sizes k 2 for ....., 9. For each batch, we compute the gradient of the aggregate loss function and use Adam (Kingma & Ba. 2015) to update the model parameters. After completing F training epochs, we evaluate the model's test accuracy at the level of individual examples (z. y).
Then, for any L > O, the hypothesis wm output by Algo- rithm 2 with step size
Pw
1
1 min
22
2
and clipping threshold satisfies, for all w² such that ||=1|| S Pw and [(w") ) S L", and any B
[B [mm] )] -[(w") S BB
whenever
Paule 3
I.* PaPP
m =
B²
We repeat the above training procedure 10 times for each loss function, dataset, bag size, and Adam learning rate in the set {10-6, 5 10-6, 10 10 10-4, 5 10-4 10 30- 10 10-3,10 10-2). 2). Each repetition uses a different partition of the training data into bags and different random model ini- tialization. For each bag size and aggregate loss, we report the average test accuracy at the end of E training epochs (that is, cycles through the data) achieved by the best per- forming learning rate.
In the above, the expectation is over the generation of S, and the asymptotic notation hides logarithmic factors of the form log(km) and log 1
Pv PwPp
In particular, in the nearly realizable case when I, O, the theorem gives a fast O(L/m) rate of convergence, as opposed to the ((1/ rate obtained in the non-realizable case (where/ I,* >> 0).
The sample complexity above reads n = 0kk39) in the non-realizable case, and n = (kk/B) (3) in the realizable case. It is instructive to compare to the SGD result from Busa- Fekete et al. (2023) (Thm 6.1 therein), whose sample bound of the form n = 0 /B). Thus, in addition to obtaining fast rates, we shave a factor l from the sample complexity. On the other hand, it is fair to say that the result in (Busa- Fekete et al., 2023) applies to more general convex losses.
6.2. Datasets and Models
We conduct our experiments on the following datasets and models. We use versions of MNIST (LeCun et al., 2010) and CIFAR-10 (Krizhevsky, 2009) with binary labels, together with the Higgs (Baldi et al., 2014) and UCI Adult (Kohavi & Becker, 1 1996) datasets, which are already binary tasks. Following Busa-Fekete et al. (2023), we binarize the labels of MNIST based on whether they are even or odd and, for CIFAR-IO, we replace the original labels by whether the image depicts animal (bird, cat, deer, dog, frog, horse) or machine (airplane, automobile, ship, truck). On MNIST and CIFAR-10 10 we train CNN models, while on Higgs and UCI Adult we train fully connected networks. Full details of the datasets and models are given in Appendix D.
sketch. sketch. Our basic approach to Algorithm 2 and es- tablishing Theorem 5.1 is to observe that the algorithm performs online projected gradient updates with respect to the loss sequence 21), ..,, f(,, ), and appeal to online-to-batch argument for obtaining a population-level excess risk bound for this algorithm. Crucially, our analy- sis leverages the fact that the non-truncated bag-level loss f(w,, 2,) is an unbiased estimator of the population square loss at the individual example level (recall Equation (3)), as well as the smoothness of the (truncated) squared loss func- tions obtain fast rates in (nearly) realizable scenarios. L
6.3. Aggregate Losses
We train models using five aggregate losses. OURS refers to the unclipped version of our proposed loss, given in (2). LI FT AL. is the aggregate loss proposed by Li et al. (2024), which is also an unbiased estimate of the squared
"Our choice of using the unclipped loss rather than the clipped one was mainly practical. On one hand, the clipped loss introduces one more parameter to tune (the clipping constant 0). On the other, observed in preliminary experiments that our method works well even without clipping.
6. Experiments
In this section we compare our proposed LLP loss to base- line losses on several datasets and models following closely the setup of Busa-Fekete et al. (2023).
7

---

Nearly Optimal Sample Complexity for LLP
CIFAR-10 Animal vs Machine 20 epochs
MNIST vs Odd epachs
Higgs epochs
0,95
1.00
0.80
0.90
0.95
0.75
0.85
accurac
0.80
accuracy
0.90
accuracy
0.70
0.75
0.65
EasyLLP
EasyLLP
EasyLLP
0.70
VanillaCE
VanIllaCE
0.60
VaniliaCE
0.65
VaniliaSQ
0.80
VanillaSQ
VanillaSQ
al.
Li
0.55
0.60
Ours
0.75
0.55
0.50
2
2
2
2
2
2
2
2 2
2
2
bag size
bag size
bag size
CIFAR-10 Animal Machine 200 epochs
epochs
0.80
Higgs epochs
1.000
0.975
0.75
0.950
accuraty Surraco
0.80
accuracy
accuracy
0.925
0.65
EasyLLP
0.900
EasyLLP
EasyLLP
VanillaCE VanillaSQ
VanillaCE
VanillaCE
0.875
VanillaSQ
Vanilla
Liet al.
0.850
et
0.55
et al.
Ours
Ours
0.55
20
2
2
2
2
2
2
2
0.825
2a
2
2
27
2
2
0.50
2
24
2
2
bag size
bag size
bag size
Figure 1. Plots showing the final test accuracy of models trained on selected datasets as function of the LLP bag size and number of training epochs. Error bars show one standard error in the average over 10 repetitions of each run. Each data point represents the accuracy achieved by learning rate tuned that bag size and loss. Some of the curves are not visible since they are overlapping. This the case, in particular, for VANILLACE, which is often overalapped with VANILLASQ.
loss at individual examples, but suffers from higher vari- ance. VANILLASQ and VANILLACE refer to the proportion matching losses where compare the model's average prediction to the label proportion using squared loss and binary cross-entropy, respectively. Finally, EASYLLP refers to the unbiased loss estimate of Busa-Fekete et al. (2023) applied with the binary cross-entropy loss. Full details of the aggregate losses are given in Appendix D, including the way we implemented the estimation of the unknown quantities [[](x)) and p for OURS.
far worse worse." We also note that OURS tends widely outperform the other baselines especially when the number of training epochs is lower, suggesting that these losses lead to more computationally efficient training.
As for comparison to the method proposed by Dulac-Arnold et al. (2019), we note that their method has already been shown to underperform in comparable experimental setups. For instance, on CIFAR-1O, Busa-Fekete et al. (2023) report test set accuracy of around 0.65 with bag size k 26 (see Figure 4 therein), while all the methods tested are above 0.8 on similar CNN architecture. On Higgs, with the very same NN architecture (the one originating from (Baldi et al., 2014)), all the methods we tested have test set accuracy which is above by at least 5% across all large enough bag sizes. E.g., for k 2 Busa-Fekete al. (2023) report test accuracy below 0.6 (see Figure therein), while all our methods are above 0.65.
6.4. Results
Figure I shows the final test accuracy of each aggregate loss at various bag sizes and number of training epochs (some of the curves are not visible since they are overlap- ping to one another). The aggregate losses OURS, LI ET AL., and EASYLLP are all unbiased estimates of the pop- ulation loss at the level of individual examples. However, as we will see in Section 6.5, the variance of OURS grows significantly slower with the bag size & than that of LI AL. and EASYLLP. In comparison, the VANILLA baselines not unbiased. At every bag size and training duration, our proposed method achieves the highest accuracy. In com- parison, even though the other methods perform reasonably well at low bag sizes, once & is sufficiently large, the high variance of these method eventually causes them to perform
8

---

Nearly Optimal Sample Complexity for LLP
20
7. Conclusions, Limitations, and Ongoing Research
Ours
Li et
15
Easy LLP
We have studied LLP in the relevant case where bags drawn i.i.d. according to fixed but unknown distribution over X' x V. Via suitable variance reduction techniques, we have proven tight bounds on the sample complexity in realizable and non-realizable settings, with substantial im- provements over prior in comparable statistical learning settings.
variance
10
50
100
150
200
250
bag size
We have empirically contrasted our variance reduction meth- ods to available LLP baselines on a variety of datasets and underlying model architectures, showing superior test set performance at the individual example level. The perfor- mance gap is especially remarkable for big bag sizes, the regime that matters the most for LLP applications.
Figure 2. Plot showing how the variance of the loss estimate of OURS, LI ET AL and EASYLLP, grows with the bag size in the simple setting described in Section 6.5. Both LI ET AL. and EASYLLP have variacne that grows linearly with the bag size, while OURS has constant variance, close to zero.
As for current limitations, this paper could be extended along number of directions.
6.5. Variance comparison
In this section we compare the variance of the loss estimates produced by our method, LI ET AL.., and EASYLLP for simple synthetic data distribution and model h defined be- low. Recall that all three of these methods produce unbiased estimates of the squared loss on individual examples, so the variance characterizes how reliable those estimates are. We showed that the variance of the loss estimate computed from single bag using our method does not grow with k, while the variance of all prior methods does.
We would like to achieve regret guarantees also for practically relevant loss functions beyond square loss, like the log loss for ERM and more general convex losses than square loss for SGD. The extension to log loss, for instance, is nontrivial, as the log loss is itself an unbounded loss function. This is a loss function commonly adopted in DNN training.
As currently presented, our analysis only applies to binary classification. A suitable extension to multiclass classification would be important in practice.
We consider the simple setting where x is uniform in [0, 1]. and the distribution of is Pr(y = 1 x) = h- (x) =
Each method used to estimate [1 - )] based on LLP data. We compute the label marginal p exactly, and estimate [T)())) in the same way as our learning experiments. That is, we break that data into batches containing 1024 examples (regardless of bag size) and for each bag within the batch, we estimate [f)( as the sample average of Ti(x)) over the batch excluding that bag.
x² We estimate the loss of the model h(x)
Another practically important extension is the case when the examples within the bags the bags them- selves come from distributions that drifts over time. This is another practically relevant scenario where a low variance estimator is expected to have an edge, thanks to its higher adaptivity.
There are also technical limitations related to some of the formal statements we provided. For instance, Theorem 3.1 applies only when & is big enough (k 2(1/B)), not for smaller it
In Figure 2 we plot the empirical variance of the loss esti- mates computed from
220 examples worth of bags for bags of size k = 2, 4, 8, 16, 32, 64, 128, 256. We see that both ET AI.. and EASYLLP have empirical variance that grows linearly with the bag size, while OURS is essentially constantly equal to 0.034. We remark that the variance of OURS does grow slightly to 0.055 at bag size k 256, but this is because, as the bag size grows, there are fewer remaining examples within the batch to estimate B([())).
*In this respect, we need to point out that our original im- plementation of the method from (Li et al., 2024) did contain measurement bug that made it perform better than reported here. This bug was contained in the original submission of this paper, has now been fixed.
9

---

Nearly Optimal Sample Complexity for LLP
Impact Statement
Information Processing Systems, NeurIPS 2023. Curran Associates Inc., 2023.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Cover, T. and Thomas, J. A. Elements of Information Theory 2nd Edition. Wiley, 2006.
de Freitas, N. and Kuck, H. Learning about individuals from group statistics. In Proceedings of the 2 Conference in Uncertainty in Artificial Intelligence (UAI 2005), pp. 332-339, 2005.
References
Chrome privacy sandbox. https:://eveelopers.
http:////.//o..aaaaaaaaaa/////// innriibution--repotte 2021.
Dery, L., Nachman, B., Rubbo, F., and Schwartzman, A. Weakly supervised classification for high energy physics. Journal of Physics: Conference Series, 1085:042006, 2018.
Skadnetwork 4 release notes.
https://developar
apple. com http:///mmmmaaato//sseeeeeee
skrchnetwwrrkkksaaahttttwreeeeee notes/skadnetwoon 2025.
Ding, Y., Li, Y.,, and Yu, W. Learning from label propor- tions for sar image classification. EURASIP Journal on Advances in Signal Processing, 2017.
Adell, J. A., Lekuona, A., and Yu, Y. Sharp bounds the entropy of the poisson law and related quantities. IEEE
Dulac-Arold, G., Zeghidour, N., Cuturi, M., Beyer, L., and Vert, J.-P. Deep multi-class learning from label propor- tions. arXiv preprint arXiv: /905. /2909, 2019.
Transactions on Information Theory, 5665):2299-2306,
May 2010. ISSN 1557-9654.
doi: 10.1109/ti.2000.
2044057. URL http:// /ttt:://x... //dxxdoii.. otg/io.rg1.... 1109/ TIT. 2010. 2044057.
Harremoës, P. Binomial and poisson distributions as maxi- mum entropy distributions. IEEE Transactions on Infor- mation Theory, 47(5):2039-206 2001.
Baldi, P., Sadowski, P., and Whiteson, D. Searching for Ex- otic Particles in ing. Nature Commun., 5:4308, 2014. doi: 10.1038/ ncomms5308.
Physics with Deep Learn-
Havaldar, S., Sharma, N., Sareen, S., Shanmugam, K., and
Raghuveer, A. Learning from label proportions: Boot- strapping supervised learners via belief propagation. In ICLR, pp. 66610-66646. Curran Associates, Inc., 2024.
Bartlett, P., Bousquet, O., and Mendelson, S. Local rademacher complexities. The Annals of Statistics, 33(4): 1497-1537, 2005.
Hazan, E. al. Introduction online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157- 325, 2016.
Bortsova, G., Dubost, F., Orting, S., Katramados, I., Hogeweg, L., Thomsen, L.,, Wille, M., and de Bruijne, M. Deep learning from label proportions for emphysema quantification. In Medical Image Computiig and Com- puter Assisted Intervention- MICCAI 2018, pp. 768-776, 2018.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Kohavi, R. and Becker, B. UCI adult data set. UCI Machine Learning Repository, 1996.
Boucheron, S., Lugosi, G., and Massart, P. Concentration inequalities: nonasymptotic theory of independence. Clarendon Press, 2012.
Krizhevsky, A. Learning multiple layers of features from tiny images. Technical report, Toronto Univ., 2009.
LeCun, Y., Cortes, C., and Burges, C. Mnist hand- written digit database. ATT Labs [Online]. Available: 2, 2010.
Boucheron, S., Lugosi, G., and Massart, P. Concentration Inequalities- Nonasymptotic Theory of Independence. Oxford University Press, 2013.
Li, F. and Taylor, G. Alter-cnn: An approach to learning from label proportions with application to ice-water clas- sification. In NIPS workshop on Learning and privacy with incomplete data and weak supervision, 2015.
Brahmbhatt, A., Saket, R., and Raghuveer, A. Pac learning linear thresholds from label proportions. In Advances in Neural Information Processing Systems, volume 36, pp. Curran Associates, Inc., 2023.
Li, G., Chen, L., Javanmard, A., and Mirrokni, V. Optimistic rates for learning from label proportions. In Proceedings of Machine Learning Research, volume 247 of 37th An- nual Conference on Learning Theory, pp. 1-38, 2024
Busa-Fekete, R., Choi, H., Dick, T., Gentile, C., and Med- ina, A. M. Easy learning from label proportions. In Pro- ceedings of the 37th International Conference on Neural
10

---

Nearly Optimal Sample Complexity for LLP
Liu, J., Wang, B., Qi, Tian, Y., and Shi, Y. Learning from label proportions with generative adversarial networks. In Proc. NeurlPS, P. pp. 7167-7177, 2019.
Shalev-Shwartz, S. and Ben-David, S. Understanding mu- chine learning: From theory algorithms. Cambridge university press, 2014.
Lu, N., Niu, G., Menon, A. K., and Sugiyama, M. On the minimal supervision for training any binary classifier from only unlabeled data. In Proc. ICLR, 2019, 2019.
Shi, Y., Cui, L., Chen, Z., and Qi, Z.. Learning from la- bel proportions with pinball loss. International Journal of Machine Learning and Cybernetics, 10(1):187-205, 2019.
Lu, N., Lei, S., Niu, G., Sato, L,, and Sugiyama, M. Bi- nary classification from multiple unlabeled datasets via surrogate set classification. In Proceedings of the 38th International Conference on Machine Learming, pp. 7134- 7144, 2021.
Stolpe, M. and Morik, K. Learning from label proportions by optimizing cluster model selection. In Machine Learn- ing and Knowledge Discovery in Databases, pp. 349-364. Springer Berlin Heidelberg, 2011.
Sun, T., Sheldon, D., and O'Connor, B. A probabilistic approach for learning with label proportions applied to the us presidential election. In IEEE International Con- ference on Data Mining (ICDM), pp. 445-454, 2017.
Massart, P. Some applications of concentration inequalities to statistics. Probability theory. Ann. Fac. Sci. Toulouse Math., 609):445-33, 2000.
Mendelson, S. Improving the sample complexity using global data. IEEE Trans. Inform. Theory, 48: 1977-1919 2002.
Tsai, K.-H. and Lin, H.-T. Learning from label proportions with consistency regularization. Asian Conference on Machine Learning, 2020.
Musicant, D., Christensen, J., and Olson, J. Supervised learning by training on aggregate outputs. In Proceedings of the 7th IEEE International Conference on Data Mining (ICDM 2007), 2007.
Vershynin, R. DigeenDimeniion Probability: An Intro- duction with Applications in Data Science, Cambridge University Press, 2018.
Yu, F., Liu, D., Kumar, S., Jebara, T., and Chang, S. Q-svm for learning with label proportions. In ICML,, Proceed- ings of the 30th International Conference on Machine Learning, pp. 504 512, 2013.
Patrini, G., Nock, R., Rivera, P., and Caetano, T. (Almost) no label no cry. In Proc. NIPS, 2014.
Qi, Z., Wang, B., Meng, F., and Niu, I.. Learning with label proportions via npsvm. IEEE Transactions on Cy- bernetics, 47(10):323333005, 2017.
Zhang, J., Wang, Y., and Scott, C. Learning from la- bel proportions by learning with label noise. In Proc. NeurlPS 22, 2022.
Quadrianto, N., Smola, A. J., Caetano, T. S., and Le, Q. V. Estimating labels from label proportions. In ICML, vol- ume 307 of ACM International Conference Proceeding Series, pp. 776-783. ACM, 2008
Rueping, S. SVM classifier estimation from group proha- bilities. In ICML, Proceedings of the 27th International Conference on Machine Learning, pp. 911-918, 2010.
Saket, R. Learnability of linear thresholds from label pro- portions. In Advances in Neural Information Processing Systems, volume 34, pp. Inc., 2021.
Curran Associates,
Saket, R. Algorithms and hardness for learning linear thresh- olds from label proportions. In Proc. NeurlPS'22 22, 2022.
Scott, C. and Zhang, J. Learning from label proportions: A mutual contamination framework. In Advances in Neu- ral Information Processing Systems 33: Annual Confer- ence on Neural Information Processing Systems 2020, NeurlPS 2020, 2020.

---

Nearly Optimal Sample Complexity for LLP
A. Proofs for Section 3
This appendix contains the proofs for the theorems contained in the warmup section.
A.1. Proof of Theorem 3.1
In order to quantify the probability of error of Algorithm suppose
|
2
V
/ 2k
with ht- -/g Note that can rewrite
A
U3 h1 (213,))
A2
U3 h2(x,,)))
Also, by = 0 while E wi - - A. Set Ca(m, k)
mk 2
log 8. Then, from a standard concentration
inequality (Hoeffding) we have, with probability at least 5 over the random draw of Ss
|A1(S) - Cs(m,))
and
[A2(S) mkA I Cs(m,k)
so that, with the same probability,
[A)( S Cs(m,k) k)
and
A22(S) 2 mk| Ca(mm Cs(m,k),
the last inequality holding provided mk >
log 4.
A symmetric argument holds if h² h2- We conclude that if A
V
the total sample size -nk needed insure
P(h + h*) S is
1
n1
O
A
log
8
On the other hand, in the sequel we also show that when
A
<
V
2k
the sample size n = mk also satisfies
1
n= 0
log
Since -/2 < B (that is, the first bound better than the second) and only | 2 V 2k
this will show that the overall
sample size indeed satisfies
n 0
(min min
log
A
We now continue by analyzing the probability of error when Algorithm
relies on the sign of Q(S). under the condition
A
2E
Denote for brevity by (-)) the conditional probability P(- (((|B1,.... Bi.... Bm), that is, the probability on the labels conditioned on the values of the Zz all bags B, { Fj,k} in S.
Suppose 2 < 3/2 (which is implied by the condition |A| and k मनकक where ((t) is the cumulative
distribution function of the standard Gaussian distribution.
We say that B, discriminative for (1n, h2) at threshold 0
E,1 2 Bj,2
Bja2 ET,1 + 0,
for suitable 0- = 0(3,k, 5) > 0 that we set later on. Let us rewrite Q so as to single out discriminative and nondiscriminative bags:
Q =
[E < 1,,2- - ()(kk - 145) +
Σ
E - 0 < E,,1 S E,2](aa - -11)
j=1
[E,11 > E, + 07(1: - ka,) +
[E2 + 0 2 E,1 > E,2 - -ka,)
1=1
12

---

Nearly Optimal Sample Complexity for LLP
Assume hi* decision).
h1 We want then bound the probability that Q 2 0 (that is, the probability that we make the wrong
Now,
[E 2 132 - 0 - pb) 2
{ I E32 0}(aa; E 0/2)
[,, 0 < E,, E,,a 14))
{Ej² 0 < B21 S EE (ka; B,,1) {E > B,2 (B,, - 0/2 kaj)
[B > B,2 + 010 kaj)
[E +02 E,, B, - kaj)
I
{E + 2 E, > (52)(EE111 kay)
so that
P'Q 2 0 S (Q) 2)
where
m Q1 Σ
m
EE,1 S F,2 (E - 0/2) Σ
[E22 8 < B,1 S E32
j=1
i=1
+ Σ [E > E + ()(-,1111 0/2) + Σ (E + + 6 (2,1) j=1
being Eg kaj- E3,1 (conditionally) zero-mean random variable. Introduce the short-hands
m
mi Σ
F S 3,22 0) Σ
[E B,,2 + 0}
X7
m
>
[E - 0 B3 S B,2] Σ [E + 02 E₁₁ Ez,2)
m2
1=1
and note that the above quantities are fully determined by Bi..... Bm Also, my +
for all 0 2 0.
Consider the four sums defining Qı as aggregated in pairs according to the definition of my and m2 above. Observe that the random variables Vj.1 Uj.., Yj.k- for all such that E,,1 S E, or such that E,,1 > Ej,2 + are m, k-may conditionally independent Bernoulli random variables, each with its own bias. Hence we can apply standard concentration bounds (Hoeffding's inequality) to conclude that
m
m
P
E S E,,2 - 0}(E,,1 - 0/2) +
Σ [E
B32 + +- - -0/2) > h
/=1
m
m
P'
E S -- 0}E Σ Σ j=1
[E E,, + 0}H > m20/2++1 +t1
2(m, 0/2 12)
< cxp
mik
for all 1 > 0m2 Similarly,
213
TP' Σ
E
0 < E,1 S E,,
Σ 1=1
E2 +02 E,1 > E,21E > to I exp
m,k
for all f/2 > 0.
Therefore, in order to bound (P) 2 0), it suffices to select 4 and l2 in the above in such way that ( + l2 = -,, with the constraints t > 0/22 and t2 > 0, allowing us to conclude that
P'(Q 2 0) S exp (- 0 t2) + exp
2t
mak k:
m2k
13

---

Nearly Optimal Sample Complexity for LLP
The above constraints easily satisfied if my and my constant multiples of one another. For instance, suppose there exist positive constants e and 02 such that m, c,m, and e1 02 1. Then may set
= 4
t/
obtaining
c10mm
(-
(-cp0mm m
P (2 2 0) S exp
+ exp
(5)
8k
802k
which is of the form exp (- mm k
provided C1 and Cg are constants independent of m and O.
We expect to be able to set 0 to be of the form 0 = By lo via an anti-concentration argument.
Now we lower bound via anti-concentration the probability of drawing a bag B, that is discriminative for (41, Recall that = ([(( [x)] We can write
[E 3 + 03 + [E
E22 - 0}
Σ
(h1(z) hg(x)) 20 }
Σ BE
zEB,
Hence, we are left to lower bound the expectation of the indicators above. Now, the variables
Z = h1(2),)) h2(2),), i= 1....,k.
are i..d. random variables with range [-1, 1] and expectation A E [-1, 1]. Thus we are compelled to leverage anti- concentration inequalities for sum of [-1, vvvalued i.i.d. random variables.
Since we are working under the assumption A S 3/2 and k 2 क-(-1)3+ an easy route is to go through finite sample version of the Central Limit Theorem, and then rely on the anti-concentration standard normal variables. One version of Berry-Essseett 's theorem claims that for Σ = Σ X,, where XI,..., Xx are i.i.d. with zero mean, variance x² = E[x"), and finite third moment / = [[| we have
sup IP lovk) +(1) S
20
where (() is the cumulative distribution function of the standard Gaussian. Note that by convexity p 03. Moreover,
p 2 since in case X 1.
We have
k +P Σ Zz <0 -0
E [[ 2 E2, + 01 + E [[E,, E, 03} P
Zz 2 0
k
A) 2 KA
+
Σ (Z₁, A) < - )
KA
+ AA
2p
ovk
oVK
20 V/
KA
0 KA
ovk
ovk
V02k k
(since S 02))
KA
0 + 0+4A 4A
2
+
+ +
(6)
ovk
ovK
3
(since o²
A
8/2, by the assumption 2 < 8/2),
14

---

Nearly Optimal Sample Complexity for LLP
where
o== = -=)((
p p= Z,, -
We set 0 = | + kvk. With this setting of 0, if A 2 0 then +
(- 1- ov
(-1). On the other hand, if A < 0, then
(-
0th O -1). In both cases (ook))
2
66) 2 (
2 2(-1)/2
3k
the last inequality using l 2 4-(-1)0- This yields
E [ B22 0}] + [(E,, < E,,2 -00] 2 $ (-11/22.
Thus, on sample S made up of i..d bags, average, fraction of least m (-1) /2 bags will be discriminative threshold 0 || + V that is,
B Bm. [m1] 2 m& (21)
Since the bags are i.i.d,, the random variables {R 2 E3 + 0} + {E E32 0) are i.i.d. Bernoulli variables (w.r.t the random draws of B,....,,,, Bm)).. From standard multiplicative Chernoff bounds, this implies that
B B.. BDr m1 S m + (-1)) & exp
m $ (
16
In order to conclude, we get back (5). Combining with the above yields
[[[Q 2 0}} E [Q > 0,m,
4 Φ ((11)} EE {ml
s + *(-1))
m
4
Se 0 (00 + (m))
We want to make the above smaller than 6. It suffices to pick
m
1 +
log
f2
Now, observe how 0 depends on the separation parameter B3. Note that B =E[Z3,), and recall that 0² = B--2 22 We have
0
k + 2/Alovk
(k: 1)42 + 2/ +
1 + > B,
independent of the bias A (and in fact, we have equality to 3 if A 0). Thus the sample complexity mk becomes
n=o 0 (K- ( (1=
B log ! 1) =0 8
-0(min) (min
k
1 8
=
log
A
3
The case Q < 0 with ht = h2 treated similarly, since is completely symmetric. This proves the first part of Theorem 3.1
In order to prove the second half, consider the following simple problem. Let the input space X' binary, X (0, 1), and the hypothesis space H be H {h1, h2). where h1 ha X + [0, 1]. Let the marginal distribution of be Bernouli((12).
Moreover, given parameter B E [0, 1). the conditional distribution h (xx) n7xx) Ply = 1 x)) is
Ply 1| = 1) = 1/2 V3/2 Ply= = = 1/2 v3/2
=
if hh h1
1 00=
h. h2
15

---

Nearly Optimal Sample Complexity for LLP
Notice that this implies
1 PVy 1) 1)= P(y - x 1)
1
Ply 1|x 0) 0)=2
2
for both ht = /1 and h- h2. Moreover, for square loss,
[c(h)) - C(h2) = [x(((()) h2(x)) 1 (11 ((()))-2((1))+ 1 -
+2 (h)100) - h2(())² = B.
Consider an i..d. sample of m bags of size k:
S ([11,1, 21,2 F1,A), o1).... ..... ((Fm.1, 2m ................................ Fm.kk amm)
(B).01)
(Bm)
and any function à (S) - H that maps any such sample H. We consider the amount of information needed perform the inference of separating b1 from ha out of S through the standard tools of (Shannon) information theory. Let then equip h" with a prior distribution
h1 w.p. 1/2
h"
=
h2 w.p. 1/2
and view h itself as a random variable. Consider the mutual information T(h",T) Mt.. By the so-called data-processing inequality and the chain rule of mutual information we have
m
I(h M) S T(h"
Σ
Now, since (B),ac) is conditionally independent of a1), (B)-I,(()))))))1 given lt,, we also have, for all j.
I(h:; (B), a.)...)......................... ( I(h::
so that from the above we can write
T(h M) & m (B1,
Moreover, by Fano's 's inequality,
I(h h) 2 1 - E(P.))
where E() is the binary entropy function
Exx) x 100g2 x (1 x)) logz (1 - x).
and P. is the "probability of error" P. IP(h + h²).. If we stipulate that want the target excess risk 3 to be achieved with probability 2 1 5, with 8 1/2, this implies P. < 8 and I(h", h) 2 E()).
Putting together
1- E8) S mI(h", (B1, 01))
which immediately yields the lower bound
1- E(8)
m
(7)
I (Bi, a1))
This is sometimes phrased by saying that these three variables form Markov chain
(B.. (,,,,,,,,,,))) + h" + 9,),
sec, e.g., Chapter (Cover & Thomas, 2006).
16

---

Nearly Optimal Sample Complexity for LLP
We are then left with the problem of finding an upper bound on I(h*, (B1, or))). Using the chain rule of mutual information, together with Y(X;Y)= HYY (Y))x), where H denotes the Shannon entropy, we can write
( = 11hh((h;]] (1) +I(h";11 [B))
H(an [B)) Hai 11,
Now, since
Ply 1|2) Ply 1h" h1 (2) + P 1h" =h2l =/212))
1
Ply 1| h1, +)+ +
Ply = 1 1| h22 x)
2
2
independent E {0, I, the distribution a₁ given B1 will the distribution of (scaled) Binomial (k, 1/2), and its entropy H(1 B1) will be the same as the entropy of a Binomial 1/2).
The following theorem from (Adell et al., 2010) provides useful bounds on it.
Theorem A.1. Let X ~ (inomial p), and q 1 p. Then, for p 10.
H(X) = 2 logg (2Tekpq))) + 0 ( Ke
Thus,
1 (a1 [B)) (Tek +
Also, the following upper and lower bounds from (Harremoës, 2001) (Theorem 6 and Theorem 7 therein) on the entropy of a Poisson-Binomial distribution' PBin in terms of the entropy of related binomial distributions will be useful.
Theorem A.2. Let X ~ PBin(pi..... .Pk), set = Eim Pt, and Te Pmux J, where Praxx max; Pi- Let B
Binomial (ke n/k), and B Binomial (ki, p//) Then
1 logz (25Te((11111))) +0 1 HBB) H(X) 2 H(B) _ logz logz (2TeH(1- p/k)) +0
1 13
the equalities coming from Theorem A.I.
As for H (a1 B1),"), consider the following argument about the conditional distribution of a given B, and ht. Let B3 be a Boolean vector containing s ones and k zeroes. The position of these zeros and ones will be immaterial, for definiteness, let us visualize B2 as follows:
B = 11... .0...
(8)
Suppose h* h1, and let Y, and (² be the random variables counting the number of y4 1 in bag Bi among its first components, and among its last & components, respectively. Since h* = h1, we clearly have
y(()) 1 B) and y(() Binomial -s, s,1/2 B)
the two variables being independent. Moreover, ka Li=1 Di = y(e) + y,(*) has distribution
PBin (// 1/2 1/ - / 3/2 1/2 1/2- 1//2)
'( Adeell et al., 2010) also contains non-asymptotic upper and lower bounds, which are not reported here for brevity.
A Doisson-Binomae random variable with parameters Pi.-...PP PP is the sum of & independent Bernoulli random variables, where the Bernoulli variable has bias Pi-
17

---

Nearly Optimal Sample Complexity for LLP
When h 122 it is easy see that we simply have to swap v3/2 with - 3v/22 in the two binomials, that ka PBin(L/2-v//22... 1/2 1B2 /B/2.... 1/2 + 3/2)..
k-a
Consider the situation when 8 = Σj 2i is such that & E A, where
A = 8 k/2 -
v log k/2]
(9)
so that when - oo both and s diverge.
By Theorem A.2 (lower bound side), when ht* = h2 and E A we have
H(m 11)1) = H
Σ Jj = 8, ht* hn
1 2 log2
2Teeu11
(1-w))
m1 )) + -0 (
ki
2
where
k+ /3(2s - k)
b
p m== k//2//2
((2s-
1
and
H(ai (2) = 11 a Σ Tj = 8, h1 = l/2
1
(1-
412 ) + t
2
log2
2TeEuz
2
where
/3(2s - k)
2
#2 = k/2 - k/2s
1+ VB
Now, we observe that the condition E A implies
k/22 /Bv 11 k/2 VBVklogk?
and
ky = (kkk).
Moreover, from the inequality
x
11
x
2 a(11-a)1-11/6
x//a|
x//a|
holding for E (1/2, 1), and x 2
2a
we also have
I-a'
141
8
(1 4 (1 11- (1)) )
1
h1
4
V
and similarly,
P2
U2
9
(1
(1 8) 2) (1 (1-0 (11))
4
//2
Vk)
Putting the two entropies together, we then see that
1
E2 (( |s,h"]]
H(a) 11,
H(a2 s,,)))
2
[__8
1
1))
(1 (1-ō (11)
2 log2((2re)
logg
k
4
4
VT:
1
1
8
(1-0 Ō
[110
-0 (1
loga
k
4
4
4
vk)
1
8
))
(
1
logg
2Te
4
VT
18

---

Nearly Optimal Sample Complexity for LLP
Finally, we have
(a1 [Bi,h")=
E
En [H h,,h
e- Binoommkk.1/2)
Since P(E; Zi E E 2 1 1/k the above gives the lower bound
1 - +))
(1 )) -ō
1
H(a1 ((a1)Bi,h")
log2
2Tee k
Vk)
l grows large.
Piecing together and simplifying results in
1
2 k 1 8) -1-4)
(1))
T(h:: (1)) S (Tek/2)
log2
logg(1 (1 8) Ô
2
2
Vkl
which is of the form
8 8+0 δ
VT
when B - 0 and & is large. When & is large enough, the above becomes smaller than 8/2. The lower bound on the number of bags is then of the form
m Ω (+ (1-2 E()
3
independent of k. when & is large enough, and / is small constant (independent of k). The sample size mkk must thus scale linearly with k. In particular,
= 12 k(1 - 8(61))
B
This concludes the proof.
B. Proofs and further results for Section
This appendix contains the proof of Theorem 4.1, well the extension of the ERM estimator in the case where p and [[)( are unknown.
B.1. Proof of Theorem 4.1: Known and B[h(x)]
First, recall the notation introduced in the main body. For bag zj (B3; az), and function h E H. we set
(y(h)
Mays),
E,(h) = Σ May,)) [E[)
0ij = a, - P
where p= pz)( We also assumed that E[](()), for h E H. and are known. Then, for bag 2, (By. az), recall the definition clipped (debiased) square loss
(h, 21) (kā (kāj- - Eb)))) 2 Gy(h) [E[h(x)]-2) -p) xz(h)
a(h)
where
Gh(h) = kkā - -
-E,()) S 8h log
for suitable value of parameter 0 0, and then its population version
2% = E2 [eS 2)]
19

---

Nearly Optimal Sample Complexity for LLP
Also, define the non-clipped version of the loss at the bag level:
E(h, 2z) = (kä, [m)))) + (p))
and note that its population counterpart Lx(h) Ex [e(h, 2)] satisfies
(b(h) [(h).
In order to prove the above claim, set for brevity
U2 - Mj p E|h(2)) - h((r))))
for [k]. Then observe that E(h, 22) can be rewritten as ((h, zj) = (Zi-i u1)² [B[[(x]] p)² where the variables V/ are i.i.d. with E(us] 0.
Therefore
k
27
Cb(h)
= k
E
Σ
U1
+
(E[h(z)] - =p)²
1=1
k
k
=
E
E
Σ
Uj
+ [B[M(x=) - p))
= B[oi] + (E[M(x)] p)²
(using the fact that the variables us are zero-mean and independent)
Var - h(z,,))))))))())0)((()())) + (B[A(z)] -p) p)²
B[(y - h(x)))
= [(h),
as anticipated.
In order to achieve fast rates, we will investigate loss differences. This is by now standard observation that dates back to least (Massart, 2000; Mendelson, 2002), See also (Bartlett al., 2005).
Now, for any pair h1, f22 E H. we have
(h1h - (12) =
- Ez, [X,(hi) ((61)-X,p00 15000---X(00)--ddd----aaa------1 (((()))))))))))))) E2, [e(hz 24) 2()2, - ((bb))))))((((//////a+x////////1 [(h1) L(h2) + E.,
a(he)l
so that
(11) - (22( - (C(hi) - C(h2))) S En, X2 (h)))
< 4h E.g
(h1) + G (ha)
(since |X, (hr)l and XX, (h2) are both bounded by 44)
< 8k0
(10)
(since E., [G, and Ex, [G)( are both > 0).
20

---

Nearly Optimal Sample Complexity for LLP
Moreover,
-
= -X -((z)) 2
((x((hn) (xx(hi)-x1(1a)) haap://:AAAAaaaaoaaaaooaaaooaaa-
2
alhra)
S 4 (x)(a)))))())))) G,(ha)G, (h2) + -,
+ +4 aaa(())) -a(h2))
(using (a (a+b+c++ d)² s 4(a² + 12 + + de))
Now, define 7(h1, h2) (x())(x)= h2(2)) We have
(a(bi) -a(h)))
(I(() (x)) 1)² (1(((((a(x)) -p)
(E(M(())] - E[h2(1)]) 2
[x]] + B[h2(x)]] - 2p) )
(B]h)()) - h12(1))) -ha())))))))))
2
[[ (x)) (x)] B(2(21) 2p)) 2
$ 4y(11,
Taking the expectation then gives
E
( (e (h1,))) - -E
(E (h2.,)))
(h2,
4E
(x,(th)) (X,())))(((ba)) (((h)),((h2)
+ +E
4B (g(h))))((h)GGtbab)))
+ 167(h1,11)
<
4E
(x,(k)) (1( ((())))))
+ 1288220 + 1677(1,,11)
4
(E,(knz) - E1( (2kā, E,(hi) E,((2)) G C,(h)) + 128k + 167((1,, h2)
E
4
E
(B,(bb) (h2)) ) (Kāā, (h1)) kkā (h2) (((b)))((bb))
+ 1288 + (22)
128
((,((h))) (h2)
2 + 128k20 16 122)
E
log 0
2
128 Var (1(x)) - h2(xx))
log 0
+ 12 + 16 h2)
< 144 ((1,, 112) log 128129
(11)
Further, recalling that h is the best-in-class hypothesis, and ht the Bayes predictor h((x) = IP(y = 1/x), we observe
21

---

Nearly Optimal Sample Complexity for LLP
that, for any h H. we can write
7(,,h' = -
Bi(((()) - - ((())())))))(()))))-)-))))))))-) (x)))
C(h) -=
(since [(h1) (h2)) = ([( -()))))))))())))(((((())) -(()))
for any h1 h2)
S -h)) -(th)--(h)) -(hh) + (((h(()) - [[(h(x)) (z)))
(from the Cauchy-Schwarz inequality)
(h) -(h))))))))))r))) + 2// Ri*) / (h,
Solving for (h, h²),, and setting for brevity AL [(h)- L(h*), this implies
(h, h-) S AC + 2y(h", (h""h"")) + 2/ (r h²) + t AC
Using the inequality va +b vā + b/(2 C). with a = =h² ([hh"I ())) we then have Th, S 4,,h" h²) 2AC
Combined with (11) this gives, for any h E H,
8 ) =0 -0(((t,)))++()) -(h)) 0 + k28
E
(12)
Finally, because of the explicit clipping, we also have, deterministically.
(h,, 2z) (h2,, S log + 1.
(13)
Consider now the difference of bag-level clipped losses
e ((,,Ti";;z))) = (h, (e((t,,,)) ;z))
and define the empirical measure
(hh,h'::) 1
1 (h, 21)
1 Σ (h 22)
e 22)))
m
and the ERM estimator
m
m eh, 2z)
io 7 = arg min
Σ j=1
(h,
arg min NEW m. j=l
NER m
Recall that we denote by Hy the set of 3-suboptimal hypotheses
Hg {he feE. H L(h) 2 2(h)) +3]
We introduce the shorthands
AC R:)) (h) LB(T1)) ALB(h, Lb(h) - Lis(h"))
where, we recall, (h) = E.y [h,, 2,)], and (b( = B.,, [e(h, 2,)].
22

---

Nearly Optimal Sample Complexity for LLP
Also recall that Lb(h) (1). We can write
hh E Ho3 }
- hh E Ha (1 kt;))
= {h E Ha (h,h' AC h-) - 8 (h',h';)) h
< 3h E Ha (h, h0)) - (1, 5) > ALs(h, (a)(,,(i)-aa -Sh
(14)
(since (h,", Rt; S) and, because of (10), (h, Ti-) (²) 2 AL Tin) 8k0).
Since we assumed [H] < oo, from (14) we can write
{ n E H $
Σ
P - ACs(h, 8K0
hEHs
Our setting
13
0 =
16k²
implies
4C h-) 8k0 2 (C (2(2)) 2 (h,(2,n*)/2
and ==0=0(03) (h))) in the variance bound (12), in both cases using the fact that h Hg. Moreover, in (13),
(h, 2g) = O log A:
(15)
3
From (12) and (15), using the standard Bernstein inequality each individual h Hgs and setting for brevity μ u(h)
AB, ht), we can write
p p(hh Ha) s Σ
2 1/2)
heKe
m²² 2²2x2/8
Σ exp
" mm0((((0 1) $ $
O (plog' &
mp²/88
Σ exp hg
0 (17 h+) + 11) lo) &
Since the function f - the fraction in the exponential is simply obtained by replacing μ with B. This yields
is increasing in μ for any y 2 0, and in our μ 2 B for any h Hgs lower bound on
7+
P p(ñ Hoes |xplexp
m h+) + 3)log))))) 5/)
If we want the right-hand side to be less than 5 it then suffices to have
m (7(00,, ,h") + 3)
Hal
log
In particular, in the realizable case, we have 7hh,,"" hh) = 0. yielding the bound
log
B
0
log
This concludes the proof.
23

---

Nearly Optimal Sample Complexity for LLP
B.2. Proof of Theorem 4.1: Unknown p and Elh(a))]
When p and E [x))] are unknown, we simply split the bags into my ma bags, and hence the dataset into two parts:
S = ((x1,1,..., #1,k), (( Lmm k) Otm))
(fmi+1,1,.... Tma +1,k), 01m++1)--- (amms fmitmmz.k) Orris +m22
82
then estimate p and E[h(2)) on the second half S.. Specifically,
m + m2
p
02
12
j=ma +1
and
my +2
E[h(z)] = mzk
Σ
Σ
h(zzz)
j=mi
Then, for j E [m1]] set
(h) Σ Maya),, = -EE[(()), =;
and re-define the clipped bag-level square loss as
(kāā - -R,((h) Gy(h) + [B(h(x)) D)
(h, 21) 1.
8,(6)
a(h)
where now
18k log 6
Gy(h)
Ikā ( V
for some value of parameter > that will be determined later on.
Note that
Ikā, - [h)] = Ikay - kp (b) + AB[M))]]
= |k((a - p) + k:p /) [=()(=)] - (b)))) A(E((())) B[(()))
< klaj p A E[h(z)] - E,(h) klp क [BB]((z)] - [[(())]]
Hence, for all 2 0, and any fixed E H. and j E [m1].
[ [h)) 2 } {kloz - p [E(((x)] (h)) 2 11 + Alp 2 12 {1++(11()))))) B[A(=)]] 2 2(3).
where t t + to = t.. We set
8k log 6 0
k
4 =
1/ = 13 =
log 0
2mz
to conclude from the standard Hoeffding's 's inequality that, for fixed j E |mmm).
{ kla, p - 2 t }}
0
E
and, taking expectation over the generation of S2.
B k[ -P 2 0
E - 2 {
24

---

Nearly Optimal Sample Complexity for LLP
Since 1 + 22 + S v 18k log é. this implies
[[G,(b)] S 0.
for each individual h H. and j [m=]- We now need to proceed with bias-variance tradeoff, which is similar to, but a bit more involved than the one contained in Section B.I.
We still define the unclipped version of the loss at the bag level as in Section B.1, but now we need to factor in the extra bias coming from the estimators from S2. In particular, for any pair hn, hr E H. we have
(b1) - (h2) = BB,, [x(t)) (,(h)) + a(h)) - a(ha)) [x((t - (k, @(hi) a(h2) (h11) + (12))
IEs;
= 22,
8,0 x,(11) + x,(11) - X,(12) + xy(h2) 81(12)
+ +(hh)) - a(hi) + a(h1) - a(h2) + al(b2) - -(h2)) -
+ (8,(0)))((h))))
= =m,, [e(h1,2)) z5) - -((h2, 23) 85 + (,(b2)
+ +B, 8 - (,(1h) + X,( -2,(22 + a(h1) a(h1)) + t(h2)) a(h2)
[(hi) - L(h2) + Eas ( + ((1()),,(ha)
+ BBE A (22 -xx + sa(h, 122 h2))
where we for brevity
A8,(h,, h2) = X,(h1) - 82(h2), , Aā(h h2) = ä(hr) - a(hz),
AX,(h1, = X,(11) - (1,())) Aa(hi,)t)) = a(h1) - -a(12).
Thus
(h1( - (h2) - (E(h)) - C(h2))) IBn, [1,, (11) Gry + 18, G3
Bs, (h1, h2) - 4x,(11, heal +E,, AAā(h, h2) Sa(h),
(16)
Now, in Section B.1,
E2, (() + (h2) ((y2)) < 8kk
(17)
Moreover, for any hi, f2..
1 - (h2) (002))EE,,) (bi)) (2ka, 2kp (h1) (b)))) + (x]h + (B(he(a)))
AX, h2)
k
(X,(h1, = Te
- (1,(
(2kce, - -kkp- - (hi) (h2)))) + + kB(h2()))
so that
A (11, - A (h)
1 k
(Ba(he) Ez(bi)) (2k(p D) + kxB(ii - E[)( + A(B(ha(<))] E(ha(x))))
25

---

Nearly Optimal Sample Complexity for LLP
and
| (M,((1111)) - AX, h2)l
$ (12) B, (h1) (2 (C))) - [[(2(=)])
(18)
From Hoeffding's inequality we know that the sum of the three absolute values in the second factor is overall bounded by
6
log m2k 8
with probability 2 1 over the random draw of S2. On the other hand, by convexity,
B,y (b(b (E,( V Ez, (B, -B,(h))
(kry(h2, h2)
Similarly, if we set for short
AE = -
A E = E[h2(=]]] - [[)]
can write
Aā(hi, h2) = (Aî A 2p Blh -[)))))) (1h)()))) + B(25 [[)] - B B(h2(1)))
Aa(h1,h2) = A E(h2 - E(hg(x))
Hence
Aā(h1, h22) - Aa(h1.h h22
(AE- - A 1E) 26 22- -Ba0) p) (x]) E[h, + (1[(2((z) - (x))
which implies
Aa h2) Aa h2)
AE| 25 [x)] - [x)) +|A E (21p pl + [[[h1())] - E[h (x)]1 + [[[h2(x)] - B(h2(+)1l)
s A AE + rhh,, h2)
2 - pl + [x)] (x)] [x)] -
(19)
where in the last step we used the fact that
AE ((]hi()))))))))))))))()((( h2(x))l S (a(hi,
As before, Hoeffding's inequality allows us to see that the sum of the three absolute values in the second term overall bounded by
6 log 8
m2 k
with probability& 2 1 - d over the random draw of Sz. Moreover, since Var (h2(x) - h1(())) 7(11, h2), Bernstein's 's inequality shows that with the same probability we also have
27(h1, log 8 3m3 k my K
1
AE
log 8
We piece together as in (16), and take a union bound over by, h2 E H. We conclude that with probability 2 1 - over S2,
((11,,2) h2)
[7 1
[76]
(Cg) (22 (C(h, -(h2)) < 8k0 + 0
log
log
(20)
m2
8
m2
26

---

Nearly Optimal Sample Complexity for LLP
which is the counterpart of (10).
As in Section B.I, we continue by bounding the second moment. We have
(e(h)12)) - -E 21)²
(8)(1))(((h)) - X((hk))(((e))+(((MM - -a(he)) 2
(1(1z)= - xX) + xz(hz) - (hy
+ +ā(hi1 - - - aa(h)) a(h2)) - (((())))((++++x((())))))) 2
(3((1) + a(h)) (h2 - a(h2) + (81 - Ax,(h1,12) + AT(hi h2) - ha(
((1 (b2))
2
<
X,(h))+ + a(h1) - (Ky(1a) - a(h2)
+4
A h2) - AX,(h1,
+4 Aa(hi, Aa(h),
(
(17)
(1I1)
2
+4 4 &
(T
(using (a d)² s 4(a² + 6² + c² + +d))
At this point, we take expectation w.r.t. Zj, and use past calculations. In particular, from (11)
B,, (()) < 144 1441, log + 128120
Moreover, from the arguments surrounding Eq. (18), with probability at least 5 over Sg.
8y(11, h2)
Eg, [(11]] S
log
122
Likewise, from the arguments surrounding Eq. (19), with probability at least - 8 over S2, 16y(h, h2)
log 1
(
1
+ 16 h2)
log 6 8
(111) <
+
log
m2
3mz
8)
m2
7(1,, h2)
=
log g
+
log
ma
m2 k
where we repeatedly used the upper bound (a + 6)² < 2(a² +b²).
Finally, from the same argument as in (17),
(2,(h))),(h)) + (,(h)) X,
E,, [IV) $ E,,
x 2E,, ((Kg(hr)) (Gyd)) + (he) &C
< 64k
27

---

Nearly Optimal Sample Complexity for LLP
Combining the above terms, and taking a union bound over N1, A22 H. we have shown that, with probability at least 1 8 over S2,
Bsy (((h))))))(((t)))))) - -0((hh log 2 r(h1, h2)
- (h2, (h2)
log 1 + m2 h.
{m)) log 5)
m2 k
which is the counterpart of (11).
As for the counterpart of (13), we also have deterministically
6 1e (h1, 2z) (112, 25)1 18 18log +
From this point on, we follow the proof of Section B.1 by setting h1 = h, and h2 h Recall that for all h E He. the quantity 7(h h") can be upper bounded as
Th, S 47 + +2AC(h,77)
where >" = =>(h",,'' and Ac(h,"*) L(h) - C(h'). We then set
9
0
16h.2
in Section B.1. This implies
- (4))))--(000) c(+)))
3
+ +0(1
(VV
7"h 7"* AC Jx*)
log
[-
+
log
2k:
112
m2 K
8
and
(E(h)) 1 (h2, 23) 2)) =0 (1' ( Achh,h")) log
+ (7" + Achhh"))
log +m1)
1 ))
Ez,
log
3
m2
m2 k
and
[e,, 2;) - (12, =0 00
holding with probability 2 1 over the generation of S2. Now if, for all h E H3.
m2 S 7" + AL(h,TT*)
[ log
(AL(h, 11))2
for appropriate constants hidden in the 2-notation, we see that the bias bound satisfies
8
+0
3* + AC(h,
log
H
log
H..
AC(h, h())
- Ac(h
3
2k
m2
8
m22 K
4
so that, when h E H,g.
ALB(h,
9
(1
o
7" + AC(h,
log
[H]
+
log
[.]
>
(h) (C(h) - c(h²))
2k
Ma
8
m2 K
8
Moreover, under the same condition on m2,
[ (e((h))))) - (h2, ((12,22)) -0 - 0(1 ALs(h, (b)))))))) log b
Ez,
(AC(h,hT)))
28

---

Nearly Optimal Sample Complexity for LLP
We proceed in Section B.1 with an application of Bernstein's inequality on the generation of S1. We set for brevity
μ = uuh) = (CB(h, ht)). We can write
P h E H&p s
Σ
P
( 2 11/4)
bEHa
m /32
Σ exp
mi ((1 + 10 #/ + n²²
+ mi (wlog
b
m1 /32
Σ exp bE
(7* + #) 3/ + 122)
This time we use the fact that the function μ yAtnAtp² is increasing in 2 0 for any A, 2 0. Since 2 B, this gives
P E Ho)s S [Hal exp (- mi /2/32
mi1 /2/32
176gl exp (To
0 (
+ 8) + 322)
((r + 33 $
Making the right-hand side smaller than gives
(7* 1-+3))00
1og
|743l )
m1
log
g²
Since the condition m2 is satisfied for all h E Hg by selecting
7- +
3
H
m2 O
log
32
the overall sample complexity is
(
(7* ( + 3)
log
17| 8
m = m1 + m2 =
log
g2
This concludes the proof.
Remark B.1. Despite not shown in the above proof, one can easily see that the dependence on |P(] in m2 can be replaced by a dependence on [PL]] thus the overall sample complexity mi + m2 is indeed only depending on [P(pl-
C. Proofs for Section
In this section detail the proof of Theorem 5.1. For the analysis, require the definition of smooth function along with some basic properties that we recall now. A function f R2d -> IR is said to be ç-smooth (with respect to the Euclidean norm || [D if its gradient is (-Lipschitz, namely if
V x. y Edd
[V - -V(())-V[() S C|| - yll-
For a twice continuously-diffeeeniia convex function f, a sufficient condition for (-smoothness is that A V²J(x) 37 for all x E RRd. Finally, a smooth function satisfies the so-called descent lemma, from which it follows that
V
[[] < f(x) - f(x"),
where x" E IR is a global minimizer of f.
For the sake of this section, let us introduce some short-hand notation:
7, = ((,,22
29

---

Nearly Optimal Sample Complexity for LLP
and
9km Pw + Py)
We begin the analysis by establishing that the losses Eg underlying Algorithm are indeed convex and smooth.
Lemma C.1. For all the loss Eg is convex, nonnegative and (-smooth, with Ç (k02 + 1)p
Proof. Convexity and nonnegativity are immediate. To see the claim about smoothness, note that E is either identically zero if || Pal > Opz, in which case it is smooth, or is identical to the function {(; =ÿ) whenever || 1z S Opn- In the latter case, the Hessian
(1)( V2e(w, 23) k(ūj px) p²z) + Pull
whose eigenvalues are upper bounded by k 1= + || S (k02 + +1)p²
Next, we demonstrate that expectation, the truncated losses f, are nearly unbiased estimates of the population loss C. The bias in this estimation controlled by the truncation threshold 0.
Lemma C.2. Suppose 0 /8log(1/0)/k: Then for all j and such that ||m]|| S Pw, one has
9k(ppP2 + p.) s [[]] [(w) S 0.
Proof. First, we note that [w)] = [(w); this follows directly from Equation (3). Further, for all w such that ||w||| S P we have ( S (k(Pu: + py))² hence
[le)(w)) [[])(w)] B(e,(w) {1E5, Mzll 0pz} S 9kk(pup P= + pb)2 PP P( - uw 0pz)
To bound the probability on the right-hand side, note that テ Me is an average of k: i.i.d. zero-mean random vectors bounded by Pa; from a vector Hoeffding bound (e.g., Boucheron et al., 2013, Example 6.3) it is straightforward to derive that for any e 2 2pz/ /p/
ke²
P(1 - -Mell > 5) exp
8p
Thus, for any 0 2 / / /llgg(//))/k
P [| P(1Ez
Mzll > 8pz) S exx((_ s 58
and therefore
[l(r(w)] - [[T( < 9k(puP> + p5)
which concludes the proof.
Henceforth, we let Ç = (A:02 + 1) and /8 //loo(1//8)/. Then by Lemma C. 1, the losses &, are convex, nonnegative
and {-smooth.
Lemma C.3. For 0 < 17 5 1 1/() and for any w² Rd
- -((())) S || 2(T) Σ (,(w))
Σ
"
j=1
Proof. Fix any w" E Rd. By a standard regret bound for online gradient descent with convex losses E, (e.g., Shalev-Shwartz Ben-David, 2014; Hazan al., 2016), we have
m
|ww
1|2
17 m
> (C)(W))) - [[((w)) <
Ve,
(1,)
2n
2
1=1
==1
30

---

Nearly Optimal Sample Complexity for LLP
Since Ey is nonnegative and (-smooth, it follows that (W,((w;)) (w,) Thus,
11
- -((())-((("))
-
+
([)(w)) - (y(w")) + Sn Σ (((=).
21
==1
2=1
==1
Rearranging terms, we obtain
Σ -
-
100 2my (n)
+ C1
((w")
CT
We conclude the proof by using 1iς I to upper bound the right-hand side.
We are now ready to prove Theorem 5.1.
Proof of Theorem 5.1. From Lemma C.3 we have
- L
Σ ==1
2Çn
Σ 1=1
E (w
On the other hand, from Lemma C.2, we know that
[[,(( E[[(w))) 9k(pwPo + p2)
(since wj is independent of the j'th bag) and
[((((w)) S L(w") 5 LL. L*
Putting together, dividing through by m, and using the convexity of [()) obtain
m
[[[((m))] L(w") S
((w,) - [(w²)
< 9k(pupx + +p))20 + Pre
+ +CyLL*
17m.
Optimizing the bound with respect to 17 E (0, 2 we can obtain
4Cp²
8Cp2
E[C(Wm)) - [(w")(ww=)))))))))" < 9k(p + p.) +
for choice of stepsize 17 min(pw/ //t///2(mmm/____ 1/())) (This is shown by considering two cases, according to whether L* < 2Cpp./m or not.) To conclude, recalling that 0 = (8loog1/5)/// and
Ç ç= (k02 + 1)p² = (8 log(1 + 1)p² & 10p² (1/8)
we have obtained the bound:
40p log(1/8) +
80L* pE.2 log(1
E E[C( [[]() L(w") S 9k(ppp= p.)38
m
22 Setting 8 Ikm 12, obtain
p2pp (P2P
L P
B[[(w.)) - L(w") =
+
Equating the right-hand side to B, and solving for m gives the claimed result.
31

---

Nearly Optimal Sample Complexity for LLP
D. Experiment details and additional results
We include here further details about our experiments that have been omitted from the main body of the paper.
Datasets. We use the following datassts::
MNIST Even Odd: MNIST is a digit classification dataset consisting of 60,000 training examples and 10,000 test examples. Each image in the data is 28 x 28 grayscale image. We replace the original labels by the parity of the digit. That is, even digits have label O, while odd digits have label 1. No other processing is performed on MNIST.
CIFAR-10 10 Animal vs Machine: CIFAR-10 is dataset where the goal is to classify images into one of 10 categories consisting of 50,000 training examples and 10,000 test examples. Each image in the data is a 32 x 32 three channel image. We replace the original labels by whether they are an animal or machine. That is, the classes 'bird', 'cat', 'deer', 'dog', 'frog' and "horse" are all mapped label 0, while classes 'airplane", "automobile", 'ship', and 'truck' are mapped to label 1. No other processing is performed on CIFAR-10.
Higgs: The Higgs dataset consists of Monte-Carlo simulated particle accelerator data, where the goal is to distinguish between processes that create Higgs bosons and that do not. Each example has 28 features consisting of raw simulated measurements and several human-designed higher level features. The Higgs dataset has 1 11,000,000 examples. We use the first 10,000 examples as test data, and the remaining examples as training data.
Adult: The Adult dataset derived from the US Census and the goal is to predict whether an individual's annual income exceeds $50k per year. The data contains 32,561 training examples and 16,281 examples. Each example consists of 14 features: numerical features 'age', 'fnlwgt', 'education- 'capital- gain', 'captial-loss', thours-per-wedt categorical features 'workclass', 'education', 'marital-status', 'occupation', 'relationship', 'race', 'sex', and 'native-country. We one-hot encode each categorical feature and shift and rescale each numerical feature so that its values fall in the interval [0, 1].
and
Models.
We use the following models:
CNN for MNIST and CIFAR-1O: For both MNIST and CIFAR-10, 10, we use the following CNN architecture:
A convolution layer with 32 filters, x 3 kernel, and ReLU activation.
A max pooling layer with 2 x 2 window and stride.
A convolution layer with 64 filters, x 3 kernel, and ReLU activation.
A max pooling layer with x 2 window and stride.
A dropout layer with 50% drop rate.
A fully connected layer with single output value.
Higgs Model:
We implement the same deep network model proposed by Baldi et al. (2014) (and also used by Busa-Fekete al. (2023)), which consists of four fully connected hidden layers each with 300 units and relu activations, followed by fully connected output layer with single neuron.
Adult Model:
We implement a simple neural network consisting of a single hidden layer with 32 neurons and single output
neuron.
Aggregate Losses. Next we describe the aggregate losses used and several important implementation details.
Ours: We simply use the unclipped version of our proposed loss given in (2) together with the implementation details described below for estimating [z](z)) and p.
Li et al.: We use the loss
1 1/K0 ka -ta-Inte 1 h(x)
2
(n B, = k
-h(x) - (I: - 1). (E[((x) p)
zEB
32

---

Nearly Optimal Sample Complexity for LLP
together with the same implementation strategy for estimating [[](())] and p.
VanillaSQ and VanillaCE: For bag B with label proportion let à = 1 EZeB h(z) denote the model's 's average prediction on B. Then VANILLASQ is (á - a)?, while VANILLACE is (á a.), where (0. = ylog(() - (1 y) log(1 - () is
the binary cross-entropy loss.
EasyLLP: Easy LLP corresponds to the loss
(h,svLLP(h,Baa)) B,a) 1 Σ (wi Lee (h(x)) + wa Lee (k(x).)))))
1
k aEB
where W1 ko (Ic 1 and We k) (k: 1)(1 pp).
p). We estimate p in the same way described below.
Implementation Details: The three aggregate losses OURS, LI AL.,, and EASYLLP all require access p (e [v] In all cases, estimate by taking the average label on the complete training data (which is equivalent to averaging the bag label proportions). The losses OURS and LI ET AL. both involve the average prediction of the current model h, [[)( Given a minibatch that contains several bags, when computing the loss estimates on bag i, we estimate [=]) to be the model's average prediction on the other bags. In particular, this provides an unbiased estimate [x)( that is uncorrelated with the other terms in the loss definition, which is important since correlations could eliminate the variance reduction achieved by the loss.
Additional Results. Figure 3 shows our results on all datasets, including Adult.
33

---

Nearly Optimal Sample Complexity for LLP
0.95
CIFAR-10 Animal vs Machine 20 epochs
0,95
CIFAR-10 Animal Machine epochs
0.90
0.90
0.85
accuracy
0.80
accuracy
0.80
0.75
0.75
EasyLLP
EasyLLP
0.70
VanillaCE
0.70
VanillaCE
0.65
VanillaSQ
0.65
VanillaSQ
et al.
et
0.60
Ours
0.60
0.55
2
2a
2
2
2
2
2
27
2
29
2
2
2
2
2
2
2
2
2
2
bag size
bag size
Higgs epochs
Higgs 50 epochs
0.80
0.80
0.75
0.75
accuracy
0.70
accuracy
0.65
0.65
EasyLLP VanillaCE
EasyLLP
0.60
0.60
VanillaCE
VanillaSQ
VanillaSQ
0.55
Li al.
0.55
el.
Ours
Ours
0.50
0.50
29
2
2
2
2
26
2
2
2
2
2
2
2
2
2
2
2'
29
bag
bag
1.00
MNIST Even Odd 20 epochs
MNIST Even Odd 200 epochs
1.000
0.95
0.975
accuracy
0.90
accuracy
0.925
0.85
EasyLLP
0.900
EasyLLP VanillaCE
VanillaCE
VanillaSQ
VanillaSQ
0.80
et all
0.850
Li et al.
Ours
Ours
0.75
0.825
2
2
26
2a
2
24
2
2
bag size
bag size
Adult epachs
Adult 200 epochs
0.86
0.84
0.84
accuracy
accuracy
0.80
0.80
0.78
EasyLLP
0.78
EasyLLP
VanillaCE
Vanilla
0.76
VanillaSQ
0.76
Vanilla
et
0.74
0.74
Ours
Ours
0.72
0.72
2
2
23
2
2
2 28
2
2
2
2
2 size
2
27
2
bag size
bag
Figure Plots showing the final test accuracy of models trained on cach dataset as function of the LLP bag size and number of training epochs. Error bars show standard error in the mean 10 repetitions. Each data point represents the accuracy achieved by learning rate tuned for that bag size and loss.
34


Reviews:
[{"review_id": "32xkgiH2Zc", "reviewer": "Reviewer_YpnD", "summary": "The paper presents a theoretical analysis for the problem of learning with label proportions (LLP) where training examples are grouped into “bags” and only the aggregate label proportion of each bag is observed (rather than individual labels). The authors propose a theoretical analysis of LLP under the square loss, proving nearly optimal sample complexity results. Algorithmically, the paper introduces carefully designed variants of standard learning methods (Empirical Risk Minimization and Stochastic Gradient Descent) equipped with variance-reduction techniques.\n\n## update after rebuttal\nThanks to the authors for the clarifying answers. I am still inclined to keep the recommendation to weak accept as the paper is still largely suited for a journal publication given the it is largely based on the proofs in the appendix and requires an appropriate scrutiny.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Claim in LL. 190-195 when $\\Delta$ and $\\beta$ are unknown + absence of proof in Appendix B.2.\n\nAs quickly mentioned in L. 195-196, Appendix B.2 contains a proof of a similar statement that applies indeed to a harder situation (the one in Thm 4.1), where $E[h(x)]$ and $E[h^*(x)]$ are unknown. The idea here was just to point out that an argument similar to (but simpler than) the one contained in Appendix B.2 applies to the scenario of Thm 3.1. We will better clarify this  in the paper. \n\n- Claims in LL. 228-232 on how to estimate $E[h(x)]$ and $E[h^*(x)]$ from unlabeled data + “when bag size becomes larger, this estimate would become worse”.\n\nFirst, our claim contains a typo, and we apologize for that. Whereas $E[h(x)]$ only needs unlabeled data to be estimated, our estimate for $E[h^*(x)]$ makes use of the label proportions (that is, the aggregate labels). To estimate $E[h(x)]$, first observe that LLP does not hide the $x$ within each bag from us, so we have many i.i.d. feature vectors to evaluate $h$ on. This observation also applies to the estimation of $\\Delta$ and $\\beta$ in Thm 3.1. It is important to observe that the accuracy of these estimates only depends on the total number of samples $n$, rather than the total number of bags $m$. So, no, the estimate does not become worse when the bag size gets larger.\n\nTo estimate $E[h^*(x)]$, we use the fact that for a bag with label proportion $\\alpha$, we have that \n\n$\\qquad E[\\alpha] = E[(y_1 + … + y_k) / k] = E[(h^*(x_1) + … + h^*(x_k)] / k] = E[h^*(x)] = p .$\n\nSo, by averaging the $\\alpha$ values across many bags, we get an accurate estimate of $E[h^*(x)]$. Again, it is important to observe that this estimate does not degrade as the bag size $k$ gets larger, as its accuracy only depends on the number of samples $n$, instead of the number of bags $m$. Another way to see this is that the LLP data provides a collection of $m$ i.i.d. sums $\\sum_i y_i$, each made up of $k$ terms. Now, an i.i.d. sum of i.i.d. variables just gives a bigger sum of i.i.d. variables, so we are again able to accurately estimate  $E[h^*(x)]$ with an accuracy that only depends on the total number of samples $n = m\\times k$, instead of the total number of bags $m$.\n\nThe way we made this work in Appendix B.2 is to simply separate the training set into two independent subsets, the first one for training and the second one for estimating $E[h(x)]$ and $E[h^*(x)]$. The accuracy at which $E[h(x)]$ and $E[h^*(x)]$ are estimated depending on $n$, not on $m$. So, even in this case, at a fixed $n$, the estimate does not become worse as the bag size gets larger. We will make all the above clearer in the main body of the paper. \n\n- On the significance of the bound improvements, $k^2/\\beta^2$ vs. $k/\\beta^2$, etc. \n\nWe have to respectfully disagree on this point … . It is just the large bag size scenario that matters the most in practice. You may view this as akin to interplay between privacy (the bigger $k$ the more “private” the labels are) and utility (the regret bound $\\beta$). Please see also the response to Reviewer UVyu about motivations.\n\n- On incrementality of the analysis. \n\nWhat we solved here was essentially stated as an open question by both Busa-Fekete et al. (2023), and Li et al. (2024) – see, e.g., the “Discussion” section in Li et al. This by itself should perhaps suggest that our work cannot be considered incremental . . .  . Technically, the sample complexity analysis is fairly different from Busa-Fekete et al., and closer to Li et al., but more involved, due to the effort to reduce the variance.\n\n- On the focus on square loss and the fact that squared error/regret does not directly translate into 0-1 classification error.\n\nObserve that we allow our models $h$ to have output in the interval $[0,1]$. As a special case, we can restrict the predictions of the models to be $0$ or $1$, making the square loss equivalent to the zero-one loss. Then our loss estimates allow one to estimate directly the zero-one loss of the model. We do not emphasize this in the paper because the zero-one loss is difficult to optimize computationally. But in fact, our Thm 4.1 about ERM seamlessly applies to 0/1 loss regret as well. \n\n- Empirical results mostly on simulated LLP scenarios.\n\nWe agree that including datasets with natively aggregated labels would be interesting. Unfortunately, most modern large-scale aggregated datasets (originating from online advertising) are proprietary. Yet, we do not feel that simulating aggregation on standard benchmark datasets makes the experiments unrealistic.\n \n- On denseness and readability. \n\nWe will work on improving the readability of the technical sections in the paper. Thank you!", "claims_and_evidence": "Overall, the paper's claims seem generally reasonable. Some of the points as mentioned below are unclear :\n\nOverall, the paper is quite dense, and understanding it is heavily dependent on having to read the appendix,  which contains long proofs. It is somewhat unreasonable to expect to read along with many other papers to review in the allocated time, with other constraints. In that sense, the paper should provide intuition of the main results in the main body, which it provides only partially, and hence the paper is largely suitable for a journal. On the other hand, I tried to check the claim of the scenario when \\Delta and \\beta are unknown (lines 190-195), and it seems there isn’t any proof in B.2. \n\nAlso, I am not sure about the claims in lines 228-232, how can one estimate E[h(x)] and E[h*(x)] from unlabeled data. Even in standard supervised setting, when h* is unknown, how could it be possible to make such estimates. In the given settings, when bag size becomes larger, this estimate would become worse in my opinion, so these assumptions seem quite strong.\n\nThe sample complexity result of realizable case O(k/beta) is not of much practical importance. While the other scenarios of non-realizability, the difference compared to previous results is not very significant O(k*k/\\beta*\\beta) in previous vs O(k/\\beta*\\beta) in this work. However, this matters only for large bag sizes, in which case the estimates of E[h(x)] and E[h*(x)] would become worse.", "methods_and_evaluation_criteria": "The methods proposed in this paper are appropriate for the LLP problem and align with the theoretical claims. The authors build on standard learning algorithms – ERM and SGD – modifying them to handle bag-level supervision.", "theoretical_claims": "Beyond the points raised above (in claims and evidence), the paper’s theoretical contributions seem reasonably sound. It would be helpful if the authors could help and clarify the above.", "experimental_designs_or_analyses": "The experimental setup in the paper is generally reasonable and comparable to those used in previous related works mentioned in the paper and appropriate for evaluating an LLP method.", "relation_to_broader_scientific_literature": "The paper seems to have a good discussion on relevant existing methods", "essential_references_not_discussed": "Not to my knowledge", "other_strengths_and_weaknesses": "Strengths\n\n1. Significance of Problem: The paper addresses an important problem setting (LLP) that is highly relevant for privacy-preserving machine learning. \n2. Practical Algorithm and Empirical Validation: Unlike some theory-heavy papers, this work doesn’t stop at theory. The empirical results, showing improved accuracy with fewer samples, underscore that the theory has some practical merit. \n3. Clarity and Organization: The paper is generally well-written and structured logically. The abstract clearly states the contributions, the introduction provides sufficient background and motivation (mentioning real-world scenarios which helps the reader care about LLP).\n\n\nweakness\n\n1. Incremental Aspects: A potential weakness is that the paper’s main theoretical claim, while valuable, is somewhat incremental with respect to very recent works Li et al. (2024), and Busa-Fekete et al. (2023). \n\n2. Focus on Square Loss: The analysis is done under square loss, which is a convenient surrogate for classification. This is a limitation in the sense that the theoretical guarantees are for squared error/regret, not directly for 0-1 classification error. It’s possible to have a small square loss but still misclassify some fraction of points \n\n3. Experimental Limitations: The empirical results are mostly on simulated LLP scenarios derived from standard datasets. The paper does not report results on an actual real-world aggregated-label dataset \n\n4. Clarity in Technical Sections: While the paper is overall well-written, the theoretical sections are dense and may be challenging for readers not deeply versed in learning theory.", "other_comments_or_suggestions": "NA", "questions_for_authors": "As mentioned above", "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": "AC6jVBjvMg", "reviewer": "Reviewer_Rv2q", "summary": "This paper addresses the challenge of Learning from Label Proportions (LLP) by analyzing the i.i.d. bag sampling setting. The authors provide improved sample complexity bounds in both realizable and non-realizable settings, using variance reduction methods, surpassing prior results. They further demonstrate the practical benefits of their approach through experiments, showing performance gains over baselines, especially in the critical regime of large bag sizes.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- On uniform bag sizes.\n\nWe present our results using a uniform bag size for simplicity, but in principle the loss estimate we propose here can be applied even in situations where we have bags of different sizes, and we should still expect to see improvements due to the reduced variance at each bag. The corresponding sample complexity will replace the dependence on the uniform bag size $k$ (see lines 262-271, right column) with a dependence on the average bag size $(k_1 + k_2 … + k_m)/m$, being $k_j$ the size of the $j$-th bag. We will add this observation to the paper.\n\n- On the use of square loss.\n\nWe agree that extensions to other losses would be beneficial (and this is the focus of our ongoing work), but we found the squared loss setting already quite challenging.\n\n- Observed gains compared to Li et al. (2024) marginal for the majority of bag sizes.\n\nThe variance of our loss estimates has a substantially improved dependence on the bag size compared to Li et al.’s loss estimate. We expect the performance of both loss estimates to be similar for small $k$ (when the variances are comparable), and for very large $k$ but fixed $n$ (when the bags are so large that the LLP algorithms simply do not have enough signal). But for large values of $k$, where learning is still possible, we expect our loss to perform better. Please see also the extra experiments we ran in response to Reviewer 2x73, where we show that the gap between our method and Li et al. 's widens substantially as $k$ grows (e.g., for $k$ = 1024). \n\n- On the technical novelty and the challenges in comparison to Busa-Fekete et al. (2023) and Li et al. (2024).\n\nThe technical novelty is multi-faceted. \n1. The main technical novelty is recognizing that the methods proposed in both Busa-Fekete et al. and Li et al. cannot provide the best sample complexity as a joint function of the regret bound $\\beta$ and the bag size $k$ (this sample complexity is akin to a “privacy vs. utility” tradeoff – the bigger $k$ the more private the labels), unless something substantially different is tried in the way the estimators are designed. The variance reduction methods we proposed based on clipping and centered variables come at the price of making our estimators *biased*, and we need to keep both bias and variance under control. For square loss, we have shown that this is the best one can hope for (up to log factors). \n2. Further, the fast rates claimed in Li et al. only apply to the easy situation where the best in class has *zero* loss (thereby ruling out the possibility of noise in the labels) – this is more restricted than the standard *realizable* scenario, where the Bayes optimal predictor coincides with the best in class hypothesis. This requires a more careful analysis than Li et al. 's when estimating the unknown parameters $E[h(x)]$ and $p$ (see Appendix B.2). \n3. Moreover, we show that, in principle, there is an even better algorithm for LLP (even for square loss), which is based on pairwise comparisons and eliminations, described in Sect. 3 (for the two function case). That algorithm is better in that it does not have extra $\\log k$ factors in its sample complexity bounds (at the cost of assuming $k$ large), but it is clearly not practical, since it requires doing comparisons for all pairs of functions in the hypothesis space. In passing, we also improve Li et al. ‘s lower bound by log factors (again, in the two hypothesis case). \n4. Last but not least, we have shown that the sample complexity improvements are tangible, in that they are reflected in our experimental evidence.\n\n- Extension to multi-class classification.\n\nWe do not expect the extension to multiclass to be hard. The main technical challenge is to come up with an estimator whose variance will depend on the number of classes *linearly* (or even sublinearly, if at all possible), instead of quadratically.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "The discussion of related work in Section 1.1 is appropriate.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "This paper is highly readable, contributes significantly to the field of LLPs, and presents novel results for the ICML community. I recommend acceptance, with the following suggestions for improvement.\n1. The results rely on certain assumptions, such as the bag size assumption in Theorem 3.1.\n2. The setting assumes a uniform bag size, which limits its practical applicability.\n3. The results are limited to the squared loss. However, the square loss is often not ideal in practice. Exploring other loss functions, such as the log loss, would be more beneficial.\n4. The observed gains compared to Li et al. (2024) are marginal for the majority of bag sizes. Could the authors discuss this observation?", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "1. Could you please elaborate on the technical novelty and the challenges you faced when proving improved bounds, especially in comparison to Busa-Fekete et al. (2023) and Li et al. (2024)?\n\n2. Could you elaborate on the challenges involved in generalizing your framework to multi-class classification?", "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": "bKuTvTGwCK", "reviewer": "Reviewer_2x73", "summary": "This paper provided the optimal sample complexity of LLP under square loss. Based on these analysis, the authors proposed an improved squared loss, which was reported to enjoy better classification accuracy on several binary classification datasets under LLP settings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Extensions to Multi-class and Other Losses.\n\nWe agree with the reviewer that extensions to the multiclass setting and losses other than the squared loss would be of interest. Having said that, our work is the first to provide matching upper and lower bounds on the sample complexity of learning from label proportions for binary classification with squared loss. In other words, if we go outside the (easy) noise-free realizable setting considered in Li et al. (2024), all prior work has suboptimal sample complexity even in this relatively simple setting. Our ongoing work explores extensions of our results to the multiclass setting and other losses. We expect the extension to multiclass to be relatively easy (but please see also the response to Reviewer Rv2q on this point). On the other hand, we feel that the extension to losses other than square loss will be more challenging (if we want to retain the minimum variance property of the estimators), thus belonging in a follow-up paper.\n\n- Essential References.\n\nThank you for bringing to our attention the missed reference. We will include a citation in the introduction!\n\n- Varying Bag Size.\n\nThis point was also raised by Reviewer Rv2q. Since our loss function produces an (almost) unbiased estimate of the per-example squared loss from a single bag, applying it to a collection of bags of varying sizes will still result in an overall (almost) unbiased estimate of the loss. And, compared to prior work, the variance of our per-bag estimates will all scale better with the size of the bags, so we expect to have lower variance and improved sample complexity even when the bags have varying sizes. Our restriction to fixed-size bags is only for clarity of presentation. We will add a comment to the paper on this point. As for the resulting sample complexity, please see the response to Reviewer Rv2q (“On uniform bag sizes”).\n\n- Variance Comparison.\n\nFollowing the reviewer’s suggestion, below is a simple scenario where the difference in variance between our estimator and Li et al. 's is readily assessable. Consider the simple setting when $x$ is uniform in $[0,1]$, $h^*(x) = x^2$, and $\\hat h(x) = x$. We compute the label marginal $p$ exactly, and estimate $E[h(x)]$ in the same way as our learning experiments using SGD batches of size 1024 and a total of $n=2^{20}$ examples. From the table below, we see that the variance of our estimate stays roughly constant, while that of Li et al. grows as the bag size increases.\n\n|   bag size |      Ours |   Li et al. |\n|-----------:|----------:|------------:|\n|          2 | 0.0336042 |   0.0593875 |\n|          4 | 0.0363739 |   0.0931322 |\n|          8 | 0.037708  |   0.155778  |\n|         16 | 0.0385156 |   0.282495  |\n|         32 | 0.0392801 |   0.540059  |\n|         64 | 0.0414068 |   1.06511   |\n|        128 | 0.0478653 |   2.21354   |\n|        256 | 0.0565216 |   4.84059   |\n\n- Larger Bag Sizes: \n\nFollowing the reviewer’s suggestion, the following table reports final test accuracy for each method on each dataset using bags of size $k = 1024$. The number in the parenthesis is one standard error in the mean over 10 repetitions. The number of epochs is the same as the longer training run for each dataset, and we increased the SGD batch size to 2048 so that each batch contains more than one bag (which is necessary for our estimates of $E[h(x)]$). Otherwise, the experimental setup is identical to that of Section 6. On MNIST, Cifar-10, and Higgs, we see a large accuracy gap using our method compared to baselines, and on UCI Adult we slightly outperform all baselines, further supporting our theory. \n\n|           | mnist              | cifar10            | uci adult          | higgs              |\n|:----------|:-------------------|:-------------------|:-------------------|:-------------------|\n| Ours      | 0.876 (+/- 0.0047) | 0.796 (+/- 0.0115) | 0.770 (+/- 0.0024) | 0.628 (+/- 0.0013) |\n| Li et al. | 0.789 (+/- 0.0158) | 0.628 (+/- 0.0182) | 0.710 (+/- 0.0445) | 0.602 (+/- 0.0024) |\n| VanillaCE | 0.847 (+/- 0.0063) | 0.665 (+/- 0.0093) | 0.762 (+/- 0.0000) | 0.570 (+/- 0.0039) |\n| VanillaSQ | 0.848 (+/- 0.0066) | 0.663 (+/- 0.0084) | 0.762 (+/- 0.0000) | 0.568 (+/- 0.0041) |\n| EasyLLP   | 0.783 (+/- 0.0158) | 0.617 (+/- 0.0174) | 0.709 (+/- 0.0485) | 0.603 (+/- 0.0033) |\n\n- Hypothesis Complexity in Section 5 is too restrictive.\n\nWe agree that restricting to linear hypotheses in Section 5 is restrictive. Still, remember that in order for SGD to have global convergence guarantees (which are the focus of this paper), the function \n\n$\\qquad w  \\rightarrow E[ \\ell(h(x; w), y) ] $\n\nshould be convex in $w$ (here $\\ell$ is any convex loss function---in our case, the squared loss), and unless $h$ is a linear function in $w$, it is unlikely that this will be the case. And indeed, assuming a linear prediction rule is standard in convex, globally convergent analyses of SGD in Machine Learning contexts.", "claims_and_evidence": "The claims made in the submission are generally supported by evidence and proofs.", "methods_and_evaluation_criteria": "It is OK. However, due to the limitation to binary classification, many SoTA LLP solvers and dataset settings cannot be considered.", "theoretical_claims": "Yes, I have roughly reviewed the correctness of all theoretical proofs provided in the paper.", "experimental_designs_or_analyses": "Because the performance improvement of the proposed method only evident for big bag sizes, I think its contribution on LLP algorithm is limited.", "relation_to_broader_scientific_literature": "This work is a seminal exploration of improving LLP improvement under large bag sizes, which enjoys a promising focus in practice.", "essential_references_not_discussed": "An important seminal work [1] on multiclass LLP should be cited in the Introduction.\n\n[1] Liu J, Wang B, Qi Z, Tian Y, Shi Y. Learning from Label Proportions with Generative Adversarial Networks. In NeurIPS 2019.", "other_strengths_and_weaknesses": "**Strengths:**\n\nThe performance improvement of LLP for big bag sizes is significant. \n\n**Weaknesses:**\n\n1.\tAs we already have several work on binary classification, the analysis on multi-class scenarios should be worth noting and desirable.\n2.\tThe squared loss is not common in current work. The analysis of other losses (e.g., CE loss) can improve the practicability the this work.", "other_comments_or_suggestions": "1. The variance comparison should be displayed in a more clearer way. (Maybe providing the quantitative results)\n2. In fact, in some datasets, the improvement becomes significant under the largest bag size, i.e., $k=2^9$. It will be better to show the results under more other large bag sizes that the proposed method performs better than other existing methods.", "questions_for_authors": "1. Can you discuss how your work can fit in the situation of varying bag size? (i.e., the bag size is not the same among the bags). Maybe a bounded interval for the bag size is a good assumption for further discussion.\n2. In terms of hypothesis complexity, the discussion on linear predictor in Section 5 seems to be too restricted. How can you extend the results to more complex hypothesis space.", "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": "RdYwX9lUOy", "reviewer": "Reviewer_UVyu", "summary": "This paper investigates the problem of Learning with Label Proportions (LLP), where training data is provided in groups (or bags) rather than individual instances, and only aggregate label proportions are available for each group. The goal is to infer the original instance-level labels using the provided proportion information. To tackle this problem, the paper adopts a statistical learning perspective and aims to minimize the excess risk under both realizable and non-realizable settings. The authors focus on empirical risk minimization (ERM) and stochastic gradient descent (SGD) and propose a variance reduction technique that theoretically achieves a tighter regret bound, improving the learning performance in LLP. The effectiveness of the proposed method is evaluated through experiments on CIFAR-10, MNIST, and Higgs5 datasets, demonstrating its superiority over existing baseline approaches.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- “... several typos and unclear descriptions… ”. \n\nWe would appreciate pointers to typos, unclear descriptions, and key arguments that the reviewer found unclear so that we can improve them. Thank you!\n\n- On Motivation.\n\nAs discussed in the right column of lines 23 – 32, a key modern motivation for the learning from label proportions framework is training conversion models for online advertising. Advertisers (or AdTechs working on their behalf) train models for predicting whether a user will convert (i.e., sign up for an account, buy a product, etc) if they click an advertisement. Since the ad click and conversion happen on different websites, collecting training data requires linking user behavior across the two sites. Historically, third party cookies or link decoration has made this straightforward. However, as web browsers move towards improving user privacy, there are several proposed APIs that allow for collecting cross-site data *in aggregate*. Many of these APIs can be used to directly measure the label proportion within a bag of examples. We view LLP as a principled technique for making the best use of these APIs for training conversion models. We will add more language along these lines to the introduction.\n\n- On challenges.\n\nThe key challenge that we seek to address is to characterize the sample complexity of LLP: how much more data is required to train a model in the LLP framework than when all labels in the training set are available in the clear. We answer this question for the case of squared loss binary classification by giving the first (nearly) matching upper and lower bounds on the sample complexity of LLP. Now, given the fact that our loss estimate is almost unbiased (unlike those in Busa-Fekete et al, and Li et al.), the way in which the sample complexity can be improved over existing works is to improve the way the loss estimates concentrate at their expectation while keeping bias under control. It is intuitively clear that any method that selects a model by minimizing the estimated losses will be more reliable when the variance of this estimate is reduced (if the bias is also small). Our analysis leverages the lower variance of our estimates to derive improved sample complexity and convergence rates that are not possible with the methods of Busa-Fekete et al, and Li et al. Also, note that the theoretical best estimator is not even the one alluded to in Thm 4.1, but the *pairwise* (but not very practical) estimator of Thm 3.1, which is again a novel contribution of this paper. We will add text to the paper in order to better clarify these aspects.\n\n- Justification of ERM and SGD + “It is unclear why the proposed variance reduction technique is equally applicable to both.”\n\nWe do not fully understand these comments. We focus on ERM and SGD because these are the most prominent learning paradigms. ERM is a learning principle – true – but the interpretation of our results should be rather clear: Any algorithm that performs ERM and operates with the loss function we designed for LLP enjoys the sample complexity guarantees we claim for ERM in Thm 4.1. Our results for ERM deal with the information-theoretic limits of LLP independently of increased computational difficulty in the underlying optimization problem. Our results for SGD study the impact of LLP on both the sample complexity and convergence rate of SGD for the case of linear hypotheses. In both cases, it is the design of an ad hoc loss function that enables improved results, not the learning algorithm itself. There are, on the other hand, some nuances, as this loss assumes prior knowledge of quantities that are usually unknown, and can only be estimated from data. We provide one such solution in Appendix B.2 in connection to ERM, and claim that similar fixes are possible for Sect. 3 (the pairwise estimator) and Sect. 5 (the SGD algorithm).\n\n- Practical and Real-World Relevance.\n\nAs discussed above, we are mainly motivated by an extremely practical problem: training advertising conversion models from aggregate data collected via new privacy-preserving browser APIs. Improvements to the sample complexity of LLP in this context can directly lead to improved model performance. We will describe this more clearly in the introduction of the paper. As for experiments related to such data, this is a legitimate point that was also made by Reviewer YpnD. Unfortunately, most modern large-scale aggregated datasets (originating from online advertising) are proprietary. That led us to simulated aggregation environments on standard benchmark datasets. Yet, we believe our experimental environment does not make our experiments unrealistic.", "claims_and_evidence": "Most of the claims are provided with evidence.", "methods_and_evaluation_criteria": "No.", "theoretical_claims": "I have roughly read the proofs.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "Theoretical contribution on a new framework for tackling LLP.", "essential_references_not_discussed": "No additional references needed.", "other_strengths_and_weaknesses": "Strengths\n- Theoretical Contributions:\n  - The paper establishes solid theoretical guarantees for LLP, particularly by addressing the necessity and sufficiency of hypothesis bias in LLP learning.\n  - The theoretical results provide valuable insights into how hypothesis bias impacts learning performance in LLP settings, which is crucial for both model design and practical implementation.\n- Generalizability of the Framework:\n  - The proposed approach is not restricted to a specific learning paradigm but is applicable to both empirical risk minimization (ERM) and stochastic gradient descent (SGD).\n  - This generalizability enhances the relevance and applicability of the proposed variance reduction technique, making it adaptable to different optimization and learning strategies.\n- Empirical Effectiveness:\n  - The experimental results show significant improvements over baseline methods, indicating the practical viability of the proposed approach.\n  - The study evaluates the method on diverse datasets, including CIFAR-10 (image classification), MNIST (digit recognition), and Higgs5 (scientific data analysis), demonstrating its broad applicability.\n\n\nWeaknesses and Areas for Improvement\n- Clarity and Writing Quality:\n  - The paper’s writing could be improved, as there are several typos and unclear descriptions that affect readability.\n  - Some key arguments, especially regarding the theoretical framework, could be more clearly articulated.\n- Motivation for the Proposed Learning Framework:\n  - The paper lacks a clear motivation for why this particular learning framework is necessary.\n  - While the authors demonstrate performance improvements, it remains unclear what specific challenges in existing LLP methods necessitate this new approach.\n  - A more detailed discussion on how the proposed variance reduction technique uniquely addresses these challenges would strengthen the motivation.\n- Justification for the Choice of ERM and SGD:\n  - The authors consider both ERM and SGD as realizations of the LLP problem but do not sufficiently justify this choice.\n  - ERM is a learning principle, whereas SGD is an optimization algorithm—this distinction should be discussed more explicitly.\n  - It is unclear why the proposed variance reduction technique is equally applicable to both. Providing additional justification or empirical comparisons between different optimization techniques would help clarify this choice.\n- Practical and Real-World Relevance:\n  - The realistic implications of this study are not fully explored.\n  - While the theoretical and empirical results are promising, the paper does not clearly articulate how LLP is applied in real-world scenarios.\n  - Including concrete applications (e.g., medical diagnosis, fraud detection, or social science studies where label proportions are more accessible than instance-level labels) would strengthen the case for the practical impact of the work.", "other_comments_or_suggestions": "Please check the weaknesses.", "questions_for_authors": "If the authors can address my concerns, I will reconsider the score.", "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:

Meta-review: This paper presents a work about learning from label proportions (LLP), where only aggregated label information is available for groups of examples (bags), and the objective remains accurate prediction at the individual example level. The authors present new theoretical insights into the sample complexity of LLP under the square loss, which demonstrates bounds that are essentially optimal and that notably improve prior results. Algorithmically, the paper introduces refined variants of empirical risk minimization and stochastic gradient descent. The empirical results show that the proposed methods outperform existing baselines across several benchmark datasets. Overall, the paper makes both solid theoretical contributions and demonstrates practical effectiveness, which is meaningful in the study of LLP.

In the initial review phase, this paper received mixed recommendations, where the concerns were mainly reflected in the explanations/justifications of theoretical results and real-world relevance. After the rebuttal, the concerns in theory are addressed properly. The rationality of the simulation experiment has also been answered. All reviewers become positive about the work. AC recommends accepting it. The authors are encouraged to incorporate the reviewers’ constructive feedback in the final version to improve the clarity and impact of this work.
Decision: Accept (poster)