Easy Learning from Label Proportions

Summary

This paper focuses on the problem of learning from label proportions. It addresses the performance degradation issue of the EPRM method when the hypothesis class lacks sufficient expressiveness. To overcome this problem, the paper introduces EasyLLP as a solution. In practice, EasyLLP differs from EPRM (or PropMatching) in the calculation process. EasyLLP first calculates the corrected instance-level loss and then takes the average, whereas EPRM first takes the average of the bag-level predictions and then calculates the loss. This simplifies the implementation of the learning algorithm: just utilize a corrected loss function and approach the problem as a regression task.

Strengths

This paper studies the problem of LLP, which is an important problem to the community. The proposed method is based on a novel loss correction method, which could be useful for some related problems. The paper points out and analyzes the limitation of EPRM. This finding is interesting and novel. The proposition 4.2 with its proof seem to be a significant contribution. Based on proposition 4.2, the proposed EasyLLP is sound and easy to implement. Experimental results show the effectiveness of the proposed EasyLLP.

Weaknesses

There are some minor issues: 1. Literature [16] is also a method based on unbiased risk estimation, and is very related to the proposed method. How's the comparison between EasyLLP and [16]? It should be compared and discussed in the experiments. 2. In section 3 the paper discussed the limitation of EPRM. However, why EasyLLP solves this problem is unclear. Please add some discussion.

Questions

See weaknesses part.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

3 good

Presentation

3 good

Contribution

3 good

Limitations

n/a

Summary

The paper aims to advance the theoretical understanding behind the LLP problem, and provide the conditions under which the algorithm is expected to work. They propose a theoretically founded algorithm for learning from label proportions called EasyLLP. In particular, they have shown how to estimate the expected value of any function of (x, y) pairs from labeled data. They have also shown complexity guarantees for ERM and convergence guarantees for SGD. The authors have also evaluated their proposed approach against PropMatch and 2 baseline models, on 4 datasets: MNIST, CIFAR-10, UCI Adult, and Higgs. For all the datasets, the authors have considered the corresponding binary classification variant, if they were multi-class. The results show

Strengths

The authors have clearly described their approach, and demonstrated the results against baselines on 4 datasets. Understanding the theoretical nature of LLP models is important given the application of the domain. The paper is a good step in that direction.

Weaknesses

In order to improve the reproducibility of the approach, it will be helpful if the authors can either share their code or provide pseudocode for using EasyLLP. The evaluation is limited to fairly broad datasets such as MNIST, CIFAR and Higgs. The LLP problem is applied to various real world problems, including those rightfully noted by the authors, such as advertising. The datasets in such domains have additional challenges such as a more complex feature space and class imbalance. It will be great if the results can be shown with such complexities taken into account. I'd encourage the authors to consider more recent approaches in LLP for comparing their results.

Questions

Concerns already listed under Weakness.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

3 good

Presentation

3 good

Contribution

3 good

Limitations

n/a

Summary

The paper presents a debiasing approach called EASYLLP for Learning from Label Proportions (LLP), where only class label frequencies in bags are available. The authors provide theoretical analyses of a label proportion matching algorithm and propose a general debiasing technique for estimating instance loss. Experimental results demonstrate the effectiveness of their approach compared to existing methods in various learning frameworks.

Strengths

The proposed method in the paper has several advantages. Firstly, it is described as simple and straightforward, making it easy to implement. This aspect can be beneficial for practitioners and researchers looking for an accessible solution to the problem of Learning from Label Proportions (LLP). Additionally, the paper is praised for being well-written, indicating clear and concise explanations of the concepts and methods presented.

Weaknesses

My main concern is its relationship with previous works, such as [16] and references therein. Both of the papers assume data are generated at random, and propose a debiasing procedure via linear transformations, with similar theoretical results on consistency. It is difficult to see any fundamental innovation in the current work compared to previous works, especially given that all theoretical results are straightforward after confirming the consistency of the proposed risk. For [16] and a more fundamental work On the Minimal Supervision for Training Any Binary Classifier from Only Unlabeled Data (ICLR19), they require separation of the class prior distribution, as argued in the paper, because they have a /theta-/theta' in the reweighting denominator, which could be reduced by multiplying them. The difference seems to be that the ICLR19 paper is calculating the expectation of risk using two sets, but the current paper is using one set; other derivatives are similar.

Questions

Compare with [16] and other works such as On the Minimal Supervision for Training Any Binary Classifier from Only Unlabeled Data (ICLR19), what are the fundamental differences of the current paper? --------------------- After rebuttal, I am satisfied with the answer on the two key differences, and would like to raise my score.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central 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

3 good

Contribution

2 fair

Limitations

yes

Summary

The authors start by providing a theoretical analysis of the proportion matching algorithm, a standard algorithm from the literature that simply minimizes the loss over the average instance-level predictions.

Strengths

I find the way the authors approach to the problem of learning from label proportions, and the goal they set out to achieve to be very worthwhile. I also believe the theoretical results therein might of interest to the community. I did, however, struggle at times in managing to follow the paper. Therefore, in my opinion, the authors really need to spend some effort polishing and refining the exposition to make it accessible to the broader community.

Weaknesses

- My main gripe with the paper is that I would've liked to see more discussion, or intuition following each Theorem, corollary or proposition. For instance, I really would've liked the authors to spend some time discussing the assumption upon which Theorem 3.2 hinges, and if such an assumption is expected to hold in practice (although I do appreciate them giving an example for when it fails due to the model class not containing the true conditional distribution) - Empirical evaluation seems to suggest improvement only with large bag sizes (2^7), and on some dataset not at all, compared to the baselines.

Questions

- Could you please say more regarding the sentence starting line 166? While the objective being approximation by equation (1) is clear to me, I'm not clear own what it means for equation (1) to "correctly approximate" it. - In Figure 1, left plot, why does the prop matching loss start out much lower compared to other methods? - Could you please elaborate on the statement of Theorem 3.2? In particular, I've been trying to conclude how strong of an assumption it is that the minimizer of the expected loss the average of $Z$ (I do believe it is very strong, and seldom holds in any realistic setting) - In definition 4.1: - Is $p$ as defined in the notation section or Theorem 3.2? - I find the use of $\alpha$ here confusing, as my first instinct was to think of it as a label proportion, but in the notation section you only define $\alpha$ as a function of a bag. I then noticed that it is any real-valued parameter in $\[0,1\]$. - Why does this definition make sense? I interpret this as somehow correcting the bias introduced by using bags instead of instances. If that is true, why does this correction term make sense? - I think this definition requires some notion of distribution due to the presence of $p$? - In proposition 4.2: - the notation does not make it clear how $x_j$ is related to $\mathcal{B}$. I think something along the lines of $\mathbb{E}_{(x_j, \alpha) \sim (\mathcal{B}, \alpha)}$ would perhaps better convey your intent? But then I'm confused again, because somehow $\tilde{g}$ is a function of an individual instance and $\alpha$? But $\alpha$ is a function of the entire bag? - Am I correct in reading the equations as saying that the soft-label corrected function averaged over all bags and proportions is simply equal to $g$ averaged over the instance-level data distribution? If so, then it is my opinion that this needs be framed and discussed since, from what I understand, your entire approach hinges upon this result, and it is by no means easy to see. - I'm very confused by Equation 5,

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

2 fair

Contribution

3 good

Limitations

Adequately addressed