Research map / Learning theory and algorithms / Sample complexity
Adaptive Estimation and Learning under Temporal Distribution Shift
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes wavelet soft-thresholding (Haar, DB8, CDJV) estimators for the latest ground truth under temporal distribution shift, with point-wise error bounds that adapt to wavelet sparsity, and applies them to excess-risk bounds for classification and TV denoising.
Problem
Estimating the latest ground-truth value from a sequence of noisy observations whose mean drifts over time, without prior knowledge of the drift level, with sharp point-wise error guarantees; extended to learning under temporal training distribution shift.
Approach
Use wavelet soft-thresholding denoising of the observation sequence and read off the last reconstructed coordinate; error is bounded by wavelet-coefficient sparsity rather than an adaptive window, giving adaptivity without a window size and a single-ERM-call classification procedure.
Key results
- On the Doppler signal with known noise level, DB8 achieves MSE 0.007 at noise 0.2 versus 0.511 for AVG and 0.068 for HAAR.
- On the Dubai housing data (79%-1% split), HAAR achieves test MSE 0.0722 versus 0.0790 for ARW.
- Under unknown noise level, ARW and AVG slightly outperform the wavelet methods on the Random signal at some noise levels, so the advantage is not uniform.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use wavelet denoising instead of ARW for model selection | Dubai Land Department model selection · Dubai Land Department, 79%-1% split | MSE: 0.0790 ± 0.0005 -> 0.0722 ± 0.0006 | Helped |
| Use wavelet denoising instead of ARW for model selection | Dubai Land Department model selection · Dubai Land Department, 75%-5% split | MSE: 0.0719 ± 0.0005 -> 0.0736 ± 0.0011 | Hurt |
| Use DB8 rather than Haar wavelets (ablation) | Wavelet denoising · Synthetic Doppler, known noise standard deviation | MSE: 0.068 ± 0.0035 -> 0.007 ± 0.0002 | Helped |
| Use DB8 rather than Haar wavelets (ablation) | Wavelet denoising · Synthetic Random, known noise standard deviation | MSE: 0.094 ± 0.0014 -> 0.0661 ± 0.0026; 0.174 ± 0.0100 -> 0.212 ± 0.0062 | Mixed |
| Use wavelet denoising rather than AVG | Wavelet estimation · Synthetic signals, known noise standard deviation | MSE | Helped |
| Use wavelet denoising rather than AVG or ARW | Estimation with unknown noise standard deviation on Random signals · Synthetic Random, unknown noise standard deviation | MSE: 0.203 to 0.307 | Mixed |
| Use wavelet denoising rather than ARW | Real-data model selection · Dubai Land Department, 79%-1% split | MSE: 0.0790 ± 0.0005 -> 0.0722 ± 0.0006 | Helped |
| Use higher-order DB8 wavelets rather than Haar (ablation) | Wavelet denoising on real data · Dubai Land Department, 75%-5% split | MSE: 0.0736 ± 0.0011 -> 0.0768 ± 0.0008 | Hurt |
| Use one ERM oracle call rather than $O(\log n)$ calls | Wavelet-based classification algorithm · Binary classification under training distribution shift | ERM oracle calls: $O(\log n)$ -> exactly one | Helped |
| Add more training samples from a distribution different from the test distribution | Model trained under distribution shift · Training distribution shift | log-loss | Hurt |
Surprising findings
- On the real Dubai housing data, Haar outperforms the smoother DB8 wavelet, contrary to the synthetic results.
- On the Random piecewise-constant signal with unknown noise level, AVG and ARW slightly beat the wavelet methods at some noise levels.
Limitations
- Selecting an appropriate wavelet system for a given task is not principled and is left open.
- The method implicitly uses data without a window size, so change-point detection implications are not addressed.
- Real-data experiments depart from the iid sub-Gaussian noise assumption.
Experimental setup
Datasets: Synthetic Random and Doppler signals (500 points) Dubai Land Department apartment sales (2008-2023)
Benchmarks: Synthetic Random signal Synthetic Doppler signal Synthetic Sine signal Dubai Land Department housing data
Metrics: MSE test MSE
Baselines: AVG ARW Aligator HAAR (this paper) DB8 (this paper)
Builds on: wavelet smoothing AVG (adaptive window averaging) ARW (adaptive restart wavelet / non-stationary averaging)
Closest papers by meaning
- Tolerant Algorithms for Learning with Arbitrary Covariate Shift (NeurIPS 2024 · similarity 0.86)
- Efficient Non-stationary Online Learning by Wavelets with Applications to Online Distribution Shift Adaptation (ICML 2024 · similarity 0.85)
- A Unified View on Learning Unnormalized Distributions via Noise-Contrastive Estimation (ICML 2025 · similarity 0.85)
- Density-Softmax: Efficient Test-time Model for Uncertainty Estimation and Robustness under Distribution Shifts (ICML 2024 · similarity 0.84)
- Improving self-training under distribution shifts via anchored confidence with theoretical guarantees (NeurIPS 2024 · similarity 0.84)
- Minimax Optimal Two-Stage Algorithm For Moment Estimation Under Covariate Shift (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.