Research map / Bandits and online learning / Online convex optimization and games
Efficient Non-stationary Online Learning by Wavelets with Applications to Online Distribution Shift Adaptation
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 a single-layer wavelet-based detection-restart method for non-stationary online learning, with a streaming wavelet operator built on a binary indexed tree, and applies it to online label shift.
Problem
Achieving optimal dynamic regret in non-stationary online learning usually requires a two-layer model ensemble with high computational and storage overhead; the paper asks whether near-optimal dynamic regret is possible with a single model.
Approach
Introduces underlying dynamic regret (comparators observed through unbiased estimates) and uses an adaptive restart triggered by online wavelet coefficient norms; a streaming wavelet operator updates only O(log T) coefficients per round via a binary indexed tree, avoiding ensembles.
Key results
- On the five image label-shift benchmarks under Linear and Square shifts, Wav-O/Wav-R are competitive with or better than ATLAS and FTFWH (e.g., Square Shift CIFAR10: Wav-O 14.72% vs ATLAS 15.21%).
- On the locomotion dataset, the single-layer Wav-based algorithms process nearly five times more items per second and use about half the storage of ATLAS.
- Theory: a single-layer method attains near-optimal dynamic regret, minimax optimal for exp-concave and strongly convex losses, and O(T^{2/3}(P_T^0)^{1/3}) for convex OLS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use wavelet detection with OGD update instead of ATLAS | Online label shift adaptation · CIFAR10, Square Shift | error (%): 15.21 -> 14.72 | Helped |
| Use wavelet detection with OGD update instead of ATLAS | Online label shift adaptation · CINIC10, Linear Shift | error (%): 26.44 -> 26.11 | Helped |
| Use wavelet detection with reweighting instead of ATLAS | Online label shift adaptation · CINIC10, Linear Shift | error (%): 26.44 -> 28.21 | Hurt |
| Use wavelet detection with OGD update instead of ATLAS | Online label shift adaptation · EuroSAT, Linear Shift | error (%): 07.21 -> 07.15 | Helped |
| Use wavelet detection with OGD update instead of ATLAS | Online label shift adaptation · EuroSAT, Square Shift | error (%): 06.99 -> 07.43 | Hurt |
| Use wavelet detection with reweighting instead of ATLAS | Online label shift adaptation · Fashion, Square Shift | error (%): 08.13 -> 07.32 | Helped |
| Use wavelet detection with OGD update instead of ATLAS | Online label shift adaptation · Fashion, Linear Shift | error (%): 07.84 -> 08.34 | Hurt |
| Use wavelet detection with reweighting instead of ATLAS | Online label shift adaptation · MNIST, Square Shift | error (%): 01.05 -> 01.03 | Helped |
| Use wavelet detection instead of the corresponding OGD baseline | Online label shift adaptation · CIFAR10, Linear Shift | error (%): 15.92 -> 15.52 | Helped |
| Use wavelet detection instead of the corresponding reweighting baseline | Online label shift adaptation · CIFAR10, Square Shift | error (%): 17.38 -> 15.55 | Helped |
| Use wavelet detection instead of the corresponding OGD baseline | Online label shift adaptation · EuroSAT, Square Shift | error (%): 07.33 -> 07.43 | Hurt |
| Use wavelet detection instead of the corresponding reweighting baseline | Online label shift adaptation · Fashion, Linear Shift | error (%): 8.15 -> 08.34 | Mixed |
Surprising findings
- For general convex OCO the single-layer rate is suboptimal (T^{2/3}(P_T)^{1/3} rather than the optimal sqrt(T P_T)), and the authors argue closing this gap is as hard as an open problem on reducing dynamic to strongly adaptive regret.
Limitations
- Suboptimal rate for general convex functions compared with ensemble methods.
- Requires known, bounded variance of the unbiased estimator (Assumption 1); sensitivity to sample size was only checked empirically.
- Still incurs O(log T) computational overhead from wavelet coefficients, as the authors acknowledge.
Experimental setup
Datasets: CIFAR10 CINIC10 EuroSAT Fashion-MNIST MNIST Locomotion (SHL)
Benchmarks: CIFAR10 CINIC10 EuroSAT Fashion-MNIST MNIST Locomotion (SHL) synthetic linear/square/sine shift OCO
Metrics: average error (%) efficiency (items/s) memory usage (MB) dynamic regret
Baselines: FIX OGD Reweight FTFWH ATLAS Effi-Dyn FLH-FTL LAME
Builds on: online trend filtering (Baby & Wang 2019, 2020) Online Newton Step Black Box Shift Estimation ATLAS (Bai et al. 2022) Effi-Dyn
Closest papers by meaning
- Non-stationary Projection-Free Online Learning with Dynamic and Adaptive Regret Guarantees (AAAI 2024 · similarity 0.89)
- Label Shift Meets Online Learning: Ensuring Consistent Adaptation with Universal Dynamic Regret (CVPR 2025 · similarity 0.89)
- Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability (ICML 2025 · similarity 0.88)
- A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of $\Theta(T^{2/3})$ and its Application to Best-of-Both-Worlds (NeurIPS 2024 · similarity 0.88)
- Online Non-convex Learning in Dynamic Environments (NeurIPS 2024 · similarity 0.88)
- A Simple and Optimal Approach for Universal Online Learning with Gradient Variations (NeurIPS 2024 · similarity 0.87)
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.