Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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. 
Their 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.

The 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.

Overall, I recommend this work for acceptance.
limitations_and_societal_impact: This work does not seem to have any negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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).
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. 
Overall, 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.
limitations_and_societal_impact: Does not apply.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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$.        

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.

Minor comments/suggestions:

- Page 5, line 195: feature -> features.  Also, double occurrence of "supported".

- Page 8, line 315: tranformed -> transformed

- Page 8, line 317: one modify -> one modifies 

- 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.)

- Page 9, line 343: "it [is] NP-Hard..."   

- Page 11, reference [29]: Title of the paper seems to be "On learning [from] label proportions".

- 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$ ?  
limitations_and_societal_impact: Yes, I think so.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the learnability of LTFs from label proportions, on bags of size at most two.
main_review: Pros:
+ 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.
+ 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.

Cons:
-  It could be better if some experiments can be added to validate the proposed theoretical results.

limitations_and_societal_impact: The authors adequately addressed the limitations, and they do not see any negative social impact of this work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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. 

A 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. 
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.

I believe that the presentation could be substantially improved. Let me mention the main problems that appeared while reading the paper:
- 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. 
-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? 
-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. 
-L135: What does the acronym WLOG mean? 

As 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. 

Theorem 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. 

Overall, 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. 
limitations_and_societal_impact: No comments.
review_title: null

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)