An Adaptive Algorithm for Learning with Unknown Distribution Drift
Authors: Alessio Mazzetto
Eli Upfal
Venue: NeurIPS 2023 poster (2023)
Keywords: statistical learning
learning theory
machine learning
supervised learning
non-stationary
transfer learning
distribution drift
TL;DR: We develop and analyze an adaptive method for learning given a sequence of independent observations from a drifting distribution.

Abstract: We develop and analyze a general technique for learning with an unknown distribution drift. Given a sequence of independent observations from the last $T$ steps of a drifting distribution, our algorithm agnostically learns a family of functions with respect to the current distribution at time $T$. Unlike previous work, our technique does not require prior knowledge about the magnitude of the drift. Instead, the algorithm adapts to the sample data. Without explicitly estimating the drift, the algorithm learns a family of functions with almost the same error as a learning algorithm that knows the magnitude of the drift in advance. Furthermore, since our algorithm adapts to the data, it can guarantee a better learning error than an algorithm that relies on loose bounds on the drift. We demonstrate the application of our technique in two fundamental learning scenarios: binary classification and linear regression.

An Adaptive Algorithm for Learning with Unknown Distribution Drift
Alessio Mazzetto
Eli Upfal Brown University
Brown University
Abstract
We develop and analyze a general technique for learning with an unknown distri- bution drift. Given a sequence of independent observations from the last 7 steps of drifting distribution, our algorithm agnostically learns a family of functions with respect to the current distribution at time T. Unlike previous work, tech- nique does not require prior knowledge about the magnitude of the drift. Instead, the algorithm adapts to the sample data. Without explicitly estimating the drift, the algorithm learns a family of functions with almost the same error as a learning algorithm that knows the magnitude of the drift in advance. Furthermore, since our algorithm adapts to the data, it can guarantee a better learning error than an algorithm that relies on loose bounds on the drift. We demonstrate the application of our technique in two fundamental learning scenarios: binary classification and linear regression.
Introduction
Standard statistical learning models (such PAC learning) assume independent and identically distributed training set, and evaluate the performance their algorithms with respect to the same distribution the training set [Vapnik] 1998 van de Geer 2000, Shalev-Shwartz and Ben-David] 2014 Wainwright [019]. However, in many practical applications, such as weather forecast, fi- nance prediction or consumer preference analysis, the training data drawn from a non-stationary distribution that drifts in time. In this work, we consider more general setting where the samples are still independent, but their distribution can change over time. To obtain accurate results, the learning algorithm needs to adjust to the distribution drift occurring in the input.
This framework has been extensively studied in the literature (Helmbold and Long 1991 Bartlett 1992 Helmbold and Long 1994 Barve and Long 1996 1997]. This line of research culminated in showing that as long as the total variation distance of two consecutive distributions bounded by A, there exists an algorithm that agnostically learns a family of binary classifiers with VC dimension with expected eтror (((A)) [Long] 1998]. which can be shown to be tight. These results were generalized in the work of Mohri and Muñoz Medina (2012 to address any family of functions with bounded Rademacher complexity and to use a finer problem-dependent distance between distribu- tions called discrepancy, originally introduced in the context of domain adaptation [Mansour al.) 2009
The core idea of the aforementioned work is to learn by using a number of previous samples that minimizes the trade-off between the error due to the variance of the estimation (statistical error), and the error due to the drifting of the samples with respect to the current distribution (drift error). If the algorithm trains using only few recent observations, the statistical error will be large. If the algorithm uses a larger training set, including not very recent observations, the drift error will be large. For example, if the algorithm uses the most recent training point, the hypothesis class has VC-dimension v, and the distribution drift in each step is bounded by A, then the statistical error is v//v/r) and the drift error is (rr The trade-off with respect to r is optimized for r (((A2/v)-1/3) giving ((vA)1/3) error, as mentioned before. This, as well as similar approaches
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

in the literature, requires an upper bound to the magnitude of the drift and resolves the trade-off between the statistical and drift eπrors based this knowledge. As noted in previous work [Hanneke] and Yang] 2019), it is an open problem to develop an algorithm that adapts to the training set and does not rely on prior knowledge about the drift, whose solution would lead to the practical applicability of those ideas.
Our work resolves this open problem. Our algorithm does not require any prior knowledge of the magnitude of the drift, and it adapts based on the input data. Without explicitly estimating the drift (which often impossible), the algorithm agnostically learns family of functions with the same error guarantee as an algorithm that knows the exact magnitude of the drift in advance. Our approach has two advantages: eliminates the, often unrealistic, requirement of having bound on the drift, and it gives better results when the drift bounds are not tight. We showcase our algorithm in two important learning settings: binary classification and linear regression.
Preliminary
Let (Z,A) be measurable space. Let Zi...., Zr be sequence of mutually independent random variables on Z distributed according to Pi...., Pr respectively, i.e. Z, ~ Pt for I T. For r S T, denote by Pf the average distribution of the most recent distributions PT Pr-rt1...., Pr:
T
(A)
Σ P((A)
A
We set
Pr to be the corresponding empirical distribution over the random variables ZT ZT:
(A) 12 E -rt A
Let F be a class of measurable functions from to R. For f E F, and any distributions P.Q on A), we let
P()) = E ((2)) fdP, Z~P
P - sup sup -(f)-Q()) JEF
The norm ||+ is a notion of discrepancy introduced by the work of Mohri and Muñoz Medina [2122] to quantify the error due to the distribution shift with respect to a family of functions J, and is based on previous work on domain adaptation [Mansour al., 2009].
The goal is to estimate Pf(f) for all f E FF using the random variables ZI...., Zr. Let 1 S S T, and suppose that do this estimate by considering the empirical values induced by the most recent r random variables. Then, by using triangle inequality, we have the following decomposition
ZT....,Zy.....
EE| Pr
Pr ||== <
P Pr IF + Pr PTII=
statistical error
drift emrr
The first term of the upper bound is the expected statistical error of the estimation, and quantifies how accurately the empirical values (fr f F) approximate the expectation of each function according Pr. The second term || - IF of the upper bound represents the drift error. Intuitively, the statistical error decreases by considering more samples, whereas the drift error can potentially increase since we are considering distributions that are further away from our current distribution. We are looking for the value of r that balances this trade-off between statistical error and drift error.
2.1 Statistical Error
Since our results revolve around learning class of functions F. we first need to assume that F is "learnable". i.e. the statistical error can be bounded as function of r. For concreteness, we use the following standard assumption that the family of F satisfies the standard machine learning uniform convergence requirement with rate (T).
Assumption 1. (Uniform Convergence). There exists non-negative constants Cr and Cr such that for any fixed r I T and (0,1), it holds
CF Vr
E3 PT
1
<

---

and with probability at least 8, we have
CF.1 Vr
C In(1/o)
PF PT S
The learnability of a family of functions F is extensively studied topic in the statistical learning literature (e.g., [Bousquet et al., 2003 Wainwright 2019]). For a family of binary functions, the above assumption is equivalent
having finite VC-dimension, in which case CF,1 - (vv) and CF.2 = (1). For a general family of functions F, a sufficient requirement is that the Rademacher complexity of the first samples is O(r-//2 and the range of any function in F is uniformly bounded. There is nothing special about the rate (/23).). It is possible to adapt our analysis to any rate O(r=)) with a (0, 1) by modifying the constants of our algorithm.
2.2 Quantifying the Drift Error
While for many classes F, it is possible to provide an upper bound to the statistical error by using standard statistical learning theory tools, the drift error is unknown and challenging to estimate. The literature used different approaches to quantify the drift error. By using triangle inequality, it is possible to show that for any r S we have the following upper bounds the drift error:
- - S
PT Pr- S max Pr - Pr- S tCr
Pr
Σ P -et-t-Pr-eiie Pr- (2)
In long line of research (e.g., (Bartlett 1992 Long 1998
Mohri and Muñoz Medina 2012 Han-
neke and Yang 2.19)), it is assumed that an upper bound to the drift error is known apriori. One of the most used assumption is that there exists known upper bound A to the discrepancy between any two consecutive distributions, in which case can upper bound Σi= Pr-t P1-ttille with rA. In this case, for a binary family F with VC-dimension v,, we obtain that:
E| PT Pf S +rA
and we can choose the value of r that minimizes this upper bound. Since these algorithms rely on an unrealistic assumption that an upper bound to the drift is known priori, they are not usable in practice. an open problem to provide competitive algorithm that can choose r adaptively and it is oblivious to the magnitude of the drift.
Another sequence of work [Mohri and Muñoz Medina 2012 Awasthi et al. 2023 relaxes the problem setting assuming that the algorithm can observe multiple samples from each distribution Pl...., Pr. In this case, they can provably estimate the discrepancies between different distribu- tions, and compute weighting of the samples that minimizes trade-off between the statistical error and the estimated discrepancies. This strategy does not apply to our more general setting, as can have access most one sample from each distribution.
Surprisingly, we show that we can adaptively choose the value of r to minimize the trade-off between statistical error and drift error without explicitly estimating the discrepancy. Noticeably, our method does not require any additional assumption on the drift. The only requirement for our algorithm is that we can compute the norm ||l from a of samples. This is formalized as follows.
Assumption 2. (Computability). There exists procedure that computes ||PP r T/2.
PP ||=
for any
In general, the hardness of computing the norm ||l|b> depends the family F. This challenge is also common in previous work that uses this norm to quantify the distribution drift [Mansour et al.) 2009 Awasthi et al.] 2023). In this paper, we provide examples of important learning settings where this assumption is satisfied: binary classification with zero-one loss and linear regression with squared loss.
3 Main Result
Under those assumption, we prove the following theorem, which is our main result.

---

Theorem 1. Let 8 E (0, Let Assumptions I and 2 hold. Given Zi.... Zr. Algorithm
outputs
value $ T such that with probability least
6, it holds that
CF VT
log(log(r + 1)/0)
| 1=
min
+
max PT Pr-1 C
In order to appreciate this theorem, we can observe the following. If we learn using the most recent
r samples, similarly to (I) we have the following error decomposition
Pr PTll= S P| Prll= + Pr Pfll=
By using Assumption T and we have that with probability at least - 5 it holds that
CF,11 + +=2V log(1/0) Vr
P 1F
max PT Pr- [<r
(3)
Theorem T guarantees a learning error that is essentially within a multiplicative constant factor as good as the upper bound obtained by selecting the optimal choice of r in (3). This result provides an affirmative answer the open problem posed by Haaneke and Yang [019], that asked if it (3) The upper bound of the
was possible to adaptively choose the value of r that minimizes
theorem contains negligible additional factor log (og(r+1) within the logarithm due to the union bound required to consider multiple candidate values of r. As further evidence of the efficiency of our algorithm, assume that there is no drift, and we are in the usual i.i.d. setting where P1
Pr. In this setting, the following corollary immediately follows from Theorem byy setting the drift error equal O.
and also assume that P1 = =.... Pr. With probability at least - 8. the window size & computed by Algorithm [ satisfies
Corollary 2. Consider the setting of Theorem I
(
Pr - PT PP--Pill= = 0 CF VT
log(log(T (T' + 1)/0)
+C22
T
Observe that in the iidd case, Assumption D iiplics that with probability at least 1 - 8, holds || - Pfll== < Cya/vT + C2.2y/lllog (oo////og///// Corollary shows that with our algorithm we obtain a result that is competitive except for negligible extra factor O T) within the logarithm. We want to emphasize that our algorithm does not know in advance whether the data is i.id. or drifting, and this factor is the small cost of our algorithm adapt between those two cases.
4 Algorithm
We describe an algorithm that attains the results of Theorem 1 Throughout the remaining of this section, we let Assumptions I hold. In particular, the algorithm has access to constants Cy.1 and CF.2 2 that satisfy this assumption. The main challenge is the fact that the drift error || P% || unknown for any r > 1, and challenging to quantify since we have only a single sample 2T ~ Pr.
We first provide an informal description of the algorithm. Our algorithm revolves around the fol- lowing strategy. We do not try to estimate the drift. Instead, we try to assess whether increasing the sample size can yield better upper bound on the error. Recall that given the most recent samples, we have the following upper bound on the error,
E El|Pr P Palls CJ + IPr -f Vr
44)
The algorithm cannot evaluate 4 since the drift component, P| Pf unknown. Our key idea is to compare the difference in the upper bound on the error when using the latest 2r or samples:
CFa
CF.1 ) + (11P: - P? Pr Pfllx) S V2r Vr
(FF1
CF.1 /2r Vr
+ +IP
P
(5)
We prove stronger result. The original formulation of the question uses the looser upper bound Ex" Pr-1- Pr-c4ill to the drift error in B) which can be significantly worse as shown in an exam-
ple of Section

---

The last step follows from the triangle inequality: || - Pf S P + - ||. By considering the latest 2r samples rather than r samples, we can see from 5 that the statistical emor decreases, and the difference in drift error can be upper bounded by ||P Pfl.. We can estimate P P I|5 using ||P? - P |r within expected error O(Cr./Vr as depends on 2 r samples. This suggests the following algorithm. Let be the current sample size considered by the algorithm. The algorithm starts from r equal to 1, and doubles the sample size as long as |PPG - || is small. If ||PT P ||= is big enough, substantial drift must have occurred in the distributions Pr-2r+1,- 12-4+11....... Pr, and we can show that this implies that max
- is also large. When this happens, can stop algorithm and return the current sample size.
For a formal description of the algorithm, let E (0, 1) denote the probability of failure of our algorithm, and let ri = 2", for i 2 0, be the size of the training set used by the algorithm at iteration i 4 1. For case of notation, we set
and
S(r,6) CF Vr
2ln(log2(r) + 10)
+ Cray
(6)
The proofs of the following propositions appear in the Appendix A
Proposition 3. With probability at least 1 6, the following event holds:
P
P | S 6))
Vi
We assume that the event of Proposition 3 holds, otherwise our algorithm fails (with probability
< 5). Our algorithm considers the following inflated upper bound U (r; 5) |IPs Prll= defined as follows
Urr 8) = 21 S(r, 6) + P| - P/
Proposition 3 Simplies that with probability at least 8 for any 2 O, we have
U(r,,)) == S(r,, 6) + P| P |P P7 P 1f -iill
We use this value as an upper bound that our algorithm guarantees if we choose sample size ri- We observe that with respect to (4) the upper bound of the algorithm also contains an additional term that is proportional to /log(1/ 1/0) for the high-probability guarantee, and a term proportional to Vlog log r; that is necessary for the union bound across all possible window sizes r; for 2 O. This union bound required
we need to have a correct estimation for all possible sample sizes in order to assure that the algorithm takes correct decision at each step. The constant factor in front of the upper bound on the statistical error S(r;, d) a technical detail that allows taking into account the error of the estimation of the difference in drift error.
We want compare the upper bound U (ri, 6) with the upper bound ((r++1, 6) obtained by doubling the current sample size rs. As we previously discussed, it is possible to show that if ||P P + || sufficiently small, then 5) < Urr,, 8), and this intuition is formalized in the following proposition.
Proposition 4. Assume that the event of Proposition Inniiiionnoole Tholds and let i 2
If PP' || I 45(r,,) then U(r++1,5) S U (r., 8).
The algorithm works as follows. Starting from i = O, we iteratively increase by one while [|P P || < 4S(r,, 8). There are two cases. In the first case, we reach
[log2 T]. and this implies that r:+1 T. In this case, the algorithm returns ri, and Proposition 4 guarantees that the sample size returned by the algorithm is as good as any previously considered sample size. In the second case, we reach a value of i such that |IP - 1f++ 5 > 6)) this case, we return ri, and we can still prove that this is good choice. In fact, as shown in the next proposition, this terminating condition implies a lower bound maxtcr;:1 Pr Pr-illz, thus any estimation with a number of recent samples greater equal to T:41 could have non-negligible drift error.
5

---

Algorithm 1: Adaptive Learning Algorithm under Drift
<-0 0:
while r < <T/2do
[P - -P7 177*11x || I 45(r;,0) then
i i+il;
end else
return ;
end end return r;
Proposition Assume that the event of Proposition holds, and assume that there exists i such that |P] Tpr " I|
4S(r;, 5), then max Pr- S(r;, 8).
The pseudo-code of the algorithm is reported Algorithm The algorithm receives in input the samples ZI,..., ZT, and returns an integer f {I...., T'} that satisfies Theorem
Proof of Theorem 7 We assume that the event of Proposition 3 holds. It doesn't, say that = 2' for j 2 be the value
algorithm fails, and this happens with probability < 5. Let returned by the algorithm when it terminates. We remind that algorithm guarantees upper bound (r 8) 2 Pr - P7 ||> to the learning error by using ry samples. Let r be the value of that minimizes this expression
r argmin "ST
21 S(r, 8) + max Pr Pr-ellz) ber
and let 8 be the minimum value of this expression, i.c.
B" 21 S(r", 8) max| Pr Pr-
be any fixed optimal sample size, where remind the definition U from 7 The first observation that the right-hand side of the inequality in Theorem is O(B"). Therefore, in order to prove the theorem, is sufficient to show that U (rj 8) B OT)..
We distinguish two cases: (a) r* < 2r,, and (b) r" 2 2r,- We first consider case (a). We let
be the largest integer such that тk S r" Since f* < 2r,. it holds that k S j. Since our algorithm returned ry. Proposition 4 applics for = O.....J . 1, thus U(r,, 6) I U(rk, We have that:
U(r,,)
U(r. 8)
B* < B²
(8)
We observe that U(rk,ō) 5) B=
21S(rk, 5) + Pr P ||=
215(rk, 8) + maxter,
Pr - PT F|
215(r* max Pr Pr-
21S(r 8) + maxter Pp Pr
S(rk, 8) max PT Pr-cll
+153,
S(r*, 5) maxter || Prl
where the first inequality is due to (2). and the last inequality due to the fact that l' I r" < 2rk
by definition of rk- By using the above inequality in (8), obtain that (rr,,))/ < 3.
We consider case (b). Since T 2 r' > 2r, rj+1, the algorithm returned ry because |P P 4,(r, 8). Using Proposition
5 we have
max Pr Pr max PP Pr- > S(r,, 6415t1
[<r
Therefore, we have that
21s(r,, 8) Pr. P ||
B+ 21S(r*, 8) maxi
Pr - Pr-
21S(r;, 0)
maxi<r;
Pr. Pr-
21S(r;, 8)
S(r;,5) +
maxter- Pr - Pr-tlf
maXier
Pr Pr-
This concludes the proof.

---

5 Binary Classification with Distribution Drift
In this section, we show an application of Theorem for the fundamental statistical learning problem of agnostic learning a family of binary classifiers. Let Z X x V. where X' is the feature space, and y = {0, I is the label space, i.c. Z₁ = (Xe, Yi). A hypothesis class H. is a class of functions h: X' Y that classify the feature space X. Given a point (æ:, v) X x y and function h E H, the risk of h on (z. y) is defined through the following function (x, y) = 1 (u)(())))- We work with the class of functions F = (L, h E H}.
heth" = arg Pr(LA) be a function with minimum expected risk with respect to the current distribution Pr. We want to use Theorem ! to find a function h E H such that Pr is close to Pr(Lx.). ). Let y be the VC dimension of H. The VC dimension describes the complexity of the family H. and it is used to quantify the statistical error. In particular, using standard learning tools, it is possible to show that the family F satisfies Assumption I on the sample complexity with constants Cz = ((Vv) and CF = O(1) (e.g.. (Mohri et al. 2018)).
Finally, to satisfy Assumption 2 we need to exhibit a procedure that for r < T/2, outputs the quantity |P; |P2 ||> ||= This quantity is also referred as y'ddiscrepancy between the empirical distributions PT. and P.r in previous work on transfer learning [Mohri and Muñoz Medina 2012). We can adapt strategy from Ban-D et al. [2010] our setting and show that possible to compute it by solving an empirical risk minimization problem. We say that a hypothesis class H is computationally tractable if given finite set of points from X V, there exists an algorithm that returns a hypothesis h that achieves the minimum risk over this set of points.
Lemma 6. Assume that H is symmetric, iee. h E H = 1- h E H. For S T/2, it holds
T Σ
T-r
PPG
P
1
inf hEH
1
(x 1- - Y)) +-
Σ 1-
In(X,, Yi)
Given the minimum in Lemma 6 can be computed by solving an empirical risk minimization over the most recent 2r points, where we flip the label of half of those points, i.e. we use the points (Xr, 1-)7). Thus, if H is computationally tractable and symmetric, Assumption Cholds. This is indeed true for many hypoth- esis class, e.g., hyperplanes, axis-aligned rectangles, or threshold functions. However, the empirical risk minimization problem could be expensive to solve exactly, but as we discuss in Section 8 is possible to modify the algorithm to allow for approximation of |IP5 | ||F.
(XT-2r41 1r-22411 (7-2r+))...... (XT-r, Y..), (XT-r+1, 1- 1-Yr-r+1),
Our main result for binary classification is given in the following theorem:
Theorem 7. Let H. be a computationally tractable and symmetric binary class with VC dimension
Let F {Ln h E H}. Let f & T be output of Algoritlum I with input Zi...., ZT using the family F. Let h argmin (T,) be an empirical risk minimizer over the most recent samples. With probability at least 1 - 6, the following holds:
log(log(r + 1)/8)
Pr(L)) - Pr(Lkc) =
min SST
V
+
max Pr - Pr-ella + V 2
r
The symmetry assumption is not necessary, and in the appendix we show how to remove it at the cost of more expensive computation of the discrepancy. is instructive to compare this upper bound with the results of previous work. An often used assumption in the literature, originally introduced Bartleti [1992], that there a known value A > O. such that drift in each step is bounded by A. i.c. for all < T, || Poll= < A. Assume that T is sufficiently large, i.c. T = (3)/33)//3) By using this assumption on the drift, previous work showed that with nigh-probability, they can find a classifier such that (Lg) - (r(..)) = ( (VAv) and it can be shown that this upper bound is tight up to constants within those assumptions [Barve and Long 1996). These previous works assumed they had access a priori to the value of A, since those algorithms compute à by solving a empirical risk minimization over number of previous samples (((u/2))1/3 that is decided before observing the data. On the other hand, this assumption on the drift together with ( implies that maxter|| Pr- S (r - 1)A. Our algorithm (Theorem 7 guarantees error that depends a minimum choice over < T. hence it is always smaller than
7

---

the one obtained with specific choice of r. If we choose r = (v/A3)1/3 in the upper bound of Theorem 7 we can show that with high-probabille our algorithm returns a classifier h such log(v// //)) Our algorithm achieves this guarantee while being adaptive with respect to the upper bound A, and can indeed guarantee a better result when this upper bound is loose.
that pr Pr(La-) = O ( -
For example, assume extreme case in which the algorithm is given A 0 bound on the drift in each step, but the training set has actually no drift, it was all drawn from the distribution Pr. Previous methods are oblivious to the actual data, and they guarantee an upper bound O Av
with high-probability, since they decide the sample size ((vrA3)) priory without observing the input. In contrast, our algorithm adapts this scenario, and Theorem 7 guaranteess that we ob- tain an O (v//T + Vllo log T) error, with high-probabillity, essentially retrieving the error guarantee for learning with independent and identically distributed samples. Observe that our upper bound depends on T, and it goes to 0 when T + 00.
possible to show that our algorithm can obtain asymptotically better guarantee even if I|P Pt-1lla A & for all & < T. i.e. there is an exact drift of A at each step. This is because our algorithm provides a guarantee as function of max || Py - Pr- rather than the looser
quantity 1 - Pr-++ l|r, as shown in the following example. Let X = [0. 1]. and let H be a class of threshold functions over [0. 1] i.e. for any E [0, 1]. there exists classifiers he, hg H such that h=) = if and only if x 2 c and (x) = if and only if x < c. The class H has VC-dimension equal to 2. We construct sequence of distributions P1. Pl.-.., Pr follows. The marginal distribution over X' is uniform for each distribution P. with t= 1,..., T. At time t S T, the classification of [o, 1] is given by a function L, [0, 1] + {0, 1}. Assume that there exists two disjoint intervals lu = [Po. Po + A/2) and 1 = [P1, P1 + A/2) such that (x = 0 for all
E Io and (x) 1 for all x E I1. We let
(x(x)
if (x E Io) A (t is odd)
(T-((x) = 1 (T(x)
if (x E 4)) A (t is even) otherwise
Vz M.E,t<<T
(r(z)
In particular, (x) differs from (r(x) for x E To if / is odd, and for x E In if / is even. By construction, [.P P1- A for all t T. i.. there is an exact drift of A each step (to be precise, in the last step Pr - Pr- = A/2). As discussed before, with the assumption of a bounded drift A at each step, previous methods guarantee an upper bound O (A) with high- probability. However, we also have that for any 1 S r S T, holds by construction that
max Pr - Pr- < A
Hence, our algorithm (Theorem 7 guarantees with high-brobability an upper bound
((++vu/T + v(log log 7)/T)
Since our algorithm is adaptive with respect to the drift, it can correctly use more samples. In contrast, previous non-adaptive algorithms that rely on the assumption of bounded drift A at each step choose a sample size of 22/3) based on this assumption, thus they can only guarantee a looser bound of O(A 1/3), even when this assumption satisfied with equality.
is possible to use the recent lower bound strategy of Mazzetto and Upfal 2023 in order to show that the upper bound of Theorem is essentially tight a minimax sense.
Theorem Let H be a binary class with VC dimension v, and consider an arbitrary non- decreasing sequence A 0, A...., AT of non-negative reul numbers. Let F = [In, h E H). Let A be any algorithm that observes Zz....,Zo Zr. and it outputs a classifier h E H. If
(V*+ <1/3.
$ min rST
then, for any algorithm A. there exists sequence of distributions Pi...., max Pp Pr- S A, for any r S T, and with probabilit least 1/8 8 it holds that:
......,P Pr such that
(V
+ max Pr - Pr- 117) )) ter
(L(a))) - Pr(Ln.) = 2(2") = Ω
min T
8

---

6 Linear Regression with Squared Loss
In the previous section, we showed an application of Theorem for the problem of binary classifica- tion with zero-one loss. In this section, show that main result can also be applied to linear regression problem. Similarly to the previous section, we let 2 = X' x V, where X' is the feature space and y 1-1,1] iJ is the label space, i.e. Z. (X,, Y,). In this section, we constrain the feature space X' {z E R ||=|| I 1) to be the unit ball centered at the origin in R
We consider the l2 regularized linear prediction class H. = far + (x, w) 1}. We denote each predictor fhr E with its weight w. To evaluate the quality of prediction (z)) we use the squared loss L IR x R ~ R defined
E Rd A ||w|22 I
L(y.3) y²) (y - y²)² For each Jhn H. we let Lo (Ir y) = (x),, 3) be the function that evaluates the loss incurred by hn for any (x,v) E 2. We work with the family of functions F=
-hw E H). By a standard uniform convergence argument based on the Rademacher complexity of F (e.g., see [Kakade al,
2008 Shamir 2015 Awasthi et al. 2020),, ) have that for any S T. it holds:
1 -77-PP1: Pyly -0 +
(n(1/6)
thus satisfy Assumption with C2 O(1) and CF O())
The computation of the discrepancy is more challenging. Let 1 S T/2. Using the definition of F, we have that:
T-r
PT P
sup
Σ
(X,,
Σ
(Ye (Y- (X)
(9)
2r
(=T-++1
2-2-2
Let G. R, b, E R., and Ap Rddx be defined as follows:
ar Σ
Y2
Σ
Y2
by
Σ
YiX,
Σ I=T--+
YıX,
2r+1
T-+-2
4 =
Σ
X
Σ
xxx,
1=----
(-
and observe that the matrix A, is symmetric. Using those definition, we can manipulate the right- hand side of (9) to show that it is equivalent to:
max (-a, + inf
w T (-A,)w 25 w]
+ inf w:]|[[||1
Iw (AA)) 2(-b,) )w]
(10)
w:]|w|||1
In order to compute 10), it is sufficient to be able to solve the minimization problem
inf (wT Aw -6 w)
(1I)
where E Raddd is a symmetric matrix, and E Rdd. This minimization problem has been exten- sively studied for the trust-region method [Conn al. 2000), and Hager [2001] Section 2] provides a way to compute the solution of (TT) in terms of diagonalization of A. Thus, we also satisfy As- sumption 2 and we can obtain the following result an immediate corollary of Theorem [
Theorem 9. Let 8 E 1). Let 1 S i < T be the oulput of Algorithm 7 with input 7 Ze and using the family FF described in this section. Let = argmin classifier with minimum loss over the most recent samples. Then, with probability at least
( ) be the linear
will |
log(log(r 1)/8)
Pr([a) PT( =
min rST
+
max]
Pr Pr- ke
Vr
r
where w = aaggmin,e:|loelsss Pr (Iw) is the linear predictor with minimum loss with respect to the current distribution Pr.

---

7 Related Work
Additional variants of learning with distribution drift have been studied in the literature. Freund and Mansour [1997] provide a refined learning algorithm in the special case of rapid distribution shift with a constant direction of change. In the work of Bartlett et al.) [2000]. they show specialized bounds in the case of infrequent changes and other different restrictions on the distribution drift. The
work Crammer et al. [2010) provides regret bound for online learning with an adversarial bounded
drift. Yang 2011] studies the problem of active learning in distribution drift setting. [Hanneke] eet al. 2015 provide an efficient polynomial time algorithm to learn a class of linear separators with drifting target concept under the uniform distribution in the realizable setting. Interestingly, they also show how to adapt their algorithm with respect to an unknown drift, although their technique relies on the realizability of the learning problem. In the more recent work of Hanneke and Yang [2019), they relax the independence assumption and provide learning guarantees for a sequence of random variables that is both drifting and mixing.
Conclusion, Limitations and Future Directions
We present general learning algorithm that adapts to an unknown distribution drift in the training set. Unlike previous work, our technique does not require prior knowledge about the magnitude of the drift. For the problem of binary classification, we show that without explicitly estimating the drift, there exists an algorithm that learns binary classifier with the same or better error bounds compared to the state-of-the-art results that rely on prior information about the magnitude of the drift. This is a major step toward practical solutions to the problem since prior knowledge about the distribution drift in the training set is often hard to obtain.
We presented concrete results for binary classification and linear regression, but our technique can be applied for learning any family of functions F as long as it is possible to compute the distance ||P P ||> between the empirical distributions with and 2r samples according to the |1-1|> norm (Assumption 2 This is often a challenging problem, and it is related to the computation of the dis- crepancy between distributions, which was studied in previous work on transfer learning [Mansour cet al. 2009 Ben-David et al. 2010). For binary classification, we assume that the empirical risk minimization problem is tractable. However, an exact solution to this problem is computationally hard for many hypothesis classes of interest, and this is a limitation of our algorithm and previous work transfer learning. In those cases, we modify our analysis to use the best-known approx- imation for the distance |Ip - P7 ||= as long as there is an approximation guarantce with respect to its exact value. As illustrative example, if we have a procedure that returns an approximation E, such that S <|PG- Pp ||>/E, E, S a for any r > 1, then it is possible to change the algorithm to obtain guarantee that is at the most factor ((a²) worse than the achieved by Algorithm with the exact computation of the distance (we refer to Appendix B for additional details).
The method presented here uses distribution-indeeeneen upper bound for the statistical error. While this upper bound can be tight in the worst-case, as shown our lower bound for binary classification (Theorem (8), it can be loose for some other sequence of distributions. As a future direction, it is an interesting problem to provide an adaptive algorithm with respect to the drift upper bounds, for example. based on the Rademacher complexity,
that uses iettributionddppedded which can be possibly computed from the input data. Our algorithm does not naturally extend to this setting, as it requires knowing the rate at which the upper bound on the statistical error is decreasing (see proof of Proposition
Acknowledgements. This material is based on research sponsored by Defense Advanced Research Projects Agency (DARPA) and Air Force Research Laboratory (AFRL) under agreement number FA8750-19-2- 19-0-199--1006-A00 and by the National Science Foundation (NSF) under award IIS-1813444 The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official poli- cies or endorsements, either expressed or implicd, of Defense Advanced Research Projects Agency (DARPA) and Air Force Research Laboratory (AFRL) or the U.S. Government.
10

---

References
Pranjal Awasthi, Natalie Frank, and Mehryar Mohri. On the rademacher complexity of linear hy- pothesis sets. arXiv preprint arXiv:2007. 10::20077//045,, 2020.
Pranjal Awasthi, Corinna Cortes, and Christopher Mohri. Theory and algorithm for batch distri- bution drift problems. In International Conference on Artificial Intelligence and Statistics (AIS- TATS), 2023.
Peter L Bartlett. Learning with a slowly changing distribution. In Proceedings of the fifth annual workshop on Computational Learning Theory (COLT), 1992.
Peter I. Bartlett, Shai Ben-David, and Sanjeev R Kulkarni. Learning changing concepts by exploiting the structure of change. Machine Learning, 11(2):153-774, 2000.
Rakesh D Barve and Philip M Long. On the complexity of learning from drifting distributions. In Conference on Computational Learning Theory (COLT), 1996.
Rakesh D Barve and Philip M Long. On the complexity of learning from drifting distributions. Information and Computation, 138(2):170-192 1997.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wort- man Vaughan. A theory of learning from different domains. Machine learning, 79(1)1151-175, 2010.
Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi, Introduction to statistical learning the- ory. In Summer School on Machine Learning. Springer, 2003.
Andrew Conn, Nicholas IM Gould, and Philippe L Toint. Trust region methods. SIAM, 2000.
Koby Crammer, Eyal Even-Dar, Yishay Mansour, and Jennifer Wortman Vaughan. Regret mini- mization with concept drift. Conference on Learning Theory (COLT), 2010.
Yoav Freund and Yishay Mansour. Learning under persistent drift. In European Conference on Computational Learning Theory, pages 109-118, 1997.
William Hager. Minimizing quadratic over sphere. SIAM Journal on Optimization, 12(1): 188-208, 2001.
Steve Hanneke and Liu Yang. Statistical learning under nonstationary mixing processes. In Inter- national Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
Steve Hanneke, Varun Kanade, and Liu Yang. Learning with a drifting target concept. In Conference on Algorithmic Learning Theory (ALT), 2015.
David P Helmbold and Philip M Long. Tracking drifting concepts using random examples. In Proceedings of the fourth annual workshop on Computational Learning Theory (COLT), 1991.
David P Helmbold and Philip M Long. Tracking drifting concepts by minimizing disagreements.
Machine learning, 14(1):27-45 1994.
Sham M Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. Advances in Neural Information Processing Systems (NeurIPS), 2008
Philip M Long. The complexity of learning according to two models of a drifting environment. In Conference on Computational Learning Theory (COLT), 1998.
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. arXiv preprini arXiv:0902.34300, 2009.
Alessio Mazzetto and Eli Upfal. Nonparametric density estimation under distribution drift. Interna- tional Conference on Machine Learning (ICML), 2023.
Mehryar Mohri and Andres Muñoz Medina. New analysis and algorithm for learning with drifting distributions. In International Conference on Algorithmic Learning Theory (ALT), 2012.
11

---

Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar Foundations of machine learning. MIT press. 2018.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning; From theory to algo- rithms. Cambridge university press, 2014.
Ohad Shamir.
The sample complexity of learning linear predictors with the squared loss. Journal of Machine Learning Research, 11:3455-4488 2015.
Alexander B Tsybakov. Introduction to nonparametric estimation. In Springer Series in Statistics, 2008.
Sara van de Geer. Empirical Processes in M-estimation, volume 6. Cambridge University Press, 2000.
Vladimir N. Vapnik. Statistical Learning Theory. John Wiley & Sons, Inc., 1998.
Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Liu Yang. Active learning with a drifting distribution. Advances in Neural Information Processing Systems (NeurIPS), 2011.
Bin Yu. Assouad, fano, and cam. Festschrift for Lucien Cam: research papers in probability and statistics, 1997.
12

---

A Deferred Proofs
Proof of Proposition P For any i 2 0, let 6, = = 10)3). By using Assumption we have
that with probability at least 1 - 8, it holds that
CF Cra++O22/m( (n(10)))) + 10)
|P P
Vri
CF.1 +
((6)) + Im(1 10)
Vi
Cr. VTi
2n + 10)
+ Cray
where in the second inequality we used the definition Cy.s and the fact that VotUs VI+ /v. Additionaly, the following equality holds
D0
Σ 6, 5
1/12 0
where in the last equality, we used the known fact that Σ 1/22 = 7266. Thus, if we take an union bound over all 2 O, we have with probability at least 1 - 8 holds that
CF Vrs
2n + 10)
P P
+ CF21
vi 2 0
The statement follows by observing that the right-hand side of the above inequality is equal to S(r,, 6) for any i 2 0.
Proof of Proposition We have U(T++1,6) - Urr., 6) = 21[S(r++1,)) S(r., 8)] + PP - P7- ||= - P
PF ||
By using the triangle inequality, obtain
P - P || & Pr PT ||= + PP
1F+
thus have
U(ri41,0) - (ri;,)) < 21(5(ri+1, 6) - S(r,, 8)] + Pl
P ||=
(12)
We use the triangle inequality and Proposition show that
| P 1| < P
P
1 || || 1 ||p 1 ||r
< T
1 S(r,, 6) S(
If we plug the above inequality in 12) and use the assumption that | - ppi 1 || S 4S(ri, 8), we
obtain
U - Urr; 6) < 21[S(r(+1,)) S(r;, S(1 6) + 55(r;,
-2.5(r+41:)) 5) 165(r,,))
If we expand the above upper bound by using the definition of the function S, we have
CF
2 ln + 11)
In(i + 10) In(i + 11)
22S(r 16S(r;, 8)
[22 16v2 Cr.y
22 16v2,
Vri+1
ri41
<
where the last inequality follows since 22 16-16 0, and 162-1622 /n((i 1 In(i + 11) < O. Thus, it holds that
U(rei, - -((r,)) 522(r))11. 165(r,, 5) 50
and we can conclude that 0) < Ör.,
13

---

Proof of Proposition 5
Observe that by using the triangle inequality, it holds that
11
PT P7
| ||
P7
1
||
PT* ||x
Pr " 1
(((
||
where in the second inequality we used Proposition 3
By assumption, we have that |P7
PT || 2 48(r;+1, 8), hence
P - P 11s 2 25(r;,
(13)
Observe that by triangle inequality, have that
PT - PT+ || S Pr - Pfi Il + Pr - Pp 1|=
We use
and obtain that
| P || S max PT Pr-ell + max 1| - Pr-cllE 1eh+:
tCr;
$ 2 max tCr+1
Pr Pr-il1s
By combining the above inequality with S(r,, 8).
13 we finally obtain that maxecr |P - Pr-ellz 2
Proof of Lemma
We remind that J
(In
H). By using the definition of ||-1|s, we have
T
sup hCH
Σ
(x Yi)
(X
Yi)
7
2r
T=--++1
2-2++1
T
T-r
1 sup heh
Σ
La(X,,
Σ
Ln(X,,Yi)
2
(=f-r+1
(=T-2r+1
We can remove the absolute value by re-writing this expression as
T Σ
T-r
|PT
P
max
sup heH
(i,,,))) - Σ
La
(=T-r+1
1-+-2
Lx Yi) )
sup keR
(X,,,
!
Σ
(14)
(=T-2r+1
I=T-r+1
Consider the first argument of the above maximum. We can observe that for any (x, Y) X x it holds that La (X, Y) Ln (X, - 1, thus obtain that
T-r Σ
sup KEH
Σ
Tx,X,
(=T-r+1
1-T-2r+1
T-r
sup keW
1 1--
Σ
(N,, 1 - Yj)
Σ
Ln(X,,
1=T-r+1
2r+1
=1 inf NEW
Σ
Lx,X,,
Σ
La(X,, Yr)
(15)
(=T-r+1
1-T-2r+1
Similarly, demonstrate that the second term of the maximum is equal to:
Σ Lx)
Σ Lx(Xx.8))
sup NCH
1r1-2
1=1-rt1
T-r
inf NEH
Σ
Lx(X, +
Σ
(x(,111-Y))
(16)
(=T--+1
2r+1
14

---

Therefore, to compute the diserepancy (14). it is sufficient to solve the two empirical risk minimiza- tion problems (5) and (16). To obtain the final statement, we can observe that for any (X, Y) and h E H. it holds that Ln (x,X) = I1-x(X,1 Y). Thus, we can show that (T6) is equivalent to:
- inf hcht
Σ
Lx Yi) +
E
1 Yi)
t=T-r+1
t=I
T-r
=1 inf
Σ
L1-h Xi)+
Σ
LI-n
KEH
1=T-r+1
2r+1
Since H. is symmetric, i.e. 1 1 h E H + h E H. we can conclude that
15 and 166 have the
same value. This concludes the proof.
Proof of Theorem 7 Since H has VC-dimension by standard argument we have that the family == [L, h E HJ has VC-dimension upper bounded by 2v, thus satisfies Assumption on the sample complexity for uniform convergence with Cy O(Vv) and Cf = 0(1).
We can observe that since H. is symmetric, Lemma 6 shows that we can compute || P ||5 for any by solving empirical risk minimization problem. Since H. is computationally tractable, there exists a procedure that solves this problem, thus we also satisfy Assumption 2
Remark: If the symmetry assumption does not hold, in the proof of Lemma O we show that we can still compute the discrepancy ||P--- P?2 || by solving the two empirical risk minimization problems
in (15) and (16).
Hence, we can use Algorithm I with the family F, and let f be the value returned by the algorithm. Theorem guaranteess that with probability at least 6, we have that
Pr - Pr- + log(log(r + 11/0) -1/00)
1)
Py - Pf1l- =
min r
max ker
(17)
Now, we have that
Pr(Ln)) Pr -
Pr(.n.) PT(L,) + Pr(
S (T, - +Pp Pr(
< (PT(L,)) (1,)) |P]((t>>) - Pr((Te))
- PT IL,
where the first inequality is due to the definition of h. Therefore, using 17 we have that with
probability least 1 5, it holds
log(log(r + 1)/8)
Pr((R)) (L o min
max Pr. Pr- +
Proof Theorem
The theorem is proven following the same structure the proof of Theorem
A.1 Lower Bound.
In this section, we prove the lower bound of Theorem The proof structure based on the work of Mazzetto and Uptal 2023). We provide simpler statement of their proof in our setting, and we remove the additional regularity assumption used that work to characterize the drift error. We introduce the following notation.
We say that a distribution Q over nn is product distribution if can be written as the product distributions over Z, i.c. Q Q1 ... Qn. For any n 2 we can observe that since the random
15

---

variables Zi.... Zn are independent, their distribution can be described as a product distribution over z". Given two strings T, E {-1,1)", we let hd(T, / - be the Hamming distance between the two strings, i.e. the number of positions in which the two strings differ.
Let be the VC dimension of the hypothesis class H. We will construct a (later defined) family of product distributions Q = {Q(T)= = Q( x... x Q T E {-1,1]"} over z" that are indexed by a string E {-1,1}". Intuitively, each distribution @(r) is possible candidate for the distribution of the random variables Zi,..., .,,, Zr. We will show that for any algorithm A, there exists a product distribution Q(7)) such that the classifier A computed by A using the samples Zi...., ZT from Q(+) has large expected error. The proof is based Assouad's Lemma. We provide a statement of this lemma that is an adaptation of its classical statement to our setting (Yu 1997].
Lemma 10 (Assouad's Lemma). Let be defined as above, For any function g 2 + {-1,1)" there exists E E{- {-1, 1 such that
IF Z~Q(r)
hd(g(Z), 2n), 2
V
min
[Q(+)
A Q((
hd
Let A1 = 0, O,A.....; Dr be the sequence defined in the statement of Theorem We let +
{1. {1..... T} + IR be the function
(rr) = (V r
-
We let x- min, ((r), and we remind that we assume s- 1/3 in the statement of the Theorem. We build the family Q based on the following value:
F max I
Proposition 11. The following holds:
(f)) S 36*
Proof. Letr* r be value such that 4- D(r"). The statement follows by exploiting the definition of F. We distinguish two cases. If F 2 r", we have that
AF VulT
< 2/1/F
= 2/
A. + vu/r"
Vu/r"
Conversely, r F. we have that
((F) AF + VulF
A +
1)/F
< /3A41/AAr 33
Φ A,
vu/r
A, + Vu/T"
In the first inequality we used the fact that the sequence A..... AT is non-decreasing, and the inequality Vv/(f + < Az41 due to the definition ot F.
We define the family of product distributions Q as follows. Let X 1,...,A X, be shatter set for the hypothesis class H. We build the following family Q = (Q(T) = Q of product distributions over ZT = (X x y)" that are indexed by r E [1 They are defined as follows:
7 x x... x Q/ : (-1,111)))
16v6 (V AT-1+1)
Pr (Y= = 1[=xxx) = (XY)))())
1
else
7
Pr (X,Y)=!!))
(X X,)
Vi (1....,v)
16

---

Those distributions are well-defined. In fact, we have that for all t > T - -P:
1
+
(V² S .()) -
3 Φ < 1/4,
16v6
16v6
16
where we used Proposition
11 Given a classifier h E H and 7 E (-1, 1|", we remind that
(T))
(l(X) #Y) (X.Y)=O)
Pr
We can observe that for any classifier E and T - r, it holds by construction that:
|f - - (L))
1
Ar- S Ar-++1
16v6
and for any S T i, we have that
(L)) 24 (L))
(Lm)
1
Ap +
V
7+1 F+1V
V
16v6
8V6
8V6
A & Ar-1+1
8/3
where the first and the second inequality are due to the definition of r, and the last inequality follows from the fact that the sequence A Ar is non-decreasing. Hence, if we let F (In : h H), it results that for and for any 1 S r S T, it holds that:
max 1 (T) t<r
(18)
We also let Ly- be the minimum loss that is achieved by function H with respect to Q/7, i.e. -, argmingysher Q (In)- By using the family Q together with Assouad's Lemma, show the following.
Lemma 12. Let Q be defined above. Let A 2 H be any algorithm that observes sequence of elements T elements from 2, and it oulpuls classifier A For any algorithm A, there exists E 1" such that if the input Z,...., Ze is sampled according to Q(7), then:
7v64
E OF (Lna)
-27 (L7.)
768
Proof. Let E (-1,1)". We can define
TA (x
1,...,2 hA(X,) (-1,1)"
We have that:
o (Ehh)=
1
(V
( F
+
AF
+
(V=+ + Σ
1 (raNtT)
2
16v6
8vbu
1
(V - Ar)
4(7)
hd (T..
2
16V6
8vbu
By construction of OfF² we can observe that
V + 2r) mi
2 (Lh))
2 16v6
hence, have the following relation
2/77 (Lna) Q/77) (L%,)
Φ(7)
hd (TAIT)
(19)
8v6r
4
= of (Lna) 22 (1%-)
E hd
hhdd(TT (TAIT)
8/6v
17

---

Observe that A can be seen as map from z to 1-1 (i.e., the string T.). Hence, we can apply Lemma 10 this implies that there exists
1- such that
B B (Lna) O (LT-)
(
1Q(T)) Q
16v6
hd(r's "r"==1
We are left to evaluate the right-hand side of the above inequality. We can use the following known relations that hold for any two distributions P and Q over - (Tsybakov 2008
|| Q = -1 -1 Qlll.
PP- (2KL(P.Q)
(20)
where KL is the Kullback Leibleer divergence (we refer to the classic definition of those distances as in [Tsybakov] 2008). Let and r" be two strings in {-1,
11 1) that only differ in one coordinate.
Let Ber(p) be Bernoulli distribution with parameter p E [0, 1]. We have that:
T
(L(Q (0000)000)))
T-
Ber 22= 16v6 (V=+a.)) Ber - 16v6 (Vz+ ))
KL
(21)
where the first equality is due to the factorization property of the KL--dieereecc,, the second and third equality are due to the definition of the family Q. For any e < 1/4, it holds that
Ber (1-c).
+())) S 12.2
KT.
-
Ber Ber
By plugging the above inequality 21 and using the fact that (x + y)² S 2x.2 + 2yy, we obtain that
24
162 6y
T
24
[V + FA
162 6y
By using the definition of F, holds that A37 < u. Thus, we we have that KL(Q(t),Q( 5 1/32. If
this inequality with 20 have
min (1Q()) ((+")) 2 7/8.
hd(
=1
Hence, we can conclude that there exists 1-, such that
7V66(F)
E O (Lma) - (L,-) 2
768
By using this Lemma, we can casily prove Thcorem g
Proof of Theorem By Lemma 12 there exists such that if P. = =Q/ for all 5 S T, then the algorithm A with input Z1, : ZT satisfies
E ((rr) PL )] 7/64" /768
(22)
Due to 18 observe that the distributions .I.... Pr satisfy the assumption on the drift.
18

---

Let Pr Pyy(L Observe that due to the construction of Q(T) and 19 E ( S 3 /(8v6), where the last inequality is due to Proposition 11 later defined value. We have that:
we have that Let or 0 be
E E > a Pr(E 2 a + EE < a0 S aΦ*)
(34' (8) Pr(E 2 a aa0 Pr(E S a
Pr((E 2 a [30 /20 - /20- + a.
By using the above inequality together with 22 we finally obtain that:
Pr(E 2 a 2 7 /768 ax 7V6/768
36 /8v6) - ax 3/(8v6) a
We set a 1/(112/)) and we finally obtain that
Pr
E
2 1/8
112v6
B Relaxing Assumption 2
Given family F, is possible that the exact computation of |P PP is computationally hard. In this section, we show an example on how to relax Assumption to allow an approximation of this quantity.
Let a 2 1. We say that an algorithm A in an a-approximation procedure given 2-22++1.-- Zr, it computes estimate A(ZT-277 15r--2+1,... 7 such that
1 || 1 |
A( ZT) a
for any r S T/2. That is, the algorithm A does not compute the value of the supremum of the norm ||-I|>= exactly, but it guarantees constant factor approximation In this case, we can modify the algorithm as follows.
Algorithm 2: Adaptive Learning Algorithm under Drift with Approximation Procedure
i x-00 0;
while ri < T2/2do do
if A(2.-2r41.....
Zr) S 4- S(rr, 6) then
i 6 1+:
end
else
return :
end end
return r;
Theorem 13. Let 8 E (0,1). Let Assumptions hold, and assume that there exists an a- approximation procedure for estimating || Irr Ppr F for any S T/2. Given Zi.... Ze, there exists an algorithm that outputs a value & < such that with high-probability, it holds that
aCF.1 VF
log(lo((r + 1)/6)
Pr - - a
min
max | - Pr-ell= + aC=2p ter
Proof. The proof follows the same strategy the of the main theorem with slight modifications, and we discuss those changes. We replace the definition of Ur, 5) with
Urr (18a + (r, 8) + PT Pf
19

---

in order to take into account the additional error due to the approximation procedure. We can observe that
A(ZI A(ZT-ra -mu Zr) - 4S(r;;)) 6)
implies
1 - 1 - (r.(
since is an a-approximation procedure. We can follow the steps of Proposition with those different constants to show equivalent statement of this Proposition. On the other hand, we have that if
A(2 .., ,r) 45(r: 8)
then
P P || > 45(
and Proposition applies. Therefore, we can use the same proof strategy of Theorem to prove Theorem 13
20


Reviews:
[{"review_id": "3LQZd42mMp", "reviewer": "Reviewer_sYaX", "summary": "This research paper presents a straightforward algorithm designed to facilitate adaptive learning of models in the presence of distribution drift. The algorithm is specifically designed to adapt to changing data patterns without requiring any prior knowledge of the drift. Moreover, the paper provides a proven bound that guarantees the learning error of the algorithm. Overall, the paper is well-written. The simplicity of the algorithm contributes to its comprehensibility, making the results easily understandable. Additionally, the inclusion of a detailed illustration showcasing the algorithm's effectiveness in handling binary classification with distribution drift serves as a strong validation of the proposed methodology.\n\nI think this is a breakthrough work for learning under non i.i.d data as it does not require prior knowledge of the potential drift. However, this could also be one of the limits of this paper. The algorithm proposed is to adaptively find r that can achieve the best trade-off between the statistical and drift error. Drift sometimes might represent an upcoming arrival of a new distribution. The proposed algorithm might get a competitive average accuracy compared to those algorithms that know the magnitude of drift in advance. However, I am not sure if this proposed algorithm will perform equivalent good if we test it on every sequential portion of the data as well. For example, a classifier of labeling every instance as 0 could also achieve an accuracy of 90% on the data where 90% of instances are 0 class. In this case, I get very limited information from its good results.\n\nOverall, I think the proposed methodology provides a new way of designing the learning algorithms under drift.", "questions": "In Theorem 1, r is the output of Algorithm 1. What will be the limits if using other algorithms?\n", "limitations": "Some of the limitations have been listed in section 7. As is discussed, satisfying Assumption 2 is challenging and authors already discuss possible solutions.\n\nFrom my perspective, the author claims their contributions as removing the prior knowledge of distribution drift. I appreciate their contribution. But as a reader, I am more curious if we do get some prior knowledge of the distribution drift, how can we use that knowledge to improve what you have presented in this work? I think this will provide more insights of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, I think the proposed methodology provides a new way of designing the learning algorithms under drift.\nI also agree that r would be an important factor during learning under drift. Therefore, adding this to the learning boundary, from my perspective, is a good start of conducting the following theoretical learning works that discuss the non-identically distributed problem. Theorem 1 could be a quite useful guidance for the following studies in this area.", "weaknesses": "As I have mentioned in the summary, Theorem 1 only provides a very general bound. The r is considered as sequentially increased. However, I think the usage of Theorem 1 is very limited if we apply it to learning sequential data. As for the sequential data, there should be always new data coming and thus very possibly new distribution in the upcoming instances. It is less practical to design the r as monotonically increasing if you don't consider the magnitude of the drift. The Inequality in Algorithm 1 is always comparing P_t between it is at r_i and r_{i+1}. This means the i is only updated when the distribution drift is large enough among two consecutive i. However, this is not true. Therefore, this algorithm removes the assumption of knowing the magnitude of distribution drift in advance, but for me, it actually adds a hidden assumption that the magnitude of distribution drift should be enough big between at least one of two consecutive i in [1, T]. \n\nLet's think of the situation that the magnitude of distribution drift is incremental increasing by i. I am not sure if your algorithm can output the expected r in such a case. But for those algorithms that assume a known magnitude of drift in advance. They can complete this task. \n\nAs is also mentioned in this paper that an adaptive algorithm with respect to the drift that uses distribution-dependent upper bounds", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you for taking the time to review our paper and for your feedback.\n\n-----\n\n**Question**:  \"The algorithm proposed is to adaptively find r that can achieve the best trade-off between the statistical and drift error. The proposed algorithm might get a competitive average accuracy compared to those algorithms that know the magnitude of drift in advance. However, I am not sure if this proposed algorithm will perform equivalent good if we test it on every sequential portion of the data as well. For example, a classifier of labeling every instance as 0 could also achieve an accuracy of 90% on the data where 90% of instances are 0 class. In this case, I get very limited information from its good results.\"\n\n**Answer**: Indeed, this is the first algorithm that doesn’t rely on prior knowledge about the drift.  The algorithm provides an optimal solution for the aforementioned trade-off for any given time T (Theorem 1) (not an average over T).  Its solution is provably as tight as the one of other algorithms that require knowing the magnitude of the drift in advance, solving the open question in [A].\n\n----\n\n**Question**: \"[...] The Inequality in Algorithm 1 is always comparing P_t between it is at r_i and r_{i+1}. This means the i is only updated when the distribution drift is large enough among two consecutive i. However, this is not true. Therefore, this algorithm removes the assumption of knowing the magnitude of distribution drift in advance, but for me, it actually adds a hidden assumption that the magnitude of distribution drift should be enough big between at least one of two consecutive i in [1, T]\"\n\n**Question**: \"Let's think of the situation that the magnitude of distribution drift is incremental increasing by i. I am not sure if your algorithm can output the expected r in such a case. But for those algorithms that assume a known magnitude of drift in advance. They can complete this task.\nIt is not true that we require the drift to be big enough between two consecutive i in [1,T].\"\n\n**Answer**: r_i and r_{i+1}  are not two consecutive time steps.  r_{i+1} = 2r_i  (see line 156). As i increases, this gap is sufficient to detect even small gradual drift, as also discussed in the example in lines 241-256 in the paper.  \n\n----\n\n**Question**: In Theorem 1, r is the output of Algorithm 1. What will be the limits if using other algorithms?\n\n**Answer**: Algorithm 1 provides an optimal solution of the trade-off, as proven in Theorem 1, which is tight up to constants for binary classification (Theorem 7, minimax). There are no other algorithms to compare to since we are addressing an open question, and there are no other algorithms that provide such guarantees.\n\n----\n\n**Question**: From my perspective, the author claims their contributions as removing the prior knowledge of distribution drift. I appreciate their contribution. But as a reader, I am more curious if we do get some prior knowledge of the distribution drift, how can we use that knowledge to improve what you have presented in this work? I think this will provide more insights of this work.\n\n**Answer**: The goal of our work is to eliminate the requirement of prior knowledge of the drift, providing similar guarantees without this knowledge. This prior knowledge is unrealistic in practice, and this is the main reason that prompts the open question of [A].\n\n----\n\nReferences.\n[A]: Steve Hanneke and Liu Yang. Statistical learning under nonstationary mixing processes. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1678–1686. PMLR, 2019\n"}, {"review_id": "J481lcsyGw", "reviewer": "Reviewer_RWUF", "summary": "The author propose a general algorithm to learn a family of functions with respect to the current distribution at time T. This algorithm achieve a drifting-instance-dependent bound without any prior knowledge of the drift. Based on this, the author further analyze a tractable algorithm on binary classifier.", "questions": "Why is empirical estimate based on a window up to T better than empirical estimates based on any consecutive window?\nWhat's the value in getting rid of prior knowledge on drift magnitude in practice or in theory?", "limitations": "Sufficient.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper solves an open problem of drifting distribution with unknown prior. The proof technique is clear and solid.\n2. It's further analysis on binary classification is inspiring.", "weaknesses": "1. The error bounded is only measured on windows that end at T. Instead, a better goal would be to select a window from t1 to t2. As an example of why this problem could be more relevant, there might be large drifts nearby T but early distributions are close to P_T.\n\n2. The techniques used in this paper is not very novel. Specifically, although the authors claim they do not directly estimate the drift error, it is still drift detection only with tolerance towards estimation error. The doubling trick is intuitive and not surprising here.\n\n3. As the authors admitted in our paper, this algorithm is very general and might be computationally intractable in more complicated cases. I think the author could discuss the benefit of their algorithm versus existing work on cases beyond binary classification. They may do this by showing either further proofs or empirical evidence. Currently, it is not immediate to me the value of an algorithm that ignores assumptions on the magnitude of the drifts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your close reading of our paper and for your feedback.\n\n---\n\n**Question**: The error bounded is only measured on windows that end at T. Instead, a better goal would be to select a window from t1 to t2. As an example of why this problem could be more relevant, there might be large drifts nearby T but early distributions are close to P_T.\n\n**Question**: Why is empirical estimates based on a window up to T better than empirical estimates based on any consecutive window?\n\n**Answer**: One can modify our algorithm and analysis to handle intervals ending at any point in the past. However, without prior knowledge (such as periodicity) the most reasonable assumption is that observations that are closest in time provide the most relevant information. For this reason, a long line of research in this area considers windows that end at T (e.g., references in lines 20-26 in the paper); we improve upon this line of work, solving the open question in [A] for this setting.\n\nWe remark that a properly chosen window that ends at T  provides a minimax tight estimation under simple assumptions (e.g., bounded drift at each step), see line 24, line 247, and Theorem 7. \n\n----\n\n**Question**: The techniques used in this paper is not very novel. Specifically, although the authors claim they do not directly estimate the drift error, it is still drift detection only with tolerance towards estimation error. The doubling trick is intuitive and not surprising here.\n\n**Answer**: We respectfully disagree. We present the first algorithm that does not rely on any prior knowledge of the drift but only uses empirical measures learned from the data. We think this is a major contribution that solves an open problem posed in [A]. Obviously, the widely popular doubling trick is not a contribution of this paper. \n\nOur question to the reviewer is why do they not think this is not a novel contribution?\n\n----\n\n**Question**: As the authors admitted in our paper, this algorithm is very general and might be computationally intractable in more complicated cases. I think the author could discuss the benefit of their algorithm versus existing work on cases beyond binary classification. They may do this by showing either further proof or empirical evidence. Currently, it is not immediate to me the value of an algorithm that ignores assumptions on the magnitude of the drifts.\n\n**Answer**: Binary classification is a major problem in machine learning. We think that even just this result  (Section 5) is a major contribution, as previous existing work relied on a priori assumption on the drift. In the general case, the hardness depends on the family F (as in almost all ML applications).  There are other cases for which the computation of the discrepancy is known to be possible [B] (e.g., regression with squared loss).  See also our discussion in lines 312-325\n\nThe hardness of evaluating the discrepancy is not limited to our technique, and it is a known limitation for work on transfer learning/distribution drift. In fact, even with access to more samples from each distribution, previous work has the challenge of estimating the discrepancy (e.g., [C,D]). In our case, we show a major setting (binary setting) in which it is efficiently computable even with limited data.\n\n----\n\n**Question**: What's the value in getting rid of prior knowledge on drift magnitude in practice or in theory?\n\n**Answer**: We eliminated the requirement of prior knowledge on the drift, providing similar guarantees without this knowledge and only relying on the data. This addresses an open problem in [A] prompted by the following reason: prior knowledge of the drift is unrealistic in practice.\n\n---- \n\nReferences:\n\n[A]: Steve Hanneke and Liu Yang. Statistical learning under nonstationary mixing processes. AISTATS, 2019.\n\n[B]: Mansour, Yishay, Mehryar Mohri, and Afshin Rostamizadeh. \"Domain adaptation: Learning bounds and algorithms.\" COLT, 2009.\n\n[C]: Mohri, Mehryar, and Andres Muñoz Medina. \"New analysis and algorithm for learning with drifting distributions.\" ALT, 2012.\n\n[D]: Awasthi, Pranjal, Corinna Cortes, and Christopher Mohri. \"Theory and algorithm for batch distribution drift problems.\" AISTATS, 2023.\n"}, {"review_id": "L92P04W8bP", "reviewer": "Reviewer_k7dA", "summary": "This paper under considers the theoretical problem of determining the sliding window size for empirical risk minimization in the presence of unknown distribution changes. The proposed method aims to enable the learning of a classifier comparable to approaches that have prior knowledge of the distribution change magnitude. ", "questions": "It is important to explicitly discuss the computability assumptions made in the paper and discuss when and how they hold. This discussion should include considerations of solvability, accurate estimation, or upper bounding of variables such as the distribution discrepancy and the constants. So it is suggested to provide an in-depth analysis of Assumption 2 and other computability assumptions on the constants mentioned above and its applicability in practical scenarios.", "limitations": "Limitations are discussed in this work.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The paper's motivation is commendable, as it aims to tackle the challenge of non-stationary sequential learning, specifically with unknown distribution shifts. This is an important problem, and the proposed technique could potentially contribute to its advancement.\n\n+ Although not evaluated extensively, the results appear reasonable. While I haven't reviewed the proofs in detail, they seem sound.", "weaknesses": "\n- The paper relies on computability assumptions for key variables, such as the distribution discrepancy (e.g., $\\|P^r_T - P^r_T\\|_{\\mathcal{F}}$) and the constants ($C_{\\mathcal{F},1}$ and $C_{\\mathcal{F},2}$). However, the paper lacks a discussion on when these assumptions hold, how solvable they are, or how accurately they can be estimated or upper bounded. In comparison to previous methods that estimate distribution shifts, it is unclear whether estimating these parameters would lead to a more practical algorithm. This aspect requires further analysis and discussion.\n\n- The authors claim that their proposed algorithm aims to provide a practical solution to handling unknown sequential distribution shifts without prior knowledge. However, the proposed algorithm introduces new parameters that are challenging to estimate or even tightly upper bound, such as the distribution discrepancy (assumption 2). While the new analysis techniques presented may contribute to addressing the problem, the overall contribution seems limited, as the proposed method essentially shifts the difficulty from estimating the distribution shift magnitude to estimating other parameters.\n\n- The paper lacks a thorough discussion on when Assumption 2 holds, especially in practical scenarios. This assumption is crucial, as the proposed method relies on estimating the distribution discrepancy and other constants that evolve the hypothesis class $\\mathcal{F}$. Without addressing the practicality of these estimations, the proposed method's feasibility remains questionable. It would be beneficial to provide a detailed comparison of the estimation difficulty for the parameters required in the proposed method compared to previous works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your work in reviewing our manuscript, and for providing thorough feedback.\n\n---\n\n**Question**: The paper relies on computability assumptions for key variables, such as the distribution discrepancy (e.g., $|P^r_T - P^r_T|_{\\mathcal{F}},\nC{\\mathcal{F},1}\nC_{\\mathcal{F},2}$). However, the paper lacks a discussion on when these assumptions hold, how solvable they are, or how accurately they can be estimated or upper-bounded. In comparison to previous methods that estimate distribution shifts, it is unclear whether estimating these parameters would lead to a more practical algorithm. This aspect requires further analysis and discussion.\n\n**Question**: The paper lacks a thorough discussion on when Assumption 2 holds, especially in practical scenarios. This assumption is crucial, as the proposed method relies on estimating the distribution discrepancy and other constants that evolve the hypothesis class \n$\\mathcal{F}$. Without addressing the practicality of these estimations, the proposed method's feasibility remains questionable [...].\n\n**Answer**: Section 5 gives a thorough discussion of both Assumptions 1 and Assumptions 2 for the important case of binary classification. \n\nFor Assumption 2, we provide an additional discussion in lines 312-325 in the Conclusion, and also in appendix B. \n\nAs we describe in the paper, Assumption 1 is related to learnability, and we discuss sufficient conditions in lines 78-83 for it to hold. This is a very well-studied problem in the statistical learning community, and indeed, these constants depend on the family F. A general discussion on how to obtain them is out of the scope of this paper.\n\n----\n\n**Question**: The authors claim that their proposed algorithm aims to provide a practical solution to handling unknown sequential distribution shifts without prior knowledge. However, the proposed algorithm introduces new parameters that are challenging to estimate or even tightly upper bound, such as the distribution discrepancy (assumption 2). While the new analysis techniques presented may contribute to addressing the problem, the overall contribution seems limited, as the proposed method essentially shifts the difficulty from estimating the distribution shift magnitude to estimating other parameters.\n\n**Answer**:  We respectfully disagree with this characterization, because previous work required prior knowledge, whereas in our work we obtain similar results while only relying on quantities that can be estimated from the data. Moreover, we completely characterize those assumptions for the major problem of binary classification, improving upon a long sequence of work in that area (Section 5). In the general case, the assumptions depend on $\\mathcal{F}$. \n\nWe also remark that in this setting it is not possible to estimate the magnitude of the distribution drift since there is only one sample from each distribution.\n\n*More details*:\nThe constants $C_{\\mathcal{F},1}$ and $C_{\\mathcal{F},2}$ are related to the complexity of learning the family $\\mathcal{F}$. This is a well-studied problem within the statistical learning community, and these constants depend on the family $\\mathcal{F}$.\n\nThe hardness of evaluating the discrepancy in the general case is not a limitation unique to our work, and it is a known limitation for work on transfer learning/domain adaptation, as we remark in the Conclusion. In fact, even with access to more samples from each distribution, previous work has the challenge of estimating the discrepancy (e.g., [C,D]). In our case, we show a major setting (binary setting) in which it is efficiently computable even with limited data.  There are other cases for which the computation of the discrepancy is known to be possible [B] (e.g., regression with squared loss)\n\n----\n\nReferences:\n\n[B]: Mansour, Yishay, Mehryar Mohri, and Afshin Rostamizadeh. \"Domain adaptation: Learning bounds and algorithms.\" COLT, 2009\n\n[C]: Mohri, Mehryar, and Andres Muñoz Medina. \"New analysis and algorithm for learning with drifting distributions.\" ALT, 2012.\n\n[D]: Awasthi, Pranjal, Corinna Cortes, and Christopher Mohri. \"Theory and algorithm for batch distribution drift problems.\" AISTATS, 2023.\n\n\n\n\n\n\n\n\n"}, {"review_id": "iQJbJsa7u7", "reviewer": "Reviewer_ePCf", "summary": "The paper proposes an algorithm for environments with changing distributions without assuming a priori knowledge about the change in distributions. The proposed algorithm provides error bounds that decrease with the number of time steps.", "questions": "How strong is the assumption on the distributions? What scenarios satisfy such assumptions, are there any real examples?\n\nThe reviewer believes that the problem formulation needs further explanation (e.g., what is to be learned at each instant of time).\n\nNumerical results could help to see the superiority of the presented method.\n\nThe references are a bit old. There are more recent related works: \n\n“Minimax Classification under Concept Drift with Multidimensional Adaptation and Performance Guarantees.”\n\n“Adaptive online learning in dynamic environment.”\n\n“Random feature based online multi-kernel learning in environments with unknown dynamics.”", "limitations": "Numerical experiments are not included.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The idea of considering independent distributions with distribution shift is unexplored.\n\nThe algorithm itself is a solid technical contribution, and the theoretical results are strong\n", "weaknesses": "Numerical experiments are not included.\n\nAssumptions need further justification.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper and for your feedback.\n\n---\n\n**Question**: The idea of considering independent distributions with distribution shift is unexplored.\n\n**Answer**: We study the classical setting where we have a sequence of drifting distributions, but the samples from those distributions are independent. \nAs we discuss in the introduction, this idea is not unexplored, see e.g. [B,C] (additionally, references in lines 20-26). Our work improves upon the results of this line of research, solving an open question posed in [A] in this setting.\n\n----\n\n**Question**:  Assumptions need further justification. How strong is the assumption on the distributions? What scenarios satisfy such assumptions, are there any real examples?\n\n**Answer**: This classical setting has been justified and studied in a long line of research, see lines 20-26 in the paper and references therein. The work [B] provides a good discussion of this setting. We are addressing an open theoretical question within this line of research [A], improving upon previous work.\n\n*In detail*: \nIn Section 5, we discuss the assumptions introduced in the paper for the major problem of binary classification.\n\nFor Assumption 2, we provide an additional discussion in lines 312-325 in the Conclusion, and also in Appendix B. \n\nAs we describe in the paper, Assumption 1 is related to learnability, and we discuss sufficient conditions in lines 78-83 for it to hold. This is a very well-studied problem in the learning community, and indeed, these constants depend on the family $\\mathcal{F}$, and a general discussion on how to obtain them is out of the scope of this paper.\n\n----\n\n**Question** The reviewer believes that the problem formulation needs further explanation (e.g., what is to be learned at each instant of time).\n\n**Answer** The goal and the problem formulation are specified in Lines 60-62, and further discussed in the following lines. We want to estimate the expectation of all the functions in a family $\\mathcal{F}$ with respect to the current distribution $P_T$. This formulation of learning and notation is common in the statistical learning/empirical process community (e.g., [D] ).\n\n---\n\n**Question**: Numerical results could help to see the superiority of the presented method.\n\n**Answer**: The nature of our work is theoretical, and there is no other equivalent method to compare to. We improve upon a long line of research by solving an open question [A]: we show that we can obtain the same results of the previous work without knowing the drift a priori. Our results are also tight in a mini-max sense (e.g., Theorem 7 for binary classification). \n\n----\n\n**Question** \nThe references are a bit old. \nThere are more recent related works:\n\n1. “Minimax Classification under Concept Drift with Multidimensional Adaptation and Performance Guarantees.”\n\n2. “Adaptive online learning in dynamic environment.”\n\n3. “Random feature based online multi-kernel learning in environments with unknown dynamics.”\n\n**Answer**: Thank you for the additional references that we could add to the paper. We believe that we discuss the most relevant line of research in the introduction and related work. Our work solves an open question that was posed in a **recent** paper [A].\n\nThe setting, the assumptions, and the main results of the mentioned papers are significantly different from our work. E.g:\n\n1. The concept drift follows a specific dynamic described in that reference. Our paper addresses a more general setting.\n\n2,3. Among the clearest differences, the measure of error is regret rather than the learning error for the distribution at the current time.\n\n----\n\n[A]: Steve Hanneke and Liu Yang. Statistical learning under nonstationary mixing processes. AISTATS, 2019.\n\n[B]: Mohri, Mehryar, and Andres Muñoz Medina. \"New analysis and algorithm for learning with drifting distributions.\" ALT, 2012.\n\n[C]:  Philip M Long. The complexity of learning according to two models of a drifting environment. COLT, 1998.\n\n[D]: Sen, Bodhisattva. \"A gentle introduction to empirical process theory and applications.\" Lecture Notes, Columbia University 11 (2018): 28-29.\n\n"}]

Author rebuttal:

Meta-review: This paper considers the problem of learning under distribution shift. More generally consider the problem of learning from n samples where each sample $x_i$ is an i.i.d draw from a distribution $P_i$. Furthermore it is known that any two consecutive distributions are $\Delta$-close in TV distance. If $\Delta$ is known before hand then the best learning guarantee on can obtain is O((\Delta OPT)^{1/3}) where OPT is the error of the best function in class. It was open as to whether one can obtain the same guarantee without the knowledge of $\Delta$. The current paper solves this problem under the assumption that the labeled Y-discrepancy can be solved efficiently. The approach is simple but neat. It involves adaptively estimating the right sample size by repeatedly invoking an oracle for solving the discrepancy problem over samples in a window of size r and 2r for various values of r.

One reviewer very enthusiastically recommended the acceptance of the paper whereas the rest did not increase their scores during the discussion phase. The main points raised were: a) moving the difficulty of the problem from knowing $\Delta$ to solving a hard optimization problem, b) the "doubling" trick being not novel, c) lack of experiments.

Based on my own independent reading of the paper point c) is irrelevant. This is a theory paper and should be judged accordingly. Point b) is also unfair since the way the doubling idea is applied is clever in my opinion. Finally, I feel that point a) is not that serious of a problem since in many settings such as classification and linear regression, estimating discrepancy boils down to invoking an ERM oracle which is a very reasonable oracle to assume access to.

In my opinion this paper presents an important and novel advancement to the problem of learning under unknown drift and would be a very good addition to NeurIPS.
Decision: Accept (poster)