Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors in this work focus on the online label distribution shift problem, where the prevalence of each of the possible labels changes dynamically and the model needs to adapt in an online manner to the new data. The online performance is measured in terms of regret, however, using off-the-shelf algorithms is not immediate here since we do not receive feedback for how well does the learner perform in each iteration. The authors circumvent that using a reparametrization of the problem. The paper analyzes the regret of two different algorithms, proves that it is sublinear under assumptions and performs experiments.

main_review: Overall, this paper is studying an important problem. The distribution shift literature has gotten a lot of interest recently given recent results that show the non-robustness of machine learning models to it. I liked the problem formulation using online learning and I found the observations about the re-weighting that allows us to circumvent the lack of immediate feedback interesting. However I think that there are some issues with the paper, from the fact that the noise that occurs from learning the confusion matrix is not taken into account (I would imagine that this just gives some additive terms in the regret bounds so it's not really too important), to the assumptions that is not clear how much they correspond to reality. In particular, assumption 1 doesn’t hold and assumption 2 seems very strong to be true as well.

Follow the leader normally doesn’t give us sublinear regret and given that the authors haven’t made any assumption on the rate of the distribution shift, as far as I can tell, I assume that it’s the strength of assumption 2 with delta = 0 that makes the problem too easy and gives the sublinear regret. I would appreciate the response from the authors here in case I’ve missed something.

As a result, the theoretical results are a little limited despite the interesting modeling, this is why I am ranking this as a borderline paper.

Typos:
L141: in the definition of Z: should it be f_0 instead of f?
Algorithm 3: you have omitted the function symbol next to the gradient.
L188: "second equality" instead of "inequality"


limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes novel methods for online label shift adaptation. The main idea is to update the reweighting vector online, given a fixed initial predictor. The reweighting vector, in the offline case, is the ratio between the target marginal label distribution and the current marginal label distribution. This paper follows two classic online learning algorithms, online stochastic gradient descent and follow the history. Regret bounds are derived for each of the methods, respectively. In the experiments, the proposed method is compared with baselines on both simulated label shift and natural label shift in the real data. 


main_review: The technical contribution is novel and sound. Even though the adaptation only deals with the weight, not the predictor, which makes it a bit unnatural, I think the idea and the proposed method are still interesting.

This paper is written in a clear way. My only feedback is, it is a bit late until I realize what is updated in the methods is just the weight but not the predictor. In other words, the “optimal” predictor in the regret terms is also dependent on this fixed initial f_0. As someone who is not very familiar with online learning but very familiar with domain adaptation, this is a bit surprising. So I would suggest making this important point clear earlier in the paper and justify it better.


On the technical side, I mainly have the following detailed feedback and questions:

1. What will happen if f_0 is not good? This is my biggest concern. In follow the history, f_0 is even assumed to be bayes optimal. However, in practice, this is hardly true. It seems, if f_0 is poor to start with, the online algorithm would be of little use even if the regret is bounded and converges, because you are converging to something equally poor. But if f_0 is good enough, the online adaptation also does not matter too much because f_0 is probably already giving you good results. I feel there is a dilemma when the setup of the problem is like this. 

2. I feel seasonal changes in the label shift makes more sense than continuous changing label shift. This is also mentioned in the experimental section of this paper. A recent paper sort of considered this case in an online active learning setting: https://arxiv.org/abs/2007.08479. So I was wondering whether the proposed method can be extended to mini-batch settings of label shift and how they work there. It seems to be a more practical case.

3. In theory, the evaluation of the method is based on the regret. But if the “optimal” predictor is even a changing one (q_t changes over time), I was wondering how useful the regret is as a metric here. In the adaptive case, there is a metric like the competitive ratio or other metrics that make more sense. Can you comment on this and justify why we should use regret here?

4. It is not very clear how \hat{q}_t is obtained in the paper. It is used in both algorithms. Also, how do we use the holdout set D_0 to estimate the gradient? These details are very important to understanding the algorithm. 

5. In offline label shift cases, the level of shift will affect the result a lot. It would be helpful to include some studies in experiments to see how label shift magnitude changes the results.

6. In experiments, only the average error is used in the evaluation. But to better validate the theory, the convergence behavior of the algorithms should also be shown. 

limitations_and_societal_impact: There is no discussion of the potential negative impact in this paper. I do not see any immediate negative impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper attempts to solve the problem of online label distribution shift. They show a clearly highlight the differences of this setting from the standard online learning setting and then show a reduction using which standard online learning techniques can be used to solve this problem. They also conduct few experiments to illustrate the performance of their algorithms.
main_review: This paper is well written and is technically sound.

Strengths: 
1. The authors direct attention towards the online version of a problem that has been studied in offline learning before. They clearly delineate the challenges it poses and how it is different than vanilla online learning. 
2. The reduction to finding a weight vector makes the problem quite simple and easy to understand.

Weaknesses:
1. Assumption 1 says that the objective is convex and the justification is given empirically in the appendix. Some of the plots show the objective to be only approximately convex instead of convex. Perhaps introducing some assumption like weak convexity, where the objective + a small quadratic is convex and analyzing it would be useful. Some graceful degradation of the rate with how small the quadratic to be added is would be an interesting and stronger result as opposed to the justification using some experiments.
2. The interesting case in the symmetric optimality assumption is when $\delta \neq 0$ and this case is dealt with only in the supplementary. Having that theorem in the main paper and some commentary about degradation with $\delta$ and how does it compare with the $(1/\sqrt{T})$ regret would be helpful.
3. (minor) The confidence intervals in the experiments are made by running only 3 trials, running at least 10 trials with different seeds seems useful.
limitations_and_societal_impact: See weaknesses for limitations.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose a novel technique to address continuous changes in the label prior distribution p(y) of the test set, a setting they name ‘online label shift’. Assuming a fixed class-conditional distribution p(x|y) their method estimates the current test loss without having access to any label and applies Online Learning techniques to adapt to the current changes in distribution continuously.
main_review: It is my opinion that the work includes a solid contribution to the label shift setting by proposing an online scenario where the label prior distribution changes over time. 

Strengths:
- The analytical work is clear overall and adequately supports the claims. In particular, the proofs provided for the theorems provide a valuable support for the comprehension of paper.  
- An extensive empirical validation faily supports the two main assumptions (convexity and symmetric optimality).
Overall the paper is clear and well written.  

Minor weaknesses:
- I had difficulty understanding the Optimal Fixed Classifier (OFC) introduced at line 228. From my understanding, this should denote the best ideal classifier, which uses the optimal rebalancing factor p found using the real label. If that’s the case then I would expect the OFC to be the lower bound for the error rate in all the experiments of section 5, which is not the case.  
Typo:
- Line 546: Assumption 3 -> Assumption 1

limitations_and_societal_impact: Yes
review_title: null

Meta-review: The paper considers the problem of re-weighting class scores to adjust for changing label probabilities in an online learning setting. It combines an estimator due to Lipton et al. with basic online learning techniques to derive algorithms, providing theoretical analysis and experiments. The reviewers all appreciated the novelty of the proposal and assessed it can potentially set ground for subsequent work on the important topic of dealing with distribution shift. Consequently, I recommend acceptance of the paper.

However, the reviewers also raised several important concerns about this work, particularly around the validity of assumptions in the theoretical derivations. The authors should carefully revise their manuscript to address the concerns. Building on comments of the reviewers, I would like to highlight here two issues that need special attention:

1. *Assumptions 1 and 2.* The revised manuscript needs to clarify that these are strong assumptions, whose proof and/or thorough verification remains the topic of future work. In particular, the experimental evidence in Appendix C, while pertinent, _do not_ verify that these assumptions “hold in practice.” The key issue here is that a property can hold for random points with arbitrarily high probability and yet still fail for the points one cares about. For example, test and training losses at random points should always be close to each other (both “in practice” and provably), and yet for empirical risk minimizers these losses are often very different.

2. *Differentiability and continuity assumptions.* The main derivations in the paper are implicitly predicated on the notion that the confusion matrix is a differentiable (or at least continuous) function of the parameter $\mathbf{p}$. This might (or might not) hold when $Q_0$ has infinite support, but is never true when approximating it with a finite sample. The submitted manuscript tackles this issue in two ways (finite-difference gradient estimator and a smoothed objective), but the treatment comes too late to prevent confusion. To amend this, the following revisions are in order:

    * Clarify that the entire theoretical analysis is performed assuming full access to the population distribution $Q_0$, and the algorithmic issues of having a finite held-out set are dealt with subsequently and without theoretical guarantees.

     * In Theorem 1, assume explicitly that the confusion matrix is differentiable with respect to $f$. 

     * Similarly, in Theorem 2 and 3, assume explicitly that $L$ is finite. 
Decision: Accept (Poster)