PAC Learning Linear Thresholds from Label Proportions

Summary

Learning from label proportions allow training data to aggregate into sets of feature vectors with sum or average of their labels for each set as a label. As supervised learning, the goal is to classify test set of instances and minimize error of the classifier. This work focuses on learnability of LLP over Gaussian distributions of linear threshold functions. Although PAC learnability of LTFs has been studies in the LLP setting, PAC-LLP is intractable to learn LTFs using LTFs. This work formalize the problem into Gaussian distribution, which makes LTFs PAC-learnable. The approach is directly to maximize the instance-level accuracy on the distribution.

Strengths

1. PAC-learnability of LTFs in the LLP setting (which is a very interesting topic) is well-defined as Definition 1.2 and well-addressed by Theorem 1.3, 1.4 and 1.5, especially considering the case for k = q/2. 2. The proof of Theorem 1.4 is sound and solid coming with an algorithm and lemmas (even proofs for lemmas). 3. As a theoretical work, it is nice to have a section for experimental results, although the datasets look relatively simple.

Weaknesses

1. For Theorem 1.3 and Theorem 1.5, it is better to provide one or two sentences for each about proofs instead of putting everything in the appendix. You dont have to provide a separate section like Theorem 1.4. Just few sentences please. 2. The writing looks less readable for some sentences. Please refer to limitations section.

Questions

1. In Theorem 1.5, what is \lambda? What are \lambda_max and \lambda_min? Please clarify notations like what you did on Line 126. 2. What are relationships for r* and r head in Theorem 1.3, 1.4 and 1.5? I know you explained this on Line 145. Please put it ahead.

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

1 poor

Contribution

3 good

Limitations

1. If possible, please don’t include citations in the abstract. 2. On Line 59, I guess you typed one more “level”. 3. Please make “Theorem” (Like on Line 247 or 257) and “Thms.” (Like on Line 128) consistent (Use either one). 4. Need a space between “independence” and “i.e.,” on Line 132. 5. Similarly, for Line 148, need a space between “directions” and “We”. 6. You should read over your manuscript carefully and try to rephrase some sentences to make them more readable (I wont correct them here verbatim). - Some sentences have no subject. - Some sentences have no periods or spaces like limitations 4 and 5. - Some pronouns refer ambiguously.

Summary

This theoretical paper investigates the learnability of linear threshold functions (LTFs) in the learning from label proportions (LLP) setting. When the feature-vectors are distributed according to a Gaussian distribution and conditioned on their underlying labels, LTFs can be efficiently properly learnt. For the general Gaussian distribution, this paper develops a principal component algorithm which estimates the means and covariance matrices using subgaussian concentration bounds. Generalization bounds from bag classification error to instance classification error are also provided to resolve the ambiguity between the obtained solutions. The experimental results validate the effectiveness of the proposed techniques.

Strengths

The learnability of LTFs in the LLP setting is an important issue, this work provides some novel and significant theoretical results.

Weaknesses

$\bullet$ From Theorem 1.3 to 1.5, as the distribution becomes more general, the sample complexity required to efficiently properly learn LTFs also increases, and the difference between these sample complexities seems to be obvious. Numerical results on the difference between these sample complexities and associated discussion and analysis are necessary to more intuitively elucidate these theoretical results. $\bullet$ Intuitively, the theoretical results in this paper will depend on the label proportion $k/q$, but in the end, it is mainly implemented on the bag size $q$, i.e., the order of the sample complexity does not explicitly reflect the label proportion $k/q$. While this is not mathematically problematic, it would be helpful to add some remarks to illustrate this point. $\bullet$ The readability of the paper needs to be improved. More introductions to the problem setting and related definitions of LLP, as well as further illustrations and explanations about the existing theoretical work will help readers better understand the theoretical results in this paper. In addition, some typos also harm the readability. Typos: $\bullet$ Line 27: they're labels The goal -> their labels. The goal $\bullet$ Line 132: independencei.e., -> independence, i.e., $\bullet$ Line 146: $r = q/2$ -> $k = q/2$ $\bullet$ Line 148: directionsWe -> directions. We $\bullet$ Line 350: bag satisfaction -> bag classification $\bullet$ Some typos in the Supplementary Material also need to be checked and corrected.

Questions

Please refer to the Weaknesses for details.

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

This work does not seem to have any potential negative societal impact.

Summary

This work studies the problem of learning linear threshold functions (LTFs, aka linear classifiers) under the setting of learning from label proportions (LLP), where the training data are "bags" (aka sets) of instances, and the training labels are classifier proportions of the instances in the bag. Under the assumption that the instances are gaussian distributed, bags are instances sampled iid, and the size of the bags are upper bounded, the authors show that it is possible to efficiently (properly) learning LTFs.

Strengths

The problem setting of PAC-LLP deserves more attention. The authors gives good justification for why LLP matters, e.g., privacy and legal. In light of the previous theory works on LLP that shows NP-hardness of PAC-LLP learning LTFs, this current work is surprising, relvant, and interesting to the ML community. Theorem 1.4 gives an algorithm that highlights the interesting geometry and the clever exploitation of the subtle difference between sampling with and without replacement.

Weaknesses

After Section 1.1, it will be useful for the reader if there is an overview of the paper. Something along the lines of "Sec 1.3 are the main results. Sec 1.4 gives proof sketch of the main results and high level description of the algorithms. Section 3 state these algorithms precisely..." For Theorem 1.3, it will be useful to interpret the sample complexity. Is the sample complexity essentially the difficulty of estimating the mean of the bag vectors? If so, the authors should make this explicit. For Theorem 1.4 and 1.5, are the lambdas eigenvalues of the covariance matrices? Please explicitly say so.

Questions

Why is Definition 1.2 called the bag oracle? Isn't it just the distribution over the training data (of bags)? Does the authors believe that the results are tight? In other words, is LLP under the considered data assumption essentially equivalent to mean/covariance estimation? It will be good if there is a discussion regarding the sample-complexities in LLP versus ordinary classification. From this point of view, what is the "cost" of only having access to bagged data?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

Yes.

Summary

This paper studies PAC learning when the training data is aggregated into sets or bags of feature vectors. For each bag, we observe the feature vectors of these bags and only the average of the labels in the bag. They focus on the case when the feature vectors are distributed according to a Gaussian distribution, and the hypothesis class is the set of Linear Threshold Functions (LTFs). Their main results include polynomial time algorithms for learning the correct halfspace when the Gausssian is either standard or skewed and the correct LTF is either homogeneous or not. Finally, they compare their Algorithm experimentally with various procedures from prior work.

Strengths

This paper proposes a very interesting direction for learning under label aggregation, which bypasses the lower bounds that existed for this setting in prior work. I think it opens the way for more interesting problems to be considered in this setting, by possibly changing the assumptions on the distribution or the hypothesis class. All the claims are sufficiently explained and the presentation is generally clear. The authors introduce some interesting technical novelties to extract information about the true vector of the LTF using the aggregated labels. In particular, the idea of comparing the variance of a random pair with and without replacement and finding that it is maximized in the direction of the true vector $\mathbf{r^\star}$ is very elegant and leads to some interesting algorithms, which can be implemented in polynomial time using PCA. Moreover, the techniques for handling non-centered and skewed Gaussians with unknown parameters are non-trivial and interesting.

Weaknesses

This is not a significant weakness, but the technical presentation in some parts of the paper seems quite dense and not necessarily adding to the understanding of this work. For example, in the proof of Theorem 1.4 or Lemma 4.2, too much emphasis is given in the calculation of the optimal setting of parameters and sample complexity. I would prefer a more intuitive explanation at times, although I'm not sure it that's possible.

Questions

How tight are the sample complexities provided in Theorem 1.4 and 1.5 in terms of their dependence on the minimum and maximum eigenvalues of the covariance matrix and the size of the bag? In Theorem 1.5, we also see a term involving $l$, which depends on the parameters of the true LTF. Is such a dependence necessary?

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

No limitations.