Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This work aims to propose an algorithm and theoretical analysis for learning from the label proportion problem, where the labels are given in aggregated form as a proportion of true labels in a bag of features. The proposed algorithm is for the case when the size of the bags is less than three and it comes with guarantees on the fraction of satisfying bags. The theoretical analysis shows the hardness of the learning problem. Some experimental results on synthetic data are provided.
strengths_and_weaknesses: I find the hardness results, saying that satisfying more than 1/q + O(1) fraction of bags in the learning from label proportion problem is NP-hard, to be interesting since most of the previous work focus on developing new algorithms while not  much looks into the inherent hardness of this problem. However, here are a few concerns:
- My main concern is the readability of this work. Even though the hardness result is interesting, I find it hard to understand the proofs. For the overview provided in Sec. 1.5, it would be helpful if the definitions of label cover problem and the template of a dictatorship test are formally stated to make this work more self-contained. Also, the proof in Sec. 5 is hard to parse since it is mostly formulas without intuitions. The readability of this proof needs to be improved, probably by making it more verbal. Besides, there are too many typos that harms readability a lot. See below.
- It seems that the complexity of the proposed algorithm is at least cubic in the size of features, which make it impractical. It would be helpful if the authors provide a detailed discussion on the complexity of the proposed algorithm. I wonder how the runtime increases as the number of dimension d increases.
- The empirical evaluation seems too toy and comparison with existing learning from label proportion algorithms are missing.
- Missing references on existing work on learning from label proportion:
Scott C, Zhang J. Learning from label proportions: A mutual contamination framework. Advances in neural information processing systems. 2020;33:22256-67.

Typos:
- Line 97: the lower case f is not defined.
- Line 97: it is unsplit by F is the latter ... -> it is unsplit by F if the latter ...
- Line 110: In the worst, case -> In the worst case, 
- Line 129: r is not defined.
- At Line 150, the symbol (*) is used to denote a formula while later at Lemma 2.4 the same symbol (*) is used to denote another formula.
- Line 205: E is undefined.
- Line 310: A right parenthesis is missing.
questions: - Can the authors discuss the complexity of the proposed algorithm?
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes algorithms for learning linear threshold functions (LTFs) from label proportions. In this model, the learning algorithm is given "bags" of points with the proportion of points in the bag labeled $1$. The goal is simply to find an LTF that maximizes the number of bags on which it labels the points exactly at the right proportion. The problem is NP-hard, so approximation algorithms are considered. The paper improves upon the previously known lower bound for bags of size $2$. It also gives a $\frac{1}{12}$ guarantee for bags of size $3$, and in general an $\Omega(1/q)$ guarantee for bags of size $q$. It is also shown that it's NP-hard to approximate the problem with bags of size $q$ beyond $\frac{1}{q}+o(1)$. The method is to solve a semidefinite programming relaxation, then round the result using a random hyperplane.
strengths_and_weaknesses: The main contribution of the paper is the new SDP relaxation, which is new, non-trivial, and interesting.

The model has been studied before, and the bags input is justified by issues of privacy/legal constraints. However, I'm not completely convinced by the justification for the objective function (that for small bags it's reasonable). Why insist on getting as many bags as possible to have the exact input ratio, perhaps at the expense of gross errors on the other bags? Alternatively, one can try to minimize the total deviation, or the maximum deviation, or a host of other alternatives.
questions: What's the justification for choosing this objective function over, say, minimizing the total deviation or maximum deviation over all bags? Do your methods extend to other choices of objective? Are there previous results on other choices? Are these alternatives easier? harder?
limitations: None.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the fairly natural learning problem of "learning from label proportions". The underlying problem is realizable supervised classification, however, instead of receiving labelled instances, the learner receives multiple bags of instances and the proportions of positively labelled instances in each bag, i.e., the "label proportions". This is motivated by e.g., privacy concerns. The goal of the learner is to find a hypothesis (from a hypothesis space) which predicts the instance labels in all bags in a way such that the number of bags with correctly predicted label proportions is maximised. This generalises regular supervised learning, as for bags of size 1 this corresponds to classifying all instance labels correctly. The main concern of the authors is to construct a polynomial-time "empirical risk minimiser" (or the equivalent thereof in this label proportions scenario) and not generalisation aspects (e.g., to new independently drawn bags).

In particular, the authors focus on this label proportions learning scenario in the case of linear threshold functions, i.e., halfspaces. For bags of size $\leq 2$ previous work suggested first algorithms and hardness results. This paper improves the hardness lower bound for bags of size at most 2 from essentially $1/2$ to essentially $4/9$. Additionally, this paper generalises these results to bags of size $\leq 3$ and achieves similar results there through an involved SDP-based relaxation. They also derive hardness lower bounds for the general case with bags of arbitrary size, which also applies to the improper case of functions that depend on a constant number of halfspaces, and propose an algorithm which asymptotically achieves this bound, however, using a weaker notion of satisfied bags.

They also prove a novel characterisation of psd matrices A,B satisfying $A\preccurlyeq B$, which might be of independent interest.

Finally, the theoretical results are complemented by first practical experiments, where the authors compare their approach with a simple randomised baseline on synthetic datasets.
strengths_and_weaknesses: Very well-written and easy to follow paper. The contributions will be most likely interesting to a theoretical sub-community of NeurIPS and potentially enables further work building on top.

The experiments are sufficient for such a theoretical contribution. In fact, they are not really necessary.

Minor points:
* Why do the authors not use the more common and simple term "halfspace" instead of LTF
* The two overview sections (1.4, 1.5) are helpful. To round it up the authors could include pointers to the actual Lemmas and Theorems (e.g., while discussing line 164 and following maybe note that the full statement is in Lemma 2.3, or multiple times on page 5). 
* Please add a short section on "LLP-LTF[q]" with the most important details in the main paper, as well. For example, by moving the experimental evaluation to the appendix.
* (Standard) references for the dictatorship test, the lavel cover problem , and the folding trick would be very much appreciated.
* I would switch the order of "4. Experimental Evaluation" and "5. Hardness Result" to separate the theoretical results from the empirical ones more clearly.

Typos:
* Berry-Essen --> "Esseen"
* line 126: missing " " (space) between "proceeds.Since"
questions: While the achieved results for linear thresholds are interesting, the question arises whether similar algorithms and bounds are possible in the general case (for arbitrary hypothesis space / set systems). Maybe there is some complexity notion similar to the VC dimension determining "learnability" here. 

What about halfspaces with margin $\gamma$? Does this help in the learning scenario?

While it is true that for bag sizes $>2$ it is unclear whether $\langle r, x_1\rangle\langle r, x_2\rangle>0$ cannot be determined anymore, the label proportion still determines $\langle r, x_1\rangle\cdot\ \dots\ \cdot\langle r, x_q\rangle>0$. Can this be used by some algorithm? Please elaborate, as it seems like a natural generalisation of the $q=2$ case.

Do the authors thing the hardness bound of $4/9$ is best possible for $q=2$?
limitations: The paper only discusses the computational problem of finding a hypothesis such that a maximum number of bags is satisfied (have correctly predicted label proportions). However, as the problem is called "learning from label proportions" a discussion of possible generalisation bounds would be very interesting (prediction label proportions of unseen bags). Previous work, e.g., [28], apparently has generalisation bounds.
review_title: null

Meta-review: metareview: All of the reviewers found the theoretical results in this paper novel and significant. In particular, the main contribution of the paper, which is the new SDP relaxation, appears to be non-trivial and interesting. However, there remain concerns about readability of the paper, as outlined by one of the reviewers, and we request that the authors put some effort into addressing them.
confidence: Certain
Decision: Accept