Research map / Bandits and online learning / Online convex optimization and games
Minimax Adaptive Online Nonparametric Regression over Besov spaces
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 parameter-free, wavelet-based online nonparametric regression algorithm (with a locally adaptive multi-scale expert aggregation extension) that achieves minimax-optimal regret against comparators in Besov spaces B^s_{pq} for convex losses.
Problem
Online adversarial regression with convex losses against highly irregular continuous competitor functions modeled by general Besov spaces, without prior knowledge of smoothness, integrability, or summability parameters, and with spatially inhomogeneous smoothness.
Approach
Learn wavelet coefficients online with coin-betting / parameter-free first-order updates restricted to active wavelets at each point, plus a dyadic-tree of local experts aggregated via sleeping-expert second-order weighting to track local smoothness.
Key results
- Algorithm achieves regret O(G||f||_{B^s_pq} sqrt(T)) for s >= d/2 or p < 2, and O(T^{1-s/d}) otherwise, matching minimax rates for convex losses against Besov competitors without knowing (s,p,q).
- Locally adaptive variant yields regret bounds in terms of local Besov regularity s_n and local norms, improving on global rates in inhomogeneous settings (example x^s with s in (1,2) gives rate in (1/5, 1/(2s+1)) exponent).
- Hölder corollary: regret C G||f||_inf sqrt(T) + C G|f|_s times sqrt(T), log_2(T) sqrt(T), or T^{1-s/d} depending on s vs d/2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| adapt starting resolution locally using a partition tree and aggregate local experts | Adaptive Online Wavelet Regression · Spatially inhomogeneous smoothness | regret | Helped |
| adapt to local smoothness and local semi-norm instead of using one global smoothness | Adaptive Online Wavelet Regression · f(x)=x^s with exp-concave losses | regret rate: O(T^r) with r \in (\nicefrac{1}{5}, \nicefrac{1}{(2s+1)}) vs. O(T^{\nicefrac{1}{(2s+1)}}) | Helped |
| use online wavelet decomposition without prior knowledge of (s,p,q) | Online Wavelet Decomposition · Besov spaces | regret rate | Helped |
Limitations
- Analysis restricted to competitors in L-infinity (s > d/p); general L^p with p<inf left open.
- Computational/dimensional complexity grows exponentially with regularity parameter S.
- Local adaptation only in smoothness; fully local (s_n, p_n, q_n) left to future work.
Experimental setup
Metrics: regret
Baselines: defensive forecasting (wild prediction rules) Sobolev kernel online regression chaining-based Lipschitz online regression
Builds on: coin-betting parameter-free online learning localized chaining for online regression defensive forecasting sleeping experts
Closest papers by meaning
- High-Probability Minimax Adaptive Estimation in Besov Spaces via Online-to-Batch (NeurIPS 2026 · similarity 0.93)
- Discounted Adaptive Online Learning: Towards Better Regularization (ICML 2024 · similarity 0.88)
- Online Composite Optimization Between Stochastic and Adversarial Environments (NeurIPS 2024 · similarity 0.87)
- Gradient-Variation Online Learning under Generalized Smoothness (NeurIPS 2024 · similarity 0.87)
- Efficient Non-stationary Online Learning by Wavelets with Applications to Online Distribution Shift Adaptation (ICML 2024 · similarity 0.87)
- Parameter-free Algorithms for the Stochastically Extended Adversarial Model (NeurIPS 2025 · 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.