REVIEW 3 major objections 3 minor 13 references
Adaptive Estimation and Learning under Temporal Distribution Shift
T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read A fixed wavelet soft-thresholding estimator, with no knowledge of the drift, matches the optimal pointwise error bound for estimating the latest value of a noisy non-stationary sequence, and iterating it yields minimax-optimal…
desk verdict Haar-wavelet core is real, but the general-wavelet claims are not proven; referee it for the TV-denoising reduction. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The mechanism is the orthonormal wavelet transform $W$ paired with coordinate-wise soft-thresholding $T_\lambda$. Algorithm 1 maps the reverse-time observation vector to empirical wavelet coefficients $\tilde\beta=Wy$, shrinks each coefficient toward zero by $\lambda$, reconstructs $\hat\theta=W^T T_\lambda(\tilde\beta)$, and returns the last coordinate. Since the estimate of $\theta_1$ is a linear combination of wavelet coefficients with weights $W_{i,n}$, only coefficients whose wavelets overlap the boundary point matter; for Haar wavelets this is a logarithmic number, so a union bound over these noise terms calibrates $\lambda=2\sigma\sqrt{2\log(\log n/\delta)}$. The true coefficients $\beta_i$ are large only where the sequence has structure—constant blocks for Haar, piecewise-polynomial trends for higher-order systems—so the bound $\sum_{i\in I}6|W_{i,n}|(|\beta_i|\wedge\lambda)$ is a sparsity-adaptive bias-variance tradeoff with no window selection. The TV-denoising result uses the fact that the pointwise bound implies, inside any interval of bounded variation, an error of order $\sigma/\sqrt{k}$, and summing these errors over a partition chosen by variation budget yields the aggregate risk rates.
What would settle it
Compute the last column of a compactly supported orthonormal wavelet matrix with more than one vanishing moment (not Haar) for $n=16$ and $n=64$; the number of entries with magnitude above numerical precision grows as a constant multiple of $\log_2 n$, exceeding the proof's asserted count. Then simulate the Lemma 1 guarantee: draw $n$ i.i.d. $\sigma$-sub-Gaussian noise samples on a signal with zero true wavelet coefficients, set $\lambda=2\sigma\sqrt{2\log(\log n/\delta)}$ with $\delta=0.05$, and measure the empirical coverage of $|\hat\theta_1-\theta_1|\le\sum_{i\in I}6|W_{i,n}|(|\beta_i|\wedge\lambda)$ over many replicates; coverage clearly below $1-\delta$ would refute the general-basis claim.
Extended reading notes
Core claim
The central claim is that pointwise estimation under temporal distribution shift is governed by the sparsity of the ground-truth sequence in a wavelet basis, and that soft-thresholding empirical wavelet coefficients realizes the optimal bias-variance tradeoff automatically. For the Haar system, Theorem 2 gives, with probability at least $1-\delta$, $|\hat\theta_1-\theta_1| \le \kappa U(r^*)$, where $U(r^*)$ minimizes over $r$ the larger of the maximum deviation of dyadic block averages from $\theta_1$ and $\sigma/\sqrt{r}$; this is the same variational bound previously obtained by algorithms that explicitly pick a window, and it holds without knowing the drift level. Lemma 1 gives the coordinate-wise bound $\sum_{i\in I} 6|W_{i,n}|(|\beta_i|\wedge\lambda)$, showing that only wavelet coefficients whose basis elements overlap the latest time point matter, with the threshold $\lambda$ set by the maximum of a logarithmic number of noise coefficients. These estimates feed a binary classification result with excess-risk control under temporal shift that needs one ERM oracle call and preserves differentiability for surrogate losses, and Theorem 11, which states that any estimator with the Theorem 2 guarantee, applied at every time point, is minimax optimal for total-variation denoising up to logarithmic factors.
Load-bearing premise
The load-bearing premise is that, for an arbitrary orthonormal wavelet transform, only about $\log_2 n$ wavelet coefficients affect the estimate of the last value $\hat\theta_1$, because this count sets the threshold $\lambda$ and the probability calibration; the premise holds for Haar wavelets but not for other compactly supported orthonormal systems, so the general-transform guarantees in Lemma 1 and their downstream uses rest on an unproved assertion.
Editorial extensions
If this is right
- A binary classifier can be trained under temporal shift with a single call to an empirical risk minimization oracle, instead of a logarithmic number of calls, while keeping surrogate-loss objectives differentiable almost everywhere.
- Any algorithm satisfying the pointwise bound of Theorem 2 or Corollary 3 is automatically minimax optimal for total-variation denoising, with squared risk $\tilde{O}(n^{1/3}C^{2/3}\sigma^{4/3})$ and absolute risk $\tilde{O}(n^{2/3}C^{1/3}\sigma^{2/3})$.
- Estimating the latest value requires no prior knowledge of the drift level: the threshold depends only on the noise level, the failure probability, and the horizon $n$.
- Higher-order wavelet bases can give sharper estimation errors than Haar when the ground truth has smooth trends, and CDJV wavelets provide a fail-safe guarantee comparable to the Haar bound.
- Under the paper's idealized training assumption, adding more dissimilar samples to the training distribution degrades the log-loss monotonically, with matching upper and lower bounds.
Reading between the lines
- Editorial inference: The sparsity-based view suggests the same soft-thresholding routine could serve as a drop-in estimator for other boundary-anchored prediction tasks, such as online forecasting, by choosing a wavelet basis matched to the expected trend order; the paper does not develop this.
- Editorial inference: Replacing the exact count $\log_2 n$ in Lemma 1 with a basis-dependent constant would likely leave the Haar-based Theorem 2 and the TV-denoising implications intact, since those results do not depend on the general-basis claim.
- Editorial inference: A practical testable extension is to select the wavelet basis and threshold by a data-dependent criterion such as cross-validation or risk estimation, rather than the practitioner heuristic the paper describes.
- Editorial inference: The black-box TV-denoising result suggests a converse direction: minimax-optimal denoising algorithms specialized to the final coordinate may admit pointwise bounds of the Theorem 2 form, which would enlarge the known class of drift-adaptive estimators.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies pointwise estimation of the latest ground truth theta_1 from noisy observations y_n, ..., y_1 under temporal distribution shift. The proposed Algorithm 1 applies a wavelet soft-thresholding estimator and, for the Haar system, is claimed to recover the optimal pointwise error bound previously achieved by adaptive window selection (Theorem 2). A general sparsity-based bound is stated as Lemma 1 and used to derive a CDJV fail-safe bound (Corollary 3) and excess-risk guarantees for binary classification with a single ERM call (Theorems 9 and 10). The paper also proves that any estimator satisfying the pointwise bound, run iteratively, is minimax optimal for total-variation denoising (Theorem 11), and it reports synthetic and real-data experiments in Section 6.
Significance. If the theorems were fully established as stated, the paper would make several useful contributions: it shows that a fixed, drift-independent wavelet-shrinkage routine matches the previous best adaptive-window pointwise guarantees; it provides a black-box reduction from pointwise bounds to minimax TV-denoising rates; and it reduces the ERM-oracle complexity of distribution-shift classification to a single call. The Haar-based Theorem 2 and the TV-denoising Theorem 11 are the strongest and most self-contained parts, and the explicit threshold lambda with no fitted constants in the theory is a strength. The main unresolved issue is the generality claimed in Lemma 1, which is load-bearing for Corollary 3 and Theorem 9 but is only proved for the Haar coefficient count, and the missing union bound in the proof of Theorem 11.
major comments (3)
- [Appendix F, Lemma 1] The proof is not established for the stated generality. The assertion that 'due to the dyadic MRA structure of the wavelet basis, only log2 n wavelet coefficients are going to affect the value of the estimate theta_hat_1' is correct for the Haar system but not for a general orthonormal wavelet transform matrix W. For Daubechies or CDJV bases with more than one vanishing moment, a filter-length-dependent constant number of wavelets per scale overlap the boundary point, so |I| = c log2 n with c > 1. The union bound and the threshold lambda = 2 sigma sqrt(2 log(log n / delta)) are calibrated to |I| = log2 n; with |I| = c log2 n, the displayed union bound does not give the claimed 1 - delta event. This propagates to Corollary 3 and Theorem 9, and to the paper's claim that higher-order wavelets such as DB8 carry proven pointwise guarantees. The fix is local: either state Lemma 1 only for Haar, or replace log2 n by c log2 n and adjust the threshold (and verify the probability calculation) for the chosen wavelet family.
- [Appendix F, Lemma 1, Eq. (5)] The probability calculation leading to Eq. (5) is not correct as written. Solving 2 log2 n exp(-t^2/(2 sigma^2)) = delta gives t = sigma sqrt(2 log(2 log2 n / delta)), not sigma sqrt(2 log(log n / delta)). The subsequent threshold lambda is twice the displayed right-hand side, so the final high-probability statement may still hold for the parameter ranges used in the paper, but the proof as written does not derive the claimed 1 - delta guarantee. Please redo the union bound with explicit constants and state the exact event used by the three-case argument.
- [Section 5, Theorem 11 proof] The proof applies the pointwise bound of Theorem 2 or Corollary 3 separately to each prefix j in [n] and then sums the resulting errors, but it does not take a union bound over the n different high-probability events. As written, the claimed 'with probability at least 1 - delta' for the simultaneous bound over all time points is not justified. This is repairable by running the pointwise guarantee with failure probability delta/n and absorbing the extra log factor into the O-tilde notation; please make this explicit.
minor comments (3)
- [Corollary 3] The definition of U_tilde(r) reads max_{t in S(r)} |TV(theta_{t:1}) - theta_1|, but TV(theta_{t:1}) is already a scalar total variation, so the expression |TV(theta_{t:1}) - theta_1| is dimensionally inconsistent; presumably the intended quantity is max_{t in S(r)} TV(theta_{t:1}) or a similar variational term. Please correct the definition.
- [Appendix F, proof of Theorem 2] The proof switches between 'maximum value among the ordered set S' and 'when the minimum in the set S is attained', and between max over t <= r* and max over t in S(r*). These should be made consistent with the dyadic set S(r) defined in the statement; the intended argument is clear but the notation should be fixed.
- [Theorem 7] The theorem states that the log-loss is bounded by 'monotonic non-decreasing functions on beta' without giving explicit formulas for LB(beta) and UB(beta). Please state the functions explicitly or provide their closed forms in the appendix, since the monotonicity claim alone does not quantify the rate of degradation.
Circularity Check
No significant circularity: the central wavelet-shrinkage bound and the TV-denoising reduction are derived from sub-Gaussian concentration and external minimax facts, not from fitted parameters or the authors' own prior results.
full rationale
The load-bearing claims, Theorem 2, Lemma 1, Theorem 9, and Theorem 11, are derived from the stated observation model and standard wavelet, union-bound, Rademacher, and Besov machinery, rather than from fitted values or from a self-citation chain. The soft-threshold lambda is specified analytically as 2 sigma sqrt(2 log(log n / delta)); no constant in the theory is fit to data, so no fitted input is relabeled as a prediction. Theorem 2 uses the Haar-specific coefficient count in Lemma 14 and standard sub-Gaussian concentration, and it does not reduce to prior work by the same authors. Theorem 11 is a black-box reduction: it assumes a pointwise bound of the Theorem 2 form and integrates it over a carefully partitioned binning, with minimax optimality cited from external results such as Donoho et al. (1996). Self-citations such as Baby and Wang (2019) for the motivation on TV classes and Baby et al. (2021) for the Aligator baseline are not load-bearing. The genuine soft spot is a correctness gap rather than circularity: in Appendix F, Lemma 1 is stated for an arbitrary orthonormal wavelet matrix W, but its proof restricts the active index set I to log2 n coefficients 'due to the dyadic MRA structure of the wavelet basis,' a property that is exact for Haar and not generally true for Daubechies or CDJV bases. This affects the claimed generality of Lemma 1, Corollary 3, and the general-W statement of Theorem 9, but it does not reduce any theorem to its own input. Theorem 7 similarly follows from Pinsker's inequality and convexity of relative entropy applied to its own Definition 6 mixture, which is a derivation rather than an imported conclusion. Overall the paper is self-contained given standard wavelet-shrinkage and concentration results, so the non-circular proof-gap concern should be scored as correctness risk rather than circularity.
Assumptions & free parameters
assumptions (5)
- domain assumption Observations are independent with y_i = theta_i + epsilon_i, where epsilon_i are i.i.d. sigma-sub-gaussian.
- ad hoc to paper For any orthonormal wavelet transform matrix W, only log2 n wavelet coefficients affect the last coordinate theta_1.
- standard math TV-bounded sequences are contained in a Besov space with equivalent norm via CDJV coefficients.
- domain assumption Assumption 5: perfect ML training, p_theta(y|x) = p_DTr(y|x).
- standard math Minimax lower bounds for TV denoising as given by Donoho et al. 1996.
Cite this review
Pith. "Pith review of Adaptive Estimation and Learning under Temporal Distribution Shift." pith.science (2026). https://pith.science/paper/XH4HZ2GL
@misc{pith2026250515803,
author = {Pith},
title = {Pith review of: Adaptive Estimation and Learning under Temporal Distribution Shift},
year = {2026},
howpublished = {\url{https://pith.science/paper/XH4HZ2GL}},
note = {Machine review of arXiv:2505.15803}
}
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 groundtruth 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 Mazzetto 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.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
We refer the reader to Donoho et al
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)[Proposition C.2] to prove the first form of the log-...
work page 1998
-
[2]
This coefficient aggregates information across the entire signal, providing a coarse summary
• 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. • Detail Coefficients: The remaining rows of the Haar transform matrix compu...
work page 1993
-
[3]
≤ √ 3 · sup f ∈F ′ X i∈I 6|Wi,n|·(|βf i |∧λ′) ≤(a) √ 3 · sup f ∈F ′ X i∈I 6|Wi,n|·(|βf i |∧2σ p 4d log(3 log 2n/δ)) = √ 3 · sup f ∈F X i∈I 6|Wi,n|·(|βf i |∧2σ p 4d log(3 log 2n/δ)), (12) 25 Adaptive Estimation and Learning under Temporal Distribution Shift , where line (a) is due to Sauer’s lemma (Sauer, 1972). Using standard Rademacher complexity argumen...
work page 1972
-
[10]
The rest of the proof proceeds similarly as in the proof of Theorem
|β|√ t∗ ≤ sup j≥1 r 2j/2 n ∥βj,0:2j −1∥1 = O(TV(θt∗:1)) 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 B1 1,∞ with radius νC for some constant ν (Donoho et al., 1998; Johnstone, 2017). The rest of the proof proceeds similarly as in the proof of Theorem
work page 1998
-
[11]
Let d be the VC dimension of F. We have with probability at-least 1 − δ, L ˆf − Lf∗ ≤ 8 r 2d log(2n) n + 2 r 2 log(3/δ) n + √ 3 · sup f ∈F X i∈I 6|Wi,n|·(|βf i |∧2σ p 4d log(3 log 2n/δ)). Proof. We begin by recalling the definition of Shattering Coefficient (Mohri et al., 2012). 24 Adaptive Estimation and Learning under Temporal Distribution Shift Definition
work page 2012
-
[12]
(Pinsker’s Inequality) (Cover and Thomas, 2006)[Lemma 11.6.1] Given two probability mass functions p and q, the information/KL divergence is related to the variation distance via the following inequality KL(p||q) ≥ 1 2ln2 ||p − q||2 1= 1 2ln2 X x,y |p(x, y) − q(x, y)| !2 Theorem
work page 2006
-
[13]
(Convexity of Relative Entropy) (Cover and Thomas, 2006)[Theorem 2.7.2]KL(p||q) is convex in the pair (p, q); that is, if (p1, q1) and (p2, q2) are two pairs of probability mass functions, then KL(λp1 + (1 − λ)p2||λq1 + (1 − λ)q2) ≤ λKL(p1||q1) + (1 − λ)KL(p2||q2) for all 0 ≤ λ ≤
work page 2006
-
[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-Candela et al., 2009; Harutyunyan et al., 2020; Wang and Mao, 2023; Zhang et al., 2022; Federici et al., 2021; A...
work page 2009
Show all 13 references
-
[2004]
Let (x′ 1y′ 1),
because the estimate ˆℓf is not a sum of individual losses. Let (x′ 1y′ 1), . . . ,(x′ n, y′ n) be n ghost samples from the same distribution D1. Let ℓf,n := 1 n Pn i=1 ℓ(f (x′ i), y′ i) be the empirical loss for distribution D1. We have sup f ∈F |Lf − ˆℓf | ≤sup f ∈F |Lf − ℓf...
2012
-
[2009]
Dld transactions open data
Land Sales. Dld transactions open data. https://www.dubaipulse.gov. ae/data/dld-transactions/dld_ transactions-open. Accessed: 2025-05-19. Philip M Long. The complexity of learning according to two models of a drifting environment. Proceedings of the Conference on Computationa...
2025
-
[2012]
Jadbabaie, and Alejandro Ribeiro
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
-
[2015]
Learning from time- changing data with adaptive windowing
Albert Bifet and Ricard Gavald `a. 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
-
[2024]
In contrast, our algorithm, based on wavelet-denoising, does not explicitly maintain a window size, yet achieve optimal estimation error rates
follow this direction. In contrast, our algorithm, based on wavelet-denoising, does not explicitly maintain a window size, yet achieve optimal estimation error rates. Non-Stationary Online Learning. There are various studies from non-stationary online learning that aim to trac...
2008
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.