## B.2 Tightness.

### Proof of Theorem 2.2.

*Proof.* Proof. We now provide an example of a sequence of problems, with a C-contractive algorithm, such that the bound given in Theorem 2.1 is tight. Our example is an elementary analysis of gradient descent on a sequence of 1-dimensional quadratic optimization problems, where the optima drift linearly. Consider a sequence of quadratic functions over $\mathbb{R}$ defined by

$$f_t(x) = \frac{(x - c_t)^2}{2};$$

for our example, let us assume that $(c_t)$ forms an arithmetic progression with common difference $-b$, i.e., $c_{t+1} = c_t - b$ for all $t \ge 1$. Consider also the gradient descent algorithm started at $x_1 \in \mathbb{R}$, and assume furthermore that $x_1 - c_1 \ge b/(1-C)$.

Then for any $t \in \mathbb{R}$, gradient descent started at $x_1 \in \mathbb{R}$ with step-size $(1-C) \in (0, 1]$ is a C-contraction since for any $t \ge 1$, the update rule is

$$x_{t+1} - c_t = x_t - (1-C)(x_t - c_t) - c_t = C(x_t - c_t).$$

Let us introduce the short-hand notation $d_t = x_t - c_t$. Then for any $t \ge 1$,

$$d_{t+1} = x_{t+1} - c_{t+1} = x_{t+1} - c_t + c_t - c_{t+1} = C d_t + b$$

The sequence $(d_t)$ therefore forms an arithmetico-geometric progression and so for any $t \ge 1$, using our assumption that $x_1 - c_1 \ge b/(1-C)$,

$$d_t - \frac{b}{1-C} = C^{t-1} \left( d_1 - \frac{b}{1-C} \right) \ge 0.$$

Therefore, for any $t \ge 1$, the squared-error $d_t^2$ can be lower bounded as

$$d_t^2 = \left( d_t - \frac{b}{1-C} + \frac{b}{1-C} \right)^2 \\ = \left( d_t - \frac{b}{1-C} \right)^2 + \frac{b^2}{(1-C)^2} + 2 \left( d_t - \frac{b}{1-C} \right) \frac{b}{1-C} \ge \frac{b^2}{(1-C)^2}.$$

Conclude by summing the inequality above over $t \in [T]$,

$$\sum_{t=1}^{T} (z_t - c_t)^2 \ge \frac{Tb^2}{(1-C)^2} \ge \frac{1}{(1-C)^2} \sum_{t=2}^{T} |c_t - c_{t-1}|^2,$$

proving the claim.

## C Proofs of main positive results.

### C.1 Proof of Theorem 3.1

*Proof.* Proof. The setting for aggregation we consider here is an instance of Prediction with Expert Advice, see Cesa-Bianchi and Lugosi [2006, Chapter 2], where the K experts provide the advice $Z_t^{(i)}$, the outcomes are the pairs $(F_t(z_t), z_t)$, and where the loss is the function over $\mathcal{Z}$ and the dual space $(\mathcal{Z})^*$, i.e., $\mathcal{L}: \mathcal{Z} \times ((\mathcal{Z})^* \times \mathcal{Z}) \to \mathbb{R}$:

$$\mathcal{L}(a; g, z) = \langle g, a \rangle + \frac{\mu}{2} \|a - z\|^2 = \frac{\mu}{2} \left\| a - z - \frac{1}{\mu} g \right\|^2 - \frac{1}{\mu} \|g\|^2 + \langle z, g \rangle;$$

we apply it to $(g, z) = (F_t(z_t), z_t)$, thus the predictions will be bounded by $D$ and the outcome vectors by $D + G/\mu$. This loss function, which is an instance of the square loss, is $\lambda$-mixable for the mean (or, in other words, $\lambda$-exp-concave) for $\lambda \le (4\mu(D + G/\mu)^2)^{-1}$, as long as $\|x + (1/\mu)g\| \le D + G/\mu$ and $\|a\| \le D$. Playing the Exponential Weights updates from (5) in this context is equivalent to using Vovk's aggregating algorithm Vovk [1995], which guarantees for $\lambda$-mixable losses that

$$\sum_{t=1}^{T} \mathcal{L}(Z_t; F_t(Z_t), Z_t) \le \min_{i \in [K]} \sum_{t=1}^{T} \mathcal{L}(Z_t^{(i)}; F_t(Z_t), Z_t) + \frac{\log K}{\lambda}.$$
Proof. We prove the claim by showing that the summand in the statement is eventually zero. First, note that the sequence $(\lambda_t)$ is non-increasing. We define the threshold value

$$ \lambda^* = \frac{\mu}{2(\mu \hat{D}_T + \hat{G}_T)^2}, $$

and let $t_0 \in \mathbb{N}$ denote the largest integer smaller than $T$ such that $\lambda_t \ge \lambda^*$. Let us first show that

$$ \sum_{t=1}^{t_0} (\bar{\ell}_t - m_t)_+ \le \frac{2(\mu \hat{D}_T + \hat{G}_T)^2}{\mu} \log K + \hat{G}_T \hat{D}_T + \frac{\mu}{2} \hat{D}_T^2, \quad (14) $$

and that for any $t \ge t_0 + 1$, we have $(\bar{\ell}_t - m_t)_+ = 0$. To show (14), we note that by definition

$$ \lambda_{t_0} = \frac{\log K}{\sum_{t=1}^{t_0-1} (\bar{\ell}_t - m_t)_+} \ge \lambda^*, \quad \text{so} \quad \sum_{t=1}^{t_0-1} (\bar{\ell}_t - m_t)_+ \le \frac{\log K}{\lambda^*} = \frac{2(\mu \hat{D}_T + \hat{G}_T)^2}{\mu} \log K. $$

Furthermore, for any $t \in [T]$,

$$ (\bar{\ell}_t - m_t)_+ \le |\bar{\ell}_t - m_t| \le \left| \max_{i \in [K]} \ell_{i,t} - \min_{j \in [K]} \ell_{j,t} \right| \le \hat{G}_T \hat{D}_T + \mu \hat{D}_T^2. \quad (15) $$

Hence, applying this inequality in particular to $t_0$, we obtain,

$$ \sum_{t=1}^{t_0} (\bar{\ell}_t - m_t)_+ = (\bar{\ell}_{t_0} - m_{t_0})_+ + \sum_{t=1}^{t_0-1} (\bar{\ell}_t - m_t)_+ \le \frac{2(\mu \hat{D}_T + \hat{G}_T)^2}{\mu} \log K + \hat{G}_T \hat{D}_T + \mu \hat{D}_T^2. \quad (16) $$

Let us now consider $t > t_0$, and let us show that $\bar{\ell}_t \le m_t$. We prove this by using the exp-concavity of the square loss. Note first that the definition of $t_0$ implies that $\lambda_t < \lambda^*$, since the sequence $(\lambda_t)$ is non-increasing. Denote by $B(Z_t, \hat{D}_T)$ the Euclidean ball centered at $Z_t$ of radius $\hat{D}_T$, that is $B(Z_t, \hat{D}_T) = \{Z \in \mathcal{Z} : \|Z - Z_t\| \le D_T\}$. The map

$$ h_t : B(Z_t, \hat{D}_T) \to \mathbb{R} \\ u \mapsto \langle F_t(Z_t), u \rangle + \frac{\mu}{2} \|Z_t - u\|^2 $$

is $\lambda^*$-exp-concave, and therefore $\lambda_t$-exp-concave since $\lambda_t \le \lambda^*$. Indeed, for any $u \in B(Z_t, \hat{D}_T)$

$$ \begin{aligned} \lambda^* \nabla_u h_t(u) \nabla_u h_t(u)^\top &= \lambda^*(F(Z_t) + \mu(u-Z_t))(F(Z_t) + \mu(u-Z_t))^\top \\ &\le \lambda^* \|F(Z_t) + \mu(u-Z_t)\|^2 I_d \\ &\le \lambda^* 2(\hat{G}_T^2 + \mu \hat{D}_T^2) I_d \\ &\le \mu I_d = \nabla_u^2 h_t(u), \end{aligned} $$

which is exactly the condition for $\lambda^*$-exp-concavity (see Hazan [2022], Section 4.2 for details). Furthermore, we note that for any base algorithm $i \in [K]$, we have $Z_t^{(i)} \in B(Z_t, \hat{D}_T)$. Hence, by $\lambda_t$-exp-concavity

$$ \sum_{i=1}^{K} p_{t,i} e^{-\lambda_t h_t(Z_t^{(i)})} \le \exp \left( - \lambda_t h_t \left( \sum_{i=1}^{K} p_{t,i} Z_t^{(i)} \right) \right) = \exp \left( - \lambda_t h_t(Z_t) \right) $$

which we rearrange into

$$ \bar{\ell}_t = \langle F_t(Z_t), Z_t \rangle = h_t(Z_t) \le -\frac{1}{\lambda_t} \ln \sum_{i=1}^{K} p_{t,i} e^{-\lambda_t \ell_{i,t}} = m_t. $$

We proved that $\lambda_t \le \lambda^*$ implies $(\bar{\ell}_t - m_t)_+ = 0$ which, together with (16), completes the proof. ■

The next lemma guarantees that all the base algorithms stay within a bounded distance from the set of solutions of the operators in the sequence. It is a straightforward consequence of the fact that the forward algorithm is contractive in that setting.
This can be written as

$$ \sum_{t=1}^{T} \langle F_t(Z_t), Z_t \rangle \le \min_{i \in [K]} \sum_{t=1}^{T} \langle F_t(Z_t), Z_t^{(i)} \rangle + \frac{\mu}{2} \|Z_t^{(i)} - Z_t\|^2 + \frac{\log K}{\lambda}. \quad (12) $$

Now note that for any $u \in \mathbb{Z}$,

$$ \begin{aligned} \langle \tilde{F}_t(Z_t^{(i)}), Z_t^{(i)} - u \rangle - \frac{\mu}{2} \|Z_t^{(i)} - u\|^2 &= \langle F_t(Z_t) + \mu(Z_t^{(i)} - Z_t), Z_t^{(i)} - u \rangle - \frac{\mu}{2} \|Z_t^{(i)} - u\|^2 \\ &= \langle F_t(Z_t), Z_t^{(i)} - u \rangle + \mu \langle Z_t^{(i)} - Z_t, Z_t^{(i)} - u \rangle - \frac{\mu}{2} \|Z_t^{(i)} - u\|^2 \\ &= \langle F_t(Z_t), Z_t^{(i)} - u \rangle - \frac{\mu}{2} \|Z_t - u\|^2 + \frac{\mu}{2} \|Z_t^{(i)} - Z_t\|^2. \end{aligned} $$

Therefore, plugging this bound in (12), we see that for any sequence of comparators $(C_t) \in \mathbb{Z}^T$,

$$ \begin{aligned} \sum_{t=1}^{T} \langle F_t(Z_t), Z_t - C_t \rangle - \frac{\mu}{2} \|Z_t - C_t\|^2 &\le \min_{i \in [K]} \sum_{t=1}^{T} \langle F_t(Z_t), Z_t^{(i)} - C_t \rangle - \frac{\mu}{2} \|Z_t - C_t\|^2 + \frac{\mu}{2} \|Z_t^{(i)} - Z_t\|^2 + \frac{\log K}{\lambda} \\ &= \min_{i \in [K]} \sum_{t=1}^{T} \langle \tilde{F}_t(Z_t^{(i)}), Z_t^{(i)} - C_t \rangle - \frac{\mu}{2} \|Z_t^{(i)} - C_t\|^2 + \frac{\log K}{\lambda}. \end{aligned} $$

If in addition, $(C_t)$ is $k$-periodic, then, by applying the guarantees from Corollary 3.1 to the operators $\tilde{F}_t$ which are upper bounded in norm by $G + \mu D$, we obtain

$$ \min_{i \in [K]} \sum_{t=1}^{T} \langle \tilde{F}_t(Z_t^{(i)}), Z_t^{(i)} - C_t \rangle - \frac{\mu}{2} \|Z_t^{(i)} - C_t\|^2 \le \frac{k(G + \mu D)^2}{2\mu} \log \left( \frac{T}{k} + 1 \right). $$

Replace $\lambda$ by its value to conclude the proof.

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

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

## C.2 Proof of Theorem 3.2

We separate the proof into three distinct lemmas. We start with an analysis of the aggregation method, showing that the regret of the full procedure can be controlled by the cumulative distance of the correctly tuned base algorithm to the comparators, plus the cumulative mixability gap. We then proceed to bound the said cumulative mixability gap, by showing that the instantaneous mixability gaps are eventually 0, making the sum bounded independently of $T$. (More accurately, the dependence is only in $\hat{D}_T$ and $\hat{G}_T$, which will then be bounded independently.)

Recall that $(x)_+$ denotes the positive part of a real number $x$, and that

$$ \hat{D}_T = \max_{t \in [T], i, j \in [K]} \|Z_t^{(i)} - Z_t^{(j)}\| \quad \text{and} \quad \hat{G}_T = \max_{t \in [T], i, j \in [K]} \|F_t(Z_t^{(i)})\|. $$

**Lemma C.1.** For any sequence of comparators $(C_t)$, the meta-algorithm with adaptive learning rate and losses as defined in (6) and (7) ensures that

$$ \sum_{t=1}^{T} \left( \langle F_t(Z_t), Z_t - C_t \rangle - \frac{\mu}{2} \|Z_t - C_t\|^2 \right) \le 2 \sum_{t=1}^{T} (\bar{\ell}_t - m_t)_+ + (\hat{G}_T + \mu \hat{D}_T) \sum_{t=1}^{T} \|Z_t^{(k)} - C_t\|. $$

*Proof.* We start by applying the standard exponential weight analysis, which relates the cumulative mix loss to the minimal cumulative loss among the $K$ base algorithms. (We refer the reader to Lemma 1, paragraph 3 and Lemma 2 in De Rooij et al. [2014] for a proof.) This yields

$$ \sum_{t=1}^{T} m_s \le \min_{i \in [K]} \sum_{t=1}^{T} \ell_{s,i} + \frac{\log K}{\lambda_T}. $$

Therefore, using the fact that the $u \le u_+$ for any $u \in \mathbb{R}$,

$$ \sum_{t=1}^{T} \bar{\ell}_t = \sum_{t=1}^{T} (\bar{\ell}_t - m_t) + \sum_{t=1}^{T} m_t \le \sum_{t=1}^{T} (\bar{\ell}_t - m_t)_+ + \min_{i \in [K]} \sum_{t=1}^{T} \ell_{t,i} + \frac{\log K}{\lambda_T}. \quad (13) $$
**Lemma C.3.** If the sequence of operators is strongly monotone and Lipschitz, if $Z = \mathbb{R}^d$, and base algorithms are the cyclic forward algorithm, then

$$ \hat{D}_T \le 2\sqrt{2\kappa^2 + 1}D_0 \quad \text{and} \quad \hat{G}_T \le L\sqrt{2\kappa^2 + 1}D_0. $$

*Proof.* Remember that $\mathcal{C}$ denotes the set of the solutions of the operators $(F_t)$. We first show that due to the contraction of the forward algorithm (cf., Section 2.2, Example 2.1), for all $t \in [T]$ and base algorithm $i \in [K]$, there exists a point $Z_t^* \in \mathcal{C}$ such that $\|Z_t^{(i)} - Z_t^*\| \le \kappa D_0 + D_c$, where $D_c = \max_{C,C' \in \mathcal{C}} \|C - C'\|$. Indeed, for all base algorithms $i \in [K]$

$$ \|Z_t^{(i)} - Z_t^*\|^2 \le (1 - \kappa^{-1}) \|Z_{t-1}^{(i)} - Z_{t-1}^*\|^2 + \kappa \|Z_t^* - Z_{t-1}^*\|^2 \le (1 - \kappa^{-1}) \|Z_{t-1}^{(i)} - Z_{t-1}^*\|^2 + 2\kappa D_0^2. $$

Applying this recursively gives

$$ \begin{aligned} \|Z_t^{(i)} - Z_t^*\|^2 &\le 2\kappa D_0^2 \sum_{s=1}^t (1 - \kappa^{-1})^{t-s} + (1 - \kappa^{-1})^{t-1} \|Z_1^{(i)} - Z_1^*\|^2 \\ &\le 2\kappa D_0^2 \sum_{s=0}^{t-1} (1 - \kappa^{-1})^s + D_0^2 \\ &\le 2\kappa^2 D_0^2 + D_0^2. \end{aligned} $$

Therefore,

$$ \hat{D}_T = \max_{t \in [T], i,j \in [K]} \|Z_t^{(i)} - Z_t^{(j)}\| \le \max_{t \in [T], i,j \in [K]} \|Z_t^{(i)} - C_t^*\| + \|Z_t^{(j)} - C_t^*\| \le 2\sqrt{1 + 2\kappa^2 D_0}. $$

Similarly, since the problem is unconstrained, we have $F_t(Z_t^*) = 0$ (apply the definition of the solution with $Z = Z_t^* - F(Z_t^*)$) and for any $t \in [T]$ and $i \in [k]$,

$$ \|F_t(Z_t^{(i)})\| = \|F_t(Z_t^{(i)}) - F_t(Z_t^*)\| \le L \|Z_t^{(i)} - Z_t^*\| \le L\sqrt{2\kappa^2 + 1}D_0, $$

proving the claim.

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

The rest of the proof is a combination of previous results, with adequate computations.

*Proof.* Conclusion of the proof of Theorem 3.2. First note that, by summing a geometric series, and using the fact that $\sqrt{1+u} \le 1+u/2$ for any $u \in [-1, \infty)$, the correctly tuned algorithm ensures that

$$ \begin{aligned} \sum_{t=1}^{T} \|Z_t^{(k)} - C_t\| &\le D_0 \sum_{t=1}^{T} \left(1 - \frac{\mu}{L}\right)^{(1/2)[t/k]} \\ &\le kD_0 \sum_{i=1}^{\lfloor T/k \rfloor} \left(1 - \frac{\mu}{L}\right)^{i/2} \\ &\le \frac{kD_0}{1 - \sqrt{1 - \mu/L}} \le \frac{kD_0}{\mu/(2L)} = \frac{2kLD_0}{\mu}. \end{aligned} $$
Next we use that by definition $(\log K)/\lambda_T = \sum_{t=1}^{T-1} (\bar{\ell}_t - m_t)_+$. Plugging this into (13) and rearranging the terms gives

$$ \sum_{t=1}^{T} \bar{\ell}_t - \min_{i \in [K]} \sum_{t=1}^{T} \ell_{t,i} \le 2 \sum_{t=1}^{T} (\bar{\ell}_t - m_t)_+ . $$

Replacing $\bar{\ell}_t$ and $\ell_{t,i}$ by their definitions in terms of $F_t$ and $Z_t^{(i)}$, we obtain

$$ \sum_{t=1}^{T} \langle F_t(Z_t), Z_t \rangle - \min_{i \in [K]} \sum_{t=1}^{T} \left( \langle F_t(Z_t), Z_t^{(i)} \rangle + \frac{\mu}{2} \|Z_t^{(i)} - Z_t\|^2 \right) \le 2 \sum_{t=1}^{T} (\bar{\ell}_t - m_t)_+ . $$

Let us now rearrange the terms and subtract $\sum_{t=1}^{T} \frac{\mu}{2} \|Z_t - C_t\|^2$ on both sides to obtain

$$ \begin{aligned} & \sum_{t=1}^{T} \left( \langle F_t(Z_t), Z_t - C_t \rangle - \frac{\mu}{2} \|Z_t - C_t\|^2 \right) \\ & \le \min_{i \in [K]} \sum_{t=1}^{T} \left( \langle F_t(Z_t), Z_t^{(i)} - C_t \rangle + \frac{\mu}{2} \|Z_t^{(i)} - Z_t\|^2 - \frac{\mu}{2} \|Z_t - C_t\|^2 \right) + 2 \sum_{t=1}^{T} (\bar{\ell}_t - m_t)_+ \\ & \le \sum_{t=1}^{T} \left( \langle F_t(Z_t), Z_t^{(k)} - C_t \rangle + \frac{\mu}{2} \|Z_t^{(k)} - Z_t\|^2 - \frac{\mu}{2} \|Z_t - C_t\|^2 \right) + 2 \sum_{t=1}^{T} (\bar{\ell}_t - m_t)_+ . \end{aligned} $$

Finally, for any $t$, the loss of the $k$-th base algorithm can be controlled by the distance to the comparators:

$$ \begin{aligned} & \langle F_t(Z_t), Z_t^{(k)} - C_t \rangle + \frac{\mu}{2} \|Z_t^{(k)} - Z_t\|^2 - \frac{\mu}{2} \|Z_t - C_t\|^2 \\ & = \langle F_t(Z_t), Z_t^{(k)} - C_t \rangle + \frac{\mu}{2} \langle Z_t^{(k)} + C_t - 2Z_t, Z_t^{(k)} - C_t \rangle \le (\hat{G}_T + \mu \hat{D}_T) \|Z_t^{(k)} - C_t\|, \end{aligned} $$

where we used the Cauchy-Schwarz inequality to conclude. Summing over $t$ gives the claim.

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

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

We now proceed to bound the cumulative mixability gap separately. The proof is essentially an application of the mixability of the square loss with respect to the mean, which is equivalent to its exp-concavity. Recall a function $f$ is said to be $\alpha$-exp-concave if $\exp(-\alpha f)$ is convex. For completeness, we provide a self-contained proof of the following result, with no explicit call to mixability.

**Lemma C.2.** Under the assumptions of Lemma C.1,

$$ \sum_{t=1}^{T} (\bar{\ell}_t - m_t)_+ \le \frac{2(\mu \hat{D}_T + \hat{G}_T)^2}{\mu} \log K + \hat{G}_T \hat{D}_T + \frac{\mu}{2} \hat{D}_T^2. $$

*Proof.* Proof. We prove the claim by showing that the summand in the statement is eventually zero. First, note that the sequence $(\lambda_t)$ is non-increasing. We define the threshold value

$$ \lambda^* = \frac{\mu}{2(\mu \hat{D}_T + \hat{G}_T)^2}, $$

and let $t_0 \in \mathbb{N}$ denote the largest integer smaller than $T$ such that $\lambda_t \ge \lambda^*$. Let us first show that

$$ \sum_{t=1}^{t_0} (\bar{\ell}_t - m_t)_+ \le \frac{2(\mu \hat{D}_T + \hat{G}_T)^2}{\mu} \log K + \hat{G}_T \hat{D}_T + \frac{\mu}{2} \hat{D}_T^2, \quad (14) $$

and that for any $t \ge t_0 + 1$, we have $(\bar{\ell}_t - m_t)_+ = 0$. To show (14), we note that by definition

$$ \lambda_{t_0} = \frac{\log K}{\sum_{t=1}^{t_0-1} (\bar{\ell}_t - m_t)_+} \ge \lambda^*, \quad \text{so} \quad \sum_{t=1}^{t_0-1} (\bar{\ell}_t - m_t)_+ \le \frac{\log K}{\lambda^*} = \frac{2(\mu \hat{D}_T + \hat{G}_T)^2}{\mu} \log K. $$

Furthermore, for any $t \in [T]$,

$$ (\bar{\ell}_t - m_t)_+ \le |\bar{\ell}_t - m_t| \le \left| \max_{i \in [K]} \ell_{i,t} - \min_{j \in [K]} \ell_{j,t} \right| \le \hat{G}_T \hat{D}_T + \mu \hat{D}_T^2. \quad (15) $$
Therefore, applying Lemmas C.1, C.2, and C.3 specifying the sequence of comparators to $(C_t) = (Z_t^*)$,

$$
\begin{aligned}
& \sum_{t=1}^{T} \left( \langle F_t(Z_t), Z_t - Z_t^* \rangle - \frac{\mu}{2} \|Z_t - Z_t^*\|^2 \right) \\
& \le 2 \sum_{t=1}^{T} (\bar{\ell}_t - m_t)_+ + (\hat{G}_T + \mu \hat{D}_T) \sum_{t=1}^{T} \|Z_t^{(k)} - Z_t^*\| \\
& \le \frac{4(\mu \hat{D}_T + \hat{G}_T)^2}{\mu} \log K + 2\hat{G}_T \hat{D}_T + \mu \hat{D}_T^2 + (\hat{G}_T + \mu \hat{D}_T) \sum_{t=1}^{T} \|Z_t^{(k)} - Z_t^*\| \\
& \le \frac{4 \left( (2\mu + L)\sqrt{2\kappa^2 + 1} \right)^2 D_0^2}{\mu} \log k + 2(2\mu + L)\sqrt{2\kappa^2 + 1} D_0^2 + 2(2\mu + L)\sqrt{2\kappa^2 + 1} k\kappa D_0^2 \\
& = 2D_0^2(2\mu + L) \left( 2(2\kappa^2 + 1)(2 + \kappa) \log K + 1 + \sqrt{2\kappa^2 + 1}\kappa k \right) \\
& \le 2D_0^2(2\mu + L) \left( 2(2\kappa^2 + 1)(2 + \kappa) \log K + 1 + (2\kappa + 1)\kappa k \right),
\end{aligned}
$$

where we used the fact that $\sqrt{2\kappa^2 + 1} \le 2\kappa + 1$. To conclude, recall that for any $t \in [T]$, by strong monotonicity of $F_t$,

$$ \langle F_t(Z_t), Z_t - Z_t^* \rangle - \frac{\mu}{2} \|Z_t - Z_t^*\|^2 \ge \frac{\mu}{2} \|Z_t - Z_t^*\|^2, $$

so the bound above ensures that

$$ \sum_{t=1}^{T} \|Z_t - Z_t^*\|^2 \le 4D_0^2(2 + \kappa) \left( 2(2\kappa^2 + 1)(2 + \kappa) \log K + (2\kappa + 1)\kappa k + 1 \right). $$

which is the claimed statement.

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

### C.2.1 Technical lemmata.

In this section, we collect several technical results we build on. These results are either small modifications of existing results or a direct consequence of the results of the main part of this paper.

**Lemma C.4.** Suppose $F_t: \mathbb{R}^d \to \mathbb{R}^d$ are $\mu$-strongly monotone and L-Lipschitz operators for all $t \in [T]$ and assume that the solution for the VIP($F_t, \mathbb{R}^d$) is $Z^* \in \mathbb{R}^d$ for all $t \in [T]$. Let $T_{\eta,t}: Z \mapsto Z - \eta F_t(Z)$ and let $(Z_t)_{t \in [T]}$ denote the sequence defined as $Z_{t+1} = T_{\eta,t}(Z_t)$. If $\eta = 1/L$ then

$$ \|Z_t - Z^*\|^2 \le \left(1 - \frac{\mu}{L}\right)^t \|Z_1 - Z^*\|^2. $$

*Proof.* For any $Z_1, Z_2 \in \mathcal{Z}$, we have

$$
\begin{aligned}
\|T_{\eta}(Z_1) - T_{\eta}(Z_2)\|^2 &= \|Z_1 - \eta F(Z_1) - (Z_2 - \eta F(Z_2))\|^2 \\
&= \|Z_1 - Z_2\|^2 - 2\eta \langle Z_1 - Z_2, F(Z_1) - F(Z_2) \rangle + \eta^2 \|F(Z_1) - F(Z_2)\|^2 \\
&\le (1 - \mu/L) \|Z_1 - Z_2\|^2.
\end{aligned}
$$

Note that $T_{\eta,t}(Z^*) = Z^*$. Applying the inequality recursively gives the result.

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

Now consider a time-varying VI problem with a $k$-periodic solution (cf. Definition 1.2). We note that the forward algorithm $A_{cFW}^{(k)}$ (cf. Algorithm 1) does one step towards the solution $Z_t^*$ every $k^{th}$ iteration.

## D Implementation details on the bifurcation diagram.

The bifurcation diagram was obtained by running gradient descent on the sequence of functions defined in (10) for different values of $\eta$. All simulations were run on a standard laptop, using `python`. Precisely, we ran GD from the initial point $x_0 = -0.1$ for 2000 time steps, for a linearly spaced grid of 3000 values between 0 and 8, that is, $\eta \in \{8i/3000 : i \in \{1, \dots, 3000\}\}$.
Hence, applying this inequality in particular to $t_0$, we obtain,

$$ \sum_{t=1}^{t_0} (\bar{l}_t - m_t)_+ = (\bar{l}_{t_0} - m_{t_0})_+ + \sum_{t=1}^{t_0-1} (\bar{l}_t - m_t)_+ \le \frac{2(\mu \hat{D}_T + \hat{G}_T)^2}{\mu} \log K + \hat{G}_T \hat{D}_T + \mu \hat{D}_T^2. \quad (16) $$

Let us now consider $t > t_0$, and let us show that $\bar{l}_t \le m_t$. We prove this by using the exp-concavity of the square loss. Note first that the definition of $t_0$ implies that $\lambda_t < \lambda^*$, since the sequence $(\lambda_t)$ is non-increasing. Denote by $B(Z_t, \hat{D}_T)$ the Euclidean ball centered at $Z_t$ of radius $\hat{D}_T$, that is $B(Z_t, \hat{D}_T) = \{Z \in \mathbb{Z} : \|Z - Z_t\| \le D_T\}$. The map

$$ h_t : B(Z_t, \hat{D}_T) \to \mathbb{R} \\ u \mapsto \langle F_t(Z_t), u \rangle + \frac{\mu}{2} \|Z_t - u\|^2 $$

is $\lambda^*$-exp-concave, and therefore $\lambda_t$-exp-concave since $\lambda_t \le \lambda^*$. Indeed, for any $u \in B(Z_t, \hat{D}_T)$

$$ \begin{aligned} \lambda^* \nabla_u h_t(u) \nabla_u h_t(u)^\top &= \lambda^*(F(Z_t) + \mu(u-Z_t))(F(Z_t) + \mu(u-Z_t))^\top \\ &\le \lambda^* \|F(Z_t) + \mu(u-Z_t)\|^2 I_d \\ &\le \lambda^* 2(\hat{G}_T^2 + \mu \hat{D}_T^2) I_d \\ &\le \mu I_d = \nabla_u^2 h_t(u), \end{aligned} $$

which is exactly the condition for $\lambda^*$-exp-concavity (see Hazan [2022], Section 4.2). Furthermore, we note that for any base algorithm $i \in [K]$, we have $Z_t^{(i)} \in B(Z_t, \hat{D}_T)$. Hence, by $\lambda_t$-exp-concavity

$$ \sum_{i=1}^{K} p_{t,i} e^{-\lambda_t h_t(Z_t^{(i)})} \le \exp \left( - \lambda_t h_t \left( \sum_{i=1}^{K} p_{t,i} Z_t^{(i)} \right) \right) = \exp \left( - \lambda_t h_t(Z_t) \right) $$

which we rearrange into

$$ \bar{l}_t = \langle F_t(Z_t), Z_t \rangle = h_t(Z_t) \le -\frac{1}{\lambda_t} \ln \sum_{i=1}^{K} p_{t,i} e^{-\lambda_t \ell_{i,t}} = m_t. $$

We demonstrated that $\lambda_t \le \lambda^*$ implies $(\bar{l}_t - m_t)_+ = 0$ which, together with (16), completes the proof. ■ ■

The next lemma guarantees that all the base algorithms stay within a bounded distance from the set of solutions of the operators in the sequence. It is a straightforward consequence of the fact that the forward-backward algorithm is contractive in that setting.

**Lemma C.3.** If the sequence of operators is strongly monotone and Lipschitz, if $Z = \mathbb{R}^d$, and base algorithms are the cyclic forward-backward algorithm, then

$$ \hat{D}_T \le 2\sqrt{2\kappa^2 + 1}D_0 \quad \text{and} \quad \hat{G}_T \le L\sqrt{2\kappa^2 + 1}D_0. $$

*Proof.* Remember that $\mathcal{C}$ denotes the set of solutions of the operators $(F_t)$. We first show that due to the contraction of the forward-backward algorithm (cf., Section 2.2, Example 2.1), for all $t \in [T]$ and base algorithm $i \in [K]$, there exists a point $Z_t^* \in \mathcal{C}$ such that $\|Z_t^{(i)} - Z_t^*\| \le \kappa D_0 + D_c$, where $D_c = \max_{C,C' \in \mathcal{C}} \|C - C'\|$. Indeed, for all base algorithms $i \in [K]$

$$ \|Z_t^{(i)} - Z_t^*\|^2 \le (1 - \kappa^{-1}) \|Z_{t-1}^{(i)} - Z_{t-1}^*\|^2 + \kappa \|Z_t^* - Z_{t-1}^*\|^2 \le (1 - \kappa^{-1}) \|Z_{t-1}^{(i)} - Z_{t-1}^*\|^2 + 2\kappa D_0^2. $$

Applying this recursively gives

$$ \begin{aligned} \|Z_t^{(i)} - Z_t^*\|^2 &\le 2\kappa D_0^2 \sum_{s=1}^{t} (1 - \kappa^{-1})^{t-s} + (1 - \kappa^{-1})^{t-1} \|Z_1^{(i)} - Z_1^*\|^2 \\ &\le 2\kappa D_0^2 \sum_{s=0}^{t-1} (1 - \kappa^{-1})^s + D_0^2 \\ &\le 2\kappa^2 D_0^2 + D_0^2. \end{aligned} $$
The bifurcation diagram represents the asymptotic accumulation points of the sequence of iterates of GD: for each value of $\eta$, the points in the diagram with x-coordinate $\eta$ represent the limit points of GD. Accordingly, we split the interval of values [-10, 10] into 1000 cells and plotted all the cells that were visited between time-steps $t = 1000$ and the end time $t = 2000$. The grey areas correspond to values of $\eta$ that led to divergence. In practice, we considered that GD had diverged as soon as one iterate had a norm larger than $x_{max} = 1000$.
Therefore,

$$ \hat{D}_T = \max_{t \in [T], i,j \in [K]} \|Z_t^{(i)} - Z_t^{(j)}\| \le \max_{t \in [T], i,j \in [K]} \|Z_t^{(i)} - C_t^*\| + \|Z_t^{(j)} - C_t^*\| \le 2\sqrt{1+2\kappa^2}D_0. $$

Similarly, since the problem is unconstrained, we have $F_t(Z_t^*) = 0$ (apply the definition of the solution with $Z = Z_t^* - F(Z_t^*)$) and for any $t \in [T]$ and $i \in [k]$,

$$ \|F_t(Z_t^{(i)})\| = \|F_t(Z_t^{(i)}) - F_t(Z_t^*)\| \le L \|Z_t^{(i)} - Z_t^*\| \le L\sqrt{2\kappa^2 + 1}D_0, $$

proving the claim.

The rest of the proof is a combination of previous results, with adequate computations.

*Proof.* Conclusion of the proof of Theorem 3.2. First note that, by summing a geometric series, and using the fact that $\sqrt{1+u} \le 1+u/2$ for any $u \in [-1, \infty]$, the correctly tuned algorithm ensures that

$$ \begin{aligned} \sum_{t=1}^{T} \|Z_t^{(k)} - C_t\| &\le D_0 \sum_{t=1}^{T} \left(1 - \frac{\mu}{L}\right)^{(1/2)[t/k]} \\ &\le kD_0 \sum_{i=1}^{[T/k]} \left(1 - \frac{\mu}{L}\right)^{i/2} \\ &\le \frac{kD_0}{1 - \sqrt{1 - \mu/L}} \le \frac{kD_0}{\mu/(2L)} = \frac{2kLD_0}{\mu}. \end{aligned} $$

Therefore, applying Lemmas C.1, C.2, and C.3 specifying the sequence of comparators to $(C_t) = (Z_t^*)$,

$$ \begin{aligned} \sum_{t=1}^{T} & \left( \langle F_t(Z_t), Z_t - Z_t^* \rangle - \frac{\mu}{2} \|Z_t - Z_t^*\|^2 \right) \\ &\le 2 \sum_{t=1}^{T} (\bar{\ell}_t - m_t)_+ + (\hat{G}_T + \mu \hat{D}_T) \sum_{t=1}^{T} \|Z_t^{(k)} - Z_t^*\| \\ &\le \frac{4(\mu \hat{D}_T + \hat{G}_T)^2}{\mu} \log K + 2\hat{G}_T \hat{D}_T + \mu \hat{D}_T^2 + (\hat{G}_T + \mu \hat{D}_T) \sum_{t=1}^{T} \|Z_t^{(k)} - Z_t^*\| \\ &\le \frac{4 \left( (2\mu + L)\sqrt{2\kappa^2 + 1} \right)^2 D_0^2}{\mu} \log k + 2(2\mu + L)\sqrt{2\kappa^2 + 1} D_0^2 + 2(2\mu + L)\sqrt{2\kappa^2 + 1} k\kappa D_0^2 \\ &= 2D_0^2(2\mu + L) \left( 2(2\kappa^2 + 1)(2 + \kappa) \log K + 1 + \sqrt{2\kappa^2 + 1}\kappa k \right) \\ &\le 2D_0^2(2\mu + L) \left( 2(2\kappa^2 + 1)(2 + \kappa) \log K + 1 + (2\kappa + 1)\kappa k \right), \end{aligned} $$

where we used the fact that $\sqrt{2\kappa^2 + 1} \le 2\kappa + 1$. To conclude, recall that for any $t \in [T]$, by strong monotonicity of $F_t$,

$$ \langle F_t(Z_t), Z_t - Z_t^* \rangle - \frac{\mu}{2} \|Z_t - Z_t^*\|^2 \ge \frac{\mu}{2} \|Z_t - Z_t^*\|^2, $$

so the bound above ensures that

$$ \sum_{t=1}^{T} \|Z_t - Z_t^*\|^2 \le 4D_0^2(2+\kappa) \left( 2(2\kappa^2+1)(2+\kappa)\log K + (2\kappa+1)\kappa k + 1 \right). $$

which is the claimed statement.
## D On Ignoring Periodicity

We illustrate one elementary yet striking consequence of ignoring the time fluctuations, on a sequence of 1-dimensional quadratic problems, using the gradient descent algorithm with a fixed step size. We will see that increasing the learning rate can move the algorithm from a diverging regime to a converging one, and even to the fastest convergence rates. This goes against the intuitive idea that decreasing the learning should make the sequence more stable.

For $Z = \mathbb{R}$, consider the sequence of functions $(f_t)$ defined by $f_{2t}(x) = x^2/2$ and $f_{2t+1}(x) = 4x^2$, which corresponds to the periodic time-varying VIP$((F_t), \mathbb{R})$ with $F_{2t}(x) = x$ and $F_{2t+1}(x) = 8x$, and with a constant solution $x^* \equiv 0$. We observe that $(F_t)$ defines a 2-periodic VI problem and a VI problem with a fixed (i.e., 1-periodic) solution. Both of the operators $F_{2t}$, $F_{2t+1}$ are 1-strongly monotone, and 8-Lipschitz. Consider gradient descent with step size $\eta$, which consists in selecting at all times $t$ the sequence defined by $x_{t+1} = x_t - \eta F_t(x_t)$. The actions at every odd time satisfy

$$x_{t+2} = (1 - \eta)(1 - 8\eta)x_t.$$

Gradient descent converges to the optimum 0 (for generic initial points) if and only if the common ratio of the geo-metric sequence is less than 1, i.e., if $|1 - \eta| |1 - 8\eta| < 1$. Moreover, when the sequence converges, the common ratio dictates its speed of convergence to the optimum: the closer it is to 0, the faster the convergence. In particular, when tuned with $\eta = 1$, gradient descent converges to the optimum in a single step. On the other hand, there is a range of smaller step sizes for which the sequence diverges. For example, for $\eta = 1/2$, the common ratio is $3/2 > 1$, and the iterates diverge.

## E Implementation details on the bifurcation diagram.

The bifurcation diagram was obtained by running gradient descent on the sequence of functions defined in (10) for different values of $\eta$. Precisely, we ran GD from the initial point $x_0 = -0.1$ for 2000 time steps, for a linearly spaced grid of 3000 values between 0 and 8, that is, $\eta \in \{8i/3000 : i \in \{1, \dots, 3000\}\}$.

The bifurcation diagram represents the asymptotic accumulation points of the sequence of iterates of GD: for each value of $\eta$, the points in the diagram with $x$-coordinate $\eta$ represent the limit points of GD. Accordingly, we split the interval of values $[-10, 10]$ into 1000 cells and shaded all the cells that were visited between time-steps $t = 1000$ and the end time $t = 2000$. The grey areas correspond to values of $\eta$ that led to divergence. In practice, we considered that GD had diverged as soon as one iterate had a norm larger than $x_{\max} = 1000$.

All simulations were run on a standard laptop, using python.