Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms
Authors: Dheeraj Baby
Saurabh Garg
Tzu-Ching Yen
Sivaraman Balakrishnan
Zachary Chase Lipton
Yu-Xiang Wang
Venue: NeurIPS 2023 spotlight (2023)
Keywords: online learning
label shift
distribution shift
unsupervised domain adaptation
TL;DR: In this work, we focused on unsupervised and supervised online label shift settings. For both settings, we developed algorithms with minimax optimal dynamic regret. Experimental results on numerous datasets highlight the effectiveness of our methods.

Abstract: This paper focuses on supervised and unsupervised online label shift,
where the class marginals $Q(y)$ varies
but the class-conditionals $Q(x|y)$ remain invariant. In the unsupervised setting, our goal is to adapt a learner, trained on some offline labeled data, to changing label distributions given unlabeled online data. In the supervised setting, we must both learn a classifier and adapt to the dynamically evolving class marginals given only labeled online data. We develop novel algorithms that reduce the adaptation problem to online regression and guarantee optimal dynamic regret without any prior knowledge of the extent of drift in the label distribution. Our solution is based on bootstrapping the estimates of *online regression oracles* that track the drifting proportions. Experiments across numerous simulated and real-world online label shift scenarios demonstrate the superior performance of our proposed approaches, often achieving 1-3% improvement in accuracy while being sample and computationally efficient. Code is publicly available at https://github.com/Anon-djiwh/OnlineLabelShift

Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms
Dheeraj Baby" UC Santa Barbara Sheeraj@uusb.ede
Saurabh Garg" Carnegie Mellon University sgarg2 @ andrew.cmu.ed
Tzu-Ching Yen Carnegie Mellon University tzuchiny euuurew.cmu.edu
Sivaraman Balakrishnan
Zachary C. Lipton
Yu-Xiang Wang UC Santa Barbara yuxiangw cww.ingwwws..uu...e..
Carnegie Mellon University
Carnegie Mellon University zlipton andrew.cmu.edu
sbalakri andrew.cmu.edu
Abstract
This paper focuses on supervised and unsupervised online label shift, where the class marginals Qιy) varies but the class-conditionals Q<>lyy) remain invariant. In the unsupervised setting, our goal is to adapt a learner, trained on some offline la- beled data, changing label distributions given unlabeled online data. In the super- vised setting, we must both learn a classifier and adapt to the dynamically evolving class marginals given only labeled online data. We develop novel algorithms that reduce the adaptation problem to online regression and guarantee optimal dynamic regret without any prior knowledge the extent of drift in the label distribution. Our solution is based on bootstrapping the estimates of online regression orucles that track the drifting proportions. Experiments across numerous simulated and real-world online label shift scenarios demonstrate the superior performance of our proposed approaches, often achieving 1-3% improvement accuracy while being sample and computationally efficient. Code is publicly available at this url.
Introduction
Supervised machine learning algorithms typically developed assuming independent and identically distributed (iid) data. However, real-world environments evolve dynamically [55, 67, 46, 29]. Absent further assumptions on the nature of the shift, such problems are intractable. One line of research has explored causal structures such covariate shift [64], label shift [61, 51], and missingness shift [86], for which the optimal target predictor identified from labeled source and unlabeled target data, Let's denote the feature-label pair of an example by (x. y). Label shift addresses the setting where the label marginal distribution (yy may change but the conditional distribution Q(xly) remains fixed. Most prior work addresses the batch setting for unsupervised adaptation, where single shift occurs between source and target population 51, 1, 2, 1, 26]. However, in the real world, shifts more likely occur continually and unpredictably, with data arriving in an online fashion. A nascent line of research tackles online distribution shift, typically in settings where labeled data available in real time [4], seeking to minimize the dynamic regret.
Researchers have only begun to explore the role that structures like label shift might play in such online settings. Initial attempts to learn under unsupervised online label shifts were made by Wu et al. [76] and Bai al. [8], both of which rely on reductions to Online Convex Optimization (OCO) [37, 54]. This line of research aims in updating classification model based on online data so that the overall regret is controlled. However, Wu al. [76] only control for statie regret against fixed
"Equal Contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Nature
offline data ((, ~ Qolrty)Qolo)
(sx, Qa(za la (+)
model
UOLS and SOLS setup. Dashed (double) arrows are exclusive to UOLS (SOLS) settings. Other objects are common to both setups. Central question: how to adapt the model in real-time to drifting label marginals based on all the available data so far?
Figure 1:
classifier (or model) in hindsight and makes the assumption of the convexity (of losses), which often violated in practice. In the face of online label shift, where the class marginals can vary across rounds, more fitting notion is to control the dynamic regret against a sequence of models in hindsight. Motivated by this observation, Bai et al. [8] control for the dynamic regret. However, their approach is based on updating model parameters (of the classifier) with online gradient descent and relying on convex losses limits the applicability of their methods (e.g. algorithms in Bai al. [8] can not be employed with decision tree classifiers).
In this paper, we study the problem of learning classifiers under Online Label Shift (OLS) in both supervised and unsupervised settings (Fig. In both these settings, the distribution shifts are an online process that respects the label shift assumption. Our primary goal step convexity assumptions and at the same time optimally adapt to the non-stationarity in the label drift. In the Unsupervised Online Label Shift (UOLS) problem, the learner is provided with a pool of labeled offline data sampled iid from the distribution Qo y) to train an initial model fo- Afterwards, at every online round f, few unlabeled data points sampled from (x) are presented. The goal is to adapt fo to the non -oa-stationary target distributions Q y) so that we can accurately classify the unlabelled data. By contrast, in Supervised Online Label Shift (SOLS), our goal is to learn classifiers from only the (labeled) samples that arrive in an online fashion from Qr y) at each time step, while simultaneously adapting to the non-stationarity induced due to changing label proportions. While SOLS is similar to online learning under non- non-stationarity. UOLS differs from classical online learning as the test label is not seen during online adaptation. Below are the list of contributions of this paper.
develop algorithms that side-
Unsupervised adaptation. For the UOLS problem, we provide a reduction online regression (see Defn. 1), and develop algorithms for adapting the initial classifier fo in a computationally efficient way leading to minimax optimal dynamic regret. Our approach achieves the best-of- both worlds of Wu et al. [76]. Bai et al. [8] by controlling the dynamic regret while allowing us to use expressive black-box models for classification (Sec. 3).
Supervised adaptation. We develop algorithms for SOLS problem that lead to minimax optimal dynamic regret without assuming convexity of losses (Sec. 4). Our theoretically optimal solution is based on weighted Empirical Risk Minimization (wERM) with weights tracked by online regression. Motivated by our theory, we also propose simple continual learning baseline which achieves empirical performance competitive to the WERM from scratch at each time step across several semi-synthetic SOLS problems while being 15x more efficient in computation cost.
Low switching regressors. We propose a black-box reduction method to convert an optimal online regression algorithm into another algorithm that switches decisions sparingly while maintaining minimax optimality. This method relevant for online change point detection. We demonstrate its application in developing SOLS algorithms to train models only when significant distribution drift is detected, while maintaining statistical optimality (App. D and Algorithm 6).
Extensive empirical study. We corroborate our theoretical findings with experiments across numerous simulated and real-world OLS scenarios spanning vision and language datasets (Sec. 5). Our proposed algorithms often improve over the best alternatives in terms of both final accuracy and label marginal estimation. This advantage is particularly prominent with limited initial holdout data (in the UOLS problem) highlighting the sample efficiency of our approach.
Notes on technical novelties. Even-though online regression is a well studied technique, to the best of our knowledge, it is not used before to address the problem of online label shift. It is precisely the usage of regression which lead to tractable adaptation algorithms while side-stepping convexity assumptions thereby allowing us to very flexible models for classification. This is in stark contrast

---

to OCO based reductions in [76] and [8]. We propose new theoretical frameworks and identify the right set of assumptions for materializing the reduction to online regression. It was not evident initially that this link would lead to minimax optimal dynamic regret rates as well as consistent empirical improvement over prior works. Proof of the lower bounds requires adapting the ideas from non-stationary stochastic optimization [10] in non-trivial manner. Further, none of the proposed methods require the prior knowledge of the extent of distribution drift.
2 Problem Setup
Let X' S Rd be the input space and y = [K] == (1.2...., K be the output space. Let Q be distribution over X' x y and let q() denotes the corresponding label marginal. Á is the K- dimensional simplex. For vector E RK x(i] is its 2th coordinate. We assume that we have hypothesis class H. For a function f E H: X - Ak. we also use f(ilz) to indicate ff fxx) With ((f(x), y). we denote the loss of making a prediction with the classifier on (z, L denotes the expected loss, i.e., L E( (x()(x), v)]- Ō()) hides dependencies in absolute constants and poly-logarithmic factors of horizon and failure probabilities.
In this work, we study online learning under distribution shift, where the distribution Qe y) may continuously change with time. Throughout the paper, we focus on the label shift assumption where the distribution over label proportions q: (y) can change arbitrarily but the distribution of the covariate conditioned on a label value (i.e., Qe [z] yy) is assumed to be invariant across all time steps. We Online Label Shift (OLS). Here, we consider settings of unsupervised and
refer to this setting supervised OLS settings captured in Frameworks and respectively. In both settings, at round a sample (Ie, ys) ) is drawn from distribution with density (x1,, ye). In the UOLS setting, the label is not revealed to the learner. However, we assume access to offline labeled data sampled iid from Qo which we use train initial classifier fo- The goal is adapt the initial classifier So drifting label distributions. In contrast, for the SOLS setting, the label is revealed to the learner after making prediction and the goal is to learn classifier f. H. for each time step.
Next, we formally define the concept of online regression which will be central to our discussions. Simply put, an online regression algorithm tracks ground truth sequence from noisy observations. Definition 1 (online regression). Fix any T > O. The following interaction scheme is defined to be the online regression protocol.
At round E [T], an algorithm predicts Ô. E R
A noisy version of ground truth = Og + E is revealed where O,, E IR and |exl12, [10 I|255 B. Further the noise Et are independent across time with Elec] and Var(e((i)) S o² Lo2Vi [K].
An online regression algorithm aims to control Ei=110,- 0el12. Moreover, the regression algorithm is defined be adaptively minimax optimal with probability least 8. Σim 110 0, l12
/3 22/3) without knowing Vr ahead of time. Here Vr Et=el10, -b-1 11 is termed as the Total Variation (TV) of the sequence (UT
3 Unsupervised Online Label Shift
In this section, we develop a framework for handling the UOLS problem. We summarize the setup in Framework 1. Since in practice, we may need to work with classifiers such as deep neural networks or decision trees, we do not impose convexity assumptions on the (population) loss of the classifier as function of the model parameters. Despite the absence of such simplifying assumptions, we provide performance guarantees for our label shift adaption techniques so that they are certified to be fail-safe.
Under the label shift assumption, we have Q+(vlz) as re-weighted version of Qo(y]z);
Qr(v) Qx(x) Qe(xlv) Qr(y) Qo(2l1) - Q.(x) (o()) Qo(ula) Qo(r)Q((v)
Qi(v)
Qx(1)=)
Qo(v) Qu(slæ),
where the second equality is due to the label shift assumption. Hence, a reasonable strategy is to re- weight the initial classifier fo with label proportions (estimate) at the current step, since we only have to correct the label distribution shift. This weightntt technique is widely used for offline label shift correction [51, 2, 1] and for learning under label imbalance [41, 74, 18).
3

---

Framework 1 Unsupervised Online Label Shift (UOLS) protocol
Algorithm 2 RegressAnddexeiihht to handle
UOLS
Input: i) Online regression oracle ALG; ii) Ini- tial classifier fu: iii) The confusion matrix C; iv) The label marginal qu E 'D of the training distri- bution;
Input: Initial classifier fo : X + Ax trained on offline labeled dataset {(2; 1 sampled iid from Qo:
1: fi fo
1: At round t. get the classifier covariate It.
2: for each round E [T] do
2: Let &
1D (ALG(51:-1)), where [m(()) = argmin yen 2122-
3: Nature samples I; E X' and ye E V. with
(1r, ~ Qii Only z, is revealed to the
3: Sample label i with probability x (.(1)
learner.
4: Learner predicts label i f((2)) E AK.
@ati) Jo((
5: f411 = A(fo, #1:e), where A is strategy to adapt the classifier based past data.
4: Let 82 Co-re()))
5: Update the online regression oracle with the estimate St-
6: end for
Our starting point in developing a framework is inspired by Wu et al. [76], Bai al. [8] For self- containedness, we briefly recap their arguments next. We refer interested readers to their papers for more details. Wu al. [76] considers a hypothesis class of re- weighted initial classifier fo- The loss of a hypothesis is parameterised by the re- re-weighting vector. They use tools from OCO to optimise the loss and converge to best fixed classifier. However as noted in Wu al. [76], the losses not convex with respect to the re-weight vector in practice. Hence usage of OCO techniques is not fully satisfactory in their problem formulation.
In a complementary direction, Bai et al. [8] abandons the idea of re- weightitg Instead, they update the parameters of model at each round using online gradient descent and loss function whose expected value is assumed to be convex with respect to model parameters. They provide dynamic regret guarantees against a sequence of changing model parameters in hindsight, and connects it to the variation of the true label marginals. More precisely, they provide algorithms with Σ (ww) (ww]) to be well controlled where w/ is the best model parameter to be used at round f and L, is a (population level) loss function. However, there are some scopes for improvement in this direction as well. For example, the convexity assumption can be easily violated when working with interpretable models based on decision trees, or if we want to retrain few final layers of deep classifier based on new data. Further as noted in the experiments (Sec. 5), their methods based on retraining the classifier require more data than re- weighting based methods. Our experiments also indicate that weightiting can be computationally cheaper than re-training without sacrificing the classifier accuracy.
Thus, on the one hand, the work of Wu al. [76] allows to use the power of expressive initial classifiers while only controlling the static regret against a fixed hypothesis. On the other hand, the work of Bai al. [8] allows controlling the dynamic regret while limiting the flexibility of deployed models. We next provide our framework for handling label shifts that achieves the best of both worlds by controlling the dynamic regret while allowing the use of expressive blackhox models.
In summary, we estimate the sequence of online label marginals and leverage the idea of re- weightiig an initial classifier in Wu et al. [76]. In particular, given an estimate qi (v) of the true label marginal at round we compute the output the re-weighted classifier f. as 1ato7 folul=)/2 where ((())
Øsly)
2 2= E,
goly) fo(y/ar). However, to get around the issue of non-convexity, we separate out the
process of estimating the re-weighting vectors via a reduction to online regression which is well- defined and convex problem with computationally efficient off- off-the-shelf algorithms readily available. Second, and more importantly, Wu et al. [76] competes with the best fixed re- re-weighted hypothesis. However, in the problem setting of label shift, the true label marginals are in fact changing. Hence, we control the dynamic regret against a sequence of re-weighted hypotheses in hindsight. All proofs for the next sub-section are deferred to App. C.
3.1 Proposed algorithm and performance guarantees
We start by presenting our assumptions. This is followed by the main algorithm for UOLS and its performance guarantees. Similar to the treatment in Bai et al. [8], we assume the following.

---

Assumption 1. Assume access to the true label marginals go E AK of the offline training data and the true confusion matrix C E R with Cj₃ singular value minn (C) = (1) is bounded away from zero.
Further the minimum
As noted in prior work [51, 26], the invertibility of the confusion matrix holds whenever the classifier fo has good accuracy and the true label marginal to assigns non-zero probability each label. Though we assume perfect knowledge of the label marginals of the training data and the associated confusion matrix, this restriction can be easily relaxed to their empirical counterparts computable from the training data. The finite sample error between the empirical and population quantities can be bounded by O (1//VN) where N is the number of initial training data samples. To this end, we operate in the regime where the time horizon obeys T = (VNN.. However, similar to Bai et al. [8], we make this assumption mainly to simplify presentation without trivializing any aspect of the OLS problem.
Next, we present our assumptions on the loss function. Let p E Ak- Consider a classifier that predicts a label (()),, by sampling (1x) according to the distribution that assigns weight p(i)
qo So((jar) to the label Define (p) be any non-negative loss that ascertains the quality of the marginal p. For example, (p) = E [(((((z) y.]]] where the expectation is taken wIt the randomness in the draw (x.,) v) ~ Qt and in sampling (()). Here is any classification loss (e.g. 0-1, cross-entropy).
Assumption 2 (Lipschitzness of loss functions). Let D be a compact and convex domain. Assume that (p) is G Lipschitz with p E D _ Ak. i.e, L,(p1) - L((2)) S Gllp1 - -p2ll2 any P1. P2 E D. The constant G need not be known ahead of time.
We show in Lemmas 11 and 12 that the above assumption is satisfied under mild regularity conditions. Furthermore, the prior works such as Wu et al. [76] and Bai et al. [8] also require that losses are Lipschitz with known Lipschitz constant apriori to set the step sizes for their OGD based methods.
The main goal here is to design appropriate re-weighting estimates such that the dynamic regret:
T Gll. - gell2
Raynamic (T) = Σ -
S
is controlled where d E Ax is the estimate of the true label marginal q:- Thus we have reduced the problem of handling OLS to the problem of online estimation of the true label marginals.
Under label shift, we can get an unbiased estimate of the true marginals at any round via the techniques in Lipton et al. [51], Azizzadenesheli et al. [2], Alexandari et al. [1]. More precisely, 8: C-1 (o(rr) has the property that E[se] qt (see Lemma 15). Further, the variance of the estimate 8, is bounded by 1/o min (C). Unfortunately, these unbiased estimates can not be directly used to track the moving
marginals q: This is because the total squared error ΣT E[l - q: [ grows linearly in T as the sum of the variance of the point-wise estimates accumulates unfavorably over time.
To get around these issues, one can use online regression algorithms such as FLH [38] with online averaging base learners or the Aligator algorithm [7]. These algorithms use ensemble methods to (roughly) output running averages of 8 where the variation in the true label marginals is small enough. The averaging within intervals where the true marginals change slowly helps to reduce the overall variance while injecting only a small bias. We use such online regression oracles to track the moving marginals and re-calibrate the initial classifier. Overall, Algorithm 2 summarizes our method which has the following performance guarantee.
Theorem 2. Suppose we run Algorithm 2 with the online regression oracle ALG as FLH-FTL F) or Aligator [7]. Then under Assumptions I and 2, we have
Rayyyaaiic (T)) = :0(
K / T
VKT
2/3 mmn (C)
Imin (C)
where Vr := ET qu-1l1 and the expectation is taken with respect to randomness in the revealed co-variates. Further, this result is attained without prior knowledge of Vr.
Remark 3. We emphasize that any valid online regression oracle ALG can be plugged into Algorithm 2. This implies that one can even use consformer-busee time series models to track the moving marginals qr. Further, we have the flexibility of choosing the initial classifier to be any black-box model that outputs a distribution over the labels.
5

---

Framework 3 Supervised Online Label Shift (SOLS) protocol
Algorithm 4 TrainByweights to handle SOLS
input hypothesis class H.
input Online regression oracle ALG, hypothesis class H At round f E [T], get estimated label marginal t: from ALG((11:-1). 2: Update the hypothesis with weighted ERM:
1: for each round E [T] do
2: Nature samples N iid data points 21,1:N E X' and 11,1:N E 3, with each (It,á: Mt.s) ~ Qti 21,1:N revealed to the learner.
go(ui.s) (f(aa)))) (2) (.((.)))
3: For each E [M], learner predicts label fz
ft argmin
SEN
4: The label Yt,i E y for each E
3: Get co- ca-vatiates F1,1:N and make predictions with
[N] is revealed.
4: Get labels Ur,1:N
5: Se+1
A(fe: 1: VI.,1:N)) where algorithm A updates the classifier with past data.
5: Compute seli]
N E== Hyn. i} for all
[K].
6: Update ALG with the empirical label marginals 8t-
6: end for
Remark Unlike prior works such as [76, 8), we do not need a pre-specified bound on the gradient of the losses. Consequently Eq.(1) holds for the smallest value of the Lipschitzness coefficient G, leading to tight regret bounds. Further, the projection step in Line 2 of Algorithm done only to safeguard our theory against pathological scenarios with unbounded Lipschitz constant for losses. In our experiments, we do not perform such projections.
We next show that the performance guarantee in Theorem is optimal (modulo factors of log T') in minimax sense.
Theorem 5. Let VT S 64T. There exists a loss function, a domain 'D (in Assumption 2), and choice of adversarial strategy for generating the data such that for any algorithm, we have EL E([L,(â)] - Le(gt)) = Ω (max(T2/3 :VT;) wwhere qe E 'D is the weight estimated by the algorithm and qe E D is the label marginal at round t chosen by the adversary. Here the expectation is taken with respect to the randomness in the algorithm and the adversary.
4 Supervised Online Label Shift
In this section, focus the SOLS problem where the labels are revealed to the learner after it makes decisions. Framework summarizes our setup. Let ft := argmin (f( be the population minimiser. We aim control the dynamic regret against the best sequence of hypotheses in hindsight:
Mynamic (T) =:
- -
(3)
the SOLS problem is convex, it reduces to OCO [37, 54] and existing works provide 0 dynamic regret guarantees [82]. However, in practice, since loss functions seldom convex with respect to model parameters modern machine learning, the performance bounds OCO algorithms cease to hold true. In work, extend the generalization guarantees of ERM from statistical learning theory [11] to the SOLS problem. All proof's of next sub-section are deferred to App. E.
4.1 Proposed algorithms and performance guarantees
We start by providing a simple initial algorithm whose computational complexity and flexibility will be improved later. Note that due to the label shift assumption, for any j. E [T], we have E(z,)) [((f(z), y)] = E(an))
Here assume that the true label marginals (v(v) > 0 for all / E [T] and all E [K]. Based on this, we propose simple weighted ERM approach (Algorithm 4) where we use an online regression oracle to estimate the label marginals from the (noisy) empirical label marginals computed with observed labeled data. With weighted
9e(v) {(f(x).
9, (9)

---

ERM and plug-in estimates of importance weights, we can obtain our classifier ft. One can expect that by adequately choosing the online regression oracle ALG, the risk of the hypothesis fo computed will be close to that of J Here the degree of closeness will also depend on the number of data points seen thus far. Consequently, Algorithm controls the dynamic regret (Fq.(3) in a graceful manner. We have the following performance guarantee:
Theorem 6. Suppose the true label marginal satisfies ming, (e(k) 2 1 > O. Choose the online regression oracle in Algorithm 4 as FLH--TL, (App. F) Aligator from Baby et al. [7] with its predictions clipped such that qe [k] 2 p. Then with probability at least 1 - 6, Algorithm 4 produces hypotheses with B dynomic = Ô T2/3 + log (H|/)) where VT = Σi= 11q - 4t-
Further, this result is atlained without any prior knowledge of the variation budget VT-
The above rate contains the sum of two terms. The second term is the familiar rate seen in the supervised statistical learning theory literature under iid data [11]. The first term reflects the price we pay for adapting to distributional drift in the label marginals. While we prove this result for finite hypothesis sets, the extension to infinite sets is direct by standard covering net arguments [70].
Remark 7. Theorem 6 requires that the estimates of the label marginals to be clipped from below by μ.. This is done only to facilitate theoretical guarantees by enforcing that the importance weights used in (2) do not become unbounded. However, note that only the labels we actually observe enters the objective in (2). In particular, if a label has very low probability of getting sampled at round, then it is unlikely that it enters the objective. Due to this reason, in our experiments, we haven't used the clipping operation (see Section 5 and Appendix F for more details).
The proof of the theorem uses concentration arguments to establish that the risk of the hypothesis fe is close to the risk of the optimal fi, However, unlike the standard offline supervised setting with iid data, for any fixed hypothesis, the terms in the summation of Eq.(2) are correlated through the estimates of the online regression oracle. We handle by introducing uncorrelated surrogate random variables and bounding the associated discrepancy. Next, we show (near) minimax optimality of the guarantee in Theorem 6.
Theorem 8. Let Vr S T/8. There exists choice of hypothesis class, loss function, and adversarial strategy of generating the data such that Raymamic Ω (T2/s/>// + (Toog(Hl)) where the expectation is taken with respect to randomness in the algorithm and adversary.
Remark Though the rates in Theorems 5 and 8 are similar, we note that the corresponding regret definitions are different. Hence the minimax rates are not directly comparable between the supervised and unsupervised settings.
Even-though Algorithm 4 has attractive performance guarantees, it requires retraining with weighted ERM at every round. This can be computationally expensive. To alleviate this issue, we design a new online change point detection algorithm (A (Algorithm 5 in App. D) that can adaptively discover time intervals where the label marginals change slow enough. We show that the new online change point detection algorithm can be used to significantly reduce the number of retraining steps without sacrificing statistical efficiency (up to constants). Due to space constraints, we defer the exact details to App. D. We remark that our change point detection algorithm is applicable to general online regression problems and hence can be of independent interest to online learning community.
Remark 10. Algorithm 5 helps reduce the run-time complexity. However, both Algorithums 4 and 5 have the drawback of storing all data points accumulated over the online rounds. This is reminiscent to FTL/ FTRL type algorithms from online learning. We leave the task of deriving theoretical guarantees with reduced storage complexity under non-convex losses as an important future direction.
5
Experiments
5.1 UOLS Setup and Results
Following the dataset setup of Bai et al. [8], we conducted experiments on synthetic and common benchmark data such as MNIST [50], CIFAR-10 [49], Fashion [77], EuroSAT [40], Arxiv [15], and SHL. [31, 71]. For each dataset, the original data is split into labeled data available
Setup
"Code is publicly available https: :/tp:://ee //ggthub....tttt// http://gttbcc.////aaa/eeee witpandddiih//lnnneneee htwp:////onneeeaeeeleeftte.
7

---

0.17
R- Imon
800
#CCIpPing
0.16
Meen Scquete troe
0.25
0.92
0.15
6:20
6.88
0.14
0.86
0.13
0.84
0.12
10a
10a
Number Holdout Data
Number Nodcout Data
1000
ATLAS
ROG0
FUNFFI
(b)
Figure 2: Results the UOLS problem. (a) and (b): Ablation on CIFAR 10 with monotone shift over sizes of holdout data used to update model parameters and compute confusion matrix, with amount of training data held fixed. FLH-FTL (ours) outperforms all other alternatives throughout in classification eтrоr and mean square error label marginal estimation. Unlike the alternatives, the performance of FLH-FTL (ours) is unaffected by the decrease in amount of holdout data. (c): CIFAR 10 results with monotone shift using varying amount training data, with the remaining labeled data used as holdout (total number of samples fixed to 50k). The performance of FLH-FTL minimally impacted by the reduction the quantity of holdout data, thus yielding the greatest ad advantage from utilizing larger volume of training data.
Methods
Synthetic
MNIST
CIFAR
EaroSAT
Fashion
ArXiv
Ber
Sin
Ber
Sin
Ber
Ber
Sin
Ber
Sin
Ber
Base
8.6_.aa
8.210a
4.9.0..
3.91m
16.1
16.0
13.0
13.1
15.0
15.0
2311
1918
OFC
6.4g
5.5
4.410.
3.2108
12:1
11:3
10:3
7.0.01
7.1.0.1
20
Oracle
3.7
3.9
2.5
1.5tma
5.480.
5.8
3.9.0.3
4.149.1
3.750.2
3.6m0.1
7.7=1.
5.1
FTH
6.5m0.6
5,7+0.a
4.5+0..
3.3-0.2
11#0
11t0
10-0
9.6-o.0
8.5+0.3
6.9+o.4
20e1
14:0
FIFWH
6.0.0.
5.740.a
4.5ee..
3.3-0.a
11#1
11#0
9.8+0.4
9.6=0.1
8.2e0.0
6.9e0.4
20
14s0
ROGD
7.9
7.2+0.6
0.2
4/E1.
16as
14=1
13#1
8.2=0.7
23=2
UOGD
8.1.
7.5
5.4a0.
4.0gm.0
1449
14a1
10
9.8
11:9
11sa
21
17
ATL.AS
8.0
7.5g0e
5.22..6
3.7ana
1349
13ar
10
9.92..7
12
12sa
21
1620
FL.H.FTI (ours)
5.410.7
5.41na
4.410.7
3.3.0
10.0
9.2
9.6_..1
7.7.0.4
7.0_..0
19
14.0
Synthetic
MNIST
CIFAR
EurSATT
Fashion
ArXiv
Ber
Sin
Ber
Sin
Ber
Sin
Ber
Sin
Ber
Sin
Ber
Sin
FTH
0.14gs.0
0.27a0m
0.142om:
FTTWI]
0.13
0,25
ROGD
0.29
0.24:mo
0.41200s
0.37
0.30
0.30caat
0.40ea0s
0.35
0.37.000
0.30zam: 0.36:aas
0.28.am
FLIHFTL (ours)
0.10 0.08:0.00 0.13:am
0.12:0000 0.17:am 0.13an00 0.1610.0: 0.13:000 0.18:0.22
0.14:am:
0.23:0ox 0.15:10.0
Table 1: Results for UOLS problems under sinusoidal (Sin) and Bernoulli (Ber) shifts. Top: Classification Error. Bottom: Mean-squared error in estimating label marginal. For both, lower better. Across all datasets, we observe that FLH-FTL (ours) often improves over best alternatives.
during offline training and validation, and the unlabeled data that we observe during online learning. We experiment with varying sizes of holdout offline data which is used obtain the confusion matrix and update the model parameters to adapt to OLS to probe the sample efficiency of all the methods. In contrast to previous works [8, 76], we have chosen to use a smaller amount of holdout offline data for our main experiments. We made this decision because the standard practice for deployment involves training and validating models on training and holdout splits, respectively (e.g.. with k-fold cross-validation). Then, the final model is deployed by training on all available data (i.e., the union of train and holdout) with the identified hyperparameters. However, to employ UOLS techniques in practice, practitioners must hold our data that was not seen during training to update the model during online adaptation. Therefore, methods that are efficient with respect to the amount of offline holdout data required might be preferable.
8

---

FLH--FLL
CT (base)
CT-RS (ours)
CT-RS (ours)
w-ERM (oracle)
Base Oracle ROGD
FTH FTFWH
(ours)
w FTH
FLH--FL
CI Err 1821 6.3 1923
14+2
14=2
13:2
CI Err 20.0
18.3820.4
17.12:0.
16.32_o.7
MSE NA 0.020.0 0.3 0.3
0.3z0.0
0.2.0.0
MSE
NA
0.18
0.12_0.01
NA
Table 2: Results with a Random Forest classi- fier on MNIST dataset. Note that methods that update model parameters are not applicable here. FLH-FTL outperforms existing alternatives for both accuracy and label marginal estimation.
Table 3:
Results on SOLS setup on CIFARIO SOLS with Bernoulli shift. CT with RS improves over the base model (CT) and achieves competi- tive performance with respect to weighted ERM oracle. MNIST results are similar (see App. F).
For all datasets except SHI., we simulate online label shifts with four types of shifts studied in Bai et al. [8]: monotone shift, square shift, sinusoidal shift, and Bernoulli shift. For SHL locomotion, use the real-world shift occurring over time. For architectures, we use an MLP for Fashion, SHL and MNIST, Resnets [39] for EuroSAT, CINIC, and CIFAR, and DistilBERT [62. 75] based models for arXiv. For alternate approaches, along with a base classifier (which does no adaptation) and oracle classifier (which reweight using the true label marginals), we make comparisons with adaptation algorithms proposed in prior works 176, 8]. In particular, we compare with ROGD, FTH, FTFWH from Wu al. [76] and UOGD, ATLAS from Bai et al. [8]. For brevity, we refer to our method as FLH-FTL (though strictly speaking, our methods are based on FLH from Hazan and Seshadhri [38] with online averages as base learners). We run all the online label shift experiments with the time horizon T = 1000 and at each step 10 samples are revealed. We repeat all experiments with 3 seeds to obtain means and standard deviations of the results. For other methods that perform re- weighting correction softmax predictions, we use the labeled holdout data to calibrate the model with temperature scaling, which tunes one temperature parameter [35]. We provide exact details about the datasets, label shift simulations, models, and prior methods in App. F.
Results Overall, across all datasets, we observe that our method FLH-FTL performs better than alternative approaches in terms of both classification error and mean squared error for estimating the label marginal. Note that methods that directly update the model parameters (i.c., UOGD, ATLAS) do not provide any estimate of the label marginal (Table 1). UOGD and ATLAS also require offline holdout labeled data (i.e., from time step 0) to make online updates to the model parameters. For this purpose, we use the same labeled data that we use to compute the confusion matrix.
As we increase the holdout offline labeled dataset size for updating the model parameters (and to compute the confusion matrix), we observe that classification error and MSE with FLH-FTL stay (relatively) constant whereas the classification errors of other alternatives improve (Fig. 2). This highlights that FLH-FTL can be much more sample efficient with respect to the size of the hold-out offline labeled data. Motivated by this observation, we perform an additional experiment in which we increase the offline training data and observe that we can overall improve the classification accuracy significantly with FLH-FTL (Fig. 2). We present results on SHL dataset with similar findings on semi- synthetic datasets in App. G.5. Finally, we also experiment with a random forest model on the MNIST dataset. Note methods that update model parameters (e.g.. UOGD and ATLAS) with OGD are not applicable here. Here, we also observe that we improve over existing applicable alternatives (Table 2).
5.2
SOLS setup and results
Setup For the supervised problem, we experiment with MNIST and CIFAR datasets. We simulate a time horizon of T = 200. For each dataset, at each step, we observe 50 samples with Bernoulli shift. Motivated by our thcoretical results with weighted ERM, we propose simple baseline which continually trains the model at every step instead of starting ERM from scratch every time. We maintain pool of all the labeled data received till that time step, and at every step, we randomly sample a batch with uniform label marginal to update the model. Finally, we re-weight the updated softmax outputs with estimated label marginal. We call this method Continual Training via Re- Sampling (CT-RS). Its relation as a close variant of weighted ERM is elaborated in App. F.I. To estimate the label marginal, we try FTH and ours FLH-FTL.
Results On both datasets, we observe that empirical performance with CT-RS improves over the naive continual training baseline. Additionally, CT-RS results are competitive with weighted ERM

---

while being 5-15x faster in terms of computation cost (we include the exact computational cost in App. F.I). Moreover, as UOLS setup, we observe that FLH-FTL improves over FTH for both target label marginal estimation and classification.
Conclusion
In this work, we focused on unsupervised and supervised online label shift settings. For both settings, we developed algorithms with minimax optimal dynamic regret. Experimental results both real and semi-synthetic datasets substantiate that our methods improve over prior works both in terms of accuracy and target label marginal estimation.
In future work, we aim to expand our experiments to more real-world label shift datasets. Our work also motivates future work in exploiting other causal structures (e.g. covariate shift) for online distribution shift problems.
Acknowledgements
SG acknowledges Amazon Graduate Fellowship and JP Morgan AT Ph.D. Fellowship for their support. ZL acknowledges Amazon AI, Salesforce Research, Facebook, UPMC. Abridge, the PwC Center, the Block Center, the Center for Machine Learning and Health, and the CMU Software Engineering Institute (SEI) via Department of Defense contract FA8702-15-D-000 of ACMI Lab's 's research on machine learning under distribution shift. DB and YW were partially supported by NSF Award #2007117 and gift from Google.
for their generous support
References
[1] A. Alexandari, A. Kundaje, and A. Shrikumar. Adapting to label shift with bias-corrected calibration. International Conference on Machine Learning (ICML), 2021.
[2] K. Azizzadenesheli, A. Liu, F. Yang, and A. Anandkumar. Regularized learning for domain adaptation under label shifts. In International Conference on Learning Representations (ICLR), 2019.
[3] D. Baby and Y.-X. Wang. Online forecasting of www.--aaaaaaaaunddeee sequences. In Neural Information Processing Systems (NeurIPS), 2019.
[4] D. Baby and Y.-X. Wang. Optimal dynamic regret in exp-concave online learning. In COLT, 2021.
[5] D. Baby and Y.-X. Wang. Optimal dynamic regret in proper online learning with strongly convex losses and beyond. AISTATS, 2022.
[6] D. Baby and Y.-X. Wang. Second order path variationals in non-stationary online learning. AISTATS, 2023.
[7] D. Baby, X. Zhao, and Y.-X. Wang. An optimal reduction of tv-denoising adaptive online learning. AISTATS, 2021.
[8] Y. Bai, Y.-J. Zhang, P. Zhao, M. Sugiyama, and Z.-H. Zhou. Adapting to online label shift with provable guarantees. Advances in Neural Information Processing Systems, 2022.
[9] Bekker and J. Davis, Learning from positive and unlabeled data: a survey, Machine Learning, 2020. URL https: //t.///o.//a//// wt./oo//...//..... 1ttp//10.1007//11099990 -02000077775...
[10] O. Besbes, Y. Gur, and A. Zeevi. Non-stationary stochastic optimization. Operations research, 632511127 2015.
[11] O. Bousquet, S. Boucheron, and G. Lugosi. Introduction to statistical learning theory. In Advanced Lectures on Machine Learning, Lecture Notes in Computer Science. Springer, 2003.
[12] N. Resa-Bianche and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, New York. NY, USA, 2006. ISBN 052 18089.
10

---

[13] T.-J. Chang and S. Shahrampour. On online optimization: Dynamic regret analysis of strongly convex and smooth problems. Proceedings of the AAAI Conference on Artificial Intelligence. 2021.
[14) X. Chen, Y. Wang, and Y.-X. Wang. Technical note non-stationary stochastic optimization under Ip, q-variation measures. Operations Research, 2018.
[15] C. B. Clement, M. Bierbaum, K. O' Keeffe, and A. A. Alemi. On the use arxiv as a dataset. arXiv preprint wiXiv:905.00000 2019.
[16] C. Cortes and M. Mohri. Domain adaptation and sample bias correction theory and algorithm for regression. Theoretical Computer Science, 519, 2014.
[17] C. Cortes, Y. Mansour, and M. Mohri. Learning Bounds for Importance Weighting. In Advances in Neural Information Processing Systems (NIPS), 2010.
[18] Y. Cui, M. Jia, T.-Y. Lin, Y. Song, and S. Belongie. blass-balanced loss based on effective number of samples. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9268-9277 2019.
[19] A. Daniely, A. Gonen, and Shalev-Shwartz Strongly adaptive online learning. In Interna- tional Conference on Machine Learning, pages 1405-1411, 2015.
[20] D. Donoho and I. Johnstone. Ideal spatial adaptation by wavelet shrinkage. Biometrika, 81(3): 425-455, 1994.
[21] D. Donoho and I. Johnstone. Minimax risk over balbs for error. Probability Theory and Related Fields, 99(2):277-303 1994.
[22] D. Donoho, R. Liu, and B. MacGibbon. Minimax risk over hyperrectangles, and implications. Annals of Statistics, 18(3):1416-15) 1437, 1990.
[23] D. L. Donoho and I. M. Johnstone. Minimax estimation via wavelet shrinkage. The annals of Statistics, 26(3):879-921, 1998.
[24] C. Elkan and K. Noto. Learning classifiers from only positive and unlabeled data. In Interna- tional Conference Knowledge Discovery and Data Mining (KDD), pages 213 220, 2008.
[25] P. Gaillard and S. Gerchinovizz. A chaining algorithm for online nonparametric regression. In Conference on Learning Theory, pages 764-796, 2015.
[26] S. Garg, Y. Wu, S. Balakrishnan, and Z. Lipton. A unified view of label shift estimation. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[27] S. Garg, Y. Wu, A. Smola, S. Balakrishnan, and Z. Lipton. Mixture proportion estimation and PU learning: A modern approach. In Advances in Neural Information Processing Systems (NeurlPS), 2021.
[28] S. Garg, S. Balakrishnan, and Z. Lipton. Domain adaptation under open set label shift. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[29] S. Garg, S. Balakrishnan, Z. Lipton, B. Neyshabur, and H. Sedghi. Leveraging unlabeled data predict out-of-distribution performance. In International Conference Learning Representations (ICLR), 2022.
[30] S. Garg, N. Erickson, Sharpnack, A. Smola, Balakrishnan, and Z. Lipton. Risbench: Domain adaptation under relaxed label shift. In International Conference on Machine Learning (ICMI.), 2023.
[31] H. Gjoreski, M. Ciliberto, L. Wang, F. J. O. Morales, S. Mekki, S. Valentin, and D. Roggen. The university of sussex-huawei locomotion and transportation dataset for multimodal analytics with mobile devices. IEEE Access, 6:42592-42604. 2018.

---

[32] G. Goel and A. Wierman. An online algorithm for smoothed regression and lqr control. In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, 2019.
[33] A. Gretton, A. Smola, J. Huang. M. Schmittfull, K. M. Borgwardt, and B. Schölkopf. Covariate Shift by Kernel Mean Matching. Journal of Machine Learning Research (JMLR), 2009.
[34] A. Guntuboyina, D. Lieu, S. Chatterjee, and B. Sen. Adaptive risk bounds in univariate total variation denoising and trend filtering, Annals of Statistics, 2020.
[35] C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger. On calibration of modern neural networks, In International conference on machine learning, pages 1321-1330. PMLR, 2017.
[36] J. Guo, M. Gong, T. Liu, K. Zhang, and D. Tao. Lif: A label transformation framework for correcting label shift. In International Conference Machine Learning, pages 3843-3853 PMLR, 2020.
[37] E. Hazan. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-325, 2016.
[38] E. Hazan and C. Seshadhri. Adaptive algorithms for online decision problems. In Electronic colloquium on computational complexity (ECCC), volume 14, 2007.
[39] K. He. X. Zhang, S. Ren, and J. Sun. Deep Residual Learning for Image Recognition. In Computer Vision and Pattern Recognition (CVPR), 2016.
[40] Helber, Bischke, A. Dengel, and D. Borth. Eurosat: A novel dataset and deep learning benchmark for land use and land cover classification. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing. 12(7):211-22266. 2019.
[41] C. Huang, Y. Li, C. C. Loy, and X. Tang. Learning deep representation for imbalanced classi- fication. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5375-5384, 2016.
[42] A. Jacobsen and A. Cutkosky, Parameter-free mirror descent. COLT, 2022.
[43] A. Jadbabaie, A. Rakhlin, S. Shahrampour, and K. Sridharan. Online optimization: Competing with dynamic comparators. In Artificial Intelligence and Statistics, pages 398-406, 2015.
[44] I. M. Johnstone. Gaussian estimation: Sequence and wavelet models, 2017. URL: https:
//imjohie momjohnstone... su. www.ddda//naaat. /ttp//GE12-222 27-11 pdf. Last visited on 2023/04/20.
[45] S.-J. Kim, K. Koh, S. Boyd, and D. Gorinevsky. & trend filtering. SIAM Review, 51(2):339- 360, 2009.
[46] P. W. Koh, S. Sagawa, H. Marklund, S. M. Xie, M. Zhang, A. Balsubramani, W. Hu, M. Ya- sunaga, R. L. Phillips, I. Gao, T. Lee, E. David, I. Stavness, W. Guo, B. A. Earnshaw, I. S. Haque, S. Beery, J. Leskovee, A. Kundaje, E. Pierson, S. Levine, C. Finn, and P. Liang. WILDS: A benchmark of in-the-wild distribution shifts. In International Conference on Machine Learn- ing (ICML), 2021.
[47] W. M. Koolen, A. Malek, P. L. Bartlett, and Y. Abbasi. Minimax time series prediction. Ad Advances in Neural Information Processing Systems (NIPS' 15), pages 2557-2565, 2015.
[48] W. Kotlowski, W. M. Koolen, and A. Malek. Online isotonic regression. In Annual Conference on Learning Theory (COLT-16), volume 49, pages 1165-1189. PMLR, 2016.
[49] A. Krizhevsky and G. Hinton. Learning Multiple Layers of Features from Tiny Images. Technical report, Citeseer, 2009.
[50] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient- Baadee Learning Applied to Document Recognition. Proceedings of the IEEE, 86, 1998.
[51] 7. Lipton, Y.-X. Wang, and A. Smola. Detecting and correcting for label shift with black box predictors. In International Conference Machine Learning, 2018.
12

---

[52] E. Mammen and S. van de Geer. Locally adaptive regression splines. Annals of Statistics, 25(1): 387-413, 1997.
[53] M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning. The MIT Press, 2012.
[54] Orabona. A modern introduction to online learning, 2019.
[55] J. Quinonero-Candela, M. Sugiyama, A. Schwaighofer, and N. D. Lawrence. Dataset shift in machine learning. Mit Press, 2008.
[56] A. Raj, Gaillard, and Saad. Non-stationary online regression, 2020.
[57] A. Rakhlin and K. Sridharan. Online non-parametric regression. In Conference on Learning Theory, pages 1232-12644 2014.
[58] M. Roberts, P. Mani, S. Garg, and Z. Lipton. Unsupervised learning under latent label shift. In Ad Advances in Neural Information Processing Systems (NeurIPS), 2022.
[59] Sadhanala, Y.-.. Wang, and R. Tibshirani. Total variation classes beyond 1d: Minimax rates, and the limitations of linear smoothers. Advances in Neural Information Processing Systems (NIPS-16), 2016.
[60] V. Sadhanala, Y.-X. Wang, and R. J. Tibshirani. Graph sparsification approaches for laplacian smoothing. In AISTATS' 16, pages 1:50-1259, 2016.
[61] M. Saerens, P. Latinne, and C. Decaestecker. Adjusting the Outputs of a Classifier to New a Priori Probabilities: A Simple Procedure. Neural Computation, 2002.
[62] V. Sanh, L. Debut, Chaumond, and Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint 11Xiv:1910.01100, 2019.
[63] B. Schölkopf, D. Janzing, J. Peters, Sgouritsa, K. Zhang, and Mooij. On Causal and Anticausal Learning. In International Conference on Machine Learning (ICML), 2012.
[64] H. Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of statistical planning and inference, 90(2):227-244 2000.
[65] A. Storkey. When training and test sets are different: characterizing learning transfer. Dataset shift in machine learning, 30:3-28, 2009.
[66] R. J. Tibshirani. Adaptive piecewise polynomial estimation via trend filtering. Annals of Statistics, 42(1):280 ((1):285-323, 2014.
[67] A. Torralba and A. A. Efros. Unbiased look at dataset bias. In Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, pages 1521-1528. IEEE, 2011.
[68] A. B. Tsybakov. Introduction to Nonparametric Estimation. Springer Publishing Company, Incorporated, 1st edition, 2008
[69] S. van de Geer. Estimating regression function. Annals of Statistics, 18(2):907-924, 1990.
[70] R. Vershynin. High-Dimensiona Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018.
[71] L. Wang, H. Gjoreski. M. Ciliberto, Mekki, Valentin, and D. Roggen. Enabling reproducible research in bessor-based transportation mode recognition with the sussex-huawei dataset. IEEE Access, 01100870-1899, 2019.
[72] Y.-.. Wang, J. Sharpnack, A. Smola, and R. Tibshirani. Trend filtering on graphs. In AIS- TATS' 15, pages 1042-1050, 2015.
[73] Y.-X. Wang. Sharpnack, A. Smola, and R. J. Tibshirani. Trend filtering on graphs. Journal of Machine Learning Research, 17(105).1-41, 2016.
13

---

[74] Y.-X. Wang, D. Ramanan, and M. Hebert. Learning to model the tail. Advances in neural information processing systems, 30, 2017.
[75] Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, Cistac, T. Rault, R. Louf, M. Funtowicz, et al. Huggingface's s transformers: State-of-the-art natural language processing. arXiv preprint 19X1v:1110.03771, 2019.
[76] R. Wu, C. Guo, Y. Su, and K. Q. Weinberger. Online adaptation to label distribution shift, In Advances in Neural Information Processing Systems, 2021.
[77] H. Xiao, K. Rasul, and R. Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 2017.
[78] T. Yang, L. Zhang. R. Jin, and J. Yi. Tracking slowly moving clairvoyant: optimal dynamic regret of online learning with true and noisy gradient. In International Conference on Machine Learning (ICMI-16), pages 449-457, 2016.
[79] B. Zadrozny. Learning and Evaluating Classifiers Under Sample Selection Bias. In International Conference on Machine Learning (ICML), 2004.
[80] K. Zhang, B. Schölkopf, K. Muandet, and Z. Wang. Domain Adaptation Under Target and Conditional Shift. In International Conference on Machine Learning (ICML), 2013.
[81] L. Zhang, S. Lu, and Z.-H. Zhou. Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems (NeurIPS-18), pages 1323-1333, 2018.
[82] I.. Zhang, T. Yang, Z.-H. Zhou, et al. Dynamic regret of strongly adaptive methods. In International Conference on Machine Learning (ICMI.-8),, pages 5877-5886, 2018.
[83] Zhao and L. Zhang. Improved analysis for dynamic regret of strongly convex and smooth functions. L4DC, 2021.
[84] P. Zhao, Y. Zhang, L. Zhang, and Z.-H. Zhou. Dynamic regret of convex and smooth functions. NeurlPS, 2020.
[85] P. Zhao, Y.-.. Wang, and Z.-H. Zhou. Non-stationary online learning with memory and non- stochastic control. AISTATS, 2022.
(86) H. Zhou, Balakrishnan, and C. Lipton. Domain adaptation under missingness shift. In Artificial Intelligence and Statistics (AISTATS), 2022.
14

---

Appendix
A
Limitations
Our work is based on the label shift assumption which restricts the applicability of our methods to scenarios where this assumption holds. However, noted in Section 1, the problem of adaptation to changing data distribution is intractable without imposing assumptions on the nature of the shift.
Furthermore, noted in Remark 9, our methods in the SOLS settings have memory requirement that scales linearly with time, which may not be feasible in scenarios where memory is limited. This is reminiscent to FTL/ / FTRL type algorithms from online learning. We leave the task of deriving theoretical guarantees with reduced storage complexity under non-convex losses as an important future direction.
B Related work
Offline total variation denoising The offline problem of Total Variation (TV) denoising constitutes estimating the ground truth under the observation model in Definition 1 with the caveat that all observations are revealed ahead of time. This problem is well studied in the literature of locally adaptive non-parametric regression [20, 21, 23, 52, 69, 45, 66, 73, 60, 34). The optimal total squared error (TSE) rate for estimation known to 0 + 1) [22]. Estimating sequences of bounded TV has received a lot of attention in literature mainly because of the fact that these sequences exhibit spatially varying degree of smoothness. Most signals of scientific interest are known to contain spatially localised patterns [44]. This property also makes the task of designing optimal estimators particularly challenging because the estimator has to efficiently detect localised patterns in the ground truth signal and adjust the amount of smoothing to be applied to optimally trade-off bias and variance.
Non-stationary online learning The problem of online regression can be casted into the dynamic regret minimisation framework of online learning. We assume the notations in Definition 1. In this framework, at each round the learner makes decision 0r. Then the learner suffers squared error loss (f.)) || 11.. The gradient of the loss at the point of decision, (l,(d,) 2(, 2, is revealed to the learner. The expected dynamic regret against the sequence of comparators 01. is given by
R(01.T)
(0.) (e)))
T
Elll
0.1121 - El1 - -..1ā5
E [[16.118
22T0. + 22.
Σ F( 0.11
where in the last line we used the fact that the noise E (see Definition 1) is zero mean and independent of the online decisions &.. Due to this relation, we conclude that any algorithm that can optimally control the dynamic regret with respect squared error losses (x)) || x=13 can be directly used to control the TSE from the ground truth sequence 01.r.
The minimax estimation rate is defined as follows:
R (T. VT) = min
E[1[0, 0, [
Algorithms that can control the dynamic regret with respect to convex losses such those presented in the works of Jadbabaie et al. [43], Besbes al. [10], Yang et al. [78], Chen al. [14], Zhang et al. [81], Goel and Wierman [32], Zhao et al. [84], Zhao and Zhang [83], Zhao et al. [85], Chang
15

---

Algorithm
Run-time
Memory
FLH-FTL [38]
O
O
Aligator [7] O log T)
O
Arrows [3] O log T)
O(1)
Table 4: Run-time and memory complexity of various adaptively minimax optimal online regression algorithms (see Definition 1). For practical purposes, the storage requirement is negligible even for FLH-FTL. For example, with 10 classes and T 1000, the storage requirement of FLH-FTL is only 40KB, which is insignificant compared to the storage capacity of most modern devices.
and Shahrampour [13], Jacobsen and Cutkosky [42], Baby and Wang [6] can lead sub-optimal estimation rates of order O( ((VT(1 + Vrr)).
On the other hand, algorithms presented in Hazan and Seshadhri [38], Daniely et al. [19], Baby and Wang [3], Baby et al. [7]. Raj al. [56], Baby and Wang [4, 5] exploit the curvature of the losses and attain the (near) optimal estimation rate of (3 2/3 +).
Online non-parametric regression The task of estimating a sequence of TV bounded sequence from noisy observations can be cast into the online non- paraametrric regression framework of Rakhlin and Sridharan [57]. Results on online non aon-aaametrric regression against reference class of Lipschitz sequences, Sobolev sequences and isotonic sequences can be found in [25, 47, 48] respectively. However as noted in Baby and Wang [3], these classes feature sequences that are more regular than TV bounded sequences. In fact they can be embedded inside a TV bounded sequence class [59]. So the minimax optimality of an algorithm for TV class implies minimax optimality for the smoother sequence classes as well.
Offline label shift Dataset shifts are predominantly studied under two scenarios: covariate shift and label shift [65]. Under covariate shift, p(y|z)) doesn't change, while in label shift p(zly) remains invariant. Schölkopf et al. [63] articulates connections between label shift and covariate shift with anti-causal and causal models respectively. Covariate shift well explored in past [80. 79, 17, 16, 33]. The offline label shift assumption has been extensively studied in the domain adaptation literature [61, 65, 80, 51, 36, 26, 30] and is also related to problems of estimating mixture proportions of different classes in unlabeled data where previously unseen classes may appear (e.g., positive and unlabeled learning; Elkan and Noto [24], Bekker and Davis [9], Garg et al. [27, 28], Roberts et al. [58]). Classical approaches suffer from the curse of dimensionality, failing in settings with high dimensional data where deep learning prevails. More recent methods work leverage black-box predictors to produce sufficient low-dimensional representations for identifying target distributions of interest [51, 2, 61, 1]. In our work, we leverage black box predictors to estimate label marginals at each step which track with online regression oracles to trade off variance with (small) bias.
C Omitted proofs from Section 3
In the next two lemmas, we verify Assumption for some important loss functions. Lemma 11 (cross-entropy loss). Consider a sample (æ, y) ~ Q. Let p E RK and p(x) E AK
be a distribution that assigns a weight proportional p()) fu(()z)) the label i. Let E(p(r),))
9oll)
E Ily = i} log(1/p(=)(i) be the cross-entropy loss. Let L(p) == (f y)] be its population analogue. Then L(p) is 22/K / K//K
Lipschitz in ll-l12 norm over the clipped box D == {p E
po : < p(i) < Vi E [K] which is compact and convex. Further, the true marginals q E D whenever (i) 2 for all i [K].
Proof. We have
K L(p) = Σ
(1El log(p(z)
K
K
Ellog(
wxp(t))
lo((::(())))) [a]],
16

---

where we define w; == [o))) Then we can see that
[p E
E
E wyp(i))
p(i)
So if min, p(t) 2 ,4, we have that Σx wyp(1) S 1/p and Qc(il=)/p(i) S 1/p. So by triangle inequality, [V E 1/2 + 1/p.
Lemma 12 (binary 0-1 loss). Consider sample (x, y) Q. Ler E R and p(x) Ak be a distribution that assigns weight proportional p())
क6[š] fo(()z)) to the label i. Let j(x) be sample obtained from the distribution p(x). Consider the binary 0-1 loss ((ū(z),)) v) [(((a) # y). Let
L(p) = - (( (ū(x) + y) be its population analogue. Let qo 2 a a> 0. Then
L(p) 2/ ((T)) Lipschitz in ll-12 norm over the domain D == {p E R E 1 f(i)lo((iz) 2
p(i S 1 Vi E [K] which is compact and convex. Further, the true marginals qe E D whenever
(e(1) Z μ for all [K].
Proof. We have that
K L(p) Σ + [|>))(>)]]]]
Denote p(z)[{] p(i) ΣØ= p(j) with w,
Then we see that
Op(x))[1]
(wap(i))ws
0p(1)
Σ/= wyp(i)
Wi
< + Σ5 wpp(i)
< 2/(ar).
Similarly,
Op(x)]i]
wip(i)u
Op(s)
Σne wyp(i))
1/(T))
Thus we conclude that ||V 2VK((ar), where the gradient is taken with respect to p E KRK Therefore,
K |V <
Σ [[)l))]]
$ /2K3/2/((n)
Remark 13. The condition EK_ fo(()x)p(()) is closely related to Condition 1 of Garg et al. [26]. Note that this is strictly weaker than imposing the restriction that the distribution p(i) 2 for each i. Remark 14. emphasize that the conditions Lemmas 11 and 12 are only sufficient conditions that imply bounded gradients. However, they necessary for satisfying bounded gradients property.
17

---

Lemma 15. Let μ.v. E AK be such that pl2] (i).. Let st C-l fo( where C is the confusion matrix defined in Assumption 1. We have that Elst] = il and Var(s,) S 1/ min (C)
Proof. Let (ūx) = QF (0).)))) ((((a)) = ùt} be the probability that the classifier fo ==x; -i= Qr(2, i). Let's denote Qe(((x)) = gelve i) ==
predicts the label de. Here Q (x) := Wt3. By law of total probability, we have that
(c(We) Σ Q+(((x))) = ielve (1)
K
Qolū(m)) = ût - (1),
where the last line follows by the label shift assumption.
Let jr, R.K be such that μd( (e) and v(i] q (i). Then the above equation can be represented as V = Cp. Thus C--v.. 'v.
Given sample E Qt, the vector (z+) forms unbiased estimate of Hence we have that the vector A = C-1 fo(xz) an unbiased estimate μ. Moreover,
l S ||C~ S 11/0min(())
Hence the variance of the estimate j is bounded by 1/0 (C).
We have the following performance guarantee for online regression due to Baby et al. [7]. Proposition 16 (Baby al. [7]). Let s, C-1 C-1 fo(zz). Let q: == ALG(s be the online estimate of the true label marginal qt produced by the Aligator algorithm by taking 81:-1 as input at a round t. Then have that
T
Σ
F [1
12] OKK
4/3 (1/0 min (C)) + K),
where Vr Et 9--1l1. Here Ô hides dependencies in absolute constants and poly- logarithmic factors of the horizon. Further this result is attained without prior knowledge of the variation VT.
By following the arguments in Baby and Wang [4], a similar statement can be derived also for the FLH-FTL algorithm of Hazan and Seshadhri [38] (Algorithm 7).
Theorem Suppose we run Algorithm with the online regression oracle ALG as FLH-FTL (App. F) or Aligator [7]. Then under Assumptions I and 2, we have
E Raayyaniic (T) Ō (
K /
KT
mmi (C)
2/3
Omin (C)
where V1 == =EE qc-1l1a and the expectation taken with respect to randomness in the revealed co-variates. Further, this result is attained without prior knowledge of Vr.
Proof. Owing to our carefully crafted reduction from the problem of online label shift to online regression, the proof can be conducted in just few lines. Let q be the value of ALG(s1:1)) computed at line of Algorithm 2. Recall that the dynamic regret was defined as:
T
Raynamic (T) = Σ L.(g.) - L.(g)) s Σ Gll 9ell2
(4)
[=1
18

---

Continuing from (4), we have
E Raymamic (T) S E
G F. - 9e122]
1
G. E.EElll: 9ellal
G
E Elia qell
1=1
T
&
T
Flll - 2:11)]
[=1
=
0
K k1/02//0v
/10/////////////////2///1/////// (1/0 min (C)) + VKT /KT/o mmin (C)
where the second line is due to non-expansivity of projection, the third line is due to Jensen's inequality, fourth line by
and last line by Proposition 16. This finishes the proof.
Next, we provide matching lower bounds (modulo log factors) for the regret in the unsupervised label shift setting. We start from an coommttion-thoorete result which will play central role in our lower bound proofs.
Proposition 17 (Theorem 2.2 in Tsybakov [68]). Let TP and Q be two probability distributions on H. such that (L( Q S 3 < co, Then for any H-measurable real function @ H - (0,1),
max(P(o 1), - -)) exp(-3).
Theorem 5. Let VT S. 64T. There exists a loss function, a domain D (in Assumption 2), and choice of adversarial strategy for generating the data such that for any algorithm, we have ET E(LL( - Lo(ge)) = Ω mmax(T2/3v.?" .VT)) wwhere de E D is the weight estimated by the algorithm and qe E is the label marginal at round chosen by the adversary. Here the expectation is taken with respect to the randomness in the algorithm and the udversary.
Proof. We start with simple observation about KL divergence. Consider distributions with density P(x, = Po(xly)p(y) and Q y) = Po(xly)g(y) where (x, E IR [K]. Note that these distributions are consistent with the label shift assumption. We note that
Po(ali)p(i) dx Po(zli)q(1))
KL(PIIQ) Σ
Pa(zli)p(1) log
K Σ
p(i)
(o(x)))pp() log
dr
g(i)
p())
p(i) log
(0)
Thus we see that under the label shift assumption, the KL divergence is equal to the KL divergence between the marginals of the labels.
Next, we define problem instance and an adversarial strategy. We focus on binary classification problem where the labels is either 0 or 1. As noted before, the KL divergence only depends on the
19

---

marginal distribution of labels. So we fix the density Qu(xly) to be any density such that under the uniform label marginals (go(1) go 1/2) we can find a classifier with invertible confusion matrix (recall from Fig. that Qo corresponds to the data distribution of the training data set).
Divide the entire time horizon T is divided into batches of size A. So there are M := T/A batches (we assume divisibility). Let è { 5, 5} be of success probabilities, where each probability can define a Bernoulli trial. Here E (0, 1/4) which will be tuned later.
The problem instance is defined follows:
For batch i E [M]. adversary selects probability d E θ uniformly at random.
For any round that belongs the 7th batch, sample a label yr Ber(g:) and co-variate ~ Qu(-Iu)) Here = %. The co-variate re is revealed.
Let de be any estimate of qi at round t. Define the loss as Le( == 1f9 2 1/2] 4c) 1[q: 1/2]
We take the domain D in Assumption 2 as [1/2 - 6, 1/2 + 8). It is easy to verify that Lg():) is Lipschitz over D. Note that unlike Besbes et al. [10], we do not have an unbiased estimate of the gradient of loss functions.
Let's compute an upperbound on the total variation incurred by the true marginals. We have
T
M
q
9--1
Σ 9
9--1
1=2
25M
$ VT,
where the last line is obtained by choosing 5 Vrr((M) = V/
Since at the beginning of each batch, the sampling probability is chosen uniformly at random, the loss function in the current batch is independent the history available at the beginning the batch. So only the data in the current batch alone is informative in minimising the loss function in that batch. Hence sufficient to consider algorithms that only use the data within a batch alone to make predictions at rounds that falls within that batch.
Now we proceed bound the regret incurred within batch 1. The computation is identical for any other batches.
Let P be the joint probability distribution in which labels (V1,..., (J) within batch 1 are sampled with success probability 1/2 - 5 (i.e = 1/2 - 5)
P V.) (1/2))
Define an alternate distribution Q such that
Qun y사) = (1/2 (11/--))--1 10'-
According to the above distribution the data are independently sampled from Bernoulli trials with success probability 1/2 6. (i.e d: 1/2 + 8)
Moving forward, we will show that by tuning appropriately, any algorithm won't be able to detect
between these two alternate worlds with constant probability resulting in sufficiently large regret.
20

---

We first bound the KL distance between these two distributions. Let
1/2 6
1/22
(L1//28/|1/22+ 0) log
+ 8)
1/2 8
+6
28
28
(a) (1/2+ 6)
(1/2 8)
1/2+
1/2 +
165
1 482
648
(b) 3
where in line (a) used the fact that log(1 + + S x for x > -1 and observed that -46((1+2)) >
-1 as (0, 1/4). In line (b) we used E (0, 1/4).
Since P and Q are product of the marginals due to independence we have that
KL((PIQ)=
Σ
S (64A/3)
16/3
B,
(5)
where we used the choices 5 = (VT/(2T) and A = (T/V7)213.
Suppose the beginning of batch, we reveal the entire observations within that batch vı.a the algorithm. Note that doing so can only make the problem easier than the sequential unsupervised
setting. Let de be any measurable function of V1.A. Define the function di l[ 1/2]. Then by Proposition 17, we have that
1
[ax = 1), Q(or = 0)} 2 7 exp(-3),
(6)
where B is as defined in (5.
Notice that if qt 1/2 8, then (4:) 2 1/2 for any d. 2 1/2. Similarly if = -1/2 + 8, we have that T. (Q:) 1/2 for any Ô < 1/2.
Further note that (gr) = 1/2 8 by construction.
For notational clarity define (xx) and (x) ;= 11 We can lower-bound the instantaneous regret as:
E[L((901 - L((g)) =aa)
2 (Er(L)(G)) -00
L7 5))
2(0) 2
(E+ 2 1/2 - - 5)P(dr =
- (E2 1/2] (112 0)
1
Sp 1) + 1 50 =0)
(r) 2
2
6/2 mmx 1), Q(ó: 0)}
2 8 exp(-5),
where in line (a) we used the fact the success probability for a batch is selected uniformly at random
from O In line (b) we used the fact that L (ā:)- - L2 (1/2-214 -6) 2
since ς. E D =
Similarly term involving L. is also handled. In line (c) we applied (Fr (G) 2
5)) 2 8 since Fr [T. dr 2 1 1/2] 2 1/2 and (1
8) 1/2 8. Similar bounding is done
for the term involving Eg well. In line (d) we used (6.
21

---

Algorithm 5 LPA: a black-box reduction to produce a low-switching online regression algorithm
input Online regression oracle ALG, failure probability 6, maximum standard deviation o (see Definition 1).
1: Initialize prev = 0 E RKR b=1
2: Get estimate 0g from ALG((1111))
3: Output 8, prev
4: Receive an observation 24
// test to detect non-staionarity
5: if Ej=++ prev 0,11>> 5Ko log(2T (8) then
6: Set = + 1, prev 24
7: Restart ALG
8: else if f. b + is a power of then
9: Set prev = وز= 8//1-+11
10: end if
11:
Update ALG with 2
Thus we get the total expected regret within batch as
82
E(L((0)) - L((g)) 2 exp(-3)
The total regret within any batch [M] can be lower bounded using exactly the same arguments as above. Hence summing the total regret across all batches yields
T
T
5A
E (L)( Le(g)) 2
exp(-9)
A
8
Vr
exp(
-B)
16
2/33 v2//
exp(-
The ((VT) part of the lowerbound follows directly from Theorem 3.2.1 in Hazan [37] by choosing D with diameter bounded by (1)..
D Design of low switching online regression algorithms
Even-though Algorithm 4 has attractive performance guarantees, it requires retraining with weighted ERM at every round. This is not satisfactory since the retraining can be computationally expensive. In this section, we aim design version of Algorithm 4 with few retraining steps while not sacrificing the statistical efficiency (up to constants). To better understand why this goal is attainable, consider time window [1, n] S [T'] where the label marginals remain constant or drift very slowly. Due to the slow drift, one reasonable strategy is to re-train the model (with weighted ERM) using the past data only time points within [1. that are powers of (i.e via doubling epoch schedule). For rounds t E [1. n] that are not powers of 2, we make predictions with previous model hpev computed at fprev logga t] which is trained using data seen upto the time fprov- Observe that this constitutes at least half of the data seen until round t. This observation when combined with the slow drift of label marginals implies that the performance of the model Atrev round will be comparable to the performance of a model obtained by retraining using entire data collected until round t.
To formalize this idea, we need an efficient online change-point-detee point-detection strategy that can detect intervals where the TV of the true label marginals is low and retrain only (modulo at most log T times within low TV window) when there is enough evidence for sufficient change in the TV of the true marginals. We address this problem via two-step approach. In the first step, we construct generic black-box reduction that takes an online regression oracle input and converts it into
22

---

another algorithm with the property that the number of switches in its predictions is controlled without sacrificing the statistical performance. Recall that the purpose of the online regression oracles is to track the true label marginals. The output of our low-switching online algorithm remains the same as long as the TV of the true label marginals (TV computed from the time point of the last switch) is sufficiently small. Then we use this low-switching online regression algorithm to re-train the classifier when a switch is detected.
We next provide the Low switching through Phased Averaging (LPA) (Algorithm 5), our black-box reduction to produce low switching regression oracles. We remark that this algorithm is applicable to the much broader context of online regression or change point detection and can be of independent interest.
We now describe the intuition behind Algorithm 5. The purpose of Algorithm 5 is to denoise the observations 2 and track the underlying ground truth 0, in statistically efficient manner while incurring low switching cost. Hence it is applicable to the broader context of online non-parametric regression [3, 56, 7] and offline non-parametric regression [66, 72].
Algorithm 5 operates by adaptively detecting low TV intervals. Within each time window it performs a phased averaging in a doubling epoch schedule. i.e consider low TV window [b, rt.. For a round & E [b, n] let prev 2 [lngg(t (tbb+1)), In round t, the algorithm plays the average of the observations Abxlgew So we see that in any low TV window, the algorithm changes its output only at-most O(log 7) times.
For the above scheme not sacrifice statistical efficiency, it important efficiently detect windows with low TV of the true label marginals. Observe that the quantity prev computes the average of at-least half of the observations within time window that start at time b. So when the TV of the ground truth within a time window [b, t) is small, we can expect the average to be good enough representation of the entire ground truth sequence within that time window. Consider the quantity R2 := Ej=++1 llprev - 0 which the total squared error (TSE) incurred by the fixed decision prev within the current time window. Whenever the TV of the ground truth sequence Oz. is large, there will be a large bias introduced by prev due to averaging. Hence in such a scenario the TSE will also be large indicating non non-stationarity. However, we can't compute Rg due the unavailability of fj. So we approximate RS by replacing 9, with the estimates 0, coming from the input online regression algorithm that is not constrained by switching cost restrictions. This is the rationale behind the non-stationarity detection test Step 5. Whenever non-staionarity is detected we restart the input online regression algorithm as well as the start position for computing averages (in Step 6).
We have the following guarantee for Algorithm 5.
Theorem 18. Suppose the input black box ALG given to Algorithm 5 is adaptively minimax optimal (see Definition 1). Then the number of times Algorithm 5 switches its decision is at most / with probability at least
Further, Algorithm satisfies Σi= 110 - 0, 0.113- O(T3/3/33 with probability at least 1 - 8, where Vr = - 200, 0t-1ll1-
Remark 19. Since Algorithm is a black-box reduction, there are number of possible candidates for the input policy ALG that are adaptively minimax. Examples include FLH with online averages as base learners [38] or Aligator algorithm [7].
Armed with low switching online regression oracle LPA, one can now tweak Algorithm to have sparse number of retraining steps while not sacrificing the statistical efficiency (up to multiplicative constants). The resulting procedure is described in Algorithm (in App. E) which enjoys similar rates as in Theorem 6 (see Theorem 22).
E Omitted proofs from Section 4
First we recall result from Baby et al. [7].
Proposition 20 (Theorem 5 of Baby et al. [7]). Consider the online regression protocol defined in Definition 1. Let 0, be the estimate of the ground truth produced by the Aligator algorithum from Baby et al. [7]. Then with probability at-least - ô, the total squared error (TSE) of Aligator satisfies
T
Σ 10, 0.13 = 0(T1/5/213 + +1).
23

---

where VT = Et= - -01-1l11. This bound is attained without any prior knowledge of the variation VT.
The high probability guarantee also implies that
Σ - -,:00--001::001133/ + +1),
where the expectation is taken with respect randomness in the observations.
By following the arguments in Baby and Wang [4], a similar statement can be derived also for the FLH-FTI. algorithm of Hazan and Seshadhri [38] (Algorithm 7).
Next, we verify that the noise condition in Definition is satisfied for the empirical label marginals computed at Step of Algorithm 4.
Lemma 21. Let be as in Step 5 of Algorithm 4. Then it holds that st q: + c with e being independent across and Var(er) I L/N.
Proof. Since 9; is simply the empirical label proportions, it holds that E[st] qt. Further Var(s:) 1 as the indicator function is bounded by 1/N. This concludes the proof.
Theorem 6. Suppose the true label marginal satisfies ming, (e(k) 2 p O. Choose the online regression oracle Algorithm 4 as FLH-FFI, (App. F) or Aligator from Baby et al. [7] with its predictions clipped such that qr [k] 2 μ. Then with probability at least - 8, Algorithm 4 produces RH hypotheses with dynamic = Ô (T + VTglool(/////
where VT = Σi=2lle 4t-1ll1-
Further, this result is attained without any prior knowledge of the variation budget VT-
Proof. In the proof we first proceed to bound the instantaneous regret at round t. Re-write the population loss as:
N E
(g((uss) e(h(z15)) 865
Lhh)- N(t-
(q(()))
where the expectation is taken with respect to randomness in the samples. We define the following quantities:
N
qe (wks) ((h(2,5), M.)),
L, cmp (h) = N(t - 1)
(7)
ge (Bbi))
[-1 N
qe de(wes) ((b(ss)))
L,(h) = N(t - 1)
(8)
ã (1ir))
i=1
and
1-1 N
de (((is) ((h(21s)) (..)
cemp (h) ( N(1 -
(1(ss)
We decompose the regret at round as
(.(),) - L.(hī) L.(he) (he) + L.(h)) - immp (h+) + L. cmp (h Le(h)) + 10 L. (h
Le(he) [.c + Le(he)
jemp (h+) + I.c (h;) L. Ie(ht) + i. (h₂) I. (N.
T2
24

---

where in the last line we used (q.(2). Now we proceed to bound each terms as note above. Note that for any label m,
2e (m) (e(m) 9: (m)) {:(m)
(((m)
ge(m))
ge(m)
(.(m)
- (m()) (m) [m(m) (m(m)
(la:(m) (.(m)+++a (m))),
where in the last line, we used the assumption that the minimum label marginals (and hence of the online estimates via clipping) is bounded from below by jr. So by applying triangle inequality and using the fact that the losses are bounded by in magnitude, we get
(-1 N
B
T x
[l +111++10:
2ella]
N(t
1)p²
i=1 1=1
BVK
t-1
E' |l| +1 9cl12]
1)1²
BVK
DE Ell qi 2:11
(0)
Elll:: -01122 V
n.2
t
BVK
1 1/3
S(b) n2
Ella: 2:112] + Φ- (1 - 1)1/3
(10)
where line (a) is a consequence of Jensen's inequality. In line (b) we used the following fact: by Lemma 21 and Proposition 16, the expected cumulative error of the online oracle at any step is bounded by ///33/2/3 for some multiplier & which can contain poly-logarithmic factors of the horizon (see Proposition 20).
Proceeding in similar fashion, the term 7'4 be bounded by Eq.(10).
Next, we proceed to handle T3, Let E be any fixed hypothesis. Then each summand Eq.(7) is independent random variable assuming values in [0, B/pi) (recall that the losses lie within [0, B)). Hence by Hoeffding's s inequality we have that
B
141(37
emp (1) Ln(h)
S
/
N(t - 1)
B
171(32
S
(II)
/4
(1 1)
with probability at-least - -5/33((7)) Now taking union bound across all hypotheses in H. we obtain that:
B
log(3)HH/0) /8)
T3 S /
(12)
(t-1)
with probability at-least 5/TT).
To bound T2, we notice that it is not possible to directly apply Hoeffding's inequality because the summands in (8) are correlated through the estimates of the online algorithm. So in the following, propose trick to decorrelate them. For any hypothesis h H. we have that
25

---

(c(Vis) ((h(zig) vis)) - E e(h(21g, wm)))
(((ss))
(c(y)s)
i (Brr)
9c(Uis)
(Wbr)
9: 9:(()))
Uis
(1rr))
ge ac(uis) (:(s)))
E
E(h(rass. (1(())))-v)))
(((Us))
Viy
qe(rr)) ((h(2z)) (()()))-)))))))))))))>)))))))(
(u((v)) ((b(zz)) v6l)
E
(:(ii)
(1(1))
qi
Was
Now using (9) and proceeding similar to the bouding steps Eq.(10), we obtain
1
MEEs j=
Up
B
11 1.11+ 11.
gella
N(t
N(t
1)p²
j=1
BVK t-1
11 +112+ 2ell2
n²(t 1)
i=1
BYK K
Σ 1 11 - 1:
l1 --llltt
(a)
112
t -
BVK
V 1
(()
|| - de 1
n
(t 1)
with probability at-least - 5/3. 3. In line (a) we used Jensen's inequlaity and in the last line we used the fact the the online oracle attains high probability bound on the total squared error (TSE) (see Proposition 20).
N(1-)) E Ej
ViJ can be bounded using the same expression as above using similar logic. ==
To bound N.- E ΣN
jj= Wij. we note that it is the sum of independent random variables. Hence using the same arguments used to obtain (11(1 we have that
1
L-
N
log(37(74/0))
W
<
N
(t (t-1)
with probability at-least 1 - ()) Hence taking union bound across all hypothesis classes and across the high probability event of low TSE for the online algorithm yields that
T2
2BVK 122
[ -Ia-qqlll -1:=-all2t0 (t - 1)1/3
V
B
1
(t-1)
with probability at-least 237
Combining the bounds developed for T1, T1,3,,T3 and T4 and by taking a union bound across the event that resulted in (12), obtain the following bound instantancous regret.
26

---

2BVK 11²
( 18c-0ll2e0 10122+111
V//3
log(3T (11/8)
- -o())) -
[
vellal + Φ. (t - 1)2/3
+
(t - ()-
(13)
with probability at-least 5/T.
Note that via Jensen's 's inequality:
T
Fllge dcl12)
T
E Flll 12
1=1
S 2/ 1/3 /
where in the last line we used Proposition 20.
Similarly it can be shown that
T
1
- ge 12 S v
1=1
under the event that resulted in (q.(1
Observe that
Vil
S 2/
t1/3
Finally note that
T 1
Σ
2V..
t=1
Hence combining the above bounds and adding (13 across all time steps, followed by a union bound across all rounds, obtain that
- (,())) < (n(t))
4BVK
(30T2/3 + VT (log(337(H/88)
122
with probability at-least 5.
Next, prove Theorem 18.
Theorem 18. Suppose the input black box ALG given Algorithm 5 is adaptively minimax optimal (see Definition 1). Then the number of times Algorithm switches its decision is at most Ö(T) 23/2/3 with probability at least 1 - 6. Further, Algorithm 5 satisfies Σ 110: 0 0 2//3 2/3 with probability at least 8, where VT Σt= 0,-1l11-
Proof. First proceed to bound the number of switches. Observe that between two time points where condition in Line 5 of Algorithm 5 evaluates true, we can have at-most log T switches due to the doubling epoch schedule in Line 8.
first bound the number of times, condition in Line is satisfied. Suppose for some some time t, we have that E ||prev 0, 123> oKo (T)6. Suppose throughout the run of the algorithm, this is th time the previous condition is satisfied. Let n, == t b + 1 and let C2 TV[ t]
27

---

where TV[p + g) = Ei=p+1 10: - -1--111. Due to the doubling epoch schedule, we have that that
prev = ビ My and E Elprev]] = 7 Σÿ= Og for some n, 2 2 (L - b + 1)/2 nt/22.
So we have
Σ jmb+1
0,112 -
2 prev 011ß++110; 0 Σ
prev
j=b+1
< Σ
2 E E(prev] - -0,1iž+2|| E|prev]||++211 - 03112
j=b+1
(a) 2(EC; 20 K log 1og(2T - 20m 1/3 /
< 4 max Cn on 1/3 C /2/33 + 40 K log(2T/6)),
(14)
with probability at-least (T). In line (a) we used the following facts: i) Due Hoeffding's inequality,
0² K log( (T/4TT//)//// < 20 K log(2T/6)) with probability at-least
1 1- (2T); ii) [|E[pre]] 0 1 Ei= 8 - 0,1125 1 1 - 8 [|2]] I C₁ iii) [|0 8, 1|35
/ with probability at-least 1 8/(2T) due to condition in Theorem 18; iv) Union bound over the events in (i) and (iii).
Since the condition in Line 5 is satisfied at round 4, (1.(14) will imply that 5Ko² log(2T/0) s 4 max Cr, on, 1/3 02/33 + 4o 16)) Rearranging the above, we find that
C, Z K/
where we suppress the dependence on constants and logT.
Let the condition in Line be satisfied M number of times. By union bound, we have that with probability at-least 1 - 5
VT
C2
i=1
M
K/ Vmq
2()) KM
(1/M) EM n
2 KM3/2/1V /TT
where in Line (a) we used Jensen's inequality. Rearranging we get that
M 0/3 K 2/3),,
(15)
with probability at-least 1 1-6. 5.
Now we proceed to bound the total squared error (TSE) incurred by Algorithm 5. Let 0, be the output of Algorithm 5 round j. Suppose times b and + 1, the condition in Line (5) is satisfied. Observe that the condition in Line is not satisfied for any times in [b. c]. Then we can conclude that within the interval [b, c] we have that 10 0,1335 5Ko² 1og(4T/8) log(T"), since there are only at-most log T times within (b, c| where condition in Line 9 is satisfied. So we have that
Σ10, /=b
0, <
> 100 0,1++110; 0,1
/=b
1/3 1/3 C2/3 < 5KK 35Ko2log log log(T) + Φ n
28

---

with probability at-least - 8/T. Here n. := b- - b-++ 1 and C
: TV + c). Further we have that |10+t1 l a 2 due to the boundedness condition in Definition
Thus overall we have that Σj=b Ö(K + + / C with probability at-least for any interval [b,c+]] such that condition in Line satisfied at times and c Thus have that
M
Σ 100
1101-0
Σ
K
ni
1/3
C
2(a) T1/31 22/3 K 1/3 +
1/3 C
n;
1=1
M
1/3
M
2/3
K2/3 2(6) T2/3 2//3
+
Tl
Σ
C
/T1332/33 K1/3
with probability at-least 8. line (a) we used (15). In line (b) we used Holder's 's inequality with the dual norm pair (3,3/2). This concludes the proof.
We now present the tweak of Algorithm 4 by instantiating ALG with Algorithm and prove its regret guarantees. The resulting algorithm is described in Algorithm 6.
Algorithm 6 Lazy-TTrainByieeihttss handling label shift with sparse ERM calls
Input: Instance ALG of Algorithm 5, A hypothesis Class H
1: At round t [T), get estimated label marginal I from ALG(s).r-)).
2: if q: = @r-1 then
3:
h4-1
4: else
5: Update the hypothesis by calling a weighted-ERM oracle:
t-1
(e(sn.s)
h argmin kCH
e(h ((h(ar)) (v)s))
6: end if
7: Get N co-variates Tr,1:N and make predictions according to he
8: Get labels Vt.1:N
9: Compute se[i] 1/2 Ey [yy. i) for all i [K].
10: Update ALG with the empirical label marginals 8t.
Theorem 22. Assume the same notations as in Theorem 6. Suppose we run Algorithm 6 (see Appendix
E) with ALG instantiated using Algorithm 5 with o² 1//N and predictions clipped as in Theorem Further let the online regression oracle given to Algorithm 5 be chosen as one of the candidates mentioned in Remark 19. Then with probability at-least
have that
B Regyumii
Ô (12 + (Tlog((H118))
Further, the number of number of calls to ERM oracle (via Step 5) is at-most O3T1/3/2/3 with probability at-least 1-6 8.
Sketch. The proof of this theorem closely follows the steps fused for proving Theorem 6. So only highlight the changes that need to be incorporated to the proof of Theorem 6.
Replace the of Proposition 20 in the proof of Theorem 6 with Theorem 18.
29

---

For any round t, where Step 5 of Algorithm is triggered, we can use the same arguments as in the Proof of Theorem 22 bound the instantaneous regret by Eq.(13). i.::
2BVK 1²
[ ( 11-2lll 1112+ 2el22 + Φ.
V1/3
log(3T H1/56
(,(h))- ((()) -
+
(1 - 1)1/3
(t - 1)
(16)
with probability at-least 8/T.
For round t, where Step 5 is not triggered, we proceed as follows:
Let t' be the most recent time step prior to Ê when Step 5 is executed. Notice that the population loss can be equivalently represented as
1 ΣΣ N(t'
go(Bis) goluu) e(h(z))) ((h(a))))))))
(h(h)
E
qi (Vke))
i=
where the expectation is taken with respect randomness in the samples. We define the following quantities:
N
q:(yir) ((h(rrs)) vis), (:(1)s)
L7 cmp (h) = N(U' 1)
1'-1 N
de((ir) e(h(2z)). (1(1))))
L( = N(t' - 1) i=1 j=1
Σ
Σ
and
P N
delars) ((h(x:z), vi)).
1 (h) = N(t 1)
[ml (11r))
We decompose the regret at round
(hhh) L.(h)) (h+)) (h+)) + L.hh)) Iomp (h+) L. 1em ( Le(h)) + L. (h+) (hi)
S Ix(ha) [1p( + Le(h))
j.emp (h+) + I emm (h?) - Te(h)) + j.mmp (MT I.C (n1
TI
T2
T3
T4
where in the last line we used (2). Now we proceed to bound each terms as note above.
By using the same arguments as in Proof of Theorem 6 and replacing the use of Proposition 20 with Theorem 18, we can bound T1 -4. This will result in an instantaneous regret bound round (which doesn't 't trigger step 5) as:
2BVK 112
V
( (t' -1
(b( T.(h;)) <
[1 2112+Ell1 2el12] + Φ.
+
(t' 1)1/3
2B
V223
4log(37174//0
[1 u1ll+ [a] + + 41/3 41133
+
11
(t 1)1/3
(1-1)
(17)
30

---

with probability at-least 1 6/T. In the last line we used the fact that t' - 1 (t/2) - 1 (t 1)/4 for all 3.
Now adding (q6( and (17) across all rounds and proceeding similar to the proof of Theorem (and replacing the of Proposition 20 with Theorem 18) completes the argument.
We next prove the matching (up factors of log 7') lower bound.
Theorem Let Vr & T/8. There exists a choice of hypothesis class, loss function, and adversarial strategy of generating the data such that R dynamic
Ω (T2/3V2/3 + vTlog((Hl)) wwhere the expectation is taken with respect randomness in the algorithm and adversary.
Proof. First we fix the hypothesis class and the data generation strategy. In the problem instance we consider, there are co co-variates. The hypothesis class is defined as
H (hp h predicts label y Ber(y); [[H[]].
Further design the hypothesis class such that both ho, h1 E H. Next fix the data generation strategy:
Divide the time horizon into batches of length A.
At the beginning of batch the adversary picks d uniformly at random from {1/2
6, 11/2+6);
For all rounds that falls within batch i, the label y ~ Ber(q:) is sampled with ge == 9:-
Learner predicts a label ÿe {0, 1) and then the actual label y is revealed (hence N in the protocol of Fig.3).
Learner suffers a loss given by ( = L(ue + ye
easy see that the losses are bounded in [0, 1]. Now let's examine the possibilities of generating labels within a batch. Let's upper bound the variation incurred by the label marginals:
M Σ
Σ gge t=2
1--1 1|
9:
أi-1l
1=2
< 25M
VT,
where the last line is obtained by choosing 8 = / Vr VrT/(2T).
Since at the beginning of each batch, the sampling probability of true labels is independently renewed, the historical data till the beginning a batch immaterial in minimising the loss within the batch. So we can lower bound the regret within each batch separately and add them up. Below, we focus on lower bounding the regret batch and the computations are similar for any other batch.
Suppose that the probability that an algorithm predict label y/+ = 1 is Gr. where q is a measurable function of the past data 91:--1- Then we have that the population loss Le(ğ:) == (ū.) =
(1- qe Qq: + če(1 - q:) Here we abuse the notation L(q)) == L(h ). We see that the population loss L.(ğ.) are convex and its gradient obeys (L,(
2q. E 2y.] since by our construction ~ Ber(g:). Thus the population losses are convex and its gradients can be estimated in an unbiased manner from the data.
We use the following Proposition due to Besbes et al. [10].
Proposition 23 (due to Lemma A-1 in Besbes et al. [10]. Let P denote the joint probability of the label sequence yıAA within batch when they are generated using Ber(1/2 5). So
Po P( M.) = n (1/2- (1/2 53 --8
31

---

Similarly define Q as
11/2 (1/2 -8)'
According to the above distribution the data are independently sampled from Bernoulli trials with success probability 1/2 6. Let qr the decision of the online algorithm qt round t so that the algorithm predicts label 1 with probability q..
Let P denote the joint probability distribution across the decisions 91:2 of any online algorithm under the sampling model P... Similarly define Q Note that any online algorithm can make decisions at round t only based on the past observed data Y1--11 Further after making the decision q at round t. an unbiased estimate of the population loss can be constructed due to the fact that V (q.) E 2y.]- Under the availability of unbiased gradient estimates of the losses, it holds that
2y.]-
KL(PI ()) S 4A8
By choosing 8 = (2M(2M) = (2T/(2T) and A = (T/V7)2/3, we get that KL(PI Q) S 1.
Since VT T/8. the above choice implies that 8 10,
For notational clarity, define gg) = (1 (1/2 6) + g(1/2 5) and (g =1 (1-)))(11)) - 5) + (112 5). These corresponds the population losses according to the sampling models IP and Q respectively. Observe that ming L (q) ming (g) 1/2 8. The minimum of L and L are achieved at O and respectively. Note that both ha, hı E H. So there is always hypothesis in H that corresponds the minimiser of the loss.
Further whenever i 2 1/2 we have that
L²(4)) = -1122- - 5) + ((26)
2 1/22.
Similarly whenever q < 1/2 we have (g) 1/2. So define the selector function dr
Ll 2 1/2). Let of E {0, 1 be the minimiser of the loss at round t. Now we can lower bound the instantaneous regret similar as
E(L L.(17)] = (Er(Li()) [2(00 + 1 (B - (1))
EEr [L, (q:) (2)0))= () =) (FQ (1) o)Q(á, 0)
2 8/2 6/2max 1), Q(o, = 0)}
2 (8)8)e-1,
where the last line is obtained by Propositions 23 and 17.
Thus get total lower bound on the instantanoeus regret
(8e)
AVr/(16e) 1/3 ((1e),
where the last line is obtained by using our choices of / / and A (T/Vr)2/3
The second term of of Ω( T (TV/log/H) be obtained from the existing results on statistical learning theory without distribution shifts. (see for example Theorem 3.23 in Mohri et al. [53]).
32

---

F More details on experiments
In Algorithm 7, we describe the FLH-FTL algorithm from Hazan and Seshadhri [38] when specialised to squared error losses. When specialized to squared error losses, this algorithm runs FLH with online averages as the base experts.
Algorithm 7 An instance of FLH-FTL from Hazan and Seshadhri [38] with squared error losses
1: Parameter a is defined to be a learning rate
//
and def iniitioss
2: For FLH-FTL instantiations within UOLS algorithms (as Algorithm 2), we set a f o omen (C)/(8)) where C' is the confusion matrix in Assumption 1. For instantiations within SOLS algorithms (as in Algorithm 4) we set a < 1/(8K)
is probability vector in R', Initialize v/ 1 4: For each! j E [T], define base learner E For each t > j. the base expert outputs E² ==
3: For each round & E [7], 2 == (o(²), .........u ot (t)
Li=j 2g,, where 2j to be specified as below. Further E (j) := 0 E R // execution steps
5: In round E [T], set Vjj S 1, xr. <- (1) (the prediction of the j"h base learner at time 1). Play
xx - ード (.)
(t+1) 6: Receive feedback 2,, set 0/41 + 0 and perform update for 1 I Sist. t:
(1) e -alls -2
Ej=1 e
(++1) 7: Addition step Set 1+1 to 1/(t + 1) and for i +
(0) o - (1-
Rationale behind the learning rate setting at Line of Algorithm 7 The loss that is incurred by Algorithm 7 and any of its base learners at round t is defined to be the squared error loss fe(x) = | x x11.. Whenever [| B and || B?, the losses (z) are 1/(8B²) exp-concave (see for eg. Chapter of [12]). The notion of exp-concavity is erucial for FLH-FTL algorithm since the learning rate is set to be equal to the exp-concavity factor of the loss functions (see Theorem 3.1
in Hazan and Seshadhri [38]).
For the UOLS problem, from Algorithm 2, we have [ocl===(ic~=f(xx))) the decisions of the algorithm is a convex combination of the previously seen 24, we conclude that the losses (x) are o² "msn (8K)(8)) exp-concave.
Since
For the SOLS problem, let 2 = s, where st is as defined in Algorithm 4. We have that || 12l VK. Hence arguing in similar fashion as above, we conclude that the losses (x) are 1/(8K) exp- concave for the SOLS problem.
This is the motivation behind Line 2 in Algorithm 7, where the learning rates are according the problem setting.
Dataset and model details.
Synthetic: For the synthetic data, we generated 72k samples as described in Bai al. [8]. There are three classes each with 24k samples generated from three Gaussian distributions in 12, Each Gaussian distribution is defined by a randomly generated unit-norm centre and covariance matrix 0.215 I. 60k samples are used as source data, and 12k samples are used as target data to be sampled from during online learning. We used logistic regression to train linear model. It is trained for a single epoch with learning rate 0.1, momentum 0.9, batch size 200, and l2 regularization 1 x 10
MNIST [50]: An image dataset of 10 types of handwritten digits. 60k samples are used as source data and 10k as target data. We used an MLP for prediction with three consecutive
33

---

hidden layers of sizes 100, 100, and 20. is trained for a single epoch with a learning rate 0.1, momentum 0.9, batch size 200, and l2 regularization 1 x 10
CIFAR-10 [49]: A dataset of colored images of 10 items: airplane, automobile, bird, cat, deer, dog, frog. horse, ship, and truck. 50k samples are used as source data and 10k as target data. We train ResNet18 model (He et al. [39]) from scratch. It is finetuned for 70 epochs with learning rate 0.1, momentum 0.9, batch size 200, and /2 regularization x 10- The learning rate decayed by 90% at the 25th and 40th epochs.
Fashion [77]: An image dataset of 10 types of fashion items: T-shirt, trouser, pullover, dress, coat, sandals, shirt, sneaker, bag, and ankle boots. 60k samples are used as source data and 10k target data. We trained an MLP for prediction. It is trained for 50 epochs with learning rate 0.1, momentum 0.9, batch size 200, and l2 regularization 1 x 10-4
EuroSAT [40]: An image dataset of 10 types of land uses: industrial buildings, residential buildings, annual crop, permanent crop, river, sea & lake, herbaceous vegetation, highway, pasture, and forest. 60k samples are used as source data and 10k as target data. We cropped the images to the size (3, 64, 64). We train a ResNet18 model for 50 epochs with learning rate 0.1, momentum 0.9, batch size 200, and 12 regularization 1 10"
Arxiv [15]: A natural language dataset of 23 classes over different publication subjects. 198k samples are used as source data and 22k as target data. We trained a DistilBERT model (Sanh et al. [62]) for 50 epochs with learning rate 2 x 10-5, batch size 64, and l2 regularization x 10
SHL [31, 71]: tabular locomotion dataset of classes of human motion: still, walking. run, bike, car and bus. 30k samples are used as source data and 70k as target data. We trained an MLP for prediction for 50 epochs with learning rate 0.1, momentum 0.9, batch size 200, and la regularization x 10-1
For all the datasets above, the initial offline data are further split by 80 20 into training and holdout data, where the former is used for offline training of the base model and the latter for computing the confusion matrix and retraining (e.g. updating the linear head parameters with UOGD or updating the softmax prediction with our FI.T-FTL) during online learning. To examine how well the algorithms adapt when holdout data is limited, we use 10% of the holdout data (i.e., 2% of the initial offline data) in the main paper unless stated otherwise. In App. G.2, we ablate with full hold-out data.
Types of Simulated Shifts. We simulate four kinds of label shifts to capture different non- ota-stationary environments. These shifts are similar to the ones used in Bai et al. [8]. For each shift, the label marginals are a mixture of two different constant marginals (41, /22 E Ax with a time-varying coefficient 0g: My, = (1 0z) + 0c(22, where Myy denotes the label distribution at round / and or controls the shift non-stationarity and patterns. In particular, we have: Sinusoidal Shift (Sin): ar sin in. where i t mod L and L is given periodic length. In the experiments, we set L= VT. Bernoulli Shift (Ber): at every iteration, we keep the a, = Q4-1 with probability p E [0, 1] and otherwise set a₁ = 1- - at-1- In the experiments, the parameter is set as = 1/VT, which implies Vn = 0(VT). Square Shift (Squ): at every L rounds we set a, =1 a1-1- Monotone Shift (Mon): we set a, = t/TT. Square, sinusoidal, and Bernoulli shifts simulate fast-changing environments with periodic patterns.
Methods for UOLS Adaptation.
Base: the base classifier without any online modifications.
OFC: the optimal fixed classifier predicts with an optimal fixed re-weighting in hindsight as in Wu et al. [76].
Oracle: re-weight the base model's predictions with the true label marginal of the unlabeled data at each time step.
FTH: proposed by Wu et al. [76], thelowythe- classifier re-weights the base model's predictions with simple online average of all marginal estimates seen thus far.
FTFWH: proposed by Wu et al. [76], of FTH that tracks only the l most recent marginal estimates. We choose k = 100 throughout the experiments in this work.
classifier is version
34

---

CT
CT-RS (ours)
CT-RS (ours)
w-ERM (oracle)
(base)
w FLH
w FLT-FTL
CI Err MSE
5.0.0.5
4.71
4.53=0.1
3.240.4
MNIST
NA
0. 0.1220.01
0.08
NA
Table Results SOLS setup. We report results with MNIST SOLS setup runs for 200 steps. We observe that continual training with re-sampling improves over the base model which continually trains on the online data and achieves competitive performance with respect to weighted ERM oracle.
W-ERM
CT-RS (ours) (oracle)
CIFAR
145
1882+14
MNIST
2012.7
107
Table 6: Comparison on computation time (in minutes). We report results with MNIST and CIFAR SOLS setup runs for T 200 steps. We observe that continual training with re-sampling is approximately 5-15x more efficient than weighted ERM oracle.
ROGD: proposed by Wu et al. (76), ROGD uses online gradient descent update its re- weighting vector based on current marginal estimate.
proposed by Bai et [8], retrains the last linear layer the model based on current marginal estimate.
UOGD:
ATLAS: proposed by Bai et al. [8] is a meta-lcarning algorithm that has UOGD as its base learners.
The learning rates of ROGD, UOGD, and ATLAS are set according suggestions in the original works. The learning rate of FLH-FTI, is set to 1/K. This corresponds faster rate than the theoretically optimal learning rate given in Line 2 of Algorithm 7. It has been observed in prior works such as Baby et al. [7] that the thcoretical learning rate is often too conservative and faster rates lead to better performance.
F1 Supervised Online Label Shift Experiment Details
For each dataset, we first fix the number time steps and then simulate the label marginal shift. To train the learner with all the methods, we store all the online data observed giving the storage complexity of (T)). We observe N labeled examples into 80:20 split for training and validation. The validation examples are used to decide the number of gradient steps at every time step, in particular, we take gradient steps till the validation error continues to decrease.
examples every iteration and we split the observed
Dataset and model details.
MNIST [50]: An image dataset of 10 types of handwritten digits. At each step, sample 50 samples with the label marginal that step without replacement and reveal the examples to the learner. We used an MLP for prediction with three consecutive hidden layers of sizes 100, 100, and 20.
trained for a single epoch with a learning rate 0.1, momentum 0.9, batch size 200, and (2 regularization 1 x 10
CIFAR-10 [49]: A dataset of colored images of 10 items: airplane, automobile, bird, cat, deer, dog, frog, horse, ship, and truck. At each step, we sample 50 samples with the label marginal that step without replacement and reveal the examples to the learner. It is finetuned for 70 epochs with learning rate 0.1, momentum 0.9, batch size 200, and regularization x 10-4
We simulate Bernoulli label shifts to capture different non-stationary environments.
Connection CT-RS to weighted ERM Before making the connection, we first re-visit the CT- RS algorithm. Step 1: Maintain pool of all the labeled data received till that time step, and at every
35

---

iteration, we randomly sample a batch with uniform label marginal to update the model. Step 2: Re- weight the softmax outputs of the updated model with estimated label marginal. Below we show that it is equivalent to wERM:
(e(vi.)) ((f(daa))) ((()).))
argmin FEN
K
(vs.) 1b) E(f(zig),
argmin FEN
(A))
(:(k)
K
(k)
L-1
(yir =k) ((F(xxs)).)
argmin JEN
(1/K)
K -.q((k)
i=1 j=1
(Mh. k)
e( ((((r))))
argmin SEN
Pi.k
Pi,k
where fr, = (k/ is the importance ratio at time with respect to uniform label marginal. Similarly, we define A ()/)) Here, -,-1, is the aggregate loss at 1-th time step for k-th class such that at each step the sampling probability of that class is uniform. By continually training classifier with CT-RS, Step approximates the classifier S, trained to minimize the average of L over all classes with uniform proportion for each class. To update the classifier fe according to label proportions at time we update the softmax output of ft according to fig.
The primary benefit of CT-RS over wERM to avoid re- re-training from scratch at every iteration. Instead, we can leverage the model trained in the previous iteration to warm-start training in the next iteration.
36

---

G Additional Unsupervised Online Label Shift Experiments
G.1 Additional results with Monotone and Square Shifts and Low Amount of Holdout Data
Methods
Synthetic
MINIST
CIFAR
EuroSAT
Fashion
ArXiv
Mon
Squ
Mon
Mon
Mon
Mon
Squ
Mon
Squ
Base
8.720.1
8.5a0.9
4.7200
4.4g0.a
1740
1710
13.0
15.0
15a0
2210
21
OFC
6.919.1
6.610.
4.1
3.9.0.
1410
14.0
1111
11.00
9.0
9.6104
1811
1819
Orucle
5.2
3.6102
2.5.10
2.2
7.7.0a
6.810.
5.3_0.2
4.4.
5.1
4.1.0a
6.91m.
6.6102
FTH
7.1
6.8
9.3
8.9
19a1
PTFWH
6.320
7.0a0.0
4.010.0
4.120.1
12.0
1310
9.9.0.
11.0
8.4g0.
9.120.
1821
1840
ROGD
7.81m.3
7.810a
4.510
5.41177
1411
1510
11,0
14g1
8.9104
10.1
1911
21
UOGD
8.1.0a
8.1
4.9.
4.81u.4
1511
15.10
1011
11.1
11.12
1212
2011
1910
ATLAS
8.0
12:1
20
FLH-FIL (ours)
6.
5.6+0.4
4.00..
4.0=0.0
12:0
12:0
104a
10#0
8.640.4
8.4=04
18=1
17:0
Synthetic
MNIST
CIFAR
EuroAAT
Fashion
ArXiv
Squ
Mon
Sqo
2.21
0.14
0.27gam0
0.
a.
0.14
0.28am00
0.16gaas
0.28gam
0.18
0.30gamm
FTFWH
0.05ggno 0.23gnm
00 on 0.30gg.0
0.07
0.30g
0.07gmm
0.30gmos
0.08g0o0
2.3)
0.00
0.32gmm
ROGD
0. 0:
0.20
0.28goos
0.41gno
0 22220
0.27gmo a.
0.41000
0.21gamr
0.37gmm
0.21
0.36gem
PLH-FIL
0.15:1000
0.17.000
0.08.mmm
0.17.001
0.1810.02
0.11.0.0
Table 7: Results for UOLS problems with monotone and square shifts using low amount of holdout data. Top: Classification Error. Bottom: squared error in estimating label marginal.
G.2
Additional results with All of Holdout Data
Methods
Synthetic
MNIST
CIFAR
EaroSAT
Fashion
ArXiv
Ber
Sin
Ber
Sin
Ber
Sin
Ber
Sin
Ber
Sin
Ber
Sin
Base
8.6.a.a
8.210a
3.810
3.91m6
17.0
16.0
13_0
13.1
15.10
15.0
23.0
1919
OFC
6.7.aaa
5.5
3.410a
3.41aa
1310
11.10
11.3
9.811.
8.3mm
6.8....
21
1410
Orucle
3.7
3.7
1.750.2
1550a
6.3ema
5,9g01
4.0
3.5502
3.6.0.1
7.8.0.2
FTH
6.8-0.2
5.5+0.3
3,2+0.2
3.2=0.3
12H0
10ce
11=0
9.5+m.1
8.0en.n
6.8+0.2
20
14:0
FTFWH
6.6m0.a
5,5e0.
3.3+0.2
3.2-0.1
12s0
10:0
10
9.1+0.2
7.9e0.0
6.9-0.2
20e0
14=0
ROGD
7.8
7.2+0.a
4.740.5
3.3en.
15a0
11
11:0
1040
1des
8.2=0.2
23
16
UOGD
7.6
7.0
3.2:0.2
3.2:0
11:0
7.710.0
7.3
9.62u2
8.6
19:0
ATLAS
7.5m0.3
6,8+0.u
3.2+0.3
3.2=0.a
1280
1150
9.1+0.0
8.3ei.2
12+0
11sn
21
16+0
FLH-FTL (ours)
5. 5.4+0.a
5. 5.3+0..2
3.2+0.2
3.3+0.2
11s0
10:0
9.4+0.2
9.3+o.1
7,5+0.1
7.0-0.0
19s0
14=0
Syntheti
MNIST
CIFAR
EuroSAT
Fashion
ArXiv
Ber
Sim
Ber
Sin
Ber
Sin
Ber
Sin
Ber
Sin
Ber
Sin
FTH
0.20ggoas
0.14gs.0
0.27amm
0.272s0o
0.14gmm
0.10aam
0.28:0.0
ROGD
0.29.000
0.23::000
0.4310m
0.30--.0 0.3
0.21:000 0.41::00 0.341om
0.45:s.ee 1.31
0.36:940 0.28.0..
FLH FTL (ours)
0.09 0:00 0.08 0.13 0.12:0.00 0.15: 0.13 0.15:10.00 0.13:000 0.15 0.13
0.22:000 0.15
Table 8: Results for UOLS problems using all hold-out data. Top: Classification Error. Bottom:
Mean-squared error in estimating label marginal. Compared to the result in the main paper (Table I),
we observe that the performances of ROGD, UOGD, and ATLAS depend more on availability of holdout data that FLH-FTL. Notably, UOGD becomes competitive in the majority of the datasets when abundant holdout data are available.
37

---

G.3 Ablation over Number of Online Samples
Here we examine how different algorithms perform as the number of online samples varies. We introduce an additional baseline BBSE, which simply uses the label marginal estimate provided by black box shift estimator reweight the predictions of classifiers. Figure 3 shows interesting trend
Oracle BBSE
UOGD
Error
FLH-FTL (ours)
MSE
0.8
Classification Error
0.3
Mean Square Error
0.6
0.2
0.4
0.1
0.2
0.0
0.0
1
2
4
8
16
32
64
128
Number of Online Samples
Figure Performances of online learning algorithms with different number of online samples. CIFAR-10 results with bernouli shift and limited holdout data. Solid line is the classification error (Error) and the dotted line is the marginal estimation mean squared error (MSE).
that as number of online samples increases, the simple baseline BBSE becomes more competitive and eventually outperforms UOGD, whereas our algorithm remains competitive.
G.4 Ablation over Types Marginal Estimates
All the algorithms examined in this work use black box shift estimate (BBSE) [51] to obtain an unbiased estimate of the target label marginal. However, two alternative methods exist: Maximum Likelihood Label Shift (MLLS) [61] and Regularized Learning under Label Shift (RLLS) [2]. Table presents additional results using these two estimates. The results shows using the alternative estimates do not substantially change the performances of the algorithms considered in this work.
38

---

Datasets
Synthetic
CIFAR
Fashion
MARG EST.
BBSE
MLLS
RLLS
BBSE
MLLS
Base
8.620.2
8.620.2
8.620.2
1620
1620
1620
1520
1520
1520
OPC
6.480.6
6.410.6
6.440.6
1241
1241
12a1
7.940.1
7.940.1
7.9
FTH
6.520.8
6.520.7
6.5
11:0
11
11.0
8.520.3
8.020.0
8.620.
Bernuli
FTFWH
6.620.5
6.7+0.5
6.6+0.5
11
11
11s1
8.2+0.6
7.9.0.2
8.3+0.6
ROGD
7.9.0.a
7.9+0.a
7.9+0.2
164a
164a
16#2
10+1
10+1
9.6+1.2
UOGD
8.1
8.0+1.0
8.0+1.0
14#0
1440
11*2
10+1
11+1
ATLAS
8.0+1.0
7.9+0.6
8.0$1.0
13#0
1340
1340
12+2
11#1
12+1
FLH-FTL (ours)
5.4
5.410.8
5.410.7
1020
1011
1040
7.7=0.4
7.3-0.a
7.620.
Base
8.220.3
8.220.3
8.220.3
1620
1620
1540
1520
OPC
5.520.2
5.520.2
5.5
11:o
1120
11:0
7.120.1
7.1ao.
7.120.1
FTH
5.720.3
5.720.2
5.720.2
11:0
1120
11:0
6.920.4
6.6=0.2
6.8g0.4
Sinusoidal
FTFWH
5.7
5.6+0.2
5.7+0.3
11:0
11:0
11:0
6.9=0.4
6.6=o.a
6.9+0.4
ROGD
7.240.8
7.220.0
7.220.8
1320
1320
8.240.7
8.9go.
8.220.3
UOGD
7.5+0.6
7.4+0.6
7.4s0.5
14+1
13+1
14s1
11+2
9.4+0.
11+2
ATLAS
7,5
7.4áo.6
7.44o.6
13a1
1341
13s1
12#2
11#1
12#2
FLH-FTL (ours)
5.410.4
5.420
5.410.
1120
1010
1110
7.020.0
6.6_0.2
6.920.4
Table Performances of online learning algorithms with different types of marginal estimates with low amount of holdout data.
G.S Additional results and details on the SHL dataset
0.8
FIN
4000
FTH
PENFEL (RAIS)
1.0-
0.6
Square Error
0.8
0.8
Classiiiatton
Distibution
0.6
0.6-
0.4
0.2
0.2-
M
0.0
0.0
2000
2000
4000
6000
20
60
100
Time
Time
(c)
Figure 4: Additional results and details the SHI. datasets with real shift. (a) and (b): The accuracies and mean square errors in label marginal estimation on SHI dataset over 7,000 time steps with limited amount of holdout data. (c): Label marginals of the six classes of SHI dataset. Each time step here shows the marginals over 700 samples.
G.6 Reweighting Versus Retraining Linear Layer
Here we compare the efficacies of re- se-weighting (RW-FLH-FTL) and retraining (RT-FLH-FTL) given the marginal estimate provided by FLH-FTL: the latter retrains the last linear layer on the loss the holdout data re-weighted by the marginal estimate. Note that RW-FLH-FTL. corresponds to FLH- FTL in the main text. We retrain RT-FLH-FTL for 50 epochs at each time step. To compare against the best possible retrained classifiers, we used all the holdout data for retraining. Table 10 shows that retraining often worse and at best similar to re-weighting in performance, despite greater computational cost and need for holdout data.
39

---

Datasets
Synthetic
Shift
Squ
Squ
Rase
8.7g0.1
8.2g0.a
8.0
8.5g0.
17a0
1620
OFC
6.810.1
5.5.0.
6.71oa
6.710a
1420
11.0
1310
1311
FITWHI
7.0
5.510.3
6,8102
6.810.3
1320
10.0
1210
1310
UOGD
7.4go.1
7.0
7.6
7.62002
12:0
1040
11:0
131o
RW-FLH-FTLL (ours)
RI-FLH-FIL (ours)
6.7
6.2e0.2
6.0+0.0
6.3+0.4
12+0
10+o
11-0
12-0
Table 10: Comparison of performances of re-weighting and retraining strategies with high amount of holdout data.
40


Reviews:
[{"review_id": "JZon3jFhsv", "reviewer": "Reviewer_Cpae", "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.", "questions": "The paper is mainly sound and well-organized, but there remain some concerns for me, see the Weaknesses part above.", "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.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The manuscript is neatly structured and clearly drafted.\n\n2. The authors have comprehensively explained both the problem setup and their proposed solutions.\n\n3. 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:\n\n1. 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.\n2. 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.\n3. 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?\n4. 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:\n    * 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.\n    * 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.\n5. 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?\n6. 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.\n7. 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?\n8. Some other relevant works related to online distribution shift should be considered to be explored and discussed, such as:\n\n    * Kumar et al., Understanding Self-Training for Gradual Domain Adaptation;\n    * Zhang et al., Adapting to Continuous Covariate Shift via Online Density Ratio Estimation;\n    * Zhou et al., Online Continual Adaptation with Active Self-Training.\n9. I wonder what are the \"NA\"s mean in the experimental tables?\n10. I am unsure about the FLH and Alligator algorithms (line 193). Could the authors briefly introduce these algorithms and explain their function?\n11. line 196: The averaging within \"intervals\" xxx, can the author detail explain what the \"intervals\" is? and how to divide these intervals.\n12. The paper can be further refined to enhance readability, and there are several typographical errors:\n     * line 31: Wu et al. [76] only controls -> Wu et al. [76] only control\n     * line 35: However their approach based on -> However, their approach is based on\n     * line 82: the extend of distribution drift -> the extent of distribution drift.\n     * line 94: i.e. -> i.e.,\n     * line 96: respectively -> , respectively\n     * line 314: i.e. -> i.e.,\n     * line 1055: $\\alpha_t = 1-\\alpha_{t-1}$.\n     * line 1079: to better performance -> to a better performance", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are thankful for Reviewer Cpae’s constructive feedback and positive perspective on the work. We have incorporated your feedback, and believe they have greatly enhanced the manuscript. \n\n>**... \"sample efficient\"...**\n\nWe apologize for the confusion. The term “sample efficient” in the theoretical context of online learning means that the regret upper bounds of our algorithms match the information-theoretic lower bounds. In experimental context, we’re referring to the finding that in the low amount of data regime (on the left of Figure 2 a/b), our method performs significantly better than prior works, and thus is more efficient in the number of labeled samples required. We’ll clarify this in the introduction. \n\n>**… Lipschitz constant G…**\n\nWe would like to clarify one confusion about the Lipschitzness. We note that the Lipschitzness of the losses are required only wrt the re-weighting measure $p \\in \\Delta_K$ (see Assumption 2) and *not* wrt the covariate $x$. The effect of the covariate space is marginalized away via expectation over the random draw of (x,y) pairs (ref. Lines 173-177). Hence the discontinuities in the decisions of the classifier across the feature space do not blow up the Lipschitz constant wrt re-weighting measure to infinity. We believe that this form of Lipschitzness is milder than imposing smoothness constraints on the loss across the feature space. \n\n>**In Theorem 6 ...**\n\nWhile we prove the above result for finite hypothesis sets, the extension to infinite sets is straight-forward by standard covering net arguments [70]. In doing so, the terms of the form $\\log |\\mathcal{H}|$ in Theorem 6 will be replaced by the Rademacher complexity of the hypothesis class. In fact, we initially had a remark on this, but removed it due to space constraints. We will add this remark in the final version.\n\n>**... more fitting title…**\n\nWe apologize if the title is misleading. The “practical algorithms” refers only to the algorithms used in the unsupervised setting. We will clarify this in the introduction. We are also happy to consider changing the title in the final version.  \n\n>**... best-of-both worlds…**\n\nThe phrase best-of-both worlds used in line 55 foreshadows the arguments in Section 3, especially lines 144-148. \n\nWe briefly describe it here. The work of [76] allows us to use expressive initial classifiers such as DNN while only controlling the *static* regret against a fixed classifier (though their theoretical guarantees hinge on convexity of losses). The work of [8] allows to control for dynamic regret against a sequence of classifiers while imposing restrictive *convexity* assumptions on the losses. The notion of dynamic regret is more adequate than static regret particularly in the face of distribution shifts.  Our work combines the best features of both of the above works by controlling for dynamic regret while not imposing restrictive convexity assumptions thereby allowing us to exploit the power of highly expressive classifiers. \n\n>**... optimization of the 2-norm …**\n\nIndeed, we may consider alternative losses like KL-divergence for tracking the marginals. In fact, if we use KL-divergence instead, we would arrive at similar guarantees as in Theorem 2. This is due to the fact that KL loss belongs to the family of exp-concave functions [12]. The  regret rates for KL and squared loss regression are the same (see [4]). Further, online regression with KL loss involves inverting a matrix, which will result in increased run-time in comparison to squared loss regression. Due to these reasons we didn’t pursue the direction of KL-loss. On the other hand, the minimax regret guarantees of Theorems 2 and 5 indicate that squared loss is sufficient to get optimal rates.\n\n>**... other relevant works …**\n\nWe thank the reviewer for bringing relevant works to our attention. We will include these references in the updated draft. \n\n>**... \"NA\"s …?**\n\nNA stands for \"Not Applicable,\" indicating that base classifiers don't use label marginal estimates for reweighting predictions. Thus, the mean square error in label marginal estimate (the row MSE) is not applicable to these classifiers. We thank the reviewer for pointing out this potential confusion, and will clarify it in the updated draft. \n\n>**... FLH and Alligator …**\n\nBoth algorithms [7, 38] can be used as online regression algorithms in the sense defined in Definition 1. At a high level, both are basically ensemble methods. They maintain a pool of online averaging base learners. Each base learner only averages a subset of past observations in the rounds {1,2,...,T}. At any round the base learners submit their predictions to a meta-algorithm, which then combines the individual predictions via the ensemble method of Exponetiated Weighted Averages. \n\nA primary challenge in the online regression problem is to decide how much of the past data we must average at each time step. FLH or Aligator optimally and adaptively average over just the right amount of past data points.\n\n>**... the \"intervals\" …**\n\nBy intervals, we are referring to the intervals in which the ground truth label marginals drift sufficiently slowly. Such intervals are only known to an unrealistic oracle. As the reviewer points out, we do not have such oracle information about the low drift intervals in practice. The remarkable property of online regression algorithms is that they can incur a total estimation error that is closely comparable to the error that would have been made by an ideal estimator with the aforementioned oracle knowledge. We refer the reviewer to [4] on more formal details about such oracle inequalities.\n\n>**... typographical errors**\n\nWe thank the reviewer for pointing out these typos and will correct them in the final draft.\n"}, {"review_id": "EoM3TySIIO", "reviewer": "Reviewer_Gcxc", "summary": "this paper applies techniques from online regression oracles to tackle the problems of unsupervised and supervised label shift, where the marginal probabilities of the labels can be changed over time by an adversary. ", "questions": "3 the lowerbounds do seem to be of a slightly different form than the upperbounds. does this matter? why (not)? why is it essential to assume V_T is smaller than T*c for some c for the lowerbounds? ", "limitations": "none", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "the main contributions include:\nC1 an algorithm that adapts to the changing labels without knowing the parameter V_T\nC2 an algorithm whose online learning assumptions are verified\nC3 an algorithm compatible with black box access to the learner, to enable deep neural networks and decision trees to be used as learners\nexperiments illustrate the proposed algorithm is promising\n\nthe paper is well written and extensive experiments are performed with many baselines", "weaknesses": "some minor issues:\n\n1 figure 2 does not explain what the uncertainty bands are. I assume these are std's or are they standard errors? similairly for the tables. figure 2c misses erroprbars or are they not visible? \n\n2 the appendix is extremely long, I did not have time to go over all the details, and I am inclined to suggest a full paper would be better reviewed at a journal. I thought its a shame that fig. 3 (appendix) which shows interesting trends is not included in the main body. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for your positive feedback and for championing our paper. We are glad that you find the paper well-written and appreciate the experiments. \n\n>**1 figure 2 does not explain what the uncertainty bands are. I assume these are std's or are they standard errors? similairly for the tables. figure 2c misses erroprbars or are they not visible?**\n\nIndeed, the uncertainty bands are standard deviations. We thank the reviewer for bringing the potential confusion to our attention, and we will clarify this in the updated draft. We decided to leave out the error bars on figure 2c for visual clarity as they are insignificant compared to the advantage in our method. \n\n>**I thought its a shame that fig. 3 (appendix) which shows interesting trends is not included in the main body.**\n\nWe thank the reviewer for appreciating this finding from the supplementary materials. We had to make a hard choice given space constraints. If given an extra page for the final version, we will include this figure in the main paper. \n\n>**3 the lowerbounds do seem to be of a slightly different form than the upperbounds. does this matter? why (not)? why is it essential to assume $V_T$ is smaller than $T*c$ for some $c$ for the lowerbounds?**\n\nIt is a known result from dynamic regret minimization literature that if the variation $V_T$ of the target marginals is not sublinear in $T$ , one cannot hope to get sublinear regret bounds (see for eg. [1, 2, 3]). The intuition is that when $V_T$ is not sublinear, the target moves too fast so that it is impossible to track the target by an online learner.\n\n\n[1] Lijun Zhang,  Shiyin Lu and  Zhi-Hua Zhou. Adaptive online learning in dynamic  environments. NeurIPS 2018\n\n[2] Dheeraj Baby and Yu-Xiang Wang. Optimal Dynamic Regret in Exp-Concave Online Learning. COLT 2021\n\n[3] Omar Besbes, Yonatan Gur and Assaf Zeevi. Non-stationary Stochastic Optimization. Operations research, 2015\n"}, {"review_id": "Gmw6VdpW99", "reviewer": "Reviewer_hAtb", "summary": "The authors study the important problem of learning in an online setting.\nIn particular, they focus on two important problems:\n- Online Unsupervised learning with Label Shift (UOLS)\n- Online Supervised Learning with Label shift (SOLS)\nIn both cases, they assume, as in previous work, that the distribution of the samples can change at each step, however, the marginal distribution of the covariate X  given the label Y is the same. Their algorithm is adaptive and does not require knowledge of the distribution drift. They show that their results on dynamic regret are (almost) optimal in a minimax sense. Unlike previous work, they do not require a convexity assumption on the family of the losses, which is an important technical contribution. They corroborate their theoretical findings with experiments.\n\n\n\n", "questions": "-  With respect to Remark 10: The black box algorithm of appendix D can be used to improve the running time, as it detects intervals in which there is little change and we do not need to train again.  \nBy using a similar argument, is it possible to say that if there is a big change in the label probabilities, then the older data is significantly less useful, and we can stop storing it? ", "limitations": "The authors discuss limitations, assumptions, and possible future work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Main strengths:\n\n- The paper is very well written, easy to follow, and the results are sound. The assumptions used are discussed and well-motivated.\n\n- They provide a major technical contribution in dropping the convexity assumption of the previous work. \n\n- They show the (almost) tightness of their results in a minimax sense.\n\n- They show an interesting algorithm to reduce the number of training steps in the SOLS setting so that they do not need to train a new model at each step. This is a very interesting result, as this is a common problem of many previous works of learning with distribution drift.\n\n- Their theoretical findings are corroborated by extensive experiments. Moreover, I appreciate the effort of the authors to address many problems related to how to obtain the optimal minimax regret efficiently in practice. (Appendix D).\n\n\n", "weaknesses": "The results are limited to changes in the probability of obtaining an element of a certain class (label shift). This is only a specific setting of learning with distribution drift. Their technique looks limited to this specific setting, as it revolves around estimating (regression) the class probabilities. It does not seem straightforward to extend this work or use the results of this work for the more general problem of learning with generic distribution drift. \n\nThe experiments are only run with respect to data where synthetic drift is introduced.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your thoughtful feedback. We are glad that you find the paper well-written, and are grateful that you appreciate the experimental and theoretical results. \n\n>**The results are limited to changes in the probability of obtaining an element of a certain class (label shift). This is only a specific setting of learning with distribution drift. Their technique looks limited to this specific setting, as it revolves around estimating (regression) the class probabilities. It does not seem straightforward to extend this work or use the results of this work for the more general problem of learning with generic distribution drift.**\n\nAs the reviewer correctly points out, our methods are applicable to the setting of label shift. We documented this in Appendix A (Limitations section). However, we note that absent causal assumptions on the distribution shift, it is in general impossible to do unsupervised domain adaptation. It is indeed an interesting future direction to extend our work to other types of shifts we see in an online setting. Our work only takes the first steps towards this bigger goal.\n\n>**The experiments are only run with respect to data where synthetic drift is introduced.**\n\nIn fact, we provide experimental results on the SHL datasets in the appendix where the shift is natural. We believe that this demonstrates the superiority of our method over other alternatives even under real shift. \n\n>**With respect to Remark 10: The black box algorithm of appendix D can be used to improve the running time, as it detects intervals in which there is little change and we do not need to train again. By using a similar argument, is it possible to say that if there is a big change in the label probabilities, then the older data is significantly less useful, and we can stop storing it?**\n\nAs the reviewer mentioned, if there is a big change in the label probabilities, then the older data is significantly less useful. However, there is still a possibility of older data becoming more relevant at a later point of time. Thus to prevent catastrophic forgetting we keep the old data around.\n"}, {"review_id": "tbOwsjPNQg", "reviewer": "Reviewer_vA3S", "summary": "The general scope is online classifier learning under online label shift where the key assumption is that the class conditionals $Q(x|y)$ are invariant. The paper focuses on both unsupervised and supervised problems, which they coined as Unsupervised Online Label Shift (UOLS) and Supervised Online Label Shift (SOLS).\n\nKey previous works in the UOLS problem [76, 8] setup a regret function and adapt the initial classifier via minimising the regret function over time.  [76] optimises the classifier via reweighting the predicted distribution $\\hat{q}_t$. [8] retrains the classifier at every step. However, both suffer from convexity issues of the losses. This paper integrates the best of both [76] and [8] in a single framework. On top of that they avoid any previous convexity issue by reducing the online label shift problem to the problem of online regression of the class marginal distribution function. Tight theoretical bounds under the usual Lipschitz condition are provided.\n\nThe second part of the paper is an extension of the approach from the UOLS problem to the SOLS problem. The main contribution here is that theoretical bounds in (weighted) Empirical Risk Minimization are generalised to the SOLS context. Other contributions involve in making online model training faster without compromising the theoretical bounds too much.\n\nFinally, there is an extensive empirical study based on well known datasets. However, in many of the datasets used for the experiments, the label shift dynamics are simulated.", "questions": "I do not have any major question. The paper is very good to me, except for a few practical concerns raised in the Weaknesses section.", "limitations": "I do not see any potential negative societal impact of the work.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is very well written and very detailed. The authors were very clear of their contributions and limitations of the proposed approaches.\n\nIn my view, the key novelty of the paper is at reformulating the online label shift problem as the problem of online regression of the marginal distribution function, which previous works have overlooked. Everything else in the paper develops from that idea in naturally. This key novelty is clever because the new problem can be solved efficiently with existing tools.\n\nThe provided bounds appear to be quite tight in terms of complexity, although I am not sure whether in practice the coefficient of the highest order term plays a significant role. Proofs in the appendices are simple applications of probabilistic tools, concentration theories and a few key results in online learning theories. I was able to follow without any major trouble.\n\nThe finding in appendix G.6 is interesting, which provides an evidence that retraining does not work better than reweighting, despite an additional computational cost for retraining.", "weaknesses": "Although well acknowledged in the paper, the fact that the approach, like [8], requires memory that scales linearly with time is quite a concern from a practical point of view. It would be good to have some quantification results regarding memory usage in the experiments.\n\nAlthough the paper addresses online label shift, among 6 datasets used in the experiments for UOLS and SOLS, 5 of them use simulated label shift data. Only SHL contains real-world label shift data.\n\nI understand that the scope of the paper is online label shift where $Q_t(x|y)$ is unchanged over time. Still I find this scope is rather restrictive compared to real-world data. In the data collection business that I have been involved, data are usually collected from many sources, with large differences in collection periods and frequencies of data being collected per source. With external factors like that it is hard to assume that $Q_t(x|y)$ is unchanged over time. The SHL dataset used in section 5 seems to be the only dataset in which the label shift part of the data is real. However, given that it was collected by only 3 participants, it is hard to justify whether the dataset reflects what happens in the real world.\n\nPerhaps the authors could try with some recent consumer-related datasets (e.g. clothes, food) that contain both pre-Covid and post-Covid periods? During the Covid-19 pandemic, so many shops closed, leading to a large-scale gradual decrement of data that can be collected. Since 2022, many shops have reopened, leading to a gradual increment of collected data.\n\nMaybe a typo. However, on line 112, why does $\\delta$ not play a role in the big $\\tilde{O}$ function?\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your generous appraisal of the main theoretical idea. We are glad that you find the paper detailed and well-written. \n\n>**Although well acknowledged in the paper, the fact that the approach, like [8], requires memory that scales linearly with time is quite a concern from a practical point of view. It would be good to have some quantification results regarding memory usage in the experiments**\n\nWe will add a table detailing the memory requirement in the appendix. \n\n>**Although the paper addresses online label shift, among 6 datasets used in the experiments for UOLS and SOLS, 5 of them use simulated label shift data. Only SHL contains real-world label shift data… The SHL dataset used in section 5 seems to be the only dataset in which the label shift part of the data is real… Perhaps the authors could try with some recent consumer-related datasets**\n\nWe thank the reviewer for suggesting consumer-related datasets as an interesting potential benchmark for our problem. Indeed, curating more real datasets where the label shift assumption is approximately met would be interesting. We are looking into suitable datasets, and will leave curation of these relevant datasets to subsequent works. \n\n>**Maybe a typo. However, on line 112, why does $\\delta$ not play a role in the $\\tilde O$ function?**\n\nFactors of $\\log(1/\\delta)$ are subsumed in $\\tilde O$ as described in Line 90. We can remind the reader in-place in the updated draft."}]

Author rebuttal:
We are thankful to the reviewers for their careful consideration of our work and thoughtful feedback. We are glad to find that the reviewers appreciate our work and gave positive scores (8, 8, 7, 4). We also appreciate that all reviewers find the paper well-written. While reviewer Cpae has some clarification questions and concerns, we believe that they are addressable in this round of rebuttal. We have adjusted the manuscript as suggested, and believe the changes has improved the exposition. Please let us know if there are any remaining concerns. We will be happy to answer any further questions you may have.


Meta-review: In this paper, the authors investigate online label shift under supervised and unsupervised settings. The goal is to develop algorithms that adapts to the non-stationarity in the label drift. Under the Lipschitzness condition, the authors reduce the adaptation problem to online regression, and then leverage existing oracles to establish minimax optimal dynamic regret rates.

This paper is easy to follow, and the algorithms are well-motivated. Compared to prior work, the authors get rid of the convexity assumption, which is a significant advantage. By doing so, they are able to leverage advanced deep models to achieve superior performance. On the other hand, the authors should further polish their paper based on the suggestions from the reviewers.
Decision: Accept (spotlight)