Summary
This paper delves into the supervised and unsupervised online label shift problem, which focuses on adapting to changing class marginals using online data. The authors propose new algorithms that convert the adaptation problem into an online regression task, guaranteeing the minimax optimal dynamic regret. These methods leverage online regression oracles to track the shifting proportions. Evaluations of various online label shift scenarios show improved performances of the proposed methods.
Strengths
1. The manuscript is neatly structured and clearly drafted.
2. The authors have comprehensively explained both the problem setup and their proposed solutions.
3. The theoretical foundations elaborated in the manuscript appear to be solid. Importantly, the authors extend the concept of non-stationary online learning to scenarios encompassing non-convex loss functions, albeit under a Lipschitzness assumption. This extension significantly broadens the applicability of non-stationary online learning, notably in the context of neural networks or other sophisticated prediction models.
Weaknesses
While I am mainly positive about the paper. However, there remain some issues that may need to be further addressed for a more compelling submission:
1. The usage of the term "sample efficient" in both the abstract and experimental sections appears confusing to me. Sample efficiency is typically understood in a theoretical context. However, the proposed method does not theoretically demonstrate sample efficiency (consistent with previous methods). Moreover, the experiments merely evaluate the size of the hold-out offline labeled data, hardly serving as evidence for "sample efficiency." Consequently, the paper does not sufficiently convince me of this.
2. It is commendable that, unlike its predecessors, the proposed method does not hinge on the convexity of the functions (line 37). Nevertheless, given the importance of the Lipschitz constant in this paper, questions arise regarding the control of the Lipschitz constant G in complex models such as Deep Neural Networks (DNNs) and decision trees. For instance, decision trees, lacking continuity, presumably possess an infinite G.
3. In Theorem 6 (line 834), a simple union bound is utilized to derive the lower bound of the online label shift problem, resulting in a term $|\mathcal{H}|$ in the lower bound. Yet, can this bound accommodate complex scenarios where $\mathcal{H}$ is the DNNs or decision trees, given that $|\mathcal{H}|$ would be infinite in such instances?
4. Based on the points raised in Weaknesses 1, 2, and 3, the paper's title, "Online Label Shift: Optimal Dynamic Regret with Non-convex Implementation", appears somewhat overclaimed to me:
* In Remark 10, the authors acknowledge that Algorithm 4 necessitates storing and reprocessing all past data in each iteration, which contradicts the fundamental principles of online learning. Consequently, the term "Practical Algorithms" in the title seems overclaimed to me.
* A more fitting title, such as "Online Label Shift: Optimal Dynamic Regret with Non-convex Implementation," could be considered, given the paper's principal contribution lies in addressing non-convexity. Such a title could potentially draw more attention from readers.
5. The authors assert (line 55) that their approach achieves the best-of-both worlds of previous works. However, the meaning of "worlds" is unclear. Could the authors elucidate this further?
6. The theoretical exposition is presented in a complicated manner and is rather daunting to read. It would potentially be more friendly to a broader audience if the authors simplified and condensed the theoretical content.
7. Within the methodology section, the discrepancy between estimated and actual label marginals is converted into a 2-norm gap, which subsequent methods seek to optimize directly. However, in the context of label shift problems, is this direct optimization of the 2-norm (square loss) between distributions appropriate? Is the 2-norm excessively susceptible to out-of-distribution (OOD) data? Perhaps, alternative measures like KL-divergence or cross-entropy could be more suitable?
8. Some other relevant works related to online distribution shift should be considered to be explored and discussed, such as:
* Kumar et al., Understanding Self-Training for Gradual Domain Adaptation;
* Zhang et al., Adapting to Continuous Covariate Shift via Online Density Ratio Estimation;
* Zhou et al., Online Continual Adaptation with Active Self-Training.
9. I wonder what are the "NA"s mean in the experimental tables?
10. I am unsure about the FLH and Alligator algorithms (line 193). Could the authors briefly introduce these algorithms and explain their function?
11. line 196: The averaging within "intervals" xxx, can the author detail explain what the "intervals" is? and how to divide these intervals.
12. The paper can be further refined to enhance readability, and there are several typographical errors:
* line 31: Wu et al. [76] only controls -> Wu et al. [76] only control
* line 35: However their approach based on -> However, their approach is based on
* line 82: the extend of distribution drift -> the extent of distribution drift.
* line 94: i.e. -> i.e.,
* line 96: respectively -> , respectively
* line 314: i.e. -> i.e.,
* line 1055: $\alpha_t = 1-\alpha_{t-1}$.
* line 1079: to better performance -> to a better performance
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.
Limitations
As delineated in the Weakness section, the authors could provide a more detailed elucidation of the methodologies employed, and potentially consider revising the title to garner a broader impact. I am open to adjusting the evaluation score if the authors address my concerns.