Venue: NeurIPS 2022 Conference

Reviews:

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 investigates multiclass learning from label proportions, i.e. the situation in which the training data is only available in "bags". For each bag, the fraction of samples belonging to a certain class is known, but the exact assignment of instances to classes is not. The idea is to assign an arbitrary label to each instance in a bag, and then consider the bag to be a noisy learning problem with known transition matrix. For learning with noisy labels, they employ the forward-correction approach, proving new calibration-style generalization bounds for this, and then extending these to the multiple-noise matrix (i.e. multiple bags -- learning from label proportions case).
strengths_and_weaknesses: While the idea of interpreting learning from label proportions as a noisy-label-learning problem is not original to this paper, the multiclass application and use of forward-correction instead of unbiased loss functions constitute a non-trivial step over the existing literature. I agree with the authors that the additional results for forward correction may be of independent interest, though whether people working on noisy-label-learning will find these results in this paper I don't know. Maybe these results should, in addition to being stated here, be presented at some workshop or similar.

Overall, I found the paper to be well written and easy enough to follow in the main argument. In terms of notation, maybe this could be improved a bit, e.g. the symbol $\gamma_{k_{i, c_1}}$ has 3(!!) levels of subscripts. Similarly, the acronyms can get rather long:
LLPFC-..., LLPGAN, LLPVAT, LMNTM. None of these are actually pronouncable. Given that the context of the paper is LLP, I think it would be enough to mark the algorithms as FC-..., GAN, VAT, for example. 

So far, I've only gone through the math in appendices C1 and C2. Aside from the comments below, this looks good. I will update the review once I've managed to go through the rest of the proofs. 
questions: In equation (1), shouldn't $\alpha_i(c)$ also be an empirical/estimated quantity?

l. 713 How de we know $A(\epsilon)$ is the closed interval, as opposed to being open?

Proof of Thm. 17
Where does the first line, $\mathcal{C}_2 < \delta(\mathcal{C}_1) \implies \ldots $, come from? 

Lemma 22 should require that the matrix be invertible, I think.
limitations: Not a limitation per se, but as far as I can see this work leaves open quite trivial imporvements of the proposed algorithm, i.e. choosing the labels that are assigned to the bags in a way that minimizes the amount of noise that needs to be assumed.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: -This paper considers a conventional weakly supervised learning problem called learning from label proportions, where the training data are given in the form of bags and the proportions of each class within each bag are also given; the goal is to train a classifier predicting instance labels from such bag data. To solve the problem, they partition the bags into groups and model each group as a standard label noise problem. Next, they apply the forward correction loss, which was proposed for dealing with class-conditional label noise, to each group and study the generalization error bound of the proposed method. They also conduct some experiments to verify the effectiveness of the proposed method on some benchmark datasets.

strengths_and_weaknesses: pros:

-The paper studies the problem of learning from label proportions in a theoretically grounded way. They provide calibration analysis of the forward correction loss and then apply it to their problem setting. They also derive the generalization error bound of the proposed method under some assumptions.

cons:

-The title of the paper is a bit misleading, as the problem settings of learning from label proportions (LLP) and learning with label noise (LLN) are not mutually exclusive. To be specific, both of them can be seen as learning from corrupted distributions, where the class-conditional densities p(x/y) are corrupted in the former setting (LLP), while the class posterior probabilities p(y/x) are corrupted in the latter setting (LLN). In the binary case, the former is also called mutually contaminated (MC) learning, and the latter is also called class-conditional label noise (CCN) learning. It is proved that CCN is a special case of MC, see sections 2.2-2.3 in the following paper for details:

Menon et al. "Learning from corrupted binary labels via class-probability estimation." International conference on machine learning. PMLR, 2015.

Therefore, my feeling is that, in a general viewpoint, LLP can also be seen as a kind of label noise problem, and the title may cause some confusion that how to solve one label noise problem by another label noise problem.


-The writing of the paper is unclear and some parts are hard to follow. For example, in lines 40-42, the authors claim that Patrini et al. 2017 proposed forward correction loss to remedy the backward correction loss since it is poorly suited for multi-class deep learning settings; however, in the original Patrini et al. 2017 paper, they seem only mention that forward correction is an alternative method that corrects the model predictions (see Section 4.2 in Patrini et al. 2017 paper), without any discussions on how it remedies the backward correction. Also in lines 50-52, it seems that the mutual contamination model is not that different from the noise transition matrix used in this paper, which can be seen as a 2 by 2 noise matrix corrupting the class-conditionals.

-Some sections seem incomplete. Especially for the algorithm section, how to estimate the noise matrix is an important step for the proposed method, but the details of these steps are not included in the main paper. And there are no experimental results provided in the main paper. I strongly recommend simplifying section 4.3, as the definitions are mainly borrowed from existing papers and may be moved to the appendix, and using the saved space for discussing the noise matrix estimation algorithm and reporting experimental results.


questions: -The proposed method randomly partitions the given bags into groups and then formulates the problem of learning with multiple noise transition matrices. This random partition step seems problematic to me. As different partitions may lead to different noise transition matrices, which determine the difficulty of each LLN problem and will significantly affect the performance of the learned classifier. In Scott and Zhang 2020, they have discussed that the optimal pairing of bags can be obtained by solving an integer programming problem. In the current paper, could the authors provide similar analysis on the optimal partition strategy?

-In theorem 7, the weights w_i are expected to reweight noiser or larger subsets of data differently. But it is still unclear to me how to choose them in practice.

-In Section 5.3, the authors discuss a general case of LLP with NC bags. What if we are given m bags and m is not divisible by C? How to deal with such a general case in the current learning framework?

limitations: -The paper has some unclear parts that need to be carefully modified, and the organization of the paper can be improved.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper focused on learning from label proportions (LLP) task. First, they show that background theory of forward correction loss in learning with label noise (LLN), and extend the results with multiple noise transition matrices. Next, they propose LLPFC algorithm with probabilistic model for reducing LLP to LLN with multiple noise transition matrices.
strengths_and_weaknesses: ### Strengths

- The connection between LLP and LLN is reasonable and novel.
- They provide theoretical analysis and this would be useful for both LLN and LLP community.

### Weaknesses

- Lack of the experiment results
  - The paper did not provide any empirical results in the main paper.
  - Also, there are no/few explanation of the main experiment results in both main and supplementary paper.
- Gap of theory and practice
  - The theoretical analysis has many assumptions, but they did not give theoretical or empirical explanations to show that the assumption is reasonable in practice.
questions: - It would be nice to provide the explanation of the experiment results and what they support.
- Is it easy to estimate the clean prior $\sigma(c)$?
- Are Assumption 13 and 14 empirically reasonable in LLP?

limitations: They addressed the limitations in the paper.
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: Multi-class label proportion learning (LLP) is a weakly supervised learning problem that aims at obtaining a multi-class classifier with only bags (each bag is a collection of data points) and the proportions of different classes contained in the bags. In this paper, it is shown that the problem of label proportion learning can be solved efficiently with the techniques in the field of noisy label learning (LLN). The authors first give the consistency results on the Forward Correction (FC) technique, which is one of the prevailing methods in the field of  LLN, and then extend it to enable the use of multiple transition matrices. Under some mild assumptions, the authors show that the problem of LLP can be solved with the proposed extension of FC. Experiments on benchmark datasets are conducted to show the efficiency of the proposed method.
strengths_and_weaknesses: Strengths:

1. A novel extension of FC technique is proposed that removes the limitation on the number of transition matrices.

2. A clear connection between LLP and LLN is constructed with a strategy of converting label proportion to noisy labels and noise-transition matrices. With this conversion, the problem of multi-class LLP can be solved with consistency guarantee.

3. Rigorous theoretical analyses are conducted to support all the claims made in this paper. The provided generalization error bound well depicts factors that have influence on the proposed method.

Weaknesses:

The presentation of this paper should be improved for better readability. LLPFC, the main result of this paper, appears in the latter part of this paper, which makes the key point of this paper ambiguous. I think this problem can be mitigated by exchanging the order of Section 4.3 and Section 5.
questions: There can be quite a number of assignments of labels w.r.t. different bags and thus the construction of transition matrices can be flexible. For example, in the scenario mentioned in Section 5.2, there can be C! different assignments. If there exists an optimal assignment of pseudo noisy labels?
limitations: The authors have addressed the limitation of assumptions made in Section 5.1.
review_title: null

Meta-review: metareview: This paper proposes an approach to LLP based on a reduction to learning with label noise, using the forward correction (FC). The method is verified both theoretically and experimentally. The theory of the FC loss may also be of independent interest. The authors have addressed most of the comments. After the discussion, the reviewers unanimously recommended acceptance. 
confidence: Certain
Decision: Accept