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

Paul Liautaud, Pierre Gaillard, Olivier Wintenberger

<figure><img src="image_1.png" /></figure>

## To cite this version:

Paul Liautaud, Pierre Gaillard, Olivier Wintenberger. High-Probability Minimax Adaptive Estimation in Besov Spaces via Online-to-Batch. 2026. hal-05506033

HAL Id: hal-05506033

https://hal.science/hal-05506033v1

Preprint submitted on 11 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
HIGH-PROBABILITY MINIMAX ADAPTIVE ESTIMATION IN BESOV SPACES VIA ONLINE-TO-BATCH

A PREPRINT

Paul Liautaud

Sorbonne Université, CNRS, LPSM
F-75005 Paris, France

paul.liautaud@sorbonne-universite.fr

Pierre Gaillard

Université Grenoble Alpes, Inria
CNRS, Grenoble INP, LJK
38000 Grenoble, France

pierre.gaillard@inria.fr

Olivier Wintenberger

Sorbonne Université, CNRS, LPSM
F-75005 Paris, France

olivier.wintenberger@sorbonne-universite.fr

February 11, 2026

ABSTRACT

We study nonparametric regression over Besov spaces from noisy observations under sub-exponential noise, aiming to achieve minimax-optimal guarantees on the integrated squared error that hold with high probability and adapt to the unknown noise level. To this end, we propose a wavelet-based online learning algorithm that dynamically adjusts to the observed gradient noise by adaptively clipping it at an appropriate level, eliminating the need to tune parameters such as the noise variance or gradient bounds. As a by-product of our analysis, we derive high-probability adaptive regret bounds that scale with the $\ell_1$-norm of the competitor. Finally, in the batch statistical setting, we obtain adaptive and minimax-optimal estimation rates for Besov spaces via a refined online-to-batch conversion. This approach carefully exploits the structure of the squared loss in combination with self-normalized concentration inequalities.

**Keywords:** Minimax Adaptive Estimation, Noise-Level-Aware, Besov spaces, Online-to-Batch, High probability

1 Introduction

A fundamental challenge in statistics and machine learning is the estimation of an unknown function $f$ from noisy observations. Given a sample of $T \ge 1$ i.i.d. data points $(X_t, Y_t)_{t=1}^T$ following the regression model

$$Y_t = f(X_t) + \epsilon_t, \quad t = 1, \dots, T,$$

where $\epsilon_t$ denotes a sub-exponential zero-mean noise, the goal is to construct an estimator $\tilde{f}_T$ of the true function $f: \mathcal{X} \to \mathbb{R}$, supported on a compact domain $\mathcal{X} \subset \mathbb{R}^d$, $d \ge 1$. The quality of an estimator $\tilde{f}_T$ is measured by the integrated squared error $\|\tilde{f}_T - f\|_{L^2(\mathbb{P}_X)}$. When $f$ is assumed to belong to a Besov space $B_{pq}^s$ (see Section 3), the landmark work of Donoho and Johnstone [1998] established the minimax-optimal rates for the mean integrated squared error, which are attained by wavelet shrinkage methods.

While this classical theory focuses on optimality in expectation, many modern learning applications—ranging from safety-critical systems to precision medicine—require guarantees that hold with high probability. This motivates the study of estimators that achieve minimax-optimal performance beyond the average-case regime.
Our objective is therefore to design an estimator $\bar{f}_T$ that satisfies, with high probability, a minimax-adaptive risk bound of the form

$$ \|\bar{f}_T - f\|_2^2 = O\left( \|f\|_B^{\frac{2d}{2s+d}} (\sigma^2)^{\frac{2s}{2s+d}} T^{-\frac{2s}{2s+d}} \right), \quad (1) $$

for any continuous function $f \in B_{pq}^s$, without prior knowledge of the Besov parameters $(s, p, q)$, the Besov norm $\|f\|_B$, or the noise variance $\sigma^2$. This bound is said to be *noise-level-aware* since it exhibits minimax-optimal dependence on the noise level $\sigma$. Importantly, unlike classical minimax analyses [e.g., Delyon and Juditsky, 1996, Donoho and Johnstone, 1998], which characterize rates asymptotically as $T \to \infty$ under known or fixed noise level, our result adapts to the variance $\sigma^2$ and matches the noise-level-aware minimax rates recently derived in DeVore et al. [2025]. Achieving such guarantees simultaneously with high probability and full adaptivity remains challenging for standard wavelet shrinkage and aggregation techniques.

To address this challenge, we turn to the framework of *online learning*. Online algorithms are natural candidates for adaptive estimation, as they are designed to control regret without prior knowledge of the data-generating process. By defining the estimator $\bar{f}_T$ as the average of the online iterates, $\bar{f}_T = \frac{1}{T} \sum_{t=1}^T \hat{f}_t$, one can relate the *excess risk* to the *stochastic regret* via Jensen's inequality:

$$ \begin{aligned} \|\bar{f}_T - f\|_2^2 &= \mathbb{E}_{XY}[(\bar{f}_T(X) - Y)^2] - \mathbb{E}_{XY}[(f(X) - Y)^2] \\ &\le \frac{1}{T} \sum_{t=1}^T \mathbb{E}_{t-1}[(\hat{f}_t(X_t) - Y_t)^2] - \mathbb{E}_{t-1}[(f(X_t) - Y_t)^2], \end{aligned} \quad (2) $$

where $\mathbb{E}_{t-1}$ denotes the expectation conditioned on the first $t-1$ samples and since $(X_t, Y_t), t \ge 1$ are i.i.d. This *online-to-batch conversion principle* [Littlestone, 1989, Cesa-Bianchi et al., 2004, Shalev-Shwartz, 2025] ensures that any regret bound for convex losses yields an equivalent excess risk bound *in expectation*. However, despite its popularity, standard online-to-batch conversion typically fails to provide sharp *high-probability* risk guarantees and adaptations of the online algorithms are required [Wintenberger, 2017, van der Hoeven et al., 2023]. While the expected regret may be optimal, fluctuations along the regret trajectory can lead to suboptimal concentration behavior when translated to the batch setting. This issue is particularly severe in nonparametric regimes, where the minimax rates can be as fast as $T^{-2s/(2s+d)}$, which is strictly faster than $T^{-1/2}$ when $s \ge d/2$. In this regime, standard first-order concentration inequalities are insufficient to control these fluctuations at the optimal rate. Recently, van der Hoeven et al. [2023] proposed a general reduction for deriving high-probability risk bounds from online learning guarantees. However, this approach is not sufficient to attain minimax-optimal rates in the low-regularity regime $s < d/2$ where the best known online regret bounds scale as $O(T^{-s/d})$ [Rakhlin and Sridharan, 2014], which is strictly slower than the optimal batch risk rate $O(T^{-2s/(2s+d)})$. The central challenge in this paper is therefore to design online algorithms ($\hat{f}_t$) whose adaptive nonparametric regret guarantees in (2) can be converted into minimax-optimal *high-probability* risk bounds of the form (1).

Recently, Liautaud et al. [2025] introduced a wavelet-based online algorithm that achieves adaptive minimax-optimal regret in the adversarial setting. Their approach relies in particular on so-called *comparator-adaptive* online algorithms, which guarantee regret bounds of order $\tilde{O}(\|c\|_1 G \sqrt{T})$ for G-Lipschitz losses against any comparator $c \in \mathbb{R}^N$, $N \ge 1$. However, in the unbounded stochastic setting considered here, the loss functions are no longer Lipschitz, and such guarantees can fail dramatically. To overcome this difficulty, we employ a *gradient clipping* strategy [Zhang and Cutkosky, 2022] with an adaptive online threshold. This modification allows us to recover high-probability control of the regret while preserving comparator adaptivity. As a by-product of our analysis, we obtain new results for stochastic online convex optimization, establishing regret bounds of the form $\tilde{O}(\|c\|_1 (G + \sigma) \sqrt{T})$ holding with high probability for any comparator $c \in \mathbb{R}^N$ with $\|c\|_\infty < \infty$ and with unknown noise level $\sigma$, answering an open question in Zhang and Cutkosky [2022].

**Notations.** The notation $O(\cdot)$ hides universal constant factors, while $\tilde{O}(\cdot)$ additionally hides polylogarithmic factors. For any integer $k \ge 1$, we denote $[k] := \{1, \dots, k\}$. Boldface letters are used to denote multivariate quantities, whereas standard (non-bold) letters denote scalar quantities. We denote $a \vee b = \max\{a, b\}$ and, for any $x \in \mathbb{R}$ and threshold $\tau > 0$, the clipping operator of $x$ in $[-\tau, \tau]$ is defined by $\text{clip}(x, \tau) = x$ if $|x| \le \tau$ and $\text{sign}(x)\tau$ otherwise.

**Contributions and outline of the paper.** In Section 2, we first derive by-product results for stochastic online convex optimization with adaptive guarantees. We establish high-probability comparator-adaptive regret bounds of order $\tilde{O}(\|c\|_1 \sqrt{T})$ in the constrained setting $\|c\|_\infty \le C$, under sub-exponential gradient noise. In Section 2.2, we extend these results to the unknown-noise setting by introducing an adaptive gradient clipping procedure. This method removes the need for prior knowledge of the noise level and is general enough to be
applicable in other online learning contexts. Finally, we leverage these online learning guarantees to design an adaptive nonparametric estimator in Section 3. The resulting algorithm achieves minimax, noise-level-aware risk bounds with high probability, without requiring prior knowledge of the noise $\sigma$.

## 1.1 Related work

**Nonparametric regression over Besov spaces.** The minimax theory for nonparametric regression over Besov spaces is well established, with classical results characterizing optimal rates in expectation; see, e.g., Delyon and Juditsky [1996], Donoho and Johnstone [1998]. More recently, DeVore et al. [2025] derived sharp upper and lower bounds that are explicitly noise-level-aware in the batch setting, under the assumption of known Gaussian noise variance. These results highlight the importance of adaptivity to the noise level and motivate the use of online learning techniques to achieve such adaptivity in a data-driven manner. Recently Liautaud et al. [2025] proposed a polynomial-time online algorithm achieving minimax-optimal regret against adversarial sequences and Besov-smooth competitors. While their focus is on adversarial regret, our work leverages related online ideas to derive high-probability, noise-level-adaptive risk guarantees in the stochastic regression setting.

**Online-to-Batch.** Classical online-to-batch reductions [Littlestone, 1989, Cesa-Bianchi et al., 2004] relate online regret to batch risk, but are limited to guarantees in expectation and do not yield fast rates with high probability. The route to obtain high probability $O(1/\tau)$ excess risk bounds via online to batch conversions was initiated by Wintenberger [2017]. More recently, van der Hoeven et al. [2023] proposed a general reduction for deriving high-probability risk bounds from sequential regret. However, this approach does not recover minimax-optimal rates in our setting, in particular in the low-regularity regime $s < d/2$, where the best known online regret bounds scale as $O(T^{-s/d})$ [Rakhlin and Sridharan, 2014], which is strictly slower than the optimal batch rate $O(T^{-2s/(2s+d)})$. In contrast, our analysis departs from generic online-to-batch reductions and relies on a refined control of the stochastic regret in (2), under a stochastic directional derivative condition (Assumption 2). This approach is inspired by recent work on noisy online convex optimization [Wintenberger, 2024], which established high-probability fast rates under sub-Gaussian perturbations, but extends it to a more general setting tailored to nonparametric regression and adaptive wavelet estimation.

**Online convex optimization with stochastic unbounded gradients.** Most online convex optimization algorithms require a priori gradient bounds, or incur exponential penalties when gradients are unbounded [Cutkosky and Boahen, 2017]. Recent works address unbounded gradients through stochastic assumptions and gradient clipping. In particular, Jun and Orabona [2019] obtain in-expectation guarantees under sub-exponential noise, while Zhang and Cutkosky [2022] derive high-probability, parameter-free regret bounds using regularization techniques. As a by-product of our analysis, we complement this line of work by establishing high-probability $\ell_1$ comparator-adaptive regret guarantees in a setting with bounded iterates and unbounded stochastic gradients.

## 2 High probability comparator-adaptive regret with constrained iterates and noisy unbounded gradients

We consider the following setting of stochastic online prediction. Let $N \ge 1$ and $(\ell_t : \mathbb{R}^N \to \mathbb{R}_+ )_{t \ge 1}$ a collection of random convex differentiable loss functions, sequentially observed. At each time $t$, a learner forms a prediction $c_t \in \mathbb{R}^N$ based on the past observations $\mathcal{F}_{t-1} = \{c_1, \nabla \ell_1(c_1), \dots, c_{t-1}, \nabla \ell_{t-1}(c_{t-1})\}$, where $\nabla \ell_s(c_s)$ is the gradient of $\ell_s$ at $c_s$. The learner aims at minimizing the cumulative stochastic regret

$$R_T(\mathbf{c}) := \sum_{t=1}^{T} \mathbb{E}_{t-1}[\ell_t(\mathbf{c}_t)] - \mathbb{E}_{t-1}[\ell_t(\mathbf{c})], \quad \text{where} \quad \mathbb{E}_{t-1}[\cdot] = \mathbb{E}[\cdot | \mathcal{F}_{t-1}],$$

with respect to all $\mathbf{c} \in \mathbb{R}^N$ such that $\|\mathbf{c}\|_\infty \le C$ for some fixed $C > 0$. In particular, considering the Dirac masses, one obtains $\ell_t = \mathbb{E}_{t-1}[\ell_t]$ and the stochastic regret matches the regret more commonly used in the online (adversarial) learning literature. In this section, we present Algorithm 1, which achieves a stochastic regret bound of order $\tilde{O}(\|\mathbf{c}\|_1(G + \sigma)\sqrt{T})$ with high probability with unbounded gradients of variance $\sigma$ and expected bound $G \ge |\mathbb{E}_{t-1}[\nabla \ell_t(\mathbf{c}_t)]|$. In particular, we assume that gradients' noise admit sub-exponential tails, as formalized in Assumption 1.

**Assumption 1 (Sub-exponential gradient noise).** The gradient sequence $(\hat{g}_t)_{t \ge 1}$ is said to have conditionally sub-exponential noise if there exist constants $\nu, \mu > 0$ such that, for all $t \ge 1$, conditionally on the past $\mathcal{F}_{t-1}$,
the centered gradient noise

$$ \xi_t := \hat{g}_t - \mathbb{E}_{t-1}[\hat{g}_t] $$

satisfies the following tail bound: for all $u \ge 0$,

$$ \max_{1 \le n \le N} \mathbb{P}_{t-1}(|\xi_{n,t}| \ge u) \le \exp\left(-\frac{1}{2} \min\left(\frac{u^2}{\nu^2}, \frac{u}{\mu}\right)\right), $$

where $\mathbb{P}_{t-1}$ denotes the conditional probability given the past observations $\mathcal{F}_{t-1}$.

**Stochastic directional derivative condition.** We introduce the following assumption on the random losses ($\ell_t$) revealed by the environment.

**Assumption 2 (Stochastic directional derivative condition).** We say that the (random) losses $\ell_t$ satisfy the stochastic directional derivative condition for some constant $\alpha > 0$ if for every $\mathbf{c}_1, \mathbf{c}_2 \in [-C, C]^N, C > 0$

$$ \mathbb{E}_{t-1}[\ell_t(\mathbf{c}_1) - \ell_t(\mathbf{c}_2)] \le \mathbb{E}_{t-1}[\nabla\ell_t(\mathbf{c}_1)^\top(\mathbf{c}_1 - \mathbf{c}_2) - \frac{\alpha}{2}(\nabla\ell_t(\mathbf{c}_1)(\mathbf{c}_1 - \mathbf{c}_2))^2]. $$

Remark that the stochastic directional derivative condition holds for non-convex losses and unbounded gradients. Setting $\alpha = 0$ coincides with the convexity of $\mathbb{E}_{t-1}[\ell_t], t \ge 1$. This assumption is a weaker condition than exp-concavity of the losses ($\ell_t$), and follows, in the deterministic setting, from the exp-concavity of the loss functions [Lemma 4.3 Hazan et al., 2016]. It coincides with Assumption (H2) of Wintenberger [2024].

## 2.1 Algorithm: Adaptive Learning with Unbounded Noisy Gradients via Clipping

We now introduce an online learning algorithm designed to operate in the presence of unbounded gradient observations, while retaining high-probability, comparator-adaptive regret guarantees of type $\tilde{O}(\|c\|_1\sqrt{T})$. Our construction is modular: each coordinate is updated by an independent one-dimensional online subroutine, which receives clipped gradient feedback. This design allows us to leverage generic comparator-adaptive online algorithms (satisfying Assumption 3), while ensuring robustness in regimes where gradient magnitudes may be large.

**Algorithm 1: Adaptive Learning with Unbounded Noisy Gradients via Clipping at time t**

1 **Input:** $N \ge 1$ algorithms $A_1, \dots, A_N$ satisfying Assumption 3, diameters $(C_n)$ of feasible sets, bounds on gradients $|\mathbb{E}_{t-1}[\nabla\ell_t(\mathbf{c}_t)_n]| \le G_{n,t}, n \in [N]$ and clipping margin $\Delta_t > 0$;

2 Predict $\mathbf{c}_t = (c_{n,t})_{n=1}^N$;

3 Receive noisy gradient $\hat{g}_t = \nabla\ell_t(\mathbf{c}_t)$;

4 **for** $n = 1, \dots, N$ **do**

5 Define clipping threshold as $\bar{G}_{n,t} = G_{n,t} + \Delta_t$;

6 Clip gradient $\tilde{g}_{n,t} = \max(-\bar{G}_{n,t}, \min(\bar{G}_{n,t}, \hat{g}_{n,t}))$ or $\bar{g}_{n,t} = 0$ if $G_{n,t} = 0$;

7 Receive $c_{n,t+1} \in [-C_n, C_n]$ from $A_n$ using $(\tilde{g}_{n,t}, \bar{G}_{n,t})$;

8 **Output:** $\mathbf{c}_{t+1}$

**Assumption on the coordinate subroutine.** We assume that each coordinate subroutine $A_n, n \in [N]$ satisfies the following assumption.

**Assumption 3 (Comparator-adaptive algorithm).** Let $T \ge 1, C > 0$ and let $g_1, \dots, g_T \in \mathbb{R}$ be a sequence of scalar gradients such that $|g_t| \le G_t$ for all $t \le T$. An online algorithm A starting at $c_1 \in [-C, C]$ and producing predictions $(c_t)_{t=1}^T \subset [-C, C]$ is said to be comparator-adaptive if for some factors $\Xi_1, \Xi_2 > 0$ and for any comparator $c \in [-C, C]$,

$$ \sum_{t=1}^{T} g_t(c_t - c) \le |c - c_1| \left( \Xi_1 \sqrt{\sum_{t=1}^{T} g_t^2} + \Xi_2 \sup_{1 \le t \le T} G_t \right). $$

This assumption holds for a broad class of first-order online learning algorithms such as online mirror descent with self-tuned learning rates or coin-betting style updates [Orabona and Pál, 2016, Cutkosky and Orabona, 2018, Mhammedi and Koolen, 2020, Jacobsen and Cutkosky, 2022, Chen et al., 2021]. These are referred to as comparator-adaptive algorithms as they provide optimal adaptivity to the magnitude of the comparator $|c|$ in
the regret, typically at the cost of logarithmic factors absorbed into $\Xi_1$ and $\Xi_2$. Algorithms satisfying the linear regret bound in Assumption 3 are primarily developed for the unconstrained setting ($C = \infty$). We here consider an extension in which the predictions $c_t$ are constrained to $[-C, C]$, typically at the cost of a multiplicative constant in the regret, which we also absorb into the factors $\Xi_1$ and $\Xi_2$ [see, e.g., Cutkosky and Orabona, 2018]. Importantly, these types of algorithms are not Lipschitz-adaptive: they require prior knowledge of a gradient bound $G_t \ge |g_t|$ at each time step $t \ge 1$, and failing to do so results in an exponential penalty in the regret bound [Cutkosky and Boahen, 2017, Mhammedi and Koolen, 2020]. In our unbounded-gradient setting, this limitation can be overcome via gradient clipping (in Alg. 1), provided that the clipping level is carefully calibrated.

**First result: high probability comparator-adaptive regret with known noise level.** We first establish a guarantee for Algorithm 1 under the assumption that, at each time $t$, the algorithm is provided with the optimal clipping threshold $\Delta_t$, which depends on the noise parameters $(\nu, \mu)$ appearing in Assumption 1. This oracle assumption is subsequently removed in the following Section 2.2, where we design an adaptive gradient clipping strategy.

**Theorem 1 (High-probability $\ell_1$-comparator-adaptive regret).** Let $G, C > 0$, $\delta \in (0, 1)$, and $N \in \mathbb{N}^*$. Assume $(\ell_t)_{t \ge 1}$ satisfy Assumption 2 and at each time step $t \ge 1$ we are given a stochastic gradient $\nabla \ell_t(c_t) \in \mathbb{R}^N$ satisfying Assumption 1 with parameter $\nu, \mu > 0$, and

$$ \|\mathbb{E}_{t-1}[\nabla \ell_t(c_t)]\|_{\infty} \le G \quad \text{and} \quad \max_{1 \le n \le N} \mathbb{E}_{t-1}[|\nabla \ell_t(c_t)_n - \mathbb{E}_{t-1}[\nabla \ell_t(c_t)_n]|^2] \le \sigma^2. $$

Then Algorithm 1, run over $T$ steps with $C_n = C$, $G_{n,t} = G$ for every $n \in [N]$, $t \ge 1$ and clipping margins

$$ \Delta_t = \left( \nu \sqrt{2 \log \left( \frac{(\sqrt{\pi/2\nu+2\mu})t}{\log(\delta^{-1})} \right)} \vee 2\mu \log \left( \frac{(\sqrt{\pi/2\nu+2\mu})t}{\log(\delta^{-1})} \right) \right), \quad t \ge 1 $$

satisfies, with probability at least $1 - 2\delta$, for all comparators $c \in \mathbb{R}^N$ such that $\|c\|_{\infty} \le C$,

$$ R_T(c) \le O\left[ \|c\|_1(G + \sigma)\sqrt{T} + \left( (CN(G + (\nu \vee \mu) \log T))^2 + \frac{1}{\alpha} \right) \log(\delta^{-1}) \right]. $$

The proof is postponed to Appendix A, where we state and prove a more general version of Theorem 1. This full result, stated as Theorem 4, will be instrumental for our regression setting in the next section, where we consider a multiscale approach with heterogeneous diameters.

Note that Algorithm 1 requires the noise parameters $\mu, \nu > 0$ to be specified in advance. In Section 2.2, we remove this requirement and develop an adaptive clipping procedure that achieves the same guarantees. In particular, the variance parameter $\sigma > 0$ is one dimensional and not passed to the algorithms while it appears optimally [Jun and Orabona, 2019] in our regret bound $\tilde{O}(\|c\|_1(G + \sigma)\sqrt{T})$ that holds in high probability. Note also that for simplicity we stated Theorem 1 with uniform noise in $(\nu, \mu, \sigma)$ over the coordinates. Defining a coordinate dependent clipping margin with $(\mu_n, \nu_n)$, $n \in [N]$ would lead to an adaptive regret bound scaling as $O(\sum_n |c_n|(G + \sigma_n)\sqrt{T} + C^2(\nu_n \vee \mu_n)^2 \log(T)^2)$, with high probability.

Our Theorem 1 also parallels the results of Zhang and Cutkosky [2022]. As discussed in their work, even in the constrained setting where $\|c_t\|_{\infty} \le C, t \ge 1$, obtaining a high-probability regret bound of order $\tilde{O}(\|c\|_1\sqrt{T})$ is nontrivial. Indeed, a direct application of standard sub-exponential martingale concentration inequalities typically introduces an additional deviation term of order $\tilde{O}(NC\sqrt{T})$, which is too coarse to preserve the desired dependence on $\|c\|_1$. In contrast, under Assumption 2, we are able to leverage second-order concentration tools based on self-normalized martingale inequalities. This approach allows us to control the deviation term at the cost of only an additional $O(\log^2 T)$ factor, thereby maintaining the target high-probability regret bound $\tilde{O}(\|c\|_1\sqrt{T})$ without resorting to regularized or surrogate loss functions. We also note that Theorem 5 of Zhang and Cutkosky [2022] does not yield regret bounds with $\ell_1$-norm comparator dependence. Their high-probability guarantees are instead restricted to $\|c\|_p$-dependence for some $p \in (1, 2]$. In contrast, maintaining an optimal dependence of order $\tilde{O}(\|c\|_1\sqrt{T})$ with high probability is essential for our analysis. This $\ell_1$-comparator adaptivity plays a crucial role in Section 3, where it enables the derivation of adaptive nonparametric risk bounds.

## 2.2 Adaptive clipping strategy

In Theorem 1, we showed that Algorithm 1, when run with an optimal clipping threshold $\bar{G}^* = G + \Delta^*$ that exceeds the true gradient bound $G \ge \|\mathbb{E}_{t-1}[\nabla \ell_t(c_t)]\|_{\infty}$ by a logarithmic margin $\Delta^* \propto (\nu \vee \mu) \log T$, achieves a
high-probability regret guarantee of $O(\|c\|_1(G + \sigma)\sqrt{T} + (CN)^2(G + \Delta^*)^2)$ for any $c \in \mathbb{R}^N$, $\|c\|_{\infty} \le C$. In this section, we design a procedure that achieves similar comparator-adaptive guarantees as in Theorem 1, without requiring prior knowledge of the clipping margin $\Delta^* > 0$, which depends on the unknown noise parameters $(\nu, \mu)$. As a consequence, the proposed strategy adapts sequentially to the level of the stochastic noise.

**Adaptive clipping via expert aggregation.** Given $T \ge 1$, we define the following set of clipping margins to pass to Algorithm 1

$$ \mathcal{D} := \{\Delta = 0, \dots, \lfloor \sqrt{T} \rfloor + 1\}. \quad (3) $$

The procedure consists in running $|\mathcal{D}| = O(\sqrt{T})$ independent instances of Algorithm 1, with a bound on the true gradient for every time $t \ge 1$, $G \ge \|\mathbb{E}_{t-1}[\nabla\ell_t(\mathbf{c}_t)]\|_{\infty}$, $t \ge 1$ and with a clipping margin set at each $\Delta \in \mathcal{D}$. Each instance then produces a prediction $\mathbf{c}_t^\Delta$ at time $t$ associated to each margin $\Delta \in \mathcal{D}$ and we leverage an expert algorithm satisfying Assumption 4 to sequentially aggregates the predictions $(\mathbf{c}_t^\Delta)_{\Delta \in \mathcal{D}}$ as, for every $t \ge 1$

$$ \hat{\mathbf{c}}_t = \sum_{\Delta \in \mathcal{D}} w_t^\Delta \mathbf{c}_t^\Delta, \quad \text{where} \quad w_t^\Delta \ge 0, \sum_{\Delta \in \mathcal{D}} w_t^\Delta = 1, t \ge 1. \quad (4) $$

Remark that given the bound of Theorem 1 scaling as $O(\|c\|_1(G + \sigma)\sqrt{T} + (CN(G + \Delta))^{2/3})$, a clipping margin at $\Delta = \sqrt{T}$ leads to a bound in $O(T)$ which is of the same order of the worst regret case bound $O(NCGT)^{1/3}$, which justifies that the range $\sqrt{T}$ of the grid $\mathcal{D}$ is sufficient.

**Assumption on the expert aggregation algorithm.** We introduce the following assumption for the expert aggregation subroutine we use in (4).

**Assumption 4 (Second-order adaptive algorithm).** Let $T, E \ge 1$ and let $\hat{\nabla}_1, \dots, \hat{\nabla}_T \in \mathbb{R}^E$ be any sequence of gradients. An expert aggregation algorithm is said to be second-order adaptive if, starting from the uniform prior $\mathbf{w}_1 = (\frac{1}{E})_{1 \le e \le E}$, it produces iterates $\mathbf{w}_t = (w_t^e)_{1 \le e \le E}$ such that $\sum_{e \in E} w_t^e = 1$ and for every $e \in \{1, \dots, E\}$, the following regret bound holds:

$$ \sum_{t=1}^{T} \hat{\nabla}_{t}^{\top} \mathbf{w}_{t} - \hat{\nabla}_{e,t} \le \Xi_3 \sqrt{\log(E) \sum_{t=1}^{T} (\hat{\nabla}_{t}^{\top} \mathbf{w}_{t} - \hat{\nabla}_{e,t})^2 + \Xi_4 \log(E) \max_{1 \le t \le T} \|\hat{\nabla}_t\|_{\infty}}, $$

where $\Xi_3$ and $\Xi_4$ are universal and independent of the gradient range and can hide $\log \log T$ terms.

Assuming prior knowledge of a bound on the gradients, MLProod [Gaillard et al., 2014] was the first algorithm to achieve this type of second-order regret guarantee. Building on this work, a substantial line of research has since focused on designing algorithms that enjoy such guarantees while being scale-free and Lipschitz-adaptive [see, e.g., Mhammedi et al., 2019, for a review]. Well-known instances of this class include BOA [Wintenberger, 2017] and Squint [Koolen and Van Erven, 2015]. Unlike standard methods that require an a priori bound on the sup-norm of the gradients (e.g., those satisfying Assumption 3), algorithms satisfying Assumption 4 adapt both to the observed gradient range $\max_{t \le T} \|\hat{\nabla}_t\|_{\infty}$ and to the cumulative quadratic variation of the prediction errors.

**Second result: high probability comparator-adaptive regret with adaptive clipping.** We now establish a high-probability comparator-adaptive regret bound in Theorem 2, for the strategy discussed in (4), when the noise level is unknown. By introducing an adaptive clipping scheme, the algorithm automatically calibrates the clipping thresholds from the observed data, while retaining the same order of regret as in the oracle setting up to logarithmic factors.

**Theorem 2.** Let $T, N \ge 1$ and $\delta \in (0, 1)$. Assume $(\ell_t)_{t \ge 1}$ satisfy Assumption 2 for some $\alpha > 0$ and for every $t \ge 1$, $c \in \mathbb{R}^N$, $\|c\|_{\infty} \le C$, $\nabla\ell_t(c)$ satisfies Assumption 1,

$$ \|\mathbb{E}_{t-1}[\nabla\ell_t(\mathbf{c})]\|_{\infty} \le G \quad \text{and} \quad \max_{1 \le n \le N} \mathbb{E}_{t-1}[|\nabla\ell_t(\mathbf{c})_n - \mathbb{E}_{t-1}[\nabla\ell_t(\mathbf{c})_n]|^2] \le \sigma^2. $$

With sequential predictions $\hat{\mathbf{c}}_t = \sum_{\Delta \in \mathcal{D}} w_t^\Delta \mathbf{c}_t^\Delta$, $t \ge 1$ as in (4) with $(w_t^\Delta)_{\Delta \in \mathcal{D}}$ satisfying Assumption 4, the regret is bounded with probability $1 - 6\delta$ as

$$ R_T(\mathbf{c}) \le O\left[\|\mathbf{c}\|_1(G + \sigma)\sqrt{T} + \left(\alpha + 1\right)\left(NC\left(G + (\nu \vee \mu)\log(T)\right)\right)^2 + \frac{1}{\alpha}\log(\delta^{-1})\right]. $$

<footnote n="1">¹For every $t \ge 1$, one has $\mathbb{E}_{t-1}[\ell_t(\mathbf{c}_t)] - \mathbb{E}_{t-1}[\ell_t(\mathbf{c})] \le \|\mathbb{E}_{t-1}[\nabla\ell_t(\mathbf{c}_t)]\|_{\infty} \|\mathbf{c}_t - \mathbf{c}\|_1 \le 2NCG$, by convexity of $c \mapsto \mathbb{E}_{t-1}[\ell_t(\mathbf{c})]$ induced by Assumption 2, with $\alpha = 0$.</footnote>
We provide a detailed version of Theorem 2 and a proof in Appendix B. To give some intuition, an adaptive expert algorithm of type Assumption 4 is key to derive this result: under Assumption 1, the maximum magnitude expert gradient $\sup_t ||\nabla_t||_\infty$ is a random variable that scales logarithmically with $T$ in high probability, and the variance (second order) term is managed with Assumption 2, enabling the recovery of high-probability regret bounds in Theorem 2, of type $\tilde{O}(|c|_1(G+\sigma)\sqrt{T})$ without assuming bounded gradient nor the knowledge of the noise parameters $\sigma, \nu, \mu > 0$. Interestingly, in the setting of sub-exponential noise and losses satisfying the stochastic directional derivative assumption, our result answers a challenging question raised by Zhang and Cutkosky [2022] as to whether it is possible to achieve a regret bound of order $\tilde{O}(|c|_1(G+\sigma)\sqrt{T})$ while remaining adaptive to the noise amplitude. Importantly, we believe that our adaptive clipping procedure with unknown noise level can be applied to a broader range of learning problems. In particular, this result will play a central role in the learning of nonparametric functions with noisy observations in Section 3, and enables the derivation of minimax adaptive nonparametric risk guarantees with high probability.

# 3 High-Probability Regression over Besov Spaces via Online-to-Batch

We now turn to the main statistical contribution of the paper, where we leverage the online learning guarantees established in the previous sections to derive high-probability minimax risk bounds for nonparametric regression over Besov spaces.

**Setting: statistical learning.** We observe a sample of $T \ge 1$ i.i.d. pairs $(X_1, Y_1), \dots, (X_T, Y_T)$ drawn from an unknown distribution on $\mathcal{X} \times \mathbb{R}$, where $\mathcal{X} \subset \mathbb{R}^d$ is compact. The data follow the nonparametric regression model

$$Y_t = f(X_t) + \epsilon_t, \quad t = 1, \dots, T,$$

where $f: \mathcal{X} \to \mathbb{R}$ is an unknown regression function and $(\epsilon_t)_{t \ge 1}$ is a sequence of zero-mean noise variables with unknown variance $\sigma^2 > 0$. Our goal is to construct an estimator $\hat{f}_T$ that minimizes, in the minimax sense, the excess prediction risk

$$\mathbb{E}_{XY}[(\hat{f}_T(X) - Y)^2] - \mathbb{E}_{XY}[(f(X) - Y)^2],$$

uniformly over $f$ belonging to a Besov space (defined below). The estimator $\hat{f}_T$ is obtained via an online-to-batch conversion and takes the form

$$\hat{f}_T = \frac{1}{T} \sum_{t=1}^{T} \hat{f}_t,$$

where each $\hat{f}_t$ is a wavelet-based estimator updated sequentially. In particular, each predictor $\hat{f}_t$ is parameterized by a collection of wavelet coefficients, which are learned online using the algorithms developed in Section 2.1 and Section 2.2. At each round $t$, the coefficients of the predictor $\hat{f}_t$ are updated based on the stochastic gradient $\hat{g}_t = \ell'_t(\hat{f}_t) = 2(\hat{f}_t(X_t) - Y_t)$, associated with the squared loss $\ell_t(\hat{f}_t) = (\hat{f}_t(X_t) - Y_t)^2$. This construction mirrors the stochastic online convex optimization framework analyzed in Section 2, as the goal is to control, for any comparator function $f$, the stochastic regret $R_T(f) = \sum_{t=1}^T \mathbb{E}_{t-1}[\ell_t(\hat{f}_t)] - \mathbb{E}_{t-1}[\ell_t(f)]$ that appears in (2).

Before describing our adaptive online wavelet regression procedure and deriving high-probability, noise-level-adaptive minimax rates matching recent optimal results DeVore et al. [2025], we briefly recall the necessary background on wavelet bases and Besov space approximation.

## 3.1 Besov functions and wavelets.

In the following, we provide a minimal introduction to wavelet approximation theory and Besov functions; see Appendix E for additional details. We refer the interested reader to Cohen [2003], Giné and Nickl [2021], Härdle et al. [2012] for a deeper introduction and comprehensive treatments of wavelets and Besov spaces.

**Wavelet function representation.** We consider compactly supported functions $f: \mathcal{X} \to \mathbb{R}$, $\mathcal{X} \subset \mathbb{R}^d$, $d \ge 1$. To design our algorithm, we rely on a multiscale representation of $f$ based on an orthonormal wavelet basis $\{\phi_{j_0,k}, \psi_{j,k}\}$. For a chosen starting scale $j_0 \in \mathbb{N}$, $f$ admits the decomposition

$$f = \sum_{k \in \Lambda_{j_0}} \alpha_{j_0,k} \phi_{j_0,k} + \sum_{j=j_0}^{\infty} \sum_{k \in \Lambda_j} \beta_{j,k} \psi_{j,k}. \quad (5)$$

Here, $\alpha_{j_0} = (\alpha_{j_0,k})_{k \in \Lambda_{j_0}}$ denotes the collection of scaling coefficients, with $|\Lambda_{j_0}| \le \lambda 2^{j_0 d}$, and for each $j \ge j_0$, $\beta_j = (\beta_{j,k})_{k \in \Lambda_j}$ denotes the collection of wavelet (or detail) coefficients at scale $j$, with $|\Lambda_j| \le \lambda 2^{jd}$. When
working with S-regular wavelet bases (with S sufficiently large, see Definition 2 in Appendix E), the expansion in (5) converges not only in L²(Χ) but also in L³(Χ) for p ≥ 1 (or the space of uniformly continuous functions) depending on whether f ∈ L³(Χ), p ≥ 1. This broader convergence behavior is a key reason for adopting such regular bases.

**Besov functions.** Besov spaces Bpq s constitute a classical family of function spaces indexed by three parameters: a smoothness parameter s > 0, an integrability parameter p ∈ [1, ∞], and a summability parameter q ∈ [1, ∞]. This space can be intuitively viewed as the space of functions with s > 0 derivatives in Lp(Χ), with p ≥ 1, and parameter q ≥ 1 allows for additional finer control of the regularity of the underlying functions. Besov spaces interpolate between Sobolev and Hölder spaces and are designed to capture both smooth and non-smooth behaviors in functions. There exist several equivalent definitions of Besov spaces (e.g. using differences, or interpolation theory): we refer to Giné and Nickl [2021], Härdle et al. [2012], Triebel [2006] for detailed and general background on Besov spaces. In this work, we adopt the wavelet characterization, which is particularly well suited for the analysis of our wavelet-based Algorithm 2.

Let $s > 0$ and let $\{\phi_{j_0,k}, \psi_{j,k}\}$ be an orthonormal S-regular wavelet basis with $S > s$ (see Definition 2). We introduce the set of $L^\infty$-bounded Besov functions of radius $B > 0$, smoothness $s > \frac{d}{p}$ and regularity parameters $1 \le p, q \le \infty$

$$ B_{pq}^{s}(B) = \left\{ f \in L^{\infty}(\mathcal{X}) : \|f\|_{B} := \|\alpha_{j_0}\|_{p} + \left( \sum_{j \ge j_0} 2^{-jpq(s-\frac{d}{p}+\frac{d}{2})} \|\beta_j\|_p^q \right)^{\frac{1}{q}} \le B, s > \frac{d}{p} \right\}. \quad (6) $$

**Approximation results with wavelets.** Approximation properties of wavelet expansions are by now classical and well understood; see, e.g., DeVore and Lorentz [1993], Cohen [2003], Giné and Nickl [2021] for reviews. In particular, for functions f belonging to smoothness spaces such as Besov spaces Bpq s with $s > \frac{d}{p}$ (so that $f \in L^\infty(\mathcal{X})$), one can construct an approximation $\hat{f}$ using nonlinear methods — see DeVore [1998] for an introduction on nonlinear approximation theory. For instance, the so-called best N-term approximant $\hat{f}$ in a S-regular wavelet basis ($S > s$, see Definition 2) achieves the bound $\|f - \hat{f}\|_\infty \lesssim N^{-s/d}$, where the hidden factor depends on the wavelet basis and the norm of the target function f. The precise construction of such $\hat{f}$ and justification of this rate are provided in the proof of Theorem 3 [and also appears, e.g., in Proof of Theorem 1 in Liautaud et al., 2025].

## 3.2 Algorithm: Adaptive Online Wavelet Regression

In the adversarial setting, Liautaud et al. [2025, Theorem 1] showed that using a single wavelet predictor at a fixed uniform resolution is suboptimal, yielding a regret of order $O(\sqrt{T})$ in the high-regularity regime $s \ge \frac{d}{2}$. This phenomenon also appears in the batch setting, where the optimal rate is $O(T^{-2s/(2s+d)}) < O(\frac{1}{\sqrt{T}})$. A workaround is to rely on a multiscale aggregation strategy that averages several wavelet predictors associated with different resolutions. Intuitively, this approach aims at selecting the resolution that best balances approximation and variance terms. As shown in Theorem 3, such a strategy with Algorithm 1 achieves minimax optimal rates $O(T^{-2s/(2s+d)})$ in the batch setting, where the losses are random through the noise $\epsilon_t$ in the data. Remarkably, we show that our procedure also adapts to the noise level and attains an optimal dependence on the noise in the risk bound of Theorem 3, reaching the recent noise-level aware bound [DeVore et al., 2025], for any unknown variance $\sigma$. Our procedure builds directly on ideas of Liautaud et al. [2025] and we summarize the resulting algorithm in Algorithm 2.

**Procedure.** Let $J_0 \ge 0$ be a maximum starting scale. At each time $t \ge 1$, we predict

$$ \hat{f}_t(X_t) = \sum_{e \in \mathcal{E}} w_{e,t} \hat{f}_{e,t}(X_t) \quad \text{with } w_{e,t} \ge 0, \sum_{e \in \mathcal{E}} w_{e,t} = 1, \quad (7) $$

where each $\hat{f}_{e,t}$ is a truncated wavelet estimator of type (5) at some maximum level $J \ge 0$, whose coefficients are learnt with Algorithm 1 and is associated to a triplet $e = (j_0, \alpha_{j_0,1}, \Delta) \in [J_0] \times A_{j_0} \times \mathcal{D} =: \mathcal{E}$: $j_0$ is the starting scale of the wavelet expansion; $\alpha_{j_0,1}$ are the scaling coefficients at initial time $t = 1$ at level $j_0$ and set on a discretization grid $A_{j_0} \subset [-2^{-j_0 d/2} \|f\|_\infty \|\phi\|_1; 2^{-j_0 d/2} \|f\|_\infty \|\phi\|_1]$ of precision $\epsilon_{j_0} = O(2^{-j_0 d/2}/\sqrt{T})$ and of constant size $|A_{j_0}| = O(\sqrt{T})$ for all $j_0 \in [J_0]$; and $\Delta$ is some margin clipping belonging to $\mathcal{D}$ defined in (3). The total number of experts is given by

$$ |\mathcal{E}| = (J_0 + 1) |\mathcal{D}| \prod_{j_0 \in [J_0]} |A_{j_0}| = O\left((J_0 + 1) T^{1+\frac{J_0}{2}}\right). $$

These experts are aggregated according to (7) using a subroutine that satisfies Assumption 4. The complete procedure is summarized in Algorithm 2.
**Algorithm 2:** Adaptive Online Wavelet Regression

**Input** : Bound on expected derivative $\mathbb{E}_{t-1}[\ell'_t(\hat{f}_t(X_t))] \le G, t \ge 1$, bound on Besov norm $B > 0$; set of wavelet experts $(\hat{f}_e)_{e \in \mathcal{E}}$;

**Initialize**: Diameters $(C_{j,k}) = (B2^{-jd/2})$; uniform weights $\tilde{w}_1 = (\tilde{w}_{e,1})_{e \in \mathcal{E}}$; prediction functions $(\hat{f}_{e,1})_{e \in \mathcal{E}}$ with initial scaling coefficients set on the grids $(A_{j0})_{0 \le j_0 \le J_0}$ and detail coefficients at zero;

1 **for** $t=1$ **to** $T$ **do**

2 Receive $X_t$ and predict $\hat{f}_t(X_t) = \sum_{e \in \mathcal{E}} w_{e,t} \hat{f}_{e,t}(x_t)$;

3 Reveal gradient $\hat{\nabla}_t = \nabla_{w_t} \ell_t(\sum_{e \in \mathcal{E}} w_{e,t} \hat{f}_{e,t}(x_t))$;

4 Update $w_{t+1} \leftarrow \text{weight}(w_t, \hat{\nabla}_t)$ with weight satisfying Assumption 4;

5 **for** $e \in \mathcal{E}$ **do**

6 Reveal gradient $\hat{g}_{e,t} = (g_{j,k,t})$ of coefficients in $\hat{f}_{e,t}$ as in (8);

7 Update coefficients $(c_{j,k,t})$ of $\hat{f}_{e,t}$ using Algorithm 1 with input $\hat{g}_{e,t}$, expected gradient bounds $(G_{j,k,t}) = G \cdot (|\varphi_{j,k}(X_t)|)$, diameters $(C_{j,k})$ and margin clipping $\Delta_e$;

**Output** : $(\hat{f}_t)_{1 \le t \le T}$

**Boundedness of predictors: choice of the diameters $(C_{j,k})$ and grids $(A_{j0})$**. A key ingredient of our analysis is that all predictors remain uniformly bounded at every time step and we explain how this boundedness is enforced through an appropriate choice of coefficient constraints. For the coarse (scaling) coefficients, one has for all $k \in \bar{\Lambda}_{j0}$, $|\alpha_{j0,k}| \le 2^{-j_0 \frac{d}{2}} \|\phi\|_1 \|f\|_{\infty}$, which allows us to construct the corresponding finite grids $A_{j0}$. For the wavelet coefficients, assuming a bound $B > 0$ on the Besov norm $\|f\|_B$, the definition of the Besov norm (6) yields, for all $j, k$, since $s > \frac{d}{p}$

$$|\beta_{j,k}| \le B 2^{-j(s-\frac{d}{p}+\frac{d}{2})} \le B 2^{-j\frac{d}{2}} =: C_{j,k}.$$

Constraining the wavelet coefficients to lie in $[-C_{j,k}, C_{j,k}]$ at all times ensures that the associated predictors $\hat{f}_{e,t}$ remain uniformly bounded in sup-norm, for all experts $e$ and all $t$, as shown in Lemma 4. This uniform-in-time boundedness is essential for controlling stochastic fluctuations via concentration inequalities in the high-probability regret analysis (see, e.g., the analysis in Section 2). Finally, we emphasize that the choice of the diameters $(C_{j,k})$ does not require prior knowledge of the smoothness parameter $s$ nor of the integrability parameters $(p, q)$. This adaptivity is achieved at the cost of an additional $O(\log T)$ factor in the bound.

**Computation of gradients and computational complexity.** Denoting by $\partial_e$ the partial derivative with respect to $c$, the gradients with respect to the wavelet coefficients are obtained by the chain rule

$$\hat{g}_{j,k,t} = \left[ \partial_e \ell_t \left( \hat{f}_t(X_t) - c_{j,k,t} \varphi_{j,k}(X_t) + c \varphi_{j,k}(X_t) \right) \right]_{c=c_{j,k,t}} = \ell'_t(\hat{f}_t(X_t)) \varphi_{j,k}(X_t), \quad (8)$$

where $\ell'_t(\hat{f}_t(X_t)) = 2(\hat{f}_t(X_t) - Y_t)$ is the derivative of the squared loss $\ell_t(\hat{Y}) = (\hat{Y} - Y_t)^2$. In particular, for every $t \ge 1$, $\mathbb{E}_{t-1}[\ell'_t(\hat{f}_t(X_t))] = 2\mathbb{E}_{t-1}[\hat{f}_t(X_t) - f(X_t) - \varepsilon_t] \le 2(\|\hat{f}_t\|_{\infty} + \|f\|_{\infty})$, where we used $\mathbb{E}_{t-1}[\varepsilon_t] = 0$ and the Lipschitz parameter required by Algorithm 1 can be set to $G = 2(\|\hat{f}_t\|_{\infty} + \|f\|_{\infty})$. Although the number of wavelet coefficients is potentially large (of order $O(2^{jd})$ at level $j$), the optimization procedure is sparse. At each time $t$, the gradient in (8) vanishes whenever $\varphi_{j,k}(X_t) = 0$. Since wavelet basis functions are compactly supported, only a small number of coefficients are active at any given location $X_t$, and the sparsity pattern—being entirely determined by $X_t$—is known deterministically. As a result, updates and clipping are performed only on active coordinates, ensuring computational efficiency; see Liautaud et al. [2025] for detailed discussion on the complexity.

**Third result: optimal noise level-aware risk bound in high probability.** We now state our main non-parametric result, establishing a high-probability nearly minimax-optimal risk bound that is adaptive to the unknown noise level.

**Theorem 3.** Let $T \ge 1$, $B > 0$, $\delta \in (0, 1)$, and assume $s - \frac{d}{p} \ge \kappa > 0$ and $\sigma \ge \sigma_0 > 0$. Let $(\hat{f}_e)_{e \in \mathcal{E}}$ be a collection of $S$-regular wavelet predictors with $S > s$ and maximum scale $J = \frac{S}{(2S+d)\kappa} \log(TB^2\sigma_0^{-2})$. After $T$ rounds, Algorithm 2 run with bounds $B$ and $G = 2(\hat{B}_\infty + B_\infty)$ as defined in Lemma 4, produces a sequence of predictors $(\hat{f}_t)_{1 \le t \le T}$. Setting $\bar{f}_T = \frac{1}{T} \sum_{t=1}^T \hat{f}_t$ we have that for any $f \in B_{pq}^s(B)$, the following guarantee holds with probability $1 - 4\delta$

$$\|\bar{f}_T - f\|_2^2 \le O\left( \|f\|_B^{\frac{2d}{2s+d}} (\sigma^2)^{\frac{2s}{2s+d}} T^{-\frac{2s}{2s+d}} + B^2 \frac{\log^2 T}{T} \log(\delta^{-1}) \right).$$
We postpone the proof of Theorem 3 to Appendix C. Remarkably, beyond its adaptivity to the unknown noise level, our algorithm achieves risk guarantees that match the minimax-optimal noise-level-aware rates recently derived in the batch setting by DeVore et al. [2025], who provide an explicit algorithm under knowledge of $(s, p, q, \sigma)$. Remark also that the main term scales with the true Besov norm of the function $\|f\|_B$. Finally, the bound matches the optimal rate $\tilde{O}(T^{-2s/(2s+d)})$, up to an additional $O(T^{-1 \log^2 T})$ term that reflects the cost of adaptivity induced by the aggregation procedure. Interestingly, the rates obtained in Theorem 3 can be compared with known bounds in online nonparametric regression. For the squared loss, Rakhlin and Sridharan [2014] established minimax-optimal regret rates in the adversarial setting. When $s \ge \frac{d}{2}$, the average regret satisfies $\frac{RT}{2} = O(T^{-2s/(2s+d)})$, matching the i.i.d. minimax risk rate. However, when $s < \frac{d}{2}$, the regret deteriorates to $\frac{RT}{2} = O(T^{-s/d})$, which is strictly slower than the optimal batch rate $O(T^{-2s/(2s+d)})$; see also Rakhlin et al. [2017] for a discussion of the gap between minimax risk and minimax regret. This distinction highlights a key difficulty in online-to-batch conversion: even when resorting to an optimal algorithm for the online setting, such as that of Liautaud et al. [2025], deriving optimal risk bounds (also in expectation) via a classical online-to-batch argument is nontrivial in the low-regularity regime $s < \frac{d}{2}$, where the minimax i.i.d. rate remains $O(T^{-2s/2s+d})$. Achieving optimal high-probability risk guarantees therefore requires a careful analysis that goes beyond standard online-to-batch techniques.

# 4 Conclusion

We proposed a sequential wavelet-based algorithm that achieves minimax-optimal integrated squared error bounds with high probability, while adapting to the unknown noise level through a refined online-to-batch conversion. Our analysis also yields new high-probability, comparator-adaptive regret guarantees with $l_1$-norm dependence. Several directions remain open. In particular, it would be of interest to extend our results to $L^{p'}$ risks for $p' \ge 1$ and to investigate whether the proposed approach recovers optimal noiseless recovery rates when $\sigma = 0$, as characterized in the recent work of DeVore et al. [2025].

# References

* Bernard Bercu and Abderrahmen Touati. Exponential inequalities for self-normalized martingales with applications. 2008.

* Nicolo Cesa-Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of on-line learning algorithms. *IEEE Transactions on Information Theory*, 50(9):2050–2057, 2004.

* Liyu Chen, Haipeng Luo, and Chen-Yu Wei. Impossible tuning made possible: A new expert algorithm and its applications. In *Conference on Learning Theory*, pages 1216–1259. PMLR, 2021.

* Albert Cohen. *Numerical analysis of wavelet methods*, volume 32. Elsevier, 2003.

* Ashok Cutkosky and Kwabena Boahen. Online learning without prior information. In *Conference on learning theory*, pages 643–677. PMLR, 2017.

* Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in banach spaces. In *Conference On Learning Theory*, pages 1493–1529. PMLR, 2018.

* Bernard Delyon and Anatoli Juditsky. On minimax wavelet estimators. *Applied and Computational Harmonic Analysis*, 3(3):215–228, 1996.

* Ronald DeVore, Robert D Nowak, Rahul Parhi, Guergana Petrova, and Jonathan W Siegel. Optimal recovery meets minimax estimation. *arXiv preprint arXiv:2502.17671*, 2025.

* Ronald A DeVore. Nonlinear approximation. *Acta numerica*, 7:51–150, 1998.

* Ronald A DeVore and George G Lorentz. *Constructive approximation*, volume 303. Springer Science & Business Media, 1993.

* David L Donoho and Iain M Johnstone. Minimax estimation via wavelet shrinkage. *The annals of Statistics*, 26(3):879–921, 1998.

* Pierre Gaillard, Gilles Stoltz, and Tim Van Erven. A second-order bound with excess losses. In *Conference on Learning Theory*, pages 176–196. PMLR, 2014.

* Evarist Giné and Richard Nickl. *Mathematical foundations of infinite-dimensional statistical models*. Cambridge university press, 2021.
Wolfgang Härdle, Gerard Kerkyacharian, Dominique Picard, and Alexander Tsybakov. *Wavelets, approximation, and statistical applications*, volume 129. Springer Science & Business Media, 2012.

Elad Hazan et al. Introduction to online convex optimization. *Foundations and Trends® in Optimization*, 2 (3-4):157–325, 2016.

Andrew Jacobsen and Ashok Cutkosky. Parameter-free mirror descent. In *Conference on Learning Theory*, pages 4160–4211. PMLR, 2022.

Kwang-Sung Jun and Francesco Orabona. Parameter-free online convex optimization with sub-exponential noise. In *Conference on learning theory*, pages 1802–1823. PMLR, 2019.

Wouter M Koolen and Tim Van Erven. Second-order quantile methods for experts and combinatorial games. In *Conference on Learning Theory*, pages 1155–1175. PMLR, 2015.

Paul Liautaud, Pierre Gaillard, and Olivier Wintenberger. Minimax adaptive online nonparametric regression over besov spaces. *arXiv preprint arXiv:2505.19741*, 2025.

Nick Littlestone. From on-line to batch learning. In *Proceedings of the second annual workshop on Computational learning theory*, pages 269–284, 1989.

Zakaria Mhammedi and Wouter M Koolen. Lipschitz and comparator-norm adaptivity in online learning. In *Conference on Learning Theory*, pages 2858–2887. PMLR, 2020.

Zakaria Mhammedi, Wouter M Koolen, and Tim Van Erven. Lipschitz adaptivity with multiple learning rates in online learning. In *Conference on Learning Theory*, pages 2490–2511. PMLR, 2019.

Francesco Orabona and Dávid Pál. Coin betting and parameter-free online learning. *Advances in Neural Information Processing Systems*, 29, 2016.

Alexander Rakhlin and Karthik Sridharan. Online non-parametric regression. In *Conference on Learning Theory*, pages 1232–1264. PMLR, 2014.

Alexander Rakhlin, Karthik Sridharan, and Alexandre B Tsybakov. Empirical entropy, minimax regret and minimax risk. 2017.

Shai Shalev-Shwartz. Online learning and online convex optimization. *Foundations and Trends® in Machine Learning*, 4(2):107–194, 2025.

Hans Triebel. *Theory of Function Spaces*. Birkhäuser, 2006.

Dirk van der Hoeven, Nikita Zhivotovskiy, and Nicolò Cesa-Bianchi. High-probability risk bounds via sequential predictors. *arXiv preprint arXiv:2308.07588*, 2023.

Olivier Wintenberger. Optimal learning with bernstein online aggregation. *Machine Learning*, 106(1):119–141, 2017.

Olivier Wintenberger. Stochastic online convex optimization. application to probabilistic time series forecasting. *Electronic Journal of Statistics*, 18(1):429–464, 2024.

Jiujia Zhang and Ashok Cutkosky. Parameter-free regret in high probability with heavy tails. *Advances in Neural Information Processing Systems*, 35:8000–8012, 2022.
# APPENDIX

## Contents

<table><tr><td>1</td><td>Introduction</td><td>1</td></tr><tr><td>1.1</td><td>Related work</td><td>3</td></tr><tr><td>2</td><td>High probability comparator-adaptive regret with constrained iterates and noisy unbounded gradients</td><td>3</td></tr><tr><td>2.1</td><td>Algorithm: Adaptive Learning with Unbounded Noisy Gradients via Clipping</td><td>4</td></tr><tr><td>2.2</td><td>Adaptive clipping strategy</td><td>5</td></tr><tr><td>3</td><td>High-Probability Regression over Besov Spaces via Online-to-Batch</td><td>7</td></tr><tr><td>3.1</td><td>Besov functions and wavelets.</td><td>7</td></tr><tr><td>3.2</td><td>Algorithm: Adaptive Online Wavelet Regression</td><td>8</td></tr><tr><td>4</td><td>Conclusion</td><td>10</td></tr><tr><td>A</td><td>Proof of Theorem 1</td><td>13</td></tr><tr><td>B</td><td>Proof of Theorem 2</td><td>16</td></tr><tr><td>C</td><td>Proof of Theorem 3</td><td>20</td></tr><tr><td>D</td><td>Technical lemmas</td><td>26</td></tr><tr><td>E</td><td>Review of multi-resolution analysis</td><td>28</td></tr></table>
A Proof of Theorem 1

**Theorem 4 (High-probability parameter-free regret).** Let $N \in \mathbb{N}^*$, $C_1, \dots, C_N > 0$ and $\delta \in (0, 1)$. Assume we are given noisy gradients $\hat{g}_1, \dots, \hat{g}_T \in \mathbb{R}^N$ such that, for all $t \ge 1$, the gradient noise satisfies Assumption 1 with parameters $\nu, \mu > 0$, and

$$|\mathbb{E}_{t-1}[\hat{g}_{n,t}]| \le G_{n,t}, n \in [N] \quad \text{and} \quad \max_{1 \le n \le N} \mathbb{E}_{t-1}[|\hat{g}_{n,t} - \mathbb{E}_{t-1}[\hat{g}_{n,t}]|^2] \le \sigma^2.$$

Then Algorithm 1, run with diameters ($C_n$), gradients bounds ($G_{n,t}$) and clipping margin

$$\Delta_t = \max \left\{ \nu \sqrt{2 \log \left( \frac{(\sqrt{0.5\pi} + 2\mu)t}{\log(\delta^{-1})} \right)}, 2\mu \log \left( \frac{(\sqrt{0.5\pi} + 2\mu)t}{\log(\delta^{-1})} \right) \right\}$$

satisfies, with probability at least $1 - 2\delta$, for all comparators $c \in \mathbb{R}^N$ such that $|c_n| \le C_n, n \in [N]$,

$$R_T(c) \le O \left[ \sum_{n=1}^{N} |c_n| \left( \Xi_1 \sqrt{\sum_{t=1}^{T} \mathbb{E}_{t-1}[|\hat{g}_{n,t}|^2]} + (\Xi_1 \sqrt{\log(\delta^{-1})} + \Xi_2) \left( \sup_{1 \le t \le T} G_{n,t} + \max(\nu, \mu) \log T \right) \right) \right. \\ \left. + \left( \frac{1}{\alpha} + \left( \sup_{1 \le t \le T} \sum_{n=1}^{N} C_n (G_{n,t} + \max(\nu, \mu) \log T) 1_{G_{n,t}>0} \right)^2 \right) \log(\delta^{-1}) \right],$$

where the notation $O[\cdot]$ hides multiplicative constants and $\log \log(\delta^{-1})$ terms.

**Proof.** Recall $\nabla L_t(c_t) = \mathbb{E}_{t-1}[\hat{g}_t]$ where we denote $\hat{g}_t = (\hat{g}_{n,t})_{1 \le n \le N} = \nabla \ell_t(c_t)$ the noisy observed gradient and $\bar{g}_t = (\text{clip}(\hat{g}_{n,t}, \bar{G}_{n,t}))_{1 \le n \le N}$ the clipped version of $\hat{g}_t$ at time $t$. We set $Z_t = \hat{g}_t^\top(c_t - c)$ and $\bar{Z}_t = \bar{g}_t^\top(c_t - c)$ and one has by stochastic $\alpha$-exp-concavity

$$\sum_{t=1}^{T} L_t(c_t) - L_t(c) \le \sum_{t=1}^{T} \mathbb{E}_{t-1}[Z_t] - \frac{\alpha}{2} \mathbb{E}_{t-1}[Z_t^2] \\ \le \underbrace{\sum_{t=1}^{T} \mathbb{E}_{t-1}[Z_t - \bar{Z}_t]}_{\text{clipping bias}} + \underbrace{\sum_{t=1}^{T} \mathbb{E}_{t-1}[\bar{Z}_t] - \frac{\alpha}{2} \mathbb{E}_{t-1}[\bar{Z}_t^2]}_{\text{stochastic regret}} \quad (9)$$

since $|\bar{Z}_t| \le |Z_t|, t \ge 1$.

**Bound on the stochastic regret.** For every $t \ge 1$,

$$\sum_{n=1}^{N} |\bar{g}_{n,t}| |c_{n,t} - c_n| \le 2 \sum_{n=1}^{N} \bar{G}_{n,t} C_n \le 2 \sup_{1 \le t \le T} \sum_{n=1}^{N} \bar{G}_{n,t} C_n =: D.$$

Then, by the second inequality of Lemma 3, with $|\bar{Z}_t| \le D, t \ge 1$ one has for every $\gamma > 0$, with probability $1 - 2\delta$

$$\sum_{t=1}^{T} \mathbb{E}_{t-1}[\bar{Z}_t] \le \sum_{t=1}^{T} \bar{Z}_t + \frac{3\gamma}{2} \mathbb{E}_{t-1}[\bar{Z}_t^2] + \left(2D^2 + \frac{2}{\gamma}\right) \log(\delta^{-1}).$$

Taking $\gamma = \frac{\alpha}{3} > 0$ cancels the second order terms and we have a stochastic regret bounded as

$$\sum_{t=1}^{T} \mathbb{E}_{t-1}[\bar{Z}_t] - \frac{\alpha}{2} \mathbb{E}_{t-1}[\bar{Z}_t^2] \le \sum_{t=1}^{T} \bar{Z}_t + \left(2D^2 + \frac{6}{\alpha}\right) \log(\delta^{-1}) \quad (10)$$

with probability $1 - 2\delta$. The problem is now reduced to bound the linear term $\sum_{t=1}^{T} \bar{Z}_t = \sum_{t=1}^{T} \bar{g}_t^\top(c_t - c)$ and one has

$$\sum_{t=1}^{T} \bar{g}_t^\top(c_t - c) = \sum_{n=1}^{N} \sum_{t=1}^{T} \bar{g}_{n,t} (c_{n,t} - c_n) \le \sum_{n=1}^{N} |c_n| \left( \Xi_1 \sqrt{\sum_{t=1}^{T} |\bar{g}_{n,t}|^2} + \Xi_2 \bar{G}_n \right) \\ \le \sum_{n=1}^{N} |c_n| \left( \Xi_1 \sqrt{\sum_{t=1}^{T} 2\mathbb{E}_{t-1}[|\bar{g}_{n,t}|^2]} + 2\bar{G}_n^2 \log(\delta^{-1}) + \Xi_2 \bar{G}_n \right) \quad (11)$$

where first inequality is by Assumption 3 on iterates $(c_{n,t})$ and gradients $(\bar{g}_{n,t})$ with $|\bar{g}_{n,t}| \le \bar{G}_n := \sup_{1 \le t \le T} \bar{G}_{n,t}$; and last inequality holds with probability $1 - \delta$, applying Lemma 2 on $(|\bar{g}_{n,t}|^2 - 2\mathbb{E}_{t-1}[|\bar{g}_{n,t}|^2])/(2\bar{G}_n^2)$.
**Bound on the clipping bias.** For every $t \ge 1$ one has for every coordinate $n \in [N]$, $g_{n,t} = \mathbb{E}_{t-1}[\hat{g}_{n,t}]$, $|g_{n,t}| \le G_{n,t}$ and

$$|\hat{g}_{n,t} - \bar{g}_{n,t}| = (|\hat{g}_{n,t}| - \bar{G}_{n,t})_+ \le (|\hat{g}_{n,t} - g_{n,t}| + |g_{n,t}| - \bar{G}_{n,t})_+ \le (|\hat{g}_{n,t} - g_{n,t}| - (\bar{G}_{n,t} - G_{n,t}))_+.$$

Then, one has for every $n \in [N]$ with $\xi_{n,t} = \hat{g}_{n,t} - g_{n,t}$, $\Delta_{n,t} = \bar{G}_{n,t} - G_{n,t}$ and using Assumption 1, we have when $G_{n,t} > 0$ (else gradients are null and we take $\bar{G}_{n,t} = G_{n,t}$):

$$ \begin{aligned} \mathbb{E}_{t-1}[|\xi_{n,t}|] &\le \int_{\Delta_{n,t}}^{\infty} \mathbb{P}_{t-1}(|\xi_{n,t}| \ge u) \, du \\ &\le \int_{\Delta_{n,t}}^{\infty} \exp\left(-\frac{1}{2} \min\left(\frac{u^2}{\nu^2}, \frac{u}{\mu}\right)\right) \, du \\ &= \int_{\Delta_{n,t}}^{\frac{\nu^2}{\mu}} \exp\left(-\frac{u^2}{2\nu^2}\right) \, du + \int_{\Delta_{n,t}}^{\infty} \exp\left(-\frac{u}{2\mu}\right) \, du \\ &\le \sqrt{\frac{\pi}{2}} \nu \exp\left(-\frac{\Delta_{n,t}^2}{2\nu^2}\right) + 2\mu \exp\left(-\frac{\Delta_{n,t}}{2\mu}\right) \\ &\le C(\nu, \mu) \exp\left(-\frac{1}{2} \min\left(\frac{\Delta_{n,t}^2}{\nu^2}, \frac{\Delta_{n,t}}{\mu}\right)\right), \end{aligned} \quad (12) $$

where $C(\nu, \mu) = \sqrt{0.5\pi\nu} + 2\mu$. Thus, the clipping bias term is bounded, with $|c_{n,t} - c_n| \le 2C_n, n \in [N]$, as

$$ \begin{aligned} \sum_{t=1}^{T} \mathbb{E}_{t-1}[\hat{\mathbf{g}}_t - \bar{\mathbf{g}}_t]^\top (\mathbf{c}_t - \mathbf{c}) &\le \sum_{t=1}^{T} \sum_{n=1}^{N} 2C_n \mathbb{E}_{t-1}[|\hat{g}_{n,t} - \bar{g}_{n,t}|] \\ &\le 2 \sum_{(12)}^{N} \sum_{n=1}^{T} C_n C(\nu, \mu) \exp\left(-\frac{1}{2} \min\left(\frac{\Delta_{n,t}^2}{\nu^2}, \frac{\Delta_{n,t}}{\mu}\right)\right). \end{aligned} \quad (13) $$

**Conclusion.** Using a union bound, we finally get with probability at least $1 - 3\delta$, using (9), (10), (11), (13)

$$ \begin{aligned} R_T(\mathbf{c}) &\le \sum_{n=1}^{N} |c_n| \left( \Xi_1 \left( \sqrt{2 \sum_{t=1}^{T} \mathbb{E}_{t-1}[|\hat{g}_{n,t}|^2]} + \sqrt{2 \bar{G}_n^2 \log(\delta^{-1})} \right) + \Xi_2 \sup_{1 \le t \le T} (G_{n,t} + \Delta_{n,t}) \right) \\ &\quad + 2 \sum_{n=1}^{N} \sum_{t=1}^{T} C_n C(\nu, \mu) \exp \left( -\frac{1}{2} \min \left( \frac{\Delta_{n,t}^2}{\nu^2}, \frac{\Delta_{n,t}}{\mu} \right) \right) \\ &\quad + 8 \left( \sup_{1 \le t \le T} \sum_{n=1}^{N} C_n (G_{n,t} + \Delta_{n,t} \mathbb{1}_{G_{n,t}>0}) \right)^2 \log(\delta^{-1}) + \frac{6}{\alpha} \log(\delta^{-1}). \end{aligned} \quad (14) $$

By setting the clipping margin $\Delta_{n,t} = \max(\nu\sqrt{2L_t}, 2\mu L_t)$ with time-dependent $L_t = \log\left(\frac{tC(\nu,\mu)}{\log(\delta^{-1})}\right)$, the exponential term simplifies as follows:

$$ \begin{aligned} \sum_{t=1}^{T} C(\nu, \mu) \exp\left(-\frac{1}{2} \min\left(\frac{\Delta_{n,t}^2}{\nu^2}, \frac{\Delta_{n,t}}{\mu}\right)\right) &= \sum_{t=1}^{T} C(\nu, \mu) e^{-L_t} \\ &= \sum_{t=1}^{T} C(\nu, \mu) \frac{\log(\delta^{-1})}{tC(\nu, \mu)} \\ &= \log(\delta^{-1}) \sum_{t=1}^{T} \frac{1}{t} \\ &\le \log(\delta^{-1}) (\log(T) + 1). \end{aligned} $$

Finally from (14) we get

$$ \begin{aligned} R_T(\mathbf{c}) &\le \sum_{n=1}^{N} |c_n| \left( \Xi_1 \sqrt{2 \sum_{t=1}^{T} \mathbb{E}_{t-1}[|\hat{g}_{n,t}|^2]} + (\Xi_1 \sqrt{2 \log(\delta^{-1})} + \Xi_2)(G_n + \Delta) \right) \\ &\quad + 2 \left[ \sup_{1 \le t \le T} \sum_{n=1}^{N} C_n(\log(T) + 1) \mathbb{1}_{G_{n,t}>0} + 4 \left( \sup_{1 \le t \le T} \sum_{n=1}^{N} C_n(G_{n,t} + \Delta \mathbb{1}_{G_{n,t}>0}) \right)^2 + \frac{3}{\alpha} \right] \log(\delta^{-1}) \end{aligned} \quad (15) $$
where $\Delta := \sup_{1 \le t \le T} \Delta_{n,t} = \max \left\{ \nu \sqrt{2 \log \left( \frac{TC(\nu,\mu)}{\log(\delta^{-1})} \right)}, 2\mu \log \left( \frac{TC(\nu,\mu)}{\log(\delta^{-1})} \right) \right\} \le O(\max(\nu, \mu) \log(T))$ and this completes the proof of Theorem 4. Theorem 1 is obtained by setting $C_1 = \dots = C_N = C$ and $G_{1,t} = \dots = G_{N,t} = G, t \ge 1$ and because for every $t \ge 1$, one has under the square root, with $g_{n,t} = \mathbb{E}_{t-1}[\hat{g}_{n,t}]$ and $|g_{n,t}| \le G$

$$ \begin{aligned} \mathbb{E}_{t-1}[|\hat{g}_{n,t}|^2] &\le \mathbb{E}_{t-1}[(|\hat{g}_{n,t} - g_{n,t}| + |g_{n,t}|)^2] \\ &\le \mathbb{E}_{t-1}[|\hat{g}_{n,t} - g_{n,t}|^2] + \mathbb{E}_{t-1}[|g_{n,t}|^2] \\ &\le \sigma^2 + G^2. \end{aligned} $$

□
## B Proof of Theorem 2

We restate and prove below a complete version of Theorem 2. We consider the general case with a coordinate- and time-dependent clipping rule where we have different expected gradient bounds $G_t := (G_{n,t})_{1 \le n \le N}$ at each time $t \ge 1$.

**Theorem 5.** Let $T, N \ge 1$, $(C_n) > 0$ and $\delta \in (0, 1)$. Assume $(\ell_t)_{t \ge 1}$ satisfy Assumption 2 and for every $t \ge 1$, $c \in \mathbb{R}^N$, $\|c\|_{\infty} \le C$, $\nabla \ell_t(c)$ satisfies Assumption 1 and

$$|\mathbb{E}_{t-1}[\nabla \ell_t(c)_n]| \le G_{n,t}, n \in [N] \quad \text{and} \quad \max_{1 \le n \le N} |\mathbb{E}_{t-1}[|\nabla \ell_t(c)_n - \mathbb{E}_{t-1}[\nabla \ell_t(c)_n]|^2] \le \sigma^2.$$

With sequential predictions $\hat{c}_t = \sum_{\Delta \in \mathcal{D}} w_t^\Delta c_t^\Delta$, $t \ge 1$ as in (4) with $(w_t^\Delta)_{\Delta \in \mathcal{D}}$ satisfying Assumption 4, the regret is bounded with probability $1 - 6\delta$ and for any $c \in \mathbb{R}^N$, $|c_n| \le C_n$, as

$$\sum_{t=1}^{T} L_t(\hat{c}_t) - L_t(c) \le O\left[ \sum_{n=1}^{N} |c_n| \left( \Xi_1 \sqrt{\sum_{t=1}^{T} \mathbb{E}_{t-1}[|\hat{g}_{n,t}|^2]} + \left( \Xi_1 \sqrt{\log(\delta^{-1})} + \Xi_2 \right) \left( \sup_{1 \le t \le T} G_{n,t} + \mu \log T \right) \right. \right. \\
+ \left( \frac{\Xi_3^2}{\alpha} + \Xi_4 \sum_{n=1}^{N} C_n \left( \sup_{1 \le t \le T} G_{n,t} + 2\mu \log(TN) \mathbb{1}_{G_{n,t}>0} \right) \log(\sqrt{T} + 1) \right. \\
\left. + \left( (\alpha+1) \sup_{1 \le t \le T} \left( \sum_{n=1}^{N} C_n \left( G_{n,t} + 2\mu \log(TN) \mathbb{1}_{G_{n,t}>0} \right) \right)^2 + \frac{1}{\alpha} \right) \log(\delta^{-1}) \right],$$

where the notation $O[\cdot]$ hides multiplicative constants.

**of Theorem 5.** At each time $t \ge 1$, $c_t^\Delta \in \mathbb{R}^N$ is the output of Algorithm 1 with clipping margins $\Delta_t = \Delta$, $t \ge 1$ and $\hat{c}_t = \sum_{\Delta \in \mathcal{D}} w_t^\Delta c_t^\Delta$ is the average prediction over $\mathcal{D}$. One can decompose the regret, for every $\Delta^* \in \mathcal{D}$, as

$$\sum_{t=1}^{T} L_t \left( \sum_{\Delta \in \mathcal{D}} w_t^\Delta c_t^\Delta \right) - L_t(c) = \underbrace{\sum_{t=1}^{T} L_t(\hat{c}_t) - L_t(c_{\hat{c}_t}^*)}_{\text{expert aggregation regret}} + \underbrace{\sum_{t=1}^{T} L_t(c_{\hat{c}_t}^*) - L_t(c)}_{\text{regret of Alg. 1 with } \Delta^* := R_T(c)}.$$

**Expert aggregation regret.** Define $w_t = (w_t^\Delta)_{\Delta \in \mathcal{D}}$ and one has

$$\hat{\nabla}_t = \nabla_{w_t} \ell_t \left( \sum_{\Delta \in \mathcal{D}} w_t^\Delta c_t^\Delta \right) = (\hat{g}_t^\top c_t^\Delta)_{\Delta \in \mathcal{D}}$$

where in this part we denote $\hat{g}_t = \nabla \ell_t(\hat{c}_t) \in \mathbb{R}^N$ the gradient of $\ell_t$ evaluated at $\hat{c}_t$, which satisfies Assumption 1 and $\mathbb{E}_{t-1}[\nabla \ell_t(\hat{c}_t)_n] \le G_{n,t}$. Therefore, denoting $\hat{\nabla}_t = (\hat{\nabla}_t^\Delta)_{\Delta \in \mathcal{D}}$ and letting $Z_t = \hat{\nabla}_t^\top w_t - \hat{\nabla}_t^{\Delta^*}$, by Assumption 2 one has

$$\sum_{t=1}^{T} L_t \left( \sum_{\Delta \in \mathcal{D}} w_t^\Delta c_t^\Delta \right) - L_t(c_{\hat{c}_t}^*) \le \sum_{t=1}^{T} \mathbb{E}_{t-1}[Z_t] - \frac{\alpha}{2} \mathbb{E}_{t-1}[Z_t^2] \\
\le \sum_{t=1}^{T} Z_t + \frac{\gamma}{2} Z_t^2 + \frac{\gamma - \alpha}{2} \mathbb{E}_{t-1}[Z_t^2] + \frac{2}{\gamma} \log(\delta^{-1}) \quad (16)$$

where last inequality holds with high probability $1 - \delta$ for any $\gamma > 0$ by Lemma 3. Moreover, one can bound the first order term by Assumption 4 with $Z_t = \hat{\nabla}_t^\top w_t - \hat{\nabla}_t^{\Delta^*}$

$$\sum_{t=1}^{T} Z_t \le \Xi_3 \sqrt{\log(|\mathcal{D}|) \sum_{t=1}^{T} Z_t^2 + \Xi_4 \log(|\mathcal{D}|)} \sup_{1 \le t \le T} \|\hat{\nabla}_t\|_{\infty}.$$

Further, by Young's inequality, we have for every $\eta > 0$

$$\Xi_3 \sqrt{\log(|\mathcal{D}|) \sum_{t=1}^{T} Z_t^2} \le \frac{\Xi_3^2 \log(|\mathcal{D}|)}{2\eta} + \frac{\eta}{2} \sum_{t=1}^{T} Z_t^2.$$

And in bound (16) we have

$$\sum_{t=1}^{T} Z_t + \frac{\gamma}{2} Z_t^2 \le \frac{\Xi_3^2 \log(|\mathcal{D}|)}{2\eta} + \frac{\eta + \gamma}{2} \sum_{t=1}^{T} Z_t^2 + \Xi_4 \log(|\mathcal{D}|) \sup_{1 \le t \le T} \|\hat{\nabla}_t\|_{\infty}. \quad (17)$$
Now we want to relate $\sum_{t=1}^T Z_t^2$ to its clipped version using the fact that $\hat{g}_t$ has coordinate with sub-exponential noise (Assumption 1). Indeed, remark that for every $t \ge 1$

$$Z_t = \hat{\nabla}_t^\top w_t - \hat{\nabla}_t^{\bar{G}^*} = \sum_{\Delta \in \mathcal{D}} \sum_{n=1}^N \hat{g}_{n,t} c_{n,t}^\Delta w_t^\Delta - \sum_{n=1}^N \hat{g}_{n,t} c_{n,t}^\Delta = \sum_{n=1}^N \hat{g}_{n,t} \left( \sum_{\Delta \in \mathcal{D}} w_t^\Delta c_{n,t}^\Delta - c_{n,t}^{\Delta^*} \right)$$

is still sub-exponential as a sum of sub-exponential random variables $\hat{g}_{n,t}$. We define a clipped version of $Z_t, \bar{Z}_t = \sum_{n=1}^N \bar{g}_{n,t} \left( \sum_{\Delta \in \mathcal{D}} w_t^\Delta c_{n,t}^\Delta - c_{n,t}^{\Delta^*} \right)$ where $\bar{g}_{n,t} = \text{clip}(\hat{g}_{n,t}, \tau_{n,t})$, $n \in [N]$ for some $\tau_{n,t} > 0$ to be optimized in the proof and that only appears in the analysis. Then, we have

$$\sum_{t=1}^{T} Z_t^2 = \sum_{t=1}^{T} \bar{Z}_t^2 \qquad (18)$$

with probability $P(\forall 1 \le t \le T, Z_t = \bar{Z}_t)$. By the union bound,

$$P(\forall 1 \le t \le T, Z_t = \bar{Z}_t) = 1 - P(\exists 1 \le t \le T : Z_t \ne \bar{Z}_t) \ge 1 - \sum_{t=1}^{T} P_{t-1}(Z_t \ne \bar{Z}_t).$$

In particular, for every $t \ge 1$,

$$\begin{aligned} P_{t-1}(Z_t \neq \bar{Z}_t) &= P_{t-1} \left( \sum_{n=1}^{N} \hat{g}_{n,t} \left( \sum_{\nu} w_t^{\nu} c_{n,t}^{\nu} - c_{n,t}^{\bar{G}^*} \right) \neq \sum_{n=1}^{N} \bar{g}_{n,t} \left( \sum_{\nu} w_t^{\nu} c_{n,t}^{\nu} - c_{n,t}^{\bar{G}^*} \right) \right) \\ &\le \sum_{n=1}^{N} P_{t-1} \left( \hat{g}_{n,t} \left( \sum_{\nu} w_t^{\nu} c_{n,t}^{\nu} - c_{n,t}^{\bar{G}^*} \right) \neq \bar{g}_{n,t} \left( \sum_{\nu} w_t^{\nu} c_{n,t}^{\nu} - c_{n,t}^{\bar{G}^*} \right) \right) \\ &= \sum_{n=1}^{N} P_{t-1}(\hat{g}_{n,t} \neq \bar{g}_{n,t}) \\ &= \sum_{n=1}^{N} P_{t-1}(|\hat{g}_{n,t}| > \tau_{n,t}) \\ &\le \sum_{n=1}^{N} P_{t-1}(|\hat{g}_{n,t} - \mathbb{E}_{t-1}[\hat{g}_{n,t}]| > \tau_{n,t} - G_{n,t}) \\ &\le \sum_{n=1}^{N} C(\nu, \mu) \exp \left( -\frac{1}{2} \min \left( \frac{(\tau_{n,t} - G_{n,t})^2}{\nu^2}, \frac{\tau_{n,t} - G_{n,t}}{\mu} \right) \right), \end{aligned}$$

where second last inequality is because $|\mathbb{E}_{t-1}[\hat{g}_{n,t}]| \le G_{n,t}, n \in [N]$, and last inequality is by Assumption 1 with $C(\nu, \mu) = \sqrt{0.5\pi\nu} + 2\mu$. Finally, taking

$$\tau_{n,t} = G_{n,t} + \nu \sqrt{2 \log \left( \frac{\mathrm{NTC}(\nu, \mu)}{\delta} \right) \lor 2\mu \log \left( \frac{\mathrm{NTC}(\nu, \mu)}{\delta} \right)} \\ \implies C(\nu, \mu) \exp \left( -\frac{1}{2} \min \left( \frac{(\tau_{n,t} - G_{n,t})^2}{\nu^2}, \frac{\tau_{n,t} - G_{n,t}}{\mu} \right) \right) \le \frac{\delta}{TN}$$

and Equality (18) holds with probability at least $1 - \sum_{t=1}^T \sum_{n=1}^N \delta \frac{1}{TN} = 1 - \delta$. With $\sum_{\Delta \in \mathcal{D}} w_t^\Delta = 1, t \ge 1$ and such clipping, we have for every $t \ge 1$

$$|\bar{Z}_t| = \left| \sum_{n=1}^{N} \bar{g}_{n,t} \left( \sum_{\Delta \in \mathcal{D}} w_t^\Delta c_{n,t}^\Delta - c_{n,t}^{\Delta^*} \right) \right| \le \sup_{1 \le t \le T} \sum_{n=1}^{N} 2C_n (G_{n,t} + \Delta(\tau_{n,t})) := D.$$

where $\Delta(\tau_{n,t}) := \nu \sqrt{2 \log \left( \frac{\mathrm{NTC}(\nu, \mu)}{\delta} \right) \lor 2\mu \log \left( \frac{\mathrm{NTC}(\nu, \mu)}{\delta} \right)} \le 2(\mu, \nu) \log \left( \frac{\mathrm{NTC}(\nu, \mu)}{\delta} \right) = O(\log(TN))$ provided that $\log \left( \frac{\mathrm{NTC}(\nu, \mu)}{\delta} \right) \ge \frac{1}{2}$, i.e. $T \ge \exp(1/2)\delta/(NC(\nu, \mu))$. By Corollary 1, with $0 \le \bar{Z}_t^2 \le D^2$, one has with probability $1 - \delta$

$$\sum_{t=1}^{T} \bar{Z}_t^2 \le 2 \sum_{t=1}^{T} \mathbb{E}_{t-1}[\bar{Z}_t^2] + 2D^2 \log(\delta^{-1}).$$

Finally, with probability $1 - 2\delta$ (union bound), one has in Equation (17)

$$\frac{\eta + \gamma}{2} \sum_{t=1}^{T} Z_t^2 \le (\eta + \gamma) \sum_{t=1}^{T} \mathbb{E}_{t-1}[\bar{Z}_t^2] + (\eta + \gamma) D^2 \log(\delta^{-1}),$$
which gives after combining Equations (16), (17) and last inequality, since $\frac{\gamma-\alpha}{2}\mathbb{E}_{t-1}[Z_t^2] \le \frac{\gamma-\alpha}{2}\mathbb{E}_{t-1}[\bar{Z}_t^2], \gamma < \alpha$ and $|\bar{Z}_t| \le |Z_t|$

$$ \sum_{t=1}^{T} L_t(\hat{c}_t) - L_t(c_t^{\Delta^*}) \le \frac{2\eta + 3\gamma - \alpha}{2} \sum_{t=1}^{T} \mathbb{E}_{t-1}[\bar{Z}_t^2] + \frac{\Xi_3^2 \log(|\mathcal{D}|)}{2\eta} + \Xi_4 \log(|\mathcal{D}|) \sup_{1 \le t \le T} \|\hat{\nabla}_t\|_{\infty} + \left( (\eta + \gamma)D^2 + \frac{2}{\gamma} \right) \log(\delta^{-1}) \quad (19) $$

with probability $1-3\delta$. Finally, one has to control $\sup_{1 \le t \le T} \|\hat{\nabla}_t\|_{\infty}$ with high probability. Indeed,

$$ \|\hat{\nabla}_t\|_{\infty} = \sup_{\Delta \in \mathcal{D}} |\hat{g}_t^{\Delta} c_t^{\Delta}| \le \sup_{1 \le t \le T} \sum_{n=1}^{N} C_n |\hat{g}_{n,t}| $$

since $c_{n,t}^{\Delta} \in [-C_n, C_n]$ for every $\Delta \in \mathcal{D}$ and taking the sup over $1 \le t \le T$, one has

$$ \sup_{1 \le t \le T} \|\hat{\nabla}_t\|_{\infty} \le \sup_{1 \le t \le T} \sum_{n=1}^{N} C_n |\hat{g}_{n,t}| = \sup_{1 \le t \le T} \sum_{n=1}^{N} C_n |\hat{g}_{n,t}| \quad (20) $$

where last inequality holds probability at least $1-\delta$ with again $\hat{g}_{n,t} = \text{clip}(\hat{g}_{n,t}, \tau_{n,t})$ using the same clipping threshold as before since

$$ \mathbb{P}\left(\forall 1 \le t \le T, \sum_{n=1}^{N} C_n |\hat{g}_{n,t}| = \sum_{n=1}^{N} C_n |\hat{g}_{n,t}|\right) \ge 1 - \sum_{t=1}^{T} \sum_{n=1}^{N} \mathbb{P}(|\hat{g}_{n,t}| > \tau_{n,t}) \ge 1 - \delta. $$

Then, taking $\eta = \frac{\alpha-3\gamma}{2}$, $\gamma < \frac{\alpha}{3} < \alpha$ cancels the second order terms in (19) and gives, combined with (20)

$$ \sum_{t=1}^{T} L_t(\hat{c}_t) - L_t(c_t^{\Delta^*}) \le \frac{\Xi_3^2 \log(|\mathcal{D}|)}{\alpha - 3\gamma} + \Xi_4 \log(|\mathcal{D}|) \sum_{n=1}^{N} C_n \tau_n + \left( \frac{\alpha - \gamma}{2} \left( 2 \sum_{n=1}^{N} C_n \tau_n \right)^2 + \frac{2}{\gamma} \right) \log(\delta^{-1}) \quad (21) $$

with probability $1-4\delta$ (union bound) and $\tau_n = \sup_{1 \le t \le T} G_{n,t} + O(\max(\nu, \mu) \log(\frac{TN}{\delta}))$.

**Regret $R_T(c)$ of Algorithm 1 with clipping margin $\Delta^*$.** Let

$$ \Delta(\nu, \mu) = \max \left\{ \nu \sqrt{2 \log \left( \frac{(\sqrt{0.5\pi} + 2\mu)T}{\log(\delta^{-1})} \right)}, 2\mu \log \left( \frac{(\sqrt{0.5\pi} + 2\mu)T}{\log(\delta^{-1})} \right) \right\} $$

be the optimal clipping margin in Theorem 2 and define $\Delta^* = \arg\min_{\Delta>\Delta(\nu,\mu)\in\mathcal{D}} |\Delta - \Delta(\nu,\mu)|$ the closest upper margin in the grid $\mathcal{D}$.

From Equation (14) in Proof of Theorem 4 (Appendix A), with clipping margin $\Delta^*$, $G_n = \sup_{1 \le t \le T} G_{n,t}$ and $\hat{g}_{n,t} = \nabla \ell_t(c_t^{\Delta^*})$, $|\mathbb{E}_{t-1}[\hat{g}_{n,t}]| \le G_{n,t}, n \in [N], t \ge 1$ (and assumptions of Theorem 4 are all satisfied), one has

$$ R_T(c^\mu) \le \sum_{n=1}^{N} |c_n| \left( \Xi_1 \sqrt{2 \sum_{t=1}^{T} \mathbb{E}_{t-1}[|\hat{g}_{n,t}|^2]} + \left( \Xi_1 \sqrt{2 \log(\delta^{-1})} + \Xi_2 \right) (G_n + \Delta^*) \right) \\ + 2 \sum_{n=1}^{N} \sum_{t=1}^{T} C_n C(\nu, \mu) \exp \left( -\frac{1}{2} \min \left( \frac{(\Delta^*)^2}{\nu^2}, \frac{\Delta^*}{\mu} \right) \right) \\ + 8 \left( \sup_{1 \le t \le T} \sum_{n=1}^{N} C_n (G_{n,t} + \Delta^* \mathbb{1}_{G_{n,t}>0}) \right)^2 \log(\delta^{-1}) + \frac{6}{\alpha} \log(\delta^{-1}) \quad (22) $$

with probability $1-2\delta$. Since $\Delta^* > \Delta(\nu, \mu)$ we still have (see below (14))

$$ \sum_{t=1}^{T} C(\nu, \mu) \exp \left( -\frac{1}{2} \min \left( \frac{(\Delta^*)^2}{\nu^2}, \frac{\Delta^*}{\mu} \right) \right) \le \log(\delta^{-1}) (\log(T) + 1) $$

and by the precision of the grid $\mathcal{D}$, one has $|\Delta^* - \Delta(\mu, \nu)| \le 1, \Delta(\mu, \nu) = O((\nu \vee \mu) \log(T))$ and then the deviation term

$$ O\left( \sup_{1 \le t \le T} \sum_{n=1}^{N} C_n (G_{n,t} + \Delta^* \mathbb{1}_{G_{n,t}>0}) \right) = O\left( \sup_{1 \le t \le T} \sum_{n=1}^{N} C_n (G_{n,t} + \Delta(\nu, \mu) \mathbb{1}_{G_{n,t}>0}) \right) $$

is still of the same order $O(\log^2 T \log(\delta^{-1}) (\sum_{n=1}^{N} C_n)^2)$.
**Conclusion.** Combining (21) and (22) one has with probability $1 - 6\delta$ and $\gamma = \frac{\alpha}{4} < \frac{\alpha}{3}$

$$ \sum_{t=1}^{T} L_t(\hat{c}_t) - L_t(c^\mu) \le \sum_{n=1}^{N} |c_n| \left[ \Xi_1 \sqrt{2 \sum_{t=1}^{T} \mathbb{E}_{t-1}[|\hat{g}_{n,t}|^2]} + (\Xi_1 \sqrt{2 \log(\delta^{-1})} + \Xi_2)(G_n + \tau) \right] \\ + \frac{4\Xi_3^2 \log(|D|)}{\alpha} + \Xi_4 \log(|D|) \sum_{n=1}^{N} C_n (G_n + \tau) \\ + \left[ \frac{3\alpha}{8} \left( 2 \sum_{n=1}^{N} C_n (G_n + \tau)^2 + 4(\log(T) + 1) \sum_{n=1}^{N} C_n \right) \right. \\ \left. + 8 \left( \sum_{n=1}^{N} C_n (G_n + \tau) \right)^2 + \frac{14}{\alpha} \right] \log(\delta^{-1}). $$

where $\tau = O(\max(\nu, \mu) \log(\frac{TN}{\delta}))$ and this concludes the proof with $|D| \le \sqrt{T} + 1$. $\square$

<figure><img src="image_3.png" /></figure>

**Remark.** Considering sparse expected gradients $g_t = \mathbb{E}_{t-1}[\hat{g}_t]$ the sum $\sum_{n=1}^{N}$ in the deviation terms can be reduced, at each time as a sum over $n \in \text{supp}(g_t)$, provided that $G_{n,t} = 0$ when $g_{n,t} = 0$. This will be useful in particular in the non-parametric setting where $N$ is exponential, but only a small fraction $|\text{supp}(g_t)|$ of coordinates are non zero (active) at time each time $t$, hence a much smaller diameter in the deviation terms.
C Proof of Theorem 3

of Theorem 3. Let $f \in \mathcal{B}_{pq}^s(B)$ be fixed and $Y = f(X) + \varepsilon$ with $\mathbb{E}[\varepsilon|X] = 0$ and $\mathbb{E}[\varepsilon^2|X] = \sigma^2 < \infty$. Recall that the training data set $((X_t, Y_t))_{1 \le t \le T} \sim (X, Y)$ is i.i.d. and with same law as the test pair $(X, Y)$.

**Decomposition of risk.** For the square loss, one has for any predictor $\hat{f}$ this nice decomposition of the expected risk

$$
\begin{align*}
\mathbb{E}_{XY}[(\hat{f}(X) - Y)^2] &= \mathbb{E}_X[\mathbb{E}[(\hat{f}(X) - Y)^2|X]] \\
&= \mathbb{E}_X[\mathbb{E}[(\hat{f}(X) - f(X) - \xi)^2|X]] \\
&= \mathbb{E}_X[\mathbb{E}[(\hat{f}(X) - f(X))^2|X]] + \mathbb{E}_X[\mathbb{E}[\xi^2|X]] - 2\mathbb{E}_X[\mathbb{E}[(\hat{f}(X) - f(X))\xi|X]] \\
&= \mathbb{E}_X[(\hat{f}(X) - f(X))^2] + \mathbb{E}[\xi^2] \\
&= \|\hat{f} - f\|_2^2 + \sigma^2. \tag{23}
\end{align*}
$$

Going back to the excess risk and letting $\hat{f} = \bar{f}_T = \frac{1}{T} \sum_{t=1}^T \hat{f}_t$ in (23), after direct algebraic calculations one has

$$
\begin{align}
\|\bar{f}_T - f\|_2^2 &= \mathbb{E}_{XY}[(\bar{f}_T(X) - Y)^2] - \mathbb{E}_{XY}[(f(X) - Y)^2] \nonumber \\
&\le \frac{1}{T} \sum_{t=1}^T \mathbb{E}_{XY}[(\hat{f}_t(X) - Y)^2] - \mathbb{E}_{XY}[(f(X) - Y)^2], \tag{24}
\end{align}
$$

by Jensen's inequality and convexity of the square loss. Further, since $(X_t, Y_t) \sim P_{(X,Y)}$ and is independent of $\mathcal{F}_{t-1}$ and $\hat{f}_t$ is $\mathcal{F}_{t-1}$ measurable, one has for every $t \ge 1$

$$
\mathbb{E}_{XY}[(\hat{f}_t(X) - Y)^2] = \mathbb{E}_{t-1}[(\hat{f}_t(X_t) - Y_t)^2],
$$

where we used the notation $\mathbb{E}_{t-1}[\cdot] = \mathbb{E}[\cdot | \mathcal{F}_{t-1}]$. And finally,

$$
\begin{align}
\| \bar{f}_T - f \|_2^2 &\le \frac{1}{T} \underbrace{\sum_{t=1}^T \mathbb{E}_{t-1}[(\hat{f}_t(X_t) - Y_t)^2] - \mathbb{E}_{t-1}[(f(X_t) - Y_t)^2]}_{=: R_T(f)} \tag{25} \\
&= \underbrace{\sum_{t=1}^T \mathbb{E}_{t-1}[(\hat{f}_t(X_t) - Y_t)^2] - \mathbb{E}_{t-1}[(f(X_t) - Y_t)^2]}_{=: R_T(f)} \nonumber
\end{align}
$$

The problem now turns out to analyse the (stochastic) regret $R_T(f)$ and this situation mirrors the problem studied in Section 2 with losses $L_t(\hat{f}_t) = \mathbb{E}_{t-1}[\ell_t(\hat{f}_t(X_t))], t \ge 1$ where $\ell_t(\hat{f}_t(X_t)) = (\hat{f}_t(X_t) - Y_t)^2$ and $\ell_t$'s randomness is due to $Y_t$'s one.

The quantity of interest $R_T(f)$ then decomposes for every oracle estimator $\hat{f}^*$, into an estimation regret term $R_T(\hat{f}^*)$ plus a bias (or approximation regret) term

$$
R_T(f) = R_T(\hat{f}^*) + \sum_{t=1}^{T} \underbrace{\mathbb{E}_{t-1}[\ell_t(\hat{f}^*(X_t))] - \mathbb{E}_{t-1}[\ell_t(f(X_t))]}_{(23)} R_T(\hat{f}^*) + T \|\hat{f}^* - f\|_2^2,
$$

with $\ell_t(\hat{f}) = (\hat{f} - Y_t)^2$.

**Step 1: Bound on the estimation regret $R_T(\hat{f}^*)$.** One has $\hat{f}_t(X_t) = \sum_e w_{e,t} \hat{f}_{e,t}(X_t)$ (average over all experts). Consider $e^* = (j_0^*, \Delta^*, \alpha^*) \in [J_0] \times \mathcal{D} \times \mathcal{A}_{j_0^*} (j_0^*$ oracle starting scale, $\alpha^*$ best scaling coefficients on the grid $\mathcal{A}_{j_0^*}$, and $\Delta^*$ the best clipping margin). We then define the expert with best parameters $e^*$ at every time $t \ge 1$, $\hat{f}_{e^*,t}$ and the oracle regressor $\hat{f}_{e^*}(X_t)$ with oracle coefficients $(c_{j,k})$ and oracle parameters $e^*$. We have at every time $t \ge 1$, the following decomposition

$$
\begin{align*}
R_T(\hat{f}^*) &= \underbrace{\sum_{t=1}^{T} L_t(\hat{f}_t(X_t)) - L_t(\hat{f}^*)}_{\text{expert aggregation regret} \quad =: R_1} \\
&= \underbrace{\sum_{t=1}^{T} L_t(\hat{f}_t) - L_t(\hat{f}_{e^*,t}(X_t))}_{\text{regret of Alg.1} \quad =: R_2} + \underbrace{\sum_{t=1}^{T} L_t(\hat{f}_{e^*,t}(X_t)) - L_t(\hat{f}_{e^*}(X_t))}_{\text{regret of Alg.1} \quad =: R_2}.
\end{align*}
$$

1. **Bound on the expert aggregation regret $R_1$.** Let $\hat{g}_t = \ell'_t(\hat{f}_t(X_t)) = 2(\hat{f}_t(X_t) - Y_t)$ be the noisy observed gradient of $L'_t(\hat{f}_t(X_t))$. In particular, $\hat{g}_t$ satisfies Assumption 1 and

$$
|\mathbb{E}_{t-1}[\hat{g}_t]| = 2\mathbb{E}_{t-1}[\hat{f}_t(X_t) - f(X_t) - \varepsilon_t]| \le 2(\hat{B}_{\infty} + B) =: G.
$$
The gradient experts $\hat{\nabla}_t = (\nabla_{e,t})_{e \in \mathcal{E}}$ writes $\hat{\nabla}_{e,t} = \hat{g}_t \cdot \hat{f}_{e,t}(X_t)$ and $|\mathbb{E}_{t-1}[\hat{\nabla}_{e,t}]| \le G\hat{B}_{\infty}$ where $\hat{B}_{\infty}$ is the sup-norm on the experts, bounded as in Lemma 4. Therefore, letting $Z_{e^*,t} = \hat{\nabla}_t^\top w_t - \hat{\nabla}_{e^*,t}$, by Assumption 2 on $(\ell_t)$ one has

$$ \sum_{t=1}^{T} L_t(\hat{f}_t) - L_t(\hat{f}_{e^*,t}) \le \sum_{t=1}^{T} \mathbb{E}_{t-1}[Z_{e^*,t}] - \frac{\alpha}{2} \mathbb{E}_{t-1}[Z_{e^*,t}^2] \\ \le \sum_{t=1}^{T} Z_{e^*,t} + \frac{\gamma}{2} Z_{e^*,t}^2 + \frac{\gamma - \alpha}{2} \mathbb{E}_{t-1}[Z_{e^*,t}^2] + \frac{2}{\gamma} \log(\delta^{-1}) \quad (26) $$

where last inequality holds with high probability $1 - \delta$ for any $\gamma > 0$ by Lemma 3. Moreover, one can bound the first order term by Assumption 4 with $Z_{e^*,t} = \hat{\nabla}_t^\top w_t - \hat{\nabla}_{e^*,t}$

$$ \sum_{t=1}^{T} Z_{e^*,t} \le \Xi_3 \sqrt{\log(|\mathcal{E}|) \sum_{t=1}^{T} Z_{e^*,t}^2 + \Xi_4 \log(|\mathcal{E}|) \sup_{1 \le t \le T} \|\hat{\nabla}_t\|_{\infty}} $$

Further, by Young's inequality, we have for every $\eta > 0$

$$ \Xi_3 \sqrt{\log(|\mathcal{E}|) \sum_{t=1}^{T} Z_{e^*,t}^2} \le \frac{\Xi_3^2 \log(|\mathcal{E}|)}{2\eta} + \frac{\eta}{2} \sum_{t=1}^{T} Z_{e^*,t}^2. $$

And in bound (26) we have

$$ \sum_{t=1}^{T} Z_{e^*,t} + \frac{\gamma}{2} Z_{e^*,t}^2 \le \frac{\Xi_3^2 \log(|\mathcal{E}|)}{2\eta} + \Xi_4 \log(|\mathcal{E}|) \sup_{1 \le t \le T} \|\hat{\nabla}_t\|_{\infty} \\ + \frac{\eta + \gamma}{2} \sum_{e^* \in \mathcal{E}^*} \sum_{t=1}^{T} Z_{e^*,t}^2. \quad (27) $$

Further, since $\hat{g}_t$ satisfies Assumption 1 with some parameters $(\nu, \mu)$, we have $\sup_{1 \le t \le T} \|\hat{\nabla}_t\|_{\infty} = \hat{B}_{\infty} \sup_{1 \le t \le T} |\hat{g}_t|$ that can be bounded, with probability $1 - \delta$, as

$$ \sup_{1 \le t \le T} \|\hat{\nabla}_t\|_{\infty} \le \tau \hat{B}_{\infty} \quad (28) $$

because $\forall 1 \le t \le T$, $g_t = \text{clip}(g_t, \tau)$ with probability $1 - \delta$ as with $\tau = G + O((\nu \vee \mu) \log(T/\delta))$ under Assumption 1. Then, with $Z_{e^*,t} = \hat{\nabla}_t^\top w_t - \hat{\nabla}_{e^*,t} = \hat{g}_t(\hat{f}_t(X_t) - \hat{f}_{e^*,t}(X_t))$, one has also with high probability $1 - \delta$,

$$ \sum_{t=1}^{T} Z_{e^*,t} = \sum_{t=1}^{T} \text{clip}(g_t, \tau)(\hat{f}_t(X_t) - \hat{f}_{e^*,t}(X_t)), $$

Setting $\bar{Z}_{e^*,t} := \text{clip}(g_t, \tau)(\hat{f}_t(X_t) - \hat{f}_{e^*,t}(X_t))$, we can use Corollary 1, with $0 \le (\bar{Z}_{e^*,t})^2 \le 4\tau^2 \hat{B}_{\infty}^2$ and we finally have with probability $1 - 2\delta$ (union bound)

$$ \sum_{t=1}^{T} Z_{e^*,t}^2 \le 2 \sum_{t=1}^{T} \mathbb{E}_{t-1}[\bar{Z}_{e^*,t}^2] + 8\tau^2 \hat{B}_{\infty}^2 \log(\delta^{-1}). \quad (29) $$

Plugging (27), (28) and (29) in (26), we get with probability $1 - 4\delta$ (union bound)

$$ R_1 \le \frac{2\eta + 3\gamma - \alpha}{2} \sum_{t=1}^{T} \mathbb{E}_{t-1}[\bar{Z}_{e^*,t}^2] \\ + \log(|\mathcal{E}|) \left( \frac{\Xi_3^2}{2\eta} + \Xi_4 \tau \hat{B}_{\infty} \right) + 2 \left( 4\tau^2 \hat{B}_{\infty}^2 + \frac{1}{\gamma} \right) \log(\delta^{-1}) \quad (30) $$

taking $0 < \gamma < \alpha$ so that $\frac{\gamma - \alpha}{2} \mathbb{E}_{t-1}[Z_{e^*,t}^2] \le \frac{\gamma - \alpha}{2} \mathbb{E}_{t-1}[\bar{Z}_{e^*,t}^2]$. Finally, taking $0 < \gamma < \frac{\alpha}{3}$, $\eta = \frac{\alpha - 3\gamma}{2} > 0$ cancels the second order term and we have, with probability $1 - 4\delta$

$$ R_1 \le \log(|\mathcal{E}|) \left( \frac{\Xi_3^2}{\alpha - 3\gamma} + \Xi_4 \tau \hat{B}_{\infty} \right) + 2 \left( 4\tau^2 \hat{B}_{\infty}^2 + \frac{1}{\gamma} \right) \log(\delta^{-1}). \quad (31) $$

with $\tau = G + O((\nu \vee \mu) \log(T/\delta))$
2. **Bound on $R_2$ via Theorem 1.** We can apply Theorem 1 to bound $R_2$. Recall that $\hat{f}_{e^*}^*$ is an oracle wavelet regressor (oracle coefficients, and oracle starting resolution) and

$$ \hat{f}_{e^*,t} = \underbrace{\sum_{k \in \bar{\Lambda}_{j_0^*}} \alpha_{j_0^*,k,t} \phi_k}_{\text{scaling part}} + \underbrace{\sum_{j=j_0^*}^{j_0^*+J} \sum_{k \in \Lambda_j} \beta_{j,k,t} \psi_{j,k}}_{\text{detail part}} $$

where $\alpha_{j_0^*,k,t}$ denotes scaling coefficients at time $t$, starting at $\alpha_{j_0^*,1} \in \mathcal{A}$, and $\beta_{j,k}, j \ge j_0^*$ are wavelet coefficients up to some optimized truncation level $J = \frac{S}{(2S+d)\kappa} \log(TB^2\sigma_0^{-2})$ (large enough to kill the approximation term). Applying Theorem 1 on coefficients $\{\alpha_{j,k}, \beta_{j,k}\}$, with oracle clipping margin $\Delta_{e^*} \propto \max(\nu, \mu) \log(T) \in \mathcal{D}$, with probability $1-2\delta$

$$ \sum_{t=1}^{T} L_t(\hat{f}_{e^*,t}(X_t)) - L_t(\hat{f}_{e^*}^*(X_t)) \le C \sum_{j,k} |c_{j,k} - c_{j,k,1}| \sqrt{\sum_{t=1}^{T} \mathbb{E}_{t-1}[\hat{g}_{j,k,t}^2]} \\ + O\left(\left(\sup_{1 \le t \le T} \sum_{j,k} C_{j,k}(G_{j,k,t} + \max(\nu, \mu) \log(T)) 1_{G_{j,k,t>0}}\right)^2 \log(\delta^{-1})\right) $$

where $c_{j,k}$ stands for either $\alpha_{j,k}$ or $\beta_{j,k}$ and $C$ is deduced from Theorem 4 and can include $\log T$ terms. We study the bound in 4 parts:

* **Scaling coefficients:** since the scaling coefficients at level $j_0^*$ starts on a grid of precision $\epsilon_{j_0^*} = \frac{B_\infty \|\phi\|_1 (2^{j_0 d/2} \sqrt{T})^{-1}}{(\sqrt{T})^{-1}}$ (the grid is of size $O(\sqrt{T})$ for every level $j_0^*$)

$$ \sum_{k \in \bar{\Lambda}_{j_0^*}} \underbrace{\left|\alpha_{j_0^*,k} - \alpha_{j_0^*,k,1}\right|}_{\le \frac{\epsilon_{j_0^*}}{2}} \sqrt{\sum_{t=1}^{T} \mathbb{E}_{t-1}[\hat{g}_{j,k,t}^2]} \le \epsilon_{j_0^*} |\bar{\Lambda}_{j_0^*}|^{\frac{1}{2}} \sqrt{\sum_{k \in \Lambda_{j_0^*}} \sum_{t=1}^{T} \mathbb{E}_{t-1}[\hat{g}_{j,k,t}^2]} \\ \le \frac{B_\infty \|\phi\|_1 \lambda^{\frac{1}{2}}}{\sqrt{T}} \sqrt{M_\phi \|\phi\|_\infty T} = (\lambda M_\phi \|\phi\|_\infty)^{\frac{1}{2}} $$

where we used Jensen's inequality, $|\bar{\Lambda}_{j_0^*}| \le \lambda 2^{j_0^* d}$, the form of the gradients $\hat{g}_{j,k,t} = \hat{g}_t \cdot \phi_k(X_t)$ and the fact that $\sum_k |\phi_k(X_t)|^2 \le \|\phi\|_\infty \cdot \sum_k |\phi(\cdot - k)|\|\phi\|_\infty = \|\phi\|_\infty \cdot M_\phi < \infty$.

* **Detail coefficients:** We use the same oracle as in [Liautaud et al., 2025, Theorem 1] that was designed for a control on the $L^\infty$ bias and works also for the $L^2$-norm. We have a linear part and non linear part in the wavelet oracle: we keep all the detail coefficients in between $[j_0^*, j_0^* + J^*]$ up to some level $j_0^* + J^*$ and then retain only greatest coefficients $\beta_{j,k}$ from level $[j_0^* + J^*, J]$.

- Linear part: $j = j_0^*, \dots, J^* + j_0^*$ For the linear part, denoting $\beta_j = (\beta_{j,k})_{k \in \Lambda_j}, j = j_0^*, \dots, j_0^* + J$, one has

$$ \sum_{j=j_0^*}^{j_0^*+J^*} \sum_{k \in \Lambda_j} |\beta_{j,k}| \sqrt{\sum_{t=1}^{T} \mathbb{E}_{t-1}[|\hat{g}_{j,k,t}|^2]} \\ \le \sum_{j=j_0^*}^{j_0^*+J^*} \|\beta_j\|_p |\Lambda_j|^{(\frac{1}{2}-\frac{1}{p})} + \sqrt{\sum_{t=1}^{T} \sum_{k \in \Lambda_j} (e^*)^2 \mathbb{E}_{t-1}[|\hat{g}_{j,k,t}|^2]} \\ \le \sum_{j=j_0^*}^{j_0^*+J^*} \|\beta_j\|_p |\Lambda_j|^{(\frac{1}{2}-\frac{1}{p})} + \sqrt{\sum_{t=1}^{T} \mathbb{E}_{t-1}[|\hat{g}_t|^2]} \|\sum_{k \in \Lambda_j} |\psi_{j,k}(\cdot)|^2\|_\infty \\ \le \sum_{j=j_0^*}^{j_0^*+J^*} \|\beta_j\|_p |\Lambda_j|^{(\frac{1}{2}-\frac{1}{p})} + 2^{\frac{j}{2}} \sqrt{M_\psi \|\psi\|_\infty \sum_{t=1}^{T} \mathbb{E}_{t-1}[|\hat{g}_t|^2]} \\ \le \lambda^{\frac{1}{2}} \|f\|_B \sqrt{M_\psi \|\psi\|_\infty \sum_{t=1}^{T} \mathbb{E}_{t-1}[|\hat{g}_t|^2]} \sum_{j=j_0^*}^{j_0^*+J^*} 2^{-j\beta} $$

where first inequality is by Hölder's inequality (with $p \ge 1$) and convexity on $\sum_k$, and last inequality applies Hölder's inequality on $\sum_j$ (with $q \ge 1$), $|\Lambda_j| \le \lambda 2^{jd}$ and $M_\psi =$
$\|\sum_k |\psi(\cdot - k)\|_{\infty} < \infty$ and $\|f\|_{\mathcal{B}}$ is the Besov norm of the function $f$ defined in (6) and we defined $\beta = s - \frac{d}{p} - (\frac{d}{2} - \frac{d}{p})_+$. Further, we have for every $t \ge 1$

$$ \mathbb{E}_{t-1}[\hat{g}_t^2] = 4(\mathbb{E}_{t-1}[(\hat{f}_t(X_t) - f(X_t))^2] + \sigma^2) = 4(L_t(\hat{f}_t(X_t)) - L_t(f(X_t)) + \sigma^2) $$

and plugging this in the previous bound gives

$$ C \|f\|_{\mathcal{B}} \left( \sqrt{\sum_{t=1}^{T} (L_t(\hat{f}_t(X_t)) - L_t(f(X_t)))} + \sigma \sqrt{T} \right) \sum_{j=j_0^*+J}^{j_0^*+J} 2^{-j\beta} $$

where $C$ can be deduced from the last lines.

- Detail coefficients in the nonlinear part: we consider only a sparse representation of the function in levels $[j_0^*+J^*, J]$, and we keep only an oracle set of coefficients $\Lambda^* = \{(j, k), J^* \le j \le J, \text{greatest coefficients } |\beta_{j,k}|\}$. Similarly to [Liautaud et al., 2025, Theorem 1], retaining only $|\Lambda^*| = 2^{(j_0^*+J^*)d}$ gives a regret of the same order of that of the linear part above. Indeed, with $\Lambda^* = \cup_{j=J^*+j_0^*+1}^J \Lambda_j^*$ where $|\Lambda_j^*| \le |\Lambda_j|$ is now the oracle sparse set made of positions $k$ at level $j$. One has on the levels $j = J^* + j_0^* + 1, \dots, J$,

$$ C \sum_{J^*+j_0^*<j \le J} \|\beta_j\|_p |\Lambda_j^*|^{(\frac{1}{2}-\frac{1}{p})+} \sqrt{\sum_{k \in \Lambda_j^*} \sum_{t=1}^T \mathbb{E}_{t-1}[|\hat{g}_{j,k,t}|^2]} \\ \le C \left( \sqrt{\sum_{t=1}^T (L_t(\hat{f}_t(X_t)) - L_t(f(X_t)))} + \sigma \sqrt{T} \right) \sum_{J^*+j_0^*<j \le J} \|\beta_j\|_p |\Lambda_j^*|^{(\frac{1}{2}-\frac{1}{p})+} 2^{\frac{dj}{2}} $$

Then, using Hölder's inequality with $q \ge 1$ one has

$$ \sum_{J^*+j_0^*<j \le J} 2^{\frac{dj}{2}} \|\beta_j\|_p |\Lambda_j^*|^{(\frac{1}{2}-\frac{1}{p})+} = \sum_{J^*+j_0^*<j \le J} 2^{j(s+\frac{d}{2}-\frac{d}{p})} \|\beta_j\|_p \cdot 2^{-j(s-\frac{d}{p})} |\Lambda_j^*|^{(\frac{1}{2}-\frac{1}{p})+} \\ \le \|f\|_{\mathcal{B}} \sum_{J^*+j_0^*<j \le J} 2^{-j(s-\frac{d}{p})} |\Lambda_j^*|^{(\frac{1}{2}-\frac{1}{p})+} $$

Finally, since $\sum_{J^*<j \le J} |\Lambda_j^*| = |\Lambda^*|$, one has

$$ \sum_{J^*+j_0^*<j \le J} 2^{-j(s-\frac{d}{p})} |\Lambda_j^*|^{(\frac{1}{2}-\frac{1}{p})+} \le |\Lambda^*|^{(\frac{1}{2}-\frac{1}{p})+} + \sum_{J^*+j_0^*<j \le J} 2^{-j(s-\frac{d}{p})} \\ \le |\Lambda^*|^{(\frac{1}{2}-\frac{1}{p})+} + \frac{2^{-(J^*+j_0^*)(s-\frac{d}{p})}}{2^{s-\frac{d}{p}}-1}, $$

by Hölder's inequality in the case $p \ge 2$ and since $s > \frac{d}{p}$ and taking $|\Lambda^*| = 2^{d(J^*+j_0^*)}$ entails a nonlinear regret of

$$ C \|f\|_{\mathcal{B}} \left( \sqrt{\sum_{t=1}^{T} (L_t(\hat{f}_t(X_t)) - L_t(f(X_t)))} + \sigma \sqrt{T} \right) 2^{-(J^*+j_0^*)(s-\frac{d}{p})} $$

which is of the same order of the regret for the linear part.

* **Deviation term:** Let $\varphi$ denote either the scaling basis function $\phi$ or the wavelet $\psi$. With $G_{j,k,t} = G|\varphi_{j,k}(X_t)| = G2^{\frac{jd}{2}}|\varphi(2^j X_t - k)|$ and $C_{j,k} = B2^{-\frac{jd}{2}}$ at any time $t \ge 1$, one has

$$ \sup_{1 \le t \le T} \sum_{j,k} |C_{j,k} G_{j,k,t}| \le GB \sup_x \sum_{j,k} |\varphi(x-k)| \le \sum_{j=j_0^*}^{j_0^*+J} \sup_x \sum_{k \in \Lambda_j} |\varphi(x-k)| \le GBM_{\varphi}(J+1), $$

and setting $N_{\varphi} = \sup_x \sum_k 1_{|\varphi(x-k)|>0} < \infty$ the number of wavelets involved at each scale (of order $S^d$)

$$ \sup_{1 \le t \le T} \sum_{n \in \Lambda_{e^*}} C_n 1_{G_{n,t} > 0} \le B \sum_{j=j_0(e^*)}^{j_0(e^*)+J} 2^{-\frac{jd}{2}} \sup_x \sum_{k \in \Lambda_{e^*,j}} 1_{|\varphi(x-k)|>0} \le \frac{BN_{\varphi}}{1-2^{-d/2}} $$

Finally the deviation term is of order

$$ D := O\left( \left( GBM_{\varphi}(J+1) + \frac{BN_{\varphi}}{1-2^{-d/2}} \max(\nu, \mu) \log(T) \right)^2 \log(\delta^{-1}) \right), $$

where $J$ will be of order $\log T$.

* **Conclusion on $R_2$:** One has with probability $1-2\delta$, summing all the previous bounds:

$$ R_2 \le C \|f\|_{\mathcal{B}} \left( \sqrt{\sum_{t=1}^{T} (L_t(\hat{f}_t(X_t)) - L_t(f(X_t)))} + \sigma \sqrt{T} \right) \sum_{j=j_0^*+J}^{j_0^*+J} 2^{-j\beta} + D $$
**Step 2: Bound on the approximation term.** Recall $\Lambda^*$ denotes the set of indices corresponding to the $|\Lambda^*|$ largest wavelet coefficients (in absolute value) among all $(v_{j,k} = \beta_{j,k} 2^{j(s+d/2-d/p)})$ with $j \in [J^* + j_0^* + 1, J]$ and $k \in \Lambda_j$. Let $j > J^* + j_0^*$. We have that

$$ \sum_{J^*+j_0^* < j \le J} \sum_{k \in \Lambda_j} |v_{j,k}|^p \le (J - (J^* + j_0^*)^{(1-\frac{p}{q})}) + \left( \sum_{J^*+j_0^* < j \le J} \left( \sum_{k \in \Lambda_j} |v_{j,k}|^p \right)^{\frac{q}{p}} \right)^{\frac{p}{q}} \\ \le [(J - (J^* + j_0^*))^{(\frac{1}{p} - \frac{1}{q})} + \|f\|_B]^p =: C_f^p, $$

and

$$ |\Lambda^*| \cdot \min_{(j,k) \in \Lambda^*} |v_{j,k}|^p \le \sum_{(j,k) \in \Lambda^*} |v_{j,k}|^p \le C_f^p < \infty. $$

In particular since $\forall (j,k) \notin \Lambda^*, |v_{j,k}| \le \min_{(j',k') \in \Lambda^*} |v_{j',k'}|$ one has

$$ \forall (j,k) \notin \Lambda^*, \quad |\Lambda^*| |v_{j,k}|^p \le C_f^p \implies \forall (j,k) \notin \Lambda^*, \quad |\beta_{j,k}| \le C_f 2^{-j(s+d/2-d/p)} |\Lambda^*|^{-\frac{1}{p}}. \quad (32) $$

And, by Parseval's inequality, with $s' = d - d/p + d/2$

$$ \|\hat{f}^* - f\|_2^2 = \sum_{(j,k) \notin \Lambda^*} |\beta_{j,k}|^2 + \sum_{j>J} |\beta_{j,k}|^2 \quad (33) $$

$$ \le C_f^2 |\Lambda^*|^{-\frac{2}{p}} \sum_{j=J^*+j_0^*+1}^{J} \sum_k 2^{-2js'} + \sum_{j>J} \sum_k \|f\|_B^2 2^{-2js'} \quad \leftarrow \text{by (32)} $$

$$ \le C_f^2 |\Lambda^*|^{-\frac{2}{p}} \frac{2^{-2(J^*+j_0^*)(s-\frac{d}{p})}}{2^{(s-\frac{d}{p})}-1} + \|f\|_B^2 \frac{2^{-2J(s-\frac{d}{p})}}{2^{(s-\frac{d}{p})}-1} \quad \leftarrow \text{replacing } s' \text{ and with } s > \frac{d}{p}. $$

$$ = \frac{1}{2^{s-\frac{d}{p}}-1} (C_f^2 2^{-2J^*s} + \|f\|_B^2 2^{-2J(s-d/p)}) \quad \leftarrow |\Lambda^*| = 2^{j_0^*+J^*} \quad (34) $$

Finally one has

$$ R_3 := T \|\hat{f}_{e^*}^* - f\|_2^2 \le C \|f\|_B^2 T 2^{-2(J^*+j_0^*)s} + \frac{\|f\|_B^2}{2^{s-d/p}} 2^{-2J(s-d/p)} \quad (35) $$

where $C \le (J - (J^* + j_0^*))^{2(\frac{1}{p} - \frac{1}{q})} / (2^{2(s-d/p)} - 1)$. In the next section, we take $J$ high enough so that the bias terms in $2^{-2J(s-d/p)}$ vanishes.

**Step 3: Optimization of the resolutions $J$, $J^*$ and $j_0^*$.** Summarizing the previous steps, we have with probability at least $1 - 6\delta$ (via a union bound over $R_1, R_2$, and the concentration terms):

$$ R_T(f) \le R_1 + R_2 + R_3 + D $$

where $R_1 = O((\log |\mathcal{E}| + \log^2 T \log \delta^{-1})$ is the expert regret and $D = O(\log^2 T \log \delta^{-1})$ is the deviation term in estimating the wavelet coefficients. From here, we assume that $J > 0$ is high enough so that the term $2^{-2J(s-d/p)}$ in $R_3$ vanishes.

According to the sign of $\beta$, one has, with $M^* = j_0^* + J^*$ the maximum resolution,

* Case $\beta > 0$

- $\beta = s - d/2 > 0$ and $p > 2$, i.e. $s > d/2$. One has $\sum_{j=j_0^*}^{j_0^*+J^*} 2^{-\beta j} \le C' 2^{-j_0^*(s-d/2)}$ and

$$ R_T(f) \le C' 2^{-j_0^*(s-\frac{d}{2})} \|f\|_B \left( \sqrt{R_T(f)} + \sigma \sqrt{T} \right) + C \|f\|_B^2 T 2^{-2(j_0^*+J^*)s} + (R_1 + D) $$

- $\beta = s - d/p > 0$ and $p < 2$. One has $\sum_{j=j_0^*}^{j_0^*+J^*} 2^{-\beta j} + 2^{-(s-\frac{d}{p})(j_0^*+J^*)} \le C' 2^{-j_0^*(s-d/p)}$ and

$$ R_T(f) \le C' 2^{-j_0^*(s-d/p)} \|f\|_B \left( \sqrt{R_T(f)} + \sigma \sqrt{T} \right) + C \|f\|_B^2 T 2^{-2(j_0^*+J^*)s} + (R_1 + D) $$

* $\beta = s - d/2 = 0$ and $p \ge 2$. One has $\sum_{j=j_0^*}^{j_0^*+J^*} 2^{-\beta j} \le C' J^*$ and

$$ R_T(f) \le C' J^* \|f\|_B \left( \sqrt{R_T(f)} + \sigma \sqrt{T} \right) + C \|f\|_B^2 T 2^{-2(j_0^*+J^*)s} + (R_1 + D) $$
• $\beta = s - d/2 < 0$ and $p > 2$, i.e. $s < d/2$. One has $\sum_{j=j_0^*}^{j_0^*+J^*} 2^{-j\beta} \le C'2^{-(j_0^*+J^*)(s-\frac{d}{2})}$

$$R_T(f) \le C' \|f\|_{\mathcal{B}} 2^{-(j_0^*+J^*)(s-\frac{d}{2})} \left( \sqrt{R_T(f)} + \sigma\sqrt{T} \right) + C \|f\|_{\mathcal{B}}^2 T 2^{-2(j_0^*+J^*)s} + (R_1 + D)$$

Let $U = \sqrt{R_T(f)}$. In all regimes, the bound satisfies a quadratic inequality $U^2 \le AU + A\sigma\sqrt{T} + R_3 + (R_1 + D)$. Applying Young's inequality ($AU \le \frac{1}{2}U^2 + \frac{1}{2}A^2$), we obtain:

$$R_T(f) \le A^2 + 2A\sigma\sqrt{T} + 2R_3 + 2(R_1 + D). \quad (36)$$

In each case, the terms $A^2 + 2A\sigma\sqrt{T} + 2R_3$ dominates and are of opposite variation. We set the maximal resolution $M^* = j_0^* + J^*$ and we have in each case:

• **Case $\beta = s - d/2 < 0$:** In this regime ($s < d/2$), the variance term is dominated by the fine-scale resolution $M^*$. With $A = C' \|f\|_{\mathcal{B}} 2^{-M^*(s-\frac{d}{2})}$, the regret is of order:

$$\|f\|_{\mathcal{B}}^2 2^{-2M^*(s-\frac{d}{2})} + \|f\|_{\mathcal{B}} 2^{-M^*(s-\frac{d}{2})} \sigma\sqrt{T} + \|f\|_{\mathcal{B}}^2 T 2^{-2M^*s}.$$

Balancing the variance and bias by setting $\sigma \|f\|_{\mathcal{B}} \sqrt{T} 2^{-(s-\frac{d}{2})M^*} \asymp T \|f\|_{\mathcal{B}}^2 2^{-2M^*s}$ yields the optimal resolution:

$$M^* = \left[ \frac{1}{2s+d} \log_2 \left( T \|f\|_{\mathcal{B}}^2 \sigma^{-2} \right) \right] \le J$$

where we assume $\sigma^2 \le T$. Plugging this back into the bound gives:

$$R_T(f) \le O \left( \|f\|_{\mathcal{B}}^{\frac{2d}{2s+d}} (\sigma^2)^{\frac{2s}{2s+d}} T^{\frac{d}{2s+d}} \right) + 2(R_1 + D).$$

Note that $A^2 = O(T^{\frac{d-2s}{2s+d}})$, which is strictly smaller than $O(T^{\frac{d}{2s+d}})$.

• **Case $\beta = 0$:** For $s = d/2$, the variance term $A$ scales with the number of levels, $A = C' \|f\|_{\mathcal{B}} J^*$. Setting $J^* \propto \frac{1}{d} \log_2(T) \le J$ and choosing $j_0^* = M^* - J^*$, with $M^*$ as defined above, ensures the optimal regret up to a logarithmic factor:

$$R_T(f) \le O \left( \|f\|_{\mathcal{B}}^{\frac{2d}{2s+d}} (\sigma^2)^{\frac{2s}{2s+d}} T^{\frac{d}{2s+d}} \log_2(T) \right) + 2(R_1 + D) = O(\sqrt{T} \log_2(T)).$$

• **Case $\beta > 0$:** This regime corresponds to $s - d/2 > 0$ (or $s - d/p > 0$ for $p < 2$). With $A = C' 2^{-j_0^*(s-d/2)} \|f\|_{\mathcal{B}}$, the dominant terms are:

$$\|f\|_{\mathcal{B}}^2 2^{-2j_0^*(s-d/2)} + \|f\|_{\mathcal{B}} 2^{-j_0^*(s-d/2)} \sigma\sqrt{T} + \|f\|_{\mathcal{B}}^2 T 2^{-2(j_0^*+J^*)s}.$$

Since $s > d/2$, all terms decrease with $j_0^* \in [0, J_0]$. Here, the variance term $2A\sigma\sqrt{T}$ dominates $R_3$ when $j_0^*$ is small. To achieve the minimax rate, we can choose $j_0^* = (\text{sup on the grid of starting scale})$ to suppress the $\sqrt{T}$ noise growth, with $j_0^* = \frac{1}{s-\frac{d}{2}} \log_2 (\|f\|_{\mathcal{B}}^{\frac{2s}{2s+d}} \sigma^{\frac{d}{2s+d}} T^{\frac{s-d}{2s+d}}) \propto \frac{1}{2s+d} \log_2(T)$ and we get the same rate as before.

• **Maximum scale $J$:** In $R_3$ also appears a bias, so we have to ensure that we take a maximum scale $J$ that is high enough so that the bias term $O(T 2^{-2J(s-d/p)})$ vanishes. To control the bias term, we choose a resolution level $J$, assuming $\|f\|_{\mathcal{B}} \le B \le \sqrt{T}$ and $\sigma \ge \sigma_0 > 0$.

$$J = \left[ \frac{S}{(2S+d)\kappa} \log_2(T B^2 \sigma_0^{-2}) \right] \ge \left[ \frac{S}{(2S+d)\kappa} \log_2(T \|f\|_{\mathcal{B}}^2 \sigma^{-2}) \right] \ge 1$$

assuming $\|f\|_{\mathcal{B}} \ge \frac{1}{\sqrt{T}}$ and $\sigma \ge \sqrt{T}$. This choice of maximum scale $J$ ensures that

$$\|f\|_{\mathcal{B}}^2 T 2^{-2J(s-d/p)} \le T 2^{-2J\kappa} \le O(T^{\frac{d}{2s+d}}).$$

**Conclusion.** Summing with $R_1 + D$ and dividing all the preceding rates by $T$ concludes the proof. □
D Technical lemmas

We recall several standard concentration inequalities and technical lemmas that are used in the proofs.

**Lemma 1 (Exponential inequality).** Let $Z$ be a positive and bounded random variable such that $0 \le Z \le D$ for some $D > 0$. Then, for every $0 \le \eta < 1/D$ one has

$$ \mathbb{E}\left[\exp\left(\eta Z - \frac{\eta \mathbb{E}[Z]}{1 - \eta D}\right)\right] \le 1. $$

*Proof.* Let $\eta > 0$. Expanding the exponential, one has by linearity of the expectation

$$ \mathbb{E}[\exp(\eta Z)] = \mathbb{E}\left[\sum_{k \ge 0} \frac{\eta^k Z^k}{k!}\right] = 1 + \sum_{k \ge 1} \frac{\eta^k}{k!} \mathbb{E}[Z^k] \quad \begin{array}{l} 0 \le Z \le D \\ \le 1 + \eta \mathbb{E}[Z] \sum_{k \ge 0} \frac{(\eta D)^k}{k!} \le 1 + \frac{\eta \mathbb{E}[Z]}{1 - \eta D} \end{array} $$

Then, using $1 + x \le \exp(x)$ and dividing by $\exp(\eta \mathbb{E}[Z]/(1 - \eta D))$ we get the desired result. $\square$

**Lemma 2.** Let $(Z_t)$ be a process adapted to the filtration $(\mathcal{F}_t)$ such that $\mathbb{E}_{t-1}[\exp(Z_t)] \le 1$. Then, one has for any $\delta \in (0, 1)$

$$ \mathbb{P}(\exists T \ge 1 : \sum_{t=1}^{T} Z_t > \log(\delta^{-1})) \le \delta. $$

**Corollary 1.** Let $0 \le Z_t \le D$. Then $\tilde{Z}_t = \frac{Z_t}{2D}$ satisfies $\mathbb{E}_{t-1}[\exp(\tilde{Z}_t - 2\mathbb{E}_{t-1}[\tilde{Z}_t])] \le 1$ and with probability $1 - \delta$

$$ \sum_{t=1}^{T} Z_t \le \sum_{t=1}^{T} 2\mathbb{E}_{t-1}Z_t + 2D \log(\delta^{-1}). $$

**Lemma 3 (Second order concentration).** Let $\delta \in (0, 1)$. For any random variables $(Z_t) \subset \mathbb{R}$ adapted to $(\mathcal{F}_t)$ and any $\gamma > 0$, one has with probability $1 - \delta$

$$ \sum_{t=1}^{T} \mathbb{E}_{t-1}[Z_t] \le \sum_{t=1}^{T} Z_t + \frac{\gamma}{2} (\mathbb{E}_{t-1}[Z_t^2] + Z_t^2) + \frac{2}{\gamma} \log(\delta^{-1}). $$

Moreover, if $(Z_t)$ are bounded as $|Z_t| \le D, D > 0$ one has with probability $1 - 2\delta$

$$ \sum_{t=1}^{T} \mathbb{E}_{t-1}[Z_t] \le \sum_{t=1}^{T} Z_t + \frac{3\gamma}{2} \mathbb{E}_{t-1}[Z_t^2] + \left(2D^2 + \frac{2}{\gamma}\right) \log(\delta^{-1}). $$

*Proof.* • First inequality: see Bercu and Touati [2008] or Wintenberger [2024, Prop. 5].

• Second inequality: Since $0 \le Z_t^2 \le D$, one has for every $t \ge 1$ by Lemma 1 on $Z_t^2$,

$$ \mathbb{E}_{t-1}[\exp(Z_t^2/(2D^2) - 2\mathbb{E}_{t-1}[Z_t^2/(2D^2)])] = \mathbb{E}_{t-1}[\exp(Z_t^2/(2D^2) - \mathbb{E}_{t-1}[Z_t^2/D^2])] \le 1. $$

Then, by Lemma 2 on $(Z_t^2/(2D^2) - \mathbb{E}[Z_t^2/D^2])$, one has

$$ \sum_{t=1}^{T} Z_t^2 \le \sum_{t=1}^{T} 2\mathbb{E}[Z_t^2] + 2D^2 \log(\delta^{-1}), $$

which gives the desired bound with a union bound.

**Lemma 4 (Sup-norm of functions and predictors).** Let $B > 0$, $f \in \mathcal{B}_{pq}^s(B)$, $s > \frac{d}{p}$ and diameters $C_{j,k} = B2^{-j\frac{d}{2}}$. Then, both $f$ and predictors $\hat{f} = \sum_{j,k} c_{j,k} \varphi_{j,k}$, $|c_{j,k}| \le C_{j,k}$ are bounded in sup-norm as follows:

$$ \|f\|_{\infty} \le B_{\infty} \quad \text{and} \quad \|\hat{f}\|_{\infty} \le \hat{B}_{\infty}, $$

$$ \text{with } B_{\infty} = \frac{BM_{\varphi}}{1-2^{-(s-\frac{d}{p})}}, \quad \hat{B}_{\infty} \le (J+1)BM_{\varphi} \quad \text{where } M_{\varphi} = \|\sum_k |\phi(\cdot - k)|\|_{\infty} \lor \|\sum_k |\psi(\cdot - k)|\|_{\infty} < \infty. $$

*Proof.* Since $f \in \mathcal{B}_{pq}^s(B)$ one has for every $j, c_j = (c_{j,k})_{k \in \Lambda_j}$

$$ \|c_j\|_{\infty} \le \|c_j\|_{p} \le B2^{-j(s-\frac{d}{p}+\frac{d}{2})}. $$
This gives

$$ \|f\|_{\infty} \le \sum_{j=j_0}^{j_0+J} \|c_j\|_{\infty} 2^{-j(s-\frac{d}{p})} \left\| \sum_k |\varphi(\cdot - k)| \right\|_{\infty} \le BM_{\varphi} \sum_{j=j_0}^{j_0+J} 2^{-j(s-\frac{d}{p})} \le \frac{BM_{\varphi}}{1-2^{-(s-\frac{d}{p})}} $$

and

$$ \|\hat{f}\|_{\infty} \le \sum_{j=j_0}^{j_0+J} |c_{j,k}| 2^{j\frac{d}{2}} \left\| \sum_k |\varphi(\cdot - k)| \right\|_{\infty} \le BM_{\varphi} \sum_{j=j_0}^{j_0+J} 1 \le BM_{\varphi}(J+1). $$

□
E Review of multi-resolution analysis

In this section we present some of the basic ingredients of wavelet theory. Let's assume we have a multivariate function $f: \mathbb{R}^d \to \mathbb{R}$.

**Definition 1 (Scaling function).** We say that a function $\phi \in L^2(\mathbb{R}^d)$ is the scaling function of a multiresolution analysis (MRA) if it satisfies the following conditions:

1. the family

$$ \{x \mapsto \phi(x-k) = \prod_{i=1}^{d} \phi(x_i - n_i) : k \in \mathbb{Z}^d\} $$

is an ortho-normal basis, that is $\langle \phi(\cdot - k), \phi(\cdot - n) \rangle = \delta_{k,n}$;

2. the linear spaces

$$ V_0 = \{f = \sum_{k \in \mathbb{Z}^d} c_k \phi(\cdot - k), (c_k) : \sum_{k \in \mathbb{Z}^d} c_k^2 < \infty\}, \dots, V_j = \{h = f(2^{j\cdot}) : f \in V_0\}, \dots, $$

are nested, i.e. $V_{j-1} \subset V_j$ for all $j \ge 0$.

We note that under these two conditions, it is immediate that the functions

$$ \{\phi_{j,k} = 2^{dj/2} \phi(2^j \cdot - k), k \in \mathbb{Z}^d\} $$

form an ortho-normal basis of the space $V_j, j \in \mathbb{N}$. One can define the projection kernel of $f$ over $V_j$ (from here we also say kernel projection at scale or level $j$) as

$$ K_j f(x) := \sum_{k \in \mathbb{Z}^d} \langle f, \phi_{j,k} \rangle \phi_{j,k}(x) = \int_{\mathbb{R}^d} K_j(x, y) f(y) dy, \quad (37) $$

with $K_j(x, y) = \sum_{n \in \mathbb{Z}^d} \phi_{j,k}(x)\phi_{j,k}(y) = \sum_{k \in \mathbb{Z}^d} 2^{dj} \phi(2^j x - n)\phi(2^j y - n)$ (which is not of convolution type) but has comparable approximation properties that we detail after.

**Incremental construction via wavelets.** Since the spaces $(V_j)$ are nested, one can define nontrivial subspaces as the orthogonal complements $W_j := V_{j+1} \ominus V_j$. We can then telescope these orthogonal complements to see that each space $V_j, j \ge j_0$ can be written as

$$ V_j = V_{j_0} \oplus \left( \bigoplus_{l=j_0}^{j} W_l \right) \quad \text{for any } j_0 \in \mathbb{N}. $$

Let $\psi$ be a mother wavelet corresponding to the scaling function $\phi$. The associated wavelets are defined as follows: for $E = \{0, 1\}^d \setminus \{0\}$, we set

$$ \psi^{\epsilon}(x) = \psi^{\epsilon_1}(x_1) \cdots \psi^{\epsilon_d}(x_d), \quad \psi^{\epsilon}_{j,n} = 2^{jd/2} \psi^{\epsilon}(2^j x - n), \quad j \ge 0, \quad n \in \mathbb{Z}^d, $$

where $\psi^0 = \phi$, $\psi^1 = \psi$. For each $j$, these functions form an orthonormal basis of $W_j$.

Analogously, one can now observe that for every $j \ge j_0$,

$$ K_j f = K_{j_0} f + \sum_{l=j_0}^{j-1} (K_{l+1} f - K_l f), \quad (38) $$

where each increment in the sum can be written as

$$ K_{j+1} f - K_j f = \sum_k \sum_\epsilon \langle f, \psi_{j,k}^\epsilon \rangle \psi_{j,k}^\epsilon, $$

where for each $j \ge 1$, the set

$$ \{\psi_{j,k}^\epsilon = 2^{dj/2} \psi^\epsilon(2^j x - k) : \epsilon \in E, k \in \mathbb{Z}^d\} $$

forms a basis of $W_j$ for some wavelet $\psi$, with $E := \{0, 1\}^d \setminus \{0\}$. For simplicity, we include the index $\epsilon$ in the multi-index $k$. Finally, the set $\{\phi_{j_0,k}, \psi_{j,k}\}$ constitutes a wavelet basis.

For our results we will not be needing a particular wavelet basis, but any that satisfies the following key properties.
**Definition 2** (S-regular wavelet basis). Let $S \in \mathbb{N}^*$ and $j_0 = 0$. The multiresolution wavelet basis

$$ \{\phi_k = \phi(\cdot - k), \psi_{j,k} = 2^{jd/2}\psi(2^d \cdot -k)\} $$

of $L^2(\mathbb{R}^d)$ with associated projection kernel $K(x, y) = \sum_k \phi_k(x)\phi_k(y)$ is said to be S-regular if the following conditions are satisfied:

(D.1) **Vanishing moments and normalization:**

$$ \int_{\mathbb{R}^d} \psi(x) x^\alpha dx = 0 \quad \text{for all multi-indices } \alpha \text{ with } |\alpha| < S, \quad \int_{\mathbb{R}^d} \phi(x) dx = 1. $$

Moreover, for all $v \in \mathbb{R}^d$ and $\alpha$ with $1 \le |\alpha| < S$,

$$ \int_{\mathbb{R}^d} K(v, v+u) du = 1, \quad \int_{\mathbb{R}^d} K(v, v+u) u^\alpha du = 0. $$

(D.2) **Bounded basis sums:**

$$ M_\phi := \sup_{x \in \mathbb{R}^d} \sum_k |\phi(x-k)| < \infty, \quad M_\psi := \sup_{x \in \mathbb{R}^d} \sum_k |\psi(x-k)| < \infty. $$

(D.3) **Kernel decay:** For $\kappa(x, y)$ equal to $K(x, y)$ or $\sum_k \psi(x-k)\psi(y-k)$, there exist constants $c_1, c_2 > 0$ and a bounded integrable function $\phi: [0, \infty) \to \mathbb{R}$ such that

$$ \sup_{v \in \mathbb{R}^d} |\kappa(v, v-u)| \le c_1 \phi(c_2 \|u\|), \quad C_S := \int_{\mathbb{R}^d} \|u\|^S \phi(\|u\|) du < \infty. $$

**Case of a bounded compact** $\mathcal{X} \subset \mathbb{R}^d$. The above definition applies to wavelet systems on $\mathbb{R}^d$, but can be extended to compact domains $\mathcal{X} \subset \mathbb{R}^d$ using standard boundary-corrected or periodized constructions. Notable examples include the compactly supported orthonormal wavelets of ?, Chapter 7 and the biorthogonal, symmetric, and highly regular wavelet bases of ?. At the j-th level, there are now $O(2^{jd})$ wavelets $\psi_{j,k}$, which we index by $k \in \Lambda_j$, the set of indices corresponding to wavelets at level j. This coincides with the expansion used in Equation (5).