Summary
This paper investigates the problem of label shift in the online setting, where the data distributions vary in a non-stationary environment. Unlike the previous which focused on re-weighting the pretrained classifier or re-training the final linear layer of the classifier, this paper proposed to enhance the feature representation by leveraging the unlabeled data at test time. Specifically, a novel Online Label Shift (OLS) adaptation with Online Feature Updates (OFU), named OLS-OFU, was proposed by refining the feature extraction process through self-supervised learning (SSL). Theoretical analysis indicated that the proposed OLS-OFU could reduce the algoritmic regret by introducing the SSL. And the empirical results showed the effectiveness and the robustness of the proposed method under both the OLS setting and the online generalized label shift (OGLS) setting.
Strengths
1. The setting that this paper considered, online (generalized) label shift, is interesting and realistic in the practical scenarios. The investigation of the adaptation methods in such scenarios is valuable.
2. The method proposed in this work is simple. It can be flexibly combined with different existing online label shift adaptation methods, such as FLHFTL, ROGD, UOGD, etc.
3. Most parts of this paper are well-written and easy to follow.
Weaknesses
1. In my opinion, the motivation of introducing feature extraction refinement is not strong. In the Introduction part, the authors claimed that "feature extractors can still be improved, even during test-time and in the absence of labels". And the authors hypothesized that "a similar effect can be leveraged in the generalized label shift setting". However, I did not see strong relations between the drawbacks of the existing methods in this field and the lack of feature representation improvement.
2. The theoretical support in this work is not well verified by the empirical results. In Eq.(5) of the draft, the math showed that the online updates yield improvements. However, this point cannot be theoretically guaranteed. Furthermore, existing empirical results cannot reveal the relationship between the larger improvement and the better performance.
3. Some algorithmic steps are a little confusing for the readers.
See Questions part for more details.
Questions
1. About the motivation of introducing the feature refinement via self-supervised learning. I did not clearly get why we should focus on the feature improvement. For example, why did you believe the feature representation learning has not been enough in the existing methods? Why should we introduce the feature representation improvement, and is there any empirical support? If we cannot explain this point, introducing self-supervised learning just looks like a naive combination of the online label shift adaptation with the popular topic, self-supervised learning.
2. About the theoretical analysis in Eq. (5). I believe that the motivation of introducing the online feature updates comes from the assumption in this inequality. 5And the authors tried to provide empirical evaluations in Sec. 4 (and Appendix D.6) to verify the holdness of this inequality. However, there is no further demonstrations of the quantitative relationship between the amount of feature representation refinement (or in other words the tightness of Eq. (5)) and the final performance. I will describe my question in the mathematical way:
Suppose $\mathcal{M}$ denote the OLS methods (e.g., $\mathcal{M}\in${FLHFTL, FTH, ROGD,...}). Take $\mathcal{M}=$FLHFTL as an example.
Let
$$X^{\mathcal{M}}=\mathbb{E}[ \frac{1}{T} \Sigma_{t=1}^{T}\ell(f_{t}^{\mathcal{M}-ofu}; \mathcal{P}_{t}^{test})]$$
$$Y=\mathbb{E}[ \frac{1}{T} \Sigma_{t=1}^{T}\ell(g(\cdot; f_{t}^{\prime\prime}, q_t/q_0); \mathcal{P}_{t}^{test})]$$
and
$$Z=\frac{1}{T} \Sigma_{t=1}^{T}\ell(g(\cdot; f_{0}, q_t/q_0); \mathcal{P}_{t}^{test})$$
According to [1], Then, the Eq.(3) can be rewrote as
$$ X^{\mathcal{M}} - Y \leq \mathcal{O}(\frac{K^{1/6}V_{T}^{1/3}}{\sigma^{2/3}T^{1/3}} + \frac{K}{\sigma \sqrt{T}})$$
If we define $\Delta = Z- Y$ as **the amount of improvement** ($\Delta \geq 0$ if we admit Eq. (5)).
Then, introducing feature update can make the original bound in Eq. (4) tighter by $\Delta$:
$$X^{\mathcal{M}} - Z \leq \mathcal{O}(\frac{K^{1/6}V_{T}^{1/3}}{\sigma^{2/3}T^{1/3}} + \frac{K}{\sigma \sqrt{T}}) - \Delta$$
The larger improvement we make by feature update (in other words larger $\Delta$), the tighter bound we can derive from the original version.
Thus, my question is: **could you please verify this point with empirical results to support your motivation in Eq. (5) in a quantitative manner?** Maybe we can fix an OLS method $\mathcal{M}$, and then choose different ways to obtain $f_{t}^{\prime\prime}$ (e.g., different $\ell_{ssl}$), then give a quantitative measure on the loss of $\mathcal{M}$-OFU (i.e., $X^{\mathcal{M}}$ defined above) with respect to the value of $\Delta$?
3. It seems the organization of the descriptions in Algorithm 1&2 is a little confusing and make the core steps of your methods less readable. For example, if we start Algorithm 1 from $t=1$, the step-1 of Algorithm 1 aims to return $f_{2}^{\prime} \leftarrow \textit{OLS-R}$. However, in the details of this step shown in Algorithm 2, it seems we need $f_{1}^{\prime\prime}$ returned by the step-3 of Algorithm of the previous loop. I failed to get what is the exact definition of $f_{1}^{\prime\prime}$.
References:
[1] Online label shift: Optimal dynamic regret meets practical algorithms. NeurIPS 2023.
Rating
5: marginally below the acceptance threshold
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.