Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper aims to minimize the dynamic regret (instead of the static regret in previous work) for the problem of online label shift (OLS). Specifically, to handle the non-stationarity environment and the lack of supervision, this paper constructs a new unbiased risk estimator that utilizes the unlabeled data and then proposes online ensemble algorithms to deal with the non-stationarity nature.  Besides, theoretical analyses about the dynamic regret bounds are provided. Experiments are conducted to validate the effectiveness of the proposed method.
strengths_and_weaknesses: I am not an expert in this area and may neglect related literature. Below are my comments.

### Originality
The novelty is limited. This work is mainly built on [15]. While [15] mainly aims to minimize the static regret for the OLS problem, this work aims to minimize the dynamic regret, which needs to consider more suitable online learning algorithms.

### Quality
Overall, this paper is sound. The proposed methods are natural and built on related work. The claims are supported by formal theoretical results. I have not carefully checked the proofs and the techniques seem standard. Experimental results are also provided to illustrate the effectiveness. Please see my main concerns in the Questions part.

### Clarity
This paper is well written and organized.

### Significance
This paper should be of interest to the community of label distribution shift, and online learning. Besides, the non-stationary setting may be very practical in some applications although this paper considers the simple OLS setting.
questions: 1. As claimed by the authors, [15] mainly utilizes the $0/1$ loss while this paper uses the surrogate loss in the construction of the unbiased risk estimator. However, I find the provided dynamic regret bound is about the surrogate loss while we originally care about the $0/1$ loss (just the same as the evaluation measure in experiments). Thus, a natural question is what is about the dynamic $0/1$ regret bound? Please give more discussions.
2. In this paper, the hypothesis set (or the model domain) $\mathcal{W}$ is assumed to be known but nearly impossible in practice. I also checked the experimental part but find no useful information. How to select or set $\mathcal{W}$? Please give more discussions.
limitations: While this paper is built on related work, I am afraid that the novelty may be a bit limited.
review_title: null

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work studies the problem of online adapting to label shift (e.g. where P(Y|X) is fixed, but the priors change) using the framework of online learning. It features a very strong theoretical analysis and excellent experimental evaluation. The presentation is great, and the Appendix even includes a brief intro to OCO! 
strengths_and_weaknesses: 1) Very strong theoretical and seemingly sound analysis (I did not have time to go through the proofs) and various different variants of the algorithm are proposed and evaluated to show their pro's and cons. 

2) A very clear comparison is made to related methods and its discussed in great detail what are the pro's and cons of the proposed method compared to the related work 

3) The experiments seem very extensive and show clearly what the authors want to show

4) I was a bit sad to see the conclusions being postponed to the appendix; but the related work was sufficiently covered in the main text according to me. 

I would maybe Transpose Table 1 if there is space to make it easier to read (easier to compare numbers vertically than horizontally). 



questions: 1) Remark 1; can you make it more formal what you mean by that you should focus on dynamic regret? Could you formally prove the advantage? Or is this already clear from the experiments? 

2) Line 162 - Should this really be \mathbb{E}_{x \sim D_t} ? I have the feeling that it should not be dependent on t here. 

3) "method still hardly suitable for the OCO framework" (line 195) - why? Can you be more precise why that is the case? CUrrently a bit vague. 

4) I could not understand the remark in line 202 - where is it shown that the risk estimator is convex in expectation? 

5) In line 260; the risk is used in the Hedge algorithm. Is there not a overfitting concern here? Should this risk not be estimated using validation data or fresh samples? 
limitations: The authors reflect and conclude sufficiently on their own work - indeed high probability regret bounds would be nice to have as a future work, but the current work is already multi-contribution and definitely high quality.
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 addresses the problem that the label distribution in testing data is different from training data. The problem is interesting and with practical interest. The authors propose to include the testing data in the training process in the goal to reduce error.

The proposed method has two stages: first selecting data and corresponding labels from the initial distribution; including unlabeled data from another distribution. If the label shift is not considered, would the model produce wrong prediction results?

The goal of the work is to make the model adaptive to the new label distribution. Is it a two way door design? That is, when there is no label distribution shift, the model performs as well as the vanilla one trained on the data following the initial distribution.

In Theorem 1, the constant \sigma >0 denotes the minimum singular value of confusion matrix. What is the assumption to make the minimum singular value of confusion matrix to be bigger than 0, instead of 0? 

V_T measures the intensity of the label distribution shift. Is there any threshold that, if V_T is smaller than the threshold, the label distribution shift does not have effect about the performance of the vanilla model.

Could the method be applied to both classification and regression?
strengths_and_weaknesses: Strength:
-The problem is interesting and with practical interest.
-The paper is well written.

Weakness:
- The assumptions of the work are not clarified.
- The data in the experiments is not in large scale.
questions: If the label shift is not considered, would the model produce wrong prediction results?

Does the proposed model follow a two way door design? That is, when there is no label distribution shift, the model performs as well as the vanilla one trained on the data following the initial distribution.

In Theorem 1, the constant \sigma >0 denotes the minimum singular value of confusion matrix. What is the assumption to make the minimum singular value of confusion matrix to be bigger than 0, instead of 0? 

V_T measures the intensity of the label distribution shift. Is there any threshold that, if V_T is smaller than the threshold, the label distribution shift does not have effect about the performance of the vanilla model.

Could the method be applied to classification and regression?
limitations: yes
review_title: null

Meta-review: metareview: This paper considers online learning under a label shift scenario: an initial model is trained  on labeled data from the first distribution, and then the learner receives unlabeled data from shifting target distributions in rounds. The assumption here is that the underlying label-conditional densities (d(x|y)) do not change, only the "weighting" of the various labels changes between the rounds. This submission introduces the notion of dynamic regret for this setting where the learner is round-wise compared to the best predictor for the round-specific task. The submission provides an algorithm and bounds on this dynamic regret (that, naturally, involves a term measuring the amount of label-weighting-shift) as well as empirical evaluations of the proposed algorithm (both on synthetic and real datasets).

Overall this appears as a well-rounded submission on a problem setup that is clearly relevant to the NeurIPS community.

Since data is provided in batches per learning round, it would be appropriate to also compare to life-long learning setups, algorithms and guarantees, rather than just to online learning. It seems that the studied framework is more commonly referred to as life-long learning, but this connection and the corresponding literature is entirely ignored in this submission. This should be fixed/clarified before publication.
confidence: Less certain
Decision: Accept