Learnability of Linear Thresholds from Label Proportions
Authors: Rishi Saket
Venue: NeurIPS 2021 Poster (2021)
Keywords: learning from label proportions
linear thresholds
algorithm
hardness

Abstract: We study the problem of properly learning linear threshold functions (LTFs) in the learning from label proportions (LLP) framework. In this, the learning is on a collection of bags of feature-vectors with only the proportion of labels available for each bag. 
First, we provide an algorithm that, given a collection of such bags each of size at most two whose label proportions are consistent with (i.e., the bags are satisfied by) an unknown LTF, efficiently produces an LTF that satisfies at least $(2/5)$-fraction of the bags. If all the bags are non-monochromatic (i.e., bags of size two with differently labeled feature-vectors) the algorithm satisfies at least $(1/2)$-fraction of them. For the special case of OR over the $d$-dimensional boolean vectors, we give an algorithm which computes an LTF achieving an additional $\Omega(1/d)$ in accuracy for the two cases.

Our main result provides evidence that these algorithmic bounds cannot be significantly improved, even for learning monotone ORs using LTFs. We prove that it is NP-hard, given a collection of non-monochromatic bags which are all satisfied by some monotone OR, to compute any function of constantly many LTFs that satisfies  $(1/2 + \varepsilon)$-fraction of the bags for any constant $\varepsilon > 0$. This bound is tight for the non-monochromatic bags case.

The above is in contrast to the usual supervised learning setup (i.e., unit-sized bags) in which LTFs are efficiently learnable to arbitrary accuracy using linear programming, and even a trivial algorithm (any LTF or its complement) achieves an accuracy of $1/2$. These techniques however, fail in the LLP setting. Indeed, we show that the LLP learning of LTFs (even for the special case of monotone ORs) using LTFs dramatically increases in complexity as soon as bags of size two are allowed.
Our work gives the first inapproximability for LLP learning LTFs, and a strong complexity separation between LLP  and traditional supervised learning.

Learnability of Linear Thresholds from Label Proportions
Rishi Saket
Google Research, India rishisaket google.com
Abstract
We study the problem of properly learning linear threshold functions (LTFs) in the learning from label proportions (LLP) framework. In this, the learning is on a collection of bags of feature-vectors with only the proportion of labels available for each bag.
First, we provide an algorithm that, given a collection of such bags each of size at most whose label proportions consistent with (i.e., the bags are satisfied by) an unknown LTF, efficiently produces an LTF that satisfies at least (2/5) 2/))-fraction of the bags. If all the bags are non-monochromatic (i.e., bags of size two with differently labeled feature-vectors) the algorithm satisfies at least (1/2)/(111/// 1/22)ffrattion of them. For the special case of OR over the d-dimensional boolean vectors, we give an algorithm which computes an LTF achieving an additional (2(1/d) in accuracy for the two cases.
Our main result provides evidence that these algorithmic bounds cannot be signifi- cantly improved, even for learning monotone ORs using LTFFs. We prove that it is NP-hard, given a collection of non- monochromatic bags which are all satisfied by some monotone OR, to compute any function of constantly many LTFs that satisfies (1/2 + e) e)-frtction of the bags for any constant for the non-monochromatic bags case.
This bound is tight
The above is in contrast the usual supervised learning setup (i.e., unit-sized bags) in which LTFs are efficiently learnable to arbitrary accuracy using linear programming, and even trivial algorithm (any LTF or its complement) achieves an accuracy of 1/2. These techniques however, fail in the LLP setting. Indeed, we show that the LLP learning of LTFs (even for the special case of monotone ORs) using LTFs dramatically increases in complexity as soon as bags of size two are allowed. Our work gives the first inapproximability for LLP learning LTFs, and a strong complexity separation between LLP and traditional supervised learning.
Introduction
linear threshold function (LTF) over the d-dimensional feature-vectors x is given by (x)(g(x)) for
some linear function g(r1,.... = Σd= === C + Cd+11 where pos(2) := 1 [2>0]] Also known as linear classifiers or halfspaces, LTFFs are one of the most fundamental classes studied computational learning and lie at the core of several machine learning algorithms such as Perceptron 25 21 and
SVM [7]. It is known 4 that LTFss are properly learnable the supervised learning setup: given training set of labeled feature-vecter vectors which are consistent with some LTF, using polynomial-time linear programming one can efficiently find one such LTF.
In this work we initiate an investigation into the proper learnability of LTFs in the framework of learning from label proportions (LLP). In this, instead labels for each feature-vector the training data consists of bags (subsets) of feature-vectors along with the proportion of labels in each bag.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Given a collection of bags with their respective label proportions which are consistent with (i.e, are satisfied by) some unknown feature-vector level classifier, the goal is to find a classifier (from the same concept class for proper learning) satisfying the most number of bags. Such a model was formalized by Yu et. al [30] who showed bounds on the generalization error for predicting the label proportion unseen bags.
When all bags are unit-sized this becomes the usual supervised learning in which as we noted above LTFs are efficiently properly learnable. A natural question is whether this remains true even when larger bag sizes are allowed. In particular, we consider the simplest setting with bags of size at most two and study the following question: Given collection of bags, all of size at most two and guaranteed to be satisfied by some unknown LTF, what is the maximum fraction of bags that can be satisfied using an efficiently computable LTF?
There naturally are two types of bags: monochromatic bags whose feature vectors have the same label, and the non-morochromutic ones whose feature-vectors have different labels and are necessarily of size two. Clearly, the monochromatic bags determine the labels of their constituent veeture-vectors. Therefore, for a collection of bags consistent with some LTF, one can efficiently find an LTF using linear programming to satisfy all the monochromatic bags. However, such an algorithm is not guaranteed to satisfy any non-monochromatic bag.
In traditional supervised learning of LTFs, the trivial algorithms of taking the best of any LTF or its complement, or a random homogeneous LTF, both achieve an accuracy of half. Unfortunately, these algorithms provide no such guarantees in the LLP setting, even for bags of size at most two. At high level, in LLP the objective is given by comparing the predicted labels of a bag's feature-vectors with each other, unlike supervised learning where they are only compared with observed ones. This seems to qualitatively change the nature of the problem in terms of the applicable techniques.
We first provide algorithm that satisfies (in expectation) at least half of the non monochromati bags and one-fourths of the monochromatic ones. This can be combined with the linear programming monochromatic ones)
algorithm which satisfies all monochromatic bags (and possibly none of the to obtain an algorithm which outputs an LTF satisfying (2/5)- 5/)afrcctioon of the bags. We also show that for the special case of the feature vectors being d-dimensional boolean and the bags being consistent with an OR (boolean disjunction) the algorithmic guarantees improve by an ((1/d) additional factor.
1.1 Previous Work on LLP
The LLP problem naturally arises in many real world scenarios where the labels are not available
individually but only as proportions for bags of feature- vectors due to privacy [28] and legal [26]
reasons, high label supervision cost 6 or technical limitations of labeling mechanisms 2 Some of
the earlier works [ 16 22 26 applied supervised learning methods such as MCMC, clustering, and
linear classifiers to the LLP problem. The work of (24) assumed an exponential generative model and proved performance bounds under assumptions
the distribution of the bags, and was further generalized by (23] while the work of [29] proposed novel proportional SVM based algorithms. Subsequently, approaches based on deep neural nets for large-scale and multi-class data [8] 10 19).
as well as bag pre-processing techniques (27 have been developed for LLP.
In contrast to the long line above of application focused research in LLP, the theoretical study of algorithmic and complexity issues in LLP has been rather limited. On the complexity side, [13] studied one-bug version of this problem where the observed global label proportion is given over all the feature-vectors and the goal is to find a classifier to minimize the deviation from this. They showed, among other results that common concept classes such as monotone-ORs cannot be learnt in their model to arbitrary accuracy.
The LLP model which we study - predicting the bag label proportions - was first formalized in the work of (30 who also bounded the generalization error when taking the (bag, poobollpppootion--Peee -pairs as instances sampled iid from some distribution. Their bound has the same dependence on the feature- vector classifier's VC-dimension as in supervised learning, with an additional logarithmic dependence on the bag size. While the loss function they consider is slightly different, their bound can be applied to minimizing the number of unsatisfied bags of size two (see Appendix of the supplemental). In the rest of this section we define the problem of learning LTFs from label proportions, describe our results and the previous related work along with an informal deseription of our methods and proof techniques.
2

---

1.2 Problem Definition
LetX = (x......, x,) Rd be the set of feature- vectors, and bags B {BI.... B.. S U?)
i.c each bag is of size most 2. The label set is binary i.c., {0, 1]. and for each bag By there is proportion 0% which is the average of the labels of the vectors in the bag, satisfying 9u E {0, 1 if [Bx] and 0% {0, 0.5, 1 if [&] = If o # 0.5 then By is said be monochromatic i.c.. bags which have same labels for their feature-vectors. The remaining bags BR necessarily of size 2 having 0g 0.5 are called non- momn-oooccrrmaiicc
bag B E B is satisfied by some f: + {0, 1) if (Exen, f(x)) / [Bx] = -k.
An instance of LLP-LTF is given (X, B (BE )==1; {=x) is said to be satisfiable if there exists an LTF that satisfies all the bags. The goal is to find an LTF that satisfies the most bags.
We denote by LLP-OR the special case when X has boolean vectors and the guaranteed LTF for satisfiable instances is an OR. A further special case is when the guaranteed OR is monotone i.e., it has no negated variables.
1.3 Our Results
We provide the following algorithmic guarantees for LLP-LTF on bags of size at most 2.
Theorem 1.1. There is a polynomial time algorithm which given a satisfiable instance of LLP-LTF on bags of size at most 2, computes an LTF that satisfies at least (2/5)-fraction of the bags. If all bags are non monoccooccooticc this satisfies at least half of the bags. For satisfiable LLP-OR on bags of size at most with d-dimensional boolean feature-vectorr there is a polynomial-tine algorithm computing LTF satisfying at least (2/5 + "T0/ /d/////////o -frfctionnn of the bugs in general, and (1/2 + yo/dd) ro/d)-fractiio if all bags are non non-monochromatic, for some absolute constant 7/0 >> O.
The above theorem for LLP-LTF is proved in Sec. 2 with the proof for LLP-OR provided in Sec.
2.1 The algorithms use random hyperplane rounding of vectors, so the above guarantees are in expectation. They can however be derandomized by the sophisticated procedure given in (00 and provide an explanation in Appendix A of the supplemental.
Our result on the intractability of LLP-OR (an thereby of LLP-LTF) is stated below.
Theorem 1.2. Given satisfiable instance of LLP-OR consisting only of non non-monochromatic bags each of size 2 s.t. there is a monotone OR that satisfies all bags, it is NP-hard to find any function of é LLFs that satisfies (1/2 + 8' 8)-fraction of the bags, for any constants & E 2
0.
The proof follows via a reduction from a variant of the Label Cover problem. We include the guarantees of the hardness reduction Theorem 3.3 which directly implies Theorem 1.2 However, due to lack of space we defer the formal proof of Theorem 3.3 to Appendices C and D of the
supplemental, while including informal description in Sec. [.5] We note that Theorem shows
the optimality of the approximation factor obtained in Theorem for non-monochromatee bags.
Previous Related Work. As mentioned carlier, the proper wewperriied--eaaaabiiie of LTFs is well known without any distributional assumptions. In the presence of adverserial label noise however, the
problem was shown to be NP-hard [17] and the works of [1 2 5 proved stronger inapproximability bounds with the optimal (1/2 + e)-factor hardness obtained independently by 11 and (15), further generalized by [ to apply for constant degree polynomial thresholds hypotheses. Subsequently,
[12] showed that this also holds for the special case of learning OR with an LTF which was recently strengthened by [14] to also rule out functions of constantly many LTFs as hypotheses.
1.4 Overview of Algorithmic Results
Algorithm for LLP-LTF. Given a satisfiable instance of LLP-LTF we can first assume by slightly translating the constant part of the unknown satisfying LTF that it classifies all the naaurre-vectors of the instance with non-zero margin. Next, we observe that there are strict quadratic constraints (over the coefficients of the LTF)) that distinguish the monochromatic from the non-monochromatic bags. Indeed, consider the unknown LTF pos( pos((c., x)) (WLOG by appending last coordinate with value 1 to vectoos x of the instance) that satisfies all bags. Then, (c., (c., x,) is positive for monochromatic bags and negative for the non- monochromatic ones whose constituent vectors are x,
3

---

and x,. Taking C = c.c. we obtain the same conditions for CX,, which are constraints linear in the entries of positive semi-definite (psd) C, and can be efficiently solved for C using semi-definite program (SDP). Using the psd decomposition C = L L we map to the vector 2; = Lx; so that (2,, 2,) x [x,, From here, the random hyperplane rounding of z; to (g. z:) (g < (0, ) yields an LTF pos(h(x;) = pos( (g. 2.)) that separates (in expectation) the vectors of at least half of the mon-hooochromatic bags and at most half of the monochromatic ones. Taking the better of px)) and pos( pos(-)(x)) satisfies in expectation at least half of the non-monochromatii bags and at least one-fourths of the monochromatic ones. Combining this with the known linear programming algorithm that satisfies all the monochromatic bags we obtain the desired (2/5)-an approximation.
Algorithm LLP-OR. Given satisfying OR we can write an equivalent LTF with a margin property the thresholded linear form has value either (-1/2) if the OR evaluates to 0, and otherwise takes values in the range [1/2, d]. This allows us to add margin terms in the SDP constraints corresponding to the bags. The rest of the algorithm mapping constraints imply an extra ((1/d) in the probabilities that the random hyperplane rounding separates the vectors of non-monochromatic bags and does not separate those of monochromatic bags, yielding a corresponding improvement in the fraction of satisfied bags.
to Z; remains the same, while the strengthened
1.5 Overview of Hardness Result
For this exposition of the proof techniques we focus only on a weaker version of Theorem 1.2 for
one LTF rather than functions of constantly many LTFs as hypothesis. The proof is obtained via a
reduction from a variant of the (by now standard) Label Cover problem. This consists of bi-regular
bipartite graph (V, U, F)) where vertices in V and have to be assigned labels from [M] and [m]
respectively for some M > m. Each edge = (v, u) E V x U is constraint with projection To.u : [M] + [m]] and is satisfied by the labels L, and Lu for u and u respectively if n., (4.) = lu- It
is NP-hard to distinguish whether Label Cover instance is completely satisfiable ("Yes" case), or
any labeling satisfies only an (f1a-frati of edges ("No" case).
The goal of the reduction is to transform a Label Cover instance & to an LLP-OR instance of only non-monochromatic 2-sized bags s.t. (i) if L is a Yes instance there is an OR satisfying all the bags, (ii) if L is No instance then there is no LTF satisfying more than (1/2 + o(1))-fraction of the bags.
The above template of reduction from Label Cover and its variants has been widely used to prove hardness results, including in computational learning by the previous works mentioned in this section. The main technical ingredient for such reductions is dictatorship test tailored transform specific local collection of variables/ccostraints of L into a sub-instance of the target problem. This is done by defining coordinate in the feature-space for each variable of and its label, and then constructing the feature-vectors and bags of the sub-instances in this space zeroing out coordinates corresponding to variables not in the local collection. Taking the union the sub-instances for all local collections yields the hard instance of the target problem, in our case LLP-OR.
Our dictatorship test needs satisfy the following meta- properrrp,,,ies, (i) completeness: any labeling satisfying the local collection of Label Cover constraints yields a good solution to the sub-instance i.e., an OR that satisfies all its bags, and (ii) soundness: any good enough solution to the sub-instances i.e., an LTF satisfying more than half the bags on average over the sub-instances, should be independently decodable into labeling satisfying the local constraints. This notion of decodability is crucial, depends on the fact (by design) that the good solution LTF will have coefficients on the disjoint sets of coordinates corresponding to each Label Cover variable. An independent decoding is any randomized procedure selecting label for each variable considering only the LTF coefficients of the coordinates corresponding to that variable. In the next few paragraphs we motivate the design of our dictatorship test and provide an overview of its completeness and soundness analyses.
1.5.1 Dictatorship test construction
We fix as our local collection any two vertices u w E V which are neighbors of some u E U in L with Ty.a and Tw.. being the respective projections. Making sure that completeness holds is usually straightforward. For the soundness we want to ensure that if the LLP-OR sub-instances have an LTF satisfying more (1/2 + f)-fraction of the bags (on an average over the local collections) then there should be independent decodings of e and w assigning labels I, and I,p s.t. (l,a(1,) = Tmra((w)) with significant probability depending on 8. We call such L, and Ly consistent labels. To begin, we
4

---

provide first cut approach and illustrate its shortcomings to provide the insights for developing the actual dictatorship test used in our reduction.
First Cut Approach. For v and w we have a separate set of [M] boolean coordinates denoted by M and { (Xm,,)i=1 Let us construct distribution that samples bags the boolean variables (Xu,a) (i=
with two feature-vectory x()) and x(2), the former supported only on { {x JM and the latter other only on
such that the OR formula (Xx,,, (. for any consistent labels ly and ty evaluates to 1 exactly on one of them. One way to do this is as follows. Sample a random set J by
choosing each j E [mm] w.p. 1/2 and let J == [m]] \ J Then, (i) for each j E J" set x( 1 for all i ()) and x_, 0 for all E (i) and (ii) for each j J set X x( 0 for all i (i) and x 1 for all i ( with the undefined coordinates in ( and ( set to O. This distribution call it 2 - then outputs a non-monochromatic bag B containing x and x It is easy verify that exactly one of (x()) V vx(l
(j):
x. and (xx2) V v = x w.ll)
wid
evaluate to for any consistent labels L, and l Therefore, this dictatorship test given by Do satisfies the completeness property. Unfortunately however, it does not have the soundness property. To see this, suppose that the pre-images of the two projections are all of the same size d i.e, [))
and -T 1 [i] = d for all j E [m]] implying M = md. Then, the linear threshold (X)( where I(X)= = Σ (Xu,, + x.. M/2, evaluates to exactly on one of ((1 and (2) w.p. 1 when m is odd and w.p. 1 - O(1/ mm) if is even. Thus, pos(h) which is a majoriityttreehhok is good solution. However, h has equal weight on each of its (X.,) i= and (Xw., 1 M coordinates, so any independent decoding of y and w using the corresponding coefficients of h will yield consistent labels with probability only around (1)M), much lower than desired.
Final Dictatorship Test. The problem with DO is that the total number of is in (1) and X together is exactly M and therefore the majority threshold works. If the coordinates were real-valued this could be mitigated by choosing the non-zero coordinates from some range of values randomly, introducing enough variability in the sum to fool the majority threshold. While this of course is not possible in the boolean case, we employ the following trick to achieve a similar effect: replace each original coordinate with some large number of new coordinates. When the original coordinate was set to zero set all the corresponding new ones to zero, and when the original was set to 1, sample the new ones from some distribution such that (i) at least one of the new coordinates is always 1, and (ii) the number of is sampled has a large variation. In particular, we replace X,, (i E [M] with (Xoiiti | b E (0. 1).4 E [Q]} for some large Q. The vector X(I) is constructed as follows. For all i s.t. To.u (i) E J independently, we first sample b = (1 - a) E {0, 1] u.a.r. then set exactly one u.a.r. chosen value from (x - to and rest to zero. Further, after choosing J", a random subset J C J is chosen by including every j E J with probability s. For those i s.t. (i,a(i) E J the variables (x 12 are sampled iid unbiased {0, 1] B-Berooulli. We can think of J be those blocks of coordinates which introduce the variability in the number of is due the fact that while given j E J is included in J with probability only E, once it is then roughly half of the coordinates in (1) corresponding to E (j) are sampled (as iid Bernoulli) to be 1, rather than ~ 1/Q fraction. For a choice E > letting Q to be sufficiently larger than 1/e yields the desired variation.
The coordinates Xw. (i E [M] are analogously replaced with {Xw,i.bq b E {0, 13, q E [Q]}, and a similar process using - C J is followed to sample the new variables for the point (2).
With the above transformations, D" is replaced by the distribution D which samples vectors (1) and (2) now over the extended coordinate sets corresponding to u and w respectively. Since we maintain the property that if the original coordinate X,,: was 1 then at least one of ( (Nu.s.0.r. X is set to 1, and when the former was then the latter are all 0 as well (similarly for Xw,)), we still have that (Voeço.1) v Xu...ba). v (Voeç0.1) / Xu..w.bb.)) for consistent labels 1, and bes satisfies all the bags sampled from D. On the other hand, the soundness analysis for D is quite lengthy and technical, and we provide below an informal description of the main steps involved and the techniques used for them, using some convenient simplified notation.
Consider linear form h on the above set of coordinates and candidate solution po)) to the dictatorship test. For simplicity let us assume that it does not have any constant term. If c, and Ca
5

---

are the coefficient vectors of h restricted to the coordinates corresponding to e and w separately, then (os(h(X()) = pos( (c., )) and pos(h(X = pos( (Cw. X )) For u let the weight of its label i be given by ||c,, = Lo.g o f,,i,b. with the total weight of c, being ||c, normalized to Using the notion of critical index with small parameter
we partition [M] into subsets reg,:
of regular coordinates which all have weight at most top, of the top-K (for some large enough K) non-regular coordinates in terms of their weight, and torso, of the rest of the coordinates. Let h², Mup hig and for be the linear forms on (1) given by the restrictions of cu to coordinates in [M], top,. reg,, and torso, respectively. Similarly we obtain for w the subsets top torso reg.. of coordinates and the restrictions h"" Papps Rieg and h
For the soundness analysis of D> we assume that does not admit a consistent independent decoding of e and w, and based on this wish to show that the distributions pos(h pos(h((X()) (X())) and pos(h(X((1)) are independent of each other. We do this through the following arguments.
Truncation:
hig (x))), her (X (2)) are too small to affect the value of (os(h(X(i) (1) and pos(h (os(h(((2) (x(2)
respectively, with any significant probability. This uses unti-concentration result of [14] applied to hop and hpp
NonnInntessectonn Te.u(topp)) O (t.u(topw.) 0. Further, the total weights of coordinates in reg, O ne (top)( and those in regw O uw,u ( (top.)) are tiny. If not, one could select label for o from either w.p. 1/2 choosing randomly from top,.. or w.p. 1/2/ sampling one from reg, with probability proportional to its weight, and do similar independent decoding for w, yielding a consistent labeling with significant probability, thereby contradicting our assumption above.
Decoupling the regular parts. We show that with high probability over the choice of J the distribution Mig (X(1) is close to fixed Gaussian random variable. This is via an application of the Berry-Esseen Esseen theorem after series of estimates on the conditional (on choice of Jd) mean and variance of heg ()). We obtain the same for J and Reg.
Using the truncation argument,
can ignore the contribution of h and hmm From the non-intersection and decoupling arguments obtain that pos( (X(1) + Mop (x()) and
phs (x) + hwp (x(")) are independent of each other. A short argument averaging over all pairs of neighbors v, w of a given shows that the fraction of bags satisfied (on average over
the choice of e and w) is at most 1/2 + o(1).
In several steps of the above arguments we are aided by the smoothness property of the the Label Cover variant (see Sec. 3 which allows us to assume that in any pre-image o, there is at most one coordinate either from top, or of weight greater than 1 1/poly(d), where is the pre-image size of the Label Cover projections. Overall, our analysis follows (at high level) the analytical approach of 12) and 14), though our decoupling step is more involved as it requires sharper as well as conditional bounds to obtain invariance as a high probability statement over the choice of J
Finally, extending our analysis rule out functions of constantly many LTFs considerably complicates the above arguments. In particular, we apply the dillii-dmmesional version of the Berry-Esseen theorem to do the decoupling step. For this, we add additional noise to the hrgg parts to lower bound the smallest eigenvalue of a correlation matrix which determines the error bounds when applying the multi-dimensional version of this theorem.
Approximation for LLP-LTF on bags of size
Let = (X, B (Bi.... B,,), fox {ox)m_) }m_)) be satisfiable instance of LLP-LTF. We begin with the following simple lemma which implies that the existence of an LTF satisfying all the bags of J while classifying each point of the instance with non-zero margin.
Lemma 2.1. There is an LTF pos(f(x)) that satisfies all the bags of along with [x(x) > foror all x E ,
Proof. By definition there is an LTF (x)(g(x)) that satisfies all the bags of J. Since pos(z) = 1 (2>:0) and the total number of feature vectors in the bags is finite, the quantity k given by
k min (9(x)) x E By px)(g(x)) 1}
(I)

---

Algorithm A. Input: satisfiable instance of LLP-LTF.
1. For each x E E2 define := (.1....:: :d. 1) E Rd+1
Solve the following SDP for psd matrix E IR [R(++I)((+1);
x C, Σ 0
V(x,, x,} = By s.t. |Bx] = 7 = 0.5
(2)
x CC,; 2 0
v(x, B₁ s.t. [B 2, + 0.5
(3)
x Cx; >
Vx; E U Bj-
(4)
Let C L be its psd decomposition.
4. Sample g u.a.r from (0, 1)a+1.
5. Define the linear form h(x) g)
6. Let h" E {h, hh such that pos (.)) satisfies more bags of J. Output pos(h" (.)).
Figure 1: Algorithm A for LLP-LTF.
satisfies > 0. Thus, we obtain the desired linear form f by decreasing the constant term of g by exactly k/2, ensuring that f(x) 2 x/2 if g(x) > 0, and f(x) I -k/2 if g(x) I 0, Vx E By.
We first provide in Fig. a SDP based algorithm A and prove the following lemma. Lemma 2.2. Algorithm A (Fig. D satisfies in expectation half of the non-monochhrmatic bags and one-fourth of the monochromatic bags.
satisfying all the bags of J. Letting x as defined in Step of A along with the non-zero margin of pos(s(x)) implies that there is some
Proof. Let pos(f(x)) be the LTF given by Lemma 2.1
C. E IRd+1 such that:
(c), X3) x (c.c.) & s
Vxx,,y) By s.t. [Ba] 0 σk 0.5
(5)
(c) xz) = xx (c.c.)
X2 2 0
v(x;,x)] = B& s.t. |Bxl = 0k + 0.5
(6)
(;, Xx) = xx] (c.c.) &; >
Vx; E Uf
(7)
Thus, C C. satisfies (2. ( and A and the SDP solved by A is feasible. Let C L
denote solution and its psd decomposition. For each i [m] consider the vector z; Rd+1 given by z, == LX, E gd+1, Observe that (z,, 2ÿ) (LX,, LX,) = x L LX, x! C& for i j E [n].
This, along with
2b. and (4) yields,
(Z,, Zz}
V(x, = Bx s.t. |B&| 2, 0.5
(8)
0
v(x,,,, = B& s.t. |B&l = 2, + 0.5
(9)
[z,]
Vx; E Uz
(10)
Let g be as in the algorithm and note that as defined in Step 4 A, M(x;) = (LX,, = (z, g) Thus,
(p(x))) )) -== is random hyperplane rounding of the vectors {2: Using this observation
along with (8. (9) and standard geometric facts (see Appendix A the supplemental) we obtain:
Pr (h(x)) + pos()(x;))) 2 1/2
v(x,,,) B& s.t. |B&l 2, 0x 0.5
(11)
Pr (x))) = pos()(x,)) 2 1/2
v(x,x,) = B& s.t. B& = 2, + 0.5
(12)
Pr (pos(((():))
pos))) =
v(x;) B₁
(13)
where the last equation for bags of size 1 is trivially true. Further, 100 implies that over the choice of g the values of all the h(x;) occurring in the above three equations are non-zero almost surely ie., with probability 1. This implies that pos(h(x)) = probability 1. Thus, it can be seen that both pos(h) and pos(-1) satisfy all the non-monochromatic bags B {x., } such that pos(h(x:)) + vos(h((x)): )) Furthermore, at least one of pos(h) (h) and pos(- satisfy half of the monochromatic bags B which have vectors x,, X; (x; x, if [ 1) for which pos ())x)) = pos()( This implies that pos(h") returned by A satisfies in expectation at least half of the non non-monochromatic bags and one-fourth of the monochromatie bags.
(xx() for all x E L Bj. with
D
7

---

Proof. (of Theorem 1.1 for LLP-LTF) We use A in combination with the linear programming method A that is guaranteed to satisfy all monochromatic bags. If the fraction of monochromatic bags is at least 2/5 of the total bags, then A finds an LTF to satisfy all of them. Otherwise, A finds one to satisfy (in expectation) g/4 + 1/2(1 - q) 1/2 q/4 2 1/2 22/20- 2/5 fraction of the bags. If 0 i.e., all bags are non-monochromatic the LTF satisfies 1/2-fraction of the bags.
2.1 Special Case: LLP-OR
Let 'J be satisfiable instance of LLP-OR. We have E 10, (i E [n)) and there is boolean OR function f of the form:
((x)
V Uz +
V
-s, X (0,
(14)
#ES{
#ES
for disjoint subsets S S/ C [d] such that / satisfies each bag of the instance J. Observe that for any {0, 1)d
((x)= Σ x,+ E11 21 f(x) = 0
Ex.t xx+ (1- =0 (15)
SE8
sES/
NES
#E8/
Let us define cf (c(...., of. ) E Rd++ as cf 1f Sy. else cf = = if 8 E S/ else
cf = s6l 1/2 if s = d 1, and cf = otherwise. Then, letting x = (I1,..., Fdd 1), 15 is
transformed to
[f(x) = + (c x) E - 1/2]]
[f(x) =0 + (c x) - 1/2]
(16)
Given the above it can be seen that
(x), x3)} S 4d ((c), xz) (
Xx,,x1} = Bx s.t. |& = 2, 0 = 0.5
(e', (c x,) N ((cl x
(c/ R)
Xx,x,} BB s.t. B& 2, σx + 0.5
4d
Thus, one modifies the algorithm in Fig. D to obtain A' by replacing and
with
-1
Cx,
x
C2:
x CX²)
v(x, x,} B₁ s.t. [Bg 2, = 0.5
(17)
4d
1
x! CX
2 4d
CX,
x CX,)
Vxx, = BB s.t. |Bgl = 2, 0z 0.5
(18)
Following the same analysis as in the LTF case, noting that ||z;|12 = x! CZ; for any E [m] (by
(10), and using the AM-GM inquality we obtain that:
(z;, 2j)
-1
|z,
1 + ||,
<
S
V(x,,,,} By s.t. |B = 2, = 0.5 (19)
|z,]
4d
|z
|
2d
(2,, kz)
1
||=.||2
+
||
1
Z
V(x;,x,) B& s.t. |B 2, o + 0.5
(20)
|2: |||2,|1
4d
|
|
2d
Therefore, from standard geometric facts (see Appendix A of the supplemental), the random hyper- plane rounding of the ) yields probabilities 1/2 + (11/d) instead of 1/2 in [I] and (12). Following the rest of the arguments as in the LLP-LTF case we obtain the following lemma.
Lemma 2.3. The algorithm A' described above satisfies at least (1/2 + on -raccionn of the non- monochromatic bags and (1/4 + oo so/2d) (222) fraction of the monochromatic bags in expectation, for some positive constant ag E (0, 1].
Proof. (of Theorem 1.1 for LLP-OR) The guarantee of the linear programming algorithm A satisfying all monochromatic bags case holds for LLP-OR well. Thus, if the fraction of monochromatic bags is greater than 2/5 + au/(8d) then A obtains an LTF that satisfies all the monochromatic bags. Otherwise, AA' from Lemma 2.3 finds one to satisfy (1/2- + on an/d)(1 (1-1))))))
(11x)) x) + z(1 4 ao/ /2) fraction of the bags which is at least (1/2- + ao/d) - (2/5 + on/ (Sd))))) 00/2d) > (2/5 + oa/ aa/(4d)
since og (0, 1] and 2 1. If x = 0 i.e., all bags are non-monochromatic the LTF satisfies (1/2 + an/ fraction of the bags.
8

---

2.2 Experimental Evaluation
We evaluate Algorithm A (Fig. D on synthetically generated satisfiable LLP-LTF instances over dimension d E (10, 40, 100) and number of bags E (50, 100, 200). For each (d, m) the algorithm solves 100 independently generated instances each by choosing a random satisfying linear form (with iid (O, 1) coefficients) and m bags independently, for each bag sampling two points iid from N NO,, 1)d with their label proportions given by pxs(f(x)). Note that the bags and their constituent points are not correlated with f.
For each instance the SDP in Gaussians g. With mi and my denoting the number of monochromatic and non-monochromatie bags respectively, the theoretical performance threshold is given by t= (mo/ + mn /2) (Lemma 2.2). We measure of (8/t) over the 100 instances per (d, m), both of which are quite a bit larger than 1, showing that the algorithm performs much better than than the theoretical guarantee on such instances. We also compute r as the number of bags satisfied by the best {pos (h'), p.spooss""") out of 100 random linear forms h', and the average value of (r/s). The latter is below in all cases indicating that our algorithm performs better on average than the random linear threshold with the gap being higher when d smaller. The results are presented in Table
is solved and the best h chosen using 100 independent
the number of bags satisfied by pos(h") and the average and minimum values
In the previous evaluation, for larger we observe only small gap between the performance of A and the random linear threshold. Our next experiment shows that this is not the with bags/points that are correlated to f- Here we choose f passing through origin and random monochromatic bags having two points the unit sphere which nearly diametrically opposite and random non nn--mooochromatiic bags having two points on the unit sphere very close to each other. We reduce the number of trials 5: taking the output of from best of 5 samples of pos(h") and the best {pos(h') (('),, pos( ( h')} out of 5 random linear forms h'. The results are in Table Unsurprisingly, due to this geometry of points, the performance of the random linear thresholds (avg r, avg (r/s)) much worse than before. On the other hand h* given by A performs better than before as the SDP is more discriminative and its solution C is highly correlated to f.
instances
Table I: Results on random 2-sized bags with iid points uncorrelated with satisfying linear form f. 100 instances per (d, m) row.
d
avg
avg
avg
avg
avg
min
avg
avg
10 50
27.20
22.80
18.20
39.24
2.162
1.714
33.09
0.847
10 100
52.98
47.02
36.76
85.26
2.325
1.949
64.12
0.754
10 200
105.83
94.17
73.54
181.95
2.479
2.217
125.04
0.688
50
25.94
24.06
18.52
29.12
1.574
1.405
28.83
0.993
40 100
50.59
49.41
37.35
54.59
1.462
1.316
53.26
0.978
40 200
101.43
98.57
74.64
104.96
1.406
1.265
100.70
0.961
100 50
24.97
25.03
18.76
28.74
1.533
1.317
28.28
0.987
100 100
50.06
49.94
37.48
52.08
1,390
1.266
51.49
0.990
100 200
100.04
99.96
74.99
97.24
1.297
1.216
96.58
0.994
Table Results random 2-sized bags with points highly correlated with satisfying linear form 100 instances per (d, m) row.
8
d w1
avg Trio
avg 77
avg
avg.
avg
min
7
avg V
avg
10 50
25.73
24.27
18.57
48.74
2.632
1.200
2.37
0.049
49.94
50.06
37.52
98.17
2.619
2.222
5.19
0.053
10 200
98.58
101.42
75.36
199.61
2.650
2.500
8.86
0.044
40 50
24.81
25.19
18.80
47.19
2.517
1.639
2.54
0.055
40 100
49.36
50.64
37.66
96.77
2.574
1.176
4.36
0.045
40
99.26
100.74
75.18
195.42
2,601
2.135
8.59
0.044
100 50
24.92
25.08
18.77
46.05
2,460
1.105
2.62
0.060
100 100
50.70
49.30
37.33
93.20
2.498
1.139
4.21
0.046
100 200
99.26
100.74
75.18
189.85
2.527
1.462
8.69
0.046

---

Smooth Label Cover and Statement of Hardness Reduction
The Smooth-Label-Cover problem is defined as follows.
Definition 3.1. A Smooth-Label-Cooer instance L((Vs, R.V,UUR U2. Eg S Ve x U2),M, M, m, [ (( consists of a bi-regular connected bipartite graph with vertex sets Vg, Ug. a directed edge set Eg, and a set of projections {Tv, [MM] + [ml] (ua))E) A labeling (0v,00 oU) dv Ve ++ [M] and du Uc + [m] is said to satisfy an edge (v,u) T ()) = ou (u).
The hardness of Smooth- Labelh--bbbll is given by the following theorem (see Appendix B.2 of the supplemental).
Theorem 3.2. There exists absolute constant Ko >> 0 such that for all integer parameters z and J, it is NP-Hard to distinguish whether an instance & of "mootth-Lbell-Coe with M = 7(J41}s and
m 227'=, satisfies,
YES: There exists a labeling a == (ov, oU) which satisfies all the edges.
NO: There is labeling which satisfies more than 2 === -fraction of the edges.
Additionally, & satisfies the following properties:
(Smoothness) For every vertex E V and for a randomly sampled edge (v, u) incident on Pruse (T Tu. [i)] for any fixed pair of distinct labels i [M].
For any edge (u, u), and any label j [m], b d. where d 4".
The hardness reduction from the above to LLP-OR is given below:
Theorem 3.3. For any constants > O and E Z+, there a polynomial time reduction from an instance & of Smoooth-Label-Cover given by Theorem 3.2 with and depending only on ō and E, to an instance I of LLP-OR with only mon-monochromate 2-sized bags such that:
(Completeness) If & is YES instance then there is monotone OR that satisfies all the bags of (Soundness) If & is a NO instance then there is no function of at most LTFs that satisfies more than 1/2 6 fraction of the bags of
Due to lack of space, the proof of the above theorem is omitted and appears in Appendices C and D of the supplemental.
4 Conclusions and Future Work
We present in this work the first study of the proper learnability of LTFs from label proportions. on bags of size at most two. Defining this formally as the LLP-LTF problem and the special case of learning OR using LTFs as LLP-OR (in Section 1.2 we give efficient algorithms compute an LTF satisfying (2/5)-fraction of the bags of a satisfible LLP-LTF instance, and (1/2)-fraction of them if all bags are non-monochromatic. For satisfiable LLP-OR over d-dimensional boolean vectors we improve these factors to (2/5 + (2(/d)) and (1/2 + ((1/d)) respectively. In our main (and most technically challenging) result we prove the NP-hardness of satisfying using any function of constantly many LTFs more than (1/2- + o(1)) fractioon of bags of instance of LLP-OR with only non-monee non-monochromatic 2-sized bags all guaranteed be satisfiable by some monotone-OR, thus establishing the optimality of our algorithms for the non-monochhrmatie bags case.
While the above we feel, is notable progress in understanding the complexity LLP-LTF, there are many interesting related directions for future work. First is resolving the gap between the (2/5)-factor algorithm and the (1/2 o(1)) hardness. Obtaining efficient proper learning algorithms for larger bag sizes is natural followup problem. Whether using more complicated hypotheses - like solymomial-threshhe
functions (PTFs) allows us obtain better bounds for LLP learning LTFs is another important question. Proving NP- NP-hardness results ruling PTFs out good classifiers seems challenging and is open even for agnostically learning noisy ORs in supervised-leamning All these questions can also be studied for other classes such as DNF-formulas. We hope that our work along with this rich landscape of open questions generates further interest in the study of learnability of common concept classes from label proportions.
10

---

References
[1] E. Amaldi and V. Kann. On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems. Theor. Comput. Sci., 209(12))3372)2 1998.
[2] S. Ben-David, N. Eiron, and P. M. Long- On the difficulty of approximately maximizing agreements. J. Comput. Syst. Sci., 66(3):496-514, 2003.
[3] A. Bhattacharyya, S. Ghoshal, and R. Saket. Hardness of learning noisy halfspaces using polynomial thresholds. Proc. COLT, volume 75, pages 876-917. PMLR, 2018. URL
http://proceeddingg mlr. press/v75/ /atess/////baatacharyaaa bhattacharyya18.5 html
[4] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the vapnik- chervonenkis dimension, J. ACM, 36(4):929-963 1989.
[5] N. H. Bshouty and L. Burroughs. Maximizing agreements and coagnostic learning. Theor. Comput. Sci., 350(1):24-39, 2006.
[6] L. Chen, Z. Huang, and Ramakrishnan. Cost-based labeling of groups of mass spectra. In Proc. ACM SIGMOD International Conference on Management of Data, pages 167-178, 2004.
[7] C. Cortes and V. Vapnik. Support-vector networks. Mach. Learn., 20(3):273-299 1995.
[8] N. de Freitas and H. Küick. Learning about individuals from group statisties. In Proc. UAI,
pages 332-339, 2005.
[9] 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.
[10] 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 http://arxiv....//////// /as///as///// 1905 abb5/90
12909
[11] V. Feldman, P. Gopalan, S. Khot, and A. K. Ponnuswami. On agnostic learning of parities, monomials, and halfspaces. SIAM J. Comput., 39(2)x606-645, 2009.
[12] V. Feldman, Guruswami, P. Raghavendra, and Wu. Agnostic learning of monomials by halfspaces is hard. In Proc. FOCS, pages 385-394, 2009.
[13] B. Fish and L. Reyzin. On the complexity of learning from label proportions. In Proc. IJCAI, pages 1675-16811 1681, 2017.
[14] S. Ghoshal and R. Saket. Hardness of learning DNFs using halfspaces. In Proc. STOC, pages 467-480 2021.
[15] V. Guruswami and P. Raghavendra. Hardness of learning halfspaces with noise, Proc. FOCS, pages 543-552, 2006.
[16] Hernández-GGonzález, I. Inza, and J. A. Lozano. Learning bayesian network classifiers from label proportions. Pattern Recognit., (66(12):34553444 2013.
[17] D. S. Johnson and F. P. Preparata. The densest hemisphere problem. Theor. Comput. Sci., 6: 93-107, 1978.
[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. NewrlPS, pages 7167-7177, 2019.
[20] S. Mahajan and R. Hariharan. Derandomizing semidefinite programming based approximation algorithms. In Proc. FOCS, pages 162-169, 1995.
[21] M. Minsky and S. Papert. Perceptrons: an introduction to computational geometry. MIT Press, Cambridge, MA. 1969.

---

[22] D. R. Musicant, J. M. Christensen, and J. F. Olson. Supervised learning by training on aggregate outputs. In Proc. ICDM, pages 252-26: 261. IEEE Computer Society, 2007.
[23] G. Patrini, R. Nock, S. Caetano, and P. Rivera. (almost) no label no cry. Proc. Advances in Neural Information Processing Systems, pages 190-198, 2014.
[24] N. Quadrianto, A. Smola, T. S. Caetano, and Q. Le Estimating labels from label proportions. J. Mach. Learn. Res., 10:2349-2311 2374,, 2009.
[25] Rosenblatt. Principles of Neurodynamics: Perceptions and the Theory of Brain Mechanisms. Spartan Books, New York, 1962.
[26] Rueping. SVM classifier estimation from group probabilities. In Proc. ICML, pages 911-918, 2010.
[27] C. Scott and J. Zhang. Learning from label proportions: A mutual contamination framework. Proc. NeurIPS, 2020.
[28] 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 Machine Learning and Applications and Workshops, volume 2, pages 84 89. IEEE, 2011.
[29] F. X. Yu, D. Liu, S. Kumar, T. Jebara, and S. F. Chang. xSVM for learning with label proportions. In Proc. ICML, volume 28, pages 504-512, 2013.
[30] X. Yu, K. Choromanski, S. Kumar, Jebara, and S. F. Chang. On learning from label proportions. CoRR, abs/1402.5902, 2014. URI.ttpp:// httt:://axxii www./i.v.ooooooooooooooooooooor abs/ 1402. 5902
12


Reviews:
[{"review_id": "VSOO4q1qG1M", "reviewer": "Reviewer_Cri6", "summary": "This work studies the problem of learning from label proportions (LLP), that is given bags of vectors and given the average of the positive labels in each bag, we need to find an LTF that satisfies most of the bags. The authors study the case where the bags contain at most 2 vectors. They study two cases, one where the vectors are taken from $\\mathcal X\\subseteq \\mathbb{R}^d$ and they are searching for an LTF; in the other case the vectors are taken from the $d$-dimensional hypercube $\\{0,1\\}^d$, and they are looking for an OR-LTF. In the first case, they provide an algorithm that satisfies $2/5$ of the bags and if all the bags are non-monochromatic (contain vectors with different labels) then the algorithm satisfies $1/2$ of the bags, for the other case they provide an algorithm that satisfies $(2/5 + \\gamma_0/d)$ bags and if all the bags are non-monochromatic it satisfies $(1/2+\\gamma_0/d)$ of the bags. Furthermore, for the last case, the authors provide an NP-hardness reduction to the Label Covering problem that shows that their result is qualitatively tight and that in general, we cannot hope for an algorithm that satisfies all the bags.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "First, this paper is very well-written and organized, with minor typos. This work shows that learning with LLP is difficult without any assumptions which does not hold in the standard (noiseless) supervised PAC learning (bags of size one); where the problem admits a polynomial-time algorithm that satisfies all the bags. In addition, I find this model very interesting as this model can have applications in privacy (i.e., when you do not want to reveal the labels of individual people) and a natural generalization of supervised PAC learning. Their algorithm uses the structural property that the $w\\cdot x_1\\times w\\cdot x_2$ is negative when the bag is non-monochromatic and then using this property they formulate SDP along with standard rounding technique. \nTheir lower bound (which is an NP-hardness reduction t) is technically challenging, which is the main contribution of this work and shows that their algorithm for the case of the non-monochromatic bags is tight, even if we allow the hypothesis to consists a union of LTFs.\n\nThe weakness of this work is that the structural property, which the algorithm heavily relies on, does not seem to extend on bags with sizes greater than two but still, this upper bound complements the lower bound for the tightness result.\n\nOverall, I recommend this work for acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work does not seem to have any negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "VQG4nsBRBVE", "reviewer": "Reviewer_w9nx", "summary": "This paper studies the learnability of LTFs from label proportions, on bags of size at most two.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n+ An algorithm is proposed which efficiently produces an LTF that satisfies at least (2/5)-fraction of the bags of an LLP-LTF instance, and (1/2)-fraction of them if all bags are non-monochromatic. Additionally, For LLP-OR over d-dimensional Boolean vectors, the authors improve these factors to (2/5 + Ω(1/d)) and (1/2 + Ω(1/d)) respectively.\n+ The authors also proved that  it is NP-hard, given a collection of non-monochromatic bags which are all satisfied 16 by some monotone OR, to compute any function of constantly many LTFs that 17 satisfies (1/2 + $\\epsilon$)-fraction of the bags for any constant $\\epsilon> 0$. The mathematics are concise.\n\nCons:\n-  It could be better if some experiments can be added to validate the proposed theoretical results.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations, and they do not see any negative social impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concern was found.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "E-Pzk3DdU9", "reviewer": "Reviewer_GBZR", "summary": "This work considers the problem of learning a linear threshold function (LTF) from label proportions. In particular they consider the special case where both single (as in the standard PAC learning setting) labeled (as 0 or 1) examples are observed or pairs of points $(x_1, x_2)$ together with their average label (which can be 0, 1, or 1/2) are observed.  They give two main results: a polynomial time algorithm that finds an LTF that satisfies at least 2/5 of the labeled examples (pairs and singletons together) and a lower bound that shows that finding an LTF that satisfies more than 1/2 of the labeled examples is NP-Hard.  For the special case where only mixed pairs, i.e., with label 1/2, are observed, the provided algorithm satisfies 1/2 of the labeled examples matching the lower bound (which also assumes only mixed pairs).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Learning from label proportions (LLP) is an interesting generalization of PAC learning that has attracted attention both from the applied and the theoretical learning communities.  This work considers the fundamental problem of learning linear threshold functions in the LLP setting.  It is interesting that even without noise it is NP-Hard to find a halfspace in the distribution free LLP setting (with bags of size 2) that satisfies more than 1/2 of the bags.  In the standard noiseless PAC setting (corresponding to bags of size 1) the same problem admits a polynomial LP algorithm that finds a halfspace satisfying all the bags.  Therefore, this work establishes a provable separation between PAC and LLP learning of halfspaces.  Taken together the upper and lower bounds of this work provide a nice (and in some interesting cases tight) picture of learning LTFs in the distribution free LLP setting.  Moreover, the results of this work (mainly the reduction) are technically interesting and non-trivial.  The paper is also well-written and the provided sketches of the proofs were very useful. \nOverall, this work provides interesting results on a fundamental learning problem in the LLP setting (which is well motivated) and I believe that it meets the standards of NeurIPS.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Does not apply.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "BiiC0h9r_BD", "reviewer": "Reviewer_myvN", "summary": "This paper intends to make a few theoretical contributions for the learning from label proportions framework. In this framework training data arrives in the form of bags that contain several feature vectors and the proportion of positive labels in the bag as ground truth. The authors focus on learning linear threshold functions, while making a restriction to bags of size two. \n\nA few theoretical results are presented. A first theorem gives a lower bound on the number of bags that can be \"satisfied\" with a polynomial time algorithm -- the authors define a bag as satisfied if the predicted proportion of positive labels equals the real proportion in the bag. A second theorem states that finding a linear threshold function that satisfies all bags is NP-hard in the worst case. ", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Frankly speaking, I found it very hard to follow the reasoning of the authors. This is probably due to my limited knowledge of the topic. This is not a paper I voted for, and it probably ended up in my batch because nobody else voted for it. In any case my review should have a low weight in taking a final decision whether this paper should be accepted or not.\n\nI believe that the presentation could be substantially improved. Let me mention the main problems that appeared while reading the paper:\n- I was unable to follow the problem setting that is described in Section 1.2. I had to consult the paper \"On learning from label proportions\" Yu et al. Arxiv 2014 to understand the problem setting. The authors should better describe that a training dataset consists of tuples (B,sigma) where B is a bag of feature vectors, and sigma is the proportion of positive instances in the bag. \n-L100: \"with the guarantee that there exists an LTF that satisfies all the bags\". It is not clear to me why such an LTF always exists. More explanation is needed here. Perhaps a reference or a short proof? \n-L103: \"when the guaranteed LTF is an OR\". The acronym OR is never defined in the paper. I have no idea what it is, but this is very crucial to understand the remainder of the paper. The acronym is already mentioned in the abstract and the introduction, but also there it is not explained what it is. \n-L135: What does the acronym WLOG mean? \n\nAs a result it is not possible to appreciate the impact of Theorem 1.2, as well as the implications that are discussed in Section 1.4 and 1.5. \n\nTheorem 1.2 looks like a nice result, but a lot of restrictions are needed. The restriction to bags of size two, which is omnipresent in the whole paper, is to my opinion a very restrictive condition, which limits the practical relevance of the results. Moreover, even with this restriction, the result is quite weak, because only half of the bags can be satisfied in polynomial time. \n\nOverall, I think that the presentation of this paper has to be improved before it can be accepted. Yet, as mentioned above, I am not an expert on the topic, and my opinion should have a low weight. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No comments. ", "review_text": "", "extra_scores": {"ethical_concerns": "No concerns. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "9yOGim1akwU", "reviewer": "Reviewer_pByS", "summary": "This paper studies proper learning of linear threshold functions (LLFs) in the learning from label proportions model.  There are two main contributions.  The first is a polynomial time algorithm that, given a collection of bags each of size at most two consistent with some (unknown) LLF, identifies an LLF that satisfies at least $2/5$ of the bags.  The second main contribution, which complements the first, shows that it is NP-hard to compute, given a collection of bags all satisfied by some monotone OR, to compute any function of constantly many LLFs that satisfies $(1/2+\\epsilon)$ of the bags for any positive $\\epsilon$.        \n", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Unfortunately, the proof techniques of Theorem 1.2 lie outside my area of expertise, so despite my best reading I am not absolutely sure whether the proof is overall correct.  It certainly looks credible enough though.\n\nMinor comments/suggestions:\n\n- Page 5, line 195: feature -> features.  Also, double occurrence of \"supported\".\n\n- Page 8, line 315: tranformed -> transformed\n\n- Page 8, line 317: one modify -> one modifies \n\n- Page 8, line 321: Should it be Appendix A rather than B?  (It seems the observations in the two bullet points appearing 5 lines after Fact A.1 were being used here.)\n\n- Page 9, line 343: \"it [is] NP-Hard...\"   \n\n- Page 11, reference [29]: Title of the paper seems to be \"On learning [from] label proportions\".\n\n- Supplementary, page 1, paragraph after Fact A.1: Should it be $\\langle z_1,z_2\\rangle$ rather than $\\langle z_1,z_1\\rangle$ ?  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, I think so.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of learning linear threshold functions (LTFs) in the following model, termed "learning from label proportions"(LLP). (Recall that in the standard statistical learning setting, one observes i.i.d. labeled examples (x, y).) In the LLP model considered in this work, in addition to labeled examples (x, y), one observes *pairs* of examples together with their *average* label. The main results of the paper are: (1) an efficient proper learner satisfying at least 2/5 fraction of the pairs, and (2) an NP-hardness of proper learning result ruling out approximation better than 1/2. For a special case of the problem, the authors show that 1/2 is in fact the optimal approximation ratio for efficient proper learning. The algorithmic result uses SDP, while the hardness result uses a PCP-style reduction from label cover. Overall, the reviewers agreed that this is a technically worthy and well-written theory paper that should be accepted to NeurIPS.
Decision: Accept (Poster)