Adapting to Continuous Covariate Shift via Online Density Ratio Estimation

Summary

This work introduced an online density ratio estimation method that can adaptively update the model to minimize the risk accumulated over time in the continuous covariate shift scenario. This method is able to estimate density ratios between test and training samples when the test set is varying over time. Only a few unlabeled samples are required at each time. A theoretical analysis of the regret bound of the density ratio estimator is provided.

Strengths

The paper is well written with clear justification and useful theoretical analysis. The proposed method relaxes the requirement of unbiasedness of prior work and does not need a large amount of unlabeled data at each time step. The authors also proved the dynamic regret bound of the density ratio estimator. The experiments demonstrate the effectiveness of the proposed method.

Weaknesses

I don't have many complaints about this paper. One weakness is that some important experimental results are in the appendix which is not reasonable as the appendix is optional to read by reviewers. I understand the page limitation but I would suggest moving some preliminary content to the appendix instead.

Questions

I understand covariate shift is a well-established research area but the assumption of covariate shift (p(y|x) not change) is quite strong, so how can we verify or guarantee this assumption is valid in a real-world problem?

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

3 good

Contribution

3 good

Limitations

Since this method is for continuous covariate shift, the inherent limitation would be the assumption of covariate shift.

Summary

This paper proposes an online density ratio estimation method to adaptively train a predictor in the scenario of continuous covariate shift. The proposed method estimates the density ratio between the training and testing distributions using a small number of unlabelled samples and updates the predictor using a weighted empirical risk minimisation algorithm. The paper provides a clear and comprehensive explanation of the problem of continuous covariate shift and the challenges it poses. The paper also provides a thorough review of related work and explains how the proposed method builds on and improves existing methods. The authors also give a dynamic regret bound, which finally leads to an excess risk guarantee for the predictor. The regret bound is minimised by designing an online optimisation process to minimise the dynamic regret defined over the observed loss. The paper explains how to optimise the dynamic regret with the online ensemble framework developed in recent studies of non-stationary online convex optimisation. The proposed method is validated through empirical results on synthetic and real-world datasets, demonstrating its effectiveness compared to other algorithms. Overall the paper appears technically sound, is easy to follow, and gives theoretical guarantees. The paper is less strong from the empirical perspective. Further, the setting is a little esoteric (offline training followed by online adaptation for models where density ratios can be used), and may be of limited appeal to a wider audience. ---- Post rebuttal increasing my score from 6 to 7

Strengths

Formulating the problem using the Bregman divergence was a useful tool to be able to generalise some existing methods, and also unlocked the analysis that follows. Disentangling the model training and importance weight estimation also allowed for adaptation to the continuous shift setting and abiility to change importance weight estimators.

Weaknesses

In terms of empirical study, this is limited to a study using synthetic data, and a small study on the yearbook dataset. For the synthetic scenario, the nature of the shift - sinusoidal and square waves altering a convex combination of distributions for the first two, then linear and “Ber” (which is not fully described in the main text, but is samples from a Bernoulli distribution) seem rather simplistic and artificial. For the single real world experiment, it’s not clear how the hyperparameter settings for the various methods were chosen, so it’s hard to know if this result is cherry-picked or robust. Another thing that’s not clear is whether the intervals chosen for the ensemble members match up with the period of change in the synthetic experiments. If they do, it’s not a surprise that they do well, but would require knowledge ahead of time. Figures 2-5 are extremely small and hard to read when printed.

Questions

How sensitive is the method to the intervals in the ensemble members? How crucial is the ensemble to the method overall? Am I right in thinking that the bound does not take account for the presence of the ensemble. Does this mean that the bound actually holds for the algorithm as employed in experiments? Could you plot the bound for one of the synthetic examples to show how tight it is?

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

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

3 good

Contribution

2 fair

Limitations

The authors did not address limitations or potential negative social impact.

Summary

This work studies the continuous covariate shift problem, where there exists an initial labelled dataset and in every subsequent round, a new unlabelled dataset is revealed. One needs to adapt the model for every round to achieve good performance. The paper uses importance-weighted ERM where the weights are estimated based on Bregman divergence minimization (Sec.3.3) and online ensemble (Sec.4.1). Theoretical analysis shows that the estimation has a linear dynamic regret (Theorem 2) and corresponding IWERM has an average excess risk that depends on problem instances (Theorem 3). Empirical studies on synthetic and real-world data show that the proposed method can outperform several alternatives.

Strengths

- Clear writing and easy-to-follow presentation - Strong theoretical guarantees on both the ratio function (Theorem 2) and the learned model (Theorem 3) - Convincing empirical demonstrations on both synthetic and real-world datasets

Weaknesses

- The algorithm and analysis rely on the assumption of using linear prediction models (see, e.g., Eq.(2) where the prediction is linear in w). Linear models are hardly sufficient in many cases, and more powerful models are needed. - The work of Baby et al (2023), albeit very recent, should be discussed as it achieves a similar bound to the current work in a different setting. - Baby, D., Garg, S., Yen, T.C., Balakrishnan, S., Lipton, Z.C. and Wang, Y.X., 2023. Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms. *arXiv preprint arXiv:2305.19570*. - A somewhat minor point to mention is that in the experiment, the description of the Yearbook dataset is not very clear. The appendix only mentions 10 images per round, but it remains unclear how the images are sequentially sampled. Some minor comments - R_t should be defined explicitly after Eq.(1) to avoid confusion (since it is the population version, different from (2), the empirical version) - L173: Ref [37] doesn’t mention UKL and ref [25] is KLIEP instead of KLLEP - L262: latter -> later - L305: minimiers -> minimizers - L336: KEIEP -> KLIEP

Questions

Q1: Are there any possible ways to extend the current work beyond linear models? Q2: How are the images being sampled for the Yearbook dataset?

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

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

4 excellent

Contribution

3 good

Limitations

The assumption of using linear models should be explicitly mentioned.

Summary

This paper focuses on deriving theoretical bounds for online density ratio when there exists continuous covariate shift. The formulation is based on the importance-weighted empirical risk minimization, which is a conventional one for covariate shift adaptation. The paper chooses the Bregman Divergence Density Ratio Matching as the method and tries to bound the regret of the to a dynamically changing optimal density ratio. The results are first established for a general convex function class and then instantiated to a logistic regression model. The online ensemble method proposed mimics the previous continuous label shift work. Experiments are conducted on four different synthetic shift patterns and mint/cifar datasets.

Strengths

Pro: The paper studies an important problem, is very clearly written, and has solid results.

Weaknesses

Con: I am not sure how much the first part of the analysis adds to our knowledge about the continuous covariate shift. This is maybe my bias. To my understanding, if we are in this kind of online learning scenario (shift is changing continuously), the minimization of the cumulative dynamic regret is a very straightforward choice. The question is how to minimize it and whether the theory guides the algorithm design. So, bounding the empirical estimation error using the approximated cumulated regret (theorem 1) is not very informative to me. Also, the paper shows that many density estimator function satisfies the assumption and can achieve the bounds. So the main novel part of the proposed methodology seems to be the twist to the FLH algorithm? Theoretically, even though it is nice to see a general and relatively standard algorithm can achieve the minimax optimal guarantee for the online density ratio estimation under continuous covariate shift, the theoretical contribution seems to be a bit limited: the high probability result (instead of the expected), and the greatly simplified analysis. The experimental results can be presented in a better way.

Questions

Questions: It would be nice to see different shift change patterns and how they affect the learning results. But it seems the errors are averaged before showing? Figure 2 only shows different methods but covers 4 kinds of shifts?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

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

3 good

Contribution

3 good

Limitations

There can be more discussions about limitations.