PAC Learning Linear Thresholds from Label Proportions
Authors: Anand Paresh Brahmbhatt
Rishi Saket
Aravindan Raghuveer
Venue: NeurIPS 2023 spotlight (2023)
Keywords: PAC learning
Learning from label proportions
Linear thresholds
TL;DR: Algorithms for PAC learning linear threshold functions from label proportions of random bags of Gaussian feature-vectors

Abstract: Learning from label proportions (LLP) is a generalization of supervised learning in which the training data is available as sets or bags of feature-vectors (instances) along with the average instance-label of each bag. The goal is to train a good instance classifier. While most previous works on LLP have focused on training models on such training data, computational learnability of LLP was only
recently explored by Saket (2021, 2022) who showed worst case intractability of properly learning linear threshold functions (LTFs) from label proportions. However, their work did not rule out efficient algorithms for this problem for natural distributions.

In this work we show that it is indeed possible to efficiently learn LTFs using LTFs when given access to random bags of some label proportion in which feature-vectors are, conditioned on their labels, independently sampled from a Gaussian distribution $N(µ, Σ)$. Our work shows that a certain matrix – formed using covariances of the differences of feature-vectors sampled from the bags with and without replacement – necessarily has its principal component, after a transformation, in the direction of the normal vector of the LTF. Our algorithm estimates the means and covariance matrices using subgaussian concentration bounds which we show can be applied to efficiently sample bags for approximating the normal direction. Using this in conjunction with novel generalization error bounds in the bag setting, we show that a low error hypothesis LTF can be identified. For some special cases of the $N(0, I)$ distribution we provide a simpler mean estimation based algorithm. We include an experimental evaluation of our learning algorithms along with a comparison with those of Saket (2021, 2022) and random LTFs, demonstrating the effectiveness of our techniques.

PAC Learning Linear Thresholds from Label Proportions
Anand Brahmbhatt' Google Research India anandpareshb@google.. com
Rishi Saket" Google Research India ri sashtsakt com
Aravindan Raghuveer Google Research India araghuveer@google. com
Abstract
Learning from label proportions (LLP) is generalization of supervised learning which the training data is available as sets bags of feature-vector (instances) along with the average instance-labe of each bag. The goal is to train a good instance classifier. While most previous works LLP have focused
training models on such training data, computational learnability of LLP was only recently explored by [25, 26] who showed worst case intractability of properly learning linear threshold functions (LTFs) from label proportions. However, their work did not rule out efficient algorithms for this problem natural distributions.
In this work we show that it is indeed possible efficiently learn LTFs using LTFs when given access to random bags of some label proportion in which feature- vectors are, conditioned on their labels, independently sampled from Gaussian distribution N(u, E). Our work shows that a certain matrix formed using co- variances of the differences of vectors sampled from the bags with and without replacement necessarily has its principal component, after transfor- mation, in the direction the normal vector of the LTF. Our algorithm estimates the means and covariance matrices using subgaussian concentration bounds which we show can be applied to efficiently sample bags for approximating the normal direction. Using this in conjunction with novel generalization error bounds in the bag setting, we show that a low error hypothesis LTF can be identified. For some special cases of the (00, I) distribution we provide simpler mean estimation based algorithm. We include an experimental evaluation of our learning algorithms along with comparison with those of [25, 26) and random L.FFs, demonstrating the effectiveness our techniques.
1 Introduction
In learning from label proportions (LLP), the training data is aggregated into sets or bags of feature- vectors (instances). For each bag we are given its constituent ceature-vectors along with only the sum or average of their labels The goal is to obtain good instance-level classifier one that minimizes the classification eиrоr on test over Gaussian distributions of linear threshold functions (LTFs), also called linear classifiers or halfspaces, given by f(x) = pos (r + c) where pos(a) 1 if > and 0 otherwise.
instances bags. In this work we study the LLP learnability
The probably approximately correct (PAC) model of [29] states that concept class e of {0, 1}- valued functions can be learnt by a hypothesis class H( if there is an algorithm to efficiently obtain, using iid samples from distribution (x. fxx), hypothesis h H( of arbitrarily high accuracy on that distribution, for any unknown f e. JC = e we say that properly learnable, for
equal contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

e.g. LTFs are known to be properly learnable using linear programming ([3]). This notion can be extended to the LLP setting which for brevity we call PAC-LLP-- as follows: distribution D is over bags and their label proportions (B, a ()) where B = (xI,..., xx) is a bag of feature vectors and o (B, f) = (x)( x E B). A bag (B, a B, f)) said to be satisfied by iff (B, - o B, f), and the accuracy of h is the fraction of bags satisfied by it.
With the above notion of PAC-LLP, [25] studied the learnability of LTFs and rather disturbingly showed that for any constant E > 0 it is NP-hard to PAC-LLP learn an LTF using an LTF which satisfies (1/2 + e)-fraction of the bags when all bags are of size at most 2, which was subsequently strengthened to a (4/9 + E) -aafcoo hardness by [26] who also proved (1/9 e) -factor hardness when the bag size is at most q. for any 9 2 3. This is in contrast to the supervised learning (i.e, with unit-sized bags) in which an LTF can be efficiently learnt by an LTF using linear programming. On the algorithmic side, [25] gave a semi-definite programming (SDP) based algorithm to find an LTF satisfying (2/5)-fraction of bags of size S 2. which was extended by [26] to a fairly involved SDP yielding aa12)aaaprooiiaation for bags of size I 3. while no non-trivial algorithms for bags of size > 3 are known. These results show that PAC-LLP learning LTFs using LTFs is intractable on hard bag distributions, and even the non-trivial algorithms for bag sizes S are via complicated convex programming techniques. A natural question therefore, is whether the problem is tractable on natural distributions that may arise out of real world scenarios.
We answer the above question in the affirmative when the feature- are distributed according to some (unknown) Gaussian distribution D = N Nu, Σ) in d-dimensions. Gaussian distributions are ubiquitous in machine learning and in many applications the input data distribution is modeled as multivariate Gaussians, and several previous works [8, 30) have studied learnability in Gaussian distributions. An unkown target LTF is given by f(x) == pos (r_x + c.) where ||r~||2 1. Let De x
be the distribution of x + 'D conditioned on f(x = a, for a E {0, 13. Using this we formalize the notion of a distribution O on bags of size @ and average label k/q: a random bag B sampled from o consists of k iid samples from D2 and (q - k) iid samples from Do. The case of k E {0, g} is uninteresting as all instances in such bags are either labeled 0 or 1 and traditional PAC-learning for ITF's can be employed directly. Unlike [25, 26) our objective is to directly maximize the instance-level level accuracy on DD With this setup we informally describe our main result.
Our PAC-LLP LTF Learner (Informal): Assuming mild conditions on E, f and c., for any q, E Z- s.t. < k < 9 -- 1 and e, d O. there is an algorithm that samples at most m bags from 0 and runs in time Ott - m) and with probability - ô produces an LTF h s.t.
Pro[f(x) A h(x) < E if l: o g/2, and
Pro (x) * h(x)] S E or (x) * (1 - [ < E if k = 9/2,
where t, m are fixed polynomials in d, 9. lo/)),
We also obtain a more efficient algorithm
when k # q/2, μ O, c. = O and Σ = I. The ambiguity in the case of k = q/2 is inherent since bags of label proportion 1/2 consistent with an LTF f(x) are also consistent with (1 - f(xx))
Remark 1.1 (Mixtures of k)). The training data could consist of bags of different sizes and label proportions, however typically the the maximun size of bags is bounded by (say) Q, and in a large enough sample we would have at least (-ractiinn of bags of a particular size and label
proportion and we can apply our PAC-LLP LTF Learner above to that subsample.
1.1 Related Work
The LLP problem is motivated by many real applications where labels are available not for each feature-vector but only as the average labels of bags of feature-vectors. This may occur because of privacy and legal ([24, 331)) reasons, supervision cost (15)) or lack of labeling instrumentation ([10)). Previous works ([9, 15, 20, 24)) on LLP have applied techniques such as such as clustering. and linear classifiers and MCMC. Specifically for LLP, assuming class conditional independence of bags, [23] gave an algorithm to learn an exponential generative model, which was further generalized by [22]. On the other hand, the work of [34] proposed novel proportional SVM based algorithms which optimized the SVM loss over instance- labels which were constrained by bag-level loss w.r.t the given propootioon.. Subsequently. approaches based deep neural nets for large-scale and multi-class data ([18, 11, 19, 21I), as well as bag pre- rre-processing techniques ([28, 27]) have been developed. Recently, [4, 6] have proposed model training methods for either random or curated bags.
The L.P framework (as an analogue of PAC learning) was first formalized in the work of [35]. They bounded the generalization error of a trained classifier when taking the (bag. label-proportion) -paiis

---

as instances sampled iid from some distribution. Their loss function was different a weaker notion than the strict bag satisfaction predicate of [25, 26]. A single-bag variant class ratio estimation of I.I. was studied by [13] in which learning LTFFs has a simple algorithm (see Appendix G). Nevertheless, the study of computational learning in the L.P framework has been fairly limited, apart from the works of [25, 26] whose results of learning LTFss in the LLP setting have been described earlier in this section.
In the fully supervised setting [3] showed that LTFs can be learnt using LTFs via linear programming without any distributional assumptions. Adversarial label noise makes the problem NP-hard to approximate beyond the trivial (1/2)-fccorr even using constant degree polynomial thresholds as hypothesis ([12, 14, 2)). However, under distributional assumptions a series of results ([16, 17, 1, 7]) have given efficient algorithms to learn adversarially noisy LTFs.
Next, Sec. 1.2 mathematically defines our problem statement. Sec. 1.3 states the main results of this paper. Sec. 1.4 provides an overview our techniques. Sec. mentions some preliminary results which are used our proofs. Sec. defines and analyses subroutine which we use in all our algorithms. Sec. 4 provides a complete proof for one of our main results. Sec 5 gives brief proof sketches of our other results. Sec. mentions some experiments which support of our results.
1.2 Problem Definition
Definition 1.2 (Bag Oracle). Given distribution DD over Ted and a target concept f: TR + 10, the bag oracle for size and label proportion h// S k S 9- 1), denoted by Ex k)), generates a bag {x Ti=1 such that x is independently sampled from (i) D for (1,.... k}. and (ii) D f.oofor {K + 11,,,.... ......... where Dja is x t D conditioned on f(x) a, for E (0,
1.3 Our results
We first state our result (proved in Appendix A) for the case of standard d-dimensional Gaussian distribution NO, I), homogeneous target LTF and unbalanced bags.
Theorem 1.3. For q >> 2 and k E {l..... q - }} s.t. lo * q/2 and LTF f(x) == pos(r.x). there is an algorithm that samples m idd bags from Ex(f, (0, I). q, k) and runs (m)) time to produce hypothesis h(x) := pos(f') (osffxxx (x)) s.t. w.p. least 1 over the sampling, Pro fr + h(x)] E, for any E, 8 O, when m O (Id/E?) log(d/)))
The above algorithm is based on estimating the mean of the bag vectors, which unfortunately does not work when & = g/ 2 or for a general covariance matrix Σ. We instead use covariance estimation based approach- albeit with worse running time for our next result which proved in Sec. 4. Amin and Amax denote the minimum and maximum eigenvalues of the covariance matrix E.
Theorem 1.4. For g > 2, ls E (1,...., 1), f(x) == pos(r] r. x), and positive definite Σ there is algorithm that samples m iid from Ex(f, (0, E), k) and runs in poly(m) time to produce
hypothesis h(x) = (fs(fT x) s.t. w.p. at least 8 over the sampling
k # 2/2, (r) # h(x)] < E, and . ifk g/2, min(Prr (x) Pro(f(() h(xi] S,, where h(x) ;= pos(-f"x) for any E, 8 > when m 2 O(d/e 4\ log(d/6)) / >minn)&²²)
Our general result stated below (proved Appendix C), extends our algorithmic methods to the case of non-centered Gaussian space and non- non-homogeneous LTFs.
Theorem 1.5. For q > 2, k .L....qq- 1}. fxx) == po + cx), and positive definite Σ there is an algorithm that samples m iid bags from Ex(f. (m, Σ), k) and rums in poly(m) time to produce a hypothesis hixx) = pos(f"s x + é) s.t. w.p. at least 1 8 over the sampling
i q/2, Pro [f() h(x)) S and
-fk=9/22 min Pro [x() + h(x)), Prolf(x) + h(x)]] s π(x)) = pos( -f 2)
for any 8, > 0, when m 2 o (d/65) (+)))((1 (og(d/))
o
Amn Aria
(SAnmatt
[|ella))) (8) where
Φ ) is the standard Gaussian cdf and E t. J
3

---

The value of f output by our algorithms is close estimate of r, (or possibly -r= in the case of balanced bags). Note that our algorithms do not require knowledge of μ or Σ. and only the derived parameters in Thms. 1.4 and 1.5 are used for the sample complexity bounds. They are based on the certain properties of the empirical meen-vectors and covariance matrices formed by sampling vectors or pairs of vectors from random bags of the bag oracle. An empirical mean based approach has been previously developed by [23] in the LLP setting to estimate the parameters of an exponential generative model, when bag distributions satisfy the so-called class conditioned independencei.e. given its label, the feature-vector distribution same for all the bags. These techniques were extended by [22] to linear classifiers with loss functions satisfying certain smoothness conditions. While the bag oracle in our setup satisfies such conditioned independence, we aim to minimize the instance classification error on which the techniques of [23, 22] are not applicable.
For the case when = 1 (ordinary classification), the sample complexity is Odde log(d/o)) as one solve linear program obtain LTF and then use uniform convergence to bound the generalization error. The sample complexity expressions in Theorems 1.3, 1.4 and 1.5 have the same dependence on d and 6. However, they have higher powers of 1/c. They also include other parameters like the bag size (q), condition number of Σ (Amax/ /min) and the normalized distance of mean of the Gaussian the LTF (I). The origins and significance of these discrepancies are discussed in Sec. 1.4.
1.4 Our Techniques
Theorem 1.3: Case (O,1)), f(x) po)(r..),, k # 9/2. Assume that k 9/2. A randomly sampled bag with label proportion k/q has vectors iid sampled from the positive side of the separating hyperplane passing through origin, and (g- (k) iid sampled from its negative side. It is easy to see that the expected sum of the vectors vanishes in all directions orthogonal to the normal vector r., and in the direction of r. it has a constant magnitude. The case of k q/2 2 is analogous with the direction of the expectation opposite to r.. Sampling sufficient number of bags and a random vector from each of them, and taking their normalized expectation (negating if A: < //2) yields the close estimate r of r,, which in turn implies low classification error. The sample complexity is the same as that for mean estimation bag- vectors (see Section 3) and thus the power of 1/s is 2.
This simple approach however does not work when r = q/2, in which case the expectation vanishes completely, or for general Gaussian distributions which (even if centered) could be skewed in arbitrary directions. We present our variance based method to handle these cases.
Theorem 1.4: Case (0, Σ), fxx pos(r. To convey the main idea of our approach, consider two different ways of sampling two feature-vectors from a random bag the oracle. The first way is to sample two nature-vecctors Zi Ze independently and u.a.r from a random bag. In this case, the probability that they have different labels (given by /) is 2k(44 - k)/4². The second way is to sample a random pair Ž, Z, of feature-vectors i.e., without replacement. In this case, the probability of different labels is 2k(q k)/(g(g 1)) which is strictly greater than 2ki k)/q². Since the labels given by thresholding in the direction of r., this suggests that the variance of (2) Z2) w.r.t. that of (Z, Zzz is maximized in the direction of r., Indeed, let ED == VarlZ, - Zz] be the pair covariance matrix and let ΣB == Var [Z,] = Var [Z, Zu] be the bag covariance matrix. Then we show that tr.- = argmax, where p(r) == r Epr
simple transformation gives us that
F'rr
t Eg' 1/1 Princcppalligeeeeeetrrrr E-1 ΣDΣE
(1)
This suggests the following algorithm: sample enough bags to construct the corresponding empirical estimates Ep and ΣB and then compute the empirical proxy of the RHS of (1). We show that using close enough empirical estimates w.h.p the algorithm computes a vector I s.t. one of + is close to r., and via a geometric stability argument this implies that one of + yields an LTF that has small instance-level classification error.
At this point, if k = q/2,, there is no way identify the correct solution from +G, since balanced bag, if consistent with an LTF, is also consistent with its complement, On the other hand, if h: * q/2 we can obtain the correct solution follows. It is easy show that since f is homogeneous and the instance distribution is a centered Gaussian, the measure of {x f(x = a} is 1/2 for a = {0, 1}. Thus, one of h(x) := pos(i x), h(x)- = pos( xx) will have high bag satisfaction accuracy.
Thus, a large enough sample of bags can be used to identify one of h, h having a high bag satisfaction

---

accuracy. Lastly, we use a novel generalization error bound (see below) to show that the identified LTF also has high instance classification accuracy.
The algorithm incurs a sample complexity of O ( ( )) to estimate Dn and Σg accu- rately so that the distance between i (or -f) and r, is sufficiently bounded. (see Lemmas 3.1 and
4. In fact, the distance is required to be O ((e/)) Amax) to translate the geometric bound
into an e-misclassification error bound, thereby incurring further factor of O (4 (Amax/ /mmin ) in the sample complexity (see Lemma 2.3). The higher powers in the dependencies are mainly due to the second moment estimates which degrade with larger values of (Amass/Amiul Note that the sample complexity explicitly depends on the bag size q (and not just the label proportion k/q). This is because the probability of of sampling (without replacement from bag) pair of differently labeled feature-vectors is 2 - k//)/(1
1/g). Keeping k/q the same, this probability decreases with increasing bag size, thereby increasing the sample complexity for larger bags.
Theorem 1.5: Case Ni, E), fxx) = pos(r..x + c.). We show that (1) also holds in this case, and therefore we use similar approach of empirically estimating the pair and bag covariance matrices solving (1) works in principle. However, there are complications, in particular the presence of I and c, degrades the error bounds in the analysis, thus increasing the sample complexity of the algorithm. This is because the measures of (x fx) = a} for a = {0, 1} could be highly skewed if 1ll2/ and/or |c.| is large. Moreover, the spectral algorithm only gives solution ti for r.. An additional step is required to obtain an estimate of c.. This we accomplish using the following procedure which, given sample of bags and any outputs a which has the following property: if 8 = max. no. of bags satisfied by pos(r') x + c)), then é will satisfy at least 8 - 1 bags. This is done by ordering the values r'x x of the vectors x within each bag in decreasing order, and then constructing set of the kth values of each bag. Out of these values, the one which taken as in pos(r x + c) satisfies the most bags, is chosen to be č.
Due to the non- non-homogeneity of the Gaussian distribution and the LTF f. the application of Lemma 2.3 instead incurs an O (g*((V + (|1x|12)// ///////// (m factor in the sample complexity, while a factor of ((2)) is towards the estimation of Eg and Σp. Note that l is the distance from μ to the hyperplane of f normalized by the stretch induced by E, and thus a larger value of implics a lower density near the hyperplane leading to an increased sample complexity. Lastly, a further blowup by 1/(0(E)(1- (())))² comes from bounding the sample error from geometric bound between i and r,, and is required for a sufficiently accurate approximation of C..
Generalization Error Bounds. We prove (Thm. 2.2) bounds on the generalization of the error of a hypothesis LTF h in satisfying sampled bags to its distributional instance-level error. Using this, we are able to distinguish (for k * //2) between the two possible solutions our principal component algorithm yields the one which satisfies more of the sampled bags has w.h.p. low instance-level error. For proving these bounds, the first step is to use a bag-level generalization error bound shown by [26] using the techniques of [35]. Next, we show that low distributional bag satisfaction error by h implics low instance level error. This involves fairly combinatorial analysis of two independent binomial random variables formed from the incorrectly classified labels within a random bag. Essentially, unless h closely aligns with f at the instance level, with significant probability there will be an imbalance in these two random variables leading to h not satisfying the bag.
Subgaussian concentration bounds. The standard estimation bounds for Gaussians are not directly applicable in our case, since the random vector sampled from a random bag is biased according to its label given by J. and is therefore not Gaussian vector. To obtain sample complexity bounds linear in log(1/ (1/8) we use subgaussian concentration bounds for mean and covariance estimation ([32, 31.. For this, we show O(2) bound on the expectation and subgaussian norm of the thresholded Gaussian given by {g- ~ 1), g > é} for some & > O. The random vectors of interest to us are (in a transformed space) distributed as combination of thresholded Gaussians in one of the coordinates, and (O, 1) in the rest. We show that they satisfy the O()) bound on their subgaussian norm and admit the corresponding subgaussian Hoeffding (for empirical mean) and empirical covariance concentration bounds. Based on this, in Sec. 3 we abstract out the procedure used in our learning algorithms for obtaining the relevant mean and covariance estimates.
Experiments. We include in Sec. 6 an experimental evaluation of our learning algorithms along with comparison of with those of [25, 26) and random L.FFs, demonstrating the effectiveness of our techniques.
5

---

2
Preliminaries
We begin with some useful linear algebraic notions. Let Amax and Amin(A) denote the max- imum and minimum eigenvalue of real symmetric matrix A. The operator norm |||| == max]]x||==1 ||Ax||2 for such matrices is given by Amax (A).
We shall restrict our attention to symmetric positive definite (p.d.) matrices A which satisfy x Ax >> O for all non-zero vectors x, implying that Amin (A) > O and A exists and is symmetric p.d. as well. Further, for such matrices A, A 1/2 is well defined to be the unique symmetric p.d. matrix B satisfying BB = A. The eigenvalues of A 1/2 are the square-roots of those of A. We have the following lemma which is proved in Appendix B.6.
Lemma 2.1. Let A and B be symmetric p.d. matrices such that ||-
E1 G1||A|12 12. Let r1, r2 Rd
be two unit vectors such that |[r r2/12 S E2. Then,
Ar
Bra Brg la
I 4 Anaa (A)
Ama (A) (E2 E1)
Arill
when Amaa (A) Auia
(02 + t1) S 2-
Bag Oracle and related statistics. Let O Ex(J, k) any bag oracle with E (1,..... 1} for LTF f(x) := x + e, in d-dimensions, and let M be collection of m bags sampled iid from the oracle. Define for any hypothesis LTF h,
BagErr oreete (ht, , f, D, k) = Pr [Avg(h(x)
x E B} k/g), and,
(2)
B+0
BagErr sample (h, MM == {BB E M Avg(h(x)
x E B} + k/ghl /m.
(3)
We define the following statistical quantities related to O. Let X be random feature-vector sampled uniformly from a random bag sampled from O. Let,
PB = E E
and,
EB = E (X - (n) (X m2) Var X].
(4)
Now, let Z X
X2 where (X1, X2) are a random pair of feature-vectors sampled (without replacement) from a random bag sampled from O. Clearly F[Z] = O. Define
ED = E zz
Var[Z].
(5)
Generalization and stability bounds. We prove in Appendix D.1 the following generalization bound from bag classification error to instance classification error.
Theorem 2.2. For any < 1/44 if BagErr.ample M) S then, h(x)) < 4s, and
(i i * q/2, Pro (x) #
(ii) if = 9/2, Pro of (xx & M(x) S 48 or Pr(f(x) + (1 h(x))] S 4c,
w.p. 1 - 8, when
Cod (log log(1/6)) for any ó 0 and absolute constant Co > 0.
In some cases we directly obtain geometric bounds on the hypothesis classifier and the following lemma (proved in Appendix D.2) allows to straightaway bound the classification error.
Lemma 2.3. Suppose
||
f|l2 I E1 for unit vectors r.
Then, Ei ex(eov/ /max/ Amin cı //llall///////// Amin)
Pr [pos (r-XX + A pos ( + +c]] E where
for some absolute constants co, C1 > 0 and Amax Amin are the maximum and minimum eigenvalues of E respectively.
3 Bag distribution statistics estimation
We provide the following estimator for μBB Eg and Ep defined in (4) and (5). We have the following lemma which follows from the subgaussian distribution based mean and covariance concentration bounds shown for thresholded Gaussians (see Appendix E) whose proof is given in Appendix E.3.
Lemma 3.1. If m 2 O ((d/e2)0(E)) log(d/5) where E is as given in Lemma E. 1.13 then Algorithm I returns BA En, En such that jĀB - p 2| S / /2, [ Enl12 S edmaso and !SE Ep 1l2 Exmax, w.p. at least 1 6, for any E, > 0. Here Amax is the maximum eigenvalue of E.

---

Algorithm MeanCovsEstimator.
Input: Ex = (μ, Σ), q, k), m, where f = pos (r"X + c).
Sample bags from Ex(ʃ, D. q. k). Let [B, )= be the sampled bags.
2. V : [x] X; u.a.r. +- B, i (1....,m)
PB Exev x/ml.
4. Eg = ExEV(x
MB)(x (xx)(x- MB)//m
5. Sample bags from Ex(J, g, R). Let {B,) be the sampled bags.
V : (x = x;=- &; (xi, x:) u.a.r. without replacement from B, E (I,..., m}}.
ΣD = EEE /
8. Return: itB EB, Ep.
4 Proof of Theorem 1.4
For the setting of Theorem 1.4, we provide Algorithm 2. uses as a subroutine polynomial time procedure PrincipalEígen Vector for the principal eigen- vector of a symmetric matrix, and first computes two LTFs given by a normal vector and its negation, returning the one that has lower error sampled collection of bags.
Algorithm 2 PAC Learner for no-offset LT'Fs over N(O, Σ)
Input: 0 Ex(f, N Σ), k), m, where f(x) pos (r.x), ||r.12 1.
Compute Eg, En using MeanCovsEstimmtor with m samples.
2. F.r- = Σ -/ 1/-1 PrincippalEigennecooo "/=1/" Σ
-1/2 if 2T exists, else exit.
3. Let r = r/ r||. 4. If 9/2 return: h = pos (F X). else
a. Let h pos (-
b. Sample collection M of bags from O.
c. Return h* E (h, h) which has lower BagErr sample (h" ,M).
Lemma 4.1. For any e, 8 E (0. 1). if 2 O((d/=)) log(d/0) Amin) )a)a), then i computed in Step of Alg. satisfies min []| 11.. [ 1 E, w.p. 1 1-811-1-- 5/2.
The above, whose proof is deferred to Sec. 4.1, is used in conjunction with the following lemma.
Lemma 4.2. Let k + 9/2, e E (0, and suppose f computed in Step 3 of Alg. 2 satisfies
minfllF- - 2, || + r. 112] S E.. Then, with s 2 O (d(log + log(1/8))/=} h² in Step. 3.c satisfies Pro (x) # [(x) < 16Goge
w.p. 1 6/2, where constant co > 0 is from Lem. 2.3. Amm Xun
With the above we complete the proof of Theorem 1.4 as follows.
Proof. (of Theorem 1.4) Let the parameters & be as given in the statement of the theorem.
For k 9/2, we use O Amin/ Amax) for the error bound in Lemma 4.1 thereby taking m O((d/s4)
Amin) )²²²))))))))))()) ) in Alg. 2, so that Lemma 4.1 along with Lemma 2.3 yields the desired misclassification error bound of for one of h, h.
For & # q/2, we use OEEV O(E//mii// Saiin/maa/// Amax/q) for the eтror bound in Lemma 4.1. Tak- ing m O((d/=))log() log(d/))()nma)) >mmin) )8g²) in Alg.
we obtain the following bound: min - r=112, ||f r.112] S E5/miin Amaa (16cog) with probability - 5/2. Using & 2
O ddlogg + log(1/5))g
Avex 2amm
Lemma 4.2 yields the desired misclassification error bound of
on h² w.p. 5.
Proof. (of Lemma 4.2) Applying Lemma 2.3 we obtain that at least one of h, h has an instance misclassification error of at most OlE / / WLOG assume that h satisfies this error bound ic., (r)lf(x) * h(x)) I CoE /maxx/ Ania =: e'. Since the separating hyperplane of the LTF f
7

---

passes through the origin, and D = (N, Σ) is centered, Pro(f(x) = 1] = Pro (f 0] = 1/2. Thus,
Pr(M(x) + ((x f(x) = 1].
1 Pr(((()))))))))) + [(x) [(x) 0] - 28'.
Therefore, the probability that random bag from the oracle contains a feature vector on which and h disagree is at most 2qE'. Applying the Chernoff bound (see Appendix B.1) we obtain that
with probability at least - 5/6, BagErrsample (hm M) 4ge". Therefore, in Step 3.c. h satisfies
BagErr (h", MM) S 4qe'
On the other hand, applying Theorem 2.2, except with probability 6/3, Prm[/(x) + (x)x)] S 16ge' 16cogE //mux/ Aminn Therefore, except with probability 6/2, the bound in Lemma 4.2 holds.
4.1 Proof of Lemma 4.1
We define and bound a few useful quantities depending on k, 2, Amin and Amax using S k S 1.
2
Definition 4.3. Define, (i) K1 == 2k 1)
2 so that 0 S k1
S 2/z, (ii) R2 == 1 t 16
g-l
q
so that
16 K2 S 5(9-1} (iii) K3 =
K2 So that 16
S Kg S
T Dilo-1 and (iv) 0 =
I-MI
2Ama Auia
(0,2xx
- N2)
+ 1 so that
3 Aumn
37me < (1 (--2/))Amm Amis
For the analysis begin by showing in the following lemma that f in the algorithms is indeed fr. the covariance estimates were the actual covariances.
Lemma 4.4. The ratio p(r) := := Egr is maximized when Hr,
Moreover,
r E' and
p(r) 2 1 (1())
where
(())
Vr Er Vr'EEVE r!
IJ EBr = (11)))))))ki) r EpEr= = Er(2 ((x) - -K2)
Proof. Let = 112 then X ~ N =) rZ where Z ~ N(0, I). Further, pos X)
pos (u²z) where u = Tr//|Tr||2 Using this, we can let XB TZ as a random feature-vector sampled uniformly from random bag sampled from O. Also, let Xn rZp be the difference of two random feature vectors sampled uniformly without replacement from a random bag sampled from O. Observe that the ratio p(r) = Var(r' Xpl/ Var X = Var(u Zp]/ Varlu ZB).
Let uI := Tr./ Tr. Il2, and g" == _ which is NO0 1). For a E 1), let Z, be Z conditioned on pos (u.z) = a. Let gh == u. E 13, be the half normal distributions satisfying El(g2)) and [[gā] = (-1)1-a 22/m. With this setup, letting g u ZB and g u. we obtain (using Lemma B.2 in Appendix B.2)
Var[gg] = 1- K1, Varlghl = 2(1 - kI) + K2
Now let ū be a unit vector orthogonal to u. Let g = à Z be NO, 1). Also, let Ja = - Z,, for f0, 1}. Since Z, are given by conditioning Z only along u. 9n ~ NO. 1) for E {0, 1]. In particular, the component along ū of Z (call it ÿn) is NN, 1) and that of Zn (call it ÿn) is the difference of two iid N(0, 1) variables. Thus, Var[ğn]
1 and Var(ān) orthogonality all these gaussian variables corresponding to û are independent of those corresponding to u, defined earlier. Now let u = au, + fü, where B === v1 a be any unit vector. From the above we have,
2. Moreover, due to
Var [u ZD] Var [u ZB]
Var [ag] + [ğD] a Var [9 + 3 Var [ö_]
2a K1) + a²k² 2,8
Var lagn + Bğø] a Var [g + 32 Var [ğa]
a2(1-ki) + 32
a²
2 a²ki
(6)
where the last equality uses = vI a Letting u (Tr.rr.) Tr (() completing the proof.
Tr/ Tr||2 we obtain that a
8

---

Lemma 4.5. argmaxp(r)
|=| BB" - Principalliiggeneeetor (2 1/2 E 2/g Σn 1g
Proof. This follows directly from its generalization in Appendix B.5.
We now complete the proof of Lemma 4.1 (with instead of 6/2 for convenience). By Lemma 3.1, taking m 2 O (dd/ef) log(d/6)) ensures that E /2 S & Amax and |E S &1 Amux w.p. at least 1 1-6 5 where Eg ΣB- ΣB and ED = Σn Σp. We start by defining p(r) == r Eor which is the equivalent of p using the estimated matrices. Observe that it can be written j(r)
Enr
r "ErrtrEEn Ear
E'rrr EDr
Using these we can obtain the following bound on j:: for any E IR4, l((r) - p(r)] S 02n ((()) w.p.
at least 1 - (*) as long as (1-ki] Ania, which we shall ensure (see Appendix B.4). Auua
For convenience we denote the normalized projection of any vector as 1//2, Now let -
i E Rdd be a unit vector such that min F- 12 || + 2 Hence, using the definitions from Lemma 4.4, [x(r) S - e2// while y(r.)
which implies p(r) S p(r.) = K3. Choosing ει < 1 S.. we obtain that p(r.) 001) > p(r) (1+)) 021). Using this along with the bound (**) we obtain that w.p. at least
2 Kg Note that
8, f(r.) > ((r) when &g >
0. Since our algorithm returns i as the maximizer of P, w.p. at least 1 - 8 we get min
F. F.112,11e + F.l12) S Eg. Using Lemma 2.1, min [|] - r. ll, || + r.l12 S V
Substituting rr 1l2 S w.p. at least 1 5. The conditions on e1 satisfied by taking it
Avsa
Aenn
62
VV Aun
||r
to be 0o
mage Arii 6(2+ms))Am
and thus we can take 2 o (dde")
Amna
)'82 82 (2+ 2 X3
)))
Aain
(d/e") log(d/0)
Aamx Amin
)
using Defn. 4.3. This completes the proof.
5 Proof Sketches for Theorems 1.3 and 1.5
Theorem 1.3: Case (O.. I), f(x) pos(r..), k * q/2. The algorithm (Algorithm 3) and the proof is in Appendix A. We argue that a vector sampled uniformly at random from a bag is distributed as wX1 (1 Xo where X. .V NN, conditioned on f(X.) 1 r.v. s.t. p(w = 1) = k/g. This along with the fact that uncorrelated Gaussians are independent, allows us show that the expectation is 0 in any direction orthogonal r. and to compute the expectation in the direction of r.. We then use Lemma 1.1 to get the sample complexity expression.
a and w is an independent
Theorem 1.5: Case N(H, Σ), f(x) = pos(r.x + c.). The algorithm (Algorithm 4) and the detailed proof is given in Appendix C. We start by generalizing the high probability geometric error bound in Lemma 4.1 to this case (Lemma C.1 proven in Appendix C.1) and appropriately generalize K1, K2, K3 and 0. The rest of the proof is similar Section 4.1. An extra factor of O is introduced to the sample complexity from Lemma 3.1. Next, assuming the geometric bound, we give high probability bound on the generalization error Lemma C.2. In this analysis, we bound the BagErr (h, M) where h(x) = pos(F' x + C,) with ř being the geometric estimate of r, and M is a sample of bags. This introducing the dependencies on (v (VAmax + [| Vmmin well as (l). Our subroutine to find è ensures that h² (x) pos(FT x ê) satisfies BagErr (h" .M) 2 BagErr Bageersample (h, M)). We then use Theorem 2.2 to bound the generalization error of h" Lemmas C. C.2 together imply Theorem 1.5.
sample
Experimental Results
General Gaussian. We empirically evaluate our algorithmic technique on centered and general Gaussian distributions for learning homogeneous LTFs. For homogeneous LTFs the general case algorithm (Alg. 4 in Appendix C) boils down to Alg. 2 in Sec. 4. The experimental L.PP datasets are created using samples from both balanced as well as unbalanced hag oracles. particular, for dimension d E {10, 50), and each pair (q, k) e {(2, 1), (3, 1), (10, 5), (10, 8), (50, 25), (50, 35)}

---

and m = we create 25 datasets as follows: for each dataset (i) sample random unit vector r" and
let f(x == pos (x) (ii) sample μ and randomly (see Appendix F for details), (iii) sample m 2000 training bags from Ex (Ju, 2) q, k). (iv) sample 1000 test instances (x, f(x)). X + Nu, E). We fix = O for the centered Gaussian case.
include the random LTF algorithm in which sample 100 random LTFs and return the one that satisfies the most bags. In addition, we evaluate the Algorithm [25] on (g. k) = (2, 1), and the Algorithm of [26] on kq) (3, 1). We measure the accuracy of each method on the test set of each dataset. The algorithms of [25, 26] are considerably slower and we 200 training bags for them. The results for centered Gaussian
For comparison
in Table 1a and for the general Gaussian are Table 1b. We observe that our algorithms perform significantly better in terms of accuracy than the comparative methods in all the bag distribution settings. Further, algorithms have significantly lower error bounds (see Appendix F).
Notice in Tables la and lb that the test accuracy for Algorithm 2 decreases with increase in q and This consistent with the sample complexity expressions Thm. 1.4 and Thm. 1.5, Also, notice that the test accuracy for Algorithm 2 for general Gaussian (Table 1b) is usually lesser than the same for centered Gaussian (Table la). This supports the theoretical result that the sample complexity increases with the increase in I.
Appendix F has additional details and further experiments for the N(0, () with homogeneous LTFFs, N (1, Σ) with non-homogeneous L.F's as well as noisy label distributions.
Table 1: Algorithm A2 vs. rand. LTF (R) vs SDP algorithms (S)
k
A2
R
S
d
k
A2
R
S 90.10
10
98.12
78.26
88.40
10
98.18
78.32
10
98.27
77.16
67.31
10
97.92
75.14
70.80
10
10
97.9
78.66
10 10
5
97.86
70.41
10
10
8
97.87
77.64
10
10
8
97.4
69.86
10
50
25
97.87
76.67
10
50
25
97.57
70.48
10 50
35
97.9
77.17
10
50
35
97.6
62.86
50
95.64
61.25
57.83
50
94.99
58.68
61.12
50 3
95.21
61.15
58.69
50 3
95.6
59.8
62,39
50 10
5
95.59
55.06
50 10
5
95.27
57.43
50 10
8
94.34
63.17
50 10
8
94.44
61.82
50
95.16
55.76
50
94.97
53.98
50 50
94.74
61.02
50
94.33
56.97
(a) (0, Σ) feature-vectors.
(b) N(u, E) feature-vectors.
7
Conclusion and Future work
Our work shows that LTFs can be efficiently properly learnt in the LLP setting from random bags with given label proportion whose feature-vectors sampled independently from a Gaussian space, conditioned on their underlying labels. For the simple case of (0, 1) distribution and bags with unbalanced labels provide mean estimation based algorithm. For the general scenarios develop a more sophisticated approach using the principal component of a matrix formed from certain covariance matrices. To resolve the ambiguity between the obtained solutions employ novel generalization eттоr bounds from bag satisfaction to instance classification. We also show that subgaussian concentration bounds applicable the thresholded Gaussians, yielding efficient sample complexity bounds. Our experimental results validate the performance guarantees of our algorithmic techniques.
In future work, classes of distributions other than Gaussian could be similarly investigated. Classifiers other than LTFs are also interesting to study in the LLP setting.
References
[1] Awasthi, M. Balcan, and M. Long. The power localization for efficiently learning linear separators with noise. J. ACM, 13:55:20 2017.
10

---

[2] A. Bhattacharyya, S. Ghoshal, and R. Saket. Hardness of learning noisy halfspaces using polynomial thresholds. In Proc. COLT, volume 75, pages 876-917. PMLR, 2018. URL http://proceeddii mlr. mmlr.preas/v7555 httt:paas//////attacaaarrae bhtttacaaryyaa111a... html.
[3] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the vapnik- chervonenkis dimension. ACM, 36(4):929-965, 1989.
[4] Robert Istvan Busa-Fekete, Heejin Choi, Travis Dick, Claudio Gentile, and Andres Munoz medina. Easy learning from label proportions. arXiv, 2023, URL httpp://arxs org/ //////////// 2302.03115.
[5] L. Chen, Z. Huang, and R. Ramakrishnan. Cost-based labeling of groups of mass spectra. In Proc. ACM SIGMOD International Conference on Management of Data, pages 167-178, 2004.
[6] Lin Chen, Thomas Fu, Amin Karbasi, and Vahab Mirrokni. Learning from aggregated data: Curated bags versus random bags. arXiv, 2023. URL https://arxiv, wtwpiiv.rgga/bb////eee 09557.
[7] Amit Daniely. A PTAS for agnostically learning halfspaces. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, Frunce, July 3-6, 2015, volume 40 of JMLR Workshop and Conference Proceedings, pages 484-502, 2015.
[8] S. Dasgupta. Learning mixtures of Gaussians. In FOCS, pages 634-644, 1999.
[9] N. de Freitas and H. Kück. Learning about individuals from group statisties. In Proc. UAI, pages 332-339, 2005.
[10] L. M. Dery, B. Nachman, F. Rubbo, and A. Schwartzman. Weakly supervised classification in high energy physics. Journal of High Energy Physics, 2017(5):1-11, 2017.
[11] G. Dulac-Amold, N. Zeghidour, M. Cuturi, L. Beyer, and J. P. Vert. Deep multi- class learning from label proportions. CoRR, Abs/1905.12909 2019. URL btttp://arxin org. aa/////s///////////////// 12909.
[12] V. Feldman, Gopalan, S. Khot, and A. K. Ponnuswami. On agnostic learning of parities, monomials, and halfspaces. SIAM J. Comput., 39(2):0066455 2009.
[13] Benjamin Fish and Lev Reyzin. On the complexity of learning a class ratio from unlabeled data. J. Artif. Intell. Res., 69: 1333-1394,, 2020.
[14] V. Guruswami and P. Raghavendra. Hardness of learning halfspaccs with noise. Proc. FOCS, pages 543-552, 2006.
[15] J. Hernández-Gonzále. I. Inza, and J. A. Lozano. Learning bayesian network classifiers from label proportions. Pattern Recognit., 46(12):3425-- 34400, 2013.
[16] A. T. Kalai, A. R. Klivans, Y. Mansour, and R. A. Servedio. Agnostically learning halfspaces. In 46th Annual IEEE Symposium Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, pages 1 11-20. IEEE Computer Society, 2005.
[17] A. R. Klivans, P. M. Long, and R. A. Servedio. Learning halfspaces with malicious noise. J. Mach. Learn, Res., 10:2715-2744 2009.
[18] D. Kotzias, M. Denil, N. de Freitas, and Smyth. From group to individual labels using deep features. In Proc. SIGKDD, pages 597-606, 2015.
[19] J. Liu, B. Wang, Z. Qi, Y. Tian, and Y. Shi. Learning from label proportions with generative adversarial networks. In Proc. NeurIPS, pages 7167-7177, 2019.
[20] D. R. Musicant, J. M. Christensen, and J. F. Olson. Supervised learning by training on aggregate outputs. In Proc. ICDM, pages 252-261. IEEE Computer Society, 2007.
[21] J. Nandy, R. Saket, P. Jain, J. Chauhan, B. Ravindran, and A. Raghuveer. Donain-agnostic contrastive representations for learning from label proportions. Proc. CIKM, pages 1542- 1551, 2022.

---

[22] G. Patrini, R. Nock, T. S. Caetano, and P. Rivera. (almost) no label no cry. In Proc. Advances in Neural Information Processing Systems, pages 190-198, 2014.
[23] N. Quadrianto,
Smola, T. Caetano, and Q. V. Le. Estimating labels from label proportions. 2009. 2009.
J. Mach. Learn. Res., 10:2349-2374
[24] S. Rueping. SVM classifier estimation from group probabilities. In Proc. ICML, pages 911-918,
2010.
[25] R. Saket. Learnability linear thresholds from label proportions. In Proc. NeurIPS, 2021. URL https://oppenrevie aeeee/Eooruun.d-SSaaaaeBaxx
[26] R. Saket. Algorithms and hardness for learning linear thresholds from label proportions. In Proc. NeurIPS, 2022. URL https: https://openreviie www.://oowwmidd112oooo..o.
4.
[27] Rishi Saket, Aravindan Raghuveer, and Balaraman Ravindran. On combining bags to better learn from label proportions. In AISTATS, volume 151 Proceedings of Machine Learning Research, pages 5913-59199999 1913-5927. PMLR, 2022. URL https://proceeedings mlr press/v151/ saket22a. html.
[28] C. Scott and J. Zhang. Learning from label proportions: mutual contamination framework. In Proc. NeurIPS, 2020.
[29] Leslie G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134-1142, 1984.
[30] Vempala. Learning convex concepts from gaussian distributions with PCA. In FOCS, pages 724-130, 2010.
[31] R. Vershynin. How close is the sample covariance matrix to the actual covariance matrix? J. Theor. Probab., 25:655-686, 2012.
[32] Roman Vershynin. High- ligee-Dimesional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematies. Cambridge University Press, 2018. doi: 10. 1017/988 10829781111111100
[33] J. Wojtusiak, K. Irvin, A. Birerdinc, and A. V. Baranova. Using published medical results and non-homogenous data in rule learning. In Proc. International Conference on Machine Learning and Applications and Workshops, volume 2, pages 84 89. IEEE, 2011.
[34] F. X. Yu, D. Liu, S. Kumar, T. Jehara, and S. F. Chang. xSVM for learning with label proportions. Proc. ICML, volume 28, pages 504-512, 2013.
[35] X. Yu, K. Choromanski, S. Kumar, T. Jebara, and S. F. Chang. On learning from label proportions. CoRR, abs/1442.5990, 2014. URL
5902.
12

---

A Proof of Theorem 1.3
For the setting of Theorem 1.3 we provide Algorithm 3.
Algorithm 3 PAC Learner for homogenous LTFs from unbalanced bags over .V (0,1)
Input: Ex(f, D.q. q, k), m, where fxx = pos (r.x), ||r,||2 = 1, k + g/2.
1. Compute üg using MeanCovsEstimate with m samples.
2. k > 9/2 Return: p p l2 else Return: -AB/ LBB12
Define X. (0,1) conditioned on f(X.) for a E {0, 13, and let XB denotes the random feature-vector u.a.r sampled from a randomly sampled bag. By the definition of the bag oracle, Xg == wX1 + (1 w) W)x where is an independent {0. 1}--ermoulli n.v. s.t. p(w 1) = k k/q- Let = r X B- 9 ((01 1) and let 9 = r. X.. E {0,1} 1). Since r. is unit vector, Sh is
half-gaussian and by direct integration obtain E [oall =--1)² 1- 22/T T for E {0,1}. Thus,
Elg = Eloil + (1- A: 9
(2 q -
2k
V V
2 0s k) S
Elgöl klg,
On the other hand, let g+ g-= r s.t. rTr. = 0 and |||||| = 1, and let g = rx,, a E (0, 1).
Since X (a E {0, 13) given by conditioning standard Gaussian vector only on the component in the direction of r., its component along any direction orthogonal to r- is a onc-dimensional standard Gaussian. Therefore, 9 are iid N [(, 1) (a E {0, 1J), and so is g+, implying E [gt] 0.
Thus, the value of TE [Xn] is (i) v/g, k) if r.; and (ii) if r 1 r.. In other words, μp = E { B. nf(g, k)r,, and ||BBle ll2 In(g, k)). Hence, if n74, k) > 0 then r,, /B////l// | la else r, = - PB//Bllee Haal|
With m O (n(q, (d/E3) log(d/8) = O (Id/c2 log(d/))). the following lemma along with Lemma 2.3 completes the proof of Theorem 1.3.
Lemma A.1. Algorithm 3 returns a normal vector i such that ||., fll2 S E wap. at least 1 - when m 2 ((d/E²) log((d/))) for e, > O.
Proof. First, we can assume & < 2 since the distance between two unit vectors is at most 2 and therefore the lemma is trivially true for & > 2. By Lemma 3.1, taking m 2= 0
log(d/5) (od//))oog((())
O (niq, (d) log(d/8)) ensures Í| - pBll2 S sln(g. k E [4 w.p. 6. There- fore, by triangle inequality, f p |||| S s B| | || 1 |
4, 5,1 + fl.
Now, r, = sign(n((, k))
/ la and the algorithm returns f = sign (7 k)) p 112
| r. r2l/2-
AB
PB
(ul|uBl22 p pl 2l + pB 1 1l -otiill---lllle Halleslla|
| 2
A |
jpB
pBlla
1 l1 + |
|
| 1
2e
Se E for S
22 $ p
4 -
B
Useful Tools
B.1
Chernoff Bound
We state the well known Chernoff Bound.
Theorem B.1. Let X,,...,X, be tid {0, 1)-valued random variables. Let S be their sum and E[S]. Then, for any > 0,
Pr 2 (1 8)pl s exp(-6²p/12 6)).
13

---

B.2 Relationship between ΣB and Ep
Lemma B.2. 1B En are as defined the preliminaries and X. = XX = a, then
k
k: 9
=E=+ + q
1
- - -
E(Xol)*
q
Proof. Let 3 be random-feature vector sampled uniformly from a random bag sampled from O. Hence, with probability k/q it is sampled from X₁ and with probability of - k/q it is sampled from Xg. Hence,
PB = E. E[ = [|,]]] + (1 (1-5)
E Xo)
ΣB = - - B[ where E[XX"] = (1-1) K [|XxXX]
Let DD= -0-x-X where X') are a random pair of feature-vectors sampled (without replacement) from random bag sampled from O. Hence, with probability ()/()) is the difference of two vectors sampled independently from X,, with probability (²²")((3 is the difference of two vectors sampled independently from Xg. with probability k(g- (2) it the difference of one vector sampled from X1 and another sampled independently from Xo and with probability ki(y- - 2 (2). the difference of one vector sampled from Xo and another sampled independently from X1, Then,
1
k
9 k X()(,, x() +
ED xXxxXX1
[X
( Xx) x))
2
2
k(g k)
[ - Xx)(X, 1 k(g k)
(Xo - x1)(X= - Xi)T]
+
2
2
Due to independence, obtain for a E {0,1}
[X,, - Xx)(XX x- X 2E[X,
[X -X (X_, X(-a) E| x E(X, EX
Hence,
1
2 k
k(g -k) B|X|X]]+ + 2 ( (9-k)
+ +kgg - k)) B[X,XXI
Ep
(2)
2
(A(k 1)E E X + (q 1)(4 - ks 1)(xo"
+ (k(q - k) EX, + E(X,)X(
Simplifying ED 22E get
2 ED - --1 1 9
(
[E[],] (EXX,) E(X,))
B.3 Bound on (r) when x" Egr. = 0
Lemma B.3. EEr, then 7(x) s
Ami Ana
- max I m0. (q.k,))
Further if E then
(x() <
Anis
(1 (1-ki(q.k)) k)).
Anax
Proof. We begin by observing the for any r E R2d, || 1, Var Zn) K1 k. E). Hence, Amin (Eg) (1 max(0, xi (q. k. Amin and Amax EB) - (1 min(0, Ki (g. kr Ama)-
14

---

Thus, by Soutchy-Schwarte inequality,
Amax
| ! E 1/212 S /1 min(0, K1 (g. K E))
Amin
Σ
1/2 - B
1
Amax
v max(0, (0, 11 (q. k. E))
Amin
Define F
E1/2r for any
p. Observe that ((r) Frr..
Now since r² Egr, 0, by
12 1
substitution
11/221111 1011//p
( Σ 1/ = 0. Thus, using Cautchy- Schwartz again
1
1/2
Σ
1/2F Σ /
f/.l v Σ 1//
1/2//11
E Σ 1/2F=
|
Amin Amax
2(
max (0, ni (q. k. E1)
|Σ
Σ
1/2
11
B
Again using Seutchy-Schward
1و/ Σ 11/2p-----
Σ
Σ
11/22-1/2
|
8.112
| Σー Σ E-1/2112
Amin Amax
2(1 max (0, Ki (g. k., E)))
1 - min 13 (g. k !))
Thus,
7()) = = S
Annin
max(0, K3 (g. k ()) min(0, 1i (q, k,
Amax
If c 0, then kı k1(q, k) 2 0. Hence,
Amin
7(r) 1
(1 k))
Amax
B.4 Bounding error in X
Lemma B.4. If EBl|2 edmux and [nd||Ep) |Epllz S emmax where EB EB EB and Ep ΣD ED
then,
K((r)) ~ lo(r)10c
for 8 as defined in Defn. 4.3 or Defi. C.3.
Proof. Let a(r) == r- Enr, b(r) ;= r' e(r) == r forr == r EBr. Using the bounds
on the spectral norms of EB and ED, we get that |e(r)] I E Amax and [f(r S E Also, using variances in Lemma C.4, a(r) 2 >mmm (2 10-ax(00,200 2k1 -k2)) 2 0 and b(r) 2 Amin (1-max(0,. k1)) Z
Hence, we can conclude that
e(r)
Amax
f(r) b(r)
Amax
and
S
Amin
2 max 2x K22)
Amin
max(0, Ki)
Observe that p(r)/p(r)=
1 - (xx)/(((x)
Hence, b(rl/((r)
Aua Auia
1axmax (0,2N1 -x2)
p(r)
1 1
Ana
Auia
2 2-
1
Aua
p(r)
1
Ana
Aviin
Dnin
1-max(0,,s1)
Now, whenever 8 5 1 max((,,1)) daii
Amaa Amm
2 1/2 and,
Amaa
I-max(O.xs)
1 Anes Anis
< <3/2. Thus, obtain that
((r) p(r)
p(r) < 0s
where as defined in Defn. C.3. we substitute = O, we get that 81 2 and we get 0 as defined in Defn, 4.3.
15

---

B.5 Ratio maximisation as PCA problem
Theorem B.5. If and B are positive definite matrices, then for all R
1. F Ar B 1/BAB
1/2
B
Br
B
F Br
1/2g where argmax B-112 A
2. argmax
BB
r 1=
||
Proof. The first statement comes from the substitution. Now, A'Ar is homogeneoous in r. Let a
F
kb, E
Arr
Ar Br
argmax
argmaa
|||||a=
Br
B 1B-1
argmax B-1
|F
F B 1/2
AB
1/2
B 1/2 argmax
||=||
B 1/2 argmax Fl B ||
1/2 AB
AB-1/22
Hence, argmax F Br |rl==1
Ar B B-/222'
where F argmnax B-11/2AB 1122
B 17
|
B.6 Proof of Lemma 2.1
Proof. Let r/
Ar and r2 Br2. As F1 and r2 are unit vectors, || I |r1ll2 I ||A]|2.
||| r22l2
|Ar Ary + Ar Br2l12
A l2 [r r2ll2 + ||A B|12||22112
A 1l(2 +1)
ri
r/2
r| 12r
|r 1122
|1|15/11ar| - ||M 12ll + |r |1
||r| 12r2
|
|| 12
2
|r 1| |r212
|| la
|
112
+
brillel|ri rélla
2( A(11A) + E1))
|r
11112/112
A (2 +1)
||A 11-
(E2 + E1)) Amaa (1)
Amax (A)
(82 + 61) if Amax (A)
(E2 + E1) S
Amaa(A) (4)
(E2 + E1)
Amin (A)
Amin (A)
Anta Male(Al (A)
C Proof of Theorem 1.5
For the setting of Theorem 1.5, we provide Algorithm 4. It uses as subroutine polynomial time procedure PrincipalEigen Vector for the principal eigen-vector of symmetric matrix. For notation, let r 1/ then by Lemma E.13,
write our linear threshold function po c.) = pos(u. E) where Z ~ N(0, where & == e.triu For any r E Rdd. define u == Tr||- Let & and t be the standard gaussian pdf and edf respectively.
|[ Ila u. Trr/I[Tr.l] |2-
The following geometric bound is obtained by the algorithm.
Lemma C.1. For any s, 1), m O (d/e*) log(d/8) in Step 3 of Alg. 4 satisfies min(lli- r+l12, || + 112) SE, w.p. 1 8/2.
Amn
(2)) ) then i computed
Ame
16

---

Algorithm 4 PAC Learner for LTF's in over Nu,, Σ)
Input: 0 0= ==x(J, (1, M), q, k), m, where f(x) = pos (r! + co), ||r-|12 1.
Compute E3 En using MeanCowsEstimator with m samples.
2. F 3 1 PinncipalliggnNVeettrr,, Let
if Σ exists, else exit.
4. If
g/2
a. Sample collection M of bags from O.
b. For each bag B, in M
i. Project each vector x (4) in 13, on i.
Order these projections a descending order f xj f {
Define hj = pos((' x + f f'x/²) )
c. Return h" E {fi...., h which has lower BagErr (h" MV).
5. else
a. Sample a collection M of bags from O.
b. For each bag B, in M
i. Project each vector xj in By on
ii. Order these projections in descending order i f'x, (1)
x
ii. Define h2 = pos(fT x + ) )
c. For each bag B, in M
i. Project each vector x) in Bj on on-
ii Order these projections descending order -xx/ Define hj = pos(- f
f xx
fTx (k))
d. Return h" {h1...., h2 hi..... h which has lower BagErrsample (h" M)..
The above lemma, whose proof is deferred to Sec. C.I, is used in conjunction with the following lemma.
Lemma C.2. Let E, 8 (0,, 1) and suppose that i computed in Step of 4 satisfies if 9/2
minflli- 12, ||r rr 2 E,, Then, with O (d(log log(1/6))/e h² computed in Step 4.c or Step 5.d satisfies
Pr Ih # f(x)) D
SqE
CO
Aus +
||14|2 Amin
(l (E))
and if 2/2,
min(Pr [h (x) + [())] (1- # [(x))) < +()) (())
Sqe
coV
Amaz
+ el
Ialll
Ani
w.p. 1 - 8/2, where co. are the constants from Lemma 2.3.
With the above complete the proof of Theorem 1.5 follows.
Proof. (of Theorem 1.5) Let the parameters 8, be as given in the statement of the theorem. We
use O (((()(1 (110)1-4400)) ((E)) for the error bound in Lemma C.I. We now take m be of m aly Ann 211))
o (11/))) (0())))0)))))))))))) (())) log(d/6)
4 "(VMurttlllll 4 q8 in Alg. we obtain the following
Amma Auia
Auns
bound: min - r, r.l12, 11/2, ||f + r. 1.112) S (#(0)1 D01))i with probability 8/2. Using o (d(log(g) log ( (2(
gro top ((a))a)
+1
Lemma C.2 yields the desired misclassification error
+(e))_Am..)
bound of on h² w.p. - 5.
Proof. (of Lemma C.2) Define h(x) == pos(F X + c.) and h(x) = pos(-i-x + c.). Applying
Lemma 2.3, obtain that least one of h. h has instance misclassification error of at most
17

---

(EE( V /mmxx/ Amin + | A.in))). WLOG assume that h satisfies this error bound i.e. Pro [f(x) +
h(x) 1 <(ca / Amus Amin + 14/2/ Amin) =: e'. Note that, Pro [x() 1] = (b(), Pr.p [x()
0] - 1 ((). Thus,
Pr(h(x) # f(z) [xx)=1]=//0(0)) D
=
Pr(l(()) # f(x) f(x) = 0] S 5 (=111(1)))
D
Therefore, taking a union bound we get that the probability that a random bag from the ora- cle contains a feature vector on which ʃ and h disagree is at most gesstt (e) - +())). Ap- plying Chernoff bound (see Appendix B.I) we obtain that with probability at least
6/6,
BagErr sample (h, I (q) - (()). Therefore, h satisfies BrgErr (h" (h,, M) S (re2/(((((11)))))) - (()). Hence, there exists at least one (y)x)) = pos(f"x x + xTx(²) will satisfy BagErr sample (hj, M) < among all (x),, BagErr sample (h', .M) S (0) (())). (()).
- (())) Since, h (x) has the minimum sample bag error
On the other hand, applying Theorem 2.2, except with probability 6/3. (fx( *
(x)] I 8qE' (1)() - .(()) = 318X1-b(1) (cov Aminn/Amin + ei cillulle/v Amin) if k +
Sqe
q/2 and min(Pro[f(x) # h" Pro|f(x # (1 h²(x)))) I (())/ (())
Sqe (((])) ( Amax/ Ami + ei ca|1m111/ Dtlll///Ammi Amia)
q/2. Therefore, except with probability
5/2, the bound in Lemma C.2 holds.
C.1 Proof of Lemma C.1
We use these to generalize a few quantities we had defined earlier. We obtain their bounds using E.2, Definition C.3. Define:
((L) (1 (112(1))
Ed(I) ( -1- -0(0((=(11)(0)) (1-9(())
K1 2 -6/4
K1 =
(()(1 (())
+(0)(1 +()))
2 k
k.
Φ())
2
R2
q ))
(1))(1 +()))
R2 282 /
when l > 1
q - 9
K2
262
R3
Ki 2
when l >
(1 - (1)(11 - max(0, (1,)))
q² (1 + 22/4)
2dmax
1
3
3
-axx 2n1 - k2) 1 max(0, m2))
S 580 < (1 - K2)Amin
Amain
Amin
Where Kj's are some finite functions of K.
Similar to Lemma 4.4, we again show in the following lemma that i in the algorithms is indeed ir. if the covariance estimates were the actual covariances.
Lemma C.4. The ratio p(r) = r Epr/r' Egr is maximized when r = tr., Moreover,
>(r)2kg
r'Er. and
p(r) 2 1-)(pmm where 7(1)
Er Er.
I = =r (1)))((()k)s)) I ''Er=r''En
(2m) -x2)
Proof. Using the transformations to Z. we can let X = rZ as a random feature-vectur sampled uniformly from random bag sampled from O. Also, let X IZp be the difference of two random feature vectors sampled uniformly without replacement from a random bag sampled from O. Observe that the ratio p(r) = Var(r /)) //ar(r X,) Var(u T Var(u' Zn).
Let g" = z which is (0, For E (0, let Z, be Z conditioned on pos (u. () = {0. 1]. d6 lower-tailed one-sided truncated normal distributions truncated at and of upper-tailed oie-sided truncated normal distributions truncated f. Hence, E[gī] = (())/1 (()). E[ghl (())/4(() 1 = 1 1 ló(e)/(1 (()). E[ 1 (E).
Let 9. = u.Z.,
18

---

With this setup, letting d3 := -u and DD := Zo we obtain (using Lemma B.2 in Appendix B.2)
Varlgh] = - K1, Var[ghl = 2(1 - -x1) + K2
Now let ū be a unit vector orthogonal to u. Let 9 = ū u be No, 1). Also, let gu = - Z for {0, 1). Since Ze are given by conditioning Z only along u. 9u ~ N(.. 1) for E {0.1), In particular, the component along à of ZB (call it (B) is N(0 1) and that of Zo (call it (D) is the difference of two iid N0,, 1) variables. Thus, Varlğn] orthogonality all these gaussian variables corresponding to i are independent of those corresponding u, defined earlier.
and Varlān] 2. Moreover, due to
Now let u = au, + 3ü, where 3 = vI a be any unit vector. From the above we have,
Var lu Lu
Var jag' 3ğDl a² Var [ + 3 Var [gp] Var [ag] + fğøl
Var u ZB
a² Var g + g2 Var [+a]
2a - k1) + a K2 + 2
a² k1) + 182
a a²K²
2 +
-a
where the last equality uses = a Letting u Tr/ [rrle we obtain that a (r.Tr.) (r)) completing the proof.
IT 2l
Lemma 4.5 shows that ratio maximization can be treated as an eigenvalue decomposition problem of the matrix ΣE >/ Di We now prove that the error in the estimate of f given to us by the algorithm is bounded if the error in the covariance estimates are bounded. The sample complexity of computing these estimates gives the sample complexity of our algorithm.
We now complete the proof of Lemma C.1 (with å instead of 5/2 for convenience). By Lemma 3.1, taking m 2 O (Id/=])O(E) log(d/5)) ensures that |E S E1 Amax and |EDll S Em w.p. at least 1 - 5 where En En En and Ep Σn Σn- We start by defining p(r) Er which is the equivalent of using the estimated matrices. Observe that can be written as Using these can obtain the following bound on 인 for any gd F'
p(r) r' L'Eurtr'En Ear
(p(r) p(r)l S 02 |p(r)) w.p. at least 1 d (*) as long as (1-max(0.x1) Ama which shall ensure (see Appendix B.4).
For convenience we denote the normalized projection of any vector F
| Now let
D//r
F E Rd be unit vector such that min F=ll2, || + f= 2 E2. Hence, using the definitions from Lemma C.4, [r(r) I c2/2 while (r.) = 1 which implies p(r.) - p(r) 2 k253/2. Note that p(r) $ p(r.) = 2 + K3(1 max(0, k))) Choosing E < (ee==aa(=max00.s)))) E2 we obtain that p(r,)(1 0=1) > (1 dεz). Using this along with the bound (*) we obtain
that w.p. at least 1 - 8, p(r.) > p(r) when E2 > 0. Since algorithm returns f as the max- we get min [ F. || + F. 122 S S2. Using Lemma 2.1,
imizer of أ. w.p. at least
min fllf - r, 1l, ||e + 112] S 4v
Ama Auin
E2. Substituting 62 = V
Arai ||r r. I E w.p. at Anx
least 1 - 5. The conditions on E are satisfied by taking it to be S o
012+na (maxa (U, ))
max((0.x) 2)
and thus we can take m 2 o (d))))
Amu
0a
Amn
o logg///))
(Auxx) 9a
since 1/k3 S q2 //4)// whenever e 1(eefn. C.3).
Amin
This completes the proof of Lemma C.I.
D Generalization error Bounds
We show that if a hypothesis LTF h satisfies close to fraction of sufficient number of bags sampled from bag oracle then with high probability h is a good approximator for the target LTF f (or its
19

---

complement in the case of balanced bags). The first step is to prove generalization bound from the sample bag-level accuracy the oracle bag-level accuracy.
Theorem D.I. Let O Ex(S, D, q, k) be any bag oracle for an LTF in d-dimensions, and let M be a collection of m bags sampled itd from the oracle. Then, there is an absolute constant Co s 1000 s.s. w.p. least 6,
BagErr (h, D, g, k) BagErr samle sample M)
when m 2 Cod (log log(118) for any 6, >
Proof. The proof follows from the arguments similar to the ones used in Appendix of [26] to prove bag satisfaction generalization bounds. Consider bag loss function of the form (h, B), (ØS B)). where of (g. 13) == ((y,B) where yg.B is the vector of (g(x))xEB, for <: 1) + R. The result of [35] showed generalization error bounds when (i) is 1-Lipschitz w.r.t to sc-norm, and (ii) & is 1-Lipschitz in the first coordinate. We can thus apply their results using the bound of (d + 1) the VC-dimension of LTFs in d-dimensions to show that the above bound on m holds (with Co/8 instead Co) for the generalization of the following bag error:
(,t, - hB),,))),
where
c if ExEBB9(x) 16
(B, 9. t)
otherwise.
fort E 901.. We can bound our bag satisfaction error by the sum of the generalization errors of (B, f (B, h, k)), and (B, k 1) y(B, h, k 1)1, which can each be bounded by 8/2 thus completing the proof.
Next we show that the oracle-level bag accuracy of h is high then this translates h is being a low error instance-level approximator for the target LTF f (or its complement in the case of balanced bags). With the setup used in the previous theorem, let us define define the regions S. == {x s.t f(x) = a} for E {0, 13. and Sas == {xs.t s.t f(x) = a, h(x) = b}. Let μ be the measure induced by D, Pa and Peb be the respectively conditional measures induced on S. and S.b. The oracle O for a random bag B, samples k points iid from (S1, p1) and (g k) points from (Sp, Mo).
we have the following theorem.
Theorem D.2. Suppose & E {I.....9). and < BagACCoraste//,, f, S < 1/(44), then & e if # 4/2, and
ii) Prp [xx) # h(x)
PrD (x) # h(x)
I E or Pr(f(x) + (1 h(x))) if 9/2.
where : = 4E'.
Before we prove the above them, we need the following lemma bounding the probability that two independent binomial random variables take the same value. Let Binomial p) be the sum of n iid (0, 1) random variables each with expectation p.
Lemma D.3. Let u, {I,....q). and X1 Binomial(u, P1) and X₂ Binomial( (,, p2) be independent binomial distributions for some probabilities and p2. Let p = minfmax (max(pi, , (1 vp".
pı) pı)}, max (22, (1 -P2)) }2)}}, then, Pr [ + X2)
Proof. We first begin by bounding binomial coefficient by the sum of its adjacent binomial coefficients. Let n 2 and n > r >>>> We begin with the standard identity and proceed further:
n
n-1
=
+
r
r
r-1
n
n
n F
+
(10)
+
1
r
-
1
r-
n
1
+
(1I)
r+
1
r
20

---

sampled from Moreover, it is trivially true that (0) < H and (") I (n"1), therefore (11) holds even for E n0 whenever the binomial coefficients exist. Now, for some probability p define v(p, n, == ("))²(1 (1-p) which is pdf at r of (1n, p). The above implies the following:
v(p n, S of (u(p,n,r 1) + v(p, n, 1))
(12)
where = we obtain that
Using the fact that 1.ppp..r-lp fettthaaa/.......--------aa
(1/p))(p,,,,)) + + v(p,n,r) - /0//+pp)> max {p. pp p}
(13)
The above allows us complete the proof of the lemma as follows.
Pr[X1 = X2]
min(u.))
Σ
u
1
Σ
r(pi, (ip....r?
Eu(perer)) 2,
<
max{v(p1, u, r)
Σ u(pl,
max(f(p2, u, Σ
v(2, 2,
r=0
p2)) (max pi }) (max (p2 1 -22
vp"
(14)
where we use Cauchy-Schwand for the first inequality.
Proof. (of Theorem D.2) We now consider three cases, for each one we shall prove points (i) and (ii) of the theorem.
Case (r)[ * [x)) 2 1 e. This condition means that ((S1o) + (((ni) 2 1 - E, which
implies that at least one of #1 (11)) (S( is 2 1 Assume that (So1) 2 E (the other case is analogous).
Consider unbalanced bags i.e., k # 9/2. Now in case that μu (S10) > 1 1-16 E, all the points sampled from S₁ are sampled from S10 w.p. (1 - ke) and those sampled from Sp are all sampled from Soi w.p. (1 [g- k))). Therefore, with probability least (1 (1-qe) all the points
S1o U So1. Since + q/2 this implies that does not satisfy the random bags with probability at least (1 qs) > e'. If ii (S10) S E, we can show with similar arguments that with probability h points are sampled from So which means (since & > 1) that h does satisfy the bag. Finally, let pi (S1o) (c, 1 8). In this case, the number of points sampled from S10 is distributed as Binomial (k, P1 (S10)) and those sampled from S01 is independently distributed as Binomial (k, (S(())) If these two numbers are different then h does not satisfy the bag. We can apply Lemma D.3 and using the bounds on Yu (S10), we get that p* S E. Therefore, the probability of not satisfying randomly sampled bag is at least
2 (1-43 qs) > e' no points are sampled from Si0 and
(1- (1-e))
1 1-V1-E2
2 2/2>6'.
(15)
1 1 v1
For balanced bags, the case Pro (x) # h(x))
implies that Pr(f(x) + (1 (i-h(x))] E, so
the condition (ii) of the theorem holds.
Case e < Pr (x)[ + M(x)] < 1 - This case violates the conditions (i) and (ii). First observe that,
fn (S1o) and f (S11)) both cannot be 2 (1 e) or S E, otherwise ((S11) + ((Soi) is either 2
or S. violating the assumption of this case. For the subcase that μu (S10) < and po (So1) 2 (1 (1-E).
21

---

we can show using arguments similar to the previous case that w.p. 2 (1 - qE) no points are sampled from S10 and q k points are sampled from Sm, and thus, h will not satisfy a random bag with
probability at least (1 qe) > e'. The subcase when μn (So1) I e and No(S1o) 2 (1 s) is analogous. Finally, we have the subcase that μu (S1o) or 1o (So1)) both lie in the range (e, 1). Now, the number of points sampled from S10 is distributed as Binomial (k; P4 (S1o)) and those sampled from Sor is independently distributed as Binomial (k, fo (S1)). If these two numbers are different then h does not satisfy the bag. We can apply Lemma D.3 and using the bounds one of µu (S10) or yo ), we get that p¹ I E. Therefore, the probability of not satisfying a randomly sampled bag is at least
VI E 2 e/2 > E', using (15).
D.1 Proof of Theorem 2.2
The proof follows directly from Theorems D.1 and D.2.
D.2 Proof of Lemma 2.3
Proof. We have,
Pr|pos(r " + c) # pos(F'X + c)] = Pr[pos( X + [Tr]l2{) * pos( ( X + [
Pr[poss a Tz + () * pos(á") Z + {)
(16)
where r = 11/2 a Tr/l and á - and Z r N I) and X +
(1, C (c+
Tr||2 and Ç {= (c+ + 1T /4) | By Lemma 2.1, ||a a|12 4
Ani
Auaa
e.
Now, the RHS of (16) can be bounded as,
TZaoossaaTttt Pr| Pr[pos(a a Tz + <) + pos(a" Tz + 2)] + Pr|pos(a Tz Tz 2) + pos Tz + 2)]
(17)
Now, g a N(,, 1). Thus, the first term in the above is bounded by the probability that g lies ||л|||/|| - fll2/ [rll2 I /||/4|12/ 1l///////mmmmm Ami-- This probability is at most
in range of length K< e|||a|1// Vall///2mma Amin.
For the second term, that is at most the probability that pos(a (a Z) * pos(á Now l| all2 S
4 Anaz Lå a x4
Ama Ama
Pr(pos(a Z) # pos( á 2)] S 2
Ames Auee
g. Hence,
Amax Amin
|
Pr|pos(r T + # pos((F xx c))sss Se 2
v 12 Amin
E
Subgaussian concentration with thresholded Gaussian random variables
Let ((.) be the standard Gaussian edf i.e., (t) == PIx-N1o,) [X 2 t). We also define +(t) := Pr Pr[X > t] = 1 -(t). We begin by defining the subgaussian norm of random variable.
Definition E.1. The subgaussian norm of a random variable X denoted by || and is defined as: |Xll> inf(t > 0 E /exp x < 2). Further, there is an absolute constant Ko such that [Xllez S KoK if X satisfies,
Pr||X| < 2exp (-t/K?),
for 2
(18)
Let X N(O, 1). easy to see that E [exp( (xpp)) (1/v2T) - exp(-x² xxp(=22/4)dr /2(1/V2m)
/2. Thus, X N is subgaussian with subgaussian norm < 2. In the analysis of this section, we shall use the following proposition from [32].
22

---

Proposition E.2 (Prop. 2.1.2 of (32]). Ler X ~ NO. 1). Then, for any t > 0,
(t
1
exp (-1/2) S (1) -
exp (-1²2).
13
2
In particular t 1,
(() v cxp (-P/2).
2m
Using the above, and by symmetry it is easy to see that for 2 Pr||X| > 1 S (v2/TT exp (- (-t2/2) s 2 exp (-t2/2). On the other hand, 2 exp (-t²/2) 2 1 for 0 st<l.
Thus,
Pr[[X] > 8 2 exp (-1/2), A4 0.
(19)
Consider the normal distribution conditioned on a threshold defined by letting Dy be the distribution of {X ~ (0, 1) X > z). We shall show that X ~ De is subgaussian random variable. Let us handle the (relatively) easy case of l first.
Lemma F.3. Let X- Di for some S O. Then, Pr [1x]] > exp (-12/2), for any t 0.
Proof. Let be the event that X 2 Conditioned on E, X distributed as |X| where X 1), and (19) implies that
Pr
X
E 2 exp (-f/2). A - 0.
On the other hand, conditioned E, X sampled as -12| where {2 (O) 1 S --=111 Thus,
Pr
|
E
Pr (0.1
| t / S [e]
(20)
Now, ift > |8] then Pr
X >
E
= 0. otherwise if < l the LHS of (20) is,
7 S [4] = Pr | <
Pr [2| > t Z~N(0,1)
[ = 1 Pr
Z t t
Pr / < E
5 Pr [
S = Pr >
which is bounded by 2 exp (-t3/2) and combining the probability bounds conditioned on E and E we complete the proof.
The case of l > 0 is proved below.
Lemma E.4. Let X ~ Dr for some E > O. Then, Pr [ > t
s 2- (-p(33/3?) for any t > 0,
where K₁ max { / 20, 10)
Proof. Let first explicitly define the pdf of X as:
(x) 5o
if Ar5c E otherwise,
(21)
(xxO))))/0(()
where fN(O,1) is the pdf of (0, 1). We prove this in two cases.
Case < 2. In this case, one can use the lower bound from Prop. E.2 to show that (()) 2 (2) > 1/50 by explicit calculation. Thus, fo, (I) 50 for 0. We can now obtain the desired bound as follows. Letting X ~ N (0, 1), for any t > 0,
Pr
x
t
Pr x
50 X
50Pr
t < 100exp (-f/2)
(22)
23

---

using (19). Now, it is easy to check that for 2 3,
exp
20
20 )
)
2
exp
9.
2 exp(4) > 50
exp
--
2
12
12
=
exp
100 exp
(23)
20
2
On the other hand, for 5t <3, 3, 2exp (-12/20) > Thus,
Pr
X
t 2 2 exp (-t²/20)
Case > In this case using the easily verifiable facts that hold for l 2:
(1/E-1/63 > 1/(2() and
exp (-362/2) S 20
Prop. E.2 yields
(1
12)
1
1
(()) 2
exp (-1212) 2 exp (- 2 exp (-2f))
(24)
(3
2n
2l
Observe that Pr x > Prz-N(o.1)
[2> t Z 2 f.. Ift < l, then this probability vanishes.
Otherwise l 2 f
> 2, and from Prop. E.2, Pr[Z > 1) < exp(-11/2) and therefore Pr x > 1 can
be bounded by
Pr|Z > 8]
< 2 -exp eep (-t/22 - 2exp 1-
(25)
Pr I 2
using (24). Now, if 562 + k for some & 2 0, then using l we have
t²
+ 26
L +
< -1
K
562 + K
(26)
2
5
562
5
10
Therefore, 2exp (-12/2 + 26²) < 2exp (-12 -(2/(1082) for 12 > 58t
On the other hand,
2exp (-+ /10()) > 2e- 1.
when t 50
Thus, in this case the following holds for all >
Pr
x > 1| < 2exp (-8/(108))
(27)
completing the proof.
The above results also apply "complements" of the thresholded Gaussians. In particular, let Dj be the distribution of (X ~ (0, X < + -X -t} which is equivalently (-X ~ NO, 1)
X -E to which the above analysis can be directly be applied. This yields, that if X Dr then for any / 0.
Pr
2 expexp (-1222),
if f 2 0,
(28)
Pr
X
exp
(-22/K)
if { < 0,
(29)
where K₁ max{ 20, 10lv10).
24

---

E.1 Bag mean and convariance estimation error bounds
In this section we shall be concerned with random variables X which are sampled from Dy with probability p and from Dr with probability (1 -p). Let denote this distribution by D(p, e). Using Lemmas E.3, E.4 and (28), (29), we obtain the following lemma.
Lemma E.5. Let X ~ D(p for some p E (0, 1). Then for any > 0,
Pr | > 1 S exp (-1²/K3)
(30)
where K1 = max{ 11). In particular, ||x|| = O(1e))
We however, shall also require similar bounds for the mean-zero version of such distributions. To begin with we state easy lemma bounding the mean of X.
Lemma E.6. Let X ~ D(p, !) for some p (0, 1). Then,
E
X
S Ye
(0, 20}, where
To > 0 is some constant.
Proof. Let consider the case of 8 (and S 0 follows analogously). When 2, easy to see that desired expectation is (1). Further, the expectation over Dd is O(t) for any since is a convex combination of the expectation of half gaussian which has ((1) expectation, and a gaussian truncated from below and above f, which has OEE) expectation. To complete the argument we need to bound the expectation over De. Using (21) and (1/v2T) Je exp(=2² /2) dr (ei/2eeepppp("" /2),, we obtain EX-D, [X] = expppppppppppemppepppppp (- (2) ( (()) and the lower bound from Prop. E.2 along with l yields an upper bound of 28 on the expectation.
With the setup as in Lemma E.5 define X ==
X -
E
X
Clearly, E
X
0. Further,
x
x
+
E
X
X
l
76-
Therefore,
Pr X
Pr 1 mo
22.exp -e)-/))2/K3
(31)
Let K₂ = max/2K1 v2 }. Now,
(t - 71)²
t2 2Th + |t| < 2 rel
4K? 2
K?
2 exp (-(1 -1t)2/K3 exp (-R/K3)
(32)
On the other hand, when 0 1 < 27c, 12 4/33 1/2, and thus
2 exp (-t² (K3) 2 2e 1/2 1.
Thus,
Pr { > 2 exp (-2//33)
(33)
for all t > 0, where O(E))
E.1.1 Concentration of mean estimate using Hoeffding's Bound
Let us first state the Hoeffding's concentration bound for subgaussian random variables.
Theorem E.7 (Theorem 2.6.2 of (32]). Let X1, XI,..., XN be independent, mean-zero, sub-gaussian
random variables. Then, for every E 2 0,
X
- cE2 N2
Pr
< 2 exp
(34)
N
ΣN
|| 113
where is some absolute constant.
25

---

For the rest of this section we shall fix é E R and E (0, 1). Consider vector valued random variable
X = (x.))...,, ((())) with independent coordinates where
X - where X Dpp E). From the previous subsection, we have |X
O(le)..
For i .,...,,....................... d, x ~ (N, 1) and therefore [xx 0/2 = O(1)
Using the above bounds on the subgaussian norms, and applying Theorem E.7 to bound the error in each coordinate by E/ /d and taking a union bound we obtain the following lemma.
Lemma E.8. Ler ...... XN be N iid samples of X. Then for every 2
Σ
N Ei=1 N
X; 2 < 2. exp
(= (d0(P))
Pr
+ 2(d - 1) exp (-cos N/d)
(35)
for some absolute constant co > 0. In particular, if > ((d/=2)0 log(d/6)),
Σ N X
Pr
==
2 3 2
for any >
E.1.2 Concentration of covariance estimate
Consider the vector random variable X defined in the previous subsection. It is mean-zero and so by Defn. 3 and Lemma 3.4.2 of [32].
supxes--1lle ||x 11 O()):
(36)
using the bounds on the subgaussian norms of the coordinates X given in the previous subsection. Using this we can directly apply Proposition 2.1 of [31] to obtain the following lemma.
Lemma E.9. Let X ..,...; XN N be N iid samples of X. then if N O ((d/==))(())og((00)))
Σ
X
Pr
E [X
28 sd.
(37)
N
for any 8 >
E.1.3 Mean and covariance estimate bounds for non-centered vector r.V.S
Distribution D assymvoo (p, E). We revisit the definition of X Sec. E. and instead define distribution
'D Dasyavoe (p, E) over = (7(1),
7(d) with independent coordinates by taking 2 = X where
X K~ ~D(p. E) and for 2, 2,...,,, d, Z
(0.
Clearly, X E [Z]. For convenience, we shall use the following notation:
pz = 1==1 Z₁
Σ N
#2 = E [Z]
and,
(38)
N
== E
(Z.
(z)) p
Σx : E((Z - (z (z))Z=
and,
Ez
(39)
N
where Z, is an iid sample of Z and X; Z, - pz, for i = ,,...,N N. We have the following lemma.
Lemma E. For any e, 5 E (0, 1), N > 0 ((d/s2) log(d/5)), then w.p. 1 1-5 5 the following hold simultaneously.
AĀ - pz 2 S E/2.
(40)
EΣz Ezl1 S
(41)
26

---

Proof. We begin by applying Lemmas E.8 and E.9 to X and the iid samples XI.... XN so that their conditions hold with e/2 and 6/2. Taking union bound we get that the following simultaneously hold with probability at least 1 à:
X;
5
(42)
N
X
E
XX
S
(43)
N
By the definitions above, (42) directly implies (40).
Now, observe that Σg = EXXX On the other hand, letting Ç = pzz - pz = (E X we
simplify Σz as.
M N (Z: iiz) =Uz)T
EN ()(X; - C)
N
EN X.X - -X,5--XXX - +CC
N
MN X
25C CC.
ΣN X
CCT
(44)
Thus, the LHS of (41) is at most,
ΣN
X.X!
Σ X,X!
E
XX - CC
-E XX
+ +1|c5T112
N
N
2
2
< e/2+
E² /
(45)
since we have shown that ||]||2 = | - uz 5
Finally, we prove version of the above lemma under a symmteric psd transformation. Let A be psd matrix s.t. Amax is the maximum eigenvalue of A AA i.e., V is the maximum eigenvalue of A. Then, if we define Ž == AZ and Z, as iid samples of Z, i = L,.... N and analogous to (38) and (39), define uzz. Pz. Σg and Σg. we have the following lemma which follows directly from Lemma E. 10 the Vmmax upper bound on the operator norm of A. Lemma E.11. For s, 5 E (0, 1), if N O ((d/s))0 log(d/6)) then w.p. 1- 5 the following hold simultaneously.
| - 12l12 < / / 2, | Σx ll2 S EXmax
(46)
(47)
E.2 Estimating Covariance of differences
First we begin this subsection with simple observation. If X and Y are two random variables such that,
Pr [ > ,), Pr [|Y] > 1) S 2 exp (-1/K3) A > 0,
(48)
then X Y is a random variable such that,
Pr[|X- - Y| > $ < [|X] L/2] + Pr ||| > 1/2] 4 (-
It is easy to see that,
4 exp (-t2 2 exp (-P/(4K)))),
when 1 > 8K7. On the other hand, when 1 < 8K?, 2 exp (-1 (-P//(4K)))) 1. Thus,
Pr| Y > f] < 2 exp (-f/(4)))))
(49)
In this subsection shall consider X ~ D(p, q, E) to be defined as follows, for some & E R, p. q E 10,1)
s.t. p + q X = U - V where:
27

---

with probability U ~ Dj and V Dr independently,
with probability U De and V Dj independently.
with probability (1 - p 22 U Dr and V De independently,
with probability (1 - p- 2, ~ Dj and V ~ Dr independently.
From the above it is clear that [[X] = 0. Further, from (49) and Lemmas E.3, E.4 and (28), (29),
Pr
[
S exp (-t/K3)
(50)
for > where K₁ max max (4v20, 4|e/ 10). In partieular, || 1l O(1).
Let us now define a distribution D Diiive (p. 9, E) vector valued random variable with independent coordinates "x.,"................ where
(1) (p, q, l), for some IR, p. q E [0, 1) s.t. p+44l
X() is the difference of two iid N(O, 1) random variables, for j = .,...,d, d. In particular, of these coordinates is O(1).
the subgaussian
From, the above it is clear that E = O, and by Defn. 3.4.1 and Lemma 3.4.2 of [32], (36) is applicable to X as defined above. Thus, letting X == AX, where A is as used in the previous subsection we have,
Lemma E.12. For X defined above, the statement of Lemma E.9 is applicable, and (37) implies that the following holds:
Σ
X
E
XXT
S Edmax
(51)
with probability 1-
E.3
Proof of Lemma 3.1
Our proof shall utilize the following normalization of LTFs Gaussian space.
Lemma E.13. Suppose f(X) pos (r"x + c), where |||| 0 and X N(u, Σ) s.t. E is positive definite. Let T == 11/ be symmetric p.d., and be any orthonormal transformation satisfying UTr/[[r[|2 ej where e is the vector with 1 in the first coordinate and in the rest. Then, letting Z ~ N(0. that X IU μ.
f(x) pos (r x + c)
pos (e Ze
(52)
where l (TT 4 + ////// Tr]l/
Proof. We have X X la where X ~ N(0, E). Thus, x PU = Z - using
U-1, Now, f(X) can be written
[ + 11) +
UT 1x + +
pos
= pos
Pr 12
|r|l
(UTr)
r ru
pos
|rr||
[r||
rT rJu +
pos
(53)
[r]]2
which completes the proof.
Proof. (of Lemma 3.1) Using the normalization in Lemma E.13, we can write X AZ + μ where A UT such that X N(p, Σ) Z NO, From the condition (52) we can write the samples in Step 2 of Alg. 1 as Az, + μ where sampled from D. Dasymooe (k/q. -E) (see Sec.
28

---

E.1.3) for as given in Lemma 1.1 Note that the maximum eigenvalue of A is Amax which is the maximum eigenvalue of Σ. Thus, one can apply Lemma E.11 to ja and EB.
Further, the difference vectors sampled in Step can be written as x; AZ, where E, are sampled
from Daifive p², -() (see Sec. E.2) where p (5) ((()) () is the probability of sampling a pair of
1-labeled feature-vectors from a bag, and p' = -"" k) (2) is that of sampling a pair of O-labeled
(2)
feature-vectors. Thus, one can apply Lemma 12 to Ep.
Using both the above applications with the error probability 6/2 and using union bound we complete the proof.
F Experimental Details and Results
F1 Implementation Details
The implementations of the algorithms in this paper (Algs. 2, 3, 4) and of the random LTF algorithm are in python using numpy libraries. The code for the SDP algorithms of [25, 26] for bag sizes 2 and 3 is adapted from the publicly available codebase', The experimental code was executed on a 16-core CPU and 128 GB RAM machine running linux in a standard python environment.
E2 Experimental Results
In the following d denotes the dimension of the feature-vectors, y the size of the bags, with k/g E (0, 1) the bag label proportion, and be the number of sampled bags in the training dataset. The instance-level test set is of size 1000 in all the experiments, and the reported metric is the accuracy over the test set.
Standard Gaussian without LTF offset. Here we primarily wish to evaluate the Algorithm 3 using
unbalanced bag oracles such that i * 9/2. For d E {10, 50). (q. k) E {33, 1). (10, 8), (50, 35)} and m E {100, 500, 2000} we create 25 datasets. In each LLP dataset, we (i) sample random unit vector r' and let fxx) == pos xx), (ii) sample m training bags from Ex(f.N((0 I), g. k), (iii) sample 1000 test instances (x, (xx)). x + N(O. I). We also evaluate the Algorithm 2 on these datasets. For comparison
have the random LTF algorithm (R) in which sample 100 random LTFs and return the one that performs best on the training set. The results are reported in Table 5. We also evaluate the SDP algorithm (S) in [26] for (q, = (3, 1) using m (50, 100, 200) (since the SDP algorithms do not scale to larger number of bags) whose results are reported in Table 6.
Table 2 reports concise set of comparative scores of Algorithms 2, and random LTF (R) using 2000 bags and of the SDP algorithms (S) with 200 bags.
Centered and general Gaussian. Here we evaluate Algorithms and 4, and we have both balanced as well as unbalanced bag oracles. In particular, for d E 50). (g, k) E {(2. 1), (3, 1), (10, 5), (10, 8), (50, 25), (50, 35)} and m E (100, 500, 2000) we create 25 datasets similar to the previous case, except that for each dataset we first sample μ and Σ and use (O, Σ) for sampling feature-vectors in the centered Gaussian case and use N(,, Σ) for sampling feature-vectors in the general Gaussian case. We perform the following set of experiments in each case. For the cases when bags are balanced, i.e. (q, E {(2, 1). (10, 5), (50, }5)}. for each our Algorithms 2 and 4 we evaluate their two possible solutions the test data and report the better number.
With LTF off'set. We sample (r...,) and create dataset using pos(r. x + c.) as the labeling function. Table 11 reports the test accuracy scores for Algorithm 4 and random LTF (R) with m = {100, 500, 2000) for centered and general Gaussians. Table 12 reports the corresponding scores for the SDP algorithm (S) [25, 26] with m = (50, 100, 200} and kq E {(2, 1), (3.1)): Table 4 provides concise comparative scores with m 2000 for Algorithm 4 and random LTF and m 200 for the SDP algorithm (S).
Without LTF offset. We sample an r. and create a dataset using (os x) as the labeling function. Table 7 reports the test accuracy scores for Algorithm 2 and random LTF (R)
______dd_ Hardness_ for Learnienn Thresholds_snte from Label_ Proportions (license included in the repository)
29

---

for centered and general Gaussians. Table 12 reports the scores for the SDP algorithm (S) [25, 26] on (q. E {(2 1), (3, 1)} with m (50, 100, 200). Table provides concise comparative scores with m 2000 for Algorithm 4 and random LTF and m 200 for the SDP algorithm (S).
Noisy Labels. We also experiment in a model with label noise. Here, the label of any instance can be independently flipped with some probability as a result the true bag label sum k has distribution over {0. ..... g). and we omit them. Tables 9 and 10 give the test accuracy scores for Algorithm and rand. LTF (R) with label flip probability Like the balanced case, here also we evaluate both the solutions of Algorithm on the test data and report the better number.
In this case the SDP algorithms
not applicable
{0.1, 0.25, 0.5) for centered and general Gaussians.
We observe that our algorithms perform significantly better in terms of accuracy than the comparative methods in all the bag distribution settings. Further, algorithms have much lower bounds their accuracy scores. For the standard gaussian case, Algorithm 2 outperforms Algorithm 3 for larger m. possibly since with larger number of bags Algorithm 2 (which has higher sample complexity) can perform to its full potential. Conversely, we can observe that with larger bag sizes and dimensions, Algorithm outperforms Algorithm for smaller m.
For the noisy cases, from Tables 9 and 10 we observe that while the test accuracy degrades with large noise, it is fairly robust to small amounts of noise. This robustness is intuitive and provide explanation for the same in Appendix H (Lemma H.2).
Table 2: Comparison of Algorithms A3, A2, rand. LTF (R) and SDP (S) on N I) feature-vectors.
g
A3
A2
R
10
3
95.52
98.17
76.0
68.04
10
10
98.58
97.68
75,46
10
50
35
99.06
97.95
74.18
50
3
89.26
95.15
59.86
57.55
50
96.73
94.36
61.58
50
50
35
97.82
94.94
61.04
Table 3: Comparision of Algorithm A2, rand. LTF (R) and SDP algorithms (S) without offset
k
A2
R
S
k
A2
R
S
10
98.12
78.26
88.40
10
98.18
78.32
90.10
10
98.27
77.16
67.31
10
97.92
75.14 14
70.80
10
10
5
97.9
78.66
10
10
5
97.86
70.41
10
10
8
97.87
77.64
10
10
8
97.4
69.86
10
50
25
97.87
76.67
10 50
25
97.57
70.48
10
97.9
77.17
10
97.6
62.86
50
95.64
61.25
57.83
50
94.99
58.68
61.12
50
95.21
61.15
58.69
50 3
95.6
59,8
62.39
50 10
5
95.59
55.06
50 10
5
95.27
57.43
50 10
94.34
63.17
50 10
94.44
61.82
50 50
95.16
55.76
50
94.97
53.98
50
50
35
94.74
61.02
50
50
35
94.33
56,97
((,, Σ) featurc-vectors.
(b) N(u, Σ) feature-vectors.
30

---

Table Comparision Algorithm A4, rand. LTF (R) and SDP algorithms (S) with offset
A4
k
A4
10
92.49
77.23
82.76
10
93.08
78.24
88.01
10
93.67
74.96
69.62
10
1
94.62
71.49
67.57
10
10
5
94.43
76.42
10 10
5
93.1
70.59
10
10
92.5
63.87
10 10
94.47
67.85
10
50
25
92.83
70.34
10
50
25
93.93
65.03
10 50
35
92.92
65.75
10
50
35
93.31
66.04
50
94.84
59.34
58.25
50
94.17
59.66
61.01
50
94.7
58.36
59.37
50
94.41
59.92
64.24
50 10
5
95.15
57.67
50 10
5
94.06
56.12
50 10
8
92.49
56.46
50 10
8
92.3
59.67
50
50
25
94.51
54.53
50
50
25
93.41
55.72
50 50
35
94.45
57.76
50
50
35
94.08
56.97
(a) (0, Σ) featurc-vectors.
(b) N(u, Σ) fcature-vcctors.
Table 5: Our algorithms Al and A2 vs. rand. LTF (R) on N I) feature-vectors.
d
A3
A2
R
10
100
82.37
90.2.0.07
73.46:068
10
500
91.2-003
96.34.oa1
73. 73.26-034
10
2000
95.522001
98. 17..0
76.020.1
10
10
100
94.282000
87.4820.59
74.73202
10
10
8
500
96.96.00
95.29
74.76.0.1
10
2000
98.58-00
97.68+0.
75.46-0.1
10
50
35
100
95. 95.79
89.99
73.34
50
500
98. 98,26-00
95.63+00R
72.83
10
50
35
2000
99.06-00
97.95
74. 74.18 18
100
67.75 20.11
61 2 10.63
55. o5.34
50
500
80.78
89. +0.4
56.72.0
2000
89.26
95. 1. 5+001
59.86-000
50
10
8
100
85.7 20002
60.420.53
56.26
10
500
24.0
86.84
60.37
50
10
8
2000
96. 2000
94.362001
61.58.00r
50
50
35
100
90.21=000
62.8.0.52
55.84
50
50
35
500
95.68=ao
89.09
59.69
50
50
35
2000
97.82=a0
94.94
61.04=0.1
Table 6: SDP Algorithm (S) on standard gaussian feature vectors
d
m
S
10
50
67.86
10
100
66.25=s.87
10
200
68.04
50
50
38.09-122
100
56.46218
50
200
57.55
31

---

Table Our algorithms A2 vs. rand. LTF (R) without offset
d
q
A2
R
d
q
k
A2
R
10
2
100)
91. 91.06=a07
77.32-0.2
10
2
100
91.25-0.1
74. .0.45
10
2
1
500
96.77200
76.22z0.36
10
2
1
500
96.26gom
26,8620.2
10
2
1
2000
12.12
78. 78.2620.12
10
2
1
2000
18.18
78.3220.23
10
3
100)
91.2-a.1
74.25
10
3
100
90.44-0.12
70.64-1.00
10
3
1
500
96.220.01
76, 12
10
3
500
96.04.0.4
73.32a1.1
10
3
1
2000
98. 98.27
77.162024
10
3
2000
97. 97.92.0011
75. 75.14
10
10
100
10129.a11
66.84-09
10
10
100
89.36-021
66.08.0.0
10
10
5
500
96.08 96.08
74.1
10
10
5
500
95. 95.48_0ozz
69,46 69.4622.99
10
10
5
2000
97. 20011
78.662011
10
10
5
2000
97. 97.86
1
10
100
89. 88.02
74.49.0.3
10
10
100
85.97
63.39....4
10
10
8
500)
95.57 -0.0
77. 19
10
10
8
500
94.02-a1
69.7 10
10
10
8
2000
97. 17.87 2000
77. 77.642019
10
10
8
2000
97. 42.40.001
69. 862..
50
100
90.48 00.48
62.52-c.64
10
50
100
87.92 97.92-0.2
60.6 60.65.0.6
10
50
25
500
95.89.a.2
-7.87
10
50
25
500
95.5
61.73 11.73.0.
10
50
25
2000
97. 97.87=a0
76.6720.1
10
50
25
2000
97. 27.57
70.48
50
100
89.69.a06
70.79
50
100
89.12-m 12-0.18
59. 59.08.0.5
10
50
35
500
95.87+000
76.09
10
50
35
500
95.2-o.m
60.67-0.62
10
50
35
2000
97. 20011
77.1720.15
10
50
35
2000
97. 62001001
62. 62.8620.75
50
2
100
69. 54.0
15.16-012
50
2
100
69. 69.08-a46
55.44-0.2
50
2
500
90.9 +0.0
57.9
50
2
500
89.46-a12
57.35.0.2.
50
2
1
2000
95. 64200
61.2520.1
50
2
2000
94.99
58.68
50
3
100
66.9 .9.8
54.6.0.12
50
3
100
66.42-1.9
57.24.0.4
50
3
500
90.63+002
59.2+6.17
50
3
500
89.96-021
57.22.0.28
50
3
1
2000
95. 2
61.1520.12
50
3
1
2000
95. 65.6s
59. 59.82h.4
50
10
100
61. 11.924036
53,492007
50
10
100
65. 65.76=1.07
54.71
50
10
5
500
20.29.a.3
55.28
50
10
5
500
90.2-0.14
56.57-022
50
10
5
2000
95. 25.592a0
55,06
50
10
5
2000
95.27
57. 57.4320.13
50
10
100
60. 662335
56.9220us
50
10
100
62. 02.48-07
62.27
50
10
8
500
87.01 80.3
61.72.0.9
50
10
8
500
88 28.00.0.29
61 ..00.49
50
10
8
2000
94.34
63.172009
50
10
8
2000
94.44_0m
61 11.22.0544
50
50
100
59. 59.33
54.31
50
50
25
100
65.0 65.07_aM1
54. 34.7820.14
50
50
25
500
89.2 89.24.003
54.53a015
50
50
25
500
87.72k0.8
55.22.0.22
50
50
25
2000
95. 62am
55.7
50
50
25
2000
94.97=am
53,982008
50
50
100
60. 20.6
56.61
50
50
100
66. 12-00
56.97
50
50
35
500
88 .0.6
57.73s0.s
50
50
35
500
87.86-0.7
59.57-0.
50
50
35
2000
94.7 o407
61.02.0.09
50
50
35
2000
94.33
56.97.0.3
(a) Centered Gaussian
(b) General Gaussian
Table 8: SDP Algorithm S without offset
m
9
m
9
10
50
2
71.8228.1
10
50
2
77.441671
10
100
2
82.53
10
100
2
84.31
10
200
2
88.39
10
200
90. 10.144444 2
10
50
3
68.
68.94
10
50
3
72.08
10
100
3
68.28
10
100
71.58 3
10
200
3
67.31
10
200
3
70.80
50
50
2
57.32
50
50
59.58 2
50
100
2
58. 2.922
50
100
2
59.95
50
200
2
57.83 +2.67
50
200
2
61.12
50
50
3
59, 1..322
50
50
3
63.90+7.61
50
100
3
57.864291
50
100
3
62,69 26.80
50
200
3
58.69
50
200
3
62.39
(a) Centered Gaussian
(b) General Gaussian
32

---

Table 9: Our algorithms A2 vs. rand. LTF (R) with label flip noise (mentioned bracket) for
Centered Gaussians
d
4
k
m
A2(0.1)
R(0.1)
A2(0.25)
R(0.25)
A2(0.5)
R(0.5)
10
2
100
81.96
72.17 =0..6
66. 66.92077
63.44sn.s
57.69203s
57.4
10
2
500
93.08
77.86-022
76.36a1.19
65.99
57 57.2a0.37
59.24
10
2000
78.21 =0.00
91.22.0..0
77.09.0.3
57. 47.64.041
60.73
10
3
100
79. .4.4..4
67.69+0.85
63.58
62.53-078
56. 3
59.83+0..
10
3
500
92. +0.0
74.82-a.k
74. 0-032
67.78-1.0
58.37-0.41
58.86+0.21
10
3
2000
96.532001
76.22
88.5 1
73.74206
58.68
59.620.55
10
10
100
75.87 20.98
59.41=0.55
62.8620.65
60.47
57.6920.3
56.3820.32
10
10
5
500
91. 01.9720.07
69. 19.36=1.07
74.6
63.14
57.720.28
61. 179.56
10
10
5
2000
95.78
74.52=067
87.93 ...33
67.22H0.5
58.00 58.042039
60.78
10
10
100
72. 72.66.0.6
71.26
61.1 1asss
67.88s0.1
56.77
60.96
10
10
500
89.6.n.1
75.16
65.65
73.61
57.720.32
59.26su.5
10
10
2000
94.98 14.98
76.48
78. 6
76.39.o22
57.78
57.48.0.3
10
50
25
100
76.86
60.43-0.54
63. -3.22
61.48+06
56.06-0.7
59.76H042
10
50
25
500
91. 0+.00
65.14-00
72.86+1.11
61.6+a.5
57.98-0.8
57.18
10
50
25
2000
96.36-o01
70.18
87.59+0.13
65.52+083
57.05
58.78+0.6
10
50
35
100
74.32.0.7
69.0220.1
60.0206
65.95
58.8 1228
58.4440.4
10
50
35
500
91. .2.3000
75.32.025
69, 16..869995
69.3320.7
58.762054
57. 97.9640.22
10
50
35
2000
95.39
75,46.0.13
84. 6..
75.25
56.95
59.6620.5
50
2
100
58. 14
55.05
54,43a0.12
54.15
54.57
54.7820.09
50
2
500
82.9 20.07
2007
57.46-0.7
59. 449.36
54.14sm.6
53.73
53.72+0.0
50
2
2000
91. 99
59, 29.862026
73.26s041
56.35
54.240.08
54.7
50
3
100
59.07
54.72-0.1
54. 66.6.11112
53.8+0.0
53.45+am8
55.07
50
3
500
79.5 60.2
56.96-a.7
57.44.0.15
54.99.m.
53.55
53.41
50
3
2000
90.66-A01
60.26-a.17
66. 64.04
56.88-01a
54.28-o.
54.69+0.14
50
10
5
100
56.3+0.29
54.32-a07
54.77+0.12
53.9+0.12
53.92-a.1
54.68+0.1
50
10
5
500
75.21 2062
54.482006
57.21a0.8
54. 14.012
53.682008
52.52001
50
10
5
2000
90.682002
55.722021
65.6510.56
56,062013
1
55.0610.1
50
10
100
55. 76.118
57.33.0.15
54. 54.34.0.08
56. 16.6210.1
53.72.005
54.93.0.1
50
10
500
65.5 55.57
60.97
55.0s021
58.98
54.7+0.11
53.824006
50
10
2000
87. 2004
62.39
60. 60.28
61.82
54.76za17
53.41
50
50
25
100
54.62096
54.16
55.45
55.12a0.2
53.1
53.9
50
50
25
500
77. +
53.81
56.34+0.6
54.44-0.09
53.4+0.05
53.8+0.9
50
50
25
2000
90.28+n0r
55.11-01
65.29+0.22
55.26+n.0
53.43=am8
54.43+a.16
50
50
35
100
55.33+o.1
55.45=0
54.51+0.14
54.08+0.07
52.94=a04
54.24+nas
50
50
35
500
72.95 72.95+
59.5+o.16
56. 8
57.85
13.71
54.28+0.12
50
50
35
2000
89.07 20.02
60. 20.16
62.8320.59
57.27
53.9940.1 14.5
33

---

Table 10: Our algorithms vs. rand. LTF (R) with label flip noise (mentioned bracket) for
General Gaussians
m
A2(0.1)
R(0.1)
A2(0.25)
R(0.25)
A2(0.5)
R(0.5)
10
100
86.682046
68.35=a96
65.8820.s
60.624m.66
59 59.48s0.48
58. 38.8220.37
10
2
1
500
93.34
77.692048
82.682079
67.52ass
60.55
61.5s0.71
2000
96. .0.02
75.5
90.02+0.24
76. 76.6.024
60.26 60.266o.53
60.05+061
10
3
100
80.05+0.3
64.76-107
64.66.08
62.96.0.98
62.46m06
60.63+044
500
91.83+o.12
70.26-142
74.9-1.18
65.09.p.96
59 99.86+0.9
58 40.
10
1
2000
96. 122003
73.05
88.2320.11
63.38
60.2220.51
60.0620.39
10
10
5
100
79.6921.
65.4820.7
63,53
63.2820.85
64. 10075
59.51
10
10
5
500
91.920.11
71.221.0
71.65
61.41a0.6
1a.85
61.5620.5
10
10
5
2000
96.2 2 1000
71.95sa71
86.2#0.2
63.04
60 60.43
59.52+04
10
10
8
100
72. 72.46
59. 59.4
64.7420.2
61.2240:7
59. 59.93
63.45
10
10
8
500
87.61
61.66=a79
64.32a0..
62.22
65. 65.0420.05
64. 1
10
10
8
2000
94.53
63. 63.79
77.46x1.7
61.28+0.58
61 75
64.82+087
10
50
25
100
80.2+0.55
60,49
62.72+0.3
59.3+062
58.45.0.4
59.32
10
50
25
500
91.96+0.2
61. 1..88
72.0-1.0
58.47+0.64
59.89.09
58.85
10
50
25
2000
96.38-0.04
63. 74-477
84.59+a.7
62.7 02.78+0.72
59.84-0.48
60. 17
10
50
35
100
69.83 69.83
60. 74.7420.4
62.45
59.0210.24
62.27
60.5 1
10
50
35
500
90.07
62,02z0.6
66,8521.8
61.8 111009
61.672093
62.3 20.6
10
50
35
2000
25.24
62.2s1.02
81.07
61.2410.5
61.13207
60.2910.9
50
2
1
100
61. 4..9
57.382025
57.9920.35
55.72ah.12
56.0an.22
54. 192000
50
500
82. 22.77
56.61
60.4420.7
56.820.4
56.3
54. 54.22#000
50
2
2000
91.5
57 27.45.011
74.3820.0
56.5240.16
58. 58.3520117
54.020.1
100
58.07+0.42 +0.42
16
59.48+0.35
59.29.0.35
57. 57.95+0.2
56.86+023
50
3
500
77.58+0.45
57.2+0.24
61.05+a.5
56.24+0.35
56.85
56.77
2000
89.25 29.25
55.3+0.18
71.13+0.6
56.78+0.1
56.98
55.62+0.22
50
10
5
100
59.26+0.5
54.08=a.
57.16+0.31
54.97-0.08
56.82+n36
55.3+0.16
10
5
500
75.83
55.05
59.4210.5
54.61
59 59.0420.72
54.5620.07
50
10
5
2000
88.0 28.63
54.7420.18
68.27
55.38
60.22a06
54.48.0.1
10
8
100
58.23 28.23
60. 60.7520.48
57.7 20.28
60.5210.53
55. $5.46,0.
59, 29.23
50
10
8
500
68.01
10.
58.77
61.39
58.76
60. 60.28
10
8
2000
a0.5
16.662042
62.99x1.22
61.562067
57. 27.54
59.1720044
50
50
25
100
59. 59.24
54.382008
59.944036
53.9240.08
57.92
54.8420.14
50
50
25
500
80.22-081
54. 54.26-a.1
57.32-04
53.97-6.12
55.14 14
55.18+02.
50
50
25
2000
90.32+0.12
54.03+a1
64.51
54.95+0.15
57.8+0.33
55.2+013
50
50
35
100
57.1+0.54
56.03=a31
58.14406
57.16+0.36
55.1 880224
56.69+0.7
50
50
35
500
72.81+0a3
58.09=044
59.59+043
56.23+ea1
57.36+0.2
58.39+h.32
50
50
35
2000
88.48
55,8620.9
61.99206
57.3210.22
57. 37.42.0.1
58.020.
34

---

Table 11: Our algorithms A4 vs. rand. LTF (R) with offset
q
k
A4
R
q
k
A4
R
10
2
1
100
89.41
73,83a052
10
2
1
100
88. 38.362024
74.2320.39
10
2
1
500
92.220.18
76. 2027
10
2
1
500
92.22.0.3
77.0420.3
10
2
1
2000
92,4920.26
77.23a0.17
10
2
1
2000
93.08
78.2410.24
10
3
1
100
19.13
71.78
10
3
1
100
88.47
68a16
10
3
1
500
92.55009
72.66an.42
10
3
1
500
93.09
72.18
10
3
1
2000
93.67
74.9620.1
10
3
1
2000
94.62
71.4920.3
10
10
5
100
89.43+0.0
64075
10
10
5
100
82.44.1.0
64.65+0.86
10
10
5
500
93.31
73. 14.44
10
10
5
500
90.75+041
68.96+0.7
10
10
5
2000
94.43+014
76.42+0.99
10
10
5
2000
93. 1
70.59+078
10
10
8
100
86.161031
64.020.8
10
10
8
100
84. 14.97
64.7 12.96
10
10
8
500
90.73a0.11
68.2920.58
10
10
8
500
92.7
1
10
10
8
2000
92.5.017
65.87
10
10
8
2000
94.47.0.26
67.85
10
50
25
100
88.6820.s
12.4
10
50
25
100
86.78 28.782
60.89
10
50
25
500
92.41
62.66
10
50
25
500
91. 21.64
63.56
10
50
25
2000
92. 92.83a0.15
70.34
10
50
25
2000
93.93
65.0321.14
10
50
35
100
87. 37.02013
62.82064
10
50
35
100
85.69
59.46s0.66
10
50
35
500
92. 92.26+0.14
65.4+0.7
500
91. 31.96Ha.
66. 66.64.1.00
10
50
35
2000
92.92+0.99
65.75+0.78
10
50
35
2000
93.31 11.333
66.04-0.
50
2
100
67.1+09
54.03+p.12
2
100
70.05
55.58+n.23
50
2
500
57.79s0.17
50
2
500
90.162001
58.8810.31
50
2
2000
94.8 14.00
59.34.0.19
50
2
I
2000
94.17 17.008
59.6620.2
50
3
I
100
19.98
55.4710.07
50
3
I
100
63.86.1.00
58. 192..77
50
3
1
500
89. 64.0.04
55.8610.18
50
3
500
86.73
58.32036
50
3
1
2000
94.7 22001
58.36s0.26
50
3
1
2000
94.4 1
59.92an.42
50
10
5
100
63. 1420.2
53.5820.08
50
10
5
100
64.76z1. 76.118
54.7620.15
50
10
5
500
89. 39.882002
54.24.0.1
50
10
5
500
86. 86.82051
55.020.14
50
10
5
2000
95.15+0.0
57.67+0022
50
10
5
2000
94.06
16.12-0.2
50
10
8
100
55.52+0.1
58.26+02
50
10
8
100
62.47+0.9
60.43+n.48
50
10
8
500
84.7 76
57.08+0.16
50
10
8
500
82.48+a7
60.34+h8
50
10
8
2000
92.4920.33
56.4610.23
50
10
8
2000
92.3
59. 39.6711.57
50
50
25
100
61.6 11.9610.3
55,441021
50
50
25
100
59.94.1.25
54.3410.17
50
50
25
500
88. 88.9620.02
55.7410.16
50
50
25
500
88.3
54.1
50
50
25
2000
94.51 20.01
54.5320.1
50
50
25
2000
93.41
55.72an.25
50
50
35
100
61.0620.28
56.42019
50
50
35
100
65. 25.29
50
50
35
500
88. 18.3320.00
56.7.0.14
50
50
35
500
84. 11116
56.9820.34
50
50
35
2000
94.45
57.7620.2
50
50
35
2000
94. 24.08
56.9710.4
(a) Centered Gaussian
(b) General Gaussian
Table 12: SDP Algorithm S with offset
m
g
S
g
S
10
50
2
73. 16.
10
50
2
75.96
10
100
2
79.09
10
100
2
80.76
10
200
2
82.76
10
200
2
88.01 1:5.0
10
50
3
67.80
10
50
69.844678 3
10
100
3
68.52+6.8
10
100
66.95 3
10
200
69.62 3
10
200
67.57 3
50
50
2
59.30
50
50
2
61.41
50
100
2
59.04
50
100
2
59,87 2..60
50
200
2
58.25 22.68
50
200
2
61.01
50
50
3
58. 17
50
50
3
63,88466.5
50
100
3
57.94
50
100
3
62.62
50
200
3
59.37 23144
50
200
3
64.24
(a) Centered Gaussian
(b) General Gaussian
35

---

G Class ratio estimation for LTFs
The work of [13] studies the problem of matching the classifier label proportion using a single sampled bag which they call class-ratio (CR) learning distinct from LLP. Indeed, in LLP the goal is to learn an accurate instance-level classifier from multiple sampled bags, whereas CR- learning does not guarantee instance-level performance. Further, similar to Prop. 18 of [13], CR learning LTFs over Gaussians is easy: for bag B {x())
Ji=1 of iid Gaussian points, random unit vector has distinct inner products {s; := r x"xx(") yem with probability 1. The LTFs {pos (r" x - >)
(-oo, , 8nn} achieve all possible target label proportions (i/n)z=o
and one can then apply the generalization error bound in Thm. of [13].
H Analysis of Mixture of Label Sums
Definition H.1 (Mixed Bag Oracle), Given set of bag oracles Ex(f, D. k) for h: E (o...... 9 and p (Pu..... ........ .o......PP)) E A where A is q-simplex, a mixed bag oracle Ex(f, D. q. p) samples bag size from Multinoulli(p) distribution" and then samples a bag from Ex(f, D.
Let Ep be the covariance matrix of difference of pair of vectors sampled u.a.r without replacement from Ex(J, DD q p) and E be the covariance matrix of vectors sampled u.a.r from Ex D, g, p). If DE is the covariance matrix of difference of pair of vectors sampled u.a.r without replacement from Ex 'D, q, k) and ERg be the covariance matrix of vectors sampled u.a.r from Ex(f, D, q, k) then have the following
Σg
Σ P
BK
ED
P Σ
Dk
(54)
Using the above, we prove the following geometric error bound which is analogous to Lemma 1.
Lemma H.2. For any ε E (0, if m 20 (d/=*) ((te")log(///))) (og(d/8)() ) (1/ (1/EX=1 pk 2) then computed in Step 3 of Alg. 2 satisfies min(lli r. || + r.l12] I 6, w.p. 1 - 6/2.
H.1 Proof of Lemma H.2
We define and bound the following useful quantities based on q. Amax. Amin and p.
2
Definition H.3. Define,
(i) (k)
=
12k
2
so that s ki(k) S 2/T,, (ii)
(2) = q
k 1
16
so
that
16
S
(2(
x whenever S k <
q 1, (ii) (p)))
MI 2izo MM that
Σ n k2(
16 1 pē
I ka(p), and (iv)
>i Ph
((p)
2Ama Ann
E p Et Man((A) so that
P.. (0, Et (1()) E A (M))
((p) S (1-2/m)) domn 22
3dm
p2)
EEr Lemma H.4. The ratio p(r) == r EDr/r" T Eg is maximized when tr.. Moreover,
Tr 7(1) = Vr Er / Dr.
p(r) 2+ +
where
and
k ph - (r) Ek5 Pi (1
9
9
r I = -
Σnd Pk - (()) Σ
p pk)1(()))
A=
9 pk
9 27(r)² Σ 1 (k) 7r()²
9
TTEr r Er
Σ (k))
k=0
k=
Section 2.3.2 (p. 35) of 'aachine Learning: A Probabilistic Perspective' (by K. Murphy)
36

---

Proof. The proof follows directly from Lemma 4.4 which gives us the expression for ΣBs and E and (54). Once the expression for p(r) is obtained, easy to see that since 1>(r) I 1, p(r) maximizes when ((r) = +1 and thus when r = +r..
Proof. (of Lemma H.2) By Lemma 3.1, taking m 2 O
ensures that | 222 S Amax and | 1|2 I E Aaxx w.p. at least 1 - where EB ΣB Σg and Ep Σn Σp. which is the equivalent of p using the estimated matrices.
We start by defining p(r) == r E'Epr r'Err
Observe that it can be written as p(r) = r'Enrtr' Ear
F'Eprtr Using these we can obtain the following bound P: for any r RR lp(r) p(r)1 s 0(p)s1le(r) w.p. at least 1 8 (*) as long as I EE Ex=o (b0) Amn which we shall ensure. This is obtained as follows.
Aun
Define a(r) == r E'Enr,be b(r) == (EBBr,((r) = En: f(r) == En. Thus, we get
that |e(r)] S &1>max, If(r)] S Em la(r)) 2 Amin (Ek-o PK Ei= PÊ (k)) and [6(r)] Z - Amin (2 max 2 Ci -
(F))(())).
Notice that p(r)/p(r) = (1
c(r)/a(r))/(1 + [(r)/((r)) Taking &1 x Ei Ph. Eizo (k)) (p(r) - p()) S c1d(p)p(r).
Anin
allows us to claim that
Amax
Now let i e g be a vector such that min F. || r. 2 E2. Hence, using the definitions from Lemma H.4, hr(r] < 1 - e while >(x)) = which implies p(r.) - p()) 2 K3 /2) Note (p)
For convenience we denote the normalized projection of any vector as E 7
that p(r) < p(r)) (()))))))))) Using this along with the bound (*) we obtain that w.p. at least 1 1- 5, ((r.) ) > (())
+ Ka (p). Choosing E I8(2+xa pJ) S.. we obtain that p(r,)(1 (1)()(()))))) >
when 62 > 0. Since our algorithm returns i as the maximizer of p. w.p. least 1 - 5 we get min ||
F. ||E + +..1122 S E2. Using Lemma 2.1, min ( || ll2. || | r. 1l2) 4v
Amn
E2. Substituting
Amn
||r oi--ra r- 1l2 S e w.p. at least 5. The conditions on e1 are satisfied by taking it be < 62 V
Aunn Aam
0 (min and thus we can take m 2 (dde)) log(d/6) (2umn
O(p))
2
Ks(P)
1 / (1/EE/ p satisfies this using bounds in Defn.
Taking m 2 O (d/e") log(d/8)
Ama Amin
H.3. This completes the proof.
We observe that the sample complexity bound is worse for {Pi...., } which are not concentrated ie., the probability of the label sum is supported over many different values. This occurs for e.g. in the noisy setting when the label flip noise is large (see Appendix F).
37


Reviews:
[{"review_id": "lpYd8hZWsr", "reviewer": "Reviewer_VQSz", "summary": "This paper studies PAC learning when the training data is aggregated into sets or bags of feature vectors. For each bag, we observe the feature vectors of these bags and only the average of the labels in the bag. They focus on the case when the feature vectors are distributed according to a Gaussian distribution, and the hypothesis class is the set of Linear Threshold Functions (LTFs). Their main results include polynomial time algorithms for learning the correct halfspace when the Gausssian is either standard or skewed and the correct LTF is either homogeneous or not. Finally, they compare their Algorithm experimentally with various procedures from prior work. ", "questions": "How tight are the sample complexities provided in Theorem 1.4 and 1.5 in terms of their dependence on the minimum and maximum eigenvalues of the covariance matrix and the size of the bag? In Theorem 1.5, we also see a term involving $l$, which depends on the parameters of the true LTF. Is such a dependence necessary?\n\n", "limitations": "No limitations. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper proposes a very interesting direction for learning under label aggregation, which bypasses the lower bounds that existed for this setting in prior work. I think it opens the way for more interesting problems to be considered in this setting, by possibly changing the assumptions on the distribution or the hypothesis class. All the claims are sufficiently explained and the presentation is generally clear. \n\nThe authors introduce some interesting technical novelties to extract information about the true vector of the LTF using the aggregated labels. In particular, the idea of comparing the variance of a random pair with and without replacement and finding that it is maximized in the direction of the true vector $\\mathbf{r^\\star}$ is very elegant and leads to some interesting algorithms, which can be implemented in polynomial time using PCA. Moreover, the techniques for handling non-centered and skewed Gaussians with unknown parameters are non-trivial and interesting. ", "weaknesses": "This is not a significant weakness, but the technical presentation in some parts of the paper seems quite dense and not necessarily adding to the understanding of this work. For example, in the proof of Theorem 1.4 or Lemma 4.2, too much emphasis is given in the calculation of the optimal setting of parameters and sample complexity. I would prefer a more intuitive explanation at times, although I'm not sure it that's possible. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q. *For example, in the proof of Theorem 1.4 or Lemma 4.2, too much emphasis is given in the calculation of the optimal setting of parameters and sample complexity. I would prefer a more intuitive explanation at times..*  \n*Authors*: We state our results formally in Section 1.3 and therefore include the parametric dependencies explicitly. However, to aid a more intuitive understanding, we will include an informal description of how the parameters in Theorems 1.4 and 1.5 are obtained and what they convey qualitatively in Section 1.4. Also, in the proofs of Lemmas 4.1 and 4.2 we shall add more explanations along the way for ease of understanding.\n\nQ. *How tight are the sample complexities provided in Theorem 1.4 and 1.5 in terms of their dependence on the minimum and maximum eigenvalues of the covariance matrix and the size of the bag?*  \n*Authors*: We have optimized the dependencies on the eigenvalues and the bag size in our application of the algorithmic techniques used in our results. However, sample complexity lower bounds for PAC-LLP learning LTFs – while a very relevant problem – is out of the scope of this work.\n\nQ. *In Theorem 1.5, we also see a term involving l, which depends on the parameters of the true LTF. Is such a dependence necessary?*  \n*Authors*: The term $l$ tells us the perpendicular distance from the center of the Gaussian to the unknown LTF's hyperplane, normalized by the stretch induced by $\\\\mathbf{\\\\Sigma}$ in the direction of $\\\\mathbf{r}^*$. This is required to estimate the density of the Gaussian distribution near the unknown LTF's hyperplane which directly affects the sample complexity – the less the density, the more the sample complexity. We will add this explanation in the relevant portion of Section 1.4.\n\n"}, {"review_id": "KFt5iJLVsO", "reviewer": "Reviewer_Xa3y", "summary": "This work studies the problem of learning linear threshold functions (LTFs, aka linear classifiers) under the setting of learning from label proportions (LLP), where the training data are \"bags\" (aka sets) of instances, and the training labels are classifier proportions of the instances in the bag. Under the assumption that the instances are gaussian distributed, bags are instances sampled iid, and the size of the bags are upper bounded, the authors show that it is possible to efficiently (properly) learning LTFs.", "questions": "Why is Definition 1.2 called the bag oracle? Isn't it just the distribution over the training data (of bags)?\n\nDoes the authors believe that the results are tight? In other words, is LLP under the considered data assumption essentially equivalent to mean/covariance estimation?\n\nIt will be good if there is a discussion regarding the sample-complexities in LLP versus ordinary classification.\nFrom this point of view, what is the \"cost\" of only having access to bagged data?", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The problem setting of PAC-LLP deserves more attention.\nThe authors gives good justification for why LLP matters, e.g., privacy and legal.\nIn light of the previous theory works on LLP that shows NP-hardness of PAC-LLP learning LTFs,\nthis current work is surprising, relvant, and interesting to the ML community.\nTheorem 1.4 gives an algorithm that highlights the interesting geometry and the clever exploitation of the subtle difference between sampling with and without replacement.", "weaknesses": "After Section 1.1, it will be useful for the reader if there is an overview of the paper. Something along the lines of\n\"Sec 1.3 are the main results. Sec 1.4 gives proof sketch of the main results and high level description of the algorithms. Section 3 state these algorithms precisely...\"\n\nFor Theorem 1.3, it will be useful to interpret the sample complexity. Is the sample complexity essentially the difficulty of estimating the mean of the bag vectors? If so, the authors should make this explicit.\n\nFor Theorem 1.4 and 1.5, are the lambdas eigenvalues of the covariance matrices? Please explicitly say so.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q. *After Section 1.1, it will be useful for the reader if there is an overview of the paper. Something along the lines of \"Sec 1.3 are the main results. Sec 1.4 gives proof sketch of the main results and high level description of the algorithms. Section 3 state these algorithms precisely...\"*  \n*Authors*: We accept this suggestion and will add a paragraph after Section 1.1 providing the organization of the paper.\n\nQ. *For Theorem 1.3, it will be useful to interpret the sample complexity. Is the sample complexity essentially the difficulty of estimating the mean of the bag vectors? If so, the authors should make this explicit.*  \n*Authors*: Yes, the sample complexity in Theorem 1.3 is essentially the same as that of mean estimation of the bag-vectors up to a desired error. We note however, that this distribution is not a Gaussian due to having unbalanced bags. We will add this to the overview in Section 1.4 and also to the proof of Theorem 1.3 in Appendix A.\n\nQ. *For Theorem 1.4 and 1.5, are the lambdas eigenvalues of the covariance matrices? Please explicitly say so.*  \n*Authors*: Yes, $\\\\lambda_{\\\\min}$ and $\\\\lambda_{\\\\max}$ denote the minimum and maximum eigenvalues of the covariance matrix $\\\\mathbf{\\\\Sigma}$ of the distribution from which the feature-vectors are sampled. We will state this before Theorems 1.4 and 1.5.\n\nQ. *Why is Definition 1.2 called the bag oracle? Isn't it just the distribution over the training data (of bags)?*  \n*Authors*: Typically in PAC learning literature, the underlying distribution is defined over the feature-vectors. Given an (unknown) classifier, the corresponding *example oracle* samples a feature-vector according to the distribution and outputs it along with the label assigned by the classifier. We extend this to the case of bags in which the bag oracle – additionally parameterized with a size $q$ and label sum $k$ – samples $k$ iid $1$-labeled feature-vectors and $(q-k)$ iid $0$-labeled feature-vectors and outputs a bag consisting of them.\n\nQ. *Does the authors believe that the results are tight? In other words, is LLP under the considered data assumption essentially equivalent to mean/covariance estimation?*  \n*Authors*: The sample complexity lower bound for PAC-LLP learning LTFs is a very relevant problem, however it is out of the scope of this work. While there is a blowup in the sample complexity incurred by the generalization and the stability bounds (Theorem 2.2. , Lemma 2.3), a major component is indeed the mean/covariance estimation (Algorithm 1). Nevertheless, one cannot rule out other algorithmic techniques for this problem which bypass such estimation.\n\nQ. *It will be good if there is a discussion regarding the sample-complexities in LLP versus ordinary classification. From this point of view, what is the \"cost\" of only having access to bagged data?*  \n*Authors*: For ordinary classification in $d$-dimensional space, the sample complexity is essentially $O(d\\\\log d)$ as one can solve a linear program to obtain an LTF and then use uniform convergence to bound the generalization error. While our algorithms have the same dependence on $d$, we shall add a discussion in Section 1.3 on the blowup incurred in the LLP setting due to the bag size, the condition number of the covariance matrix and the other geometric and error parameters."}, {"review_id": "HvkiEdYjYD", "reviewer": "Reviewer_FWVX", "summary": "This theoretical paper investigates the learnability of linear threshold functions (LTFs) in the learning from label proportions (LLP) setting. When the feature-vectors are distributed according to a Gaussian distribution and conditioned on their underlying labels, LTFs can be efficiently properly learnt. For the general Gaussian distribution, this paper develops a principal component algorithm which estimates the means and covariance matrices using subgaussian concentration bounds. Generalization bounds from bag classification error to instance classification error are also provided to resolve the ambiguity between the obtained solutions. The experimental results validate the effectiveness of the proposed techniques.", "questions": "Please refer to the Weaknesses for details.", "limitations": "This work does not seem to have any potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The learnability of LTFs in the LLP setting is an important issue, this work provides some novel and significant theoretical results.", "weaknesses": "$\\bullet$ From Theorem 1.3 to 1.5, as the distribution becomes more general, the sample complexity required to efficiently properly learn LTFs also increases, and the difference between these sample complexities seems to be obvious. Numerical results on the difference between these sample complexities and associated discussion and analysis are necessary to more intuitively elucidate these theoretical results.\n\n$\\bullet$ Intuitively, the theoretical results in this paper will depend on the label proportion $k/q$, but in the end, it is mainly implemented on the bag size $q$, i.e., the order of the sample complexity does not explicitly reflect the label proportion $k/q$. While this is not mathematically problematic, it would be helpful to add some remarks to illustrate this point.\n\n$\\bullet$ The readability of the paper needs to be improved. More introductions to the problem setting and related definitions of LLP, as well as further illustrations and explanations about the existing theoretical work will help readers better understand the theoretical results in this paper. In addition, some typos also harm the readability.\n\nTypos:\n\n$\\bullet$ Line 27: they're labels The goal -> their labels. The goal\n\n$\\bullet$ Line 132: independencei.e., -> independence, i.e.,\n\n$\\bullet$ Line 146: $r = q/2$ -> $k = q/2$\n\n$\\bullet$ Line 148: directionsWe -> directions. We\n\n$\\bullet$ Line 350: bag satisfaction -> bag classification\n\n$\\bullet$ Some typos in the Supplementary Material also need to be checked and corrected.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q. *From Theorem 1.3 to 1.5, as the distribution becomes more general, the sample complexity required to efficiently properly learn LTFs also increases, and the difference between these sample complexities seems to be obvious. Numerical results on the difference between these sample complexities and associated discussion and analysis are necessary to more intuitively elucidate these theoretical results.*  \n*Authors*: We do include experiments in Appendix F on the setting of Theorems 1.3, 1.4 and 1.5, focusing on the performance improvement against existing baselines of [Saket 21, 22] and random LTF. For example, from Tables 3 and 4 we observe that Algorithm 2 (without LTF offset) has better accuracy than Algorithm 4 (with offset) for the same sample complexity, which is consistent with our theoretical results. We will include in Section 5, a discussion of the performance and sample complexity for the various settings.\n\nQ. *Intuitively, the theoretical results in this paper will depend on the label proportion , but in the end, it is mainly implemented on the bag size, i.e., the order of the sample complexity does not explicitly reflect the label proportion. While this is not mathematically problematic, it would be helpful to add some remarks to illustrate this point.*  \n*Authors*: The sample complexity depends on both $q$ and $k$, however for ease of notation we have used the upper bound of $q$ for $k$ as well.\nAppendix A gives the proof of Theorem 1.3 where the sample complexity solely depends on $k/q$ (refer to the expression for $\\\\eta(k, q)$). The algorithm (Algorithm 3) samples a single feature-vector from each bag to compute a mean estimate. Thus, the probability of sampling it from the positive half should only depend on $k/q$ and the sample complexity therefore only depends on $k/q$.\nHowever, in Algorithm 2, we sample pairs of feature-vectors with and without replacement. When sampling without replacement, the probabilities of the label configurations of the two feature-vectors depend on the size of the bag $q$, and not only on $k/q$. In particular, the probability of sampling a pair of differently labeled feature-vectors without replacement is $2(k/q)(1-k/q)/(1-1/q)$. Keeping $k/q$ the same, this probability decreases with increasing bag size which increases the sample complexity for larger bags. We shall add this explanation in Section 1.4.\n\nQ. *The readability of the paper needs to be improved. More introductions to the problem setting and related definitions of LLP, as well as further illustrations and explanations about the existing theoretical work will help readers better understand the theoretical results in this paper. In addition, some typos also harm the readability.*  \n*Authors*: We will add more discussion in Section 1 to describe the LLP setting, and also further explain the existing body of theoretical work in LLP.  \n\nWe thank the Reviewer for pointing out the inadvertent typos and we will fix them along with any others in the paper as well as the supplementary material."}, {"review_id": "ivqvhKwDtO", "reviewer": "Reviewer_UNzS", "summary": "Learning from label proportions allow training data to aggregate into sets of feature vectors with sum or average of their labels for each set as a label. As supervised learning, the goal is to classify test set of instances and minimize error of the classifier. This work focuses on learnability of LLP over Gaussian distributions of linear threshold functions. Although PAC learnability of LTFs has been studies in the LLP setting, PAC-LLP is intractable to learn LTFs using LTFs. This work formalize the problem into Gaussian distribution, which makes LTFs PAC-learnable. The approach is directly to maximize the instance-level accuracy on the distribution.", "questions": "1. In Theorem 1.5, what is \\lambda? What are \\lambda_max and \\lambda_min? Please clarify notations like what you did on Line 126.\n2. What are relationships for r* and r head in Theorem 1.3, 1.4 and 1.5? I know you explained this on Line 145. Please put it ahead.", "limitations": "1. If possible, please don’t include citations in the abstract. \n2. On Line 59, I guess you typed one more “level”.\n3. Please make “Theorem” (Like on Line 247 or 257) and “Thms.” (Like on Line 128) consistent (Use either one).\n4. Need a space between “independence” and “i.e.,” on Line 132.\n5. Similarly, for Line 148, need a space between “directions” and “We”.\n6. You should read over your manuscript carefully and try to rephrase some sentences to make them more readable (I wont correct them here verbatim).\n- Some sentences have no subject.\n- Some sentences have no periods or spaces like limitations 4 and 5.\n- Some pronouns refer ambiguously.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "1. PAC-learnability of LTFs in the LLP setting (which is a very interesting topic) is well-defined as Definition 1.2 and well-addressed by Theorem 1.3, 1.4 and 1.5, especially considering the case for k = q/2.\n2. The proof of Theorem 1.4 is sound and solid coming with an algorithm and lemmas (even proofs for lemmas).\n3. As a theoretical work, it is nice to have a section for experimental results, although the datasets look relatively simple.", "weaknesses": "1. For Theorem 1.3 and Theorem 1.5, it is better to provide one or two sentences for each about proofs instead of putting everything in the appendix. You dont have to provide a separate section like Theorem 1.4. Just few sentences please.\n2. The writing looks less readable for some sentences. Please refer to limitations section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q. *For Theorem 1.3 and Theorem 1.5, it is better to provide one or two sentences for each about proofs instead of putting everything in the appendix. You dont have to provide a separate section like Theorem 1.4. Just few sentences please.*  \n*Authors*: While we have included in Section 1.4 an overview of our techniques for Theorems 1.3 and 1.5, we accept the suggestion and will also add a paragraph after Section 4 in the main paper with an informal description of the proofs of Theorems 1.3 and 1.5 along with references to the respective appendices with the formal proofs.\n\nQ. *In Theorem 1.5, what is \\lambda? What are \\lambda_max and \\lambda_min? Please clarify notations like what you did on Line 126.*  \n*Authors*: $\\\\lambda_{\\\\max}$ and $\\\\lambda_{\\\\min}$ are the maximum and minimum eigenvalues respectively of $\\\\mathbf{\\\\Sigma}$, and we will explicitly state this before the statements of Theorems 1.4 and 1.5.\n\nQ. *What are relationships for r\\* and r head in Theorem 1.3, 1.4 and 1.5? I know you explained this on Line 145. Please put it ahead.*  \n*Authors*: The value of $\\\\hat{\\\\mathbf{r}}$ output by our algorithms is a close estimate of $\\\\mathbf{r}^*$ (or possibly $-\\\\mathbf{r}^*$ in the case of balanced bags) obtained via the mean-estimation (Theorem 1.3) or the PCA based method (Theorems 1.4 and 1.5). We will add this in Section 1.3 as well.\n\nWe are grateful to the Reviewer for pointing out inadvertent typos and some editorial feedback. We shall of course correct all the typos as well as improve the phrasing of sentences wherever required."}]

Author rebuttal:
We thank the Reviewers for their encouraging and helpful feedback. We have addressed their questions and comments in the respective author rebuttals to the reviews.

Meta-review: The  PAC learning of linear threshold functions (LTFs) from label proportions was shown to be intractable on hard bag distributions. This paper proposed a very appealing direction for learning under label aggregation, which shows that there indeed exist polynomial time algorithms for learning the correct halfspace when the feature vectors are Gaussian. The initial concerns are well addressed in the rebuttal. The reviewers unanimously agree that this is a technically solid paper and recommend its acceptance.    Following the strong recommendation from the reviewers, I recommend its acceptance as a spotlight paper.
Decision: Accept (spotlight)