Proof. Let us recall the notations of van der Hoeven et al. (2023) in order to apply the Theorem 1 of their paper. Let $\tilde{\ell}_t$ denote the shifted loss as in van der Hoeven et al. (2023)

$$ \tilde{\ell}_t(g) = \ell_t \left( \frac{1}{2} g + \frac{1}{2} \hat{g}_t \right) = \left\| \frac{1}{2} g(x_t) + \frac{1}{2} \hat{g}_t(x_t) - \varphi_t \right\|_{\mathcal{H}}^2. \quad (54) $$

We defined $R_T(\lambda, m)$ such that

$$ \sum_{t=1}^{T} \tilde{\ell}_t(\hat{g}_t(x_t)) - \tilde{\ell}_t(g_t^*) \le R_T(\lambda, m) $$

with the only assumption on $(g_t^*)_t$ that they are functions in the space $\mathcal{G}$. Using the convexity of $\tilde{\ell}$, we use Jensen inequality

$$ \tilde{\ell}(\mathbb{E}_{g \sim Q_t}[g]) \le \mathbb{E}_{g \sim Q_t}[\tilde{\ell}(g)], $$

where $(Q_t)_t$ are some distributions over $\mathcal{G}$, and by convexity of the space $\mathcal{G}$ we have that $\mathbb{E}_{g \sim Q_t}[g] \in \mathcal{G}$. We derive the following inequality

$$ \sum_{t=1}^{T} \tilde{\ell}_t(\hat{g}_t) - \mathbb{E}_{g \sim Q_t}[\tilde{\ell}_t(g)] \le \sum_{t=1}^{T} \tilde{\ell}_t(\hat{g}_t) - \tilde{\ell}(\mathbb{E}_{g \sim Q_t}[g]) \le R_T(\lambda, m). $$

We now remark that the proof of the Theorem 1 of van der Hoeven et al. (2023) can be applied with a non-stationary baseline $(Q_t)_t$ instead of $Q$. This concludes the proof. □

We use this lemma and a comparison inequality to bound the cumulative risk of the predictors.

**Theorem 13 (Expected Regret in a Non-Stationary Environment).** Assume that there exists $(g_t^*)$ a sequence in $\mathcal{G}$ such that $\mathbb{E}[\sum_{t=1}^T \|g_t^*(x_t) - \mathbb{E}[\varphi_t|x_t]\|_{\mathcal{H}}^2] = 0$. Let $\delta \in (0, 1]$. Then, Algorithm 3 run with $\lambda > 0$ and $\eta = 1/2(\kappa \sup_{\|g\|_{\mathcal{G}} + 1)^2}$ satisfies with probability $1 - \delta$

$$ \mathbb{E}[R_T] = \begin{cases} \tilde{O}\left(V_G^{1/6}T^{5/6} + T^{1/2}\sqrt{\log(\delta^{-1})}\right) & \text{if } \lambda = V_G^{-1/3}T^{1/3} \\ \tilde{O}\left(V_0^{1/4}T^{3/4} + T^{1/2}\sqrt{\log(\delta^{-1})}\right) & \text{if } \lambda = V_0^{-1/2}T^{1/2} \end{cases}. \quad (55) $$

Precisely, let $\gamma$ let be defined as in Eq. (33), if $\lambda = V_G^{-1/3}T^{1/3}$ we have

$$ \sum_{t=1}^{T} \mathbb{E}_t[\Delta(\hat{f}_t(x_t), y_t) - \Delta(f_t^*(x_t), y_t)] \\ \le 2c_{\Delta}\sqrt{2T} \left( \frac{[V_G^{2/3}T^{1/3}\kappa^{-2/3}] \log T}{\eta} + (1 + \kappa \sup_{\|g\|_{\mathcal{G}}} \kappa^{5/3}V_G^{1/3}T^{2/3}} \right. \\ \left. + (V_G^{2/3}T^{4/3}\kappa^{-2/3} + T)^{1/2} \frac{\kappa^2 B^2}{16} \log \left( e + \frac{e\kappa^2}{4}(V_G^{2/3}T^{4/3}\kappa^{-2/3} + T)^{1/2} \right) \right. \\ \left. + (V_G^{2/3}T^{4/3}\kappa^{-2/3} + T)^{1/2} \max_{t \in [T]} \|g_t^*\|_{\mathcal{G}}^2 + \gamma \log(\delta^{-1}) \right)^{1/2}, $$

and if $\lambda = V_0^{-1/2}T^{1/2}$ we have

$$ \sum_{t=1}^{T} \mathbb{E}_t[\Delta(\hat{f}_t(x_t), y_t) - \Delta(f_t^*(x_t), y_t)] \\ \le 2c_{\Delta}\sqrt{2T} \left( \frac{V_0 \log T}{\eta} + \frac{B^2 \kappa^2 \sqrt{T V_0}}{16} \log \left( e + \frac{e \kappa^2 \sqrt{T V_0}}{4} \right) + \sqrt{T V_0} \max_i \|\bar{g}_{t_i:t_{i+1}}\|^2 + \gamma \log(\delta^{-1}) \right)^{1/2}. $$
Proof. Step 1: Controlling the regret of $(f_t)_t$ by the regret of $(\hat{g}_t)_t$. From Lemma 8, we have

$$
\begin{align*}
& \sum_{t=1}^{T} \mathbb{E}_t[\Delta(\hat{f}_t(x_t), y_t) - \Delta(f_t^*(x_t), y_t)] \\
& \le 2c_\Delta \sqrt{T} \sqrt{\sum_{t=1}^{T} \mathbb{E}_t[\|\hat{g}_t(x_t) - \mathbb{E}[\varphi_t|x_t]\|_{\mathcal{H}}^2]} \\
& = 2c_\Delta \sqrt{T} \sqrt{\sum_{t=1}^{T} \mathbb{E}_t[\|\hat{g}_t(x_t) - \mathbb{E}[\varphi_t|x_t]\|_{\mathcal{H}}^2 - \|g_t^*(x_t) - \mathbb{E}[\varphi_t|x_t]\|_{\mathcal{H}}^2 + \|g_t^*(x_t) - \mathbb{E}[\varphi_t|x_t]\|_{\mathcal{H}}^2]} \\
& = 2c_\Delta \sqrt{T} \sqrt{\sum_{t=1}^{T} \mathbb{E}_t[\|\hat{g}_t(x_t) - \varphi_t\|_{\mathcal{H}}^2 - \|g_t^*(x_t) - \varphi_t\|_{\mathcal{H}}^2] + \mathbb{E}_t[\|g_t^*(x_t) - \mathbb{E}[\varphi_t|x_t]\|_{\mathcal{H}}^2]}.
\end{align*}
$$

We may now apply Lemma 12 to obtain

$$
\begin{align}
& \sum_{t=1}^{T} \mathbb{E}_t[\Delta(\hat{f}_t(x_t), y_t) - \Delta(f_t^*(x_t), y_t)] \nonumber \\
& \le 2c_\Delta \sqrt{T} \sqrt{2R_T(\lambda, m) + 2\gamma \log(\delta^{-1}) + \sum_{t=1}^{T} \|g_t^*(x_t) - \mathbb{E}[\varphi_t|x_t]\|_{\mathcal{H}}^2} \tag{56}
\end{align}
$$

where $R_T(\lambda, m)$ is defined as

$$
R_T(\lambda, m) = \frac{m \log T}{\eta} + \frac{B^2}{4} \log \left( e + \frac{e \kappa^2 T}{4 \lambda} \right) \sum_{i=1}^{m} d_{\text{eff}}(4\lambda, t_{i+1} - t_i) + \lambda m \max_{t \in [T]} \|g_t^*\|_G^2 + \frac{(1+\kappa \sup \|g\|_G) \kappa V_G T}{m}
$$

and comes from Proposition 11 for shifted losses.

**Case 1: Continuous variations.** We bound the effective dimension by $d_{\text{eff}}(4\lambda, t_{i+1} - t_i) \le \frac{\kappa^2(t_{i+1} - t_i)}{4\lambda}$. Thus we can bound the sum by $\sum_{i=1}^m d_{\text{eff}}(4\lambda, t_{i+1} - t_i) \le \kappa^2 T/4\lambda$ and obtain

$$
R_T(\lambda, m) \le \frac{m \log T}{\eta} + \frac{B^2}{4} \log \left( e + \frac{e \kappa^2 T}{4 \lambda} \right) \frac{\kappa^2 T}{4 \lambda} + \lambda m \max_{t \in [T]} \|g_t^*\|_G^2 + \frac{(1 + \kappa \sup \|g\|_G) \kappa V_G T}{m}.
$$

We choose $\lambda = \sqrt{T/m}$ and get

$$
R_T(\lambda, m) \le \frac{m \log T}{\eta} + \frac{B^2}{4} \log \left( e + \frac{e \kappa^2 \sqrt{Tm}}{4} \right) \frac{\kappa^2 \sqrt{Tm}}{4} + \sqrt{Tm} \max_{t \in [T]} \|g_t^*\|_G^2 + \frac{(1 + \kappa \sup \|g\|_G) \kappa V_G T}{m}.
$$

We choose $m = \lceil V_G^{2/3} T^{1/3} \kappa^{-2/3} \rceil$ and get

$$
R_T(\lambda, m) \le \frac{[V_G^{2/3} T^{1/3} \kappa^{-2/3}] \log T}{\eta} + (1 + \kappa \sup \|g\|_G) \kappa^{5/3} V_G^{1/3} T^{2/3} \\
+ (V_G^{2/3} T^{4/3} \kappa^{-2/3} + T)^{1/2} \left( \frac{\kappa^2 B^2}{16} \log \left( e + \frac{e \kappa^2}{4} (V_G^{2/3} T^{4/3} \kappa^{-2/3} + T)^{1/2} \right) + \max_{t \in [T]} \|g_t^*\|_G^2 \right).
$$

We conclude by noting that $V_G \le (2T - 1) \sup \|g\|_G$.

**Case 2: Discrete variations.** In the case of discrete distributions data variations there is no more need to approximate the data distributions $(g_t^*)_t$ by the hypothetical forecasters $(\tilde{g}_{t_i:t_{i+1}})_i$. Thus the third term of the sum in Eq. (41) is not necessary. And we can replace $R_T(\lambda, m)$ by $R_T^0(\lambda, V_0)$ defined as

$$
R_T^0(\lambda, V_0) := \frac{V_0 \log T}{\eta} + \frac{B^2}{4} \log \left( e + \frac{e \kappa^2 T}{4 \lambda} \right) \sum_{i=1}^{V_0} d_{\text{eff}}(4\lambda, t_{i+1} - t_i) + \lambda \sum_{i=1}^{V_0} \|\tilde{g}_{t_i:t_{i+1}}\|_G^2.
$$
Proof. Step 1: Controlling the regret of $(f_t)_t$ by the regret of $(\hat{g}_t)_t$. From Lemma 8, we have

$$
\begin{align*}
& \sum_{t=1}^{T} \mathbb{E}_t[\Delta(\hat{f}_t(x_t), y_t) - \Delta(f_t^*(x_t), y_t)] \\
& \le 2c_\Delta \sqrt{T} \sqrt{\sum_{t=1}^{T} \mathbb{E}_t[\|\hat{g}_t(x_t) - \mathbb{E}[\varphi_t|x_t]\|_{\mathcal{H}}^2]} \\
& = 2c_\Delta \sqrt{T} \sqrt{\sum_{t=1}^{T} \mathbb{E}_t[\|\hat{g}_t(x_t) - \mathbb{E}[\varphi_t|x_t]\|_{\mathcal{H}}^2 - \|g_t^*(x_t) - \mathbb{E}[\varphi_t|x_t]\|_{\mathcal{H}}^2 + \|g_t^*(x_t) - \mathbb{E}[\varphi_t|x_t]\|_{\mathcal{H}}^2]} \\
& = 2c_\Delta \sqrt{T} \sqrt{\sum_{t=1}^{T} \mathbb{E}_t[\|\hat{g}_t(x_t) - \varphi_t\|_{\mathcal{H}}^2 - \|g_t^*(x_t) - \varphi_t\|_{\mathcal{H}}^2] + \mathbb{E}_t[\|g_t^*(x_t) - \mathbb{E}[\varphi_t|x_t]\|_{\mathcal{H}}^2]}.
\end{align*}
$$

We may now apply Lemma 12 to obtain

$$
\begin{align}
& \sum_{t=1}^{T} \mathbb{E}_t[\Delta(\hat{f}_t(x_t), y_t) - \Delta(f_t^*(x_t), y_t)] \nonumber \\
& \le 2c_\Delta \sqrt{T} \sqrt{2R_T(\lambda, m) + 2\gamma \log(\delta^{-1}) + \sum_{t=1}^{T} \|g_t^*(x_t) - \mathbb{E}[\varphi_t|x_t]\|_{\mathcal{H}}^2} \tag{56}
\end{align}
$$

where $R_T(\lambda, m)$ is defined as

$$
R_T(\lambda, m) = \frac{m \log T}{\eta} + \frac{B^2}{4} \log \left( e + \frac{e \kappa^2 T}{4 \lambda} \right) \sum_{i=1}^{m} d_{\text{eff}}(4\lambda, t_{i+1} - t_i) + \lambda m \max_{t \in [T]} \|g_t^*\|_G^2 + \frac{(1+\kappa \sup \|g\|_G) \kappa V_G T}{m}
$$

and comes from Proposition 11 for shifted losses.

**Case 1: Continuous variations.** We bound the effective dimension by $d_{\text{eff}}(4\lambda, t_{i+1} - t_i) \le \frac{\kappa^2(t_{i+1} - t_i)}{4\lambda}$. Thus we can bound the sum by $\sum_{i=1}^m d_{\text{eff}}(4\lambda, t_{i+1} - t_i) \le \kappa^2 T/4\lambda$ and obtain

$$
R_T(\lambda, m) \le \frac{m \log T}{\eta} + \frac{B^2}{4} \log \left( e + \frac{e \kappa^2 T}{4 \lambda} \right) \frac{\kappa^2 T}{4 \lambda} + \lambda m \max_{t \in [T]} \|g_t^*\|_G^2 + \frac{(1 + \kappa \sup \|g\|_G) \kappa V_G T}{m}.
$$

We choose $\lambda = \sqrt{T/m}$ and get

$$
R_T(\lambda, m) \le \frac{m \log T}{\eta} + \frac{B^2}{4} \log \left( e + \frac{e \kappa^2 \sqrt{Tm}}{4} \right) \frac{\kappa^2 \sqrt{Tm}}{4} + \sqrt{Tm} \max_{t \in [T]} \|g_t^*\|_G^2 + \frac{(1 + \kappa \sup \|g\|_G) \kappa V_G T}{m}.
$$

We choose $m = \lceil V_G^{2/3} T^{1/3} \kappa^{-2/3} \rceil$ and get

$$
R_T(\lambda, m) \le \frac{[V_G^{2/3} T^{1/3} \kappa^{-2/3}] \log T}{\eta} + (1 + \kappa \sup \|g\|_G) \kappa^{5/3} V_G^{1/3} T^{2/3} \\
+ (V_G^{2/3} T^{4/3} \kappa^{-2/3} + T)^{1/2} \left( \frac{\kappa^2 B^2}{16} \log \left( e + \frac{e \kappa^2}{4} (V_G^{2/3} T^{4/3} \kappa^{-2/3} + T)^{1/2} \right) + \max_{t \in [T]} \|g_t^*\|_G^2 \right).
$$

We conclude by noting that $V_G \le (2T - 1) \sup \|g\|_G$.

**Case 2: Discrete variations.** In the case of discrete distributions data variations there is no more need to approximate the data distributions $(g_t^*)_t$ by the hypothetical forecasters $(\tilde{g}_{t_i:t_{i+1}})_i$. Thus the third term of the sum in Eq. (41) is not necessary. And we can replace $R_T(\lambda, m)$ by $R_T^0(\lambda, V_0)$ defined as

$$
R_T^0(\lambda, V_0) := \frac{V_0 \log T}{\eta} + \frac{B^2}{4} \log \left( e + \frac{e \kappa^2 T}{4 \lambda} \right) \sum_{i=1}^{V_0} d_{\text{eff}}(4\lambda, t_{i+1} - t_i) + \lambda \sum_{i=1}^{V_0} \|\tilde{g}_{t_i:t_{i+1}}\|_G^2.
$$
We bound the effective dimension by $d_{\text{eff}}(4\lambda, t_{i+1}-t_i) \le \frac{\kappa^2(t_{i+1}-t_i)}{4\lambda}$. Thus we bound the sum by $\sum_{i=1}^{V_0} d_{\text{eff}}(4\lambda, t_{i+1}-t_i) \le \kappa^2 T/4\lambda$ and obtain

$$R_T^0(\lambda, V_0) \le \frac{V_0 \log T}{\eta} + \frac{B^2 \kappa^2 T}{16\lambda} \log \left( e + \frac{e \kappa^2 T}{4\lambda} \right) + \lambda V_0 \max_{i \in [V_0]} \| \bar{g}_{t_i:t_{i+1}} \|_{\mathcal{G}}^2. \quad (57)$$

By choosing $\lambda = \sqrt{T/V_0}$, we get

$$R_T^0(\lambda, V_0) \le \frac{V_0 \log T}{\eta} + \frac{B^2 \kappa^2 \sqrt{T V_0}}{16} \log \left( e + \frac{e \kappa^2 \sqrt{T V_0}}{4} \right) + \sqrt{T V_0} \max_{i \in [V_0]} \| \bar{g}_{t_i:t_{i+1}} \|_{\mathcal{G}}^2. \quad (58)$$

We then bound the cumulative risk using Step 1.

$$\sum_{t=1}^{T} \mathbb{E}_t[\Delta(\hat{f}_t(x_t), y_t) - \Delta(f_t^*(x_t), y_t)] \\ \le 2c_{\Delta} \sqrt{2T} \sqrt{\frac{V_0 \log T}{\eta} + \frac{B^2 \kappa^2 \sqrt{T V_0}}{16} \log \left( e + \frac{e \kappa^2 \sqrt{T V_0}}{4} \right) + \sqrt{T V_0} \max_{i \in [V_0]} \| \bar{g}_{t_i:t_{i+1}} \|_{\mathcal{G}}^2 + \gamma \log(\delta^{-1})}$$

We now note that $V_0 \le T$ to conclude the proof. $\square$

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

## E.1 Refined Regret Bounds

In this section we assume that the capacity condition holds and we derive refined bounds of the cumulative risk. For more details about the capacity condition see Appendix D.1. Assuming that there exists $(g_t^*)$ a sequence in $\mathcal{G}$ such that $\mathbb{E}[\sum_{t=1}^T \|g_t^*(x_t) - \mathbb{E}[\varphi_t|x_t]\|_{\mathcal{H}}^2] = 0$. Let $\delta \in (0, 1]$. Then choosing $\lambda = T^{\frac{\beta}{\beta+1}} m^{\frac{-\beta}{\beta+1}}$ and $m = \left\lceil V_{\mathcal{G}}^{\frac{\beta+1}{\beta+2}} T^{\frac{1}{\beta+2}} \kappa^{\frac{-(\beta+1)}{\beta+2}} \right\rceil$ leads to the following bound on the expected regret with probability $1 - \delta$

$$\sum_{t=1}^{T} \mathbb{E}_t[\Delta(\hat{f}_t(x_t), y_t) - \Delta(f_t^*(x_t), y_t)] = \tilde{O} \left( V_{\mathcal{G}}^{\frac{1}{2(\beta+2)}} T^{\frac{2\beta+3}{2(\beta+2)}} + T^{1/2} \sqrt{\log(\delta^{-1})} \right). \quad (59)$$

Indeed using the capacity condition, we bound the effective dimension by $d_{\text{eff}}(4\lambda, t_{i+1} - t_i) \le Q \left( \frac{t_{i+1} - t_i}{4\lambda} \right)^{\beta}$. Using Jensen's inequality, we then derive

$$\begin{aligned} \sum_{i=1}^{m} d_{\text{eff}}(4\lambda, t_{i+1} - t_i) &\le Q \sum_{i=1}^{m} \left( \frac{t_{i+1} - t_i}{4\lambda} \right)^{\beta} \\ &= Qm \sum_{i=1}^{m} \frac{1}{m} \left( \frac{t_{i+1} - t_i}{4\lambda} \right)^{\beta} \\ &\le Qm \left( \sum_{i=1}^{m} \frac{t_{i+1} - t_i}{4\lambda m} \right)^{\beta} \\ &= Qm^{1-\beta} \left( \frac{T}{4\lambda} \right)^{\beta}. \end{aligned}$$

We obtain

$$R_T(\lambda, m) \le \frac{m \log T}{\eta} + \frac{QB^2}{4} m^{1-\beta} \left(\frac{T}{4\lambda}\right)^{\beta} \log \left(e + \frac{e \kappa^2 T}{4\lambda}\right) + \lambda m \max_{t \in [T]} \|g_t^*\|_{\mathcal{G}}^2 + \frac{(1+\kappa \sup_{\|g\|_{\mathcal{G}}) \kappa V_{\mathcal{G}} T}}{m}.$$

We choose $\lambda = T^{\frac{\beta}{\beta+1}} m^{\frac{-\beta}{\beta+1}}$, and obtain

$$R_T(\lambda, m) \le \frac{m \log T}{\eta} + \frac{(1+\kappa \sup_{\|g\|_{\mathcal{G}}) \kappa V_{\mathcal{G}} T}}{m} + m^{\frac{1}{\beta+1}} T^{\frac{\beta}{\beta+1}} \left( \frac{QB^2 4^{-\beta}}{4} \log \left( e + \frac{e \kappa^2}{4} m^{\frac{\beta}{\beta+1}} T^{\frac{1}{\beta+1}} \right) + \max_{t \in [T]} \|g_t^*\|_{\mathcal{G}}^2 \right).$$
We bound the effective dimension by $d_{\text{eff}}(4\lambda, t_{i+1}-t_i) \le \frac{\kappa^2(t_{i+1}-t_i)}{4\lambda}$. Thus we bound the sum by $\sum_{i=1}^{V_0} d_{\text{eff}}(4\lambda, t_{i+1}-t_i) \le \kappa^2 T/4\lambda$ and obtain

$$R_T^0(\lambda, V_0) \le \frac{V_0 \log T}{\eta} + \frac{B^2 \kappa^2 T}{16\lambda} \log \left( e + \frac{e \kappa^2 T}{4\lambda} \right) + \lambda V_0 \max_{i \in [V_0]} \|\bar{g}_{t_i:t_{i+1}}\|_{\mathcal{G}}^2. \quad (57)$$

By choosing $\lambda = \sqrt{T/V_0}$, we get

$$R_T^0(\lambda, V_0) \le \frac{V_0 \log T}{\eta} + \frac{B^2 \kappa^2 \sqrt{T V_0}}{16} \log \left( e + \frac{e \kappa^2 \sqrt{T V_0}}{4} \right) + \sqrt{T V_0} \max_{i \in [V_0]} \|\bar{g}_{t_i:t_{i+1}}\|_{\mathcal{G}}^2. \quad (58)$$

We then bound the cumulative risk using Step 1.

$$\sum_{t=1}^{T} \mathbb{E}_t[\Delta(\hat{f}_t(x_t), y_t) - \Delta(f_t^*(x_t), y_t)] \\ \le 2c_{\Delta} \sqrt{2T} \sqrt{\frac{V_0 \log T}{\eta} + \frac{B^2 \kappa^2 \sqrt{T V_0}}{16} \log \left( e + \frac{e \kappa^2 \sqrt{T V_0}}{4} \right) + \sqrt{T V_0} \max_{i \in [V_0]} \|\bar{g}_{t_i:t_{i+1}}\|_{\mathcal{G}}^2 + \gamma \log(\delta^{-1})}$$

We now note that $V_0 \le T$ to conclude the proof. $\square$

## E.1 Refined Regret Bounds

In this section we assume that the capacity condition holds and we derive refined bounds of the cumulative risk. For more details about the capacity condition see Appendix D.1. Assuming that there exists $(g_t^*)$ a sequence in $\mathcal{G}$ such that $\mathbb{E}[\sum_{t=1}^T \|g_t^*(x_t) - \mathbb{E}[\varphi_t|x_t]\|_{\mathcal{H}}^2] = 0$. Let $\delta \in (0, 1]$. Then choosing $\lambda = T^{\frac{\beta}{\beta+1}} m^{\frac{-\beta}{\beta+1}}$ and $m = \lceil V_{\mathcal{G}}^{\frac{\beta+1}{2}} T^{\frac{1}{\beta+2}} \kappa^{\frac{-(\beta+1)}{\beta+2}} \rceil$ leads to the following bound on the expected regret with probability $1 - \delta$

$$\sum_{t=1}^{T} \mathbb{E}_t[\Delta(\hat{f}_t(x_t), y_t) - \Delta(f_t^*(x_t), y_t)] = \tilde{O} \left( V_{\mathcal{G}}^{\frac{1}{2(\beta+2)}} T^{\frac{2\beta+3}{2(\beta+2)}} + T^{1/2} \sqrt{\log(\delta^{-1})} \right). \quad (59)$$

Indeed using the capacity condition, we bound the effective dimension by $d_{\text{eff}}(4\lambda, t_{i+1} - t_i) \le Q \left( \frac{t_{i+1} - t_i}{4\lambda} \right)^{\beta}$. Using Jensen's inequality, we then derive

$$\begin{aligned} \sum_{i=1}^{m} d_{\text{eff}}(4\lambda, t_{i+1} - t_i) &\le Q \sum_{i=1}^{m} \left( \frac{t_{i+1} - t_i}{4\lambda} \right)^{\beta} \\ &= Qm \sum_{i=1}^{m} \frac{1}{m} \left( \frac{t_{i+1} - t_i}{4\lambda} \right)^{\beta} \\ &\le Qm \left( \sum_{i=1}^{m} \frac{t_{i+1} - t_i}{4\lambda m} \right)^{\beta} \\ &= Qm^{1-\beta} \left( \frac{T}{4\lambda} \right)^{\beta}. \end{aligned}$$

We obtain

$$R_T(\lambda, m) \le \frac{m \log T}{\eta} + \frac{QB^2}{4} m^{1-\beta} \left(\frac{T}{4\lambda}\right)^{\beta} \log \left(e + \frac{e \kappa^2 T}{4\lambda}\right) + \lambda m \max_{t \in [T]} \|g_t^*\|_{\mathcal{G}}^2 + \frac{(1+\kappa \sup_{\|g\|_{\mathcal{G}})} \kappa V_{\mathcal{G}} T}{m}.$$

We choose $\lambda = T^{\frac{\beta}{\beta+1}} m^{\frac{-\beta}{\beta+1}}$, and obtain

$$R_T(\lambda, m) \le \frac{m \log T}{\eta} + \frac{(1+\kappa \sup_{\|g\|_{\mathcal{G}})} \kappa V_{\mathcal{G}} T}{m} + m^{\frac{1}{\beta+1}} T^{\frac{\beta}{\beta+1}} \left( \frac{QB^2 4^{-\beta}}{4} \log \left( e + \frac{e \kappa^2}{4} m^{\frac{\beta}{\beta+1}} T^{\frac{1}{\beta+1}} \right) + \max_{t \in [T]} \|g_t^*\|_{\mathcal{G}}^2 \right).$$
We choose $m = \left[ V_G^{\frac{\beta+1}{\beta+2}} T^{\frac{1}{\beta+2}} \kappa^{\frac{-(\beta+1)}{\beta+2}} \right]$ to obtain

$$R_T(\lambda, m) \le \frac{\left[ V_G^{\frac{\beta+1}{\beta+2}} T^{\frac{1}{\beta+2}} \kappa^{\frac{-(\beta+1)}{\beta+2}} \right] \log T}{\eta} + (1 + \kappa \sup \|g\|_G) \kappa^{\frac{2\beta+3}{\beta+2}} V_G^{\frac{1}{\beta+2}} T^{\frac{\beta+1}{\beta+2}} \\ + \left( V_G^{\frac{1}{\beta+2}} T^{\frac{\beta+1}{\beta+2}} \kappa^{\frac{-1}{\beta+2}} + T^{\frac{\beta}{\beta+1}} \right) \left( \frac{Q B^2 4^{-\beta}}{4} \log \left( e + e^{\frac{2\beta+3}{\beta+2} V_G^{\frac{\beta}{\beta+2}} T^{\frac{2}{\beta+2}} + T^{\frac{1}{\beta+1}}} \right) + \max_{t \in [T]} \|g_t^*\|_G^2 \right).$$

We conclude by noting that $V_G = \|g_1^*\|_G + \sum_{t=2}^T \|g_t^* - g_{t-1}^*\|_G \le (2T - 1) \sup \|g\|_G$.
We choose $m = \left[ V_G^{\frac{\beta+1}{2}} T^{\frac{1}{\beta+2}} \kappa^{\frac{-(\beta+1)}{\beta+2}} \right]$ to obtain

$$R_T(\lambda, m) \le \frac{\left[ V_G^{\frac{\beta+1}{2}} T^{\frac{1}{\beta+2}} \kappa^{\frac{-(\beta+1)}{\beta+2}} \right] \log T}{\eta} + (1 + \kappa \sup \|g\|_G) \kappa^{\frac{2\beta+3}{\beta+2}} V_G^{\frac{1}{\beta+2}} T^{\frac{\beta+1}{\beta+2}} \\ + \left( V_G^{\frac{1}{\beta+2}} T^{\frac{\beta+1}{\beta+2}} \kappa^{\frac{-1}{\beta+2}} + T^{\frac{\beta}{\beta+1}} \right) \left( \frac{QB^2 4^{-\beta}}{4} \log \left( e + e^{\frac{2\beta+3}{\beta+2} V_G^{\frac{\beta}{\beta+2}} T^{\frac{2}{\beta+2}} + T^{\frac{1}{\beta+1}}} \right) + \max_{t \in [T]} \|g_t^*\|_G^2 \right).$$

We conclude by noting that $V_G = \|g_1^*\|_G + \sum_{t=2}^T \|g_t^* - g_{t-1}^*\|_G \le (2T - 1) \sup \|g\|_G$.