---
abstract: 'In continual learning settings, deep neural networks are prone to catastrophic forgetting. Orthogonal Gradient Descent [@farajtabar2019orthogonal] achieves state-of-the-art results in practice for continual learning, although no theoretical guarantees have been proven yet. We derive the first generalisation guarantees for the algorithm OGD for continual learning, for overparameterized neural networks. We find that OGD is only provably robust to catastrophic forgetting across a single task. We propose OGD+, prove that it is robust to catastrophic forgetting across an arbitrary number of tasks, and that it verifies tighter generalisation bounds. Our experiments show that OGD+ achieves state-of-the-art results on settings with a large number of tasks, even though the models are not overparameterized. Also, we derive a closed form expression of the learned models through tasks, as a recursive kernel regression relation, which captures the transferability of knowledge through tasks. Finally, we quantify theoretically the impact of task ordering on the generalisation error, which highlights the importance of the curriculum for lifelong learning.'
bibliography:
- 'icml.bib'
nocite: '[@*]'
---

Introduction
============

Continual learning is a setting in which an agent is exposed to multiples tasks sequentially [@Kirkpatrick2016EWC]. The core challenge lies in the ability of the agent to learn the new tasks while retaining the knowledge acquired from previous tasks. Too much plasticity will lead to catastrophic forgetting, which means the degradation of the ability of the agent to perform the past tasks (@MCCLOSKEY1989109, @Ratcliff1990ConnectionistMO, @Goodfellow2013Forgetting). On the other hand, too much stability will hinder the agent from adapting to new tasks. Recent works on the Neural Tangent Kernel [@Jacot2018NTK] and on the convergence of Stochastic Gradient Descent for overparameterized neural networks [@Arora:2019:FineGrained] have unlocked powerful tools to analyze the training dynamics of over-parameterized neural networks. We leverage these theoretical findings in order to to prove guarantees on the convergence and the generalisation of the algorithm, Orthogonal Gradient Descent for Continual Learning [@farajtabar2019orthogonal].

Our contributions are summarized as follows:

1.  We provide closed form expressions of the functions learned across tasks. We find that they can be expressed as a linear combination of kernel regressors, over the previously seen tasks. The relationship also captures task similarity and the transferability of knowledge across tasks (Sec. \[sec:convergence\], Theorem \[thm:conv\]).

2.  We prove the first generalisation bound for continual learning with OGD, to our knowledge. We derive bounds for within-task and outside-task generalisation. We find that generalisation through time depends on task similarity, which we quantify rigorously (Sec. \[sec:generalisation\], Theorem \[thm:gen-ogd\]).

3.  We prove that OGD is robust to forgetting with respect to the previous task only (Sec. \[sec:generalisation\], Lemma \[lem:train-unchanged\]).

4.  We build-up on this insight to propose OGD+ (Sec. \[sec:ogd-plus\], Alg. \[alg:ogd-plus-train\]), an extension of OGD, which we prove robust to catastrophic forgetting across an arbitrary number of tasks (Sec. \[sec:ogd-plus\], Lemma \[lem:train-unchanged-ogd-plus\]). We also prove tighter generalisation bounds than OGD (Sec. \[sec:ogd-plus\], Theorem \[thm:gen-ogd-plus\]).

5.  As a side result, we find that Lemma \[lem:rademacher-tasks\] also quantifies the impact of the learning curriculum on the generalisation error. We find that task dissimilarity impacts negatively generalisation, and that an ordering of tasks that minimises dissimilarity between neighbouring tasks leads to a tighter generalisation bound. (Sec. \[thm:gen-ogd\], Lemma \[lem:rademacher-tasks\]).

Even though the analysis relies on the assumption that the neural network is overparametrised, the analysis leads to practical insights to improve OGD, which led us to OGD+. We run experiments in the non-overparametrised setting, and show that OGD+ achieves state-of-the-art results in settings with large number of tasks (Sec. \[sec:experiments\]).

Preliminaries {#sec:ogd}
=============

#### Notation

We use bold-faced characters for vectors and matrices. We use $\norm{\cdot}$ to denote the Euclidian norm of a vector or the spectral norm of a matrix, and $\|\cdot\|_\mathrm{F}$ to denote the Frobenius norm of a matrix. We use $\langle\cdot,
\cdot\rangle$ for the Euclidian dot product, and $\langle\cdot,\cdot\rangle_{{\mbox{$\mathcal{H}$}}}$ the dot product in the Hilbert space ${\mbox{$\mathcal{H}$}}$. We index the the task ID by $\tau$. The $ \leq $ operator if used with matrices, corresponds to the partial ordering over symetric matrices. We denote ${\mbox{$\mathbb{N}$}}$ the set of natural numbers, ${\mbox{$\mathbb{R}$}}$ the space of real numbers and ${\mbox{$\mathbb{N}$}}^{\star}$ for the set ${\mbox{$\mathbb{N}$}}\smallsetminus\{0\}$. We use $\oplus$ to refer to the direct sum over Euclidian spaces.

Continual Learning
------------------

Continual learning considers a series of tasks $\{{\mbox{$\mathcal{T}$}}_1, {\mbox{$\mathcal{T}$}}_2, \ldots\}$, where each task can be viewed as a separate supervised learning problem. Similarly to online learning, data from each task is revealed only once. The goal of continual learning is to model each task accurately with a single model. The challenge is to achieve a good performance on the new tasks, while retaining knowledge from the previous tasks [@v2018variational].

We assume the data from each task ${\mbox{$\mathcal{T}$}}_\tau$, $\tau \in {\mbox{$\mathbb{N}$}}^\star$, is drawn from a distribution ${\mbox{$\mathcal{D}$}}_\tau$. Individual samples are denoted $({\mbox{${\mbox{$\mathbf{x}$}}$}}_{\tau, i}, y_{\tau, i})$, where $i \in [n_\tau]$. Also, we only consider the binary classification setting for the sake of simplicity: ${\mbox{${\mbox{$\mathbf{x}$}}$}}_{\tau,i} \in {\mbox{$\mathbb{R}$}}^d$ and $y_{\tau, i} \in \{ -1, +1 \}$. We note that it does not restrict the scope of the analysis, which can be easily extended to multiclass settings.

OGD for Continual Learning {#subsec:ogd-for-continual-learning}
--------------------------

Let ${\mbox{$\mathcal{T}$}}_T$ the current task, where $T \in {\mbox{$\mathbb{N}$}}^\star$. For all $i \in [n_T]$, let ${\mbox{${\mbox{$\mathbf{v}$}}$}}_{T, i} = \nabla_\theta f^\star_{T-1}({\mbox{${\mbox{$\mathbf{x}$}}$}}_{T-1,i})$, which is the Jacobian of task ${\mbox{$\mathcal{T}$}}_T$. We define ${\mbox{$\mathbb{E}$}}_\tau = \mathrm{vec}( \{{\mbox{${\mbox{$\mathbf{v}$}}$}}_{\tau, i}, i \in [n_\tau] \} )$, which is the subspace induced by the Jacobian. The idea behind OGD is to update the weights along the projection of the gradient on the orthogonal space induced by the Jacobians over the previous tasks ${\mbox{$\mathbb{E}$}}_1 \oplus \ldots \oplus {\mbox{$\mathbb{E}$}}_{\tau-1} $. The update rule for the task ${\mbox{$\mathcal{T}$}}_T$ is as follows [@farajtabar2019orthogonal]: $${\mbox{${\mbox{$\mathbf{w}$}}$}}_T(t+1) = {\mbox{${\mbox{$\mathbf{w}$}}$}}_T(t) - \eta \Pi_{{\mbox{$\mathbb{E}$}}_{T-1}^\bot} \nabla_{{\mbox{${\mbox{$\mathbf{w}$}}$}}} {\mbox{$\mathcal{L}$}}^T_{\lambda}({\mbox{${\mbox{$\mathbf{w}$}}$}}_T(t)).$$

The intuition behind OGD is to [@farajtabar2019orthogonal].

To prevent over-fitting and guarantee the uniqueness of the global minimum in the Neural Tangent Kernel (NTK) regime, we apply a ridge regularization with a parameter $\lambda \in {\mbox{$\mathbb{R}$}}^{+}$. For a task ${\mbox{$\mathcal{T}$}}_\tau$, we write the corresponding loss as follows: $${\mbox{$\mathcal{L}$}}_\lambda^\tau({\mbox{${\mbox{$\mathbf{w}$}}$}}) = \sum_{i=1}^{n_\tau} (f_\tau({\mbox{${\mbox{$\mathbf{x}$}}$}}_{\tau, i}) - y_{\tau, i})^2 + \lambda
    \norm{{\mbox{${\mbox{$\mathbf{w}$}}$}}-
    {\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau-1}}^2.$$

Generalisation for Continual Learning
-------------------------------------

We define within-task generalisation as the ability of the agent to acquire new knowlege and outside-task generalisation as its ability to preserve the acquired knowledge.

Consider a loss function $l: {\mbox{$\mathbb{R}$}}\times {\mbox{$\mathbb{R}$}}\rightarrow {\mbox{$\mathbb{R}$}}$. The population loss over the distribution ${\mbox{$\mathcal{D}$}}$, and the empirical loss over $n$ samples $D = \{({\mbox{${\mbox{$\mathbf{x}$}}$}}_i, y_i), i \in [n] \}$ from the same distribution ${\mbox{$\mathcal{D}$}}$ are defined as: $$\begin{aligned}
        L_D(f) &= {\mathbb{E}}_{({\mbox{${\mbox{$\mathbf{x}$}}$}}, y) \sim {\mbox{$\mathcal{D}$}}} [l(f({\mbox{${\mbox{$\mathbf{x}$}}$}}), y)], &\\
        L_S(f) &= \frac{1}{n} \sum_{i=1}^n l(f({\mbox{${\mbox{$\mathbf{x}$}}$}}_i), y_i).
    \end{aligned}$$

Let ${\mbox{$\mathcal{T}$}}_1, \ldots {\mbox{$\mathcal{T}$}}_T$ a sequence of tasks, and ${\mbox{$\mathcal{D}$}}_1, \ldots {\mbox{$\mathcal{D}$}}_T$ their corresponding distributions.\
Let $f_1^\star, \ldots f_T^\star$ the trained models at each task. Let $\tau \in [T]$ fixed.\
We define:

-   within-task generalisation of the task ${\mbox{$\mathcal{T}$}}_\tau$ as $L_{D_\tau}(f_\tau^\star)$.

-   outside-task generalisation of the task ${\mbox{$\mathcal{T}$}}_\tau$ with respect to a task ${\mbox{$\mathcal{T}$}}_{\tau^\prime}$, where $\tau^\prime < \tau$ as $L_{D_\tau}(f_{\tau^\prime}^\star)$.

In practice, several works also tracked these metrics in their experiments (@Kirkpatrick2016EWC, @farajtabar2019orthogonal).

Neural Tangent Kernel
---------------------

In their seminal paper, @Jacot2018NTK established the connection between deep networks and kernel methods by introducing the Neural Tangent Kernel (NTK). They showed that at the infinite width limit, the kernel remains constant throughout training. @lee2019wide also showed that a network evolves as a linear model in the infinite width limit when trained on certain losses under gradient descent.

Throughout our analysis, we make the assumption that the neural network is overparameterized, and consider the linear approximation of the neural network around its initialisation: $$f^{(t)}({\mbox{${\mbox{$\mathbf{x}$}}$}}) \approx f^{(0)}({\mbox{${\mbox{$\mathbf{x}$}}$}}) + \nabla_{{\mbox{${\mbox{$\mathbf{w}$}}$}}} f^{(0)}({\mbox{${\mbox{$\mathbf{x}$}}$}})^T ({\mbox{${\mbox{$\mathbf{w}$}}$}}(t) - {\mbox{${\mbox{$\mathbf{w}$}}$}}(0)).$$

Convergence of OGD for Continual Learning {#sec:convergence}
=========================================

In this section, we derive a closed form expression for the learned models across tasks. We find a recursive kernel ridge regression relationship between the models across tasks. The result is presented in Theorem \[thm:conv\], a stepping stone towards proving the generalisation bound for OGD in Sec. \[sec:generalisation\].

Convergence Theorem {#subsec:conv}
-------------------

Now, we state the main result of this section:

\[thm:conv\] Let ${\mbox{$\mathcal{T}$}}_1,\ldots, {\mbox{$\mathcal{T}$}}_T$ be a sequence of tasks. Fix a learning rate sequence $(\eta_\tau)_{\tau \in [T]}$. If, for all $\tau$, the learning rate satisfies $$\eta_\tau < \frac{1}{\norm{k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau)} +\lambda_\tau^2},$$ $$\begin{aligned}
        \intertext{then for all $\tau$, ${\mbox{${\mbox{$\mathbf{w}$}}$}}_\tau(t)$ converges linearly to a limit solution ${\mbox{${\mbox{$\mathbf{w}$}}$}}_\tau^\star$ such
that}
        f_\tau^\star({\mbox{${\mbox{$\mathbf{x}$}}$}})
        &= f_{\tau-1}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) + k_\tau({\mbox{${\mbox{$\mathbf{x}$}}$}}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau)^T {\mbox{${\mbox{$\mathbf{H}$}}$}}_{\tau, \lambda_\tau}^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau,
        \intertext{where}
        k_\tau({\mbox{${\mbox{$\mathbf{x}$}}$}}, {\mbox{${\mbox{$\mathbf{x}$}}$}}^\prime) &= {\widetilde{\phi}}_\tau({\mbox{${\mbox{$\mathbf{x}$}}$}})^T {\widetilde{\phi}}_\tau({\mbox{${\mbox{$\mathbf{x}$}}$}}^\prime), &\\
        {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau &= {\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau - {\mbox{${\mbox{$\mathbf{y}$}}$}}_{\tau - 1 \rightarrow \tau}, &\\
        {\mbox{${\mbox{$\mathbf{y}$}}$}}_{\tau - 1 \rightarrow \tau} &= f_{\tau-1}^\star({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau), &\\
        \phi_\tau({\mbox{${\mbox{$\mathbf{x}$}}$}}) &= \nabla_{{\mbox{${\mbox{$\mathbf{w}$}}$}}} f_{\tau-1}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}), &\\
        {\mbox{${\mbox{$\mathbf{H}$}}$}}_{\tau, \lambda} &= k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) + \lambda^2 {\mbox{${\mbox{$\mathbf{I}$}}$}}, &\\
        {\widetilde{\phi}}_\tau({\mbox{${\mbox{$\mathbf{x}$}}$}}) &=
        \begin{cases}
            \phi_\tau({\mbox{${\mbox{$\mathbf{x}$}}$}}) \text{\quad $\mathrm{for SGD}$,}\\
            {\mbox{${\mbox{$\mathbf{T}$}}$}}_\tau \phi_\tau({\mbox{${\mbox{$\mathbf{x}$}}$}}) \text{\quad $\mathrm{for OGD}$.}
        \end{cases}
        \intertext{and $\{{\mbox{${\mbox{$\mathbf{T}$}}$}}_{\tau}, \tau \in [T]\}$ are proxy matrices for the analysis.}
    \end{aligned}$$

The theorem describes how the model $f_\tau^\star$ evolves across tasks. The theorem is recursive because the learning is incremental. For a given task ${\mbox{$\mathcal{T}$}}_\tau$, $f_{\tau-1}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}})$ is the knowledge acquired by the agent up to the task ${\mbox{$\mathcal{T}$}}_{\tau-1}$. At this stage, the model only fits the residual ${\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau ={\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau - {\mbox{${\mbox{$\mathbf{y}$}}$}}_{\tau - 1 \rightarrow \tau}$, which complements the knowledge acquired through previous tasks. This residual is also a proxy for task similarity. If the tasks are identical, the residual is equal to zero. The knowledge increment is captured by the term: $k_\tau({\mbox{${\mbox{$\mathbf{x}$}}$}}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau)^T (k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau , {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) +
\lambda_\tau^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau$. Finally, task similarity is computed with respect to the most recent feature map ${\widetilde{\phi}}_\tau$, and $k_\tau$ is the NTK with respect to the feature map ${\widetilde{\phi}}_\tau$.

The recursive relation from Theorem \[thm:conv\] can also be written as a linear combination of kernel regressors as follows: $$\begin{aligned}
        f_\tau^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) &= \sum_{k=1}^\tau {\mbox{$\tilde{f}$}}_{k}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}),
        \intertext{where}
        {\mbox{$\tilde{f}$}}_{k}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) &= k_k({\mbox{${\mbox{$\mathbf{x}$}}$}}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k)^T (k_k({\mbox{${\mbox{$\mathbf{X}$}}$}}_k , {\mbox{${\mbox{$\mathbf{X}$}}$}}_k) + \lambda_k^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_k.
    \end{aligned}$$

#### Proof Sketch:

We prove Theorem \[thm:conv\] by induction. We rewrite the loss function as a regression on the residual ${\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau$ instead of ${\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau$. Then, we rewrite the optimisation objective as an unconstrained strongly convex optimisation problem. Finally, we compute the unique solution in a closed form. The full proof is presented in App. \[subsec:conv-multiple-proof\].

Distance from Initialisation {#subsec:distance-from-initialisation}
----------------------------

As described in Sec. \[subsec:conv\], ${\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau$ is a residual. It is equal to zero if the model makes perfect predictions on the next task ${\mbox{$\mathcal{T}$}}_\tau$. The more the next task ${\mbox{$\mathcal{T}$}}_\tau$ is different, the further the neural network needs to move from its previous state in order to fit it. Corollary \[cor:weight-dist\] tracks the distance from initialisation as a function of task similarity.

\[cor:weight-dist\] For SGD, and for OGD under the additional assumption that $\{{\mbox{${\mbox{$\mathbf{T}$}}$}}_{\tau}, \tau \in [T]\}$ are orthonormal, $$\begin{aligned}
        \norm{{\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau + 1}^\star - {\mbox{${\mbox{$\mathbf{w}$}}$}}_\tau^\star}_\mathrm{F} &= \sqrt{{\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau^T {\mbox{${\mbox{$\mathbf{H}$}}$}}_{T, \lambda}^{-1} {\mbox{${\mbox{$\mathbf{H}$}}$}}_{\tau, 0}
        {\mbox{${\mbox{$\mathbf{H}$}}$}}_{T,
        \lambda}^{-1}
        {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau},
        \intertext{where}
        {\mbox{${\mbox{$\mathbf{H}$}}$}}_{\tau, \lambda} &= k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) + \lambda^2 {\mbox{${\mbox{$\mathbf{I}$}}$}}.
    \end{aligned}$$

The proof is presented in App. \[subsec:proof-weight-dist\]. The orthonormality assumption is not restrictive, since the set $\{{\mbox{${\mbox{$\mathbf{T}$}}$}}_{\tau}, \tau \in [T]\}$ is only a proxy for the analysis; indeed we can choose any convenient basis to work with.

\[rem:weight-dist\] Corollary \[cor:weight-dist\] can be used to get a similar result to Theorem 3 by @liu2019understanding. In this remark, we consider mostly their notations. Their theorem states that under some conditions, for 2-layer neural networks with a RELU activation function, with probability no less than $1 - \delta$ over random initialisation, $$\begin{aligned}
        \norm{{\mbox{${\mbox{$\mathbf{W}$}}$}}(P) - {\mbox{${\mbox{$\mathbf{W}$}}$}}(Q)}_\mathrm{F} &\leq \sqrt{ {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{P \rightarrow Q}^T H_P^{\infty \space -1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{P \rightarrow Q}}
+ \epsilon, &\\
        \intertext{where, in their work:}
        {\mbox{${\mbox{$\mathbf{y}$}}$}}_{P \rightarrow Q} &= H_{PQ}^{\infty, T} H_P^{\infty \space -1} {\mbox{${\mbox{$\mathbf{y}$}}$}}_P,\\
        {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{P \rightarrow Q} &= {\mbox{${\mbox{$\mathbf{y}$}}$}}_Q - {\mbox{${\mbox{$\mathbf{y}$}}$}}_{P \rightarrow Q}.
    \end{aligned}$$

Note that $H_P^{\infty}$ is a Gram matrix, which also corresponds to the NTK of the neural network they consider. We see an analogy with our result, where we work directly with the NTK, with no assumptions on the neural network. One important observation is that, to our knowledge, since there are no guarantees for the invertibility of our Gram matrix, we add a ridge regularisation to work with a regularised matrix, which is then invertible. In our setting, by considering $\lambda \rightarrow 0$, and with the additional assumption of invertibility of ${\mbox{${\mbox{$\mathbf{H}$}}$}}_{\tau, 0}$,which is valid in the two-layer overparametrised RELU neural network considered in the setting of @liu2019understanding, we can recover a similar approximation.

Generalisation of OGD for Continual Learning {#sec:generalisation}
============================================

In this section, we study the generalisation properties of OGD. First, we prove that OGD is robust to catastrophic forgetting with respect to the previous task (Lemma \[lem:train-unchanged\]). Then, we present the the main generalisation theorem for OGD (Thm. \[thm:gen-ogd\]). The theorem provides several insights on the relation between task similarity and generalisation. Finally, we present how the Rademacher complexity relates to task similarity across a large number of tasks (Lemma \[lem:rademacher-tasks\]). The lemma states that the more dissimilar tasks are, the larger the class of functions explored by the neural network, with high probability.

Memorisation property of OGD {#subsec:memorisation-property-of-ogd}
----------------------------

The key to obtaining tight generalisation bounds for OGD is Lemma \[lem:train-unchanged\].

\[lem:train-unchanged\] Given a task ${\mbox{$\mathcal{T}$}}_\tau$, for all ${\mbox{${\mbox{$\mathbf{x}$}}$}}_{\tau, i} \in D_\tau$, a sample from the training data of the task ${\mbox{$\mathcal{T}$}}_\tau$, it holds that $$f_{\tau + 1}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{\tau, i}) = f_{\tau}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{\tau, i}).$$

As motivated by @farajtabar2019orthogonal, the orthogonality of the gradient updates aims to preserve the acquired knowledge, by not altering the weights along relevant dimensions when learning new tasks. Lemma \[lem:train-unchanged\] states that the training error on the previous task is unchanged, when training with OGD. However, there are no guarantees that the knowledge from the tasks before the previous task is preserved.

The proof of Lemma \[lem:train-unchanged\] is presented in App. \[subsubsec:proof-train-unchanged\]

Generalisation of OGD for Continual Learning {#subsec:generalisation-ogd}
--------------------------------------------

Now, we state the main generalisation theorem for OGD, which provides within-task and outside-task generalisation bounds.

\[thm:gen-ogd\] Let $\{{\mbox{$\mathcal{T}$}}_1, \ldots {\mbox{$\mathcal{T}$}}_T\}$ be a sequence of tasks. Let be $\{{\mbox{$\mathcal{D}$}}_1, \ldots, {\mbox{$\mathcal{D}$}}_T\}$ the respective distributions over ${\mbox{$\mathbb{R}$}}^d \times \{-1, 1\}$. Let $\{({\mbox{${\mbox{$\mathbf{x}$}}$}}_{\tau, i}, y_{\tau, i}), i \in [n_t], \tau \in [T] \}$ be i.i.d. samples from ${\mbox{$\mathcal{D}$}}_\tau, \tau \in
    [T] $. Denote ${\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau = ({\mbox{${\mbox{$\mathbf{x}$}}$}}_{\tau, 1}, \ldots, {\mbox{${\mbox{$\mathbf{x}$}}$}}_{\tau, n_\tau})$, ${\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau = (y_{\tau, 1}, \ldots, y_{\tau,
    n_\tau})$. Consider the kernel ridge regression solution $f_T^\star$. Suppose that the kernel matrices satisfy

(k\_(\_, \_)) &= (n\_), \_[D\_T]{}(f\_T\^) & + &\
&\_[k=1]{}\^T (( ) + \_k), &\
\_[D\_[T-1]{}]{}(f\_T\^) & + &\
&\_[k=1]{}\^T (( ) + \_k), &\
\_[D\_]{}(f\_T\^) & + &\
&\_[k=1]{}\^T (( ) + \_k), &\
\_k &= () + 3 c , &\
\_[, ]{} &= k\_(\_, \_) + \^2 , &\
A\_&= &\
\_() &= \_\_ f\_[-1]{}\^(), &\
\_&= \_- \_[- 1 ]{}, &\
\_[- 1 ]{} &= f\_[-1]{}\^(\_), &\
\_[i,j,k]{} &= k\_i(\_j, \_k), &\
\_[k, ]{} &= \_[k,k,k]{}\^[-1]{}\_[k,,k]{}\_[k,,k]{}\^T \_[k,k,k]{}\^[-1]{}.

The intution behind Theorem \[thm:gen-ogd\] is as follows:

-   Within-task generalisation: The generalisation error on the most recent task leverages the information learned during training on the previous tasks. The bound is tighter compared to learning from scratch, since it depends on the residual ${\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau}$. Therefore it captures the transferability of knowledge across tasks.

-   Outside-task generalisation (${\mbox{$\mathcal{T}$}}_{T - 1}$): The generalisation bound increases only with respect to the Rademacher complexity when training with OGD. The tightness of this bound for OGD is due to Lemma \[lem:train-unchanged\]. This lemma is valid for OGD and not for SGD, which implies that tighter generalisation is guaranteed compared to SGD.

-   Outside-task generalisation (${\mbox{$\mathcal{T}$}}_{\tau}, \tau \leq T- 2$): The upper bound depends on the similarity between the outside task and the latest task; the more dissimilar the subsequent tasks are, the more the upper bound diverges from the initial upper bound. This bound captures catastrophic forgetting as a function of the tasks dissimilarity. This bound is the same for OGD and SGD.

These bounds share some similarities with the bounds derived by @Arora:2019:FineGrained, @liu2019understanding and @hu2019simple, where in these works, the bounds were derived for supervised learning settings, and in some cases for two-layer RELU neural networks. Similarly, the bounds depend on the Gram matrix of the data, with the feature map corresponding to the NTK.

#### Proof Sketch:

The proof is presented in App. \[subsec:proof-gen-ogd\]. One challenge is that the function class is the set of linear combinations of kernel regressors (Theorem \[thm:conv\]). We state Lemma \[lem:rademacher-kernels\] to bound the Rademacher complexity for this function class. Then we derive bounds for the training error for each case in Theorem \[thm:gen-ogd\]. The first case is straightforward. For the second case, we use Lemma \[lem:train-unchanged\], then derive a similar proof to the first case. The third case presents some additional technical challenges. In order to derive the upper bounds, we draw a strong inspiration from @hu2019simple, and leverage several of their proof techniques and mathematical tools.

Distance from Initialisation through Tasks {#subsec:distance-from-initialisation-through-tasks}
------------------------------------------

Now, we state Lemma \[lem:rademacher-tasks\], which tracks the Rademacher complexity through tasks.

\[lem:rademacher-tasks\] Keeping the same notations and setting as Theorem \[thm:gen-ogd\], the Rademacher Complexity can be bounded as follows: $$\begin{aligned}
        \hat{{\mbox{$\mathcal{R}$}}}({\mbox{$\mathcal{F}$}}_{{\mbox{${\mbox{$\mathbf{B}$}}$}}_T}) &\leq \sum_{\tau=1}^T {\mathcal{O}}\left( \sqrt{\frac{{\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau^T (k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau , {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) +
        \lambda^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1}  {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau }{n_\tau}} \right)  &\\
        &+ \sum_{\tau=1}^T {\mathcal{O}}(\frac{1}{\sqrt{n_\tau}}).
    \end{aligned}$$

The intuition behind Lemma \[lem:rademacher-tasks\] is that the upper bound on the Rademacher complexity increases when the tasks are dissimilar. The dissimilarity between two subsequent tasks is measured through ${\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau^T (k_t({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau , {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) +
        \lambda^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1}  {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau$. The knowledge from the previous tasks is implicitly encoded in the kernel $k_\tau$, which is based on the feature map $\phi_\tau$. This feature map encodes the acquired knowledge. As an edge case, if two successive tasks are identical, the residual ${\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau = {\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau -
{\mbox{${\mbox{$\mathbf{y}$}}$}}_{\tau - 1 \rightarrow \tau} = 0$, therefore, the upper bound on the Rademacher complexity does not increase.

#### Implications for Curriculum Learning

We also observe that the upper bound depends on the task ordering, which may provide a theoretical explanation on the importance of learning with a curriculum [@Bengio2009curriculum]. In the following, we present an edge case which provided an intuition on how the bound captures the importance of the order. Consider two dissimilar tasks ${\mbox{$\mathcal{T}$}}_1$ and ${\mbox{$\mathcal{T}$}}_2$. A sequence of tasks alternating between ${\mbox{$\mathcal{T}$}}_1$ and ${\mbox{$\mathcal{T}$}}_2$ will lead to a large upper bound, as explained in the first paragraph. While, a sequence of tasks concatenating two sequences of ${\mbox{$\mathcal{T}$}}_1$ then ${\mbox{$\mathcal{T}$}}_2$ will lead to a lower upper bound.

#### Proof Sketch:

The proof techniques for Lemma \[lem:rademacher-tasks\] are exactly the same as the ones for Theorem \[thm:gen-ogd\]. The full proof is presented in Sec. \[subsubsec:bound-rademacher\].

OGD+: Learning without Forgetting {#sec:ogd-plus}
=================================

In the previous section, we demonstrated the limits of OGD, in terms of robustness to catastrophic forgetting on the long run. Now, we present OGD+, an extension of OGD, which we prove robust to catastrophic forgetting, across an arbitrary number of tasks (Lemma \[lem:train-unchanged-ogd-plus\]). Then, we prove tighter generalisation bounds compared to OGD (Theorem \[thm:gen-ogd-plus\]).

The OGD+ Algorithm {#subsec:ogd+-:-the-algorithm}
------------------

Algorithm \[alg:ogd-plus-train\] presents the OGD+ algorithm, we highlight the differences with OGD in red. The main difference is that OGD+ stores the feature maps with respect to the samples from previous tasks, in addition to the feature maps with respect to the samples from the current task, as opposed to OGD. This small change unlocks the proof of Lemma \[lem:train-unchanged-ogd-plus\] given below, which implies tighter bounds for Theorem \[thm:gen-ogd-plus\].

The idea behind OGD+ comes from the convergence Theorem (Sec. \[sec:convergence\], Thm. \[thm:conv\]). After training on a task ${\mbox{$\mathcal{T}$}}_\tau$, the learned model is a linear combination of the previous models. For a given sample ${\mbox{${\mbox{$\mathbf{x}$}}$}}$ from a task ${\mbox{$\mathcal{T}$}}_k$ where $k < \tau$, in order to keep the training error identical, the weights need to be updated along the directions that are orthogonal to *all the subsequent feature maps* of ${\mbox{${\mbox{$\mathbf{x}$}}$}}$. OGD only considers the feature map of the source task of the sample. Storing all the feature maps implies that the learned model back from task ${\mbox{$\mathcal{T}$}}_k$, can be recovered even after training on an arbitrary number of tasks.

In order to compute the feature maps with respect to the previous samples, OGD+ saves these samples in a dedicated memory, we call this storage the *samples memory*. This memory comes in addition to the orthonormal *feature maps memory*. The only role of the *samples memory* is to compute the feature maps. While the proofs below are under the assumption that the memory size is infinite, in the experiments, we keep a limited size for both memories.

1.  Initialize $S_{J}\leftarrow \{\}$ ; [ $S_{D}\leftarrow \{\}$]{}; ${\mbox{${\mbox{$\mathbf{w}$}}$}}\leftarrow {\mbox{${\mbox{$\mathbf{w}$}}$}}_0$

2.  

Memorisation Property of OGD+ {#subsec:memorisation-ogd-plus}
-----------------------------

The key to obtaining tight generalisation bounds for OGD+ is the Lemma \[lem:train-unchanged-ogd-plus\] below. It states that the training error across all previous tasks is unchanged, when training with OGD+.

\[lem:train-unchanged-ogd-plus\] Given a task ${\mbox{$\mathcal{T}$}}_\tau$, for all ${\mbox{${\mbox{$\mathbf{x}$}}$}}_{k, i} \in D_k$, a sample from the training data of a previous task, it holds that: $$f_{\tau}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{k, i}) = f_{k}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{k, i}).$$

The full proof of Lemma \[lem:train-unchanged-ogd-plus\] is presented in App . \[subsubsec:proof-train-unchanged-ogd-plus\].

Generalisation Guarantees for OGD+ {#subsec:generalisation-theorem}
----------------------------------

Now, we state the generalisation theorem for OGD+, which provides tighter generalisation bounds in comparison with Theorem \[thm:gen-ogd\], for OGD.

\[thm:gen-ogd-plus\] Under the same conditions as Theorem \[thm:gen-ogd\], for OGD+, it holds that, for all tasks ${\mbox{$\mathcal{T}$}}_\tau$, within-task and outside-task generalisation error can be bounded as follows $$\begin{aligned}
        {\mbox{$\mathcal{L}$}}_{D_\tau}(f_T^\star) &\leq \frac{\lambda}{2} \sqrt{ \frac{{\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau^T k_{T}
        ({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau,{\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau)^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau}{n_\tau} } + &\\
        &\sum_{k=1}^T {\mathcal{O}}\left( \sqrt{\frac{{\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_k^T (k_t({\mbox{${\mbox{$\mathbf{X}$}}$}}_k , {\mbox{${\mbox{$\mathbf{X}$}}$}}_k) +
        \lambda^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1}  {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_k }{n_k}} \right)  + \Delta_k, &\\
        \intertext{where}
        \Delta_k &= {\mathcal{O}}(\frac{1}{\sqrt{n_k}}) + 3 c \sqrt{\frac{\log(2/\delta) }{2n_k}},  &\\
        \phi_\tau({\mbox{${\mbox{$\mathbf{x}$}}$}}) &= {\mbox{${\mbox{$\mathbf{T}$}}$}}_\tau \nabla_{{\mbox{${\mbox{$\mathbf{w}$}}$}}} f_{\tau-1}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}), &\\
        {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau &= {\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau - {\mbox{${\mbox{$\mathbf{y}$}}$}}_{\tau - 1 \rightarrow \tau}, &\\
        {\mbox{${\mbox{$\mathbf{y}$}}$}}_{\tau - 1 \rightarrow \tau} &= f_{\tau-1}^\star({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau).
    \end{aligned}$$

The generalisation bounds of Theorem \[thm:gen-ogd-plus\] are tighter than the generalisation bounds for OGD. The tightness of the bounds is a consequence of Lemma \[lem:train-unchanged-ogd-plus\]. The term that corresponds to the Rademacher complexity is unchanged, while the term that bounds the training error is tighter. It is also tighter than a standard supervised learning bound, because it captures the transferability of knowledge across tasks through the residual ${\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau$, as opposed to the Supervised Learning only bounds, which would depend on ${\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau$ instead.

#### Proof Sketch

The full proof is presented in App. \[subsec:proof-gen-ogd-plus\]. The proof is based on Lemma \[lem:train-unchanged-ogd-plus\] and Lemma \[lem:rademacher-kernels\]. The proof techniques are the same as the ones for Theorem \[thm:gen-ogd\].

Experiments {#sec:experiments}
===========

We performed experiments on the continual learning benchmark Permuted Mnist. The setup is the same as the one described in (@Goodfellow2013Forgetting, @kirkpatrick2017forgetting, @chaudhry2018efficient, @farajtabar2019orthogonal). However, in order to assess the robustness to catastrophic forgetting over a long sequence of tasks, we increase the size of the task sequence to 15. We generated 15 i.i.d. permutations of the MNIST pixels, then defined each task as a MNIST supervised learning problem with respect to each permutation, respectively. We trained the neural network sequentially on all tasks and tracked the validation loss on all previous tasks. We considered the same neural network architecture and mostly similar hyperparameters as [@farajtabar2019orthogonal]. The reproducibility details are presented in Appendix \[subsec:reproductibility\].

We report the results in Figure \[fig:ogd-plus-acc\], extended results are presented in App . \[subsec:app-exp-gen-extended\]. The plot shows that OGD+ is more robust to catastrophic forgetting than OGD when the tasks occurrence difference is large. It also shows that OGD+ is equivalent to OGD when the tasks occurrence difference is small. These results concur with Lemma \[lem:ogd-train-gen-bounds\] which states that OGD is robust to catastrophic forgetting up to a single task ahead. forgetting up to a single task ahead. They also concur with Lemma \[lem:train-unchanged-ogd-plus\], which states that OGD+ is robust to catastrophic forgetting across any number of tasks. Two probable reasons that OGD+ is not perfectly prone to catastrophic forgetting in the experiment are the memory limit and the non-overparameterization of the neural network, while in Lemma \[lem:train-unchanged-ogd-plus\], we assumed that the memory is unlimited and that the neural network is overparameterized. The results in the Appendix \[subsec:app-exp-gen-extended\] concur with these hypotheses. Fig. \[fig:app:overparam\] shows that the test accuracy through time increases with overparameterization, in which case our approximation is more valid. Fig. \[fig:app:memory\] shows that the test accuracy also increases uniformly with the size of the memory.

We also observe that OGD outperforms OGD+ for shorter term tasks, on the long run (App . \[subsec:app-exp-gen-extended\], Fig. \[fig:app:gen\]). One probable reason is that OGD+ performs a uniform sampling across samples from all past tasks, considering its limited memory budget, and that the memory requirements increase quadratically through tasks, we expect an information loss with respect to the most recent tasks, since the corresponding storage is used by OGD+ to older tasks. OGD uses the equivalent storage for the most recent task.

![Test accuracy on the first 3 tasks of permuted MNIST, for SGD, OGD and OGD+. We report the dynamics of additional tasks in App. \[subsec:app-exp-gen-extended\], Fig. \[fig:app:gen\]. 15 different permutations are used, and the model is trained to classify MNIST digits for 5 epochs for each permutation. The y-axis is truncated for clarity. We report the mean and standard deviation over 5 independent runs. The test error is measured for every 50 mini-batch interval. The vertical dashed lines separate the 15 tasks. []{data-label="fig:ogd-plus-acc"}](figs/out/gen/out.png){width="40.00000%"}

Related works
=============

#### Continual Learning

Approaches to Continual Learning can be categorised into: regularization methods, memory based methods, and dynamic architectural methods. We refer the reader to the survey [@PARISI201954] for an extensive overview on the existing methods. The idea behind memory-based methods is to store data from previous tasks in a buffer of fixed size, which can then be reused during training on the current task (@chaudhry2018efficient, @vandeven2018generative). Dynamic architectural methods rely on growing architectures which keep the past knowledge fixed and store new knowledge in new components, such as new nodes, layers ... (@Lee2017Lifelong, @Schwarz2018ProgressCompress) The idea behind regularization methods is to regularize the objective in order to preserve the knowledge acquired from the previous tasks (@Kirkpatrick2016EWC, @Aljundi2017MAS, @farajtabar2019orthogonal, @Zenke2017SI).

#### Catastrophic Forgetting

Catastrophic Forgetting refers to the tendency of agents to “forget” the previous tasks over the course of training. It has proven to be a challenging problem, several heuristics were developed in order to characterise it (@ANS1997989, @Ans2000Refreshing, @Goodfellow2013Forgetting, @Robert1999Connectionist, @MCCLOSKEY1989109, @Robins1995Rehearsal, @Nguyen2019UnderstandForgetting).

#### Deep Learning Theory

Recent work have started to provide explanations about the mechanics of overparametrised Neural Networks. In their seminal work, @Du2018GD prove that Gradient Descent on multilayer overparametrised RELU neural networks achieve zero training error at the limit. These works have unlocked the analysis of several properties of Deep Neural Networks, in the context of various applications, such as Transfer Learning [@liu2019understanding], Noisy Supervision [@hu2019simple], Reinforcement Learning [@wang2020long] ... Another line of works provide closed form expressions of the training dynamics of overparameterized neural networks, leveraging tools from statistical physics (@Goldt2019Dynamics, @goldt2020modelling).

Also, Corrolary \[cor:weight-dist\] in Sec. \[sec:convergence\] can be seen as a generalisation of the Theorem 3 by @liu2019understanding. While we don’t make any assumptions on the neural network as opposed to @liu2019understanding, which studies two-layer RELU neural networks, our analysis is based on less fine-grained approximations. Finally, as explained in Sec. \[subsec:generalisation-ogd\], we used several proof techniques from @hu2019simple to prove the Theorems \[thm:conv\], \[thm:gen-ogd\] and \[thm:gen-ogd-plus\].

#### Transfer Learning

Several works have also recently started studying Transfer Learning from a theoretical perspective (@yu2020gradient, @liu2019understanding, @Nguyen2019UnderstandForgetting, @Achille2019task2vec).

#### Statistical Learning Theory

@pmlr-v54-alquier17a define a compound regret for lifelong learning, as the regret with respect to the oracle who would have known the best common representation $g$ for all tasks in advance. Another line of works addresses lifelong learning and meta-learning from a statistical learning theory perspective, they define and provide regret bounds for lifelong learning [@pmlr-v54-alquier17a], or study the sample complexity and convergence of meta-learning algorithms (@denevi2018incremental, @du2020fewshot, @ji2020multistep, @saunshi2020sample, @ltl_common_mean).

Discussion {#sec:discussion-limits}
==========

We discuss some assumptions and limits of our analysis.

#### Linearization

We considered a linear approximation of the neural network, which may not be valid in the non overparameterized regime. We find that the approximation leads to multiple insights on how to improve OGD, generalisation, knowledge transferability, curriculum learning and convergence. Also, our analysis is based solely on convex optimisation, which surprisingly leads us to results from other works, which considered other approximations for overparameterized neural networks. Finally, the experiments with non-overparametrized neural networks concur with our theoretical findings.

#### How are the NTKs different between SGD and OGD ?

We note that the key difference comes from the feature map, which is projected with $T$ to a feature space orthogonal to ${\mbox{$\mathbb{E}$}}$. In practice, the size of the data is much smaller than the number of the parameters, therefore, the dimension of ${\mbox{$\mathbb{E}$}}$ is negligible in comparison with the $d$, the dimension of the parameter space of the neural net, independently of the NTK regime. It could be interesting to understand more in depth the difference between the kernels of SGD and OGD. Their formulation looks similar to Von Neumann Kernels, which may be a possible direction to investigate.

Conclusion {#sec:conclusion-and-outlook}
==========

In this paper, we present an approach to study the properties of OGD for Continual Learning theoretically. Through this approach, we present in a closed-form how the model evolves through tasks. This result leads to a generalisation theorem for OGD and provides insights on the transferability of knowledge across tasks and on the importance of task ordering and how the curriculum impacts generalisation. We also present OGD+, an extension of OGD, for which we derive stronger guarantees in terms of robustness to catastrophic forgetting and generalisation error. Finally, we observe that OGD+ achieves state-of-the-art performance for settings with a large number of tasks.

There are multiple avenues for future investigation. First, similarly to @Arora:2019:FineGrained and @liu2019understanding, a lower bound over the number of parameters to fall in the overparameterization regime is an important question, it would clarify the cases for which the theory is valid.

Another possible direction to investigate is the theoretical properties of the other Continual Learning training methods and the catastrophic forgetting heuristics, such as the ones proposed by @Nguyen2019UnderstandForgetting. A theroetical understanding of these algorithms and heuristics, even for asymptotic cases, may provide insights on their limits and directions of improvements, similarly to OGD+.

We also observed in the experiments that uniform sampling across all tasks for OGD+ would be the optimal sampling strategy for an average performance balance across all past tasks. In order to favor remembering specific tasks, a possible direction is adapting the sampling distribution with respect to the past tasks’ importance.

Finally, we found multiple connections to other fields such as Transfer Learning and Curriculum Learning. A promising direction for further investigation is to investigate how the theory could apply to neighbouring fields, such as meta-learning, multi-task learning ... We hope this work provides new keys to address these challenges.

#### Acknowledgements

We would like to thank Mohammad Emtiyaz Khan, Michael Przystupa, Pierre Alquier, Pierre Orenstein and Bo Han for their feedback and the helpful discussions.\
MS was supported by KAKENHI 17H00757.

Missing proofs of section \[sec:convergence\] - Convergence
===========================================================

Proof of Theorem \[thm:conv\] {#subsec:conv-multiple-proof}
-----------------------------

#### Orthogonal Gradient Descent

$$\begin{aligned}
            \intertext{We prove the Theorem \ref{thm:conv} by induction. Our induction hypothesis $H_\tau$ is the
    following :}
            \intertext{$H_\tau$ : For all $k \leq \tau$, Theorem \ref{thm:conv} holds.}
            \intertext{First, we prove that $H_1$ holds.}
            \intertext{The proof is straightforward. For the first task, since there were no previous tasks ${\mbox{$\mathbb{E}$}}_1 =
            \emptyset$. Therefore, OGD on this task is equivalent to SGD.}
            \intertext{Therefore, it is equivalent to minimising the following objective, where $\tau = 1$ : }
            \operatorname*{arg\,min}_{{\mbox{${\mbox{$\mathbf{w}$}}$}}\in {\mbox{$\mathbb{R}$}}^d} &\norm{\phi_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau)^T ({\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau+1}(t) - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau}^\star) -
            {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau+1}}_2^2 + \lambda_\tau \norm{{\mbox{${\mbox{$\mathbf{w}$}}$}}- {\mbox{${\mbox{$\mathbf{w}$}}$}}_0}^2 &\\
            \intertext{The objective is quadratic and the Hessian is positive definite, therefore the minimum exists
            and is unique :}
            {\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau}^\star - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{0} &= \phi_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) (\phi_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau)^T \phi_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) +
            \lambda_{\tau}^2 I)^{-1}
            {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau} &\\
            \intertext{For $\tau = 1$, since there are no previous tasks ${\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau} = {\mbox{${\mbox{$\mathbf{y}$}}$}}_{\tau}$. Therefore :}
            {\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau}^\star - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{0} &= k_{\tau}({\mbox{${\mbox{$\mathbf{x}$}}$}},{\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau)  (k_{\tau}({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau,
            {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) + \lambda_{\tau}^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau} &\\
            \intertext{Which completes the proof of $H_1$.}
    \intertext{Let $\tau \in {\mbox{$\mathbb{N}$}}^\star$, assume $H_\tau$ is true, we show $H_{\tau+1}$ }
    \intertext{On the task $\tau + 1$, we can write the loss ${\mbox{$\mathcal{L}$}}^{\tau+1}$ as :}
    {\mbox{$\mathcal{L}$}}^{\tau+1}({\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau+1}(t)) &= \norm{\phi_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau)^T ({\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau+1}(t) - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau}^\star) -
            {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau+1}}_2^2 + \lambda_{\tau + 1} \norm{{\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau+1} - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau}}^2 &\\
        \intertext{We recall that the optimisation problem at time $(\tau + 1)$ :}
        \operatorname*{arg\,min}_{{\mbox{${\mbox{$\mathbf{w}$}}$}}\in {\mbox{$\mathbb{R}$}}^d} &\norm{\phi_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau)^T ({\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau+1}(t) - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau}^\star) -
            {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau+1}}_2^2 + \lambda_{\tau + 1} \norm{{\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau+1} - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau}}^2 &\\
        \text{u.c.} \quad & {\mbox{${\mbox{$\mathbf{V}$}}$}}_{\tau+1} ({\mbox{${\mbox{$\mathbf{w}$}}$}}- {\mbox{${\mbox{$\mathbf{w}$}}$}}^\star_\tau) = 0 &\\
        \intertext{Let ${\mbox{${\mbox{$\mathbf{T}$}}$}}_{\tau+1} \in {\mbox{$\mathbb{R}$}}^{d \times (d - K_{\tau+1})}$ and ${\mbox{${\mbox{$\mathbf{\tilde{w}}$}}$}}_{\tau+1} \in
        {\mbox{$\mathbb{R}$}}^{d-K_{\tau+1}}$ such as :}
        {\mbox{${\mbox{$\mathbf{w}$}}$}}- {\mbox{${\mbox{$\mathbf{w}$}}$}}^\star_\tau &= {\mbox{${\mbox{$\mathbf{T}$}}$}}_{\tau+1} {\mbox{${\mbox{$\mathbf{\tilde{w}}$}}$}}_{\tau+1} &\\
            K_{\tau+1} &= \dim({\mbox{$\mathbb{E}$}}_{\tau+1}) &\\
        \intertext{We rewrite the objective by plugging in the variables we just defined. The two objectives are
        equivalent : }
        \operatorname*{arg\,min}_{{\mbox{${\mbox{$\mathbf{\tilde{w}}$}}$}}\in {\mbox{$\mathbb{R}$}}^{d - K_{\tau+1}}} &\norm{\phi_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau)^T {\mbox{${\mbox{$\mathbf{T}$}}$}}_{\tau+1} {\mbox{${\mbox{$\mathbf{\tilde{w}}$}}$}}-
            {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau+1}}_2^2 + \lambda_{\tau + 1}^2 \norm{{\mbox{${\mbox{$\mathbf{T}$}}$}}_{\tau+1} {\mbox{${\mbox{$\mathbf{\tilde{w}}$}}$}}}_2^2 &\\
        \intertext{For clarity, we define ${\mbox{${\mbox{$\mathbf{Z}$}}$}}_{\tau+1} {\mbox{$\mathbb{R}$}}^{n_{\tau + 1} \times (d - K_{\tau+1})}$ as :}
        {\mbox{${\mbox{$\mathbf{Z}$}}$}}_{\tau+1} &= \phi_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau)^T {\mbox{${\mbox{$\mathbf{T}$}}$}}_{\tau+1} &\\
        \intertext{By plugging in ${\mbox{${\mbox{$\mathbf{Z}$}}$}}_{\tau+1}$, we rewrite the objective as :}
        \operatorname*{arg\,min}_{{\mbox{${\mbox{$\mathbf{\tilde{w}}$}}$}}\in {\mbox{$\mathbb{R}$}}^{d - K_{\tau+1}} } &\norm{{\mbox{${\mbox{$\mathbf{Z}$}}$}}_{\tau+1} {\mbox{${\mbox{$\mathbf{\tilde{w}}$}}$}}-
            {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau+1}}_2^2 + \lambda_{\tau + 1}^2 \norm{{\mbox{${\mbox{$\mathbf{T}$}}$}}_{\tau+1} {\mbox{${\mbox{$\mathbf{\tilde{w}}$}}$}}}_2^2 &\\
            \intertext{The optimisation objective is quadratic, unconstrainted, with a positive definite hessian.
            Therefore, an optimum exists and is unique :  }
        {\mbox{${\mbox{$\mathbf{\tilde{w}}$}}$}}^\star_{\tau+1} &= {\mbox{${\mbox{$\mathbf{Z}$}}$}}_{\tau+1}^T ({\mbox{${\mbox{$\mathbf{Z}$}}$}}_{\tau+1} {\mbox{${\mbox{$\mathbf{Z}$}}$}}_{\tau+1}^T + \lambda_{\tau+1}^2 I)^{-1}
            {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau+1} &\\
        \intertext{We recover the expression of the optimum in the original space :}
        {\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau+1}^\star - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau}^\star &= {\mbox{${\mbox{$\mathbf{T}$}}$}}_{\tau+1} {\mbox{${\mbox{$\mathbf{Z}$}}$}}_{\tau+1}^T ({\mbox{${\mbox{$\mathbf{Z}$}}$}}_{\tau+1} {\mbox{${\mbox{$\mathbf{Z}$}}$}}_{\tau+1}^T + \lambda_{\tau+1}^2 I)^{-1}
            {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau+1} &\\
        \intertext{We define the kernel $k_{\tau+1} : {\mbox{$\mathbb{R}$}}^d \times {\mbox{$\mathbb{R}$}}^d \rightarrow {\mbox{$\mathbb{R}$}}$ as :}
        k_{\tau+1}({\mbox{${\mbox{$\mathbf{x}$}}$}}, {\mbox{${\mbox{$\mathbf{x}$}}$}}^\prime) &= \phi_\tau({\mbox{${\mbox{$\mathbf{x}$}}$}})^T {\mbox{${\mbox{$\mathbf{T}$}}$}}_{\tau+1} {\mbox{${\mbox{$\mathbf{T}$}}$}}_{\tau+1}^T \phi_\tau({\mbox{${\mbox{$\mathbf{x}$}}$}}^\prime) \quad \text{for all ${\mbox{${\mbox{$\mathbf{x}$}}$}},
            {\mbox{${\mbox{$\mathbf{x}$}}$}}^\prime \in {\mbox{$\mathbb{R}$}}^d$} &\\
        \intertext{Now we rewrite ${\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau+1}^\star - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau}^\star$ :}
        {\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau+1}^\star - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau}^\star &= {\mbox{${\mbox{$\mathbf{T}$}}$}}_{\tau+1} {\mbox{${\mbox{$\mathbf{Z}$}}$}}_{\tau+1}^T (k_{\tau+1}({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau,
            {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) + \lambda_{\tau+1}^2 I)^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau+1} &\\
        \intertext{Finally, we recover a closed form expression for $f_{\tau +1}^\star$ :}
            \intertext{First, we use the induction hypothesis $H_\tau$ :}
        f_{\tau +1}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) &= f_{\tau}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) + \langle \nabla_{{\mbox{${\mbox{$\mathbf{w}$}}$}}} f_{\tau}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) ,{\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau+1}^\star
            - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau}^\star \rangle &\\
        &= f_{\tau}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) + \phi_\tau({\mbox{${\mbox{$\mathbf{x}$}}$}}) {\mbox{${\mbox{$\mathbf{T}$}}$}}_{\tau+1} {\mbox{${\mbox{$\mathbf{Z}$}}$}}_{\tau+1}^T (k_{\tau+1}({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau,
            {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) + \lambda_{\tau+1}^2 I)^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau+1}  &\\
        &= f_{\tau}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) + k_{\tau+1}({\mbox{${\mbox{$\mathbf{x}$}}$}},{\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau)  (k_{\tau+1}({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau,
            {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) + \lambda_{\tau+1}^2 I)^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau+1}  &\\
        \intertext{At this stage, we have proven $H_{t+1}$.}
        \intertext{We conclude.}
    \end{aligned}$$

#### Stochastic Gradient Descent

The proof is exactly the same as the proof for Orthogonal Gradient Descent, except that there are no equalities constraints.

Proof of the Corollary \[cor:weight-dist\] {#subsec:proof-weight-dist}
------------------------------------------

#### Orthogonal Gradient Descent

$$\begin{aligned}
        \intertext{In the proof of Theorem \ref{thm:conv} (App.~\ref{subsec:conv-multiple-proof}), we proved that :}
        {\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau+1}^\star - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau}^\star &= {\mbox{${\mbox{$\mathbf{T}$}}$}}_{\tau+1} {\mbox{${\mbox{$\mathbf{Z}$}}$}}_{\tau+1}^T (k_{\tau+1}({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau,
            {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) + \lambda_{\tau+1}^2 I)^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau+1} &\\
        \intertext{Therefore :}
        \norm{{\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau+1}^\star - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau}^\star}^2  &=
        {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau+1}^T (k_{\tau+1}({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau,
            {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) + \lambda_{\tau+1}^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1} {\mbox{${\mbox{$\mathbf{Z}$}}$}}_{\tau+1} {\mbox{${\mbox{$\mathbf{T}$}}$}}_{\tau+1}^T {\mbox{${\mbox{$\mathbf{T}$}}$}}_{\tau+1} {\mbox{${\mbox{$\mathbf{Z}$}}$}}_{\tau+1}^T (k_{\tau+1}({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau,
            {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) + \lambda_{\tau+1}^2 I)^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau+1} &\\
        &={\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau+1}^T (k_{\tau+1}({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau,
            {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) + \lambda_{\tau+1}^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1} k_{\tau+1}({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau,{\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) (k_{\tau+1}({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau,{\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) +
        \lambda_{\tau+1}^2 I)^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau+1} &\\
    \end{aligned}$$

#### Stochastic Gradient Descent

The proof is exactly the same as for Orthogonal Gradient Descent.

Missing proofs of section \[sec:generalisation\] - Generalisation
=================================================================

Proof of Theorem \[thm:gen-ogd\] {#subsec:proof-gen-ogd}
--------------------------------

### Notations

$$\begin{aligned}
    \intertext{We recall that :}
    f_\tau^\star({\mbox{${\mbox{$\mathbf{x}$}}$}})
    &= \sum_{k=1}^{\tau-1} f_{k}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) + k_\tau({\mbox{${\mbox{$\mathbf{x}$}}$}}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau)^T (k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau , {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau)
    + \lambda_\tau^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau
    \intertext{We define :}
    {\mbox{$\tilde{f}$}}_\tau^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) &= k_\tau({\mbox{${\mbox{$\mathbf{x}$}}$}}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau)^T {\mbox{${\mbox{$\boldsymbol{\alpha}$}}$}}_\tau
    \intertext{where :}
    {\mbox{${\mbox{$\boldsymbol{\alpha}$}}$}}_\tau &= (k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau , {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) + \lambda_\tau^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau  &\\
    \intertext{Then :}
    f_\tau^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) &= \sum_{k=1}^\tau {\mbox{$\tilde{f}$}}_\tau^\star({\mbox{${\mbox{$\mathbf{x}$}}$}})\end{aligned}$$

#### Reminder on RKHS norm

$$\begin{aligned}
    \intertext{Let $k$ a kernel, and ${\mbox{$\mathcal{H}$}}$ the reproducing kernel Hilbert space (RKHS) corresponding to the kernel
    $k$.}
    \intertext{Recall that the RKHS norm of a function $f({\mbox{${\mbox{$\mathbf{x}$}}$}}) = \alpha^T k({\mbox{${\mbox{$\mathbf{x}$}}$}}, {\mbox{${\mbox{$\mathbf{X}$}}$}})$ is :}
    \norm{f}_{{\mbox{$\mathcal{H}$}}} &=  \sqrt{\alpha^T k({\mbox{${\mbox{$\mathbf{X}$}}$}}, {\mbox{${\mbox{$\mathbf{X}$}}$}}) \alpha  } &\\\end{aligned}$$

#### Reminder on Generalization and Rademacher Complexity {#par:recap-rademacher}

Consider a loss function $l : {\mbox{$\mathbb{R}$}}\times {\mbox{$\mathbb{R}$}}\rightarrow {\mbox{$\mathbb{R}$}}$. The population loss over the distribution ${\mbox{$\mathcal{D}$}}$, and the empirical loss over $n$ samples $D = \{({\mbox{${\mbox{$\mathbf{x}$}}$}}_i, y_i), i \in [n] \}$ from the same distribution ${\mbox{$\mathcal{D}$}}$ are defined as : $$\begin{aligned}
    L_D(f) &= {\mathbb{E}}_{({\mbox{${\mbox{$\mathbf{x}$}}$}}, y) \sim {\mbox{$\mathcal{D}$}}} [l(f({\mbox{${\mbox{$\mathbf{x}$}}$}}), y)] &\\
    L_S(f) &= \frac{1}{n} \sum_{i=1}^n l(f({\mbox{${\mbox{$\mathbf{x}$}}$}}_i), y_i)\end{aligned}$$

Suppose the loss function is bounded in $[0, c]$ and is $\rho-$Lipchitz in the first argument. Then, with probability at least $1 - \delta$ over sample $S$ of size n : $$\sup_{f \in {\mbox{$\mathcal{F}$}}} \{L_D(f) - L_S(f)\} \leq 2 \rho \hat{{\mbox{$\mathcal{R}$}}}({\mbox{$\mathcal{F}$}}) + 3 c \sqrt{\frac{\log(2/\delta)}{2n}}$$

### Bounding the Rademacher Complexity

\[lem:rademacher-kernels\] Let $k_t : {\mbox{$\mathcal{X}$}}\cross {\mbox{$\mathcal{X}$}}\rightarrow {\mbox{$\mathbb{R}$}}, t \in [T]$ kernels such that : $$\sup_{{\mbox{${\mbox{$\mathbf{x}$}}$}}\in {\mbox{$\mathcal{X}$}}} \norm{k_t({\mbox{${\mbox{$\mathbf{x}$}}$}}, {\mbox{${\mbox{$\mathbf{x}$}}$}})} < \infty$$ To every kernel $k_t$, we associate a feature map $\phi_t : {\mbox{$\mathcal{X}$}}\rightarrow {\mbox{$\mathcal{H}$}}_t$, where ${\mbox{$\mathcal{H}$}}_t$ is a Hilbert space with inner product $\langle\cdot,\cdot\rangle_{{\mbox{$\mathcal{H}$}}_t}$, and for all ${\mbox{${\mbox{$\mathbf{x}$}}$}}, {\mbox{${\mbox{$\mathbf{x}$}}$}}^\prime \in {\mbox{$\mathcal{X}$}}$, $k_t({\mbox{${\mbox{$\mathbf{x}$}}$}},
    {\mbox{${\mbox{$\mathbf{x}$}}$}}^\prime) = \langle \phi_t({\mbox{${\mbox{$\mathbf{x}$}}$}}), \phi_t({\mbox{${\mbox{$\mathbf{x}$}}$}}^\prime) \rangle_{{\mbox{$\mathcal{H}$}}_t}$

We define ${\mbox{$\mathcal{F}$}}$ as follows : $${\mbox{$\mathcal{F}$}}= \{ {\mbox{${\mbox{$\mathbf{x}$}}$}}\rightarrow \sum_{t=1}^T f_t({\mbox{${\mbox{$\mathbf{x}$}}$}}), \quad f_t({\mbox{${\mbox{$\mathbf{x}$}}$}}) = \alpha_t^T k_t({\mbox{${\mbox{$\mathbf{x}$}}$}}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_t) \quad \forall t \in
        [T], \norm{f_t}_{{\mbox{$\mathcal{H}$}}_t} \leq B_t
        \}$$ Let $X_1, ..., X_n$ be random elements of ${\mbox{$\mathcal{X}$}}$. Then for the class ${\mbox{$\mathcal{F}$}}$, we have : $$\hat{{\mbox{$\mathcal{R}$}}}({\mbox{$\mathcal{F}$}}) \leq \sum_{t=1}^T \frac{2 B_t}{n_t} (Tr(k_t({\mbox{${\mbox{$\mathbf{X}$}}$}}_t, {\mbox{${\mbox{$\mathbf{X}$}}$}}_t)))^{1/2}$$

f() &= \_[t=1]{}\^T \_[i=1]{}\^[n\_t]{} \_i\^t k\_t(, \_i\^t) & , \^k\_t(, \^) &= \_t(), \_t(\^) \_[\_t]{} & f() &= \_[t=1]{}\^T \_[i=1]{}\^[n\_t]{} \_i\^t \_t(\_i\^t), \_t() \_[\_t]{} &\
&= \_[t=1]{}\^T \_[i=1]{}\^[n\_t]{} \_i\^t \_t(\_i\^t), \_t() \_[\_t]{} &\
\_[\_t]{}\^2 &= \_[i, j]{} \_i\^t \_j\^t k\_t(\_i\^t, \_j\^t) B\_t\^2 &\
&{ \_[t=1]{}\^T \_t, \_t() \_[\_t]{}, \_2 B\_t t } := & () &() &\
&= \[ \_[\_2 B\_t, t ]{} \_[t=1]{}\^T \_t, \_[i=1]{}\^[n\_t]{} \_i \_t(\_i\^t) \_[\_t]{} (\_t) \] &\
&= \_[t=1]{}\^T \[ \_[\_2 B\_t ]{} \_t, \_[i=1]{}\^[n\_t]{} \_i \_t(\_i\^t) \_[\_t]{} (\_t) \] &\
&\_[t=1]{}\^T (Tr(k\_t(\_t, \_t)))\^[1/2]{} &\

### Bounding $\norm{{\mbox{$\tilde{f}$}}_\tau^\star}_{{\mbox{$\mathcal{H}$}}_{\tau}}$ :

Let ${\mbox{$\mathcal{H}$}}_\tau$ the Hilbert space associated to the kernel $k_\tau$ .

\_\^() &= k\_(, \_)\^T \_&\
\_&= (k\_(\_, \_) + \_\^2 )\^[-1]{} \_&\
\_[\_]{}\^2 &\_\^T (k\_(\_, \_) + \^2 )\^[-1]{} \_&\

$$\begin{aligned}
        \norm{{\mbox{$\tilde{f}$}}_\tau^\star}_{{\mbox{$\mathcal{H}$}}_{\tau}}^2 &= {\mbox{${\mbox{$\boldsymbol{\alpha}$}}$}}_\tau^T k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) {\mbox{${\mbox{$\boldsymbol{\alpha}$}}$}}_\tau &\\
        &= {\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau^T (k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) + \lambda^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1}  k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) (k_\tau ({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) + \lambda^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})
        ^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau &\\ &\\
        \intertext{Since $(k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}, {\mbox{${\mbox{$\mathbf{X}$}}$}}) + \lambda^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1} \leq k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}, {\mbox{${\mbox{$\mathbf{X}$}}$}})^{-1}$, we get  :}
        \norm{{\mbox{$\tilde{f}$}}_\tau^\star}_{{\mbox{$\mathcal{H}$}}_{\tau}}^2 &\leq {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau^T k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) (k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau,
        {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) + \lambda^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau
    \end{aligned}$$

### Proof of Lemma \[lem:train-unchanged\] {#subsubsec:proof-train-unchanged}

The intuition behind the proof is : since the gradient updates were performed orthogonally to the feature maps of the training data of the source task, the parameters in this space are unchanged, while the remaining space, which was changed, is orthogonal to these features maps, therefore, the inference is the same and the training error remanis the same as at the end of training on the source task.

$$\begin{aligned}
    f_{T}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{T-1, i}) &= f_{T-1}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{T-1, i}) + \langle \phi_T({\mbox{${\mbox{$\mathbf{x}$}}$}}_{T-1, i}), {\mbox{${\mbox{$\mathbf{w}$}}$}}_T^\star - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{T-1}^\star
    \rangle &\\
    &= f_{T-1}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{T-1, i}) + \langle \nabla_{{\mbox{${\mbox{$\mathbf{w}$}}$}}} f({\mbox{${\mbox{$\mathbf{w}$}}$}}_{T-1}^\star, {\mbox{${\mbox{$\mathbf{x}$}}$}}), {\mbox{${\mbox{$\mathbf{w}$}}$}}_T^\star - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{T-1}^\star
    \rangle &\\
    \intertext{Since we the training on task ${\mbox{$\mathcal{T}$}}_T$ is perfomed with OGD, we have : }
    \Pi_{{\mbox{$\mathbb{E}$}}_{T-1}}({\mbox{${\mbox{$\mathbf{w}$}}$}}_T^\star - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{T-1}^\star) &= 0 &\\
    \intertext{Since $\nabla_{{\mbox{${\mbox{$\mathbf{w}$}}$}}} f({\mbox{${\mbox{$\mathbf{w}$}}$}}_{T-1}^\star, {\mbox{${\mbox{$\mathbf{x}$}}$}}) \in {\mbox{$\mathbb{E}$}}_{T-1}$ by definition, it follows that :}
    f_{T}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{T-1, i}) &= f_{T-1}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{T-1, i}) &\\\end{aligned}$$

### Bounding the training error

\[lem:ogd-train-gen-bounds\] The training errors on the source and target tasks can be bounded as follows : $$\begin{aligned}
        \intertext{Let $T \in {\mbox{$\mathbb{N}$}}$ fixed. Then, for all $\tau \in [T]$ }
        \frac{1}{n_T}\sum_{i=1}^{n_T} (f_T^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{T,i}) - y_{T,i})^2 &\leq \frac{1}{n_T} \frac{\lambda^2}{4} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_T^T
    (k_T({\mbox{${\mbox{$\mathbf{X}$}}$}}_T, {\mbox{${\mbox{$\mathbf{X}$}}$}}_T) )^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_T &\\
        \frac{1}{n_{T-1}} \sum_{i=1}^{n_{T-1}} (f_T^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{T-1,i}) - y_{T-1,i})^2 &\leq \frac{1}{n_{T-1}} \frac{\lambda^2}{4}
     {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{T-1}^T  (k_{T-1}({\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}) )^{-1}{\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{T-1} &\\
        \intertext{For all $\tau \in [T-2]$}
        \frac{1}{n_{\tau}} \norm{f_T^\star({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) - {\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau}^2_2 &\leq \frac{1}{n_{\tau}} (\frac{\lambda^2}{4} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau}^T  (k_{\tau}
     ({\mbox{${\mbox{$\mathbf{X}$}}$}}_{\tau}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_{\tau}) )^{-1}{\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau} + &\\
        &\sum_{k=\tau+1}^T \frac{1}{4 \lambda^2} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_k^T k_k({\mbox{${\mbox{$\mathbf{X}$}}$}}_k, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k)
    ^{-1} k({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k) k({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k)^T k_k({\mbox{${\mbox{$\mathbf{X}$}}$}}_k, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k)^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_k)
    \end{aligned}$$

#### Task ${\mbox{$\mathcal{T}$}}_{T}$

$$\begin{aligned}
    \intertext{We start from the definition of the training error :}
        \sum_{i=1}^{n_T} (f_T^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{T,i}) - y_{T,i})^2
    &= \norm{ (k_T({\mbox{${\mbox{$\mathbf{X}$}}$}}_T, {\mbox{${\mbox{$\mathbf{X}$}}$}}_T)^T (k_T({\mbox{${\mbox{$\mathbf{X}$}}$}}_T , {\mbox{${\mbox{$\mathbf{X}$}}$}}_T) + \lambda^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1} - {\mbox{${\mbox{$\mathbf{I}$}}$}}) {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_T }_2^2 &\\
    \intertext{The expression is very similar to the previous norm, we can derive the same analysis as above to derive
    the following bound :}
    \sum_{i=1}^{n_T} (f_T^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{T,i}) - y_{T,i})^2 &\leq \frac{\lambda^2}{4} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_T^T  (k_T({\mbox{${\mbox{$\mathbf{X}$}}$}}_T, {\mbox{${\mbox{$\mathbf{X}$}}$}}_T) )^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_T &\\
    \intertext{Therefore : }
    \frac{1}{n_T}\sum_{i=1}^{n_T} (f_T^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{T,i}) - y_{T,i})^2 &\leq \frac{1}{n_T} \frac{\lambda^2}{4} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_T^T
    (k_T({\mbox{${\mbox{$\mathbf{X}$}}$}}_T, {\mbox{${\mbox{$\mathbf{X}$}}$}}_T) )^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_T &\\\end{aligned}$$

#### Task ${\mbox{$\mathcal{T}$}}_{T-1}$

$$\begin{aligned}
     \intertext{We start with the definition of the training error, then applying Lemma \ref{lem:train-unchanged} :}
        \sum_{i=1}^{n_{T-1}} (f_T^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{T-1,i}) - y_{T-1,i})^2
        &= \sum_{i=1}^{n_{T-1}} (f_{T-1}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{T-1, i}) - y_{T-1,i})^2 &\\
        &= \norm{f_{T-1}^\star({\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}) - {\mbox{${\mbox{$\mathbf{y}$}}$}}_{T-1}}_2^2 &\\
        &= \norm{ k_{T-1}({\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1})^T (k_{T-1}({\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}) + \lambda^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1} - {\mbox{${\mbox{$\mathbf{I}$}}$}})
     {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{T-1}}_2^2 &\\
        &= \norm{ - \lambda^2    (k_{T-1}({\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}) + \lambda^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1}{\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{T-1}}_2^2 &\\
        &= \lambda^4 \norm{ (k_{T-1}({\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}) + \lambda^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1}{\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{T-1}}_2^2 &\\
        &= \lambda^4 {\mbox{${\mbox{$\mathbf{y}$}}$}}_{T-1}^T  (k_{T-1}({\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}) + \lambda^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-2}{\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{T-1} &\\
        \intertext{Since : }
        (k_{T-1}({\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}) + \lambda^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-2} &\leq \frac{1}{4 \lambda^2} k_{T-1}({\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1})^{-1}
        \intertext{We get :}
        \sum_{i=1}^{n_{T-1}} (f_T^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{T-1,i}) - y_{T-1,i})^2 &\leq \frac{\lambda^2}{4} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{T-1}^T  (k_{T-1}
     ({\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}) )^{-1}{\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{T-1} &\\
        \intertext{Therefore :}
        \frac{1}{n_{T-1}} \sum_{i=1}^{n_{T-1}} (f_T^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{T-1,i}) - y_{T-1,i})^2 &\leq \frac{1}{n_{T-1}} \frac{\lambda^2}{4}
     {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{T-1}^T  (k_{T-1}({\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_{T-1}) )^{-1}{\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{T-1}
    \end{aligned}$$

#### Task ${\mbox{$\mathcal{T}$}}_1, ..., {\mbox{$\mathcal{T}$}}_{T-2}$

$$\begin{aligned}
    \intertext{Let $\tau \in [T-2]$ fixed.}
    \intertext{We recall that :}
    f_T^\star({\mbox{${\mbox{$\mathbf{x}$}}$}})
    &= f_\tau^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) + \sum_{k=\tau+1}^T {\mbox{$\tilde{f}$}}_k^\star({\mbox{${\mbox{$\mathbf{x}$}}$}})
    \intertext{Then :}
    \norm{f_T^\star({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) - {\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau}^2_2
    &= \norm{f_\tau^\star({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) + \sum_{k=\tau+1}^T {\mbox{$\tilde{f}$}}_k^\star({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) - {\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau}^2_2  &\\
    &\leq \norm{f_\tau^\star({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) - {\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau}^2_2 + \norm{ \sum_{k=\tau+1}^T {\mbox{$\tilde{f}$}}_k^\star({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) }^2_2 &\\
    &\leq  \underbrace{\norm{f_\tau^\star({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) - {\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau}^2_2}_{{{  \tikz[baseline=(X.base)]
    \node (X) [draw, shape=circle, inner sep=0] {\strut A};}}}  + \underbrace{\sum_{k=\tau+1}^T \norm{
    {\mbox{$\tilde{f}$}}_k^\star ({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) }^2_2}_{{{  \tikz[baseline=(X.base)]
    \node (X) [draw, shape=circle, inner sep=0] {\strut B};}}}
    &\\
    \intertext{We can upper bound {{  \tikz[baseline=(X.base)]
    \node (X) [draw, shape=circle, inner sep=0] {\strut A};}}similarly to the previous paragraphs, therefore we get :}
    \norm{f_\tau^\star({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) - {\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau}^2_2 &\leq \frac{\lambda^2}{4} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau}^T  (k_{\tau}
     ({\mbox{${\mbox{$\mathbf{X}$}}$}}_{\tau}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_{\tau}) )^{-1}{\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau} &\\
    \intertext{Now, we upper bound {{  \tikz[baseline=(X.base)]
    \node (X) [draw, shape=circle, inner sep=0] {\strut B};}}. Let $k \in [\tau+1, \space T]$ :}
    \norm{{\mbox{$\tilde{f}$}}_k^\star ({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) }^2_2
    &= {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_k^T (k_k({\mbox{${\mbox{$\mathbf{X}$}}$}}_k, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k) + \lambda_k^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1} k({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k) k({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k)^T (k_k({\mbox{${\mbox{$\mathbf{X}$}}$}}_k, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k)
    + \lambda_k^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_k &\\
    &= \frac{1}{4 \lambda^2} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_k^T k_k({\mbox{${\mbox{$\mathbf{X}$}}$}}_k, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k)^{-1} \underbrace{k({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k) k({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k)
    ^T}_{\text{Captures the similarity between the tasks ${\mbox{$\mathcal{T}$}}_\tau$ and ${\mbox{$\mathcal{T}$}}_k$}}
    k_k({\mbox{${\mbox{$\mathbf{X}$}}$}}_k, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k)^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_k &\\
    \intertext{We conclude by plugging back the upper bounds of {{  \tikz[baseline=(X.base)]
    \node (X) [draw, shape=circle, inner sep=0] {\strut A};}}and {{  \tikz[baseline=(X.base)]
    \node (X) [draw, shape=circle, inner sep=0] {\strut B};}}}
    \norm{f_T^\star({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) - {\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau}^2_2 &\leq \frac{\lambda^2}{4} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau}^T  (k_{\tau}
     ({\mbox{${\mbox{$\mathbf{X}$}}$}}_{\tau}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_{\tau}) )^{-1}{\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau} +
    \sum_{k=\tau+1}^T \frac{1}{4 \lambda^2} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_k^T k_k({\mbox{${\mbox{$\mathbf{X}$}}$}}_k, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k)
    ^{-1} k({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k) k({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k)^T k_k({\mbox{${\mbox{$\mathbf{X}$}}$}}_k, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k)^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_k
    \intertext{Therefore :}
    \frac{1}{n_{\tau}} \norm{f_T^\star({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) - {\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau}^2_2 &\leq \frac{1}{n_{\tau}} (\frac{\lambda^2}{4} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau}^T  (k_{\tau}
     ({\mbox{${\mbox{$\mathbf{X}$}}$}}_{\tau}, {\mbox{${\mbox{$\mathbf{X}$}}$}}_{\tau}) )^{-1}{\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_{\tau} + \sum_{k=\tau+1}^T \frac{1}{4 \lambda^2} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_k^T k_k({\mbox{${\mbox{$\mathbf{X}$}}$}}_k, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k)
    ^{-1} k({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k) k({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k)^T k_k({\mbox{${\mbox{$\mathbf{X}$}}$}}_k, {\mbox{${\mbox{$\mathbf{X}$}}$}}_k)^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_k)\end{aligned}$$

### Bounding the Rademacher Complexity {#subsubsec:bound-rademacher}

$$\begin{aligned}
        \intertext{The proof strategy is exactly the same as sec. \ref{subsec:proof-gen-ogd}. We generalize the previous
        proof, by applying the same lemmas.}
        {\mbox{$\mathcal{F}$}}_{{\mbox{${\mbox{$\mathbf{B}$}}$}}_T} &= \{ {\mbox{${\mbox{$\mathbf{x}$}}$}}\rightarrow \sum_{\tau=1}^T  f_\tau({\mbox{${\mbox{$\mathbf{x}$}}$}}), \quad f_\tau({\mbox{${\mbox{$\mathbf{x}$}}$}}) = {\mbox{${\mbox{$\boldsymbol{\alpha}$}}$}}_\tau^T k_\tau
        ({\mbox{${\mbox{$\mathbf{x}$}}$}},
        {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) \quad \forall \tau
        \in [T], \norm{f_\tau}_{{\mbox{$\mathcal{H}$}}_\tau} \leq B_\tau\} &\\
        \intertext{It holds that :}
        f_T^\star &\in {\mbox{$\mathcal{F}$}}_{{\mbox{${\mbox{$\mathbf{B}$}}$}}_T} &\\
        \intertext{where, for all $\tau \in [T]$ :}
        B_{\tau} &= \sqrt{({\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau - {\mbox{${\mbox{$\mathbf{y}$}}$}}_{\tau - 1 \rightarrow \tau})^T ( k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau , {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) +
        \lambda^2_\tau {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1}  ({\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau - {\mbox{${\mbox{$\mathbf{y}$}}$}}_{\tau - 1 \rightarrow \tau})} &\\
        \hat{{\mbox{$\mathcal{R}$}}}({\mbox{$\mathcal{F}$}}_{{\mbox{${\mbox{$\mathbf{B}$}}$}}_T}) &\leq \sum_{\tau=1}^T \frac{2(B_\tau + \epsilon) }{n_\tau} (Tr(k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau,
        {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau)))^{1/2} &\\
        \intertext{We made the assumption that for all $\tau \in [T]$ $\trace(k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau)) = {\mathcal{O}}(n_\tau)
        $, also, by setting $\epsilon=1$  :}
        \hat{{\mbox{$\mathcal{R}$}}}({\mbox{$\mathcal{F}$}}_{{\mbox{${\mbox{$\mathbf{B}$}}$}}_T}) &\leq \sum_{\tau=1}^T \frac{2(B_\tau + 1) }{n_\tau} {\mathcal{O}}(\sqrt{n_\tau}) &\\
        &\leq \sum_{\tau=1}^T  {\mathcal{O}}(\frac{B_\tau }{\sqrt{n_\tau}})  + \sum_{\tau=1}^T {\mathcal{O}}(
        \frac{1}{\sqrt{n_\tau}})  &\\
        &\leq \sum_{\tau=1}^T {\mathcal{O}}\left( \sqrt{\frac{({\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau - {\mbox{${\mbox{$\mathbf{y}$}}$}}_{\tau - 1 \rightarrow \tau})^T (
        k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau , {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) + \lambda^2
        {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1}  ({\mbox{${\mbox{$\mathbf{y}$}}$}}_\tau - {\mbox{${\mbox{$\mathbf{y}$}}$}}_{ \tau - 1 \rightarrow \tau}) }{n_\tau}} \right)  + \sum_{\tau=1}^T {\mathcal{O}}(
        \frac{1}{\sqrt{n_\tau}}) &\\
    \end{aligned}$$

### Proof of the Theorem \[thm:gen-ogd\]

$$\begin{aligned}
        \intertext{With probability $1 - \delta$ we have :}
        \sup_{f \in {\mbox{$\mathcal{F}$}}_{{\mbox{${\mbox{$\mathbf{B}$}}$}}_T}} \{L_D(f) - L_S(f)\} &\leq 2 \rho \hat{{\mbox{$\mathcal{R}$}}}({\mbox{$\mathcal{F}$}}_{{\mbox{${\mbox{$\mathbf{B}$}}$}}_T}) + 3 c \sqrt{\frac{\log
        (2/\delta)}{2n}} &\\
        {\mbox{$\mathcal{L}$}}_{D_\tau}(f_T^\star) &\leq {\mbox{$\mathcal{L}$}}_{S_\tau}(f_T^\star) + 2 \rho \hat{{\mbox{$\mathcal{R}$}}}({\mbox{$\mathcal{F}$}}_{{\mbox{${\mbox{$\mathbf{B}$}}$}}_T}) + 3 c \sqrt{\frac{\log
        (2/\delta) }{2n_T}}
        &\\
        {\mbox{$\mathcal{L}$}}_{D_\tau}(f_T^\star) &\leq {\mbox{$\mathcal{L}$}}_{S_\tau}(f_T^\star) + \sum_{\tau=1}^T {\mathcal{O}}\left( \sqrt{\frac{{\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau^T
(k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau ,
        {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) +
        \lambda^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1}  {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau }{n_\tau}} \right)  + \sum_{k=1}^T {\mathcal{O}}(\frac{1}{\sqrt{n_k}}) + 3 c
        \sqrt{\frac{\log(2/\delta) }{2n_\tau}}
        \intertext{We get Theorem \ref{thm:gen-ogd} by replacing into ${\mbox{$\mathcal{L}$}}_{S_\tau}(f_T^\star)$ using the
        inequalities from Lemma \ref{lem:ogd-train-gen-bounds}}
    \end{aligned}$$

Missing proofs of section \[sec:ogd-plus\] - OGD+ : Learning without forgetting {#sec:missing-proofs-of-sectionref--ogd+-:-learning-without-forgetting}
===============================================================================

Memorisation property of OGD+ - Proof {#subsubsec:proof-train-unchanged-ogd-plus}
-------------------------------------

$$\begin{aligned}
        \intertext{In the proof of Theorem \ref{thm:conv}, App.~\ref{subsec:conv-multiple-proof}, we showed that, for
${\mbox{$\mathcal{T}$}}_\tau$ a fixed task:}
        f_{\tau +1}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) &= f_{\tau}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) + \langle \nabla_{{\mbox{${\mbox{$\mathbf{w}$}}$}}} f_{\tau}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) ,{\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau+1}^\star
            - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{\tau}^\star \rangle. &\\
        \intertext{We rewrite the recursive relation into a sum: }
        f_{\tau +1}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) &= \sum_{k=1}^\tau \langle \nabla_{{\mbox{${\mbox{$\mathbf{w}$}}$}}} f_{k}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) ,{\mbox{${\mbox{$\mathbf{w}$}}$}}_{k+1}^\star
            - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{k}^\star \rangle. &\\
        \intertext{We observe that, for all $k \in [T]$: }
        {\mbox{${\mbox{$\mathbf{w}$}}$}}_{k+1}^\star - {\mbox{${\mbox{$\mathbf{w}$}}$}}_{k}^\star &\in {\mbox{$\mathbb{E}$}}_{k^\prime}.
        \intertext{On the other hand, for OGD+, given a sample ${\mbox{${\mbox{$\mathbf{x}$}}$}}$ from ${\mbox{$\mathcal{D}$}}_\tau$, for all $k^\prime \in [\tau + 1, T]$ :}
        \nabla_{{\mbox{${\mbox{$\mathbf{w}$}}$}}} f_{k}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) \in {\mbox{$\mathbb{E}$}}_{k^\prime}
        \intertext{Therefore, for all $k^\prime \in [k + 1, \tau]$ :}
        \langle \nabla_{{\mbox{${\mbox{$\mathbf{w}$}}$}}} f_{k^\prime}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) ,{\mbox{${\mbox{$\mathbf{w}$}}$}}_{k^\prime+1}^\star- {\mbox{${\mbox{$\mathbf{w}$}}$}}_{k^\prime}^\star \rangle = 0
        \intertext{Therefore :}
        f_{\tau}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}) &= f_{k}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}})
        \intertext{We conclude.}
    \end{aligned}$$

OGD+ Generalisation Theorem - Proof {#subsec:proof-gen-ogd-plus}
-----------------------------------

$$\begin{aligned}
    \intertext{The proof is very similar to the proof of Theorem \ref{thm:gen-ogd}.}
    \intertext{Let ${\mbox{$\mathcal{T}$}}_\tau$ a given task and $T \in {\mbox{$\mathbb{N}$}}^\star$ fixed }
    \intertext{We start from the following result in Appendix \ref{subsec:proof-gen-ogd}.}
    {\mbox{$\mathcal{L}$}}_{D_\tau}(f_T^\star) &\leq {\mbox{$\mathcal{L}$}}_{S_\tau}(f_T^\star) + \sum_{k=1}^T {\mathcal{O}}\left( \sqrt{\frac{{\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_k^T
(k_k({\mbox{${\mbox{$\mathbf{X}$}}$}}_k ,
        {\mbox{${\mbox{$\mathbf{X}$}}$}}_k) +
        \lambda^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1}  {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_k }{n_k}} \right)  + \sum_{k=1}^T {\mathcal{O}}(\frac{1}{\sqrt{n_k}}) + 3 c
        \sqrt{\frac{\log(2/\delta) }{2n_\tau}}
    \intertext{We apply Lemma \ref{lem:train-unchanged-ogd-plus} for tasks ${\mbox{$\mathcal{T}$}}_\tau$ and ${\mbox{$\mathcal{T}$}}_T$ :}
    f_{T}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{\tau, i}) &= f_{\tau}^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{\tau, i}).
    \intertext{Therefore :}
    {\mbox{$\mathcal{L}$}}_{S_\tau}(f_T^\star) &= {\mbox{$\mathcal{L}$}}_{S_\tau}(f_\tau^\star)
    \intertext{We replace into the first inequality :}
    {\mbox{$\mathcal{L}$}}_{D_\tau}(f_T^\star) &\leq {\mbox{$\mathcal{L}$}}_{S_\tau}(f_\tau^\star) + \sum_{k=1}^T {\mathcal{O}}\left( \sqrt{\frac{{\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_k^T
(k_k({\mbox{${\mbox{$\mathbf{X}$}}$}}_k ,
        {\mbox{${\mbox{$\mathbf{X}$}}$}}_k) +
        \lambda^2 {\mbox{${\mbox{$\mathbf{I}$}}$}})^{-1}  {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_k }{n_k}} \right)  + \sum_{k=1}^T {\mathcal{O}}(\frac{1}{\sqrt{n_k}}) + 3 c
        \sqrt{\frac{\log(2/\delta) }{2n_\tau}}
    \intertext{We recall the folowwing result from the proof of Theorem \ref{thm:gen-ogd} in App.
    \ref{subsec:proof-gen-ogd} :}
    \frac{1}{n_\tau}\sum_{i=1}^{n_\tau} (f_\tau^\star({\mbox{${\mbox{$\mathbf{x}$}}$}}_{\tau,i}) - y_{\tau,i})^2 &\leq \frac{1}{n_\tau} \frac{\lambda^2}{4} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau^\tau
    (k_\tau({\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau, {\mbox{${\mbox{$\mathbf{X}$}}$}}_\tau) )^{-1} {\mbox{${\mbox{$\mathbf{\tilde{y}}$}}$}}_\tau &\\
    \intertext{By replacing into the previous inequality, we conclude the proof of Theorem \ref{thm:gen-ogd-plus}.}\end{aligned}$$

Experiments : {#experiments}
=============

Reproducibility {#subsec:reproductibility}
---------------

### Code details

We implemented the code for the experiments in PyTorch. We initially forked the code from [https://github .com/GMvandeVen/continual-learning](https://github .com/GMvandeVen/continual-learning) . This source code is related to the works @vandeven2018generative and @vandeven2019three.

### Hyperparameters {#subsec:hyperparameters}

We use the same architecture and mostly the same hyperparameters as @farajtabar2019orthogonal. We also keep a small learning rate, in order to preserve the locality assumption of OGD, and in order to verify the conditions of the theorems.

The neural network is a three-layer MLP with 100 hidden units in two layers, each layer uses RELU activation function. The model has 10 logit outputs, which do not use any activation function. The optimiser is either SGD or OGD and the loss is Softmax cross-entropy. We report the hyperparameters in detail in Table \[tab:hyperparam\].

  ---------------- --------
  Hyperparameter   Value
  Learning rate    1e-02
  Batch size       256
  Epochs           5
  Torch seeds      0 to 4
  Memory size      1000
  Activation       RELU
  ---------------- --------

  : Hyperparameters used across experiments[]{data-label="tab:hyperparam"}

### Experiment setup {#subsec:experiment-setup}

We run each experiment 5 times, the seeds set is the same across all experiments sets. We report the mean and standard deviation of the measurements. The test error is measured every 50 mini-batch interval.

### OGD+ Implementation Details

In practice, we split the memories uniformly across tasks. Also, we construct ${\mbox{$\mathcal{S}$}}$ from ${\mbox{$\mathcal{S}$}}_{D}$ by sampling uniformly without replacement. Finally, for the memory reduction step, we truncate the last elements of the storage to free-up the space for the next task’s data.

Additional experiments
----------------------

### OGD+ Generalisation {#subsec:app-exp-gen-extended}

[.32]{} ![Test accuracy on the 10 first tasks of permuted MNIST, for SGD, OGD and OGD+. 15 different permutations are used, and the model is trained to classify MNIST digits for 5 epochs for each permutation. The y-axis is truncated for clarity. We report the mean and standard deviation over 5 independent runs. The test error is measured for every 50 mini-batch interval. The vertical dashed lines separate the 15 tasks.[]{data-label="fig:app:gen"}](figs/out/gen/val_acc_1.png "fig:"){width="\textwidth"}

[.32]{} ![Test accuracy on the 10 first tasks of permuted MNIST, for SGD, OGD and OGD+. 15 different permutations are used, and the model is trained to classify MNIST digits for 5 epochs for each permutation. The y-axis is truncated for clarity. We report the mean and standard deviation over 5 independent runs. The test error is measured for every 50 mini-batch interval. The vertical dashed lines separate the 15 tasks.[]{data-label="fig:app:gen"}](figs/out/gen/val_acc_5.png "fig:"){width="\textwidth"}

[.32]{} ![Test accuracy on the 10 first tasks of permuted MNIST, for SGD, OGD and OGD+. 15 different permutations are used, and the model is trained to classify MNIST digits for 5 epochs for each permutation. The y-axis is truncated for clarity. We report the mean and standard deviation over 5 independent runs. The test error is measured for every 50 mini-batch interval. The vertical dashed lines separate the 15 tasks.[]{data-label="fig:app:gen"}](figs/out/gen/val_acc_2.png "fig:"){width="\textwidth"}

[.32]{} ![Test accuracy on the 10 first tasks of permuted MNIST, for SGD, OGD and OGD+. 15 different permutations are used, and the model is trained to classify MNIST digits for 5 epochs for each permutation. The y-axis is truncated for clarity. We report the mean and standard deviation over 5 independent runs. The test error is measured for every 50 mini-batch interval. The vertical dashed lines separate the 15 tasks.[]{data-label="fig:app:gen"}](figs/out/gen/val_acc_6.png "fig:"){width="\textwidth"}

[.32]{} ![Test accuracy on the 10 first tasks of permuted MNIST, for SGD, OGD and OGD+. 15 different permutations are used, and the model is trained to classify MNIST digits for 5 epochs for each permutation. The y-axis is truncated for clarity. We report the mean and standard deviation over 5 independent runs. The test error is measured for every 50 mini-batch interval. The vertical dashed lines separate the 15 tasks.[]{data-label="fig:app:gen"}](figs/out/gen/val_acc_3.png "fig:"){width="\textwidth"}

[.32]{} ![Test accuracy on the 10 first tasks of permuted MNIST, for SGD, OGD and OGD+. 15 different permutations are used, and the model is trained to classify MNIST digits for 5 epochs for each permutation. The y-axis is truncated for clarity. We report the mean and standard deviation over 5 independent runs. The test error is measured for every 50 mini-batch interval. The vertical dashed lines separate the 15 tasks.[]{data-label="fig:app:gen"}](figs/out/gen/val_acc_7.png "fig:"){width="\textwidth"}

[.32]{} ![Test accuracy on the 10 first tasks of permuted MNIST, for SGD, OGD and OGD+. 15 different permutations are used, and the model is trained to classify MNIST digits for 5 epochs for each permutation. The y-axis is truncated for clarity. We report the mean and standard deviation over 5 independent runs. The test error is measured for every 50 mini-batch interval. The vertical dashed lines separate the 15 tasks.[]{data-label="fig:app:gen"}](figs/out/gen/val_acc_4.png "fig:"){width="\textwidth"}

[.32]{} ![Test accuracy on the 10 first tasks of permuted MNIST, for SGD, OGD and OGD+. 15 different permutations are used, and the model is trained to classify MNIST digits for 5 epochs for each permutation. The y-axis is truncated for clarity. We report the mean and standard deviation over 5 independent runs. The test error is measured for every 50 mini-batch interval. The vertical dashed lines separate the 15 tasks.[]{data-label="fig:app:gen"}](figs/out/gen/val_acc_8.png "fig:"){width="\textwidth"}

### OGD+ Overparameterization

[.50]{} ![Test accuracy on the 3 first tasks of permuted MNIST, for the MLP’s hidden dimensions 100, 250 and 400. The y-axis is truncated for clarity. We report the mean and standard deviation over 5 independent runs. The test error is measured for every 50 mini-batch interval. The vertical dashed lines separate the 15 tasks.[]{data-label="fig:app:overparam"}](figs/out/hidden/val_acc_1.png "fig:"){width="\textwidth"}

[.50]{} ![Test accuracy on the 3 first tasks of permuted MNIST, for the MLP’s hidden dimensions 100, 250 and 400. The y-axis is truncated for clarity. We report the mean and standard deviation over 5 independent runs. The test error is measured for every 50 mini-batch interval. The vertical dashed lines separate the 15 tasks.[]{data-label="fig:app:overparam"}](figs/out/hidden/val_acc_2.png "fig:"){width="\textwidth"}

[.50]{} ![Test accuracy on the 3 first tasks of permuted MNIST, for the MLP’s hidden dimensions 100, 250 and 400. The y-axis is truncated for clarity. We report the mean and standard deviation over 5 independent runs. The test error is measured for every 50 mini-batch interval. The vertical dashed lines separate the 15 tasks.[]{data-label="fig:app:overparam"}](figs/out/hidden/val_acc_3.png "fig:"){width="\textwidth"}

### OGD+ Memory size

[.50]{} ![Test accuracy on the 3 first tasks of permuted MNIST, for the memory sizes 1.000, 1.500 and 2.000. The y-axis is truncated for clarity. We report the mean and standard deviation over 5 independent runs. The test error is measured for every 50 mini-batch interval. The vertical dashed lines separate the 15 tasks.[]{data-label="fig:app:memory"}](figs/out/mem/val_acc_1.png "fig:"){width="\textwidth"}

[.50]{} ![Test accuracy on the 3 first tasks of permuted MNIST, for the memory sizes 1.000, 1.500 and 2.000. The y-axis is truncated for clarity. We report the mean and standard deviation over 5 independent runs. The test error is measured for every 50 mini-batch interval. The vertical dashed lines separate the 15 tasks.[]{data-label="fig:app:memory"}](figs/out/mem/val_acc_2.png "fig:"){width="\textwidth"}

[.50]{} ![Test accuracy on the 3 first tasks of permuted MNIST, for the memory sizes 1.000, 1.500 and 2.000. The y-axis is truncated for clarity. We report the mean and standard deviation over 5 independent runs. The test error is measured for every 50 mini-batch interval. The vertical dashed lines separate the 15 tasks.[]{data-label="fig:app:memory"}](figs/out/mem/val_acc_3.png "fig:"){width="\textwidth"}
