--- title: "On the Complexity of Learning from Label Proportions" authors: - "Benjamin Fish" - "Lev Reyzin" doi: "10.24963/ijcai.2017/232" url: "https://ijcai.org/proceedings/2017/232" pdf: "https://ijcai.org/proceedings/2017/0232.pdf" venue: "Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence" year: 2017 pages: "1675-1681" track: "Main track" keywords: - "Machine Learning: Learning Theory" - "Machine Learning: Semi-Supervised Learning" --- # On the Complexity of Learning from Label Proportions Benjamin Fish, Lev Reyzin *Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence*, pages 1675-1681. DOI: [10.24963/ijcai.2017/232](https://doi.org/10.24963/ijcai.2017/232) ## Abstract In the problem of learning with label proportions (also known as the problem of estimating class ratios), the training data is unlabeled, and only the proportions of examples receiving each label are given. The goal is to learn a hypothesis that predicts the proportions of labels on the distribution underlying the sample. This model of learning is useful in a wide variety of settings, including predicting the number of votes for candidates in political elections from polls. In this paper, we resolve foundational questions regarding the computational complexity of learning in this setting. We formalize a simple version of the setting, and we compare the computational complexity of learning in this model to classical PAC learning. Perhaps surprisingly, we show that what can be learned efficiently in this model is a strict subset of what may be leaned efficiently in PAC, under standard complexity assumptions. We give a characterization in terms of VC dimension, and we show that there are non-trivial problems in this model that can be efficiently learned. We also give an algorithm that demonstrates the feasibility of learning under well-behaved distributions. ## Full text ## 1 Introduction In this paper, we investigate the complexity of the learning problem of estimating the proportion of labels for a given set of instances. For example, this problem appears when predicting the proportion of votes for a given candidate [de Freitas and K¨uck, 2005]; correctly predicting how each individual votes is not required, only which candidate will win. Variants of this problem also appear in many other domains, including in consumer marketing [Chen et al., 2006], medicine and other health domains [Hern´andez-Gonz´alez et al., 2013; Wojtusiak et al., 2011], image processing [de Freitas and K¨uck, 2005], physical processes [Musicant et al., 2007], fraud detection [R¨uping, 2010], manufacturing [Stolpe and Morik, 2011], and voting networks [Fish et al., 2016]. In classical PAC learning, we are given labeled data instances from a distribution, and in the idealized case, must find a function that labels all of the data consistent with the observations. In less constrained settings, the goal is to find a function of low error, or at least of error as low as possible on the data presented to the algorithm. There is substantial literature on classical PAC learning outside the scope of this work; see e.g. [Shalev-Shwartz and Ben-David, 2014] for a survey. Once the classifier is found, it is easy to find the proportion of instances with a given label by invoking the classifier on the instances. Algorithms for estimating the proportion of labels with labeled data have been introduced before, for example by Iyer et al. [2014]. However, getting instances with attached labels, as assumed in classical PAC learning, is often difficult. Sometimes this is due to limits on the measurement process [Hern´andezGonz´alez et al., 2013; de Freitas and K¨uck, 2005; Musicant et al., 2007; Stolpe and Morik, 2011]. At other times, before datasets are released, labels are purposely detached from their instances in order to maintain privacy [Chen et al., 2006; R¨uping, 2010; Wojtusiak et al., 2011]. Instead, only the proportion of labels are given for a group of sample instances. For example, in estimating who will win an election, preelection polls only release the percentage of people planning to vote for a given candidate. Quadrianto et al. [2009] give several other examples where the only data available is of this form. The goal is then to learn a classifier from a hypothesis class that is able to correctly predict the proportions of labels from a hidden distribution using a training set which consists of a set of instances and the proportions of labels of that set of instances. This is the learning-theoretic problem we formalize and tackle in this paper. The proportion of labels may be inferred by first finding a classifier that predicts the labels for each instance [Patrini et al., 2014; Quadrianto et al., 2009; R¨uping, 2010; Yu et al., 2013]. Alternatively, Iyer et al. [2016] propose inferring the proportion of labels directly. A related setting is Multiple Instance Learning [Dietterich et al., 1997], where the goal is to classify bags of examples with unobserved labels, where the bag is labeled positively by a boolean 'or' function: if any example in the bag is labeled positively, the bag is as well. The goal in Multiple Instance Learning is to label new bags with whether any example in the bag is labeled positively. This is distinct from the problem we tackle in this paper because in our problem we know the proportion of labels instead. Yu et al. [2014] introduce a version of a model for learning from label proportions. In their model, each bag of examples comes with the proportions of each label in that bag, and each bag is drawn i.i.d. from a distribution over bags. They give some of the first sample complexity guarantees. Another other approach is where the examples are drawn i.i.d., but the bags may be an arbitrary partition of the examples, as in [R¨uping, 2010; Stolpe and Morik, 2011]. Compared to these 'bag' models, our model of learning from label proportions corresponds to the 'one-bag case' with binary labels, where each example is drawn i.i.d. from an arbitrary distribution. However, as we demonstrate, this model is already interesting to study. We formalize this as a PAC-like learning model, which allows us to compare the difficult of learning a hypothesis class in classical PAC learning to learning a hypothesis class in this model. In particular, we give the following results, including the first computational hardness results for learning label proportions. After formally defining the model in Section 2, we show in Section 3 that under standard complexity assumptions, classes of high VC dimension are not efficiently learnable from label proportions. We also give examples of classes with lower VC dimension that are not efficiently learnable from label proportions, using stronger complexity assumptions. Then, in Section 4 we show that the classes of functions that are learnable from label proportions are a strict subset of the classes that are PAC learnable. Finally, in Section 5 we give some positive results indicating cases where it is possible to PAC learn from label proportions. We also show that n-dimensional half-spaces over the boolean cube are learnable from label proportions under the uniform distribution. ## 2 Model and Sample Complexity For a distribution D over the domain of a function c, call c(D) the resulting distribution over the range of c. For c a function {0, 1}n → {0, 1}, we will call pc the percentage of positive labels in this distribution, i.e. c(D)(1). For a given sample, we call the percentage labeled positively as ˆ pc. Where clear, we will abbreviate these as p and ˆ p respectively. In this setting, each example x drawn from D has a hidden label c(x), but the learning algorithm does not get to see examples with labels. Instead, the algorithm only gets to see the set of unlabeled examples S and ˆ p, the percentage of S labeled positively by c. The goal is to find a function h in a hypothesis class H such that pc should be close to ph with high probability. Definition 1. A class of functions H is PAC learnable from label proportions if there is an efficient algorithm A such that for every target function c in H, any distribution D over {0, 1}n , and for any ϵ, δ > 0, given m ≥ poly(1/ϵ, 1/δ, n, size(c)) examples drawn i.i.d. from D and ˆ p, returns a hypothesis h in H such that We call this form of learning "PAC learning from label proportions." In general, we may consider agnostic or improper versions of this PACmodel. However, improper learning from the class of all functions here is very easy: We can efficiently learn with a sample complexity that only depends on ϵ and δ: Observation 1. The sample complexity for improper PAC learning from label proportions is O ( ln(1/δ) ϵ2 ). Proof outline. In improper learning, it is easy to find a function h∗ so that not only does ˆ ph∗ = ˆ p, but also ph∗ = ˆ p: e.g. h∗ may be a randomized function that on any input returns 1 with probability ˆ p and 0 otherwise. Then ph∗ = ˆ p and a Chernoff bound implies that ˆ p is close to p. For example, if the task is to predict the proportion of votes for a given candidate using only a single poll, improper learning in this model is easy simply by virtue of the fact that ˆ p is an unbiased estimator for p. However, the hypothesis h∗ described above will not be a realistic model of voting. So proper learning corresponds to finding a realistic model of voting, one which describes a relationship between examples and labels, that also predicts the proportion of votes correctly. For this reason, for the remainder of this paper, we will only consider proper PAC learning from label proportions. Definition 1 is a distribution-free setting, but when the distribution is known, sample complexity also may be independent of the VC-dimension. Observation 2. Let D be a known distribution. Let Then the sample complexity for PAC learning from label proportions the hypothesis class H is O ( ln(1/δ) β2 ). Proof outline. Here, we can use another Chernoff bound to get that with high probability, ˆ p is within β/2 of pc, for c the target hypothesis. But the definition of β implies that there is exactly one value pc∗ in {pc : c ∈ H} such that ˆ p is closer to pc∗ than any other value in {pc : c ∈ H}. Then with high probability pc = pc∗. Thus an algorithm may output any h such that ph = pc∗ . This analysis of the distribution-free setting only considers sample complexity and not computational complexity. In Section 5, we will give an example where we can efficiently PAC learn from label proportions under the uniform distribution. We may still wish to bound the sample complexity of PAC learning from label proportions in the setting where the distribution is arbitrary. The same bounds that hold in PAC learning under an arbitrary loss function [Shalev-Shwartz and BenDavid, 2014] (or the absolute value of an arbitrary loss function) also hold here. Namely, we can use the VC dimension of a hypothesis class H to bound generalization error. We denote this quantity by VC(H). In particular, we have: Theorem 3 (Occam's razor). For target function c ∈ H, with probability at least 1 - δ, for all h ∈ H, ## 3 Hardness of Learning fromLabel Proportions We start by showing it is NP-hard to learn when the VC dimension is sufficiently large. To do this, we start by defining the consistency problem of a hypothesis class. For a hypothesis class C, the consistency problem for PAC learning from label proportions is the following: Given a set X = {xi} of points, for each point xi an integer ai, and a proportion p, is there a hypothesis c ∈ C such that ∑i∈I ai ∑i ai = p, where I = {i : c(i) = 1}? If there is such a c, we will say that c is consistent with X. Proposition 4. Let C be a hypothesis class such that VC(C) ≥ nγ for some constant γ > 0. The consistency problem for C is NP-hard. Proof. We reduce from SUBSET SUM, which asks, without loss of generality, given a set S = {a1, . . . , am} of positive integers and a positive integer b, if there is a subset S′ ⊆ S such that ∑a∈S′ = b. Let n = m1/γ . Then VC(C) ≥ m, so C shatters some m points, call them x1, . . . , xm. We now construct the following instance of the consistency problem: Define X = {x1, . . . , xm}, each associated integer to be ai, and the percent p of positive labels to be b ∑i ai . We now show that X is consistent with a hypothesis c ∈ C if and only if the given subset sum instance has a solution. If X is consistent with a hypothesis c, then p = ∑i∈I ai ∑i ai . This immediately implies i.e. b = ∑i∈I ai. Then the subset {ai : i ∈ I} is the solution for the subset sum instance. In the other direction,let S′ ⊆ S be the set of integers such that ∑a∈S′ a = b. Since C shatters x1, . . . , xm, there is a hypothesis c that labels positively all and only the points xi for i such that ai ∈ S′ . That is, Thus X is consistent, witnessed by this hypothesis: We now show that PAC learning from label proportions is hard whenever the VC-dimension is a fractional power. We reduce from the consistency problem to the learning problem, which is a slightly more involved reduction than in the classical PAC setting. Theorem 5. Let C be a hypothesis class such that VC(C) ≥ nγ for some constant γ > 0. There is no efficient algorithm for PAC learning C from label proportions unless NP = RP. Proof. It suffices to reduce from the consistency problem, above. Indeed, using an oracle to an efficient PAC learner for C from label proportions, we merely need to solve the consistency problem with high probability. Given an instance of the consistency problem with input set X = {xi}, integers ai, and proportion p. Define a distribution D that outputs xi with probability proportional to ai. Set For δ > 0, we will query the oracle with inputs δ, ϵ, and an i.i.d. sample from D of size m = f(1/δ, 1/ϵ), where f is the polynomial sample bound for the oracle. Since the sample from D may not be exactly ai copies of xi, we do not know ˆ p to give to the oracle. So instead, we will invoke the oracle m + 1 times, setting the input proportion to be each of 0, 1/m, . . . , 1, and then check the resulting output hypothesis to see if it is consistent with X. If so, accept, and if no such hypothesis is ever found, reject 1 . Certainly, if we accept, there is a consistent hypothesis by definition: we accept if an oracle outputs a consistent hypothesis. Conversely, if the consistency problem is solvable, then we will accept: Let c be the consistent hypothesis. Since it is consistent, by the definition of D, pc = p. Now consider the invocation of the oracle with the true proportion ˆ p. This invocation will output some hypothesis h that will, except with probability at most δ, satisfy where S is the set of points h labels positively. Since each ai is an integer, this implies that p = ∑xi∈S′ ai ∑i ai , i.e. that h is consistent with X and therefore we will accept with probability at least 1- δ. Setting δ to go to 0 in the size of the input of the consistency problem completes the proof. A natural question to ask is if there are classes with VC dimension smaller than nγ that are still hard to learn. We now show that this is the case for parity functions on the first k bits of the input. Recall in (white-label) noisy PAC learning, each label in the training data is flipped with unknown rate η. We assume the algorithm is given as input some η′ , where η ≤ η′ < 1/2 and must only take time polynomial in 1 1-2η′ . Noisy PAC learning parity functions under the uniform distribution is presumed to be hard. Blum et al. [2003] give an 2O(n/log n) ) algorithm, which is the best-current bound. We now find a specific distribution where PAC learning from label proportions is hard in this sense for parities: Theorem 6. For a hypothesis c, Let Dc be the the distribution over {0, 1}n that places η 2n-1 weight on the examples labeled 0 and 1-η 2n-1 weight on examples labeled 1. PAC learning parities from label proportions under Dc is as least as hard as PAC learning unknown parity c with η white-label noise under the uniform distribution. 1 The oracle's behavior is undefined if the value input as the proportion of positive labels is not the true value ˆ p. We may assume, however, that the oracle rejects whenever this is the case because the time the oracle takes is polynomially-bounded so we can just wait for that amount of time to see if the oracle returns a hypothesis. Proof. We use an oracle for PAC learning parities from label proportions under Dc to noisy-PAC learn parities. We get as input η′ , parameters ϵ and δ, and some m examples xi, with m to be determined later, with noisy labels ˜ ℓi. When ˜ ℓi = 1, with probability η, the true label ℓi = 0 and otherwise ℓi = 1. We may assume that the unknown parity c is nontrivial. Then under the uniform distribution over {0, 1}n , for any such parity function, there are 2n-1 points labeled 1 and 2n-1 points labeled 0. For any point labeled 0, the probability that it was drawn from the uniform distribution is 1 2n-1 and the probability that its label was flipped to 1 was η. Then the probability that an example had ˜ ℓi = 1 but ℓi = 0 is η 2n-1 and similarly if ℓi = 1 the probability is 1-η 2n-1 . Note that this is exactly the distribution Dc. So if the oracle for PAC learning parities from label proportions is given just the examples where ˜ ℓi = 1, the oracle will receive i.i.d. samples from Dc. We will also give to the oracle ϵ′ = 1/2-η′ 2 and δ′ = δ/3. The expected proportion of these examples given to the oracle is 1 - η, but we do not know the true labels nor do we know η. So instead, we will invoke this oracle M+1 times, with the proportion given to the oracle as each of 0, 1/M, . . . , 1, where M = ∑i ˜ ℓi, i.e. the number of training examples with noisy label ˜ ℓi = 1 2 . If the oracle returns the correct parity c, then it should agree in expectation with the noisy labels ˜ ℓi on all but η of the examples. For an incorrect parity c′ , by the orthonormality of the parity functions, the expected disagreement is 1/2. For h the output of the oracle, if smaller than an η′+1/2 2 fraction of the noisy labels ˜ ℓi disagree with the corresponding label h(xi), then we return the hypothesis. Otherwise, we repeat with the next invocation of the oracle. Let f be the polynomial sample bound for the oracle for PAC learning from label proportions . First, we need to make sure that the oracle receives at least f(1/ϵ′ , 1/δ′ ) examples except with probability at most δ/3. In expectation, m/2 of the examples xi will have ˜ ℓi = 1. Using a Chernoff bound, P [∣∣∣∑i ˜ ℓi -m/2∣∣∣ >m/4] ≤ 2e-m/8 . So the oracle will receive at least 1 4 m examples (and no more than 34 m examples) except with probability no more than δ/3 so long as m > 8 log(6/δ). This then means that we require m > 4 · f(1/ϵ′ , 1/δ′ ) so that M ≥ f(1/ϵ′ , 1/δ′ ). Now we need to verify that when the proportion given to the oracle is the correct proportion ˆ pc, the oracle will return c except with probability at most δ/3. The oracle is guaranteed to return a parity h such that except with probability δ′ = δ/3, Using the definition of Dc, pc = 1 - η. If h ̸= c, then ph = 1/2 again by orthonormality. But then 2 As in the proof of Theorem 5, the oracle is undefined when the proportion of positive labels is not the true value ˆ p. And similar to before, we may assume that the oracle returns an arbitrary hypothesis. so it must be the case that h = c. Thus at least one of the invocations of the oracle will return the correct parity. So it remains to show that we will succeed at returning this parity. If the oracle returns an incorrect parity h, again using a Chernoff bound, when because M ≤ 3 4 m, where 1A is the indicator function that is 1 if A is true and 0 otherwise. This implies that for an incorrect hypothesis, whose expected fraction of disagreements with the noisy labels is 1/2, the empirical fraction is at least η′+1/2 2 , the threshold we had set. Similarly, for the correct hypothesis, where the expected fraction of disagreements is η < η′ , the empirical fraction of disagreements is no more than η′+1/2 2 except with probability at most 1 M+1 · δ3 . This means that all of the tests of the hypothesis succeeds except with probability at most δ/3. Then setting suffices so that, with the union bound, the total probability of failure is no more than δ, as required. Consider parity functions on the first k bits, which have VC dimension equal to k. There is no known algorithm for noisy PAC learning parity functions on the first k bits when k = ω(logn log logn). It is conjectured that there is no efficient algorithm for PAC-learning noisy parity that runs in time o(2√n ), which would imply hardness of noisy PAC learning parities on the first k bits for k = ω(log2 n). Calling this the 'parity hardness assumption,' Theorem 6 implies the following: Corollary 7. Under the parity hardness assumption, there is no efficient algorithm for PAC learning label proportions of parities on the first k bits for k = ω(log2 n). This means there are hypothesis classes with VC dimension ω(log2 n) that aren't PAC learnable from label proportions. However, under a stronger assumption than, say, NP̸=RP, we can find a hypothesis class hard to learn with even smaller VC dimension. Consider the hypothesis class where each hypothesis labels exactly k points positively, say for k ≤ n/2: We show that in order to find a consistent hypothesis, we will need to solve the k-SUM problem, which we may assume asks when given integers a1, . . . , am, is there a set S of size k whose sum is input b: Observation 8. The consistency problem for Hk is as least as hard as k-SUM. Proof. Using the notation above, given integers a1, . . . , am, let X = {1, . . . ,m}, let the associated integer to i be ai, and let p = b ∑i ai . If there is a set S of ai's whose sum is b, then X is consistent, witnessed by the hypothesis h that labels h(i) = 1 if and only if i is in S, and vice versa if there is a consistent hypothesis h for X, then the set S of size k where h(i) = 1 will sum to b. k-SUM has a well-known mk/2 algorithm. On the other hand, this is also a lower bound: Patrascu and Williams [2010] show that k-SUM requires mΩ(k) time assuming the exponential time hypothesis. Ailon and Chazelle [2005] also give a lower bound of mk/2 for linear decision trees. If k = logn, then Hk is hard to lean efficiently in either of these settings. This follows from the same proof as in Theorem 5. ## 4 Comparing Our Model to Classical PAC The definition of PAC learning from label proportions makes it harder to learn a class on one hand (by unlinking input from label) but easier on the other hand (by making the loss function easier to satisfy). So it may not be obvious what the relationship with PAC is. In this section, we show that the hypothesis classes that may be efficiently learned in PAC from label proportions is a subset of the classes that may be efficiently learned in PAC. Theorem 5 then implies it is a strict subset. Theorem 9. Suppose NP ̸= RP. Then if a hypothesis class H is efficiently learnable from label proportions, it is also efficiently (proper) PAC learnable. Proof. Let H be learnable from label proportions by some efficient oracle A, and f the polynomial sample size required by this oracle. We now give an efficient algorithm for PAC learning H. Given ϵ, δ > 0, draw m samples from the unknown distribution D, with m to be determined later. Call the set S of unique inputs x1, . . . , xm and their labels c(x1), . . . , c(xm) for hidden target function c. Let k be the number of positive labels ∑j c(x′j ). Define a new distribution D′ as the following: Let ϵ′ = 1/(2m2 ) and δ′ = δ. Draw m′ = f(1/ϵ′ , 1/δ′ ) samples x′j from D′ and label each as c(x′j ). We give to the oracle as input ϵ′ , δ′ , and the examples x′j , along with the proportion of positive labels ˆ p = km′ . Then with probability at least 1 - δ the oracle returns a hypothesis c∗ such that The smallest non-zero probability mass in D′ , however, is minimized when k = m. Thus pc∗ = pc. We now show that c∗ = c when restricted to the points x1, . . . , xm. Suppose there is a point xi such that c∗ (xi) ̸= c(xi) where c(xi) = 1. Then in order to have pc∗ = pc while c∗ (xi) = 0, at least m points labeled 0 by c must be labeled positively by c∗ , since D′ places (proportional to) m weight on positively labeled points and only unit weight on negative points. This is a contradiction, as there are only m total points. Similarly, if c(xi) = 0 and c∗ (xi) = 1, there must be m points labeled 0 by c∗ that are labeled 1 by c, but again there are only m distinct points. Thus c and c∗ must agree on all m points, i.e. c∗ has zero empirical error. All that remains is to check that the VC dimension of H is sufficiently small so that Occam's razor implies sufficiently small distributional error. But if VC(H) were, say, superexponential, (indeed, merely polynomial), then by Corollary 5, it wouldn't be learnable from label proportions, contrary to our assumption that it is. (This only prevents the VC dimension of H from being too large as a function of n. However, a similar proof to Corollary 5 implies that it is hard to learn H if VC(H) were exponential in, say, the maximum representation size of a hypothesis in H instead.) ## 5 Classes PAC Learnable fromLabel Proportions Call d the VC dimension of a given hypothesis class H. In Section 3, we showed that if d is a fractional power, H is hard to learn. We also gave examples with d as small as log n that are hard to learn, under stronger complexity assumptions. On the other hand, as long as labelings in a given hypothesis class are efficiently enumerable, then finite classes H are certainly PAC learnable from label proportions in time |H|. Or instead, by enumerating only distinct hypotheses on the sample, assuming that this is efficient, learning can be achieved in md time using Sauer's lemma. This immediately implies that all such classes with constant d are learnable from label proportions. We now show that not all classes with d = Ω(log n) are hard to learn. Consider the following variation of Hk which only allows hypotheses whose positive labels are close to each other: There are still exponentially many functions and VC(H′k ) = k. Hk was shown to be hard in Section 3. However, for H′k , this is not the case: Observation 10. PAC learning H′k from label proportions has an O(2km) time algorithm. Order the m examples in {1, . . . , 2n }, and for each length k subset, of which there are m - k + 1 of them, check all 2k possible labelings. Now when k = O(logn), this is a polynomial-time algorithm for learning H′k from label proportions even though the VC dimension is not constant. In the classical PAC setting, when it is hard to learn under an arbitrary distribution, it is often still valuable to show that learning can still be done in special cases, such as the uniform distribution. We now give an example, namely half-spaces, where it is hard to learn from label proportions under arbitrary distributions (Theorem 5) but easy to learn under the uniform distribution. In other words, when the distribution is wellbehaved, learning becomes much easier. The idea to find a half-space that classifies the given proportion ˆ p positively is to take a random half-space through the origin, and then move it in the direction of its normal vector, and stop when the half-space classifies the input p proportion of the sample positively. With high probability, this will be possible because no two points in the sample will be projected to the same point on the normal vector. Proposition 11. The class of half-spaces in n dimensions is learnable from label proportions under the uniform distribution over {0, 1}n . Proof. Since the VC-dimension of half-spaces is linear in n by Radon's theorem [Mohri et al., 2012], using Theorem 3 it certainly suffices to be able to efficiently find a half-space h such that ˆ ph = p with high probability. Consider a hyperplane P of dimension n-1 through the origin and v a normal vector defining P . First, we show that for a randomly chosen vector v, no two points in {0, 1}n project more than exponentially close to each other (in terms of n) on v. This allows us to use only a polynomial number of bits to represent each projected point. Consider an arbitrary pair of points x and y in {0, 1}n and consider the line ℓ that passes through these two points. If v and ℓ are perpendicular, then x and y will project onto the same point on v. More generally, we can find the maximum obtuse angle between v and ℓ such that the two points so that the points project exponentially close together on v. Any closer, and we will not have enough bits to distinguish between the projection of x and y. Namely, for a pair of points distance d apart, using the Taylor approximation for sin(x), the difference between π/2 and this maximum angle is no more than O ( 1 d2ω(nc) ) for constant c. Since the points come from {0, 1}n , d ≥ 1, and there are O(2n2 ) such pairs of points, so the total angle from which a uniformly-random vector v may not be chosen is at most O ( 2n2 2ω(nc) ) , an exponentially small probability. Thus, with high probability, no two points in {0, 1}n project to the same point on v, or project more than exponentially close to each other on v. Given m examples, setting m to be polynomial in n insures with high probability that all examples are distinct, and therefore no two examples project more than exponentially lose to each other on v. Since ˆ pc = i/m for some i ∈ {0, 1, . . . , m}, we need to find a plane parallel to P such that the corresponding linear threshold function classifies i of the sample points positively. For each pair of consecutive projected points cv and c′ v on v for real number c and c′ , consider the half-space given by the plane defined by the points p ∈ Rn satisfying v (p - ( c+c′ 2 ) v) = 0, so that these two points are classified differently by the half-space. Thus one of these half-spaces (or the half-spaces classifying all points positively or negatively) will have ˆ ph = i/m since no two points in the sample project onto the same point on v. While we have shown that it is strictly harder to PAC learn from label proportions than to PAC learn, introducing noise to the models changes the relationship between these two models. For example, PAC learning parities with unknown η white-label noise is hard under the uniform distribution, as discussed above, but PAC learning parities from label proportions with white-label noise is easy under the uniform distribution. In our model, that means each label is flipped i.i.d. with probability some unknown η, and the proportion of noisy positive labels ˆ pη is given as input instead, but otherwise the learning requirement remains stays the same. Observation 12. The class of parities is learnable from label proportions under the uniform distribution and unknown η white-label noise. Proof. Let pηc be the proportion of positive labels under η noise and parity c. Note pηc is always but for any non-trivial parity c, pc = 1/2, so pηc = 1/2. Then Observation 2 implies that we may distinguish efficiently the trivial parity from the non-trivial parities and in the case that pηc = 1/2 we may return any non-trivial parity. ## 6 Conclusion In this paper we formalized a model for learning a hypothesis class by only examples drawn from a distribution and the proportion of them receiving each label, with the goal of finding a hypothesis that matches these statistics on the underlying distribution, and we focused on the binary label setting. While this task may seem easier than PAC learning, we prove that it is actually no easier, and sometimes harder - namely, we show that everything that is efficiently learnable in our model is also efficiently properly PAC learnable. Moreover, we show that classes of polynomially large VCdimension are NP-hard to learn in our model, and we give some even stronger lower bounds for specific classes. We give examples where it is possible to efficiently PAC learn from label proportions, which may be surprising given that this is a low-information setting, including half-spaces under the uniform distribution. These results are for the binary setting and only for the 'one bag' version of the problem. We leave for future work the analysis of the case where there is more than one bag of examples and each bag's proportion of labels is given. For that case, and in other similar settings where the learner is given more information, we expect there to be more positive algorithmic results. ## References 1. [Ailon and Chazelle, 2005] Nir Ailon and Bernard Chazelle. Lower bounds for linear degeneracy testing. J. ACM, 52(2):157-171, 2005. 2. [Blum et al., 2003] Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM, 50(4):506-519, 2003. 3. [Chen et al., 2006] Bee-Chung Chen, Lei Chen, Raghu Ra- makrishnan, and David R. Musicant. Learning from ag- gregate views. In Proceedings of the 22nd International Conference on Data Engineering, ICDE 2006, 3-8 April 2006, Atlanta, GA, USA, page 3, 2006. 4. [de Freitas and Kück, 2005] Nando de Freitas and Hendrik Kück. Learning about individuals from group statistics. In Proceedings of the 21st Conference in Uncertainty in Artificial Intelligence, UAI '05, Edinburgh, Scotland, July 26-29, 2005, pages 332-339, 2005. 5. [Dietterich et al., 1997] Thomas G. Dietterich, Richard H. Lathrop, and Tomás Lozano-Pérez. Solving the multiple instance problem with axis-parallel rectangles. Artificial Intelligence, 89(1-2):31-71, 1997. 6. [Fish et al., 2016] Benjamin Fish, Yi Huang, and Lev Reyzin. Recovering social networks by observing votes. In Proceedings of the 2016 International Conference on Au- tonomous Agents & Multiagent Systems, Singapore, May 9-13, 2016, pages 376-384, 2016. 7. [Hernández-González et al., 2013] Jerónimo Hernández- González, Iñaki Inza, and José Antonio Lozano. Learning bayesian network classifiers from label proportions. Pattern Recognition, 46(12):3425-3440, 2013. 8. [Iyer et al., 2014] Arun Shankar Iyer, J. Saketha Nath, and Sunita Sarawagi. Maximum mean discrepancy for class ratio estimation: Convergence bounds and kernel selec- tion. In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014, pages 530-538, 2014. 9. [Iyer et al., 2016] Arun Shankar Iyer, J. Saketha Nath, and Sunita Sarawagi. Privacy-preserving class ratio estima- tion. In Proceedings of the 22nd ACM SIGKDD Interna- tional Conference on Knowledge Discovery and Data Min- ing, San Francisco, CA, USA, August 13-17, 2016, pages 925-934, 2016. 10. [Mohri et al., 2012] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. Adaptive computation and machine learning. MIT Press, 2012. 11. [Musicant et al., 2007] David R. Musicant, Janara M. Chris- tensen, and Jamie F. Olson. Supervised learning by train- ing on aggregate outputs. In Proceedings of the 7th IEEE International Conference on Data Mining (ICDM 2007), October 28-31, 2007, Omaha, Nebraska, USA, pages 252- 261, 2007. 12. [Pȃtras ¸cu and Williams, 2010] Mihai Pȃtras ¸cu and Ryan Williams. On the possibility of faster SAT algorithms. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1065-1075, 2010. 13. [Patrini et al., 2014] Giorgio Patrini, Richard Nock, Tiberio Caetano, and Paul Rivera. (almost) no label no cry. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 190-198, 2014. 14. [Quadrianto et al., 2009] Novi Quadrianto, Alexander J. Smola, Tibério S. Caetano, and Quoc V. Le. Estimating labels from label proportions. Journal of Machine Learn- ing Research, 10:2349-2374, 2009. 15. [Rüping, 2010] Stefan Rüping. SVM classifier estimation from group probabilities. In Proceedings of the 27th In- ternational Conference on Machine Learning (ICML-10), June 21-24, 2010, Haifa, Israel, pages 911-918, 2010. 16. [Shalev-Shwartz and Ben-David, 2014] Shai Shalev- Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014. 17. [Stolpe and Morik, 2011] Marco Stolpe and Katharina Morik. Learning from label proportions by optimizing cluster model selection. In Proceedings of the Joint Eu- ropean Conference on Machine Learning and Knowledge Discovery in Databases, ECML-PKDD 2011, Athens, Greece, September 5-9, 2011, pages 349-364, 2011. 18. [Wojtusiak et al., 2011] Janusz Wojtusiak, Katherine Irvin, Aybike Birerdinc, and Ancha V. Baranova. Using pub- lished medical results and non-homogenous data in rule learning. In 10th International Conference on Machine Learning and Applications and Workshops, ICMLA 2011, Honolulu, Hawaii, USA, December 18-21, 2011. Volume 2: Special Sessions and Workshop, pages 84-89, 2011. 19. [Yu et al., 2013] Felix X. Yu, Dong Liu, Sanjiv Kumar, Tony Jebara, and Shih-Fu Chang. ∝-SVM for learning with la- bel proportions. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, pages 504-512, 2013. 20. [Yu et al., 2014] Felix X. Yu, Krzysztof Choromanski, San- jiv Kumar, Tony Jebara, and Shih-Fu Chang. On learning from label proportions. arXiv preprint arXiv:1402.5902, 2014.