Research map / Learning theory and algorithms / Matrix and tensor methods

High-Probability Minimax Adaptive Estimation in Besov Spaces via Online-to-Batch

NeurIPS 2026 · Learning theory and algorithms › Matrix and tensor methods · approach: Nonconvex low-rank and sparse optimization · 0 citations (OpenAlex)

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 wavelet-based online learning algorithm with adaptive gradient clipping and expert aggregation that, via a refined online-to-batch conversion, yields high-probability, noise-level-adaptive minimax-optimal estimation rates for Besov regression.

Problem

Nonparametric regression over Besov spaces under sub-exponential noise requires minimax-optimal integrated squared error bounds that hold with high probability and adapt to unknown noise level and Besov parameters; standard online-to-batch conversion fails to give sharp high-probability rates in low

Approach

Combines comparator-adaptive online learners on wavelet coefficients with an adaptive clipping margin chosen by second-order expert aggregation over a grid of margins, and uses self-normalized concentration with a refined online-to-batch conversion to obtain l1-comparator high-probability regret and minimax risk bounds without knowing noise or Besov parameters.

Key results

• High-probability risk bound of order (||f||_B)^{2d/(2s+d)} (sigma^2)^{2s/(2s+d)} T^{-2s/(2s+d)} + B^2 log^2 T / T * log(1/delta), matching noise-level-aware minimax rates while adapting to unknown sigma, s, p, q.
• Adaptive clipping achieves high-probability l1-comparator regret O~(||c||_1 (G+sigma) sqrt(T)) without knowing noise parameters, answering an open question from prior work.
• Regret bounds hold with probability 1-6delta with only an O(log^2 T) overhead over oracle clipping.

Surprising findings

• Standard online-to-batch conversion from optimal adversarial online regret fails to yield minimax-optimal batch rates when s < d/2.

Limitations

• Expert set size grows polynomially in T (exponential in J0 via grid over initial scaling coefficients), making the method computationally heavy.
• Results stated for L2 risk only; extension to L^p' risks left open.
• Requires assumptions such as sub-exponential noise, bounded sup-norm of target, and s - d/p >= kappa > 0.

Experimental setup

Metrics: integrated squared error high-probability regret excess risk

Baselines: classical wavelet shrinkage noise-level-aware minimax estimator (batch) standard online-to-batch conversion

Builds on: comparator-adaptive online learning (coin-betting / mirror descent) MLProd Squint Online-to-batch conversion Adaptive online wavelet regression (Gaillard and Gerchinovitz-style multiscale a

Closest papers by meaning

• Minimax Adaptive Online Nonparametric Regression over Besov spaces (NeurIPS 2025 · similarity 0.93)
• Regularized least squares learning with heavy-tailed noise is minimax optimal (NeurIPS 2025 · similarity 0.86)
• Efficient Non-stationary Online Learning by Wavelets with Applications to Online Distribution Shift Adaptation (ICML 2024 · similarity 0.86)
• Posterior Contraction for Sparse Neural Networks in Besov Spaces with Intrinsic Dimensionality (NeurIPS 2025 · similarity 0.85)
• Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD (NeurIPS 2024 · similarity 0.84)
• The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithms (NeurIPS 2024 · similarity 0.84)