Adaptive Estimation and Learning under Temporal Distribution Shift
Authors: Dheeraj Baby
Yifei Tang
Hieu Duy Nguyen
Yu-Xiang Wang
Rohit Pyati
Venue: ICML 2025 poster (2025)
Keywords: Temporal Distribution Shift; Non-Stationary data; Total Variation Denoising
Primary area: general_machine_learning
TL;DR: We propose to use wavelet-denoising to obtain point-wise estimation error guarantees for estimating trend in time-series.

Abstract: In this paper, we study the problem of estimation and learning under temporal distribution shift. Consider an observation sequence of length $n$, which is a noisy realization of a time-varying ground-truth sequence. Our focus is to develop methods to estimate the groundtruth at the final time-step while providing sharp point-wise estimation error rates. We show that, *without prior knowledge* on the level of temporal shift, a wavelet soft-thresholding estimator provides an *optimal* estimation error bound for the groundtruth. Our proposed estimation method generalizes existing researches (Mazetto and Upfal, 2023) by establishing a connection between the sequence's non-stationarity level and the sparsity in the wavelet-transformed domain. Our theoretical findings are validated by numerical experiments. Additionally, we applied the estimator to derive sparsity-aware excess risk bounds for binary classification under distribution shift and to develop computationally efficient training objectives. As a final contribution, we draw parallels between our results and the classical signal processing problem of total-variation denoising (Mammen and van de Geer 1997; Tibshirani 2014 ), uncovering *novel optimal* algorithms for such task.

Adaptive Estimation and Learning under Temporal Distribution Shift
Dheeraj Baby' Yifei Tang' Hieu Duy Nguyen'
Yu-Xiang Wang" Rohit Pyati
Abstract
Concretely, we consider an estimation task where we are given access to independently drawn observations Un: In::...... such that E(y.] 0g E R and Var(u:) being finite for all i E [n]] := [m....,m.. Our goal is to construct estimate 01 for the most recent ground-truth 01. This estimation task is strongly related to various practi- cal scenarios, such as estimating/predicting the latest stock price, temperature, humidity or network traffic based on a sequence of historically observed and correlated measure- ments. We remark that any algorithm for the aforementioned problem setting can be directly used to construct estimates for ......, O2 mainly used for notational convenience.
In this paper, we study the problem of estima- tion and learning under temporal distribution shift. Consider an observation sequence of length n, which is a noisy realization of a time-varying groundtruth sequence. Our focus to develop methods to estimate the groundtruth at the final time-step while providing sharp point-wise esti- mation enror rates. We show that, without prior knowledge on the level of temporal shift, wavelet soft-thresholding estimator provides an optimal estimation error bound for the groundtruth. Our proposed estimation method generalizes existing researches Mazzetto and Upfal (2023) by estab- lishing a connection between the sequence's 's non- stationarity level and the sparsity in the wavelet- transformed domain. Our theoretical findings are validated by numerical experiments. Additionally, we applied the estimator to derive sparsity-awan excess risk bounds for binary classification under distribution shift and to develop computationally efficient training objectives. As a final contribu- tion, we draw parallels between results and the classical signal processing problem of total- variation denoising (Mammen and van de Geer. 1997; Tibshirani, 4a), uncovering novel opti- mal algorithms for such task.
as well. The reverse-indexing of time is
Note that constructing an estimator 0, itself is not enough. In many scenarios, we also need to provide statistical guar- anteey for such estimators, for example to calculate the risk profile of a stock-picking strategy for stock-price estimator. To achieve very high estimation quality, obtain point-wise performance guarantee for the estimate, i.e., a bound on |0 01| which is as small as possible. This requirement is more rigorous in comparison to controlling the estimation error for the sequqnce ....... O1 in terms of some aggregate performance metric. For example, a point- wise bound implies control over cumulative performance metrics like the mean squared error (MSE) regret from online learning (Hazan, 2016) is controlled.
would like to
A natural algorithm for estimating 01 is to average the most recent observations within a sliding window. However de- ciding on the optimal window size in a completely data- adaptive manner non-trivial. Choosing small window size will lead to an estimate with small bias but large vari- ance. A large window size will lead to variance reduction at the expense of introducing large bias. Hence to attain a sharp point-wise estimation error guarantee, one must choose a window size with an optimal bias-variance trade- off. The second challenge for this task is the dependency on the smoothness/stationnaity of the ground-truth sequence near the timepoint of interest, which directly influences the optimal window. In practice, we often do not have prior knowledge on the smoothness/sattionaiig of the ground- truth sequence. As a consequence, we also need to (poten- tially in an implicit way) learn the smoothness/sattionaiity of the underlying ground-truth sequence and adjust the aver- aging window size accordingly.
1. Introduction
Standard statistical estimation problems assumes access to independent and identically distributed (i.i.d)) observations. However, in many practical applications the familiar i.i.d. assumption often not applicable. Hence it is important to study the statistical estimation problem while relaxing such assumptions. In this paper, take a step in this direction by relaxing the identical distributed assumption on the observations.
1 Amazon F University Californa San Diego Correspondence to: Dhecraj Baby <dheerajbaby @ eegmalll.cmm..
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Adaptive Estimation and Learning under Temporal Distribution Shift
Signal with Sparse DBB Wavelet Decomposition
Ampituude
0
20
0
0
Ground Truth Observations
time
Wavelet Confficients Different
Level
Coeffiiiet Index
Figure 1: We have access to noisy observations of a ground truth signal, and our task is estimate the ground truth at the latest time. Although the ground truth signal appears to exhibit non-stationary trend in the time domain, the wavelet transform reveals sparse set of coefficients. As a result, we only need to estimate few key coefficients, enabling wavelet denoising-baat based estimators to achieve sharp point-wise and data-adaptive error rates.
A version of this problem has been posed an open prob- lem in Hanneke and Yang (2019) and was first addressed in the work of Mazzetto and Upfal (2023). In this study, we take a fresh look at the same problem and show that the famous wavelet soft thresholding algorithm (Donoho, 1995), using Haar wavelets, already recovers the results
the evolution of the groundtruth sequence with sparse set of wavelet coefficients, leading to fast estimation guaran- tees/bounds (see Fig. 1). On the other hand, in the presence of complex temporal evolution patterns, the optimal window chosen based on the notion of local stability can potentially be small which cause a moving-average average estimate incur larger error due to high variance.
from Mazzetto and Upfal (2023). The solution put forward by this paper based on the general machinery of wavelets not only offers fresh perspectives but also lead to deeper statistical implications on the estimation problem, which are described as follows.
We summarize our list of contributions below:
We show that a wavelet-denoising based algorithm us- ing Haar tranform achieves the optimal point-wise es- timation error guarantees similar to that of Mazzetto and Upfal (2023) (Theorem 2). Note that by using higher order wavelet transforms, it is possible to obtain a general error bound, based on the sparsity level of the wavelet coefficients of the ground-trutt which can be potentially sharper than the bounds obtained by using the Haar system (Lemma 1).
Specifically, as remarked earlier, the quality of estimation connected the stationarity (or smoothness) level of the ground-truth sequence. The more stationary the sequence is, sharper the guarantees/bounds of the estimate become. The solution in Mazzetto and Upfal (2023) leverages lo- cal stability to capture non-stationarity. i.c, their algorithm effectively chooses the largest window in which the ground- truth sequence (recall that the sequence formed by starting from time and going to less recent indices) has small vari- ation and is close to a constant signal. The larger such window is, the smaller the estimation error rate becomes since averaging with such window can lead to significant variance reduction while introducing only a little bias. Ap- proaching the problem from a different angle, we show that an estimator, based on wavelet soft thresholding, will result into an estimation error which strongly correlates with the sparsity of the wavelet coefficients of the ground-truth se- quence. From that perspective, the stationarity level of the ground-truth is strongly connected to the sparsity level of the wavelet coefficients. Our approach based on wavelet coefficients' sparsity is more general than the notion of local stability. For example, by using higher order Daubechies wavelets, one can potentially capture complex trends in
We present a rigorous theoretical examination of dis- tribution shift's consequences for machine learning models, conclusively showing that temporal variations undermine model performance. (Section 3).
We consider the problem of binary classification under temporally shifted dataset. By using wavelet-based loss estimators, we obtain an oracle-efficient and statis- tically near-optimal algorithm that requires single call empirical risk minimization (ERM) oracle, thereby improving the computational efficiency in compari- son to the algorithm proposed in Mazzetto and Upfal (2023) which requires (log n) ERM calls (Theorem 9). Furthermore for differentiable surrogate losses, our ERM objective preserves the differentiability and en-
2

---

Adaptive Estimation and Learning under Temporal Distribution Shift
ables oracle-efficient procedures, unlike the methods in prior works (Section 4).
Algorithm 1 Wavelet-Denoising Algorithm
1: Input: data yn,...., 91 E RR4, Wavelet Transform ma- trix W, soft-threshold X, failure probability 8.
We prove general result that any algorithm obtaining point-wise estimation enror guarantee similar to that from our proposed wavelet denoising algorithm under Haar system (see Theorem 2) is automatically mini- max optimal for the problem of votal-variation (TV) denoising. This reveals a previously unknown mini- max optimality of several existing algorithms for the
Initialize y +- [pr: ./........... 311"" R".
3: Compute empirical wavelet coefficients 3 +- Wy.
4: Compute denoised coefficients ,3 + (3)), where for an E RR (x(z) := sign(x) max X, X,0} is the soft- soft-thresholding operator. When acted upon vector, the soft-thresholding is performed coordinate- wise.
5: Reconstruct ka. inverse wavelet transform) the signal by Ô <- W 3.
TV denoising problem (Section 5).
Finally, we present numerical results to showcase the superior performance of our proposed (higher order) wavelct-denoising based algorithms in estimating the ground-truth, compared to prior works (Section 6.1).
Return the last coordinate of O.
with a simple property of soft-thresholding operation.
Lemma 1. Consider the observation model yi - 0: + ei for
1...., n with e, being iid u-sub-gaussian ran- dom variables. Let == [wn.....11] 0 = [o.....,)) 01] and W be an orthonormal wavelet transform matrix. Let 3 == Wy and (3 == WO be respectively the empirical and true wavelet coefficients. Let I be an index set of wavelet coefficients that affect the value of reconstruction of the last groundtruth 02- Let W be the value of the element in 8th row and 1hth column of W. Let 0 be the estimate of the groundtruth 0, obtained via Algorithm I with À 20 /2 logg(oo n/8). Define (aAb)= == minfa, b}. we have with probability at-least 1 5 that
The rest of the paper is organized as follows: Section 2 presents our theory and algorithm for estimating the ground truth. Section 3 analyzes train-test distribution mismatch, followed by a binary classification algorithm for temporally drifted data in Section 4. Connections to TV-denoising are explored in Section 5, and experimental results are in Section 1. Due to space constraints, discussion on related works and preliminaries are deferred to Appendix and B respectively.
2. Estimation Under Temporal Distribution Shift
10, - -015
Σ SEZ
In this section we consider the estimation setup specified in Section 1 and study algorithmic approaches to estimate the groundtruth at the latest time. This will later help to train ML. models under training distribution shift in Section 4.
Next we show that if we use the Haar wavelet system in Algorithm 1, one recover the variational bounds similar to the results in Mazzetto and Upfal (2023), indicating the versatility of the wavelet-based solution.
2.1. Algorithm
Theorem 2. Let 0 = (01 + + 6,)/t. /t. For a time- point r, let Sr) = {1, 21,2,4 4,4 4,...... 211022 r.). Let U(r)= = max 10.1 021) val fi and minre U(r)= == U(r") with being the smallest time-point where the equal- ity holds. By using the Haar wavelet system in Algorithm 1, we have with probability at at-least 8 that
We propose to use wavelet-denoosing-basss algorithm, which is adapted from the well-known idea of wavelet smoothing (Donoho, 1995). The algorithm is presented in Algorithm for the sake of completeness. A fundamental difference between the wavelet-based solution and algo- rithms from prior works (Mazzetto and Upfal, 2023; Han the latter maintain an adaptive window-sizz for averaging the relevant past observations, the wavelet-based solution maintains no such window-size. Instead it implicitly uses the most relevant portion of data to estimate the groundtruth at the final time-step.
et al., 2024) is that while
10 - 00-- (K.UUK))
where K (4 2log 2 (a (a = b).
2 n+ + 1) and
Although the above theorem is a testament to the versatil- ity of wavelet-based methods for the estimation problem, we remind the reader that it is only an upper-bound to the general bound developed in Lemma 1. Lemma I holds the potential to achieve faster estimation error rates by leverag- ing the sparsity of wavelet coefficients in any user-specified wavelet transformed space. This is indeed corroborated by
2.2. Analysis
All proofs of this section are deferred to the Appendices. We emphasize that all the estimation error bounds presented in this section are achievable by Algorithm without any prior knowledge on the degree of distribution drift. We begin
3

---

Adaptive Estimation and Learning under Temporal Distribution Shift
our numerical experiments in Section 6. Though we do not provide specific construction where Lemma 1 can lead to faster error rate than that of Theorem 2, we empirically compare the corresponding upperbounds in Fig.5 (Appendix E) to validate this idea. However, a limitation of Lemma is that for general wavelet transform matrices, it does not guarantee a rate that is at-least as good as the one given by Theorem 2, obtained via using Haar wavelets. In the following corollary, we derive fail-safe guarantee obtained by using specialized wavelet system, namely the CDJV wavelets (Cohen et al., 1993), in Algorithm 1.
output y, and testing data Drs distribution, with 0 denotes the model parameters. Note that po po(vlx) is obtained by training the model with training data Drr.
Lemma 4. (Two Forms of the Log-Loss Function, adapted from (Achille and Soatto, 2018)) The log-loss [(0, Drr. Drs) can be expressed in two forms
S(0,Drrs Dr.)= -KL (pD,, (.DD,,(()))))))). (ylx))/po()))>))
+ H (pDr, (1)x))
Corollary 3. For a sequence Oa:h (a > b). de- fine TV()u.)) = E5=0+1 10 - 0--1|- For a time- point T, let S(r) == f1,2, 4, 21...,,!!o00?!!!
[(0, DIr. Dre) KL (x,
U)) (x)]lo (x)) + H (pDr. (v/x)) (2)
Let (r) = max(Es(() 17 - 011) V olvr and min,.e(.....)) (r) (r() == (rr') with r" being the small- est time-point where the equality holds. Define k (4v2 loggoggooo n/ V 21o2) n 1). By using CDJV wavelet transform with 2 vanishing moments in algorithm 1, we have with probability at-least 1- - 8 that
in which PDr, (y/x) and pe po(y)x)) are the conditional dis- tribution of the label for testing data and predictive dis- tribution, respectively; KL (pllg) is the Ballback-eeible divergence of two distributions p and q; and H (p) is the entropy of distribution p.
During the model training, we only have access to DIr and the loss function is measured/tested on a val- idation data which is subset of Drr- Substituting DT. into DT in (1,(1), we have Ltrasning (0, Dr+) ~ (U(p..,.ylx
x), ())0)))) ))
101 001=000 = O min Σ W..ll (13.) A A), (18111)))11)))))))))11) VEI
(v/x))/ (e(lx)) as H. (U/x)) is a constant, which independent of the MI. model and its conditional probabilitylogii function (o/)x) To achieve the minimum value for the log-loss, the KL-divergence should be driven towards O.
The above corollary guarantees a robust fail-safe estimation error. However, there are some caveats when comparing it against the result given in Theorem 2. Consider the scenario where the minimum in the bound given in Corollary 3 is achieved by (rr*) term. We remark that in such situation, the bound in Theorem 2 can be tighter because U(r") < (r"). However, as we shall see in Section 5, a bound of the form given in Corollary 3 is already sufficient to imply optimal estimation rates for the TV-denoising problem. This illustrates one utility of (r)") type bounds.
As the focus is to study the effect of distribution shift, we will assume an infinite number of samples from the train- ing data for perfect model training, and hence neglecting concentration arguments for the ease of presentation.
Assumption 5. (Perfect ML Training) To investigate the effect of data distribution shift, we will assume a perfect MI. model and training process, ie, we are able to achieve pe p)())x) = =Drr, x).
3. Effect of Distribution Shift on the Model Performance
In the previous section, we proposed wavelet-based methods for estimating quantities during temporal distribution shifts. We now explore the rationale behind developing learning algorithms specifically designed for distribution shift scenar- ios. This section aims to theoretically demonstrate how and why model performance deteriorates when the training and testing distributions deviate. We first offer a theoretical ex- amination of the machine learning model's loss function and comparing its behavior across training and testing datasets. Through our analysis, we establish upper and lower bounds for the loss function, which are directly influenced by the proportion of dissimilarly distributed/Shiitee samples. All proofs are deferred to the Appendices.
Note that without Assumption 5, the model can train with Dr, distribution but output another distribution D, and if D = Dr, then seemingly bad model can perform sur- prisingly well. In subsequent sections, we will consider more realistic assumptions, i.c. limited training data and imperfect machine learning training processes.
From the first form of the log-loss function, i.e, Eq.(1), is tempting to already conclude that distribution shift leads to model degradation. However, the first form Eq.(I) only refers to the divergence in the predictive distribution and con- ditional distribution of the label. In practical and real-world scenarios, it is more general and realistic to consider a shift in the dataset/joint probability (x, y) (Quionero-Cami et al., 2009; Harutyunyan et al., 2020). For example, when we add more samples into the training data, such addition
We first derive the log-loss of an ML model via its predictive distribution Po (y)* x), with input covariates x and model
4

---

Adaptive Estimation and Learning under Temporal Distribution Shift
leads shift in PDr, (x, y) first and foremost instead of directly leading to a shift in pDr, (y]x). The second form (2) provides the connection between the sample (x, v)
A direct consequence of Theorem 7 is the below corollary
Corollary 8. Under Assumption S, the model performs worse when we add more samples a distribution, which is different from the testing data, into the training data. Conversely, the model performs better when we add more samples the testing distribution into the training data.
and covariance x shift.
The first term in (1) and the first two terms in (2) represents the loss due to the distribution shift. That loss minimizable by optimizing the model parameters 6. The term H. (PDr. (f/x)) represents the intrinsic error (Achille and Soatto, 2018) to learn dataset and it is not optimizable. For example, assume that we have an image dataset with two labels "dog" and "cat". For each image x we toss a coin and label the image as "dog" if head, and as "cat" if tail, irrespective of the image itself. In such case, H (pDr, (1/ x)) and the log-loss are very high (in fact, maximized) and the model performance is extremely bad, even if we have perfect ML training and use the test dataset to train the model.
Theorem 7, established under Assumption 5 (which as- sumes an idcalized machine learning model and training process), provides best-case performance boundaries. The lower bound thus reveals an inherent limitation: regardless of the sophistication of our learning algorithm, model per- formance will decline as the dissimilarity ratio 3 increases. Despite recent literature suggesting that doing naive ERM might perform adequately across different distributions, our analysis demonstrates that predictive power will substan- tially deteriorate in worst case, as training and testing dsitri- bution diverge. It is worth noting that we need both lower and upper bounds of the log-loss. The reason is that the lower bound in Theorem 7 can only says how worse the loss can become. The further from 0, the worse the loss is. When B, the lower bound reduces to the conclusion that the loss is larger than 0 (see Appendix D), which is trivial. Only an upper-bound confirms that the model gets better when having more similarly distributed training samples versus the testing data.
To investigate the effect of distribution shift, we consider two scenarios usually observed in practice. Specifically, we define Training Distribution Shift Scenario as when the testing data is fixed, and we are able to gather more data samples in the past and train the model with new data to make better predictions. Conversely, we define Testing Distribution Shift Scenario when we collect the training data and train the model only once. Afterwards, the model is used for inference for all testing samples in the future. Definition 6. (Training (or Testing) Distribution Shift Sce- mario) The training (or testing) data distribution Dr con- sists of two distributions Dri and Dr2 Denote and 3 as the proportion of samples from Dri and DD2 in Dr, respectively with a + 3 = 1, we have
4. Learning Under Temporal Distribution Shift
In the previous section, our analysis reveals the performance decline inherent when training and testing distributions dif- fer. Consequently, developing robust learning algorithms that can mitigate this degradation is an important research objective. In this section, we study the fundamental sta- tistical problem of binary classification under training dis- tribution shift. We are given access to n covariate- pairs: (Xn, Un)...., (x2, V2), (1) along with a hypoth- esis class F. We assume that for each i E [1...., m). (x4, v:) is independently sampled from distribution D,- Let ((f(x),)) with hypothesis f E F on the example (x, where I is the binary indicator function. The population level loss of a hypothesis f on the testing distribution D; is Ly := Exx,r)-,, (((( Y)]. We are interested in find- ing a hypothesis whose population level loss on testing Distribution D1 is close to minser Lj := Ly. for some f. E F. More precisely are interested in finding hypothesis f whose excess risk given by Lj- L,. is con- trolled.
PD, (x. 3) appr (x. 3) + SpDr2 (x. y)
(3)
Here T represents training data T = Tr (or testing data T= Ts) and T1 = Ts (or T = Tr).
Under the Training Distribution Shift Scenario, the train- ing data T = Tr consists of (1) samples from the testing distribution T1 = T's, and (2) samples from a dissimilar dis- cesiimilarly-ditributtte samples from 72 are added into the training distribution, this leads to higher dissimilarity ratio 3. Under the Testing Distribution Shift Scenario, the testing data T T's con- sists of (1) samples from the training distribution T1 = Tr, and (2) samples from dissimilar distribution T2. When, more and more saaiimllarly-ditribbur
tribution 722. When, more and more
I(f(x) # y) be the loss associated
samples from T2 are added into the testing distribution, this leads to higher dissimilarity ratio 3.
We are now ready to investigate the effect of the distribution shift. One of our contributions is the following theorem Theorem 7. Under Assumption 5 and for distribution shift scenarios specified in Definition 6, the log-loss is bounded above and below by monotonic non non--ecreasee decreasing functions on 3: L3B(3) S C(0, Dry, Drs) & (B).
This differs from standard statistical learning, where we assume n i..dd samples from D2 are used to learn a hypoth- esis (Bousquet al., 2004). Since we observe only a single
5

---

Adaptive Estimation and Learning under Temporal Distribution Shift
labelled datapoint from D1. pooling recent data based on shift severity is crucial. The challenge is determining how
the excess risk to sparsity (and hence the degree of temporal stationarity) of the sequence of population level losses in wavelet transformed domain. Hence this bound can be potentially much sharper than those obtained by constrain- ing the wavelet transform to be Haar. A fail-safe guarantee similar to that of Corollary can be obtained by using CDJV wavelets.
much past data to use for training, without prior insight into the shift's s intensity. To address this, we perform ERM using the loss estimates from Section 2, leading to the following excess risk control.
Theorem 9. For a function f E F, we defined obtain its estimated loss & as follows. Run Algorithm 1 with data ((f(x)); (ff((x))))) y1) as input. Let y be the estimate returned by Algorithm 1. The ERM is defined by f gegmingerly
We note that the logarithmic improvement in computation stems from simple but careful technical observation. More precisely, one can reduce the computational complexity of the procedure in Mazzetto and Upfal (2023) by estimating the loss of each function f E F separately while performing the ERM. This is realizable by taking the input function class to their algorithm to be the singleton set (Cf) with é defined by the mapping Ey X' X'yy - {(f(x), y). However, doing so poses major challenge when optimizing with surrogate losses. We elaborate on this aspect as follows.
For a function f E F, let 0 := [ED(((Xnn) Boll ..... Fe
(X1), y1 ).. Let 3) Lei == WA for a wavelet trans- form matrix W. Consider the index set I defined in Lemma Let d be the VC dimension of F. We have with probability at-least 1 5,
2d 2d + +
2 1og(3/6)
Though the result in Theorem 9 concerns with binary zero- one loss, one is often interested in solving the ERM (pos- sibly sub-optimally) via the use of differentiable surrogate losses and optimizing the objective via gradient descent. Given a differentiable surrogate loss, one can form an ERM objective based soft- soft-thresholding the surrogate loss se- quence similar to what is done in Theorem 9. Such an objective is differentiable almost everywhere. In contrast, estimating the loss of each function separately using the pro- cedure from Mazzetto and Upfal (2023) renders the ERM objective diffferrentteble. The con-differemtiability stems from the fact that their estimator is constructed based on the output of a sequence of data-dependent binary comparisons.
I.j L.. 88
n
n
v3. sup Σ FEF iEI
6l (18/1A ^ 20 Aed log 2n/5))
Assuming that the wavelet transform in Theorem 9 is the Haar transform and applying Theorem 2, we obtain the following corollary.
Corollary 10. Let D. = - +E Dr. Define (f((x)))) |D= Dill= = AEPFETEEXXYY (,, Y)] E( (e( as the discrepancy measure. Consider W in Theorem 9 to be the Haar transform matrix. Then the excess risk is bounded with probability at-least 1- by
5. Optimal Error Rates for Potal-Variatie Denoising
2d (2n)
2 230((3/5)
Lj- - Ls. S 88y
+ +2/
In this section, we prove a black-box result that any algo- rithm that satisfies bounds of the type studied in Theorem 2 or Corollary 3 can imply optimal estimation eтror rates for TV-denoising problem. To the best of our knowledge, such an implication has been not uncovered before in literature. Apart from being result of theoretical interest, helps un- cover the previously unknown optimality of some existing algorithms for the problem of TV-denoising.
x min rE[m]
max
|1, - Dill=) V ddrr)
(rES(r)
where K- = (4v4 4 1og(33 log 2n/0) V (2ogz n + 1) and S(r) is as defined in Theorem 2.
Discussion of our results in contrast to prior work. We remark that an optimal answer to the problem of classifi- cation under temporal training distribution shift has been given by Mazzetto and Upfal (2023) in the form of bound similar to that in Corollary 10. Their solution relies on mak- ing (log n)) calls to an ERM oraele obtain a minimizer that can control the excess risk under the distribution Dj. In contrast, our solution requires exactly one call to the ERM oracle. The tradeoff for this computational improvement is the inflation of the excess risk bound of the prior work only by a factor of (log n). We remark that the result in Theo- rem 9 is more general than the prior work since it connects
In TV-denoising problem, we are given access to n obser- vations of the form y/ = 6₂- - Es. t = 1...., n where é, are i.i.d. o-sub-gaussian observations. Our goal is to form estimates fI.m of the groundtruth 01... from the noisy obser- vations. To impose regularity/structuee to the underlying ground truth, one can define the Total Variation (TV) class as follows.
6

---

Adaptive Estimation and Learning under Temporal Distribution Shift
is the version of Algorithm 1 that uses Haar wavelets. 3)
AVG is the algorithm from Mazzetto and Upfal (2023). 4) ARW is the algorithm from Han et al. (2024). 5) Aligator is the trend forecasting algorithm (hedged version) from Baby et al. (2021).
TVCC) - Opm Σ 10 0 10--
{
wherein the quantity C' is viewed as the radius of the TV class. We assume that the groundtruth sequence satsifies 0im E TVC).. We remark that one can also define alternate sequence classes based on penalising the sum of squared differences of sequence, For eg. Σx= 10,- ft-1/² < C2. We defer the reader to Baby and Wang (2019) for an exposi- tion why the TV class is more expressive and statistically challenging to estimate than such sequence classes.
Experimental methodology. First a ground-truth signal is generated. We considered two types of ground truth signal as shown in Fig.4. The Random signal features a signal which can be either 0 or 1 based the output fair coin flip and Doppler features a trend with spatially varying degree of smoothness, All signals lie within the range (-1.5, The ground-truth sequence is generated by sampling these signals at 500 equispaced points. To generate the observations, we add independent uniformly sampled noise from [-B, B] to the ground-truth signal for each of the 500 time-points. The quantity B is varied across the levels {0.2, 0.5, 0.7, to study the behaviour of the algorithms across different noise-levels. At any time- point, the baselines (except Aligator) use all the observations from history including the current time-point to estimate the ground-truth. The Mean Squared Error (MSE) across all 500 time-points are measured. All experiments were conducted across 5 trials. We report the average MSE and associated standard deviations across the trials. The failure probability parameter for all algorithms is set to be 0.1.
To measure the quality of risk estimates, we focus on two commonly used risk functionals in practice as follows: (0y (11:01100000 01:,) = (0, - 0.)² and Rans (0n (0 01m) Ei=1 U,- Orl-
We are interested in coming up with estimators that can attain this min-max error lower-bounds (upto log terms).
Theorem 11. Suppose that an algorithm satisfies a bound of the form given in Theorem 2 or Corollary 3. Consider running the algorithm iteratively produce the estimates Ova- Then with probability at-least 1 - 8 we have that
Rag (8 01m) = Ö(n! /3 2213
Rabi (01m, 01m) = ((/2/3
We report the results by considering two scenarios. In the first case, the standard deviation of the noise is exactly known. In this case we adjust the constants in Algorithms and that of AVG according to their theoretically optimal values. Next, we consider the case of no prior knowledge of the standard deviation. The algorithms ARW and Aligator are directly applicable to this scenario since they do not require prior knowledge of the standard deviation. As a con- sequence, for a fair comparison, we report another table in which AVG and wavelet based thresholding algorithms are executed via bounding or estimating the standard deviation while displaying alongside the results from algorithms ARW and Aligator. For the wavelet-basee algorithms, an estimate of the standard deviation is formed based on the Median Absolute Deviation (MAD) of the wavelet coefficients at the highest resolution similar to as done in Donoho et al. (1998). For AVG, a bound on the observed values are used as a proxy. The results are reported for the known standard deviation and the case of unknown deviation respectively in Tables 1 and 2.
These rates can be shown to be optimal modulo log terms (Donoho et al., 1996). We note that the algorithms in Mazzetto and Upfal (2023); Han et al. (2024) already sat- isfy a bound of the form in Theorem 2. Thus Theorem 11 uncovers new off-the-shelf optimal algorithms for the TV-denoising problem.
6. Experimental Results
In this section, we validate our findings on synthetic and
real-world data.
6.1. Experiments on Synthetic Data
In this section, we report the results obtained from simu- lation studies. As discussed before, the algorithm from Mazzetto and Upfal (2023) aims to capture the non- stationarity in terms of local averages of a sequence. This can potentially sege-ssmotth/nnde-smooooe
trends in the ground-truth which may not always assume a piece-wise constant structure. In this section, we show that Algorithm 1 is superior in capturing wider range of trend patterns, while Lemma I and Theorem 2 achieves faster estimation error rates.
Interpretation of results. For the case of known stan- dard deviation, the wavelet-based algorithms are found to perform better than AVG. In almost all cases, we see signifi- cant improvements via the usage of wavelets across various noise levels with biggest improvements observed in the high signalonoise-ratio regime. This validates the ability of wavelets to produce sharp estimation error rates. In particu-
Baselines. 1) DB8 is the version of Algorithm 1 that uses Daubechies wavelet with 8 vanishing moments. 2) HAAR
7

---

Adaptive Estimation and Learning under Temporal Distribution Shift
Noise
HAAR
DB8
Noise Level
HAAR
DB8
Level
AVG
(Thir paper)
(This paper)
AVG
(Thix poper)
(Thir paperi
0.2
0.205 0.00+1
0.034
0:0014
0.0661 + 0.0026
0.2
0.611 + 0.0013
0.0GS I 0,0035
0.007 = 0.0002
0.3
0.202
= 0.0095
0.154
2 0.0087
0.091 = 0.0020
0.3
0.510
= 0.0020
0.103 E 0.0060
0.013 = 0.0003
0.209
0.0077
0.191
0.0065
0.119 1 0.0042
0.5
0.509 1. 0.0003
0.155 1 0.0113
0.032 1 0.0007
0.7
0.208 0.0082
0.182 0.0077
0.147 + 0.0051
0.7
0.508
+ 0.0002
0.155
+ 0.0162
0.061 + 0.0014
0.214 0.0019
0.174 0.0100
0.212 I 0.0062
0.508
= 0.0081
0.135 = 0.0221
0.1
= 0.0028
(a) Ground truth: Random
(b) Ground truth: Doppler
Table 1: MSE of different algorithms when the noise standard deviation is known. Groundtruth signals used are shown in Fig.4 (Appendix E).
Noise Level
HAAR
DB8
AVG
ARW
Aligator
(This paper)
(This paper)
0.2
0.210 + 0.0045
0.203 - 0.0079
0.214 = 0.0086
0.243 + 0.0218
0.188 - 0.0155
0.3
0.204 + 0.0060
0.205 + 0.0079
0.214 = 0.0071
0.258 + 0.0224
0.188 + 0.0191
0.5
0.210 = 0.0080
0.214 = 0.0078
0.212 = 0.0066
0.271 + 0.0087
0.214 0.0058
0.7
0.209 = 0.0081
0.205 = 0.0053
0.222 = 0.0070
0.270 + 0.0081
0.238 = 0.0143
0.219 + 0.0062 1
0.211 + 0.0115
0.213 = 0.0103
0.289 + 0.0196
0.307 = 0.0151
(a) Ground truth: Random
Noise Level
HAAR
DB8
AVG
ARW
Aligator
(This paper)
(This paper)
0.2
0.512 + 0.0021
0.3844 + 0.0052
0.234 + 0.0021
0.053 = 0.0017
0.0204 0.0007
0.3
0.512 + 0.0032
0.389 + 0.0077
0.234 + 0.0032
= 0.0018
0.0265 = 0.0010
0.5
0.512 + 0.0053
0.400 = 0.0136
0.235 = 0.0055
0.065 0.065 0.0018
0.0444
0.7
0.512 = 0.0074
0.402 + 0.0181
0.235 + 0.0078
0.002 0.0031
0.070 + 0.0021
0.514 = 0.0106
0.407 = 0.0215
0.235 + 0.0111
0.088 = 0.0035
0.129 + 0.0058
(b) Ground truth: Doppler
Table MSE of different algorithms when the noise standard deviation is unknown.
lar, the usage of higher order DB8 wavelet produces lowest estimation error in most cases since the DB8 wavelet system can capture complex trends more effectively than the HAAR system (which is also known as the DB1 wavelet which is of lower order than DB8). Similar observations are carried forward to the unknown standard deviation regime. Both Aligator and wavelet based methods outperforms ARW and AVG in most cases. A fundamental difference between these algorithms is that ARW and AVG are based the estimate produced by single predictor, while Aligator and wavelet based algorithms ensembles a set of base predictors to form the final prediction. For wavelet based methods, the base predictors are the wavelet bases and ensemble weights are precisely the denoised wavelet coefficients. Intuitively, the ensemble nature of these algorithms enables to outper- form the counterparts by achieving an improved variance reduction. We remark that we used theoretically recom- mended values for constants that guide the restart/selection decisions in AVG and ARW. Tuning those constants in an online setting is otherwise unclear. The algorithm Aliga- tor is known to produce minimax optimal MSE rates for
estimating ground truth signal from noisy observations (Baby et al., 2021). However, point- wise bound on the estimation quality similar to Theorem 2 is not known for Aligator. In contrast, the methods HAAR and DB8 comes with strong point-wise error bounds (Lemma and Theorem 2) which translates to improved performance in practice. In the unknown standard deviation regime, we see that AVG and ARW performs slightly better than HAAR and DB8 for certain noise levels for the Random signal. AVG and ARW are designed to detect (nearly) stationary portions in signal and average the stable portions to compute the final estimates. Hence Random signal by virtue of its piecewise constant nature becomes a favourable prior to AVG and ARW performing slightly better than other methods with when provided with noisy estimates of the standard devia- tion. However, in almost all cases for Random signal, the performance of all algorithms are roughly comparable (with difference only in the second significant digit, see Table 2) which in turn emphasizes the robustness of ensemble based methods like Aligator, HAAR and DB8 even when the standard deviation unknown. Further empirical results
8

---

Adaptive Estimation and Learning under Temporal Distribution Shift
Method
79%-1% Split
75%-5% Split
Mo Mayhlt My by Nap
ARW
0.0719#000005 0.0722:10.0006
0.0790 + 0.0005
13.0
HAAR (ours)
0.0736 + 0.0011
DB8 (ours)
0.0762 + 0.0002
0.0768 + 0.0008
13.6
Table 3: Average test MSE + standard error on the Dubai Land Department dataset over 192 months and 5 runs.
Extimoted
13.4
13.2-
are deferred to Appendix E.
13.0
100
Time
6.2. Experiments on Real Data
Figure 2: Mean house prices vs time in Dubai housing data (reproduced from Han et al. (2024)). The pricing trend is abrupt and highly non-stationary.
As an application of our proposed methods, we conduct a model selection experiment using real-world data. We evaluate our method on data from the Dubai Land Depart- ment (Land Sales) following the setup identical to that of [2]. The dataset includes apartment sales from January 2008 to December 2023 (192 months). Each month is treated as a time period, where the goal is to predict final prices based on apartment features. Data is randomly split into 20% test, with two train-validane splits: (a) 79%- - 1% and (b) 75%- 5%.
6.3. Notes to Practitioners about Wavelet Selection
We close off the experimental section by few remarks about how one can select a wavelet system in practice for the use in Algorithm 1. Practitioners typically analyze data trends if they follow a piecewise polynomial of degree k. a wavelet of order k + is chosen, effectively models such struc- tures. However, higher-order wavelets introduce numerical instabilities and variance, though the latter can be mitigated with more data. Selecting a wavelet basis is akin to choos- ing a kernel in Gaussian Processes-apy pepessses-apppicationsspccciieeo and guided by practical intuition. A more comprehensive exposition can be obtained from Mallat (2008).
For each month 1, we train Random Forest (Breiman, 2001) and XGBoost (Chen and Guestrin, 2016) models using window of past data where we consider window sizes w E [1, 4, 16, 62, 256]. yielding 10 models per month. Validation mean squared error (MSE) from past and current months are used to refine the current month's 's estimate of MSE via Algorithm or ARW from Han et al. (2024). The refined validation scores used select the best model for final MSE evaluation on test data. We report the average MSE of this model selection scheme over 192 months and 5 independent runs, comparing our method to ARW. In Table 3, HAAR and DB8 are versions of Algorithm with the corresponding wavelet basis given as input.
7. Conclusion, Limitations and Future Work
We introduced wavelet-based approach for estimating non- stationary time series with strong point-wise error guaran- tees. Our solution offers a fairly general perspective to this problem compared to prior works. Using Haar wavelets recovers prior results, while advanced wavelets enable es- timation of complex trends. Our findings extend to binary classification, leading efficient algorithms, and uncover new optimal methods for TV-denoising. Experiments on real and synthetic data show notable improvements over previous work.
We see that wavelet based methods shine especially when the validation data is scarce. This allows us to include more data for training while still allowing to obtain high quality estimates for validation scores. Such property can be especially helpful in data-scarce regimes. Unlike the synthetic data experiments, here we find that Haar wavelets perform better than DB8. This can be attributed to the following facts: i) the noise in the observations depart from iid sub- bab-gaussiinn assumption and; ii) the high degree of non-stationarity in the pricing data as indicated by Fig.2 makes the underlying trends to have low degree piecewise polynomial structure. This render the groundtruth irregular (or less smooth) which can be suitably handled by lower order Haar wavelets which are also less smooth and abrupt (see Fig.3).
There are some limitations that we leave to be addressed in future works. Principled ways to select an appropriate wavelet system for given task of interest needs additional investigation. Unlike prior approaches that use adaptive window sizes for moving averages, our method implicitly leverages relevant data portions. However, maintaining a window-size can have meaningful implications to change- point detection. Exploring the utility of our methods to this extension remains as an interesting direction to explore.

---

Adaptive Estimation and Learning under Temporal Distribution Shift
Acknowledgments
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79(1), 2010.
We thank Jiaxing Zhang and Alessio Mazzetto for insightful early discussions that helped shape the direction of this
work.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non- stationary stochastic optimization. Operations research, 63(5):1227-1244, 2015.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Albert Bifet and Ricard Gavaldà. Learning from time- changing data with adaptive windowing. In Proceedings of the Seventh SIAM International Conference on Data Mining, April 26-28, 2007, Minneapolis, Minnesota, USA, 2007.
References
Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi. Introduction to Statistical Learning Theory. Springer Berlin Heidelberg, 2004.
Alessandro Achille and Stefano Soatto. Emergence of in- variance and disentanglement in deep representations. Journal of Machine Learning Research, 8, 2018.
Leo Breiman. Random Forests. Springer, 2001.
Dheeraj Baby and Yu-Xiang Wang. Online forecasting of Notal-variation-buurre sequences. In Neural Information Processing Systems (NeurIPS), 2019.
Tiffany (Tianhui) Cai, Hongseok Namkoong, and Steve Yadlowsky. Diagnosing model performance under distri- bution shift. Proceedings of the International Conference on Machine Learning (ICML), 2022.
Dheeraj Baby and Yu-Xiang Wang. Adaptive online estima- tion of piecewise polynomial trends. Neural Information Processing Systems (NeurIPS), 2020.
Tianqi Chen and Carlos Guestrin. Xghoost: A scalable tree boosting system. KDD '1, 2016.
Dheeraj Baby and Yu- Yu-Xiang Wang. Optimal dynamic regret in exp-concave online learning. In COLT, 2021.
Xi Chen, Yining Wang, and Yu-Xiang Wang. Non-stationary stochastic optimization under lp. q-variation measures. 2018.
Dheeraj Baby and Yu- Yu-Xiang Wang. Optimal dynamic regret in proper online learning with strongly convex losses and beyond. AISTATS, 2022.
Albert Cohen, Ingrid Daubechies, and Pierre Vial. Wavelets on the interval and fast wavelet transforms. Applied and Computational Harmonic Analysis, 1(1):54 - 81, 1993. ISSN 1063-5203.
Dheeraj Baby and Yu-Xiang Wang. Second order path variationals in non-stationary online learning. AISTATS, 2023.
Thomas Cover and Joy Thomas. Element of information theory, 2nd edition. Wiley-Intersccenne,, 2006.
Dheeraj Baby, Xuandong Zhao, and Yu-Xiang Wang. An optimal reduction of tv-denoising to adaptive online learn- ing. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, 2021.
Ashok Cutkosky. Parameter-free dynamic, and strongly- adaptive online learning. ICML, 2020.
Amit Daniely, Alon Gonen, and Shai Shalev-Shward Strongly adaptive online learning. In International Con- ference on Machine Learning, pages 1405-1411 2015.
Dheeraj Baby, Saurabh Garg, Tzu-Ching Yen, Sivaraman Balakrishnan, Zachary Chase Lipton, and Yu-Xiang Wang. Online label shift: Optimal dynamic regret meets practical algorithms. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
David L Donoho. De-noising by soft-thresholding IEEE Iransactions on information theory, 41(3))613-627, 1995.
David L. Donoho, Iain M. Johnstone, Gérard Kerkyacharian, and Dominique Picard. Density estimation by wavelet thresholding. The Annals of Statistics, 1996.
Dheeraj Baby. Boran Han, Shuai Zhang, Cuixiong Hu, Yuyang Wang, and Yu-Xiang Wang. Adapting to online distribution shifts in deep learning: A black-box approach. In Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, Proceedings of Ma- chine Learning Research, 2025.
David Donoho, lain M Johnstone, et al. Minimax estima- tion via wavelet shrinkage. The annals of Statistics, 26 (3):879-922 1998.
10

---

Adaptive Estimation and Learning under Temporal Distribution Shift
Marco Federici, Ryota Tomioka, and Patrick Forré. An information-theoreti approach to distribution shifts. Pro- ceedings of the Annual Conference Neural Information Processing Systems (NIPS), 2021.
Land Sales.
Did transactions
open data.
https://wwet htttp::/www..dbba.puts www.duuwwwpie..ee.om gov.
ht//daaa/lld-taanssctiioooooo /dld_
tzansactions-open Accessed: 2025-05-19.
Adityanand Guntuboyina, Donovan Lieu, Sabyasachi Chat- terjee, and Bodhisattva Sen. Adaptive risk bounds in univariate total variation denoising and trend filtering. 2017.
Philip M Long. The complexity of learning according to two models of drifting environment. Proceedings of the Conference on Computational Learning Theory (COLT), 1998.
Elise Han, Chengpiao Huang, and Kaizheng Wang, Model assessment and selection under temporal distribution shift. In Proceedings of the s1 International Conference on Machine Learning. PMLR, 2024.
Stephane Mallat, wavelel tour of signal processing. Aca- demic Press, San Diego, 2008. Third edition.
Enno Mammen and Sara van de Geer. Locally apadtive regression splines. Annals of Statistics, 25(1):387-413, 1997.
Steve Hanneke and Liu Yang. Statistical learning under nonstationary mixing processes. In Proceedings of the Twenty-Second International Conference Artificial In- telligence and Statistics, Proceedings of Machine Learn- ing Research, 2019.
Alessio Mazzetto and Eli Upfal. An adaptive algorithm for learning with unknown distribution drift. Proceedings of the 37th International Conference Neural Informa- tion Processing Systems, 2023.
Steve Hanneke, Varun Kanade, and Liu Yang. Learning with a drifting target concept. In Algorithmic Learning Theory, 2015.
Mehryar Mohri and Andres Muñoz Medina. New analy- sis and algorithm for learning with drifting distributions. In Proceedings of the 23rd International Conference on Algorithmic Learning Theory, 2012.
Hrayr Harutyunyan, Kyle Reing, Greg Ver Steeg, and Aram Galstyan. Improving generalization by controlling label- noise information in neural network weights. Proceedings of the International Conference on Machine Learning (ICML), 2020.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Tal- walkar. Foundations of Machine Learning. The MIT Press, 2012.
Aryan Mokhtari, Shahin Shahrampour, A. Jadbabaie, and Alejandro Ribeiro. Online optimization in dynamic en- vironments: Improved regret rates for strongly convex problems. 2016 IEEE 55th Conference on Decision and Control (CDC), pages 7195-7201, 2016.
Elad Hazan. Introduction to online convex optimization. Foundations and Trends@ in Oplimization, 2(3-4):157- 325, 2016.
Elad Hazan and Comandur Seshadhri. Adaptive algorithms for online decision problems. In Electronic colloquium computational complexity (ECCC), volume 14, 2007.
Yu-Yang Yang Qian, Peng Zhao, Yu-Jie Zhang, Masashi Sugiyama, and Zhi-Hua Zhou. Efficient non-stationary online learning by wavelets with applications to online distribution shift adaptation. In Proceedings of the 41st International Conference on Machine Learning, 2024.
Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimization: Competing with dynamic comparators. In Artificial Intelligence and Statistics, pages 398 406, 2015.
Joaquin Quionero-Candela A. Schwaighofer, and Neil D. Lawrence. Dataset shift in machine learning. MIT Press, 2009.
Masashi Sugiyama,
lain M. Johnstone. Gaussian estimation: Sequence and wavelet models. 2017.
Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 1972.
Kwang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. Improved Strongly Adaptive Online Learning using Coin Betting. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017.
Ryan Tibshirani. Adaptive piecewise polynomial esti- mation via trend filtering. Annals of Statistics, 42(1):
285-323, 2014a.
Seung-Jean Kim, Kwangmoo Koh, Stephen Boyd, and Dim- itry Gorinevsky. l trend filtering. SIAM Review, 51(2): 339-360, 2009.
Ryan J. Tibshirani. Adaptive piecewise polynomial esti- mation via trend filtering. Annals of Statistics, 42(1): 285-323, 2014b.

---

Adaptive Estimation and Learning under Temporal Distribution Shift
Yu-Xiang Wang, James Sharpnack, Alex Smola, and Ryan Tibshirani. Trend filtering graphs. In AISTATS'15, pages 1042-1050, 2015.
Ziqiao Wang and Yongyi Mao. information-theoretti analy- sis of unsupervised domain adaptation. Proceedings of the International Conference on Learning Representa- tions (ICLR), 2023.
Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: optimal dynamic regret of online learning with and noisy gradient. In International Conference on Machine Learning (ICML- 16), pages 449-457, 2016.
Haoran Zhang, Harvineet Singh, and Shalmali Joshi. "why did the model fail?": Attributing model performance changes to distribution shifts. Proceedings of the In- ternational Conference on Machine Learning (ICML), 2022.
Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou, Adaptive on- line learning in dynamic environments. In Advances in Neural Information Processing Systems (NeurIPS-18), pages 1323-1333, 2018.
Peng Zhao, Y. Zhang, L. Zhang, and Zhi-Hua Zhou. Dy- namic regret of convex and smooth functions. NeurlPS, 2020.
Martin Zinkevich. Online convex programming and gen- eralized infinitesimal gradient ascent. In International Conference Machine Learning (ICML-03), pages 928
936, 2003.
12

---

Adaptive Estimation and Learning under Temporal Distribution Shift
A. Related Work
Effect of Distribution Shift It is commonly believed that when the training data differs from the testing data, the model's performance will degrade (Quionero- QQuioner-Caandlla et al., 2009; Harutyunyan al., 2020; Wang and Mao, 2023; Zhang et al., 2022; Federici et al., 2021; Achille and Soatto, 2018; Cai al., 2022). Several studies attempted to connect the distance of the training and testing distributions with the expected errors (Long, 1998; Ben-David et al., 2010; Mazzetto and Upfal, 2023), by poper-bounding the expected errors for certain function classes. In contrast, we analyze the model loss function directly and provide both the upper- and lower-bounds, thus concluding once and for all that the model performance degrades as the misalignment between training and testing data increases, and vice versa.
Rolling Window Based Estimation Techniques. As mentioned in Section 1, a natural way to balance the variancee trade-off estimating 0 is to use data from a carefully selected, but then fixed, window of most recent observations. Works such (Hanneke et al., 2015; Mohri and Muñoz Medina, 2012; Bifet and Gavaldå, 2007; Mazzetto and Upfal, 2023; Han et al., 2024) follow this direction. In contrast, our algorithm, based wavelet-denoisingg does not explicitly maintain window size, yet achieve optimal estimation error rates.
Non-Stationary Online Learning. There are various studies from non-stationary online learning that aim to track moving target of ground-trui truth (Zinkevich, 2003; Zhang et al., 2018; Cutkosky, 2020; Besbes et al., 2015; Jadbabaic et al., 2015;
Yang et al., 2016; Mokhtari et al., 2016; Chen et al., 2018; Baby and Wang, 2019; Zhao et al., 2020; Daniely et al., 2015; Jun et al., 2017; Hazan and Seshadhri, 2007; Baby and Wang, 2021: 2022; 2020; 2023; Baby et al., 2023; 2025). These works aim estimate a moving target while controlling a cumulative performance metric such as MSE or (dynamic) regret. To the best of our knowledge, none of these works lead to point-wise estimation error guarantees which are strictly stronger than controlling cumulative performance metrics. We remark that our methods can also be used as sub-routine for the online estimation problem by iteratively executing our algorithm for each round.
Total- Variation Denoising. The field of TV denoising studies the problem of estimating a ground truth sequence from noisy observations. Unlike the
estimation procedures, no parametric structure is imposed, e.g., linear w.r.t some covariates. Instead, the ground-trute is assumed to belong to an abstract class of sequences whose total variation is bounded by some unknown value. There are several algorithms that known be minimax optimal for this task (Mammen and van de Geer, 1997; Kim et al., 2009; Tibshirani, 2014b; Wang al., 2015; Guntuboyina et al., 2017). In this paper we prove fairly general result that any algorithm that satisfies bound of the form given in Theorem 2 is by default an optimal algorithm for the TV-denoising problem.
B. Preliminaries
In this section, we give brief introduction to wavelets. We focus only on some details that are relevant to the discussion in this paper and refer the readers to Mallat (2008); Johnstone (2017) for comprehensive overview.
B.1. Discrete Haar Wavelet Transform
The discrete Haar wavelet transform (HWT) is fundamental method in signal processing, designed decompose signal into components that represent its average and detailed variations. It operates efficiently by leveraging the simplicity of the Haar basis functions, making it particularly suitable for computational tasks.
1.I.1. CORFFICIENTS IN THE HAAR WAVELET TRANSFORM
The HWT splits a signal into one approximation coefficient and multiple detail coefficients. These coefficients are computed using the Haar transform matrix H, which operates on a signal x E IR", where n is a power of 2.
Approximation Coefficient: The first row of the Haar transform matrix computes the approximation coefficient, which represents the global average (low-frequency content) of the signal. This coefficient aggregates information across the entire signal, providing a coarse summary.
The remaining rows of the Haar transform matrix compute the detail coefficients, which capture the differences high-frequency content) at progressively finer scales. These coefficients reveal variations within smaller and smaller segments of the signal.
Detail Coefficients:
13

---

Adaptive Estimation and Learning under Temporal Distribution Shift
The of the matrix represents (discrete) wavelets. As an example, for signal of length the orthonormal Haar transform matrix H is:
V8 L
v8
V8
V8
V8
v8
V4
V4
V
0
0
0
/
7/4
H
V2
V2
0
0
V2
0
0
0
1/2
v2
0
0
0
22
v2
The first row computes the approximation coefficient.
All other rows compute differences between groups values various levels resolution (detail coefficients).
B.1.2.
REPRESENTATION
The HWT follows a multi-resolution scheme where the detail coefficients are computed at various scales, progressively halving the resolution at each step. This hierarchical representation enables the efficient analysis and reconstruction of signals, capturing both coarse and fine features.
For a signal of length n, we can decompose the detail wavelets into log, n resolution/levels. At a reslution j E (0,... log, n - 1). there are 2 wavelets. These detail wavelets can be thought of obtained by scaling and transla- tion of mother wavelet. For Haar transform, the mother wavelet assumes the form
L.
0<tán/2,
(1))
1, n/2 < n,
0.
otherwise.
where E nn.....n.. Detail wavelets at resolution j are obtained as follows:
( 2 v2't nk), & E (O...., 1}.
Consequently one can use a dyadic indexing scheme to refer to the associated wavelet coefficients. We can see that any wavelet at resolution j has support length of n/22'. Further, different wavelets at same resolution have disjoint support. Due to these properties one can see that when we decompose the signal æ E RR" using the wavelet basis, only log, n + 1 wavelets affects the value of the signal any index i which is xfi). Here the count is log, n + because of the inclusion of the approximation wavelet well (the first row of the HWT matrix).
B.2. Other Wavelet Systems
While the discrete Haar wavelet transform (HWT) provides a foundational introduction wavelet analysis, it one specific case within the broader family of wavelet transforms. Many wavelet transforms have been developed address limitations of the Haar transform, such its lack of smoothness and inability to capture higher-order variations or trends in signals. These alternative wavelets offer enhanced smoothness, compact support, and better time-frequena localization.
B.2.1. DAUBECHIES WAVELETS
The Daubechies wavelets, introduced by Ingrid Daubechies, are a prominent family of compactly supported orthogonal wavelets. These wavelets generalize the Haar transform by using smoother basis functions, making them ideal for

---

Adaptive Estimation and Learning under Temporal Distribution Shift
db1
db2
db1 Wavelet
db2 Wavelet
0.75
0.50
1.0
0.00
0.0
-0.25
-0.
-0.50
-0.75
-1.0
-1.5
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
db4 Wavelet
1.0
db8 Wavelet
1.0
0.5
-0.5
-0.5
-1.0
Figure 3: Daubechies (DB) wavelets with increasing number of vanishing moments. We that the Haar system is special case of the DB system with I vanishing moment. As increase the number of vanishing moments, the wavelets get smoother.
15

---

Adaptive Estimation and Learning under Temporal Distribution Shift
representing signals with continuous slowly varying features. Each wavelet in the family is denoted as DBN where N is the number of vanishing moments. Higher-order Daubechies wavelets (DB2, DB4, etc.) offer better smoothness, which is advantageous in applications such as image processing and audio compression. The Haar wavelets is precisely the dbl system.
B.2.2. CDJV WAVELETS
A special wavelet construction scheme based on Daubechies wavelets was proposed in Cohen et al. (1993). These wavelet functions enjoy near or exact symmetry contrast to the Daubechies wavelets. The CDJV system is particularly useful in theoretical analysis due to equivalence between functional norms that capture smoothness of functions and Besov norms of the associated wavelet coefficients. remarkable property is that the Total variation of function can be completely represented using weighted sum of LI norm (with weights larger than 1) of its associated CDJV wavelet coefficients at each resolution. We refer the reader to Donoho et al. (1998); Johnstone (2017) for an elaborate treatment. A high level overview of the construction of CDJV wavelets can be found in Qian et al. (2024).
C. Proof of Lemma 4
We adapt (Achille and Soatto, 2018 { C.2] to prove the first form of the log-likelihood function. The original (Achille and Soatto, 201 P)Poppsstion C.2] lacks clarity in differentiating between Drr and pe (e()/x). Through our revision, we can articulate Assumption 5 with greater precision.
We have
[(0, Drr, Dr.)
1 log
II
PY = Uk X1) =
log
II
Po(Y = Mk|( oecurrennce number of(Xx
K
K
(8 Dr.
(g Dr
1
log
II
PY y/ x1.) (N(
ON ON (Xk, yx) loggo(Y po(Y ya wx(xx)
K
K
(xL..)))Dr.
(x)r)))EDT,
(N Mle)
Jogpo(YY =vv(x*)
Σ
PDr. (Xk, yb) log yu(xx)
K
DED
DED
where the last step comes from the fact that (Xk, Uk) drawn from the testing distribution Drs. Continuing with Eq.(4), obtain the first form of [(0, Drr, DT=)
PY yk|xx)) pDr. (Y 1/k: xx.)
DTr. DTe)
Σ PDr, (xs)PDr) = y/4 Xxx log
Σ PDr, (X:),(Xx)DD: (Y y/ xxx) log PDr. (Y 3/4 (x(x3))
PDr, (11xx)
= pDr. (5/x) log
71 (prrr, (v/x))
po(3)
KL (pDT, (v1x) x)) + H (pDT. (y x))
in which K L (pDr, (xlx)](po({(x)) the Kullback-Leible divergence of prr. (ulx) and po(u)x), and H (pDz. (y]x))
the entropy of conditional distribution (ylx).
To obtain the second form of the log likelihood, apply the chain rule of KL divergence
K (0 = KL(p(=))l((z)) + (LLoo))))))))(L(())o))))l)))))
And thus, we have
L(O, Dr., Drs) K KT(ppr, (x, 1)llo( - K (x)p)o + 7 (PDT. (v/x))
D. Proof of Theorem 7
Before proving the lemma, we note the following Theorems
16

---

Adaptive Estimation and Learning under Temporal Distribution Shift
Theorem 12. (Pinsker's Inequality) (Cover and Thomas, 2006)fLemma 11.6.1] ] Given two probability mass functions p and 4. the information/KI. divergence is related to the variation distance via the following inequality
2
KL(plla) 2 21n2 lp all;
1 21n2
Σ x.9
1p(x, v) q(x,, 8)
Theorem 13. (Convexity of Relative Entropy) (Cover and Thomas, 2006) 2.7.2] (L(ppl4) is convex in the pair (p, q): that is, if (Pi,4) Q1) and (px, 92) are two pairs of probubility mass functions, then
KL(API (1 A)p2llAq1 + (1 (1- (1-))g2) S AXL(pilla)) +(1 L)22l92))))
for all 0 S 1.
D.I. Training Distribution Shift Scenario
We first prove the lower bound. From (3.(3), we have
PDr, (x) = Σ
EDD.. PDr. (x, v) = a E PDr, (x,9) + > DD (x, = appr. (x) + Spp... (x)
and thus
PDr. (ulx)= PDr, (x,3)
apDr, (x. 3) BpD. (x, V)
PDr, (x)
apDr. (x) + 3pp... (x)
As 7 (PDr. (vlx)) is a constant with respect to 8 and can be ignored, we apply Theorem 12 into Eq.(1) to get
L(0, Drr. Drs)
KT/ppr..w/x))lpool
KI(PDr. (vlx))lpo,.
2
1
Σ (pDr.(u/x) PD.
21m2
Now,
apDr. (x, y) + BpD.., (x.D..,(.V))
(p/x)) - PDrr (3/x) = PDr, (y|x)
apDr. (x) + BpD... (x)
B
1pDr. (y) (DD (x) - PD (x, v)l
apDr. (x) + -pp..aa (x)
x |PDr. (ylx))DD.. (x) PD (x,8)
3PDr, (x) + PD... (x)
As IPDT, (yl (ylx)PD..:?xx) PD... PDr- (u]x)) is monotonic non-decreasing function on B. As consequence, we conclude that the lower-bound of loss function C(0, Drr, Dr.) is also monotonic non-decreasing function on 3.
(xP v)), PDr, (x), and PD (x) all 0, it is straightforward to that [ppr, (y|x)
To prove the upper bound, from (3), applying Theorem 13, we have
KL(pDr. (x, (xx y)) = KL(pp,. y) y) (x, y))
SaKL(pDr. (x. y) IpD., (x, y)) + BK LLLD,, (x, (I (x, 9)
-3KL(pD,. (x. 1) 1) v))
17

---

Adaptive Estimation and Learning under Temporal Distribution Shift
Signali
1.7
14
4472
0.0
68
-1.5
1ine
Timee
1.00
Figure 4: Groundtruthh signals used for experiments.
Applying Theorem 12 to the KI. divergence of the feature distribution, we have
(L(PDr,(x)]Poo(
(x) (XLPp, (xx)
IDDr. (x) - PDDr [x)]
21
Σ
PDr, (x) PD (xx)
2ln2
Now as H (pDr. (vlx)) is a constant with respect to 5, we consider (2. to get
C(, Drr, Dr
KL(ppr, (x, ()ll v)) K LL (x)))
B
< 3KL(pDD, (x. v)ll (x,, (x,
1DDr. (x) DDe (xx]
21n2
[KL(PDr. (x. V)lp (x, v)) KL (xl((pDr(x))lllppo.. (x))]
27
3 3 KLIpDr.
1
Σ (xD - PDina(x))
21n2
Note that both terms the right hand side are 2 0 due to the chain rule of KL divergence and Pinsker's inequality. Therefore, the upper-bound of loss function L(0, Drr, Drs) is a monotonic non-decreasing function of (.
D.2. Testing Distribution Shift Scenario
The proof for this case is similar to that of Shifted Training Data Scenario, by swapping PDr, and PDr.
E. Further Empirical Results
In Lemma bound that connects the estimation error to the degree of sparsity of the wavelet coefficients was established.
The bound general enough support any chosen wavelet basis. When we choose the wavelet system to be Haar, the bound
18

---

Adaptive Estimation and Learning under Temporal Distribution Shift
Groundtruth: sine
db8
30
40
upper
30
20
10
10
10
10'
sigma
Groundtruth: doppler
hear
db8
00
60
20
10-2
10-1
100
103
sigma
Groundtruth: random
haar
db8
upper
30
10a
10
10t
sigma
Figure 5: Bound in Lemma 1 averaged across all time-stampy different noise levels in semi-log plot. The groundtruth signals that are used are displayed in Fig.4. We can see that using higher order wavelet like DB8 results in significantly lower values for the bound. This provides empirical evidence for the phenomenon where Lemma I can lead to sharper rates than that obtained by Theorem We remind the reader that the bound Theorem 2 is only an upperbound of the bound in Lemma applied to Haar wavelets.
19

---

Adaptive Estimation and Learning under Temporal Distribution Shift
in Lemma can be further upperbounded by the variational expression displayed in Theorem However it argued in Section 2.2 that by choosing other wavelet systems, the bound in Lemma potentially lead sharper error rates than that can be obtained by the Haar system. In this section, we give empirical evidence for this claim. The experimental setup is exactly same as described in Section 6.1. We report the value of the bound in Lemma 1 averaged across all timestamps vs different noise standard deviations in Figure 5. Experimental results similar to that of Section 6. is reported Tables 4 and
Noise Level
HAAR
DB8
AVG
(This paper)
(This paper)
0.2
0.539 = 0.0011
0.110 + 0.0019
0.019 = 0.0005
0.3
0.541 + 0.0017
0.170 + 0.0044
0.031 = 0.0008
0.5
0.542 + 0.0027
0.249 + 0.0070
0.078 = 0.0018
0.7
0.544 = 0.0037
0.247 = 0.0101
0.141 = 0.0039
0.547 + 0.0052
0.238 + 0.0154
0.264 = 0.0065
Ground truth: Sine
Table 4: MSE of different algorithms when the noise standard deviation is known.
Noise Level
HAAR
DB8
AVG
ARW
Aligator
(This paper)
(This paper)
0.2
0.538
0.0023
0.542 + 0.0009
0.435 + 0.0037
0.152 + 0.0046
0.029
0.0017
0.3
0.538 0.0035
0.541
0.0014
0432 0.0056
0.184 + 0.0090
0.037 + 0.0029
0.5
0.538
0.0057
0.538
0.0021
0.427 = 0.0093
0.245 = 0.0140
0.058 = 0.0061
0.7
0.539 0.0078
0.526
0.0035
0.422 + 0.0129
0.265 + 0.0150
0.085
0.0098
0.541 0.0108
0.508 0.0048
0.415 + 0.0182
0.272 + 0.0225
0.146 0.0163
Ground truth: Sine
Table 5: MSE of different algorithms when the noise standard deviation is unknown.
F. Other Omitted Proofs
Lemma 1. Consider the observation model = 0; + for 1,..,, with e; being iid r-sub-gaussian random variables. Let y := [yn..... 81]", = (on..... 01] and W be an orthonormal wavelet transform matrix. Let 3 == W and B == WO be respectively the empirical and true wavelet coefficients. Let I be an index set of wavelet coefficients that affect the value reconstruction of the last groundtruth 0,, Let Win. be the value of the element in ith row and nh column of W. Let 02 be the estimate of the groundtruth 0 obtained via Algorithm with X = 20 /2 log(log n/0). Define (a A b) = min(a, (a,bb,, b}, we have with probability at-least 1 that
0 0,1 S Σ 6,l (...al.(181A...)) A).
IEI
Proof. We start by noticing a bound on the maximum of log2 n sub-gaussian random variables. Let ci,..., Glog, a be iid a-sub-gausse usubb-gaussia random variables. By sub- gaussian tail inequality we have for a fixed i,
P([el > t) < 2 (exp(=#((22'))
Now taking a union bound across all log, random variables yields
P(max lea| > 1) < 2 logg n nexp -
Hence we conclude that with probability at-least 5, we have
max |es| I / nog))
(5)
20

---

Adaptive Estimation and Learning under Temporal Distribution Shift
We have 3 = Wy W0 + é, where are again drawn from spherical Normal distribution. Let WO be the true wavelet coefficients.
Note that due to the dyadic MRA structure of the wavelet basis, only loga n wavelet coefficients are going to affect the value of the estimate Q. So I in the lemma statement becomes equal to set (ji:-.-: n for appropriatetly chosen indices. Let Ej 1 Ehogg be the noise associated with those wavelet coefficients.
Let 3, = (3.) with À = 20 / (og Throughout the proof we use to denote the binary indicator function.
For any E (.i,..., fhog, n due to (5), we have with probability at-least å that |ā,| S A. Now we proceed to bound the estimation error of soft-threshold in coordinate-wise manner. We proceed in three cases:
Case I: when | & X/2. Then with probability at-least 1 - 5, we have that |3:|| S X. So we must have 3g with high
probability. Consequently, | B:| = |3:| = m A/2].
Case 2: when [3:| 32/2. Then with probability at-least 8 we must have 13, - Bil F A| s 2X min (1311,
Case 3: when X/2 - |.|| < 32/2. Here we have,
Note that if (3.)
then sign(3.)(($,) - X) = A. On the other hand if sign(3:) - -1, then sign( (1:) A) 8 = E + A. Hence in both situations, we have with probability at-least 5 that (() - 2) -.1 S 2A. With this in mind, we proceed to bound the estimation error for Case 3.
|3, - A1 1 & XJ + (sign (s.))(3.)(()) A) 1..111.11 > A
$ max | [|
S(a) 32
min (13
where in the last line we used the fact that X/2 S |,3:] and in line (a) we used |
S 32/2.
Combining all three cases leads the conclusion that with probability at-least 1 6, have for all i ji,... Io
1 3,1 s 6 6inn(18.)..)
Now the statement of the lemma follows by reconstructing the last value of the signal from denoised wavelet coefficients and applying triangle inequality.
Lemma 14. Let the orthonormal Haar wavelet transform matrix be denoted by H. Define quantities imilar as in lemma 1. We follow dyadic indexnng scheme to index elements in B, i.e. := [3-1, 30 31.0, B1.1,.., ,8.00 Bj.1y..., ,,,3, m
Brou 1,0 .. Br0g, 10,tnn-11n/2-11 TR.. Then the estimate 0, returned by algorithm satisfies
10, F[[(Z)]] 3(3-1 AA/VV
loga R-1
(181 AAA)
+ 3
Vn/2
with probability at-least 1 8.
Proof. Consider the last column hn, of the Haar wavelet transform matrix. We can also index the last column using a dyadic indexing scheme as:
h,,,2 -1.......... Mog, n n-1,0...... h Mora n- n-1.222 E R". From the properties of the Haar matrix, we have h-1 1/ /n, [h).k| = T[k: 2d 1//nn/22 n/22 where T the binary indicator function.
h, 1h-1, ha.o. hy h......., h1,00 hy.,.... h,..,,
21

---

Adaptive Estimation and Learning under Temporal Distribution Shift
With this structure in place, the proof the lemma is direct consequence of Lemma
Theorem 2. Let 00:1 = (01 + + 0.)/t. For time-point let S(r) :=
2 211082r13. Let Urr :=
max(Es(r) 10t1 01l) V vaavv and min,e U(r)= = U(r") with r" being the smallest time-point where the equality holds. By using the Haar wavelet system in Algorithm 1, we have with probability at-least that
10 S Urr"),
where K = (4v ( V 2/2)) n + 1) and (a b) = max (a, b)-
Proof. Suppose that maximum value among the ordered set S = {(13-1] A)/Vn, (13ooo A)/V (13,a1
A//vn/2....
(13tog, n n-....1--111111 2)/ occurs at the index i*
With any index in the ordered set, we can associate a value of the time-scale which is basically the starting time-scale. For example, we associate the time-point index with time-scale n, index with time-scale n, index with time-scale n/2, and so on untill index log2 n with time-scale 2. Let ta be the time-scale associated with the index i*
When the minimum the set S is attained at (|8-1) A)/ Vn, then due to Lemma 14, the error 10, - E()(Z))] S 2 log, n//vn I 4 loog2 / log(log n/o)((r) for any and the desired conclusion is trivial. So in the of the proof, focus the case where the minimum in the set S is not attained at (|3-1) A \)/ /n.
Let j S r - 2j for some j' which is power of 2. We consider two cases:
Case (a): when t" 2 j
We have that
U(r") = max (ES(r')
10.1 - 011) 011)
2 v/vT Vr
2 0/ 2//22__
(6)
Let the maximum value in the set be (18) A AL where the value of the wavelet coefficient at the index 1" the set S and is its associated time-scale. Observe that
(18) A A) Vt"
2 log(log n/0)
I 2
1x
2 logg(log n/o)
(a) 2a
j
log(log n/
= Vov
2j*
s 4 log(log (r")U(r"),
where in line (a) used the fact that 1* > jr for the case considered and in the last line we used (6)
Now can Lemma 14 to upper bound the estimation error of algorithm I as
1 E[f(Zi)] (log, 1) (B
V
4(log, + 1) /oog(oog//0)U (r").
22

---

Adaptive Estimation and Learning under Temporal Distribution Shift
Case (b): when j" 1" We split the analysis into two scenarios:
Scenario 1: U(r*) / /vr The immediate conclusion for this scenario is:
max 00.11 011 v
Scenario 2: U(r*) = maxegr 10.1 - 01 In this scenario, we immediately obtain
u(r') 2 2/V/
Due to the optimality of Urr)), we have
max
001 01 ES
0a.1 1-
max
011 V
Recall that r is the smallest optimal time-point (see the statement of the Theorem). Observe that maxegrt-1 00.1 01 v a/ 3/Vr* - must be equal to a -v+-II I. Otherwise r* will not be the smallest optimal time-point. So in this scenario, we obtain
max 00
011
(8)
Hence for case(b), we can conclude from Eq.(7) and (8) that
max 10.1 01l vr-
(9)
and
U(r)) 0/Vr..
(10)
Let be the Haar wavelet coefficient corresponding to the index i (with 1 being the time-scale associated with that index as defined earlier) in the ordered set S. We have
| Vt-
= 0.-11 - 0/./2./ /2:11
$ 10-11 - 011 + 10t-/2:1 011
$ 2 max 10r.1 011
15t
S (a) max 10.1 011
SSp
2a
where in the last line we used (9) and in line (a) used the fact that t" <5" S r in Case (b) under consideration.
Hence we can conclude that
(18) AA) A)
3
VI*
20
Vr*-1
2/20
V
$ 2V2U
23

---

Adaptive Estimation and Learning under Temporal Distribution Shift
where in the last line we used (q.(
Now can use Lemma 14 to upper bound the estimation error of algorithm I as
(if=)l < (logg n 1) (B (BAr X)
Vt"
- 22V2(1og, n + 1)U(r")
Corollary 3. For a sequence 0ub (a > 6), define TV()o:b) = Ej- 10, 0--1|. For a time-point T, let S(r) == 11.2,4,..,,2looo 21) Let (r) max [TV(0.a)) 011) V a/vr and (i Ü() Ü(r") with r being the smallest time-point where the equality holds. Define k = (4v log (log n/ V (Vog n + 1). By using CDJV wavelet transform with vanishing moments in algorithm 1, we have with probability at-least that
6l -13. A A), m))
10: - 0-11= =0 min Σ
FEZ
Proof. The bound Eiez 6/...ll -(183) A X) is immediate from Lemma 1.
The proof of the Corollary follows mainly the steps of the proof of Theorem 2 with U() replaced by Ü.). We elaborate on the arguments that take deviation from the former proof.
The departure in the proof steps happens in the way we bound /31/vF" in case (b) the proof of Theorem We follow the follow the dyadic indexing scheme and notations defined the previous proof.
We focus the case where i* > 2. Otherwise can bound the error optimally using similar logic we used to bound the error when i = 1 in the proof of Theorem 2.
B
21/2
S sup j21
113,0:25-111
(6
where the last line is due to the fact that the class of functions of total variation less that some quantity C' is contained within a Besov space o with radius vC' for some constant // (Donoho et al., 1998; Johnstone, 2017).
The rest of the proof proceeds similarly as in the proof of Theorem
Theorem 9. For a function f E F, we defined obtain its estimated loss & as follows. Run Algorithm with data (x((x))
yo).... vn)) argmin e.
(x((x), as input. Let Eg be the estimate returned by Algorithm 1. The ERM is defined by f E
For a function f E F, let of = (ET(((X.)) Bw)) ... (UI((X)).))I)) Let B = Wof for a wavelet transform matrix W. Consider the index set defined Lemma I. Let d. be the VC dimension of F. We have with probability at-least 1
2d log(2n)
2 log(3/0)
T, L. S <8/
+ +
n
+ v sup fEF FET
6/W..al (1881 20 v Ad log( 2n/
Proof. We begin by recalling the definition of Shattering Coefficient (Mohri al., 2012).
24

---

Adaptive Estimation and Learning under Temporal Distribution Shift
Definition 15. Let F be a function that maps (X,Y) to 0, The shattering coefficient is defined the maximum number of behaviours points.
S(F, (FFn)== = max
(x.9)mmEXX)
We say that subset F S F an n-shatlering-sel if it smallest subset of F such that for any (e(f(zn), 9n), ...., (f((1)),1)) there exists some f E F such that Bn)) ((f(z)) vi)) (E(f"(zn)) Un). (1))
By standard arguments, the excess risk can be bounded as
F Lg. S 1h1 - 2gll+ + 5L. - f1.1+ tl Ez.
S $/6 - Egl + 1L, - -2ppl.
Next, we need bound quantities of the form , - l for any function f E so as to facilitate uniform convergence arguments later. However, observe that this is different from usual arguments done in statistical learning theory (Bousquet al., 2004) because the estimate Ê is not sum of individual losses.
Let (z1v)),.... (a v/) be ghost samples from the same distribution D1. Let & 1. E ((f(x)),)) be the empirical loss for distribution Dj. We have
L - Eyp S sup by - l + sup
12 - Łzl FEF
sup JEF
JEF
The first term above can be bounded using standard argument based on Rademacher complexity and further application of Massart's and Sauer's lemmas (Mohri et al., 2012). More precisely with probability at-least - 6/3, we have
2d log(n)
log (3/6)
fp Ls| fer
sup
(11)
Notice that the second term only depends on the observed and the ghost data-sets. Let F be (2n)-shattering of F.
sup fe - -p,1= sup feF
f - Eyl
fEF
sup
1e T.pl + sup
e L,l
fEF
SEF
Define XL = 2og/log(3n (3S((F 2n)/ö. For the last term, we have by Lemma and a union bound across F', with probability at-least - 6/3 that
sup E Topl feF1
5 sup
Σ
fef IEI
$ v3. sup Σ
6,W..l (1391 A X
feF Ver
S(o) V3. sup
6|W..ll (185 A 20 4d log(3 log 2/)))
SEF IEI
- sup JEF
6]W, mn (18) A 20 4d log(3 (0gg33100g log 2n/
(12)
25

---

Adaptive Estimation and Learning under Temporal Distribution Shift
where line (a) is due Sauer's lemma (Sauer, 1972).
Using standard Rademacher complexity arguments, we have with probability at-least 1 8/3
2 log (F,, 2m)m
2 (3/66
1 JEF'
sup
L S 41
2d (2g(
log(3/5)
- 4v
(13)
n
where the last line is due to Sauer's Lemma. Now union bounding across Equations (11), (12) and (13) yields that with probability at-least 1 - 8 we have
- Ls S <81 2d (og)
2 (3/()
+ 2
n
+ v3 sup
6/W,
(18) A 2 4d log 2n/
IEF iE7
Theorem 11. Suppose that an algorithm satisfies a bound of the form given in Theorem or Corollary 3. Consider rumning the algorithm iteratively to produce the estimates fi. Then with probability at-least 5 have that
Ray Rog(01m 01:)) = 1/3 A/3))
Rethe ( Im B (m) Ō /3/3
Proof. For time points a < b, let Ca-sh = Σe t 10, 0,- be the TV of the groundtruth sequence within interval [a, bj. We begin my partitioning the horizon into M bins [Lg, l.]...., [i,, ie....... [M,, My] wherein = (i 1), 1. For the bin number i, let the quantity n, := is + 1 denote its length. The bins in the partition are constructed such that Ce,+é, I / yn: while -2,+ > a/vnn + for all bins (except possibly for the last bin). We first bound the number of bins in the partition. We focus on the non-trivial case where M > 1. We have
M-1
C2
C
M-1
>
Σ
a/Vn: +
1=1
M-1
>
0/ /2n
i=1
aMM - 1)
2(4)
V
2n (M 11)
0 M3/2
4/n²"
where the last line we used M > 1 so that M 1 M/2 and line (a) we used Jensen's 's inequality along with the convexity of the function f=) 1/v2. Rearranging the last display yields M s /3 2/3
Next, we proceed bound the estimation error. Consider bin (i,, de] and let [is, fe]- Notice that 10,..; 0,1 Cr S Oi -ig- With this observation the bound in Theorem 2 can be re-written into simpler form for any j E [1 as
0 0,l (Ci,-si, Vol Vj - i i
26

---

Adaptive Estimation and Learning under Temporal Distribution Shift
where in the last line we used the property of the partition that Cr,-ii 1/ VTz Hence can upperbound the risk within bin i as
Ray (Oissi 0zgú.) S
= x² kk
k=1
S 2x
2 log f4i-
Now summing the risk across all M bins and using the fact that M S 42/3 2/3 yields Rag(O1.n: 01m)) - 2T/3 logn n2/33
Proceeding similarly, can bound the risk in absolute deviations. We have
Rabs (01:n: 01:))
Σ Raba (Os Pecse)
M
R /v
k=1
2x 2 n4 i=1
(a) 2 Mn
s 2kn 2/3 111332233
wherein line (a) used Stuchy-Schwarn inequality.
27


Reviews:
[{"review_id": "GrGxRsmJrj", "reviewer": "Reviewer_zp7o", "summary": "In this paper, the authors  study the problem of estimation and learning under temporal distribution shift. In simple words (of the author),  they consider an estimation task where  n independently drawn observations are given by y_n, \\hdots, y_1 and E[y_i] = \\theta_i. The goal is to construct an estimator for theta_i. The authors do not assume that the observations are identitally distributed.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. Please see the responses inline.\n\n**Experiments on real dataset**\n\nPlease see the response to Reviewer c9dT under the same comment title.\n\n**Experiments are based on ablation**\n\nAblation on noise level was conducted primarily to test the validity of the algorithm for various signal-to-noise levels. \n\n**Existence of Linear Representation of Ground Truth**\n\nWavelet basis are universal basis for $\\mathbb{R}^n$. This means that they are of full rank and any ground-truth sequence in $\\mathbb{R}^n$ can be written as a linear combination of the basis vectors. So the existence of such linear combination is not an assumption, but a structural property that always holds true.\n\n**Extending to other noise distributions**\n\nIn this work we primarily focused on subgaussian noise, as the main motivation for our methods is to get high quality estimates of the groundtruth without any prior knowledge on how it evolves. This is common in many studies from non-paramteric regression (see for eg [6] for a comprehensive exposition).  That said, extending to other noise distributions that are heavy tailed is a possible future direction of research.\n\n**Missing Constants in Lemma 1**\n\nWe believe that we have defined all constants pertaining to Lemma 1 in its statement.\n\n**$H$ in Algorithm 1**\n\nThanks for pointing this typo, instead of $H$, it should be the Wavelet Transform Matrix $W$ that is given as input to the algorithm.\n\n**Meaning of $\\bar \\theta_{1:t}$**\n\nIt is the average of last $t$ ground truth values. $\\bar \\theta_{1:t} := (\\theta_1+\\ldots+\\theta_t)/t$. We will update the manuscript to reflect this.\n\n**Assumptions for estimation**\n\nThe only assumption we make is the fact that the noise in the observations are iid sub-gaussian as stated in Lemma 1. No further assumptions are made.\n\n**Connection to random process**\n\nRandom processes such as Gaussian processes impose prior structural assumptions (which are often hard to verify) on how the ground-truth evolves over time. However, no such structural assumptions are placed while deriving our bounds in Lemma 1 and Theorem 2. Instead, the bound naturally adapts to the degree of smoothness in the ground-truth. We will mention this in the context of random process.\n\nHowever, viewing our problem setup through the lens of GPs holds the potential to unlock new properties that are simultaneously connected to estimation quality and uncertainty quantification. This is indeed a good direction to explore in the future.\n\n**The proof is adapted from (Achille and Soatto, 2018)**\n\nIn the paper, we have acknowledged in Appendix C that we adapt the proof from (Achille and Soatto, 2018). Note that (Achille and Soatto, 2018) did not make a distinction between the training distribution $D_{Tr}$ and the predictive distribution $p_{\\theta}( y | \\mathbf{x} )$. \nAs the result, it is important to include our full proof so that avid readers are able to understand and recreate all of the mathematic derivations. The proof will also serve as a reference for researchers who want to improve our performance bounds in Theorem 7. \n\n**Infinite number of training data and perfect ML model training in Section 3**\n\nOur goal with Section 3 was just to act as a compelling motivation for Section 4. In particular, to formally show how distribution shift between training and test can degrade model performance. Though we deal with population level losses, extension to finite samples can be realized with standard concentration inequality arguments. Our focus was just to show formally that if the test distribution is a mixture of training and some other contaminant distribution, then the model performance degrades as the contamination fraction increases.\n\nThis sets the stage that performance degradation is inevitable even in an ideal case for perfect model training and it is important to develop algorithms whose performance degrades gracefully under distribution shift in practical use-cases. Note that to develop our algorithms in Sections 4, we already considered realistic scenarios with limited training data and imperfect machine learning training processes.\n\n**References**\n\n[6] Adaptive Piecewise Polynomial Estimation via Trend Filtering, Ryan Tibshirani, Annals of Statistics 2014", "claims_and_evidence": "The authors claim that wavelet-denoising-based algorithm using Haar tranform achieves the optimal point-wise estimation error guarantees, which has been proved for subGaussian noise, which is a favourable case. It has not been demonstrated for other distributions.\n\nThe authors demonstrate the effect of temporally shifted distribution in ML settings. However, this is done under assumptions with  infinite number of samples from the training data for perfect model training, and perfect ML training is considered which largely dilutes the problem in the ML setting.", "methods_and_evaluation_criteria": "Experimental results are most lacking in this work. Only synthetic datasets have been used. Demonstration on real-world data sets that have temporally shifted data is useful.  Baselines are not provided and all results are based on ablations.", "theoretical_claims": "Some of the proofs are checked and following are the issues:\n\n1.. Lemma 1 holds for the ground truth that has a linear representation using wavelet coefficients. What happens to the upper bound when such a linear representation does not exist. More specifically, it is essential that the authors list the set of assumptions prior to analysis. Several constants in Lemma 1 are not defined. Further, H in algorithm table is not defined.\n2. In Theorem 2, what is \\bar theta? \n3. Lemma 4 and proof is not clear. The proof is adapted from (Achille and Soatto, 2018)  and several notations are not defined.", "experimental_designs_or_analyses": "NA.", "relation_to_broader_scientific_literature": "The problem presented by the authors is very interesting as it takes an alternate route to analysing temporally shifted data. One way to model such a data would be to assume stationarity and fit a random process. However, this work does not assume stationarity or identical distributions. The modelling is achieved using wavelet transforms which is a more general formulation. The stationarity of the sequence in turn affects the sparsity of the wavelet coefficients.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "The problem addressed is interesting and important connections between the statistical literature and machine learning formulation has been made. However, several simplifying assumptions hider the true potential of the work. The major weakness of the work are the experimental results as detailed above.", "other_comments_or_suggestions": "Some additional comments are as follows: \n1. Here, the data is not modeled as a random process. Since it is a closely related technique, it is appropriate to introduce literature in this direction?\n2. In Lemma 1, subGaussian assumption helps achieve faster convergence usually. What happens under other probabilistic assumptions on \\epsilon?\n3. Lemma 1 holds for the ground truth that has a linear representation using wavelet coefficients. What happens to the upper bound when such a linear representation does not exist. More specifically, it is essential that the authors list the set of assumptions prior to analysis. 4. Several constants in Lemma 1 are not defined. Further, H in algorithm table is not defined.\n5. In Theorem 2, what is \\bar theta? \n6. Lemma 4 and proof is not clear. The proof is adapted from (Achille and Soatto, 2018)  and several notations are not defined. \n7. This work attempts to connect the statistical formulation to that of machine learning. However, the main essence of such an extension arises in how the dataset challenges are handled. However assumptions with  infinite number of samples from the train-ing data for perfect model training and perfect ML training are considered which largely dilutes the problem in the ML setting.", "questions_for_authors": "Same as above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DRaoiw8iek", "reviewer": "Reviewer_ZcGb", "summary": "Given noisy observations of independent but non-identical random variables, the authors consider the problem of estimating the most recent ground truth.\n\nA key insight of the paper is that although the ground truth sequence may be non-stationary in the time domain, its wavelet transform reveals a sparse structure. Leveraging this sparsity, the authors propose a wavelet soft-thresholding (denoising) algorithm that automatically adapts to the level of temporal shift. In addition to providing pointwise error bounds for this estimator, the paper extends the ideas in two important directions:\n\n- It analyzes the effect of temporal distribution shift on the performance of machine learning models via upper and lower bounds on the loss function.\n- It applies the estimation method to binary classification under distribution shift—developing a computationally efficient ERM-based algorithm that uses a single call to an ERM oracle yet achieves near-optimal excess risk bounds.\n\nFinally, the paper draws connections between its estimation error guarantees and the classical problem of total-variation (TV) denoising, which shows that any algorithm achieving similar pointwise error guarantees is minimax optimal for TV-denoising.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for correctly recognizing and appreciating our contributions. \n\n**Rates in Theorem 11**\n\nThe displayed rates are indeed the optimal rates for squared and absolute losses.\n\n**Paragraph below corollary 8**\n\nWe will fix the typos and rewrite it for better clarity.", "claims_and_evidence": "Yes I found the claims to be well supported.", "methods_and_evaluation_criteria": "I found the methodology to be well formulated. Specifically the authors use the following set of ideas\n\n- Wavelet Representation:  \n  Although the ground truth $\\theta_1, \\dots, \\theta_n$ may be nonstationary in the time domain, its wavelet transform reveals a sparse structure; only a few key wavelet coefficients carry most of the information.\n\n- Wavelet Denoising Algorithm: \n  The proposed algorithm (Algorithm 1) proceeds as follows:\n  1. Wavelet Transform: Compute the empirical wavelet coefficients:\n     $\\tilde{\\beta} = W y$\n     where $y = [y_n, \\dots, y_1]^T$ and $W$ is the wavelet transform matrix.\n  \n  2. Soft-thresholding: Apply soft-thresholding to the coefficients:\n     $\\hat{\\beta} = T_\\lambda(\\tilde{\\beta}), \\quad \\text{with} \\quad T_\\lambda(x) = \\operatorname{sign}(x)\\max\\{|x| - \\lambda, 0\\}.$\n  \n  3. Reconstruction: Obtain the denoised signal by the inverse wavelet transform:\n     $\\hat{\\theta} = W^T \\hat{\\beta}.$\n     The final estimate $\\hat{\\theta}_1$ is the last coordinate of $\\hat{\\theta}$.", "theoretical_claims": "I did not check the proofs in detail, but the results are believable given prior classic work.\n\n - Pointwise Error Bound: \n  For the Haar wavelet system, the paper shows that with high probability,\n  $  |\\hat{\\theta}_1 - \\theta_1| \\leq \\kappa \\cdot U(r^*),$\n  where $U(r^*)$ reflects the local bias-variance trade-off of the data, and $\\kappa$ is a constant (depending on logarithmic factors).\n\n- Adaptivity via Sparsity:\n  The error bound is directly linked to the sparsity of the wavelet coefficients. Using higher order wavelet systems (e.g., Daubechies DB8) can capture more complex trends, potentially leading to even sharper error bounds.\n\n- Excess Risk for Classification: \n  The approach is extended to binary classification under temporal distribution shift. By employing wavelet-based loss estimates, the authors design an empirical risk minimization (ERM) procedure that achieves near-optimal excess risk bounds with only one ERM call.\n\n- Optimality for Total Variation Denoising:  \n  The paper proves that any algorithm satisfying a pointwise error bound like that of their wavelet estimator is minimax optimal for the TV-denoising problem (up to logarithmic factors).", "experimental_designs_or_analyses": "The algorithm performs well on the simulations. Although the baselines are better on a certain class of ground-truth signals, the proposed approach looks reasonably robust (I suspect the performance drop is due to the ground truth signal not being smooth enough).", "relation_to_broader_scientific_literature": "- I think this paper makes a significant contribution to the theory of learning under distribution shifts by leveraging classical techniques from Donoho. \n\n- The error guarantees are pointwise, which is stronger than typical cumulative error metrics in online learning. \n\n- The algorithm is also computationally feasible as it can leverage fast Wavelet transforms.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "- The rate in Theorem 11 has $n^{\\frac{1}{3}}$ for the square loss and $n^{\\frac{2}{3}}$ for the absolute error. Have these been interchanged?\n\n- The paragraph below corollary 8 needs to be rewritten. There are many missing details and typos, such as \"When $\\beta$, the lower\nbound reduces to the conclusion that the loss is larger than 0\"", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ASDINqjOJd", "reviewer": "Reviewer_4jCD", "summary": "The paper studies the problem of temporal distribution shift, by formulating the problem as parameter estimation in an univariate non-stationary sequence with sub-gaussian noise. The authors propose a wavelet denoising approach for this estimation problem, and theoretically upper bound its error rate. The authors then show how to use this algorithm as a subroutine for learning using ERM. Finally, the authors show that their method outperforms a sliding window baseline from prior work on synthetic data.\n\n\n## update after rebuttal\n\nI thank the authors for their rebuttal. Most of my concerns have been addressed, except for the limitations of the univariate setting. I will keep my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. Please see the responses below.\n\n**Why DB8 can outperform Haar wavelets in the synthetic experiments**\n\nThe main reason why higher order wavelets can outperform Haar is because, $k+1$-th order wavelets provide an ideal basis for sparsely compressing the information in a gorundtruth signal that has a piecewise polynomial trend with degree upto $k$. A sparse set of wavelet coefficients of the groundtruth signal leads to a low value for the bound in Lemma 1. We attempt to capture this intuition empirically as demonstrated in Fig.4 in Appendix and pointed the readers to that figure in the main text itself (L165, col 1).\n\n**Theoretical justification for using higher order wavelets**\n\nWavelet basis of order $k+1$ is known to be an ideal basis for sparsely representing piecewise polynomials of degree (upto) $k$, or more generally groundtruths with low $k$-th order total variation. $k$-th order total variation measures the the variation incurred in the $k$-th order (discrete) derivatives of a groundtruth. It is known in the literature that low $k$-th order TV for a groundtruth is equivalent to sparse (measured in the sense of L1 norm) wavelet coefficients in a $k+1$-th order wavelet basis. For a precise quantification see Theorem 1 in [4]. \n\n**Extension to the multivariate setting**\n\nWe acknowledge that we study the estimation in a univariate setting. Extension of our point-wise estimation proposal to multivariate time series that takes into account inter-task correlations is an interesting direction to explore as a future work.\n\n**Experiments on real dataset**\n\nPlease see the response to Reviewer c9dT under the same comment title.\n\n**Intuition behind achieving Lemma 1 and Theorem 2 without assuming prior bounds on $|\\theta_i|$ or $|\\theta_{i+1} - \\theta_i|$**\n\nWe first address informally why no prior bound on $|\\theta_i|$ is required. The wavelet soft-thresholding estimator applies a soft-threshold at the level of $\\tau := \\sigma \\sqrt{\\log n}$. Suppose $\\alpha_i$ is a wavelet coefficient of the groundtruth data. Consider the case when $|\\alpha_i| > \\tau$. Then the shrinkage caused by soft-thresholding only introduces a bias of at-most $\\tau$. Similarly when  $|\\alpha_i| \\le \\tau$, then the bias is capped at $|\\alpha_i|$ itself. This intuition can be extended to noisy wavelet coefficients upto constants using concentration arguments.\n\nEventhough we do not assume any prior knowledge on $|\\theta_{i+1} - \\theta_i|$, note that the bound in Theorem 2 naturally gets worse when there is lot of intra-sequence total variation. We remark that in the bound $\\bar theta_{1:t} = (\\theta_1 + \\ldots + \\theta_t)/t$. Hence higher intra-sequence total variation leads to larger values for the bound. The highlight here is that the bound (which is minimax optimal as per the results of Mazzetto and Upfal 2023) in Theorem 2 is obtained with no such prior knowledge on the intra-sequence variation. The reason for attaining such an adaptive bound is primarily algebraic as highlighted in the proof of Theorem 2.\n\n\n**References**\n\n[4] Minimax Estimation via Wavelet Shrinkage, David L. Donoho and Iain M. Johnstone, Annals of Statistics, 1998", "claims_and_evidence": "1. The authors empirically show that higher order wavelets (DB8) outperforms the Haar wavelets. However, there does not seem to be theoretical justification for why this happens. Having a toy example to demonstrate this would also be helpful.\n\n2. The authors study a very simple system with a univariate time series. How would the theorems and algorithm be extended to the multivariate setting?\n\n3. The authors hint (at the end of Section 4) that it possible to solve the ERM problem using a differentiable surrogate loss, but this is not expanded on further methodologically or empirically, and backpropagating through Algorithm 1 may be non-trivial.", "methods_and_evaluation_criteria": "1. The authors have only empirically evaluated the estimation setting (Section 2) in their experiments, but not the learning setting (Section 4). The authors should evaluate their method on the learning setting as well, particularly when the hypothesis class is infinite and gradient-based methods are required (as the authors discuss at the end of Section 4).\n\n2. The authors have only tested on synthetic data with fairly simple ground truth signals. It would be interesting to test the learning setting on real time-series such as those in the Wild-Time dataset.", "theoretical_claims": "I did not check the proofs of the theorems.", "experimental_designs_or_analyses": "Please see \"Methods And Evaluation Criteria\" above.", "relation_to_broader_scientific_literature": "The authors study a variant of the problem proposed in Hanneke and Yang (2019) for learning in the nonstationary sequential setting. Their primary baseline is the work by Mazzetto and Upfal (2023), which proposes a sliding window algorithm. The authors propose an algorithm based on wavelet transforms which has a long history in time series analysis.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "Typos: \"syetm\" on L147,  \"gven\" on L254", "questions_for_authors": "1. Could the authors give some intuition on how they are able to achieve Lemma 1 and Theorem 2 without any assumptions on $\\theta_i$, e.g. bounds on $|\\theta_i|$ or $|\\theta_{i+1} - \\theta_i|$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fVCl4sQual", "reviewer": "Reviewer_c9dT", "summary": "This paper investigates the problem of learning under temporal distribution shift, where the task is to estimate the ground truth related to the last observation under minimal stationarity assumptions. They prove new bounds on existing versions of a soft-thresholding algorithm for the problem, and translate these findings to general classification and learning problems under temporal distribution shift. The key contribution of the work is that their bounds depend on the sum of the wavelet coefficients, which allow for fast rates when the sparsity level is high.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. Please see the responses below.\n\n**Experiments on real dataset**\n\nAs an application of our proposed methods, we conduct a model selection experiment using real-world data.\nWe evaluate our method on data from the Dubai Land Department (https://www.dubaipulse.gov.ae/data/dld-transactions/dld_transactions-open), following the setup identical to that of [2]. The dataset includes apartment sales from January 2008 to December 2023 (192 months). Each month is treated as a time period, where the goal is to predict final prices based on apartment features. Data is randomly split into 20\\% test, with two train-validation splits: (a) 79\\%-1\\% and (b) 75\\%-5\\%.\n\nFor each month $t$, we train Random Forest and XGBoost models using a window of past data where we consider window sizes $w \\in [1,4,16,64,256]$, yielding 10 models per month. Validation MSEs from past and current months are used to refine the current month’s estimate of MSE via Algorithm 1 or ARW from [2]. The refined validation scores are used to select the best model for final MSE evaluation on test data. We report the average MSE of this model selection scheme over 192 months and 5 independent runs, comparing our method to ARW [2]. In the table below, HAAR and DB8 are versions of Algorithm 1 with the corresponding wavelet basis given as input.\n\nCase 1:  79\\%-1\\% Train-Validation split for each month\n--\n| Method  | MSE ± Std. Error |\n|---------|------------------|\n| **ARW (from [2])**  | $0.079 \\pm 0.0005$  |\n| **HAAR (ours)** | $0.0722 \\pm 0.0006$ |\n| **DB8 (ours)**  | $0.0762 \\pm 0.0002$ |\n\nCase 2:  75\\%-5\\% Train-Validation split for each month\n--\n| Method  | MSE ± Std. Error |\n|---------|------------------|\n| **ARW (from [2])**  | $0.0719 \\pm 0.0005$  |\n| **HAAR (ours)** | $0.0736 \\pm 0.0011$ |\n| **DB8 (ours)**  | $0.0768 \\pm 0.0008$ |\n\nWe see that wavelet based methods shine especially when the validation data is scarce. This allows us to include more data for training while still allowing to obtain high quality estimates for validation scores. Such a property can be especially helpful in data-scarce regimes. Unlike the synthetic data experiments, here we find that Haar wavelets perform better than DB8. This can be attributed to the following facts: i) the noise in the observations depart from iid sub-gaussian assumption and; ii) the high degree of non-stationarity in the pricing data as indicated by Fig.6(b) in [2] makes the underlying trends to have a low degree piecewise polynomial structure. This makes the groundtruth irregular (or less smooth) which can be suitably handled by lower order Haar wavelets which are also less smooth and abrupt (see Fig. 2 in Appendix).\n\n**Lemma 4: please cite if it came from somewhere else or state that this is a previously unknown result**\n\nWe have mentioned in the proof that Lemma 4 that it is adapted from (Achille and Soatto, 2018). For clarity, we will add the phrase “(adapted from Achille and Soatto, 2018)” in the Lemma statement itself.\n\n**Def 6: I do not understand the last line, could you explain that more clearly? With the T1=Ts if T = Tr, etc**\n\nThanks for pointing this out! There is a typo and the sentence should be “Here T represents training data T≡T_r (or testing data T≡T_s) and T1 ≡ T_s (or T1 ≡ T_r).” We will revise the manuscript accordingly. We will also add the following explanation into the manuscript.\n“Specifically, under the Training Distribution Shift Scenario, the training data T≡T_r consists of (1) samples from the testing distribution T_1≡T_s, and (2) samples from a dissimilar distribution T_2. When, more and more dissimilarly-distributed samples from T_2 are added into the training distribution, this leads to higher dissimilarity ratio $\\beta$.\nUnder the Testing Distribution Shift Scenario, the testing data T≡T_s consists of (1) samples from the training distribution T_1≡T_r, and (2) samples from a dissimilar distribution T_2. When, more and more dissimilarly-distributed samples from T_2 are added into the testing distribution, this leads to higher dissimilarity ratio $\\beta$.\n\n**Typos**\n\nThanks for pointing out the typos. We will fix them. $H$ in Algorithm 1 should be $W$ the matrix for wavelet transform. The example below the definition of the TV class must be sum of squared differences as the reviewer pointed out.  This is a typo that will be corrected.\n\n**References**\n\n[1] Adapting to Unknown Smoothness via Wavelet Shrinkage, David L. Donoho and Iain M. Johnstone, Journal of the American Statistical Association, 1995\n\n[2] Model Assessment and Selection under Temporal Distribution Shift, Elise Han, Chengpiao Huang, and Kaizheng Wang, ICML 2024", "claims_and_evidence": "The claims are supported by clear and convincing evidence. I would appreciate more insight into the proof techniques for each of the Lemmas, but the results themselves are convincing.", "methods_and_evaluation_criteria": "Synthetic datasets are provided, and the paper’s approach is shown to outperform the state of the art in a number of cases. The paper could benefit from a real data experiment or experimental application.", "theoretical_claims": "I did not check the correctness of proofs, and the lack of proof ideas/techniques makes it hard to verify the accuracy of proofs in the main body. The results themselves are convincing and not completely surprising, leading me to believe that the theoretical claims are not overstated.", "experimental_designs_or_analyses": "The experimental methodology seems sound.", "relation_to_broader_scientific_literature": "The paper considers an important and foundational problem in statistics and machine learning, and relates its findings to previous related works on the Total Variation Denoising problem tackled by Van de Geer and more immediately related works such as Mazzetto and Upfal 2023. The paper builds upon these previous works and expands the literature on the problem by proving new upper bounds on the risk of estimation under temporal distribution shift, and highlight the adaptive nature of such wavelet based methods. \n\nThe main contribution of the paper as per my understanding is the precise quantification of the role of sparsity in the accuracy of these wavelet-based methods. It does not, as far as I know, propose an entirely new methodology or algorithm, so its contribution is mainly a useful theoretical one to better understand existing algorithms in the field.", "essential_references_not_discussed": "None that I am aware of.", "other_strengths_and_weaknesses": "I think the paper is mostly clear, with a few minor drawbacks related to clarity: \n\n- Algorithm 1, what is H? not defined\n- Thm 2 “syetm”\n\n- Lemma 4: not clear whether this is an already known result, this appears very foundational, please cite if it came from somewhere else or state that this is a previously unknown result and an original contribution.\n- Def 6: I do not understand the last line, could you explain that more clearly? WIth the T1=Ts if T = Tr, etc.\n- Paragraph before section 4 is not clear to me, with a few spelling/grammar mistakes.\n- Theorem 9 typo “defined obtain”\n- First paragraph of section 5, “has been not uncovered” typo/unclear", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1) Below the definition of the total variation class, you define the alternate sequence penalising the sum of squared differences, but the example you give is not the sum of squared differences right? Is this a typo?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "u6CN8RsU2c", "reviewer": "Reviewer_8JTP", "summary": "This paper focuses on estimation and learning time series data in the presence of temporal distribution shifts. The authors propose a wavelet soft-thresholding estimator that optimally estimates the ground truth sequence under unknown shifts and provide theoretical error bounds for their method. Their approach generalizes existing research by linking the sequence’s non-stationarity to sparsity in the wavelet domain. The paper also applies this estimator to binary classification under distribution shifts and establishes its connection to total-variation denoising. The authors conduct experiments on synthetic data to validate their proposed method.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Experiments on real dataset**\n\nPlease see the response to Reviewer c9dT under the same comment title.\n\n**How to do optimal wavelet selection.**\n\nThis is a well-known model selection problem in wavelet denoising, not a drawback unique to our work. We acknowledge this in Section 7. Practitioners typically analyze data trends—if they follow a piecewise polynomial of degree $k$, a wavelet of order $k+1$ is chosen, as it effectively models such structures. However, higher-order wavelets introduce numerical instabilities and variance, though the latter can be mitigated with more data. Selecting a wavelet basis is akin to choosing a kernel in Gaussian Processes—application-specific and guided by practical intuition. A more comprehensive exposition can be obtained from [5].\n\n**Theoretical justification for using higher order wavelets**\n\nPlease see the comment to Reviewer 4jCD under the same comment title.\n\n**Computational efficiency in comparison to prior work (Mazzetto and Upfal , 2023)**\n\nApplying the algorithm from (Mazzetto and Upfal , 2023) requires $O(\\log n)$ calls to an ERM oracle. While our method requires exactly one call as detailed in Section 4. This is the reason for computational efficiency.\n\n**How to use Algorithm 1 for binary classification?**\n\nPlease refer to the statement of Theorem 9. We compute refined the loss estimate of a model at most recent timestamp. For this, loss sequence $\\ell(f(x_n),y_n),\\ldots,\\ell(f(x_1),y_1)$ is given as input to Algorithm 1. ERM is performed using the returned loss estimate.\n\n**Algorithm uses fixed soft-thresholding for wavelet denoising, which may not always be optimal**\n\nThe guarantee in Theorem 2 is obtained via the universal soft-thresholding based denoising. The bound is known to be minimax optimal in light of (Mazzetto and Upfal , 2023).\n\n**The algorithm assumes that the ground truth sequence has sparse wavelet coefficients but it's hard to verify this assumption**\n\nWe would like to point out that such an assumption is not made. Instead the bounds naturally adapts to the sparsity of the wavelet coefficient and hence the degree of non-stationarity of the groundtruth without any prior knowledge.\n\n**The temporal shift setting the algorithm considers is limited and not applicable to online learning...**\n\nWe clarify that our setup is offline: given all data $y_n, \\dots, y_1$, the goal is to estimate the ground truth at $t=1$. For online settings, Algorithm 1 can be used iteratively to update estimates over time. The multi-resolution nature of wavelets enables efficient updates with $O(\\log n)$ complexity per round. Unlike typical online methods with cumulative regret guarantees, our approach provides stronger per-round estimation error guarantees.\n\n**Study omits comparisons with transformers and RNN architectures**\n\nOur method operates in a data-scarce regime. For example, to estimate the groundtruth at timestamp 50 we only have just 50 data points. Advanced models like transformers and RNNs excel with abundant data. Hence, we compare against methods suited for low-data settings that are also known to have robust theoretical guarantees on estimation error.\n\n**Results on adaptive tuning schemes for thresholding**\n\nAs per reviewer’s suggestion, we conducted experiments on other well studied thresholding schemes namely SUREShrink [1] and Energy based thresholding [3] heuristic. The MSE results are reported below for Doppler signal and different wavelet types. Name in brackets indicates the thresholding scheme. Similar observations hold true for Random ground truth signal.\n\n| Noise Level | Haar (sure) | Haar (energy) | Haar (soft) |\n|-------|------------|--------------|-------------|\n| 0.2   | 0.0376 ± 0.0023 | 0.0210 ± 0.0010 | 0.053 ± 0.0017 |\n| 0.3   | 0.0400 ± 0.0031 | 0.0265 ± 0.0015 | 0.056 ± 0.0018 |\n| 0.5   | 0.0490 ± 0.0044 | 0.0456 ± 0.0024 | 0.065 ± 0.0018 |\n| 0.7   | 0.0653 ± 0.0051 | 0.0726 ± 0.0032 | 0.072 ± 0.0031 |\n| 1.0   | 0.0938 ± 0.0055 | 0.1265 ± 0.0054 | 0.088 ± 0.0035 |\n\n| Noise Level | DB8 (sure) | DB8 (energy) | DB8 (soft) |\n|-------|------------|--------------|-------------|\n| 0.2   | 0.0190 ± 0.0013 | 0.0195 ± 0.0007 | 0.0204 ± 0.0007 |\n| 0.3   | 0.0257 ± 0.0017 | 0.0274 ± 0.0010 | 0.0265 ± 0.0010 |\n| 0.5   | 0.0464 ± 0.0029 | 0.0527 ± 0.0015 | 0.0444 ± 0.0016 |\n| 0.7   | 0.0760 ± 0.0054 | 0.0904 ± 0.0023 | 0.070 ± 0.0021  |\n| 1.0   | 0.1406 ± 0.0090 | 0.1697 ± 0.0035 | 0.129 ± 0.0058  |\n\nThis experiment shows that some thresholding schemes may outperform universal soft thresholding empirically, but no single method is best overall. While SUREShrink is known to achieve minimax MSE optimality in non-parametric regression, its extension to point-wise bounds remains unclear. We will include these insights in the manuscript.\n\n**References**\n\n[1] https://www.jstor.org/stable/2291512\n\n[3] https://digital-library.theiet.org/doi/full/10.1049/iet-smt.2016.0168\n\n[5] https://www.sciencedirect.com/book/9780123743701/a-wavelet-tour-of-signal-processing", "claims_and_evidence": "The authors made several claims in their paper. However, some claims are not well supported:\n- The authors claimed that using higher-order wavelets can achieve better performance. However, their theoretical analysis and algorithm do not provide a principled method for choosing the optimal wavelet transform.\n- The authors claimed that their algorithm achieve better computational efficiency for binary classification setting compared to the existing works. However, no empirical evidence is provided to support it.\n- The authors claimed the superior performance of their proposed wavelet-denoising based algorithms in estimating the ground-truth, compared to prior works. However, they lacks real-world data validation for it.", "methods_and_evaluation_criteria": "- The authors proposed wavelet-denoising algorithm (Algorithm 1) for time series data estimation problem. However, it is not clear how to apply this algorithm for binary classification problem as shown in Theorem 9. Given that Algorithm 1 only takes Y as input instead of both X and Y. More explanations are needed.\n- The algorithm does not provide a principled method for choosing the optimal wavelet transform. While Haar wavelets work well in many cases, higher-order wavelets may be needed for complex trends, but their selection remains ad hoc.\n- The algorithm uses fixed soft-thresholding for wavelet denoising, which may not always be optimal.\n- The algorithm assumes that the ground truth sequence has sparse wavelet coefficients. However, it's hard to verify this assumption in practical application.\n- The temporal shift setting the algorithm considers is limited. Specifically,it does not continuously update its model as new data arrives (online learning).", "theoretical_claims": "- The theoretical analysis for binary classification setting (section 3) provide no new insights compared to existing works in domain adaptation literature. In particular, the error is bounded by the distance of the joint data distribution between training and testing datasets is widely known.\n- While the paper claims that higher-order wavelets (e.g., Daubechies wavelets) can improve estimation, it does not provide a theoretical comparison between different wavelet families.\n- The analysis is limited to a specific type of temporal shift, as the authors only consider scenarios where the training and testing data are modeled as a linear combination of two base distributions.", "experimental_designs_or_analyses": "- The authors primarily validate their method on synthetic datasets (e.g., Random and Doppler signals) rather than real-world time series data such as financial market data, climate trends, or network traffic patterns. This limits the generalizability of their findings to practical applications where temporal distribution shifts may be more complex and unpredictable.\n- The study focuses on classical estimation and statistical learning techniques, omitting comparisons with modern deep learning approaches that incorporate adaptive architectures for handling temporal distribution shifts (e.g., transformer models or recurrent neural networks)\n- The authors leverage higher-order wavelets (i.e., Daubechies-8) but does not thoroughly explore how different wavelet families affect estimation performance. Ablation study need to be conducted to explore this issue. Moreover, there is no discussion on when Haar wavelets suffice versus when higher-order wavelets provide advantages, leaving an open question about optimal wavelet selection.\n- The impact of hyperparameter selection requires further discussion. Specifically, the authors rely on a fixed soft-thresholding approach for wavelet denoising but do not investigate how adaptive tuning could enhance performance.\n- Experiment with binary classification setting is highly recommended to demonstrate the utility of the proposed method.", "relation_to_broader_scientific_literature": "This paper falls within the fields of domain adaptation and time-series estimation, tackling challenges related to temporal distribution shifts in machine learning. However, its technical contributions and advantages over existing literature remain unclear. Please refer to other sections for further details.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Please see the above sections.", "other_comments_or_suggestions": "Please see the above sections.", "questions_for_authors": "Please see the above sections.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: **Summary.**

The topic of this work is estimation under temporal distribution shift.
Specifically, after observing a sequence of n independent but not identically distributed $Y_t$, each with mean $\theta_t$, the goal is to estimate the “last” parameter $\theta_1$ and to bound the point-wise performance guarantee.

The authors propose to use an algorithm based on wavelets and show that it achieves comparable performance with the prior work of  Mazzetto and Upfal (2023) when specialized to use the Haar wavelet system. Other wavelet systems may even yield sharper bounds, and which adapt to the sparsity of the wavelet coefficients.

They propose an analysis of the detrimental effects of distribution shift for machine learning models.

They obtain additional results in the context of binary classification and an optimality condition for the problem of TV denoising.

Finally, the authors demonstrate the superiority of they algorithm based on wavelets through experiments (synthetic data).

**Strengths.**

* The contribution was deemed significant (ZcGb); the problem considered is foundational (c9dT).
* The method is computationally tractable (ZcGb); in particular, it is more computationally efficient than Mazzetto and Upfal (2023).
* The obtained pointwise guarantee is strong (ZcGb).

**Weaknesses.**

* The analysis is limited to sub-Gaussian noise (zp7o).
* The analysis is restricted to the univariate setting (4jCD).
* No experiments for the learning setting (4jCD).
* No principled method for choosing the optimal wavelet transform (8JTP).

**Discussion and reviewer consensus.**

ZcGb did not acknowledge the rebuttal and 8JTP did not share their updated thoughts after the author response. I think the authors addressed the concerns of 8JTP satisfactorily; they also acknowledged that optimal wavelet selection remains a limitation of their work. 

**Additional remarks.**

* Originally, there was a concern about the absence of experiments with real data (c9dT, 8JTP, zp7o), but in their response, the authors went the extra mile and ran additional experiments with data from the Dubai Land Department, which was well-received be the referee (c9dT, zp7o).
* In addition, a certain amount of typos were reported by the reviewers; should the paper be accepted, I recommend the authors to carefully address them.

**Overall evaluation.**

I recommend acceptance if there is room in the program.
Decision: Accept (poster)