Introduction
Continual learning (CL) aims to learn from a sequence of non-stationary data streams and tasks over time. However, this classical training paradigm remains vulnerable to a fundamental challenge, known as catastrophic forgetting [1 , 2 ] , in which the model exhibits a substantial degradation in performance on previously learned tasks as it adapts to newly introduced tasks.
To mitigate catastrophic forgetting, several empirical methods have been proposed and have achieved promising results [3 ] . However, the theoretical understanding remains much less developed. Existing analyses have largely focused on the linear regime [4 , 5 , 6 , 7 , 8 ] or the neural tangent kernel (NTK) regime [9 , 10 , 11 ] . While linear models yield explicit forgetting bounds, the resulting guarantees depend on the assumed linear structure. NTK-based analyses extend the study to neural networks, but typically rely on infinite-width limits. Moreover, most of these studies analyze forgetting through closed-form solutions to the optimization problem, abstracting away the fine-grained dynamics of iterative updates and yielding coarse bounds. Recently, Zheng et al. [11 ] analyze forgetting dynamics through NTK gradient flow, which captures more detailed trajectories than conventional static analyses. Taheri et al. [12 ] characterize forgetting in two-layer quadratic neural networks in the kernel regime, deriving explicit empirical forgetting bounds for orthogonal XOR-cluster tasks and using algorithmic stability to control delayed generalization. These studies provide insights into how forgetting evolves during training, while their guarantees remain tied to specific kernel approximations, network architectures, or task structures. This motivates an analysis of training dynamics, without prescribing a particular network architecture, that tracks both within-task updates and the propagation of their effects across tasks.
In this work, we develop an algorithmic stability analysis of expected forgetting in CL. We quantify forgetting as the expected increase in population risk on historical tasks and decompose it into intra-task generalization gaps (IGG), cross-task generalization gaps (CGG), and empirical forgetting (EF). To bound the generalization terms, we characterize stability under a sample perturbation in either the current task or a historical task. We follow SGD trajectories to track how the perturbation affects updates within that task and propagates through subsequent tasks. This analysis yields generalization bounds for constant, intra-task decaying, and continuously decaying learning rate schedules in the convex setting, and for the two decaying schedules in the non-convex setting. Under intra-task decay, the learning rate decreases from the same initial value within each task, whereas under continuous decay, it continues decreasing across task boundaries. Comparing these schedules allows us to characterize how resetting the learning rate at task boundaries affects the propagation of historical sample perturbations. For EF, we analyze changes in empirical risk on historical tasks along the optimization trajectory, retaining the cumulative inner products between gradients of historical tasks and those of the current task. The EF analysis covers all three learning rate schedules without requiring convexity. Combining these results yields bounds on expected population forgetting that explicitly account for both generalization gaps and empirical risk changes.
As summarized in Table I , the bounds reveal distinct effects of learning-rate scheduling on generalization and empirical forgetting. For convex losses with step sizes at most 2 / β 2/\beta 2/ β O ( N / n ) \mathcal{O}(N/n) O ( N / n )
Table I. Results for the IGG, CGG, and EF under convex and non-convex loss functions with three learning-rate (LR) schedules: constant (C), intra-task decaying (ID), and continuously decaying (CD). Here, T T T i ∈ [ T − 1 ] i \in[T-1] i ∈ [ T − 1 ] N N N n n n L L L β \beta β p = c β c β + 1 p=\frac{c\beta}{c\beta+1} p = c β + 1 c β c c c G T , i G_{T,i} G T , i (6) . For the non-convex ID setting, the IGG and CGG upper bounds reported in the table apply when 2 c L 2 < N 2cL^{2}<N 2 c L 2 < N 2 c L 2 ( e N ) c β ( T − i ) < N 2cL^{2}(eN)^{c\beta(T-i)}<N 2 c L 2 ( e N ) c β ( T − i ) < N N / n N/n N / n § 4 .
learning rates and O ( log ( e N ) / n ) O(\log(eN)/n) O ( log ( e N ) / n ) N N N i > 1 i>1 i > 1 i > 1 i>1 i > 1 c c c β \beta β L L L T T T i i i i > 1 i>1 i > 1 O ( 1 / n ) O(1/n) O ( 1/ n ) N N N n n n O ( N ) O(N) O ( N ) O ( 1 ) O(1) O ( 1 ) O ( 1 / N ) O(1/N) O ( 1/ N )
Our main contributions can be summarized as follows:
We derive explicit IGG and CGG bounds for continual SGD by tracking sample perturbations within a task and through subsequent tasks. These bounds characterize the effects of sample size, local training length, the total number of tasks, and learning-rate schedules.
We derive an EF bound in terms of cumulative gradient alignment and an explicit second-order term involving squared learning rates. The bound reveals how positive cumulative gradient alignment contributes to controlling empirical forgetting.
We derive upper bounds on expected forgetting through combining the IGG, CGG, and EF bounds, linking generalization with changes in empirical risk along the continual learning trajectory.
Empirical studies in CL. Continual learning has made substantial progress in empirical methods for mitigating catastrophic forgetting. We divide these methods into three main families: (1) replay-based methods, which either store data from previous tasks and replay it during training on the current task [13 , 14 , 15 ] , or store gradient or feature information from prior tasks and constrain the current-task gradient to be orthogonal to the stored information [16 , 17 , 18 , 19 , 20 ] ; (2) regularization-based methods, which aim to restrain updates of parameters that are important for previous tasks [21 , 22 ] , or maintain consistency of intermediate features by adding a regularization term to the loss [23 ] ; and (3) architecture-based methods, which dynamically expand or adapt the model architecture to preserve knowledge from previous tasks [24 , 25 , 26 ] .
Theoretical analysis of CL. Recent theoretical studies on CL have mainly focused on catastrophic forgetting and generalization. Broadly speaking, the existing literature can be divided into two main lines of work: linear model analysis and NTK-based analysis. Under the linear regime, Evron et al. [4 ] , Lin et al. [5 ] investigate forgetting and generalization under the assumptions of overparameterized linear models. Ding et al. [6 ] study forgetting in both overparameterized and underparameterized regimes while relaxing the data assumptions to fourth-moment conditions. Moreover, several works use linear models to analyze concrete methods for mitigating forgetting, including replay-based methods [8 , 27 , 28 ] , regularization-based methods [7 , 29 , 30 , 31 ] , and mixture-of-experts methods [32 ] . The other main line of theoretical work relies on the NTK regime. Specifically, Bennani et al. [33 ] establish generalization error bounds for CL based on the NTK and Rademacher complexity. Doan et al. [9 ] analyze forgetting by introducing the NTK overlap matrix as a task similarity metric. Karakida and Akaho [10 ] study forgetting and generalization error through learning-curve analysis between two tasks. Zheng et al. [11 ] further characterize the training-time dynamics of forgetting and generalization in the general CL setting. Taheri et al. [12 ] analyze forgetting in two-layer quadratic neural networks in the kernel regime, deriving explicit empirical forgetting bounds for orthogonal XOR-cluster tasks and using algorithmic stability to control delayed generalization. Liu et al. [34 ] derive generalization bounds for parameter-efficient fine-tuning in CL. However, these theoretical analyses have several limitations: (1) they rely on restrictive model assumptions, such as linear models, infinite-width models, or infinitesimal learning rates, which make the results less general; and (2) the upper bounds derived in the NTK setting often involve complicated kernel matrices, making them difficult to interpret and generalize. In contrast, we analyze forgetting through a fine-grained characterization of the training trajectory without restrictive model assumptions. Moreover, our bounds depend only on a few readily interpretable quantities, such as the training set size, local training length, learning-rate schedule, and gradient inner products between tasks.
The work most closely related to ours is that of Taheri et al. [12 ] , who analyze forgetting using algorithmic stability. Our analysis differs in three aspects: (1) Their theoretical results are developed for two-layer neural networks with quadratic activations and fixed output-layer weights, whereas our analysis does not prescribe a particular network architecture. (2) Their explicit empirical forgetting guarantees rely on orthogonal XOR-cluster tasks and the specified network model. Our EF bound requires only that each sample loss be Lipschitz continuous and smooth with respect to the model parameters, without imposing these structural assumptions. Their delayed generalization analysis also uses Lipschitz and smoothness assumptions on the loss. (3) Their main forgetting and generalization theorems adopt constant learning rates, whereas we examine constant, intra-task decaying, and continuously decaying learning rates.
Preliminary
Continual Learning Setting
We consider the standard CL setting with T ≥ 2 T \ge2 T ≥ 2 n n n [ n ] : = { 1 , … , n } [n] := \{1,\ldots,n\} [ n ] := { 1 , … , n } τ ∈ [ T ] \tau\in[T] τ ∈ [ T ] D τ \mathcal{D}_{\tau} D τ n n n S τ = ( z τ , 1 , … , z τ , n ) S_{\tau} = (z_{\tau,1},\ldots,z_{\tau,n}) S τ = ( z τ , 1 , … , z τ , n ) D τ \mathcal{D}_{\tau} D τ S 1 : T : = { S 1 , … , S T } S_{1:T} := \{S_1,\ldots,S_T\} S 1 : T := { S 1 , … , S T } T T T f f f Ω = R d \Omega= \mathbb{R}^{d} Ω = R d
w τ , t + 1 = w τ , t − η τ , t ∇ w f ( w τ , t ; z τ , i t ) , w_{\tau,t+1} = w_{\tau,t} - \eta_{\tau,t} \nabla_w f(w_{\tau,t}; z_{\tau,i_t}), w τ , t + 1 = w τ , t − η τ , t ∇ w f ( w τ , t ; z τ , i t ) , where η τ , t ≥ 0 \eta_{\tau,t} \ge0 η τ , t ≥ 0 i t i_t i t [ n ] [n] [ n ] w τ , t w_{\tau,t} w τ , t t t t τ \tau τ N N N t = 0 , … , N − 1 t = 0,\ldots,N-1 t = 0 , … , N − 1 w τ = w τ , N w_{\tau} = w_{\tau,N} w τ = w τ , N τ \tau τ w τ , 0 = w τ − 1 w_{\tau,0} = w_{\tau-1} w τ , 0 = w τ − 1 w 0 w_0 w 0
Furthermore, we define the population risk of w τ w_{\tau} w τ D i \mathcal{D}_i D i R D i ( w τ ) R_{\mathcal{D}_i}(w_{\tau}) R D i ( w τ ) w τ w_{\tau} w τ S i S_i S i R S i ( w τ ) R_{S_i}(w_{\tau}) R S i ( w τ )
R D i ( w τ ) : = E z ∼ D i f ( w τ ; z ) , R_{\mathcal{D}_i}(w_{\tau}) := \mathbb{E}_{z\sim\mathcal{D}_i} f(w_{\tau};z), R D i ( w τ ) := E z ∼ D i f ( w τ ; z ) , R S i ( w τ ) : = 1 n ∑ k = 1 n f ( w τ ; z i , k ) . R_{S_i}(w_{\tau}) := \frac{1}{n}\sum_{k=1}^{n} f(w_{\tau};z_{i,k}). R S i ( w τ ) := n 1 k = 1 ∑ n f ( w τ ; z i , k ) . We next adopt the definition of forgetting from Zheng et al. [11 ] , Taheri et al. [12 ] , which characterizes the model’s performance over the underlying data distribution. The formal definition is given in Definition 1.
Definition 1 (Forgetting in expectation). For any i ∈ [ T ] i \in[T] i ∈ [ T ] w i = A ( S 1 : i ) w_i = \mathcal{A}(S_{1:i}) w i = A ( S 1 : i ) A \mathcal{A} A S 1 : i S_{1:i} S 1 : i
F T = 1 T − 1 ∑ i = 1 T − 1 E S 1 : T , A [ R D i ( w T ) − R D i ( w i ) ] . (1) F_T = \frac{1}{T-1}\sum_{i=1}^{T-1}\mathbb{E}_{S_{1:T},\mathcal{A}}\left[R_{\mathcal{D}_i}(w_T)-R_{\mathcal{D}_i}(w_i)\right]. \tag*{(1)} F T = T − 1 1 i = 1 ∑ T − 1 E S 1 : T , A [ R D i ( w T ) − R D i ( w i ) ] . (1) Discussion. Definition 1 generalizes backward transfer (BWT) [35 ] , a conventional metric for evaluating forgetting, in two respects. First, BWT measures forgetting on a test dataset, whereas F T F_T F T F T F_T F T F T F_T F T
Algorithmic Stability
In the non-CL setting, standard algorithmic stability typically concerns perturbations in the current training data only. In CL, by contrast, the model is exposed to a sequence of tasks, so perturbations at different tasks can propagate differently through the subsequent training trajectory. To reflect this sequential structure, we propose intra-task uniform stability for perturbations on the current task and cross-task uniform stability for perturbations on a historical task.
Definition 2 (Intra-task uniform stability). For any i ∈ [ T ] i \in[T] i ∈ [ T ] A \mathcal{A} A ϵ i , i \epsilon_{i,i} ϵ i , i i i i i i i S 1 : i , S 1 : i ′ ∈ Z i × n S_{1:i},S'_{1:i} \in\mathcal{Z}^{i\times n} S 1 : i , S 1 : i ′ ∈ Z i × n i i i
sup z E A [ f ( A ( S 1 : i ) ; z ) − f ( A ( S 1 : i ′ ) ; z ) ] ≤ ϵ i , i . (2) \sup_z \mathbb{E}_{\mathcal{A}}\left[f(\mathcal{A}(S_{1:i});z)-f(\mathcal{A}(S'_{1:i});z)\right] \le\epsilon_{i,i}. \tag*{(2)} z sup E A [ f ( A ( S 1 : i ) ; z ) − f ( A ( S 1 : i ′ ) ; z ) ] ≤ ϵ i , i . (2) Definition 3 (Cross-task uniform stability). For any i ∈ [ T − 1 ] i \in[T-1] i ∈ [ T − 1 ] A \mathcal{A} A ϵ T , i \epsilon_{T,i} ϵ T , i i i i T T T S 1 : T , S 1 : T ′ ∈ Z T × n S_{1:T},S'_{1:T} \in\mathcal{Z}^{T\times n} S 1 : T , S 1 : T ′ ∈ Z T × n i i i
sup z E A [ f ( A ( S 1 : T ) ; z ) − f ( A ( S 1 : T ′ ) ; z ) ] ≤ ϵ T , i . (3) \sup_z \mathbb{E}_{\mathcal{A}}\left[f(\mathcal{A}(S_{1:T});z)-f(\mathcal{A}(S'_{1:T});z)\right] \le\epsilon_{T,i}. \tag*{(3)} z sup E A [ f ( A ( S 1 : T ) ; z ) − f ( A ( S 1 : T ′ ) ; z ) ] ≤ ϵ T , i . (3) In the following analysis, ϵ i , i \epsilon_{i,i} ϵ i , i ϵ T , i \epsilon_{T,i} ϵ T , i
In this work, we follow Hardt et al. [36 ] , Wang et al. [37 ] , Chen et al. [38 ] , Liu et al. [39 ] , Zhu et al. [40 ] to adopt the standard assumptions used in algorithmic stability analysis:
Assumption 1 (L-Lipschitz). For every z ∈ Z z \in\mathcal{Z} z ∈ Z f ( ⋅ ; z ) : Ω → R f(\cdot; z): \Omega\to\mathbb{R} f ( ⋅ ; z ) : Ω → R L L L u , v ∈ Ω u, v \in\Omega u , v ∈ Ω
∣ f ( u ; z ) − f ( v ; z ) ∣ ≤ L ∥ u − v ∥ . \lvert f(u; z) - f(v; z) \rvert\le L\lVert u-v\rVert. ∣ f ( u ; z ) − f ( v ; z )∣ ≤ L ∥ u − v ∥ . Assumption 2 (β \beta β For every z ∈ Z z \in\mathcal{Z} z ∈ Z f ( ⋅ ; z ) : Ω → R f(\cdot; z): \Omega\to\mathbb{R} f ( ⋅ ; z ) : Ω → R β \beta β u , v ∈ Ω u, v \in\Omega u , v ∈ Ω
∥ ∇ f ( u ; z ) − ∇ f ( v ; z ) ∥ ≤ β ∥ u − v ∥ . \lVert\nabla f(u; z) - \nabla f(v; z) \rVert\le\beta\lVert u-v\rVert. ∥ ∇ f ( u ; z ) − ∇ f ( v ; z )∥ ≤ β ∥ u − v ∥ . Assumption 3 (Convex). For every z ∈ Z z \in\mathcal{Z} z ∈ Z f ( ⋅ ; z ) : Ω → R f(\cdot; z): \Omega\to\mathbb{R} f ( ⋅ ; z ) : Ω → R u , v ∈ Ω u, v \in\Omega u , v ∈ Ω
f ( u ; z ) ≥ f ( v ; z ) + ⟨ ∇ f ( v ; z ) , u − v ⟩ . f(u; z) \ge f(v; z) + \langle\nabla f(v; z), u-v\rangle. f ( u ; z ) ≥ f ( v ; z ) + ⟨ ∇ f ( v ; z ) , u − v ⟩ . Theoretical Analysis
In this section, we provide a theoretical analysis of catastrophic forgetting. To comprehensively analyze the forgetting measure F T F_T F T (1) , it is important to derive a fine-grained decomposition that allows us to understand forgetting from multiple perspectives:
F T = 1 T − 1 ∑ i = 1 T − 1 E S 1 : T , A [ R D i ( w T ) − R S i ( w T ) ] ⏟ Cross-Task Generalization Gap + E S 1 : T , A [ R S i ( w T ) − R S i ( w i ) ] + E S 1 : T , A [ R S i ( w i ) − R D i ( w i ) ] . (4) \begin{aligned}
F_T ={}& \frac{1}{T-1}\sum_{i=1}^{T-1}\underbrace{\mathbb{E}_{S_{1:T},\mathcal{A}}\left[R_{\mathcal{D}_i}(w_T)-R_{S_i}(w_T)\right]}_{\text{Cross-Task Generalization Gap}}\\
&+\mathbb{E}_{S_{1:T},\mathcal{A}}\left[R_{S_i}(w_T)-R_{S_i}(w_i)\right]\\
&+\mathbb{E}_{S_{1:T},\mathcal{A}}\left[R_{S_i}(w_i)-R_{\mathcal{D}_i}(w_i)\right]. \tag*{(4)}
\end{aligned} F T = T − 1 1 i = 1 ∑ T − 1 Cross-Task Generalization Gap E S 1 : T , A [ R D i ( w T ) − R S i ( w T ) ] + E S 1 : T , A [ R S i ( w T ) − R S i ( w i ) ] + E S 1 : T , A [ R S i ( w i ) − R D i ( w i ) ] . (4) Based on the decomposition in Equation (4) , we analyze the forgetting measure F T F_T F T
Intra-Task Generalization Gap (§ 4 -A). This term captures the generalization behavior of the trained model on the current task. A smaller absolute intra-task generalization gap indicates closer agreement between the empirical risk and the population risk on the current task.
Cross-Task Generalization Gap (§ 4 -B). This term reflects the generalization behavior of the model trained on later tasks when evaluated on earlier task distributions. A smaller absolute cross-task generalization gap indicates closer agreement between the empirical risk and the population risk on previous tasks.
Empirical Forgetting (§ 4 -C). This term captures how much performance on the training set of task i i i T T T
In what follows, we derive upper bounds for these three terms under convex and non-convex loss functions, respectively, to provide a comprehensive understanding of catastrophic forgetting in CL.
Intra-Task Generalization Gap
The intra-task generalization gap (IGG) describes the generalization performance on the current task. We next present an important theorem showing that intra-task uniform stability implies an upper bound on the intra-task generalization gap in expectation. The result is stated in Theorem 1, and the corresponding proof is given in Appendix B-A.
Theorem 1. For any i ∈ [ T ] i \in[T] i ∈ [ T ] A \mathcal{A} A ϵ i , i \epsilon_{i,i} ϵ i , i
∣ E S 1 : i , A [ R D i ( A ( S 1 : i ) ) − R S i ( A ( S 1 : i ) ) ] ∣ ≤ ϵ i , i . \left|\mathbb{E}_{S_{1:i},\mathcal{A}}\left[R_{\mathcal{D}_i}(\mathcal{A}(S_{1:i}))-R_{S_i}(\mathcal{A}(S_{1:i}))\right]\right| \le\epsilon_{i,i}. ∣ E S 1 : i , A [ R D i ( A ( S 1 : i )) − R S i ( A ( S 1 : i )) ] ∣ ≤ ϵ i , i . Theorem 1 shows that an intra-task uniformly stable algorithm will have a small IGG. This suggests that we can control the uniform stability itself, rather than directly bounding the generalization gap. We then provide the corresponding upper bound under both convex and non-convex loss functions.
First, we establish an upper bound for the case where the loss function is convex in Theorem 2, and the proof of Theorem 2 is given in Appendix B-B.
Theorem 2. Assume that the loss function f ( ⋅ ; z ) f(\cdot; z) f ( ⋅ ; z ) N N N τ ∈ [ i ] \tau\in[i] τ ∈ [ i ] η τ , t ≤ 2 β \eta_{\tau,t} \le\frac{2}{\beta} η τ , t ≤ β 2
ϵ i , i ≤ 2 L 2 n ∑ t = 0 N − 1 η i , t . (5) \epsilon_{i,i} \le\frac{2L^2}{n}\sum_{t=0}^{N-1}\eta_{i,t}. \tag*{(5)} ϵ i , i ≤ n 2 L 2 t = 0 ∑ N − 1 η i , t . (5) Moreover, for different learning rate schedules, including the constant learning rate η τ , t = c \eta_{\tau,t}=c η τ , t = c η τ , t = c t + 1 \eta_{\tau,t}=\frac{c}{t+1} η τ , t = t + 1 c η τ , t = c ( τ − 1 ) N + t + 1 \eta_{\tau,t}=\frac{c}{(\tau-1)N+t+1} η τ , t = ( τ − 1 ) N + t + 1 c (5) can be further written as
ϵ i , i ≤ { 2 c L 2 N n , if η τ , t = c , 2 c L 2 ln ( e N ) n , if η τ , t = c t + 1 , 2 c L 2 n ln ( 1 + 1 i − 1 ) , if η τ , t = c ( τ − 1 ) N + t + 1 , i > 1. \epsilon_{i,i} \le
\begin{cases}
\frac{2cL^2N}{n}, & \text{if } \eta_{\tau,t}=c,\\
\frac{2cL^2\ln(eN)}{n}, & \text{if } \eta_{\tau,t}=\frac{c}{t+1},\\
\frac{2cL^2}{n}\ln\left(1+\frac{1}{i-1}\right), & \text{if } \eta_{\tau,t}=\frac{c}{(\tau-1)N+t+1},\ i>1.
\end{cases} ϵ i , i ≤ ⎩ ⎨ ⎧ n 2 c L 2 N , n 2 c L 2 l n ( e N ) , n 2 c L 2 ln ( 1 + i − 1 1 ) , if η τ , t = c , if η τ , t = t + 1 c , if η τ , t = ( τ − 1 ) N + t + 1 c , i > 1. Remark 3. The upper bound on ϵ i , i \epsilon_{i,i} ϵ i , i N N N O ( ln ( e N ) ) O(\ln(eN)) O ( ln ( e N )) i = 1 i=1 i = 1 i > 1 i>1 i > 1 N N N i i i
Before presenting the IGG bounds for non-convex losses, we introduce the following notation for a recurring term in the subsequent analysis:
K N : = c β + 1 n c β ( 2 c L 2 ) 1 c β + 1 N c β c β + 1 . \mathcal{K}_{N}:=\frac{c\beta+1}{nc\beta}(2cL^{2})^{\frac{1}{c\beta+1}}N^{\frac{c\beta}{c\beta+1}}. K N := n c β c β + 1 ( 2 c L 2 ) c β + 1 1 N c β + 1 c β . The subscript specifies the number of iterations, with c c c β \beta β L L L n n n i i i
K i N = c β + 1 n c β ( 2 c L 2 ) 1 c β + 1 ( i N ) c β c β + 1 . \mathcal{K}_{iN}=\frac{c\beta+1}{nc\beta}(2cL^{2})^{\frac{1}{c\beta+1}}(iN)^{\frac{c\beta}{c\beta+1}}. K i N = n c β c β + 1 ( 2 c L 2 ) c β + 1 1 ( i N ) c β + 1 c β . Then, we derive an upper bound for the more challenging non-convex case in Theorem 3, and the proof of Theorem 3 is given in Appendix B-C.
Theorem 3. Assume that the loss function f ( ⋅ ; z ) ∈ [ 0 , 1 ] f(\cdot;z)\in[0,1] f ( ⋅ ; z ) ∈ [ 0 , 1 ] n ≥ 2 n\ge2 n ≥ 2 c , β > 0 c,\beta>0 c , β > 0 N N N τ ∈ [ i ] \tau\in[i] τ ∈ [ i ] η τ , t \eta_{\tau,t} η τ , t
(a) under intra-task decaying learning rates η τ , t = c t + 1 \eta_{\tau,t}=\frac{c}{t+1} η τ , t = t + 1 c
ϵ i , i ≤ { K N − 2 L 2 β n , if 2 c L 2 < N , N n , if 2 c L 2 ≥ N . \epsilon_{i,i}\le
\begin{cases}
\mathcal{K}_{N}-\frac{2L^{2}}{\beta n}, & \text{if }2cL^{2}<N,\\
\frac{N}{n}, & \text{if }2cL^{2}\ge N.
\end{cases} ϵ i , i ≤ { K N − β n 2 L 2 , n N , if 2 c L 2 < N , if 2 c L 2 ≥ N . (b) under continuously decaying learning rates η τ , t = c ( τ − 1 ) N + t + 1 \eta_{\tau,t}=\frac{c}{(\tau-1)N+t+1} η τ , t = ( τ − 1 ) N + t + 1 c i > 1 i>1 i > 1
ϵ i , i ≤ { 2 L 2 β n [ ( i i − 1 ) c β − 1 ] , if 2 c L 2 ≤ C 1 C D , K i N − ( i − 1 ) N n − 2 L 2 β n , if C 1 C D < 2 c L 2 < i N , N n , if 2 c L 2 ≥ i N , \epsilon_{i,i}\le
\begin{cases}
\frac{2L^{2}}{\beta n}\left[\left(\frac{i}{i-1}\right)^{c\beta}-1\right], & \text{if }2cL^{2}\le C_{1}^{\mathrm{CD}},\\
\mathcal{K}_{iN}-\frac{(i-1)N}{n}-\frac{2L^{2}}{\beta n}, & \text{if }C_{1}^{\mathrm{CD}}<2cL^{2}<iN,\\
\frac{N}{n}, & \text{if }2cL^{2}\ge iN,
\end{cases} ϵ i , i ≤ ⎩ ⎨ ⎧ β n 2 L 2 [ ( i − 1 i ) c β − 1 ] , K i N − n ( i − 1 ) N − β n 2 L 2 , n N , if 2 c L 2 ≤ C 1 CD , if C 1 CD < 2 c L 2 < i N , if 2 c L 2 ≥ i N , where
C 1 C D = ( i − 1 ) N ( i − 1 i ) c β . C_{1}^{\mathrm{CD}}=(i-1)N\left(\frac{i-1}{i}\right)^{c\beta}. C 1 CD = ( i − 1 ) N ( i i − 1 ) c β . Remark 4. Theorem 3 provides an upper bound for the IGG without assuming convexity of the loss function. Let p = c β / ( 1 + c β ) p=c\beta/(1+c\beta) p = c β / ( 1 + c β ) 2 c L 2 < N 2cL^{2}<N 2 c L 2 < N O ( N p / n ) O(N^{p}/n) O ( N p / n ) c , β , L > 0 c,\beta,L>0 c , β , L > 0 [36 ] in the single-task setting. As n → ∞ n\to\infty n → ∞ N = o ( n 1 / p ) N=o(n^{1/p}) N = o ( n 1/ p ) n 1 / p n^{1/p} n 1/ p 2 c L 2 ≥ N 2cL^{2}\ge N 2 c L 2 ≥ N N / n N/n N / n
Remark 5. For i > 1 i>1 i > 1 2 c L 2 ≤ C 1 C D 2cL^{2}\le C_{1}^{\mathrm{CD}} 2 c L 2 ≤ C 1 CD N N N i i i i ≥ 2 i\ge2 i ≥ 2 2 L 2 β n ( 2 c β − 1 ) \frac{2L^{2}}{\beta n}(2^{c\beta}-1) β n 2 L 2 ( 2 c β − 1 ) C 1 C D < 2 c L 2 < i N C_{1}^{\mathrm{CD}}<2cL^{2}<iN C 1 CD < 2 c L 2 < i N N N N 2 L 2 β n [ ( i / ( i − 1 ) ) c β − 1 ] \frac{2L^{2}}{\beta n}[(i/(i-1))^{c\beta}-1] β n 2 L 2 [( i / ( i − 1 ) ) c β − 1 ] N N N c , β , L , n , N c,\beta,L,n,N c , β , L , n , N 0 < 2 c L 2 < i N 0<2cL^{2}<iN 0 < 2 c L 2 < i N 2 c L 2 ≥ i N 2cL^{2}\ge iN 2 c L 2 ≥ i N N / n N/n N / n N < n N<n N < n
Cross-Task Generalization Gap
The cross-task generalization gap (CGG) captures the generalization performance on earlier tasks. Next, we present the relationship between cross-task uniform stability and the expected CGG, which reflects how perturbations on historical tasks propagate through training in the CL setting and affect CGG. The result is stated in Theorem 4, and the proof is given in Appendix C-A.
Theorem 4. For any i ∈ [ T − 1 ] i\in[T-1] i ∈ [ T − 1 ] A \mathcal{A} A ϵ τ , i \epsilon_{\tau,i} ϵ τ , i
∣ E S 1 : T , A [ R D i ( A ( S 1 : T ) ) − R S i ( A ( S 1 : T ) ) ] ∣ ≤ ϵ τ , i . \left|\mathbb{E}_{S_{1:T},\mathcal{A}}\left[R_{D_i}\left(\mathcal{A}(S_{1:T})\right)-R_{S_i}\left(\mathcal{A}(S_{1:T})\right)\right]\right|\le\epsilon_{\tau,i}. ∣ E S 1 : T , A [ R D i ( A ( S 1 : T ) ) − R S i ( A ( S 1 : T ) ) ] ∣ ≤ ϵ τ , i . Theorem 4 indicates that small cross-task uniform stability leads to a small CGG. We then analyze CGG under both convex and non-convex loss functions.
First, we establish an upper bound for the case where the loss function is convex in Theorem 5, and the proof of Theorem 5 is given in Appendix C-B.
Theorem 5. Assume that the loss function f ( ⋅ ; z ) f(\cdot;z) f ( ⋅ ; z ) N N N τ ∈ [ T ] \tau\in[T] τ ∈ [ T ] η τ , t ≤ 2 β \eta_{\tau,t}\le\frac{2}{\beta} η τ , t ≤ β 2
ϵ T , i ≤ 2 L 2 n ∑ t = 0 N − 1 η i , t . \epsilon_{T,i}\le\frac{2L^{2}}{n}\sum_{t=0}^{N-1}\eta_{i,t}. ϵ T , i ≤ n 2 L 2 t = 0 ∑ N − 1 η i , t . Remark 6. Theorem 5 surprisingly shows that the bound for the CGG coincides with that for the IGG under convex loss functions. This indicates that, under convexity, the algorithmic stability of SGD is preserved throughout the entire sequence of tasks. Even as the model parameters are continuously updated using data from new tasks, the resulting bound on the expected generalization gap on historical tasks does not grow. This conclusion relies on the non-expansive property of convex and smooth loss functions, as established in Lemma 1. Therefore, the discussion of IGG bound in Remark 3 remains valid for CGG as well.
Then, we derive an upper bound for the more challenging non-convex case in Theorem 6, and the proof of Theorem 6 is given in Appendix C-C.
Theorem 6. Assume that the loss function f ( ⋅ ; z ) ∈ [ 0 , 1 ] f(\cdot;z)\in[0,1] f ( ⋅ ; z ) ∈ [ 0 , 1 ] n ≥ 2 n\ge2 n ≥ 2 c , β > 0 c,\beta>0 c , β > 0 N N N τ ∈ [ T ] \tau\in[T] τ ∈ [ T ] η τ , t \eta_{\tau,t} η τ , t t = 0 , … , N − 1 t=0,\ldots,N-1 t = 0 , … , N − 1
(a) under intra-task decaying learning rates η τ , t = c t + 1 \eta_{\tau,t}=\frac{c}{t+1} η τ , t = t + 1 c
ϵ ~ T , i ≤ { B 2 1 , if 2 c L 2 ( e N ) c β ( T − i ) < N , N n , if 2 c L 2 ( e N ) c β ( T − i ) ≥ N . \widetilde{\epsilon}_{T,i}\le
\begin{cases}
\mathcal{B}_{2}^{1}, & \text{if }2cL^{2}(eN)^{c\beta(T-i)}<N,\\
\frac{N}{n}, & \text{if }2cL^{2}(eN)^{c\beta(T-i)}\ge N.
\end{cases} ϵ T , i ≤ { B 2 1 , n N , if 2 c L 2 ( e N ) c β ( T − i ) < N , if 2 c L 2 ( e N ) c β ( T − i ) ≥ N . where
B 2 1 = K N ( e N ) c β ( T − i ) c β + 1 − 2 L 2 ( e N ) c β ( T − i ) β n . \mathcal{B}_{2}^{1}=\mathcal{K}_{N}(eN)^{\frac{c\beta(T-i)}{c\beta+1}}-\frac{2L^{2}(eN)^{c\beta(T-i)}}{\beta n}. B 2 1 = K N ( e N ) c β + 1 c β ( T − i ) − β n 2 L 2 ( e N ) c β ( T − i ) . (b) under continuously decaying learning rates η τ , t = c ( τ − 1 ) N + t + 1 \eta_{\tau,t}=\frac{c}{(\tau-1)N+t+1} η τ , t = ( τ − 1 ) N + t + 1 c i > 1 i>1 i > 1
ϵ ~ T , i ≤ { 2 L 2 β n [ ( T i − 1 ) c β − ( T i ) c β ] , if 2 c L 2 ≤ C 2 C D , B 2 2 , if C 2 C D < 2 c L 2 < i N ( i − 1 T ) c β , N n , if 2 c L 2 ≥ i N ( i − 1 T ) c β . \widetilde{\epsilon}_{T,i}\le
\begin{cases}
\frac{2L^{2}}{\beta n}\left[\left(\frac{T}{i-1}\right)^{c\beta}-\left(\frac{T}{i}\right)^{c\beta}\right], & \text{if }2cL^{2}\le\mathcal{C}_{2}^{\mathrm{CD}},\\
\mathcal{B}_{2}^{2}, & \text{if }\mathcal{C}_{2}^{\mathrm{CD}}<2cL^{2}<iN\left(\frac{i-1}{T}\right)^{c\beta},\\
\frac{N}{n}, & \text{if }2cL^{2}\ge iN\left(\frac{i-1}{T}\right)^{c\beta}.
\end{cases} ϵ T , i ≤ ⎩ ⎨ ⎧ β n 2 L 2 [ ( i − 1 T ) c β − ( i T ) c β ] , B 2 2 , n N , if 2 c L 2 ≤ C 2 CD , if C 2 CD < 2 c L 2 < i N ( T i − 1 ) c β , if 2 c L 2 ≥ i N ( T i − 1 ) c β . where
B 2 2 = K T N − ( i − 1 ) N n − 2 L 2 β n ( T i ) c β , \mathcal{B}_{2}^{2}=\mathcal{K}_{TN}-\frac{(i-1)N}{n}-\frac{2L^{2}}{\beta n}\left(\frac{T}{i}\right)^{c\beta}, B 2 2 = K T N − n ( i − 1 ) N − β n 2 L 2 ( i T ) c β , C 2 C D = ( i − 1 ) N ( i − 1 T ) c β . \mathcal{C}_{2}^{\mathrm{CD}}=(i-1)N\left(\frac{i-1}{T}\right)^{c\beta}. C 2 CD = ( i − 1 ) N ( T i − 1 ) c β . For i = 1 i=1 i = 1
ϵ ~ T , 1 ≤ { K T N − 2 L 2 T c β β n , if 2 c L 2 T c β < N , N n , if 2 c L 2 T c β ≥ N . \widetilde{\epsilon}_{T,1}\le
\begin{cases}
\mathcal{K}_{TN}-\frac{2L^{2}T^{c\beta}}{\beta n}, & \text{if }2cL^{2}T^{c\beta}<N,\\
\frac{N}{n}, & \text{if }2cL^{2}T^{c\beta}\ge N.
\end{cases} ϵ T , 1 ≤ { K T N − β n 2 L 2 T c β , n N , if 2 c L 2 T c β < N , if 2 c L 2 T c β ≥ N . Remark 7. Under intra-task decaying learning rates, the displayed CGG bound is nondecreasing in the number of subsequent tasks and is no smaller than the corresponding IGG bound. When 2 c L 2 ( e N ) c β ( T − i ) < N 2cL^{2}(eN)^{c\beta(T-i)}<N 2 c L 2 ( e N ) c β ( T − i ) < N n → ∞ n\to\infty n → ∞ N = o ( n 1 / [ p ( T − i + 1 ) ] ) N=o(n^{1/[p(T-i+1)]}) N = o ( n 1/ [ p ( T − i + 1 )] ) c , β , L , T , i c,\beta,L,T,i c , β , L , T , i N = o ( n 1 / p ) N=o(n^{1/p}) N = o ( n 1/ p ) B 2 1 \mathcal{B}_{2}^{1} B 2 1 1 / ( c β + 1 ) 1/(c\beta+1) 1/ ( c β + 1 )
Remark 8. Under continuous decay, the learning rate continues to decrease across task boundaries, whereas intra-task decay resets it to c c c ( T / i ) c β (T/i)^{c\beta} ( T / i ) c β ( e N ) c β ( T − i ) (eN)^{c\beta(T-i)} ( e N ) c β ( T − i ) N N N i > 1 i>1 i > 1 2 L 2 β n [ ( T / ( i − 1 ) ) c β − ( T / i ) c β ] \frac{2L^{2}}{\beta n}\left[(T/(i-1))^{c\beta}-(T/i)^{c\beta}\right] β n 2 L 2 [ ( T / ( i − 1 ) ) c β − ( T / i ) c β ] 2 c L 2 ≤ ( i − 1 ) N ( ( i − 1 ) / T ) c β 2cL^{2}\le(i-1)N((i-1)/T)^{c\beta} 2 c L 2 ≤ ( i − 1 ) N (( i − 1 ) / T ) c β i i i N N N c , β , L , T , i c,\beta,L,T,i c , β , L , T , i i > 1 i>1 i > 1 O ( 1 / n ) O(1/n) O ( 1/ n ) N N N n → ∞ n\to\infty n → ∞
Empirical Forgetting
Empirical Forgetting (EF) quantifies the degradation in performance on the training set of a previous task caused by learning subsequent tasks. We denote ϵ ~ T , i = E S 1 : T , A [ R S i ( w T ) − R S i ( w i ) ] \widetilde{\epsilon}_{T,i}=\mathbb{E}_{S_{1:T},A}[R_{S_i}(w_T)-R_{S_i}(w_i)] ϵ T , i = E S 1 : T , A [ R S i ( w T ) − R S i ( w i )] i i i i i i T T T i i i
G T , i : = ∑ τ = i + 1 T ∑ t = 0 N − 1 η τ , t E S 1 : T , A [ ⟨ ∇ R S i ( w τ , t ) , ∇ R S τ ( w τ , t ) ⟩ ] . (6) \mathcal{G}_{T,i}:=\sum_{\tau=i+1}^{T}\sum_{t=0}^{N-1}\eta_{\tau,t}\mathbb{E}_{S_{1:T},A}\left[\langle\nabla R_{S_i}(w_{\tau,t}),\nabla R_{S_\tau}(w_{\tau,t})\rangle\right]. \tag*{(6)} G T , i := τ = i + 1 ∑ T t = 0 ∑ N − 1 η τ , t E S 1 : T , A [ ⟨ ∇ R S i ( w τ , t ) , ∇ R S τ ( w τ , t )⟩ ] . (6) Here, G T , i \mathcal{G}_{T,i} G T , i i i i ϵ ~ T , i \widetilde{\epsilon}_{T,i} ϵ T , i
Theorem 7. Assume that the loss function f ( ⋅ ; z ) f(\cdot;z) f ( ⋅ ; z ) N N N τ ∈ [ T ] \tau\in[T] τ ∈ [ T ] η τ , t \eta_{\tau,t} η τ , t
(a) under constant learning rates η τ , t = c \eta_{\tau,t}=c η τ , t = c
ϵ ~ T , i ≤ − G T , i + β c 2 L 2 2 N ( T − i ) ; \widetilde{\epsilon}_{T,i}\le-\mathcal{G}_{T,i}+\frac{\beta c^{2}L^{2}}{2}N(T-i); ϵ T , i ≤ − G T , i + 2 β c 2 L 2 N ( T − i ) ; (b) under intra-task decaying learning rates η τ , t = c t + 1 \eta_{\tau,t}=\frac{c}{t+1} η τ , t = t + 1 c
ϵ ~ T , i ≤ − G T , i + β c 2 L 2 2 ( 2 − 1 N ) ( T − i ) ; \widetilde{\epsilon}_{T,i}\le-\mathcal{G}_{T,i}+\frac{\beta c^{2}L^{2}}{2}\left(2-\frac{1}{N}\right)(T-i); ϵ T , i ≤ − G T , i + 2 β c 2 L 2 ( 2 − N 1 ) ( T − i ) ; (c) under continuously decaying learning rates η τ , t = c ( τ − 1 ) N + t + 1 \eta_{\tau,t}=\frac{c}{(\tau-1)N+t+1} η τ , t = ( τ − 1 ) N + t + 1 c
ϵ ~ T , i ≤ − G T , i + β c 2 L 2 2 ( 1 i N − 1 T N ) . \widetilde{\epsilon}_{T,i}\le-\mathcal{G}_{T,i}+\frac{\beta c^{2}L^{2}}{2}\left(\frac{1}{iN}-\frac{1}{TN}\right). ϵ T , i ≤ − G T , i + 2 β c 2 L 2 ( i N 1 − T N 1 ) . Remark 9. Theorem 7 bounds empirical forgetting in terms of the cumulative inner products between the old-task and current-task gradients and the squared learning rates. A positive G T , i \mathcal{G}_{T,i} G T , i T T T i i i c c c L L L β \beta β N N N β c 2 L 2 ( T − i ) \beta c^{2}L^{2}(T-i) β c 2 L 2 ( T − i ) N N N N N N N N N 1 / N 1/N 1/ N
As discussed in Remark 9, a positive G T , i \mathcal{G}_{T,i} G T , i i i i
Relation to gradient alignment mechanisms. GEM [35 ] aims to mitigate negative BWT by projecting the current gradient onto the set of directions having nonnegative inner products with all previous-task memory gradients. Let M i \mathcal{M}_i M i i i i t t t τ \tau τ
min g ~ τ , t 1 2 ∥ g ~ τ , t − ∇ f ( w τ , t ; z τ , t ) ∥ 2 \min_{\widetilde{g}_{\tau,t}} \frac{1}{2}\left\|\widetilde{g}_{\tau,t}-\nabla f(w_{\tau,t};z_{\tau,t})\right\|^2 g τ , t min 2 1 ∥ g τ , t − ∇ f ( w τ , t ; z τ , t ) ∥ 2 s.t. ⟨ g ~ τ , t , 1 ∣ M i ∣ ∑ z ∈ M i ∇ f ( w τ , t ; z ) ⟩ ≥ 0 , ∀ i < τ . (7) \text{s.t. }\left\langle\widetilde{g}_{\tau,t},\frac{1}{|\mathcal{M}_i|}\sum_{z\in\mathcal{M}_i}\nabla f(w_{\tau,t};z)\right\rangle\ge0,\quad\forall i<\tau. \tag*{(7)} s.t. ⟨ g τ , t , ∣ M i ∣ 1 z ∈ M i ∑ ∇ f ( w τ , t ; z ) ⟩ ≥ 0 , ∀ i < τ . (7) The parameters are then updated as w τ , t + 1 = w τ , t − η τ , t g ~ τ , t w_{\tau,t+1}=w_{\tau,t}-\eta_{\tau,t}\widetilde{g}_{\tau,t} w τ , t + 1 = w τ , t − η τ , t g τ , t [13 ] replaces these individual constraints with a single constraint based on a reference gradient estimated from samples drawn from the combined episodic memory. Both methods seek to reduce gradient interference with past data, which is consistent with the role of cumulative gradient alignment captured by − G T , i -\mathcal{G}_{T,i} − G T , i
Observable CGA. To examine the role of gradient alignment in empirical forgetting, we accumulate the learning-rate-weighted inner products between historical evaluation-loss gradients and the actual training gradients. We estimate the historical gradients using measurement buffers sampled from previous tasks and denote the resulting cumulative alignment by G ^ T , i \widehat{\mathcal{G}}_{T,i} G T , i
As shown in Figure 1 , the estimated CGA is large and positive under constant learning rates, particularly for earlier tasks. Under intra-task decay, its magnitude is substantially smaller, although EF and − G ^ T , i -\widehat{\mathcal{G}}_{T,i} − G T , i
Figure 1. EF and CGA under different learning-rate schedules on Split CIFAR-100. C, ID, and CD denote constant, intra-task decaying, and continuously decaying learning rates, respectively. Curves show the means over three seeds, and shaded regions indicate one standard deviation.
Forgetting in Expectation
In this section, we summarize the discussions in Sections IV-A, IV-B, and IV-C. Specifically, the forgetting measure F T F_T F T
F T ≤ 1 T − 1 ∑ i = 1 T − 1 ( ϵ T , i + ϵ i , i + ϵ ~ T , i ) . (8) F_T\leq\frac{1}{T-1}\sum_{i=1}^{T-1}\left(\epsilon_{\mathcal{T},i}+\epsilon_{i,i}+\widetilde{\epsilon}_{T,i}\right). \tag*{(8)} F T ≤ T − 1 1 i = 1 ∑ T − 1 ( ϵ T , i + ϵ i , i + ϵ T , i ) . (8) We next provide upper bounds on F T F_T F T
Theorem 8. Assume that the loss function f ( ⋅ ; z ) f(\cdot;z) f ( ⋅ ; z ) β > 0 \beta>0 β > 0 N N N τ ∈ [ T ] \tau\in[T] τ ∈ [ T ] η τ , t ≤ 2 / β \eta_{\tau,t}\leq2/\beta η τ , t ≤ 2/ β 0 < c ≤ 2 / β 0<c\leq2/\beta 0 < c ≤ 2/ β
(a) under constant learning rates η τ , t = c \eta_{\tau,t}=c η τ , t = c
F T ≤ − ∑ i = 1 T − 1 G T , i T − 1 + β c 2 L 2 N T 4 + 4 c L 2 N n ; F_T\leq-\frac{\sum_{i=1}^{T-1}\mathcal{G}_{T,i}}{T-1}+\frac{\beta c^2L^2NT}{4}+\frac{4cL^2N}{n}; F T ≤ − T − 1 ∑ i = 1 T − 1 G T , i + 4 β c 2 L 2 N T + n 4 c L 2 N ; (b) under intra-task decaying learning rates η τ , t = c t + 1 \eta_{\tau,t}=\frac{c}{t+1} η τ , t = t + 1 c
F T ≤ − ∑ i = 1 T − 1 G T , i T − 1 + β c 2 L 2 T 4 ( 2 − 1 N ) + 4 c L 2 ln ( e N ) n ; F_T\leq-\frac{\sum_{i=1}^{T-1}\mathcal{G}_{T,i}}{T-1}+\frac{\beta c^2L^2T}{4}\left(2-\frac{1}{N}\right)+\frac{4cL^2\ln(eN)}{n}; F T ≤ − T − 1 ∑ i = 1 T − 1 G T , i + 4 β c 2 L 2 T ( 2 − N 1 ) + n 4 c L 2 ln ( e N ) ; (c) under continuously decaying learning rates η τ , t = c ( τ − 1 ) N + t + 1 \eta_{\tau,t}=\frac{c}{(\tau-1)N+t+1} η τ , t = ( τ − 1 ) N + t + 1 c
F T ≤ − ∑ i = 1 T − 1 G T , i T − 1 + β c 2 L 2 2 N ( T − 1 ) ( ln ( T − 1 ) + 1 T ) + 4 c L 2 n ( T − 1 ) ln ( e N ( T − 1 ) ) . F_T\leq-\frac{\sum_{i=1}^{T-1}\mathcal{G}_{T,i}}{T-1}+\frac{\beta c^2L^2}{2N(T-1)}\left(\ln(T-1)+\frac{1}{T}\right)
+\frac{4cL^2}{n(T-1)}\ln\left(eN(T-1)\right). F T ≤ − T − 1 ∑ i = 1 T − 1 G T , i + 2 N ( T − 1 ) β c 2 L 2 ( ln ( T − 1 ) + T 1 ) + n ( T − 1 ) 4 c L 2 ln ( e N ( T − 1 ) ) . Theorem 9. Assume that the loss function f ( ⋅ ; z ) ∈ [ 0 , 1 ] f(\cdot;z)\in[0,1] f ( ⋅ ; z ) ∈ [ 0 , 1 ] n ≥ 2 n\geq2 n ≥ 2 c , β , L > 0 c,\beta,L>0 c , β , L > 0 N N N τ ∈ [ T ] \tau\in[T] τ ∈ [ T ] η τ , t \eta_{\tau,t} η τ , t
(a) under intra-task decaying learning rates η τ , t = c t + 1 \eta_{\tau,t}=\frac{c}{t+1} η τ , t = t + 1 c 2 c L 2 ( e N ) c β ( T − 1 ) < N 2cL^2(eN)^{c\beta(T-1)}<N 2 c L 2 ( e N ) c β ( T − 1 ) < N
F T ≤ − ∑ i = 1 T − 1 G T , i T − 1 + β c 2 L 2 T 4 ( 2 − 1 N ) + K N [ 1 + ( e N ) c β ( T − 1 ) c β + 1 − 1 ( T − 1 ) ( 1 − ( e N ) − c β c β + 1 ) ] − 2 L 2 β n [ 1 + ( e N ) c β ( T − 1 ) − 1 ( T − 1 ) ( 1 − ( e N ) − c β ) ] . (9) F_T\leq-\frac{\sum_{i=1}^{T-1}\mathcal{G}_{T,i}}{T-1}+\frac{\beta c^2L^2T}{4}\left(2-\frac{1}{N}\right)
+\mathcal{K}_N\left[1+\frac{(eN)^{\frac{c\beta(T-1)}{c\beta+1}}-1}{(T-1)\left(1-(eN)^{-\frac{c\beta}{c\beta+1}}\right)}\right]
-\frac{2L^2}{\beta n}\left[1+\frac{(eN)^{c\beta(T-1)}-1}{(T-1)\left(1-(eN)^{-c\beta}\right)}\right]. \tag*{(9)} F T ≤ − T − 1 ∑ i = 1 T − 1 G T , i + 4 β c 2 L 2 T ( 2 − N 1 ) + K N 1 + ( T − 1 ) ( 1 − ( e N ) − c β + 1 c β ) ( e N ) c β + 1 c β ( T − 1 ) − 1 − β n 2 L 2 [ 1 + ( T − 1 ) ( 1 − ( e N ) − c β ) ( e N ) c β ( T − 1 ) − 1 ] . (9) (b) under continuously decaying learning rates η τ , t = c ( τ − 1 ) N + t + 1 \eta_{\tau,t}=\frac{c}{(\tau-1)N+t+1} η τ , t = ( τ − 1 ) N + t + 1 c
F T ≤ − ∑ i = 1 T − 1 G T , i T − 1 + β c 2 L 2 2 N ( T − 1 ) ( ln ( T − 1 ) + 1 T ) + 2 L 2 β n ( T − 1 ) 2 c β − 1 ln 2 ln ( T − 1 ) + 1 T − 1 × { K N ( 1 + T c β c β + 1 ) − 2 L 2 n β [ 1 + ( T T − 1 ) c β ] , if C 3 1 , K N − 2 L 2 n β + ( T − 1 ) N n , if C 3 2 , K T N − 2 L 2 n β ( T T − 1 ) c β + N n , if C 3 3 , N T n , if C 3 4 . (10) \begin{aligned}
F_T \leq{}&-\frac{\sum_{i=1}^{T-1}\mathcal{G}_{T,i}}{T-1}+\frac{\beta c^2L^2}{2N(T-1)}\left(\ln(T-1)+\frac{1}{T}\right)\\
&+\frac{2L^2}{\beta n(T-1)}\frac{2^{c\beta}-1}{\ln2}\ln(T-1)+\frac{1}{T-1}\times
\begin{cases}
\mathcal{K}_N\left(1+T^{\frac{c\beta}{c\beta+1}}\right)-\frac{2L^2}{n\beta}\left[1+\left(\frac{T}{T-1}\right)^{c\beta}\right], & \text{if } \mathcal{C}_3^1,\\
\mathcal{K}_N-\frac{2L^2}{n\beta}+\frac{(T-1)N}{n}, & \text{if } \mathcal{C}_3^2,\\
\mathcal{K}_{TN}-\frac{2L^2}{n\beta}\left(\frac{T}{T-1}\right)^{c\beta}+\frac{N}{n}, & \text{if } \mathcal{C}_3^3,\\
\frac{NT}{n}, & \text{if } \mathcal{C}_3^4.
\end{cases} \tag*{(10)}
\end{aligned} F T ≤ − T − 1 ∑ i = 1 T − 1 G T , i + 2 N ( T − 1 ) β c 2 L 2 ( ln ( T − 1 ) + T 1 ) + β n ( T − 1 ) 2 L 2 ln 2 2 c β − 1 ln ( T − 1 ) + T − 1 1 × ⎩ ⎨ ⎧ K N ( 1 + T c β + 1 c β ) − n β 2 L 2 [ 1 + ( T − 1 T ) c β ] , K N − n β 2 L 2 + n ( T − 1 ) N , K T N − n β 2 L 2 ( T − 1 T ) c β + n N , n N T , if C 3 1 , if C 3 2 , if C 3 3 , if C 3 4 . (10) where
C 3 1 : 2 c L 2 < N , 2 c L 2 T c β < N ( T − 1 ) c β + 1 , C 3 2 : 2 c L 2 < N , 2 c L 2 T c β ≥ N ( T − 1 ) c β + 1 , C 3 3 : 2 c L 2 > N , 2 c L 2 T c β < N ( T − 1 ) c β + 1 , C 3 4 : 2 c L 2 ≥ N , 2 c L 2 T c β ≥ N ( T − 1 ) c β + 1 . \begin{aligned}
\mathcal{C}_3^1 &: 2cL^2<N,\quad2cL^2T^{c\beta}<N(T-1)^{c\beta+1},\\
\mathcal{C}_3^2 &: 2cL^2<N,\quad2cL^2T^{c\beta}\geq N(T-1)^{c\beta+1},\\
\mathcal{C}_3^3 &: 2cL^2>N,\quad2cL^2T^{c\beta}<N(T-1)^{c\beta+1},\\
\mathcal{C}_3^4 &: 2cL^2\geq N,\quad2cL^2T^{c\beta}\geq N(T-1)^{c\beta+1}.
\end{aligned} C 3 1 C 3 2 C 3 3 C 3 4 : 2 c L 2 < N , 2 c L 2 T c β < N ( T − 1 ) c β + 1 , : 2 c L 2 < N , 2 c L 2 T c β ≥ N ( T − 1 ) c β + 1 , : 2 c L 2 > N , 2 c L 2 T c β < N ( T − 1 ) c β + 1 , : 2 c L 2 ≥ N , 2 c L 2 T c β ≥ N ( T − 1 ) c β + 1 . The proofs of Theorems 8 and 9 are given in Appendix E. To obtain explicit bounds on F T F_T F T (8) , the upper bound on forgetting can be reduced by controlling ϵ T , i \epsilon_{T,i} ϵ T , i ϵ i , i \epsilon_{i,i} ϵ i , i ϵ ~ T , i \tilde{\epsilon}_{T,i} ϵ ~ T , i i ∈ [ T − 1 ] i\in[T-1] i ∈ [ T − 1 ] F T F_T F T § 4 -A–IV-C. We summarize the implications of the bounds as follows:
Using decaying learning rates or increasing the number of training samples per task n n n
Smaller initial learning rates c c c N N N
Positive cumulative alignment between the gradients of previous and subsequent tasks contributes to reducing the EF upper bound through the term − G T , i -\mathcal{G}_{T,i} − G T , i
Experiment
In this section, we present experiments on Split CIFAR-100 to examine the empirical implications of our theoretical analysis. We also conduct experiments on Split MiniImageNet, with the results reported in Appendix F.
Experimental Setup
Experimental setting on Split CIFAR-100. We conduct experiments on the widely used CL benchmark Split CIFAR-100 [13 ] . This benchmark partitions the 100 classes of CIFAR-100 [41 ] into 10 disjoint tasks, with 10 classes per task. We use AlexNet as the backbone, following the setting of Serra et al. [42 ] . We train the model with SGD to match our theoretical setting. To verify our theoretical findings, we vary the number of epochs per task in { 10 , 25 , 50 , 75 , 100 } \{10,25,50,75,100\} { 10 , 25 , 50 , 75 , 100 } { 10 − 3 , 5 × 10 − 3 , 10 − 2 , 5 × 10 − 2 , 10 − 1 } \{10^{-3},5\times10^{-3},10^{-2},5\times10^{-2},10^{-1}\} { 1 0 − 3 , 5 × 1 0 − 3 , 1 0 − 2 , 5 × 1 0 − 2 , 1 0 − 1 } { 500 , 1500 , 2500 , 3500 , 4500 } \{500,1500,2500,3500,4500\} { 500 , 1500 , 2500 , 3500 , 4500 }
The number of epochs per task affects the metrics. We fix c = 0.1 c=0.1 c = 0.1 c = 0.1 c=0.1 c = 0.1 N = 3550 N=3550 N = 3550
Observable metric. The definition in Equation (4) relies on the population risk, which is not directly observable. Therefore, we define an observable metric by replacing the population risk in the theoretical metric with the test loss. Specifically, let R t , i R_{t,i} R t , i R ~ t , i \widetilde{R}_{t,i} R t , i i i i t t t
IGG = 1 T − 1 ∑ i = 1 T − 1 ∣ R i , i − R ~ i , i ∣ , \operatorname{IGG}=\frac{1}{T-1}\sum_{i=1}^{T-1}\left|R_{i,i}-\widetilde{R}_{i,i}\right|, IGG = T − 1 1 i = 1 ∑ T − 1 R i , i − R i , i , CGG = 1 T − 1 ∑ i = 1 T − 1 ∣ R ~ T , i − R T , i ∣ , \operatorname{CGG}=\frac{1}{T-1}\sum_{i=1}^{T-1}\left|\widetilde{R}_{T,i}-R_{T,i}\right|, CGG = T − 1 1 i = 1 ∑ T − 1 R T , i − R T , i , EF = 1 T − 1 ∑ i = 1 T − 1 ( R T , i − R i , i ) , \operatorname{EF}=\frac{1}{T-1}\sum_{i=1}^{T-1}\left(R_{T,i}-R_{i,i}\right), EF = T − 1 1 i = 1 ∑ T − 1 ( R T , i − R i , i ) , F T = 1 T − 1 ∑ i = 1 T − 1 ( R ~ T , i − R ~ i , i ) . F_T=\frac{1}{T-1}\sum_{i=1}^{T-1}\left(\widetilde{R}_{T,i}-\widetilde{R}_{i,i}\right). F T = T − 1 1 i = 1 ∑ T − 1 ( R T , i − R i , i ) . In addition to forgetting, we evaluate the model’s predictive performance using average accuracy (ACC). Let A t , i A_{t,i} A t , i i i i t t t T T T
ACC = 1 T ∑ i = 1 T A T , i . \operatorname{ACC}=\frac{1}{T}\sum_{i=1}^{T}A_{T,i}. ACC = T 1 i = 1 ∑ T A T , i . Compute resources. We conduct the experiments on an Intel Xeon Platinum 8160 @ 2.10 GHz system with an NVIDIA RTX A6000 GPU.
Experimental Result
Effects of the learning rate and the number of epochs per task. As shown in Figure 2 , the two decaying learning-rate schedules generally yield smaller generalization gaps and less forgetting than the constant schedule. In particular, continuous decay keeps forgetting close to zero across these settings. Moreover, the smallest initial learning rate and the fewest training epochs generally yield the least forgetting. To examine whether these observations extend to a more challenging benchmark and a different backbone, we also conduct experiments on Split MiniImageNet using ResNet-18. The results, reported in Appendix F, show similar overall trends.
Figure 2. IGG, CGG, EF, F T F_T F T The top row shows results for different initial learning rates c c c
Stability-plasticity dilemma. As shown in Figure 2 , training with a continuously decaying learning rate yields the lowest ACC among the three learning-rate schedules. Moreover, reducing the number of training epochs or the initial learning rate does not necessarily improve ACC, even when it reduces forgetting. These observations reflect the classical stability-plasticity dilemma in CL [43 , 44 , 45 ] , highlighting the difficulty of preserving past knowledge while learning new tasks.
Effect of the number of training samples per task. As shown in Figure 3 , both IGG and CGG decrease as the number of training samples per task increases, with the number of SGD updates per task held fixed. This trend is consistent with our theoretical bounds, which decrease with the sample size when the other parameters are fixed.
Figure 3. IGG and CGG with different numbers of training samples per task on Split CIFAR-100.
Effect of gradient alignment under different learning rate schedules. We compare original CL, GEM, and A-GEM on Split CIFAR-100 under three learning rate schedules. GEM
enforces nonnegative inner products between the projected gradient and the memory gradients of previous tasks, whereas A-GEM uses a single constraint based on an aggregate memory gradient. As shown in Figure 4 , GEM achieves the highest ACC and BWT under the constant and intra-task decaying schedules, with larger performance gaps under the constant schedule. Under the continuously decaying schedule, however, all three methods exhibit similarly low ACC despite achieving BWT values close to zero. This pattern is consistent with the stability-plasticity dilemma. Overall, these results suggest that the benefits of gradient alignment depend on the learning rate schedule, in line with our theoretical analysis in Section IV-C, which relates EF to both CGA and learning rates.
Figure 4. ACC and BWT for original CL, GEM, and A-GEM under different learning-rate schedules on Split CIFAR-100. Higher ACC indicates better predictive performance, while higher BWT indicates less forgetting.
Conclusion
In this work, we propose an algorithmic stability based theoretical framework for analyzing catastrophic forgetting under both convex and non-convex loss functions with three learning-rate schedules. Specifically, we derive a fine-grained decomposition of forgetting into IGG, CGG, and EF. We further propose intra-task and cross-task stability to analyze IGG and CGG, and analyze EF through the optimization dynamics. Our theoretical results characterize how local training lengths, initial learning rates, learning-rate schedules, and cumulative gradient alignment affect the forgetting bounds. Finally, we validate our theoretical findings through several empirical studies.
Limitation. The theoretical analysis is carried out under classical assumptions such as L L L β \beta β
Biographies
Guodong Zheng
Guodong Zheng is currently a postdoctoral researcher with Sun Yat-sen University, China. He received his Ph.D. degree from Huazhong University of Science and Technology, China. His work appeared in several top-tier ML conferences/journals, including ICML, ICLR, and Neural Networks. His current research interests include optimization, continual learning.
Yan Sun
Yan Sun is currently a Postdoctoral Researcher with Nanyang Technological University (NTU). He received the B.E. degree from the University of Science and Technology of China (USTC) and the Ph.D. degree from the University of Sydney. He has published 10+ first-author papers in leading machine learning venues, including NeurIPS, ICML, ICLR, and IEEE TPAMI. His research interests include machine learning, federated and distributed learning, optimization and generalization, and efficient training and adaptation of large-scale foundation models.
Peng Wang
Peng Wang is currently a postdoctoral researcher with Sun Yat-sen University, China. He received his Ph.D. degree from Huazhong University of Science and Technology, China. His work appeared in several top-tier ML conferences/journals, including ICML, ICLR, Neural Networks, and Pattern Recognition. His current research interests include the generalization and optimization theories of deep learning.
Enneng Yang
Enneng Yang is currently a postdoctoral researcher at Sun Yat-sen University, China. He received his Ph.D. degree from the Software College, Northeastern University, China. His work appeared in several top-tier ML & IR conferences/journals, including IEEE TPAMI, IEEE TKDE, JMLR, ICML, NeurIPS, ICLR, ICCV, ACL, WWW, SIGIR, and AAAI. His research interests include machine learning and recommendation systems.
Jiafei Lyu
Jiafei Lyu is currently a Senior Researcher at Tencent. He received the bachelor’s and Ph.D. degrees from Tsinghua University in 2020 and 2025, respectively. He has published papers in NeurIPS, ICML, ICLR, AAAI, and the Journal of Artificial Intelligence Research. His research interests include RLHF and efficient decision-making with deep Reinforcement Learning.
Xiaochun Cao
Xiaochun Cao (Senior Member, IEEE) received the B.E. and M.E. degrees in Computer Science from Beihang University, Beijing, China, in 1999 and 2002, and the Ph.D. degree from the University of Central Florida, USA, in 2006. He worked as a Research Scientist at ObjectVideo Inc. for three years. From 2008 to 2012, he was a Professor at Tianjin University, China. Before joining Sun Yat-sen University, Shenzhen, he was a Professor at the Institute of Information Engineering, Chinese Academy of Sciences. He is currently the Dean and Professor with the School of Cyber Science and Technology at Sun Yat-sen University, Shenzhen. He has published over 200 papers and received the Piero Zamperoni Best Student Paper Award at ICPR in 2004 and 2010. He serves on the Editorial Boards of IEEE TPAMI and IEEE TIP.
Dacheng Tao
Dacheng Tao (Fellow, IEEE) is currently a Distinguished University Professor with the College of Computing and Data Science, Nanyang Technological University. He mainly applies statistics and mathematics to artificial intelligence and data science. His research is detailed in one monograph and over 200 publications in prestigious journals and conferences, with best paper awards, best student paper awards, and test-of-time awards. His publications have been cited over 112K times. He has an H-index of more than 160 in Google Scholar. He is a Fellow of Australian Academy of Science, AAAS, and ACM. He received the 2015 and 2020 Australian Eureka Prize, the 2018 IEEE ICDM Research Contributions Award, and the 2021 IEEE Computer Society McCluskey Technical Achievement Award.
Li Shen
Li Shen is currently an associate professor at Sun Yat-sen University. Previously, he was a research scientist at JD Explore Academy, Beijing, and a senior researcher at Tencent AI Lab, Shenzhen. He received his bachelor’s degree and Ph.D. from the School of Mathematics, South China University of Technology. His research interests include efficient deep learning, efficient reinforcement learning, optimization and deep learning theory. He has served as the senior program committee for AAAI and IJCAI, area chairs for ICML, NeurIPS, ICLR, CVPR, and ACMMM. He is also the associate editor for IEEE Transactions on Pattern Analysis and Machine Intelligence, IEEE Transactions on Knowledge and Data Engineering, and IEEE Transactions on Multimedia.
Appendix A: Preliminaries on Algorithmic Stability
In this section, we introduce several preliminaries that will be used in the subsequent proofs. We adopt the notation of Hardt et al. [36 ] .
Definition 4. For a nonnegative step size α ≥ 0 \alpha\ge0 α ≥ 0 f : Ω → R f:\Omega\to\mathbb{R} f : Ω → R G f , α G_{f,\alpha} G f , α
G f , α ( w ) = w − α ∇ f ( w ) . G_{f,\alpha}(w) = w - \alpha\nabla f(w). G f , α ( w ) = w − α ∇ f ( w ) . Definition 5 (η \eta η An update rule is η \eta η
sup v , w ∈ Ω v ≠ w ∥ G ( v ) − G ( w ) ∥ ∥ v − w ∥ ≤ η (11) \sup_{\substack{v,w\in\Omega\\v\ne w}}\frac{\lVert G(v)-G(w)\rVert}{\lVert v-w\rVert}\le\eta \tag*{(11)} v , w ∈ Ω v = w sup ∥ v − w ∥ ∥ G ( v ) − G ( w )∥ ≤ η (11) Definition 6 (σ \sigma σ An update rule is σ \sigma σ
sup w ∈ Ω ∥ w − G ( w ) ∥ ≤ σ (12) \sup_{w\in\Omega}\lVert w-G(w)\rVert\le\sigma \tag*{(12)} w ∈ Ω sup ∥ w − G ( w )∥ ≤ σ (12) Lemma 1. Assume that f f f β \beta β
G f , α G_{f,\alpha} G f , α ( 1 + α β ) (1+\alpha\beta) ( 1 + α β )
Assume in addition that f f f α ≤ 2 / β \alpha\le2/\beta α ≤ 2/ β G f , α G_{f,\alpha} G f , α 1 1 1
Assume in addition that f f f γ \gamma γ α ≤ 2 β + γ \alpha\le\frac{2}{\beta+\gamma} α ≤ β + γ 2 G f , α G_{f,\alpha} G f , α ( 1 − 2 α β γ β + γ ) \left(1-\frac{2\alpha\beta\gamma}{\beta+\gamma}\right) ( 1 − β + γ 2 α β γ )
Appendix B: Intra-Task Generalization Gap
Proof of Theorem 1
Theorem. Assume that A \mathcal{A} A ϵ i , i \epsilon_{i,i} ϵ i , i
∣ E S 1 : i , A [ R D i ( A ( S 1 : i ) ) − R S i ( A ( S 1 : i ) ) ] ∣ ≤ ϵ i , i . (13) \left|\mathbb{E}_{S_{1:i},\mathcal{A}}\left[R_{D_i}\left(\mathcal{A}(S_{1:i})\right)-R_{S_i}\left(\mathcal{A}(S_{1:i})\right)\right]\right|\le\epsilon_{i,i}. \tag*{(13)} ∣ E S 1 : i , A [ R D i ( A ( S 1 : i ) ) − R S i ( A ( S 1 : i ) ) ] ∣ ≤ ϵ i , i . (13) Proof. We first introduce the following notation. Let S 1 : i S_{1:i} S 1 : i S 1 : i ′ S'_{1:i} S 1 : i ′ S 1 : i ( i , k ) S_{1:i}^{(i,k)} S 1 : i ( i , k ) S 1 : i S_{1:i} S 1 : i k k k z i , k z_{i,k} z i , k S i S_i S i i i i z i , k ′ z'_{i,k} z i , k ′
S 1 : i = ( z 1 , 1 , … , z 1 , n , … , z i , 1 , … , z i , n ) , S_{1:i}=(z_{1,1},\ldots,z_{1,n},\ldots,z_{i,1},\ldots,z_{i,n}), S 1 : i = ( z 1 , 1 , … , z 1 , n , … , z i , 1 , … , z i , n ) , S 1 : i ′ = ( z 1 , 1 ′ , … , z 1 , n ′ , … , z i , 1 ′ , … , z i , n ′ ) , S'_{1:i}=(z'_{1,1},\ldots,z'_{1,n},\ldots,z'_{i,1},\ldots,z'_{i,n}), S 1 : i ′ = ( z 1 , 1 ′ , … , z 1 , n ′ , … , z i , 1 ′ , … , z i , n ′ ) , S 1 : i ( i , k ) = ( z 1 , 1 , … , z 1 , n , … , z i , 1 , … , z i , k − 1 , z i , k ′ , z i , k + 1 , … , z i , n ) . (14) S_{1:i}^{(i,k)}=(z_{1,1},\ldots,z_{1,n},\ldots,z_{i,1},\ldots,z_{i,k-1},z'_{i,k},z_{i,k+1},\ldots,z_{i,n}). \tag*{(14)} S 1 : i ( i , k ) = ( z 1 , 1 , … , z 1 , n , … , z i , 1 , … , z i , k − 1 , z i , k ′ , z i , k + 1 , … , z i , n ) . (14) With these notations, we have
E S 1 : i E A [ R S i ( A ( S 1 : i ) ) ] = E S 1 : i E A [ 1 n ∑ k = 1 n f ( A ( S 1 : i ) ; z i , k ) ] = E S 1 : i E S 1 : i ′ E A [ 1 n ∑ k = 1 n f ( A ( S 1 : i ( i , k ) ) ; z i , k ′ ) ] = E S 1 : i E S 1 : i ′ E A [ 1 n ∑ k = 1 n f ( A ( S 1 : i ) ; z i , k ′ ) ] + δ = E S 1 : i E A [ R D i ( A ( S 1 : i ) ) ] + δ . \begin{aligned}
\mathbb{E}_{S_{1:i}}\mathbb{E}_{\mathcal{A}}[R_{S_i}(\mathcal{A}(S_{1:i}))]
&=\mathbb{E}_{S_{1:i}}\mathbb{E}_{\mathcal{A}}\left[\frac{1}{n}\sum_{k=1}^{n}f(\mathcal{A}(S_{1:i});z_{i,k})\right]\\
&=\mathbb{E}_{S_{1:i}}\mathbb{E}_{S'_{1:i}}\mathbb{E}_{\mathcal{A}}\left[\frac{1}{n}\sum_{k=1}^{n}f(\mathcal{A}(S_{1:i}^{(i,k)});z'_{i,k})\right]\\
&=\mathbb{E}_{S_{1:i}}\mathbb{E}_{S'_{1:i}}\mathbb{E}_{\mathcal{A}}\left[\frac{1}{n}\sum_{k=1}^{n}f(\mathcal{A}(S_{1:i});z'_{i,k})\right]+\delta\\
&=\mathbb{E}_{S_{1:i}}\mathbb{E}_{\mathcal{A}}[R_{D_i}(\mathcal{A}(S_{1:i}))]+\delta.
\end{aligned} E S 1 : i E A [ R S i ( A ( S 1 : i ))] = E S 1 : i E A [ n 1 k = 1 ∑ n f ( A ( S 1 : i ) ; z i , k ) ] = E S 1 : i E S 1 : i ′ E A [ n 1 k = 1 ∑ n f ( A ( S 1 : i ( i , k ) ) ; z i , k ′ ) ] = E S 1 : i E S 1 : i ′ E A [ n 1 k = 1 ∑ n f ( A ( S 1 : i ) ; z i , k ′ ) ] + δ = E S 1 : i E A [ R D i ( A ( S 1 : i ))] + δ . where
δ = E S 1 : i E S 1 : i ′ E A [ 1 n ∑ k = 1 n f ( A ( S 1 : i ( i , k ) ) ; z i , k ′ ) − 1 n ∑ k = 1 n f ( A ( S 1 : i ) ; z i , k ′ ) ] . \delta=\mathbb{E}_{S_{1:i}}\mathbb{E}_{S'_{1:i}}\mathbb{E}_{\mathcal{A}}\left[\frac{1}{n}\sum_{k=1}^{n}f(\mathcal{A}(S_{1:i}^{(i,k)});z'_{i,k})-\frac{1}{n}\sum_{k=1}^{n}f(\mathcal{A}(S_{1:i});z'_{i,k})\right]. δ = E S 1 : i E S 1 : i ′ E A [ n 1 k = 1 ∑ n f ( A ( S 1 : i ( i , k ) ) ; z i , k ′ ) − n 1 k = 1 ∑ n f ( A ( S 1 : i ) ; z i , k ′ ) ] . Under the assumption that A \mathcal{A} A ϵ i , i \epsilon_{i,i} ϵ i , i
∣ δ ∣ ≤ ϵ i , i . |\delta|\le\epsilon_{i,i}. ∣ δ ∣ ≤ ϵ i , i . Therefore,
∣ E S 1 : i , A [ R D i ( A ( S 1 : i ) ) − R S i ( A ( S 1 : i ) ) ] ∣ = ∣ δ ∣ ≤ ϵ i , i . \left|\mathbb{E}_{S_{1:i},\mathcal{A}}\left[R_{D_i}\left(\mathcal{A}(S_{1:i})\right)-R_{S_i}\left(\mathcal{A}(S_{1:i})\right)\right]\right|=|\delta|\le\epsilon_{i,i}. ∣ E S 1 : i , A [ R D i ( A ( S 1 : i ) ) − R S i ( A ( S 1 : i ) ) ] ∣ = ∣ δ ∣ ≤ ϵ i , i . Proof of Theorem 2
Theorem. Assume that the loss function f ( ⋅ ; z ) f(\cdot;z) f ( ⋅ ; z ) N N N τ ∈ [ i ] \tau\in[i] τ ∈ [ i ] η τ , t ≤ 2 β \eta_{\tau,t}\le\frac{2}{\beta} η τ , t ≤ β 2
ϵ i , i ≤ 2 L 2 n ∑ t = 0 N − 1 η i , t . \epsilon_{i,i}\le\frac{2L^2}{n}\sum_{t=0}^{N-1}\eta_{i,t}. ϵ i , i ≤ n 2 L 2 t = 0 ∑ N − 1 η i , t . Proof. Let S 1 : i S_{1:i} S 1 : i S 1 : i ′ S'_{1:i} S 1 : i ′ i i i i i i G 1 , 0 , … , G 1 , N − 1 , … , G i , 0 , … , G i , N − 1 G_{1,0},\ldots,G_{1,N-1},\ldots,G_{i,0},\ldots,G_{i,N-1} G 1 , 0 , … , G 1 , N − 1 , … , G i , 0 , … , G i , N − 1 G 1 , 0 ′ , … , G 1 , N − 1 ′ , … , G i , 0 ′ , … , G i , N − 1 ′ G'_{1,0},\ldots,G'_{1,N-1},\ldots,G'_{i,0},\ldots,G'_{i,N-1} G 1 , 0 ′ , … , G 1 , N − 1 ′ , … , G i , 0 ′ , … , G i , N − 1 ′ S 1 : i S_{1:i} S 1 : i S 1 : i ′ S'_{1:i} S 1 : i ′
Fix an arbitrary example z ∈ Z z\in\mathcal{Z} z ∈ Z L L L f ( ⋅ ; z ) f(\cdot;z) f ( ⋅ ; z )
E ∣ f ( w i , N ; z ) − f ( w i , N ′ ; z ) ∣ ≤ L E [ δ i , N ] , (15) \mathbb{E}\left|f(w_{i,N};z)-f(w'_{i,N};z)\right|\le L\mathbb{E}[\delta_{i,N}], \tag*{(15)} E f ( w i , N ; z ) − f ( w i , N ′ ; z ) ≤ L E [ δ i , N ] , (15) where δ i , N = ∥ w i , N − w i , N ′ ∥ \delta_{i,N}=\lVert w_{i,N}-w'_{i,N}\rVert δ i , N = ∥ w i , N − w i , N ′ ∥
During the t t t i i i 1 − 1 n 1-\frac{1}{n} 1 − n 1 S i S_i S i S i ′ S'_i S i ′ G i , t = G i , t ′ G_{i,t}=G'_{i,t} G i , t = G i , t ′ 1 1 1 G i , t G_{i,t} G i , t f f f 1 n \frac{1}{n} n 1 G i , t G_{i,t} G i , t G i , t ′ G'_{i,t} G i , t ′ η i , t L \eta_{i,t}L η i , t L
Combining these two cases yields
E [ δ i , t + 1 ] ≤ ( 1 − 1 n ) E [ δ i , t ] + 1 n E [ δ i , t ] + 2 η i , t L n = E [ δ i , t ] + 2 η i , t L n . \begin{aligned}
\mathbb{E}[\delta_{i,t+1}]
&\le\left(1-\frac{1}{n}\right)\mathbb{E}[\delta_{i,t}]+\frac{1}{n}\mathbb{E}[\delta_{i,t}]+\frac{2\eta_{i,t}L}{n}\\
&=\mathbb{E}[\delta_{i,t}]+\frac{2\eta_{i,t}L}{n}.
\end{aligned} E [ δ i , t + 1 ] ≤ ( 1 − n 1 ) E [ δ i , t ] + n 1 E [ δ i , t ] + n 2 η i , t L = E [ δ i , t ] + n 2 η i , t L . Unrolling this recursion over the N N N i i i
E [ δ i , N ] ≤ E [ δ i , 0 ] + ∑ t = 0 N − 1 2 η i , t L n . (16) \mathbb{E}[\delta_{i,N}]\le\mathbb{E}[\delta_{i,0}]+\sum_{t=0}^{N-1}\frac{2\eta_{i,t}L}{n}. \tag*{(16)} E [ δ i , N ] ≤ E [ δ i , 0 ] + t = 0 ∑ N − 1 n 2 η i , t L . (16) Under the CL protocol, the initialization of task i i i i − 1 i-1 i − 1 w i , 0 = w i − 1 , N w_{i,0}=w_{i-1,N} w i , 0 = w i − 1 , N w i , 0 ′ = w i − 1 , N ′ w'_{i,0}=w'_{i-1,N} w i , 0 ′ = w i − 1 , N ′
δ i , 0 = ∥ w i , 0 − w i , 0 ′ ∥ = ∥ w i − 1 , N − w i − 1 , N ′ ∥ = δ i − 1 , N . \delta_{i,0}=\lVert w_{i,0}-w'_{i,0}\rVert=\lVert w_{i-1,N}-w'_{i-1,N}\rVert=\delta_{i-1,N}. δ i , 0 = ∥ w i , 0 − w i , 0 ′ ∥ = ∥ w i − 1 , N − w i − 1 , N ′ ∥ = δ i − 1 , N . Since the perturbation occurs only in task i i i S 1 : i − 1 S_{1:i-1} S 1 : i − 1 S 1 : i − 1 ′ S'_{1:i-1} S 1 : i − 1 ′ w i − 1 , N = w i − 1 , N ′ w_{i-1,N}=w'_{i-1,N} w i − 1 , N = w i − 1 , N ′ δ i − 1 , N = 0 \delta_{i-1,N}=0 δ i − 1 , N = 0
E [ δ i , 0 ] = 0. \mathbb{E}[\delta_{i,0}]=0. E [ δ i , 0 ] = 0. Substituting this into (16) gives
E [ δ i , N ] ≤ 2 L n ∑ t = 0 N − 1 η i , t . \mathbb{E}[\delta_{i,N}]\leq\frac{2L}{n}\sum_{t=0}^{N-1}\eta_{i,t}. E [ δ i , N ] ≤ n 2 L t = 0 ∑ N − 1 η i , t . Finally, plugging this bound into (15) , we obtain
E [ ∣ f ( w i , N ; z ) − f ( w i , N ′ ; z ) ∣ ] ≤ 2 L 2 n ∑ t = 0 N − 1 η i , t . \mathbb{E}\left[|f(w_{i,N};z)-f(w'_{i,N};z)|\right]\leq\frac{2L^2}{n}\sum_{t=0}^{N-1}\eta_{i,t}. E [ ∣ f ( w i , N ; z ) − f ( w i , N ′ ; z ) ∣ ] ≤ n 2 L 2 t = 0 ∑ N − 1 η i , t . This proves the theorem.
Proof of Theorem 3
Lemma 2. Assume that n ≥ 2 n\geq2 n ≥ 2 f ( ⋅ ; z ) f(\cdot;z) f ( ⋅ ; z ) L L L z z z S 1 : i S_{1:i} S 1 : i S 1 : i ′ S'_{1:i} S 1 : i ′ i i i i i i z ∈ Z z\in\mathcal{Z} z ∈ Z t 0 ∈ { 0 , 1 , … , N } t_0\in\{0,1,\ldots,N\} t 0 ∈ { 0 , 1 , … , N }
E [ ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ] ≤ t 0 n sup w , z f ( w ; z ) + L E [ ∥ w i − w i ′ ∥ ∣ δ i , t 0 = 0 ] . \mathbb{E}\left[|f(w_i;z)-f(w'_i;z)|\right]\leq\frac{t_0}{n}\sup_{w,z}f(w;z)+L\mathbb{E}\left[\|w_i-w'_i\|\mid\delta_{i,t_0}=0\right]. E [ ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ] ≤ n t 0 w , z sup f ( w ; z ) + L E [ ∥ w i − w i ′ ∥ ∣ δ i , t 0 = 0 ] . The same inequality holds under the random permutation rule when t 0 < n t_0<n t 0 < n
Proof. Let S 1 : i S_{1:i} S 1 : i S 1 : i ′ S'_{1:i} S 1 : i ′ i i i i i i G 1 , 0 , … , G 1 , N − 1 , … , G i , 0 , … , G i , N − 1 G_{1,0},\ldots,G_{1,N-1},\ldots,G_{i,0},\ldots,G_{i,N-1} G 1 , 0 , … , G 1 , N − 1 , … , G i , 0 , … , G i , N − 1 G 1 , 0 ′ , … , G 1 , N − 1 ′ , … , G i , 0 ′ , … , G i , N − 1 ′ G'_{1,0},\ldots,G'_{1,N-1},\ldots,G'_{i,0},\ldots,G'_{i,N-1} G 1 , 0 ′ , … , G 1 , N − 1 ′ , … , G i , 0 ′ , … , G i , N − 1 ′ S 1 : i S_{1:i} S 1 : i S 1 : i ′ S'_{1:i} S 1 : i ′
Let E \mathcal{E} E δ i , t 0 = 0 \delta_{i,t_0}=0 δ i , t 0 = 0
E [ ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ] = P ( E ) E [ ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ∣ E ] + P ( E c ) E [ ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ∣ E c ] ≤ E [ ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ∣ E ] + P ( E c ) sup w , z f ( w ; z ) ≤ L E [ ∥ w i − w i ′ ∥ ∣ E ] + P ( E c ) sup w , z f ( w ; z ) . \begin{aligned}
\mathbb{E}\left[|f(w_i;z)-f(w'_i;z)|\right]
&=\mathbb{P}(\mathcal{E})\mathbb{E}\left[|f(w_i;z)-f(w'_i;z)|\mid\mathcal{E}\right]\\
&\quad+\mathbb{P}(\mathcal{E}^{c})\mathbb{E}\left[|f(w_i;z)-f(w'_i;z)|\mid\mathcal{E}^{c}\right]\\
&\leq\mathbb{E}\left[|f(w_i;z)-f(w'_i;z)|\mid\mathcal{E}\right]+\mathbb{P}(\mathcal{E}^{c})\sup_{w,z}f(w;z)\\
&\leq L\mathbb{E}\left[\|w_i-w'_i\|\mid\mathcal{E}\right]+\mathbb{P}(\mathcal{E}^{c})\sup_{w,z}f(w;z).
\end{aligned} E [ ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ] = P ( E ) E [ ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ∣ E ] + P ( E c ) E [ ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ∣ E c ] ≤ E [ ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ∣ E ] + P ( E c ) w , z sup f ( w ; z ) ≤ L E [ ∥ w i − w i ′ ∥ ∣ E ] + P ( E c ) w , z sup f ( w ; z ) . We now bound P ( E c ) \mathbb{P}(\mathcal{E}^{c}) P ( E c ) i ∗ i^* i ∗ S 1 : i S_{1:i} S 1 : i S 1 : i ′ S'_{1:i} S 1 : i ′ I I I z i ∗ z_{i^*} z i ∗ I > t 0 I>t_0 I > t 0 t 0 t_0 t 0 δ i , t 0 = 0 \delta_{i,t_0}=0 δ i , t 0 = 0
P ( E c ) = P ( δ i , t 0 ≠ 0 ) ≤ P ( I ≤ t 0 ) . \mathbb{P}(\mathcal{E}^{c})=\mathbb{P}(\delta_{i,t_0}\ne0)\leq\mathbb{P}(I\leq t_0). P ( E c ) = P ( δ i , t 0 = 0 ) ≤ P ( I ≤ t 0 ) . Under the random permutation rule, I I I { 1 , … , n } \{1,\ldots,n\} { 1 , … , n } t 0 < n t_0<n t 0 < n
P ( I ≤ t 0 ) = t 0 n . \mathbb{P}(I\leq t_0)=\frac{t_0}{n}. P ( I ≤ t 0 ) = n t 0 . Under the random selection rule, let A t A_t A t z i ∗ z_{i^*} z i ∗ t t t
P ( I ≤ t 0 ) ≤ P ( ⋃ t = 1 t 0 A t ) ≤ ∑ t = 1 t 0 P ( A t ) = t 0 n . \mathbb{P}(I\leq t_0)\leq\mathbb{P}\left(\bigcup_{t=1}^{t_0}A_t\right)\leq\sum_{t=1}^{t_0}\mathbb{P}(A_t)=\frac{t_0}{n}. P ( I ≤ t 0 ) ≤ P ( t = 1 ⋃ t 0 A t ) ≤ t = 1 ∑ t 0 P ( A t ) = n t 0 . This proves the claim.
Theorem. Assume that the loss function f ( ⋅ ; z ) ∈ [ 0 , 1 ] f(\cdot;z)\in[0,1] f ( ⋅ ; z ) ∈ [ 0 , 1 ] n ≥ 2 n\geq2 n ≥ 2 c , β > 0 c,\beta>0 c , β > 0 N N N τ ∈ [ i ] \tau\in[i] τ ∈ [ i ] η τ , t \eta_{\tau,t} η τ , t
(a) under intra-task decaying learning rates η τ , t = c t + 1 \eta_{\tau,t}=\frac{c}{t+1} η τ , t = t + 1 c
ϵ i , i ≤ { K N − 2 L 2 β n , if 2 c L 2 < N , N n , if 2 c L 2 ≥ N . \epsilon_{i,i}\leq
\begin{cases}
\mathcal{K}_N-\frac{2L^2}{\beta n}, & \text{if }2cL^2<N,\\
\frac{N}{n}, & \text{if }2cL^2\geq N.
\end{cases} ϵ i , i ≤ { K N − β n 2 L 2 , n N , if 2 c L 2 < N , if 2 c L 2 ≥ N . (b) under continuously decaying learning rates η τ , t = c ( τ − 1 ) N + t + 1 \eta_{\tau,t}=\frac{c}{(\tau-1)N+t+1} η τ , t = ( τ − 1 ) N + t + 1 c i > 1 i>1 i > 1
ϵ i , i ≤ { 2 L 2 β n [ ( i i − 1 ) c β − 1 ] , if 2 c L 2 ≤ C 1 C D , K i N − ( i − 1 ) N n − 2 L 2 β n , if C 1 C D < 2 c L 2 < i N , N n , if 2 c L 2 ≥ i N , \epsilon_{i,i}\leq
\begin{cases}
\frac{2L^2}{\beta n}\left[\left(\frac{i}{i-1}\right)^{c\beta}-1\right], & \text{if }2cL^2\leq C_1^{\mathrm{CD}},\\
\mathcal{K}_{iN}-\frac{(i-1)N}{n}-\frac{2L^2}{\beta n}, & \text{if }C_1^{\mathrm{CD}}<2cL^2<iN,\\
\frac{N}{n}, & \text{if }2cL^2\geq iN,
\end{cases} ϵ i , i ≤ ⎩ ⎨ ⎧ β n 2 L 2 [ ( i − 1 i ) c β − 1 ] , K i N − n ( i − 1 ) N − β n 2 L 2 , n N , if 2 c L 2 ≤ C 1 CD , if C 1 CD < 2 c L 2 < i N , if 2 c L 2 ≥ i N , where
C 1 C D = ( i − 1 ) N ( i − 1 i ) c β . C_1^{\mathrm{CD}}=(i-1)N\left(\frac{i-1}{i}\right)^{c\beta}. C 1 CD = ( i − 1 ) N ( i i − 1 ) c β . Proof. Let S 1 : i S_{1:i} S 1 : i S 1 : i ′ S'_{1:i} S 1 : i ′ i i i i i i G 1 , 0 , … , G 1 , N − 1 , … , G i , 0 , … , G i , N − 1 G_{1,0},\ldots,G_{1,N-1},\ldots,G_{i,0},\ldots,G_{i,N-1} G 1 , 0 , … , G 1 , N − 1 , … , G i , 0 , … , G i , N − 1 G 1 , 0 ′ , … , G 1 , N − 1 ′ , … , G i , 0 ′ , … , G i , N − 1 ′ G'_{1,0},\ldots,G'_{1,N-1},\ldots,G'_{i,0},\ldots,G'_{i,N-1} G 1 , 0 ′ , … , G 1 , N − 1 ′ , … , G i , 0 ′ , … , G i , N − 1 ′ S 1 : i S_{1:i} S 1 : i S 1 : i ′ S'_{1:i} S 1 : i ′
Based on Lemma 2, we have for every integer t 0 ∈ { 0 , … , N } t_0\in\{0,\ldots,N\} t 0 ∈ { 0 , … , N }
E [ ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ] ≤ t 0 n + L E [ ∥ w i − w i ′ ∥ ∣ δ i , t 0 = 0 ] . \mathbb{E}\left[|f(w_i;z)-f(w'_i;z)|\right]\leq\frac{t_0}{n}+L\mathbb{E}\left[\|w_i-w'_i\|\mid\delta_{i,t_0}=0\right]. E [ ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ] ≤ n t 0 + L E [ ∥ w i − w i ′ ∥ ∣ δ i , t 0 = 0 ] . We let Δ i , t = E [ δ i , t ∣ δ i , t 0 = 0 ] \Delta_{i,t}=\mathbb{E}[\delta_{i,t}\mid\delta_{i,t_0}=0] Δ i , t = E [ δ i , t ∣ δ i , t 0 = 0 ] L = 0 L=0 L = 0 L > 0 L>0 L > 0
Integer cutoffs are handled by the following comparison for any nonnegative, nonincreasing function D D D ( 0 , N ] (0,N] ( 0 , N ]
min m ∈ { 0 , … , N } { m + ∑ t = m + 1 N D ( t ) } = ∑ t = 1 N min { 1 , D ( t ) } ≤ ∫ 0 N min { 1 , D ( u ) } d u . (17) \min_{m\in\{0,\ldots,N\}}\left\{m+\sum_{t=m+1}^{N}D(t)\right\}
=\sum_{t=1}^{N}\min\{1,D(t)\}
\leq\int_{0}^{N}\min\{1,D(u)\}\,du. \tag*{(17)} m ∈ { 0 , … , N } min { m + t = m + 1 ∑ N D ( t ) } = t = 1 ∑ N min { 1 , D ( t )} ≤ ∫ 0 N min { 1 , D ( u )} d u . (17) Choose m m m D ( t ) ≥ 1 D(t)\geq1 D ( t ) ≥ 1 η τ , t = c t + 1 \eta_{\tau,t}=\frac{c}{t+1} η τ , t = t + 1 c t t t η i , t − 1 = c / t \eta_{i,t-1}=c/t η i , t − 1 = c / t t = t 0 + 1 , … , N t=t_0+1,\ldots,N t = t 0 + 1 , … , N
Δ i , t ≤ ( 1 − 1 n ) ( 1 + η i , t − 1 β ) Δ i , t − 1 + 1 n Δ i , t − 1 + 2 η i , t − 1 L n = ( 1 n + ( 1 − 1 n ) ( 1 + c β t ) ) Δ i , t − 1 + 2 c L t n = ( 1 + ( 1 − 1 n ) c β t ) Δ i , t − 1 + 2 c L t n ≤ exp ( ( 1 − 1 n ) c β t ) Δ i , t − 1 + 2 c L t n . \begin{aligned}
\Delta_{i,t}\leq\left(1-\frac{1}{n}\right)(1+\eta_{i,t-1}\beta)\Delta_{i,t-1}+\frac{1}{n}\Delta_{i,t-1}+\frac{2\eta_{i,t-1}L}{n} \\
&=\left(\frac{1}{n}+\left(1-\frac{1}{n}\right)\left(1+\frac{c\beta}{t}\right)\right)\Delta_{i,t-1}+\frac{2cL}{tn} \\
&=\left(1+\left(1-\frac{1}{n}\right)\frac{c\beta}{t}\right)\Delta_{i,t-1}+\frac{2cL}{tn} \\
&\leq\exp\left(\left(1-\frac{1}{n}\right)\frac{c\beta}{t}\right)\Delta_{i,t-1}+\frac{2cL}{tn}.
\end{aligned} Δ i , t ≤ ( 1 − n 1 ) ( 1 + η i , t − 1 β ) Δ i , t − 1 + n 1 Δ i , t − 1 + n 2 η i , t − 1 L = ( n 1 + ( 1 − n 1 ) ( 1 + t c β ) ) Δ i , t − 1 + t n 2 c L = ( 1 + ( 1 − n 1 ) t c β ) Δ i , t − 1 + t n 2 c L ≤ exp ( ( 1 − n 1 ) t c β ) Δ i , t − 1 + t n 2 c L . Unrolling this recursion from t 0 t_0 t 0 N N N t 0 ≥ 1 t_0\geq1 t 0 ≥ 1
Δ i , N ≤ ∑ t = t 0 + 1 N { ∏ k = t + 1 N exp ( ( 1 − 1 n ) c β k ) } 2 c L t n = ∑ t = t 0 + 1 N { exp ( ( 1 − 1 n ) c β ∑ k = t + 1 N 1 k ) } 2 c L t n ≤ ∑ t = t 0 + 1 N { exp ( ( 1 − 1 n ) c β ln ( N t ) ) } 2 c L t n = 2 c L n N ( 1 − 1 n ) c β ∑ t = t 0 + 1 N t − ( 1 − 1 n ) c β − 1 ≤ 2 c L n N c β ∑ t = t 0 + 1 N t − c β − 1 ≤ 2 c L n N c β ∫ t 0 N u − c β − 1 d u = 2 L β n [ ( N t 0 ) c β − 1 ] . (18) \begin{aligned}
\Delta_{i,N}\leq\sum_{t=t_0+1}^{N}\left\{\prod_{k=t+1}^{N}\exp\left(\left(1-\frac{1}{n}\right)\frac{c\beta}{k}\right)\right\}\frac{2cL}{tn} \\
&=\sum_{t=t_0+1}^{N}\left\{\exp\left(\left(1-\frac{1}{n}\right)c\beta\sum_{k=t+1}^{N}\frac{1}{k}\right)\right\}\frac{2cL}{tn} \\
&\leq\sum_{t=t_0+1}^{N}\left\{\exp\left(\left(1-\frac{1}{n}\right)c\beta\ln\left(\frac{N}{t}\right)\right)\right\}\frac{2cL}{tn} \\
&=\frac{2cL}{n}N^{\left(1-\frac{1}{n}\right)c\beta}\sum_{t=t_0+1}^{N}t^{-\left(1-\frac{1}{n}\right)c\beta-1} \\
&\leq\frac{2cL}{n}N^{c\beta}\sum_{t=t_0+1}^{N}t^{-c\beta-1} \\
&\leq\frac{2cL}{n}N^{c\beta}\int_{t_0}^{N}u^{-c\beta-1}\,du \\
&=\frac{2L}{\beta n}\left[\left(\frac{N}{t_0}\right)^{c\beta}-1\right]. \tag*{(18)}
\end{aligned} Δ i , N ≤ t = t 0 + 1 ∑ N { k = t + 1 ∏ N exp ( ( 1 − n 1 ) k c β ) } t n 2 c L = t = t 0 + 1 ∑ N { exp ( ( 1 − n 1 ) c β k = t + 1 ∑ N k 1 ) } t n 2 c L ≤ t = t 0 + 1 ∑ N { exp ( ( 1 − n 1 ) c β ln ( t N ) ) } t n 2 c L = n 2 c L N ( 1 − n 1 ) c β t = t 0 + 1 ∑ N t − ( 1 − n 1 ) c β − 1 ≤ n 2 c L N c β t = t 0 + 1 ∑ N t − c β − 1 ≤ n 2 c L N c β ∫ t 0 N u − c β − 1 d u = β n 2 L [ ( t 0 N ) c β − 1 ] . (18) Here, the first inequality after the sum uses ( N / t ) ( 1 − 1 / n ) c β ≤ ( N / t ) c β (N/t)^{(1-1/n)c\beta}\leq(N/t)^{c\beta} ( N / t ) ( 1 − 1/ n ) c β ≤ ( N / t ) c β
E ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ≤ t 0 n + 2 L 2 β n [ ( N t 0 ) c β − 1 ] . \mathbb{E}\left|f(w_i;z)-f(w'_i;z)\right|\leq\frac{t_0}{n}+\frac{2L^2}{\beta n}\left[\left(\frac{N}{t_0}\right)^{c\beta}-1\right]. E ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ≤ n t 0 + β n 2 L 2 [ ( t 0 N ) c β − 1 ] . Differentiating the right-hand side with respect to the real variable t 0 t_0 t 0
t 0 ⋆ = ( 2 c L 2 ) 1 c β + 1 N c β c β + 1 . t_0^\star=(2cL^2)^{\frac{1}{c\beta+1}}N^{\frac{c\beta}{c\beta+1}}. t 0 ⋆ = ( 2 c L 2 ) c β + 1 1 N c β + 1 c β . Applying (17) to the unrolled sum, with D ( u ) = 2 c L 2 N c β u − c β − 1 D(u)=2cL^2N^{c\beta}u^{-c\beta-1} D ( u ) = 2 c L 2 N c β u − c β − 1
E ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ≤ 1 n ∫ 0 N min { 1 , 2 c L 2 N c β u − c β − 1 } d u . \mathbb{E}\left|f(w_i;z)-f(w'_i;z)\right|
\leq\frac{1}{n}\int_0^N\min\left\{1,2cL^2N^{c\beta}u^{-c\beta-1}\right\}\,du. E ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ≤ n 1 ∫ 0 N min { 1 , 2 c L 2 N c β u − c β − 1 } d u . When t 0 ⋆ < N t_0^\star<N t 0 ⋆ < N t 0 ⋆ t_0^\star t 0 ⋆
E ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ≤ t 0 ⋆ n + 2 c L 2 N c β n ∫ t 0 ⋆ N u − c β − 1 d u = c β + 1 n c β t 0 ⋆ − 2 L 2 β n . \begin{aligned}
\mathbb{E}\left|f(w_i;z)-f(w'_i;z)\right|
\leq\frac{t_0^\star}{n}+\frac{2cL^2N^{c\beta}}{n}\int_{t_0^\star}^{N}u^{-c\beta-1}\,du \\
&=\frac{c\beta+1}{nc\beta}t_0^\star-\frac{2L^2}{\beta n}.
\end{aligned} E ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ≤ n t 0 ⋆ + n 2 c L 2 N c β ∫ t 0 ⋆ N u − c β − 1 d u = n c β c β + 1 t 0 ⋆ − β n 2 L 2 . When t 0 ⋆ ≥ N t_0^\star\geq N t 0 ⋆ ≥ N ( 0 , N ) (0,N) ( 0 , N ) N / n N/n N / n t 0 ⋆ < N t_0^\star<N t 0 ⋆ < N 2 c L 2 < N 2cL^2<N 2 c L 2 < N t 0 ⋆ t_0^\star t 0 ⋆
(b) Under continuously decaying learning rates η τ , t = c ( τ − 1 ) N + t + 1 \eta_{\tau,t}=\frac{c}{(\tau-1)N+t+1} η τ , t = ( τ − 1 ) N + t + 1 c t t t η i , t − 1 = c / ( ( i − 1 ) N + t ) \eta_{i,t-1}=c/((i-1)N+t) η i , t − 1 = c / (( i − 1 ) N + t ) t = t 0 + 1 , … , N t=t_0+1,\ldots,N t = t 0 + 1 , … , N
Δ i , t ≤ ( 1 − 1 n ) ( 1 + η i , t − 1 β ) Δ i , t − 1 + 1 n Δ i , t − 1 + 2 η i , t − 1 L n = ( 1 n + ( 1 − 1 n ) ( 1 + c β ( i − 1 ) N + t ) ) Δ i , t − 1 + 2 c L ( ( i − 1 ) N + t ) n = ( 1 + ( 1 − 1 n ) c β ( i − 1 ) N + t ) Δ i , t − 1 + 2 c L ( ( i − 1 ) N + t ) n ≤ exp ( ( 1 − 1 n ) c β ( i − 1 ) N + t ) Δ i , t − 1 + 2 c L ( ( i − 1 ) N + t ) n . \begin{aligned}
\Delta_{i,t}\leq\left(1-\frac{1}{n}\right)(1+\eta_{i,t-1}\beta)\Delta_{i,t-1}+\frac{1}{n}\Delta_{i,t-1}+\frac{2\eta_{i,t-1}L}{n} \\
&=\left(\frac{1}{n}+\left(1-\frac{1}{n}\right)\left(1+\frac{c\beta}{(i-1)N+t}\right)\right)\Delta_{i,t-1}+\frac{2cL}{((i-1)N+t)n} \\
&=\left(1+\left(1-\frac{1}{n}\right)\frac{c\beta}{(i-1)N+t}\right)\Delta_{i,t-1}+\frac{2cL}{((i-1)N+t)n} \\
&\leq\exp\left(\left(1-\frac{1}{n}\right)\frac{c\beta}{(i-1)N+t}\right)\Delta_{i,t-1}+\frac{2cL}{((i-1)N+t)n}.
\end{aligned} Δ i , t ≤ ( 1 − n 1 ) ( 1 + η i , t − 1 β ) Δ i , t − 1 + n 1 Δ i , t − 1 + n 2 η i , t − 1 L = ( n 1 + ( 1 − n 1 ) ( 1 + ( i − 1 ) N + t c β ) ) Δ i , t − 1 + (( i − 1 ) N + t ) n 2 c L = ( 1 + ( 1 − n 1 ) ( i − 1 ) N + t c β ) Δ i , t − 1 + (( i − 1 ) N + t ) n 2 c L ≤ exp ( ( 1 − n 1 ) ( i − 1 ) N + t c β ) Δ i , t − 1 + (( i − 1 ) N + t ) n 2 c L . Unrolling this recursion from t 0 t_0 t 0 N N N
Δ i , N ≤ ∑ t = t 0 + 1 N { ∏ k = t + 1 N exp ( ( 1 − 1 n ) c β ( i − 1 ) N + k ) } 2 c L ( ( i − 1 ) N + t ) n = ∑ t = t 0 + 1 N exp ( ( 1 − 1 n ) c β ∑ k = t + 1 N 1 ( i − 1 ) N + k ) 2 c L ( ( i − 1 ) N + t ) n ≤ ∑ t = t 0 + 1 N exp ( ( 1 − 1 n ) c β ln ( i N ( i − 1 ) N + t ) ) 2 c L ( ( i − 1 ) N + t ) n = 2 c L n ( i N ) ( 1 − 1 n ) c β ∑ t = t 0 + 1 N ( ( i − 1 ) N + t ) − ( 1 − 1 n ) c β − 1 ≤ 2 c L n ( i N ) c β ∑ t = t 0 + 1 N ( ( i − 1 ) N + t ) − c β − 1 ≤ 2 c L n ( i N ) c β ∫ t 0 N ( ( i − 1 ) N + u ) − c β − 1 d u = 2 L β n [ ( i N ( i − 1 ) N + t 0 ) c β − 1 ] . (19) \begin{aligned}
\Delta_{i,N}\leq\sum_{t=t_0+1}^{N}\left\{\prod_{k=t+1}^{N}\exp\left(\left(1-\frac{1}{n}\right)\frac{c\beta}{(i-1)N+k}\right)\right\}\frac{2cL}{((i-1)N+t)n} \\
&=\sum_{t=t_0+1}^{N}\exp\left(\left(1-\frac{1}{n}\right)c\beta\sum_{k=t+1}^{N}\frac{1}{(i-1)N+k}\right)\frac{2cL}{((i-1)N+t)n} \\
&\leq\sum_{t=t_0+1}^{N}\exp\left(\left(1-\frac{1}{n}\right)c\beta\ln\left(\frac{iN}{(i-1)N+t}\right)\right)\frac{2cL}{((i-1)N+t)n} \\
&=\frac{2cL}{n}(iN)^{\left(1-\frac{1}{n}\right)c\beta}\sum_{t=t_0+1}^{N}((i-1)N+t)^{-\left(1-\frac{1}{n}\right)c\beta-1} \\
&\leq\frac{2cL}{n}(iN)^{c\beta}\sum_{t=t_0+1}^{N}((i-1)N+t)^{-c\beta-1} \\
&\leq\frac{2cL}{n}(iN)^{c\beta}\int_{t_0}^{N}((i-1)N+u)^{-c\beta-1}\,du \\
&=\frac{2L}{\beta n}\left[\left(\frac{iN}{(i-1)N+t_0}\right)^{c\beta}-1\right]. \tag*{(19)}
\end{aligned} Δ i , N ≤ t = t 0 + 1 ∑ N { k = t + 1 ∏ N exp ( ( 1 − n 1 ) ( i − 1 ) N + k c β ) } (( i − 1 ) N + t ) n 2 c L = t = t 0 + 1 ∑ N exp ( ( 1 − n 1 ) c β k = t + 1 ∑ N ( i − 1 ) N + k 1 ) (( i − 1 ) N + t ) n 2 c L ≤ t = t 0 + 1 ∑ N exp ( ( 1 − n 1 ) c β ln ( ( i − 1 ) N + t i N ) ) (( i − 1 ) N + t ) n 2 c L = n 2 c L ( i N ) ( 1 − n 1 ) c β t = t 0 + 1 ∑ N (( i − 1 ) N + t ) − ( 1 − n 1 ) c β − 1 ≤ n 2 c L ( i N ) c β t = t 0 + 1 ∑ N (( i − 1 ) N + t ) − c β − 1 ≤ n 2 c L ( i N ) c β ∫ t 0 N (( i − 1 ) N + u ) − c β − 1 d u = β n 2 L [ ( ( i − 1 ) N + t 0 i N ) c β − 1 ] . (19) where we again use i N / ( ( i − 1 ) N + t ) ≥ 1 iN/((i-1)N+t)\geq1 i N / (( i − 1 ) N + t ) ≥ 1 ( 1 − 1 / n ) c β (1-1/n)c\beta ( 1 − 1/ n ) c β c β c\beta c β i > 1 i>1 i > 1 t 0 = 0 t_0=0 t 0 = 0
E ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ≤ t 0 n + 2 L 2 β n [ ( i N ( i − 1 ) N + t 0 ) c β − 1 ] . (20) \mathbb{E}\left|f(w_i;z)-f(w'_i;z)\right|
\leq\frac{t_0}{n}+\frac{2L^2}{\beta n}\left[\left(\frac{iN}{(i-1)N+t_0}\right)^{c\beta}-1\right]. \tag*{(20)} E ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ≤ n t 0 + β n 2 L 2 [ ( ( i − 1 ) N + t 0 i N ) c β − 1 ] . (20) Differentiating the right-hand side with respect to the real variable t 0 t_0 t 0
t 0 ⋆ = ( 2 c L 2 ) 1 c β + 1 ( i N ) c β c β + 1 − ( i − 1 ) N . t_0^\star=(2cL^2)^{\frac{1}{c\beta+1}}(iN)^{\frac{c\beta}{c\beta+1}}-(i-1)N. t 0 ⋆ = ( 2 c L 2 ) c β + 1 1 ( i N ) c β + 1 c β − ( i − 1 ) N . Applying (17) to the unrolled sum, with D ( u ) = 2 c L 2 ( i N ) c β ( ( i − 1 ) N + u ) − c β − 1 D(u) = 2cL^{2}(iN)^{c\beta}((i-1)N+u)^{-c\beta-1} D ( u ) = 2 c L 2 ( i N ) c β (( i − 1 ) N + u ) − c β − 1
E ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ≤ 1 n ∫ 0 N min { 1 , 2 c L 2 ( i N ) c β ( ( i − 1 ) N + u ) c β + 1 } d u . \mathbb{E}|f(w_i;z)-f(w_i';z)| \le\frac{1}{n}\int_{0}^{N}\min\left\{1,\frac{2cL^{2}(iN)^{c\beta}}{((i-1)N+u)^{c\beta+1}}\right\}\,\mathrm{d}u. E ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ≤ n 1 ∫ 0 N min { 1 , (( i − 1 ) N + u ) c β + 1 2 c L 2 ( i N ) c β } d u . When t 0 ⋆ ≤ 0 t_0^{\star}\le0 t 0 ⋆ ≤ 0 ( 0 , N ) (0,N) ( 0 , N )
E ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ≤ 2 L 2 β n [ ( i i − 1 ) c β − 1 ] . \mathbb{E}|f(w_i;z)-f(w_i';z)|\le\frac{2L^{2}}{\beta n}\left[\left(\frac{i}{i-1}\right)^{c\beta}-1\right]. E ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ≤ β n 2 L 2 [ ( i − 1 i ) c β − 1 ] . When 0 < t 0 ⋆ < N 0<t_0^{\star}<N 0 < t 0 ⋆ < N t 0 ⋆ t_0^{\star} t 0 ⋆
E ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ≤ t 0 ⋆ n + 2 c L 2 ( i N ) c β n ∫ t 0 ⋆ N ( ( i − 1 ) N + u ) − c β − 1 d u = c β + 1 n c β ( ( i − 1 ) N + t 0 ⋆ ) − ( i − 1 ) N n − 2 L 2 β n . \begin{aligned}
\mathbb{E}|f(w_i;z)-f(w_i';z)|\le\frac{t_0^{\star}}{n}+\frac{2cL^{2}(iN)^{c\beta}}{n}\int_{t_0^{\star}}^{N}((i-1)N+u)^{-c\beta-1}\,\mathrm{d}u \\
&=\frac{c\beta+1}{nc\beta}\left((i-1)N+t_0^{\star}\right)-\frac{(i-1)N}{n}-\frac{2L^{2}}{\beta n}.
\end{aligned} E ∣ f ( w i ; z ) − f ( w i ′ ; z ) ∣ ≤ n t 0 ⋆ + n 2 c L 2 ( i N ) c β ∫ t 0 ⋆ N (( i − 1 ) N + u ) − c β − 1 d u = n c β c β + 1 ( ( i − 1 ) N + t 0 ⋆ ) − n ( i − 1 ) N − β n 2 L 2 . When t 0 ⋆ ≥ N t_0^{\star}\ge N t 0 ⋆ ≥ N ( 0 , N ) (0,N) ( 0 , N ) N / n N/n N / n t 0 ⋆ ≤ 0 t_0^{\star}\le0 t 0 ⋆ ≤ 0 t 0 ⋆ ≥ N t_0^{\star}\ge N t 0 ⋆ ≥ N 2 c L 2 ≤ ( i − 1 ) N ( ( i − 1 ) / i ) c β 2cL^{2}\le(i-1)N((i-1)/i)^{c\beta} 2 c L 2 ≤ ( i − 1 ) N (( i − 1 ) / i ) c β 2 c L 2 ≥ i N 2cL^{2}\ge iN 2 c L 2 ≥ i N t 0 ⋆ t_0^{\star} t 0 ⋆
Cross-Task Generalization Gap
Proof of Theorem 4
Theorem. If A \mathcal{A} A ϵ T , i \epsilon_{T,i} ϵ T , i
∣ E S 1 : T , A [ R D i ( A ( S 1 : T ) ) − R S i ( A ( S 1 : T ) ) ] ∣ ≤ ϵ T , i . (21) \left|\mathbb{E}_{S_{1:T},\mathcal{A}}[R_{D_i}(\mathcal{A}(S_{1:T}))-R_{S_i}(\mathcal{A}(S_{1:T}))]\right|\le\epsilon_{T,i}. \tag*{(21)} ∣ E S 1 : T , A [ R D i ( A ( S 1 : T )) − R S i ( A ( S 1 : T ))] ∣ ≤ ϵ T , i . (21) Proof. We first introduce the following notation. Let S 1 : T S_{1:T} S 1 : T S 1 : T ′ S'_{1:T} S 1 : T ′ S 1 : T ( i , k ) S_{1:T}^{(i,k)} S 1 : T ( i , k ) S 1 : T S_{1:T} S 1 : T k k k z i , k z_{i,k} z i , k S i S_i S i i i i z i , k ′ z'_{i,k} z i , k ′
S 1 : T = ( z 1 , 1 , … , z 1 , n , … , z T , 1 , … , z T , n ) , S_{1:T}=(z_{1,1},\ldots,z_{1,n},\ldots,z_{T,1},\ldots,z_{T,n}), S 1 : T = ( z 1 , 1 , … , z 1 , n , … , z T , 1 , … , z T , n ) , S 1 : T ′ = ( z 1 , 1 ′ , … , z 1 , n ′ , … , z T , 1 ′ , … , z T , n ′ ) , S'_{1:T}=(z'_{1,1},\ldots,z'_{1,n},\ldots,z'_{T,1},\ldots,z'_{T,n}), S 1 : T ′ = ( z 1 , 1 ′ , … , z 1 , n ′ , … , z T , 1 ′ , … , z T , n ′ ) , S 1 : T ( i , k ) = ( z 1 , 1 , … , z i , k − 1 , z i , k ′ , z i , k + 1 , … , z T , n ) . (22) S_{1:T}^{(i,k)}=(z_{1,1},\ldots,z_{i,k-1},z'_{i,k},z_{i,k+1},\ldots,z_{T,n}). \tag*{(22)} S 1 : T ( i , k ) = ( z 1 , 1 , … , z i , k − 1 , z i , k ′ , z i , k + 1 , … , z T , n ) . (22) With these notations, we have
E S 1 : T E A [ R S i ( A ( S 1 : T ) ) ] = E S 1 : T E A [ 1 n ∑ k = 1 n f ( A ( S 1 : T ) ; z i , k ) ] = E S 1 : T E S 1 : T ′ E A [ 1 n ∑ k = 1 n f ( A ( S 1 : T ( i , k ) ) ; z i , k ′ ) ] = E S 1 : T E S 1 : T ′ E A [ 1 n ∑ k = 1 n f ( A ( S 1 : T ) ; z i , k ′ ) ] + δ = E S 1 : T E A [ R D i ( A ( S 1 : T ) ) ] + δ . \begin{aligned}
\mathbb{E}_{S_{1:T}}\mathbb{E}_{\mathcal{A}}[R_{S_i}(\mathcal{A}(S_{1:T}))]
=\mathbb{E}_{S_{1:T}}\mathbb{E}_{\mathcal{A}}\left[\frac{1}{n}\sum_{k=1}^{n}f(\mathcal{A}(S_{1:T});z_{i,k})\right] \\
&=\mathbb{E}_{S_{1:T}}\mathbb{E}_{S'_{1:T}}\mathbb{E}_{\mathcal{A}}\left[\frac{1}{n}\sum_{k=1}^{n}f(\mathcal{A}(S_{1:T}^{(i,k)});z'_{i,k})\right] \\
&=\mathbb{E}_{S_{1:T}}\mathbb{E}_{S'_{1:T}}\mathbb{E}_{\mathcal{A}}\left[\frac{1}{n}\sum_{k=1}^{n}f(\mathcal{A}(S_{1:T});z'_{i,k})\right]+\delta\\
&=\mathbb{E}_{S_{1:T}}\mathbb{E}_{\mathcal{A}}[R_{D_i}(\mathcal{A}(S_{1:T}))]+\delta.
\end{aligned} E S 1 : T E A [ R S i ( A ( S 1 : T ))] = E S 1 : T E A [ n 1 k = 1 ∑ n f ( A ( S 1 : T ) ; z i , k ) ] = E S 1 : T E S 1 : T ′ E A [ n 1 k = 1 ∑ n f ( A ( S 1 : T ( i , k ) ) ; z i , k ′ ) ] = E S 1 : T E S 1 : T ′ E A [ n 1 k = 1 ∑ n f ( A ( S 1 : T ) ; z i , k ′ ) ] + δ = E S 1 : T E A [ R D i ( A ( S 1 : T ))] + δ . where
δ = E S 1 : T E S 1 : T ′ E A [ 1 n ∑ k = 1 n f ( A ( S 1 : T ( i , k ) ) ; z i , k ′ ) − 1 n ∑ k = 1 n f ( A ( S 1 : T ) ; z i , k ′ ) ] . \delta=\mathbb{E}_{S_{1:T}}\mathbb{E}_{S'_{1:T}}\mathbb{E}_{\mathcal{A}}\left[\frac{1}{n}\sum_{k=1}^{n}f(\mathcal{A}(S_{1:T}^{(i,k)});z'_{i,k})-\frac{1}{n}\sum_{k=1}^{n}f(\mathcal{A}(S_{1:T});z'_{i,k})\right]. δ = E S 1 : T E S 1 : T ′ E A [ n 1 k = 1 ∑ n f ( A ( S 1 : T ( i , k ) ) ; z i , k ′ ) − n 1 k = 1 ∑ n f ( A ( S 1 : T ) ; z i , k ′ ) ] . Under the assumption that A \mathcal{A} A ϵ T , i \epsilon_{T,i} ϵ T , i
∣ δ ∣ ≤ ϵ T , i . |\delta|\le\epsilon_{T,i}. ∣ δ ∣ ≤ ϵ T , i . Therefore,
∣ E S 1 : T , A [ R D i ( A ( S 1 : T ) ) − R S i ( A ( S 1 : T ) ) ] ∣ = ∣ δ ∣ ≤ ϵ T , i . \left|\mathbb{E}_{S_{1:T},\mathcal{A}}[R_{D_i}(\mathcal{A}(S_{1:T}))-R_{S_i}(\mathcal{A}(S_{1:T}))]\right|=|\delta|\le\epsilon_{T,i}. ∣ E S 1 : T , A [ R D i ( A ( S 1 : T )) − R S i ( A ( S 1 : T ))] ∣ = ∣ δ ∣ ≤ ϵ T , i . Proof of Theorem 5
Theorem. Assume that the loss function f ( ⋅ ; z ) f(\cdot;z) f ( ⋅ ; z ) N N N τ ∈ [ T ] \tau\in[T] τ ∈ [ T ] 0 ≤ η τ , t ≤ 2 β 0\le\eta_{\tau,t}\le\frac{2}{\beta} 0 ≤ η τ , t ≤ β 2 t = 0 , … , N − 1 t=0,\ldots,N-1 t = 0 , … , N − 1
ϵ T , i ≤ 2 L 2 n ∑ t = 0 N − 1 η i , t . \epsilon_{T,i}\le\frac{2L^{2}}{n}\sum_{t=0}^{N-1}\eta_{i,t}. ϵ T , i ≤ n 2 L 2 t = 0 ∑ N − 1 η i , t . Proof. Let S 1 : T S_{1:T} S 1 : T S 1 : T ′ S'_{1:T} S 1 : T ′ T T T i i i G 1 , 0 , … , G 1 , N − 1 , … , G T , 0 , … , G T , N − 1 G_{1,0},\ldots,G_{1,N-1},\ldots,G_{T,0},\ldots,G_{T,N-1} G 1 , 0 , … , G 1 , N − 1 , … , G T , 0 , … , G T , N − 1 G 1 , 0 ′ , … , G 1 , N − 1 ′ , … , G T , 0 ′ , … , G T , N − 1 ′ G'_{1,0},\ldots,G'_{1,N-1},\ldots,G'_{T,0},\ldots,G'_{T,N-1} G 1 , 0 ′ , … , G 1 , N − 1 ′ , … , G T , 0 ′ , … , G T , N − 1 ′ S 1 : T S_{1:T} S 1 : T S 1 : T ′ S'_{1:T} S 1 : T ′
First, fix an arbitrary example z ∈ Z z\in\mathcal{Z} z ∈ Z L L L f ( ⋅ ; z ) f(\cdot;z) f ( ⋅ ; z )
E ∣ f ( w T , N ; z ) − f ( w T , N ′ ; z ) ∣ ≤ L E [ δ T , N ] , (23) \mathbb{E}|f(w_{T,N};z)-f(w'_{T,N};z)|\le L\mathbb{E}[\delta_{T,N}], \tag*{(23)} E ∣ f ( w T , N ; z ) − f ( w T , N ′ ; z ) ∣ ≤ L E [ δ T , N ] , (23) where δ T , N = ∥ w T , N − w T , N ′ ∥ \delta_{T,N}=\|w_{T,N}-w'_{T,N}\| δ T , N = ∥ w T , N − w T , N ′ ∥ w k , 0 = w k − 1 , N w_{k,0}=w_{k-1,N} w k , 0 = w k − 1 , N w k , 0 ′ = w k − 1 , N ′ w'_{k,0}=w'_{k-1,N} w k , 0 ′ = w k − 1 , N ′ k ∈ { 2 , … , T } k\in\{2,\ldots,T\} k ∈ { 2 , … , T } δ k , 0 = δ k − 1 , N \delta_{k,0}=\delta_{k-1,N} δ k , 0 = δ k − 1 , N E [ δ T , N ] \mathbb{E}[\delta_{T,N}] E [ δ T , N ]
(i) When the task index satisfies j ∈ { i + 1 , i + 2 , … , T } j\in\{i+1,i+2,\ldots,T\} j ∈ { i + 1 , i + 2 , … , T } j j j S 1 : T S_{1:T} S 1 : T S 1 : T ′ S'_{1:T} S 1 : T ′ G j , t = G j , t ′ G_{j,t}=G'_{j,t} G j , t = G j , t ′ j ∈ { i + 1 , i + 2 , … , T } j\in\{i+1,i+2,\ldots,T\} j ∈ { i + 1 , i + 2 , … , T } t ∈ { 0 , … , N − 1 } t\in\{0,\ldots,N-1\} t ∈ { 0 , … , N − 1 } G j , t G_{j,t} G j , t
E [ δ T , N ] ≤ E [ δ T , N − 1 ] ≤ ⋯ ≤ E [ δ T , 0 ] = E [ δ T − 1 , N ] ≤ ⋯ ≤ E [ δ i + 1 , 0 ] = E [ δ i , N ] . (24) \mathbb{E}[\delta_{T,N}]\le\mathbb{E}[\delta_{T,N-1}]\le\cdots\le\mathbb{E}[\delta_{T,0}]
=\mathbb{E}[\delta_{T-1,N}]\le\cdots
\le\mathbb{E}[\delta_{i+1,0}]=\mathbb{E}[\delta_{i,N}]. \tag*{(24)} E [ δ T , N ] ≤ E [ δ T , N − 1 ] ≤ ⋯ ≤ E [ δ T , 0 ] = E [ δ T − 1 , N ] ≤ ⋯ ≤ E [ δ i + 1 , 0 ] = E [ δ i , N ] . (24) (ii) During the t t t i i i 1 − 1 n 1-\frac{1}{n} 1 − n 1 S i S_i S i S i ′ S'_i S i ′ G i , t = G i , t ′ G_{i,t}=G'_{i,t} G i , t = G i , t ′ G i , t G_{i,t} G i , t f f f 1 n \frac{1}{n} n 1 G i , t G_{i,t} G i , t G i , t ′ G'_{i,t} G i , t ′ η i , t L \eta_{i,t}L η i , t L
Combining these two cases, we obtain the following recurrence relation for t = 0 , … , N − 1 t=0,\ldots,N-1 t = 0 , … , N − 1
E [ δ i , t + 1 ] ≤ ( 1 − 1 n ) E [ δ i , t ] + 1 n E [ δ i , t ] + 2 η i , t L n = E [ δ i , t ] + 2 η i , t L n . \begin{aligned}
\mathbb{E}[\delta_{i,t+1}]\le\left(1-\frac{1}{n}\right)\mathbb{E}[\delta_{i,t}]+\frac{1}{n}\mathbb{E}[\delta_{i,t}]+\frac{2\eta_{i,t}L}{n} \\
&=\mathbb{E}[\delta_{i,t}]+\frac{2\eta_{i,t}L}{n}.
\end{aligned} E [ δ i , t + 1 ] ≤ ( 1 − n 1 ) E [ δ i , t ] + n 1 E [ δ i , t ] + n 2 η i , t L = E [ δ i , t ] + n 2 η i , t L . Unraveling this recursion from step N N N 0 0 0 i i i
E [ δ i , N ] ≤ E [ δ i , 0 ] + ∑ t = 0 N − 1 2 η i , t L n . (25) \mathbb{E}[\delta_{i,N}] \le\mathbb{E}[\delta_{i,0}] + \sum_{t=0}^{N-1}\frac{2\eta_{i,t}L}{n}. \tag*{(25)} E [ δ i , N ] ≤ E [ δ i , 0 ] + t = 0 ∑ N − 1 n 2 η i , t L . (25) Since the data perturbation occurs only in the dataset for task i i i m ∈ { 1 , … , i − 1 } m \in\{1,\ldots,i-1\} m ∈ { 1 , … , i − 1 } t ∈ { 0 , … , N − 1 } t \in\{0,\ldots,N-1\} t ∈ { 0 , … , N − 1 } G m , t = G m , t ′ G_{m,t}=G'_{m,t} G m , t = G m , t ′
0 ≤ E [ δ i , 0 ] ≤ E [ δ i − 1 , N ] ≤ ⋯ ≤ E [ δ 1 , 0 ] = 0. 0 \le\mathbb{E}[\delta_{i,0}] \le\mathbb{E}[\delta_{i-1,N}] \le\cdots\le\mathbb{E}[\delta_{1,0}]=0. 0 ≤ E [ δ i , 0 ] ≤ E [ δ i − 1 , N ] ≤ ⋯ ≤ E [ δ 1 , 0 ] = 0. Substituting E [ δ i , 0 ] = 0 \mathbb{E}[\delta_{i,0}]=0 E [ δ i , 0 ] = 0 (25) and combining it with (24) , we obtain
E [ δ T , N ] ≤ 2 L n ∑ t = 0 N − 1 η i , t . \mathbb{E}[\delta_{T,N}] \le\frac{2L}{n}\sum_{t=0}^{N-1}\eta_{i,t}. E [ δ T , N ] ≤ n 2 L t = 0 ∑ N − 1 η i , t . Finally, plugging this bound back into (23) , we arrive at the stability bound:
E ∣ f ( w T , N ; z ) − f ( w T , N ′ ; z ) ∣ ≤ 2 L 2 n ∑ t = 0 N − 1 η i , t . \mathbb{E}|f(w_{T,N};z)-f(w'_{T,N};z)| \le\frac{2L^2}{n}\sum_{t=0}^{N-1}\eta_{i,t}. E ∣ f ( w T , N ; z ) − f ( w T , N ′ ; z ) ∣ ≤ n 2 L 2 t = 0 ∑ N − 1 η i , t . Proof of Theorem 6
Lemma 3. Assume that the loss function f ( ⋅ ; z ) f(\cdot;z) f ( ⋅ ; z ) L L L z z z n ≥ 2 n \ge2 n ≥ 2 S 1 : T S_{1:T} S 1 : T S 1 : T ′ S'_{1:T} S 1 : T ′ T T T i i i z ∈ Z z \in\mathcal{Z} z ∈ Z t 0 ∈ { 0 , 1 , … , N } t_0 \in\{0,1,\ldots,N\} t 0 ∈ { 0 , 1 , … , N }
E ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ≤ t 0 n sup w , z f ( w ; z ) + L E [ ∥ w T − w T ′ ∥ ∣ δ i , t 0 = 0 ] . \mathbb{E}|f(w_T;z)-f(w'_T;z)| \le\frac{t_0}{n}\sup_{w,z}f(w;z)+L\mathbb{E}[\|w_T-w'_T\|\mid\delta_{i,t_0}=0]. E ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ≤ n t 0 w , z sup f ( w ; z ) + L E [ ∥ w T − w T ′ ∥ ∣ δ i , t 0 = 0 ] . The same inequality holds under the random permutation rule for 0 ≤ t 0 ≤ N 0 \le t_0 \le N 0 ≤ t 0 ≤ N t 0 < n t_0<n t 0 < n
Proof. Let E \mathcal{E} E δ i , t 0 = 0 \delta_{i,t_0}=0 δ i , t 0 = 0 t 0 t_0 t 0 i i i
E ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ = P { E } E [ ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ∣ E ] + P { E c } E [ ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ∣ E c ] ≤ E [ ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ∣ E ] + P { E c } sup w , z f ( w ; z ) ≤ L E [ ∥ w T − w T ′ ∥ ∣ E ] + P { E c } sup w , z f ( w ; z ) . \begin{aligned}
\mathbb{E}|f(w_T;z)-f(w'_T;z)|
={}&\mathbb{P}\{\mathcal{E}\}\mathbb{E}[|f(w_T;z)-f(w'_T;z)|\mid\mathcal{E}]\\
&+\mathbb{P}\{\mathcal{E}^{c}\}\mathbb{E}[|f(w_T;z)-f(w'_T;z)|\mid\mathcal{E}^{c}]\\
\le{}&\mathbb{E}[|f(w_T;z)-f(w'_T;z)|\mid\mathcal{E}]+\mathbb{P}\{\mathcal{E}^{c}\}\sup_{w,z}f(w;z)\\
\le{}&L\mathbb{E}[\|w_T-w'_T\|\mid\mathcal{E}]+\mathbb{P}\{\mathcal{E}^{c}\}\sup_{w,z}f(w;z).
\end{aligned} E ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ = ≤ ≤ P { E } E [ ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ∣ E ] + P { E c } E [ ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ∣ E c ] E [ ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ∣ E ] + P { E c } w , z sup f ( w ; z ) L E [ ∥ w T − w T ′ ∥ ∣ E ] + P { E c } w , z sup f ( w ; z ) . The bound on P { E c } \mathbb{P}\{\mathcal{E}^{c}\} P { E c }
Theorem. Assume that the loss function f ( ⋅ ; z ) ∈ [ 0 , 1 ] f(\cdot;z)\in[0,1] f ( ⋅ ; z ) ∈ [ 0 , 1 ] n ≥ 2 n\ge2 n ≥ 2 c , β > 0 c,\beta>0 c , β > 0 N N N τ ∈ [ T ] \tau\in[T] τ ∈ [ T ] η τ , t \eta_{\tau,t} η τ , t t = 0 , … , N − 1 t=0,\ldots,N-1 t = 0 , … , N − 1
(a) under intra-task decaying learning rates η τ , t = c t + 1 \eta_{\tau,t}=\frac{c}{t+1} η τ , t = t + 1 c
ϵ T , i ≤ { B 2 1 , if 2 c L 2 ( e N ) c β ( T − i ) < N , N n , if 2 c L 2 ( e N ) c β ( T − i ) ≥ N . \epsilon_{T,i}\le
\begin{cases}
\mathcal{B}^{1}_{2}, & \text{if }2cL^2(eN)^{c\beta(T-i)}<N,\\
\frac{N}{n}, & \text{if }2cL^2(eN)^{c\beta(T-i)}\ge N.
\end{cases} ϵ T , i ≤ { B 2 1 , n N , if 2 c L 2 ( e N ) c β ( T − i ) < N , if 2 c L 2 ( e N ) c β ( T − i ) ≥ N . where
B 2 1 = K N ( e N ) c β ( T − i ) c β + 1 − 2 L 2 ( e N ) c β ( T − i ) β n . \mathcal{B}^{1}_{2}=\mathcal{K}_{N}(eN)^{\frac{c\beta(T-i)}{c\beta+1}}-\frac{2L^2(eN)^{c\beta(T-i)}}{\beta n}. B 2 1 = K N ( e N ) c β + 1 c β ( T − i ) − β n 2 L 2 ( e N ) c β ( T − i ) . (b) under continuously decaying learning rates η τ , t = c ( τ − 1 ) N + t + 1 \eta_{\tau,t}=\frac{c}{(\tau-1)N+t+1} η τ , t = ( τ − 1 ) N + t + 1 c i > 1 i>1 i > 1
ϵ T , i ≤ { 2 L 2 β n [ ( T i − 1 ) c β − ( T i ) c β ] , if 2 c L 2 ≤ C 2 C D , B 2 2 , if C 2 C D < 2 c L 2 < i N ( i T ) c β , N n , if 2 c L 2 ≥ i N ( i T ) c β . \epsilon_{T,i}\le
\begin{cases}
\frac{2L^2}{\beta n}\left[\left(\frac{T}{i-1}\right)^{c\beta}-\left(\frac{T}{i}\right)^{c\beta}\right], & \text{if }2cL^2\le\mathcal{C}^{\mathrm{CD}}_{2},\\
\mathcal{B}^{2}_{2}, & \text{if }\mathcal{C}^{\mathrm{CD}}_{2}<2cL^2<iN\left(\frac{i}{T}\right)^{c\beta},\\
\frac{N}{n}, & \text{if }2cL^2\ge iN\left(\frac{i}{T}\right)^{c\beta}.
\end{cases} ϵ T , i ≤ ⎩ ⎨ ⎧ β n 2 L 2 [ ( i − 1 T ) c β − ( i T ) c β ] , B 2 2 , n N , if 2 c L 2 ≤ C 2 CD , if C 2 CD < 2 c L 2 < i N ( T i ) c β , if 2 c L 2 ≥ i N ( T i ) c β . where
B 2 2 = K T N − ( i − 1 ) N n − 2 L 2 β n ( T i ) c β , \mathcal{B}^{2}_{2}=\mathcal{K}_{TN}-\frac{(i-1)N}{n}-\frac{2L^2}{\beta n}\left(\frac{T}{i}\right)^{c\beta}, B 2 2 = K T N − n ( i − 1 ) N − β n 2 L 2 ( i T ) c β , C 2 C D = ( i − 1 ) N ( i − 1 T ) c β . \mathcal{C}^{\mathrm{CD}}_{2}=(i-1)N\left(\frac{i-1}{T}\right)^{c\beta}. C 2 CD = ( i − 1 ) N ( T i − 1 ) c β . For i = 1 i=1 i = 1
ϵ T , 1 ≤ { K T N − 2 L 2 T c β β n , if 2 c L 2 T c β c β < N , N n , if 2 c L 2 T c β c β ≥ N . \epsilon_{T,1}\le
\begin{cases}
\mathcal{K}_{TN}-\frac{2L^2T^{c\beta}}{\beta n}, & \text{if }\frac{2cL^2T^{c\beta}}{c\beta}<N,\\
\frac{N}{n}, & \text{if }\frac{2cL^2T^{c\beta}}{c\beta}\ge N.
\end{cases} ϵ T , 1 ≤ { K T N − β n 2 L 2 T c β , n N , if c β 2 c L 2 T c β < N , if c β 2 c L 2 T c β ≥ N . Proof. Let S 1 : T S_{1:T} S 1 : T S 1 : T ′ S'_{1:T} S 1 : T ′ T T T i i i G 1 , 0 , … , G 1 , N − 1 , … , G T , 0 , … , G T , N − 1 G_{1,0},\ldots,G_{1,N-1},\ldots,G_{T,0},\ldots,G_{T,N-1} G 1 , 0 , … , G 1 , N − 1 , … , G T , 0 , … , G T , N − 1 G 1 , 0 ′ , … , G 1 , N − 1 ′ , … , G T , 0 ′ , … , G T , N − 1 ′ G'_{1,0},\ldots,G'_{1,N-1},\ldots,G'_{T,0},\ldots,G'_{T,N-1} G 1 , 0 ′ , … , G 1 , N − 1 ′ , … , G T , 0 ′ , … , G T , N − 1 ′ S 1 : T S_{1:T} S 1 : T S 1 : T ′ S'_{1:T} S 1 : T ′
By Lemma 3, for any integer t 0 ∈ { 0 , … , N } t_0\in\{0,\ldots,N\} t 0 ∈ { 0 , … , N }
E ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ≤ t 0 n + L E [ ∥ w T − w T ′ ∥ ∣ δ i , t 0 = 0 ] . (26) \mathbb{E}|f(w_T;z)-f(w'_T;z)|\le\frac{t_0}{n}+L\mathbb{E}[\|w_T-w'_T\|\mid\delta_{i,t_0}=0]. \tag*{(26)} E ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ≤ n t 0 + L E [ ∥ w T − w T ′ ∥ ∣ δ i , t 0 = 0 ] . (26) Define Δ τ , t : = E [ δ τ , t ∣ δ i , t 0 = 0 ] \Delta_{\tau,t}:=\mathbb{E}[\delta_{\tau,t}\mid\delta_{i,t_0}=0] Δ τ , t := E [ δ τ , t ∣ δ i , t 0 = 0 ] Δ T , N \Delta_{T,N} Δ T , N m ∈ { i + 1 , … , T } m\in\{i+1,\ldots,T\} m ∈ { i + 1 , … , T } S 1 : T S_{1:T} S 1 : T S 1 : T ′ S'_{1:T} S 1 : T ′ G m , t = G m , t ′ G_{m,t}=G'_{m,t} G m , t = G m , t ′ t ∈ { 0 , … , N − 1 } t\in\{0,\ldots,N-1\} t ∈ { 0 , … , N − 1 } ( 1 + η m , t β ) (1+\eta_{m,t}\beta) ( 1 + η m , t β ) G m , t G_{m,t} G m , t
Therefore, for any t ∈ { 0 , … , N − 1 } t\in\{0,\ldots,N-1\} t ∈ { 0 , … , N − 1 }
(a) under intra-task decaying learning rates η τ , t = c t + 1 \eta_{\tau,t}=\frac{c}{t+1} η τ , t = t + 1 c
Δ T , t + 1 ≤ ( 1 + η T , t β ) Δ T , t = ( 1 + c β t + 1 ) Δ T , t ≤ exp ( c β t + 1 ) Δ T , t . \Delta_{T,t+1}\le(1+\eta_{T,t}\beta)\Delta_{T,t}
=\left(1+\frac{c\beta}{t+1}\right)\Delta_{T,t}
\le\exp\left(\frac{c\beta}{t+1}\right)\Delta_{T,t}. Δ T , t + 1 ≤ ( 1 + η T , t β ) Δ T , t = ( 1 + t + 1 c β ) Δ T , t ≤ exp ( t + 1 c β ) Δ T , t . Unrolling this recursion from N N N 0 0 0
Δ T , N ≤ ∏ k = 0 N − 1 exp ( c β k + 1 ) Δ T , 0 = exp ( c β ∑ k = 0 N − 1 1 k + 1 ) Δ T , 0 = exp ( c β ∑ k = 1 N 1 k ) Δ T , 0 ≤ exp ( c β ( ln N + 1 ) ) Δ T , 0 = ( e N ) c β Δ T , 0 . \begin{aligned}
\Delta_{T,N}
&\le\prod_{k=0}^{N-1}\exp\left(\frac{c\beta}{k+1}\right)\Delta_{T,0}\\
&=\exp\left(c\beta\sum_{k=0}^{N-1}\frac{1}{k+1}\right)\Delta_{T,0}\\
&=\exp\left(c\beta\sum_{k=1}^{N}\frac{1}{k}\right)\Delta_{T,0}\\
&\le\exp\left(c\beta(\ln N+1)\right)\Delta_{T,0}\\
&=(eN)^{c\beta}\Delta_{T,0}.
\end{aligned} Δ T , N ≤ k = 0 ∏ N − 1 exp ( k + 1 c β ) Δ T , 0 = exp ( c β k = 0 ∑ N − 1 k + 1 1 ) Δ T , 0 = exp ( c β k = 1 ∑ N k 1 ) Δ T , 0 ≤ exp ( c β ( ln N + 1 ) ) Δ T , 0 = ( e N ) c β Δ T , 0 . Under the CL protocol, the initialization of each task is the final model from the previous task, namely w k , 0 = w k − 1 , N w_{k,0}=w_{k-1,N} w k , 0 = w k − 1 , N w k , 0 ′ = w k − 1 , N ′ w'_{k,0}=w'_{k-1,N} w k , 0 ′ = w k − 1 , N ′ k ∈ { 2 , … , T } k\in\{2,\ldots,T\} k ∈ { 2 , … , T } δ k , 0 = δ k − 1 , N \delta_{k,0}=\delta_{k-1,N} δ k , 0 = δ k − 1 , N
Δ T , N ≤ ( e N ) c β Δ T , 0 = ( e N ) c β Δ T − 1 , N ≤ ⋯ ≤ ( e N ) c β ( T − i ) Δ i , N . \Delta_{T,N}\le(eN)^{c\beta}\Delta_{T,0}
= (eN)^{c\beta}\Delta_{T-1,N}
\le\cdots\le(eN)^{c\beta(T-i)}\Delta_{i,N}. Δ T , N ≤ ( e N ) c β Δ T , 0 = ( e N ) c β Δ T − 1 , N ≤ ⋯ ≤ ( e N ) c β ( T − i ) Δ i , N . For 1 ≤ t 0 ≤ N 1\le t_0\le N 1 ≤ t 0 ≤ N (18) further gives
Δ T , N ≤ 2 L ( e N ) c β ( T − i ) β n [ ( N t 0 ) c β − 1 ] . \Delta_{T,N}\le\frac{2L(eN)^{c\beta(T-i)}}{\beta n}\left[\left(\frac{N}{t_0}\right)^{c\beta}-1\right]. Δ T , N ≤ β n 2 L ( e N ) c β ( T − i ) [ ( t 0 N ) c β − 1 ] . Substituting this bound into (26) , we have
E ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ≤ t 0 n + 2 L 2 ( e N ) c β ( T − i ) β n [ ( N t 0 ) c β − 1 ] . \mathbb{E}\left|f(w_T;z)-f(w'_T;z)\right|
\le\frac{t_0}{n}+\frac{2L^2(eN)^{c\beta(T-i)}}{\beta n}\left[\left(\frac{N}{t_0}\right)^{c\beta}-1\right]. E ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ≤ n t 0 + β n 2 L 2 ( e N ) c β ( T − i ) [ ( t 0 N ) c β − 1 ] . Differentiating the right-hand side with respect to a positive real cutoff gives the stationary point
t ^ 0 = ( 2 c L 2 ) 1 c β + 1 e c β ( T − i ) c β + 1 N c β ( T − i + 1 ) c β + 1 . \widehat{t}_0=(2cL^2)^{\frac{1}{c\beta+1}}e^{\frac{c\beta(T-i)}{c\beta+1}}N^{\frac{c\beta(T-i+1)}{c\beta+1}}. t 0 = ( 2 c L 2 ) c β + 1 1 e c β + 1 c β ( T − i ) N c β + 1 c β ( T − i + 1 ) . For integer SGD steps, apply (17) to the unrolled sum in (18) , after using ( N / t ) ( 1 − 1 / n ) c β ≤ ( N / t ) c β (N/t)^{(1-1/n)c\beta}\le(N/t)^{c\beta} ( N / t ) ( 1 − 1/ n ) c β ≤ ( N / t ) c β
D ( x ) = 2 c L 2 ( e N ) c β ( T − i ) N c β x − c β − 1 . D(x)=2cL^2(eN)^{c\beta(T-i)}Nc\beta x^{-c\beta-1}. D ( x ) = 2 c L 2 ( e N ) c β ( T − i ) N c β x − c β − 1 . When 0 < t ^ 0 < N 0<\widehat{t}_0<N 0 < t 0 < N t ^ 0 \widehat{t}_0 t 0
E ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ≤ t ^ 0 n + 2 L 2 ( e N ) c β ( T − i ) β n [ ( N t ^ 0 ) c β − 1 ] = c β + 1 n c β t ^ 0 − 2 L 2 ( e N ) c β ( T − i ) β n . \mathbb{E}\left|f(w_T;z)-f(w'_T;z)\right|
\le\frac{\widehat{t}_0}{n}+\frac{2L^2(eN)^{c\beta(T-i)}}{\beta n}\left[\left(\frac{N}{\widehat{t}_0}\right)^{c\beta}-1\right]
= \frac{c\beta+1}{nc\beta}\widehat{t}_0-\frac{2L^2(eN)^{c\beta(T-i)}}{\beta n}. E ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ≤ n t 0 + β n 2 L 2 ( e N ) c β ( T − i ) [ ( t 0 N ) c β − 1 ] = n c β c β + 1 t 0 − β n 2 L 2 ( e N ) c β ( T − i ) . This evaluation also covers t ^ 0 < 1 \widehat{t}_0<1 t 0 < 1 (17) permits a zero integer cutoff. When t ^ 0 ≥ N \widehat{t}_0\ge N t 0 ≥ N N N N N / n N/n N / n t ^ 0 < N \widehat{t}_0<N t 0 < N 2 c L 2 ( e N ) c β ( T − i ) < N 2cL^2(eN)^{c\beta(T-i)}<N 2 c L 2 ( e N ) c β ( T − i ) < N L = 0 L=0 L = 0
(b) under continuously decaying learning rates η τ , t = c ( τ − 1 ) N + t + 1 \eta_{\tau,t}=\frac{c}{(\tau-1)N+t+1} η τ , t = ( τ − 1 ) N + t + 1 c
Δ T , t + 1 ≤ ( 1 + η T , t β ) Δ T , t = ( 1 + c β ( T − 1 ) N + t + 1 ) Δ T , t ≤ exp ( c β ( T − 1 ) N + t + 1 ) Δ T , t . \Delta_{T,t+1}\le(1+\eta_{T,t}\beta)\Delta_{T,t}
=\left(1+\frac{c\beta}{(T-1)N+t+1}\right)\Delta_{T,t}
\le\exp\left(\frac{c\beta}{(T-1)N+t+1}\right)\Delta_{T,t}. Δ T , t + 1 ≤ ( 1 + η T , t β ) Δ T , t = ( 1 + ( T − 1 ) N + t + 1 c β ) Δ T , t ≤ exp ( ( T − 1 ) N + t + 1 c β ) Δ T , t . For any j ∈ { i + 1 , … , T } j\in\{i+1,\ldots,T\} j ∈ { i + 1 , … , T } N N N 0 0 0
Δ j , N ≤ ∏ k = 0 N − 1 exp ( c β ( j − 1 ) N + k + 1 ) Δ j , 0 = exp ( c β ∑ k = 0 N − 1 1 ( j − 1 ) N + k + 1 ) Δ j , 0 = exp ( c β ∑ k = 1 N 1 ( j − 1 ) N + k ) Δ j , 0 ≤ exp ( c β ln ( j j − 1 ) ) Δ j , 0 = ( j j − 1 ) c β Δ j , 0 . \begin{aligned}
\Delta_{j,N}\le\prod_{k=0}^{N-1}\exp\left(\frac{c\beta}{(j-1)N+k+1}\right)\Delta_{j,0}
=\exp\left(c\beta\sum_{k=0}^{N-1}\frac{1}{(j-1)N+k+1}\right)\Delta_{j,0} \\
&=\exp\left(c\beta\sum_{k=1}^{N}\frac{1}{(j-1)N+k}\right)\Delta_{j,0}
\le\exp\left(c\beta\ln\left(\frac{j}{j-1}\right)\right)\Delta_{j,0}
=\left(\frac{j}{j-1}\right)^{c\beta}\Delta_{j,0}.
\end{aligned} Δ j , N ≤ k = 0 ∏ N − 1 exp ( ( j − 1 ) N + k + 1 c β ) Δ j , 0 = exp ( c β k = 0 ∑ N − 1 ( j − 1 ) N + k + 1 1 ) Δ j , 0 = exp ( c β k = 1 ∑ N ( j − 1 ) N + k 1 ) Δ j , 0 ≤ exp ( c β ln ( j − 1 j ) ) Δ j , 0 = ( j − 1 j ) c β Δ j , 0 . Under the CL protocol, the initialization of each task is the final model from the previous task, namely w k , 0 = w k − 1 , N w_{k,0}=w_{k-1,N} w k , 0 = w k − 1 , N w k , 0 ′ = w k − 1 , N ′ w'_{k,0}=w'_{k-1,N} w k , 0 ′ = w k − 1 , N ′ k ∈ { 2 , … , T } k\in\{2,\ldots,T\} k ∈ { 2 , … , T } δ k , 0 = δ k − 1 , N \delta_{k,0}=\delta_{k-1,N} δ k , 0 = δ k − 1 , N
Δ T , N ≤ ( T T − 1 ) c β Δ T , 0 = ( T T − 1 ) c β Δ T − 1 , N ≤ ⋯ ≤ ( T T − 1 ) c β ⋯ ( i + 1 i ) c β Δ i , N = ( T i ) c β Δ i , N . \Delta_{T,N}\le\left(\frac{T}{T-1}\right)^{c\beta}\Delta_{T,0}
=\left(\frac{T}{T-1}\right)^{c\beta}\Delta_{T-1,N}
\le\cdots
\le\left(\frac{T}{T-1}\right)^{c\beta}\cdots\left(\frac{i+1}{i}\right)^{c\beta}\Delta_{i,N}
=\left(\frac{T}{i}\right)^{c\beta}\Delta_{i,N}. Δ T , N ≤ ( T − 1 T ) c β Δ T , 0 = ( T − 1 T ) c β Δ T − 1 , N ≤ ⋯ ≤ ( T − 1 T ) c β ⋯ ( i i + 1 ) c β Δ i , N = ( i T ) c β Δ i , N . Based on (19) , we can further obtain
Δ T , N ≤ 2 L β n [ ( T N ( i − 1 ) N + t 0 ) c β − ( T i ) c β ] . \Delta_{T,N}\le\frac{2L}{\beta n}\left[\left(\frac{TN}{(i-1)N+t_0}\right)^{c\beta}-\left(\frac{T}{i}\right)^{c\beta}\right]. Δ T , N ≤ β n 2 L [ ( ( i − 1 ) N + t 0 T N ) c β − ( i T ) c β ] . Substituting this bound into (26) , we have
E ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ≤ t 0 n + 2 L 2 β n [ ( T N ( i − 1 ) N + t 0 ) c β − ( T i ) c β ] . (27) \mathbb{E}\left|f(w_T;z)-f(w'_T;z)\right|
\le\frac{t_0}{n}+\frac{2L^2}{\beta n}\left[\left(\frac{TN}{(i-1)N+t_0}\right)^{c\beta}-\left(\frac{T}{i}\right)^{c\beta}\right]. \tag*{(27)} E ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ≤ n t 0 + β n 2 L 2 [ ( ( i − 1 ) N + t 0 T N ) c β − ( i T ) c β ] . (27) Differentiating the right-hand side gives the stationary point of its continuous relaxation:
t ^ 0 = ( 2 c L 2 ) 1 c β + 1 ( T N ) c β c β + 1 − ( i − 1 ) N . \widehat{t}_0=(2cL^2)^{\frac{1}{c\beta+1}}(TN)^{\frac{c\beta}{c\beta+1}}-(i-1)N. t 0 = ( 2 c L 2 ) c β + 1 1 ( T N ) c β + 1 c β − ( i − 1 ) N . The integer cutoff is again justified by (17) , applied to the finite-sum recursion with
D ( x ) = 2 c L 2 ( T N ) c β ( ( i − 1 ) N + x ) − c β − 1 . D(x)=2cL^2(TN)^{c\beta}\bigl((i-1)N+x\bigr)^{-c\beta-1}. D ( x ) = 2 c L 2 ( T N ) c β ( ( i − 1 ) N + x ) − c β − 1 . If t ^ 0 ≤ 0 \widehat{t}_0\le0 t 0 ≤ 0 t 0 = 0 t_0=0 t 0 = 0 (27) . This gives
E ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ≤ 2 L 2 β n [ ( T i − 1 ) c β − ( T i ) c β ] . \mathbb{E}\left|f(w_T;z)-f(w'_T;z)\right|
\le\frac{2L^2}{\beta n}\left[\left(\frac{T}{i-1}\right)^{c\beta}-\left(\frac{T}{i}\right)^{c\beta}\right]. E ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ≤ β n 2 L 2 [ ( i − 1 T ) c β − ( i T ) c β ] . If 0 < t ^ 0 < N 0<\widehat{t}_0<N 0 < t 0 < N
E ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ≤ c β + 1 n c β ( ( i − 1 ) N + t ^ 0 ) − ( i − 1 ) N n − 2 L 2 β n ( T i ) c β . \mathbb{E}\left|f(w_T;z)-f(w'_T;z)\right|
\le\frac{c\beta+1}{nc\beta}\bigl((i-1)N+\widehat{t}_0\bigr)-\frac{(i-1)N}{n}-\frac{2L^2}{\beta n}\left(\frac{T}{i}\right)^{c\beta}. E ∣ f ( w T ; z ) − f ( w T ′ ; z ) ∣ ≤ n c β c β + 1 ( ( i − 1 ) N + t 0 ) − n ( i − 1 ) N − β n 2 L 2 ( i T ) c β . If t ^ 0 ≥ N \hat{t}_0 \ge N t ^ 0 ≥ N N N N N / n N/n N / n t ^ 0 ≤ 0 \hat{t}_0 \le0 t ^ 0 ≤ 0 t ^ 0 > N \hat{t}_0 > N t ^ 0 > N 2 c L 2 ≤ ( i − 1 ) N ( ( i − 1 ) / T ) c β 2cL^2 \le(i-1)N((i-1)/T)^{c\beta} 2 c L 2 ≤ ( i − 1 ) N (( i − 1 ) / T ) c β 2 c L 2 ≥ i N ( i / T ) c β 2cL^2 \ge iN(i/T)^{c\beta} 2 c L 2 ≥ i N ( i / T ) c β i = 1 i=1 i = 1 T c β T^{c\beta} T c β
Appendix D: Empirical Forgetting
Theorem. Assume that the loss function f ( ⋅ ; z ) f(\cdot;z) f ( ⋅ ; z ) N N N τ ∈ [ T ] \tau\in[T] τ ∈ [ T ] η τ , t \eta_{\tau,t} η τ , t (a) under constant learning rates η τ , t = c \eta_{\tau,t}=c η τ , t = c
ϵ ~ T , i ≤ − G T , i + β c 2 L 2 2 N ( T − i ) ; \widetilde{\epsilon}_{T,i} \le-G_{T,i}+\frac{\beta c^2L^2}{2}N(T-i); ϵ T , i ≤ − G T , i + 2 β c 2 L 2 N ( T − i ) ; (b) under intra-task decaying learning rates η τ , t = c t + 1 \eta_{\tau,t}=\frac{c}{t+1} η τ , t = t + 1 c
ϵ ~ T , i ≤ − G T , i + β c 2 L 2 2 ( 2 − 1 N ) ( T − i ) ; \widetilde{\epsilon}_{T,i} \le-G_{T,i}+\frac{\beta c^2L^2}{2}\left(2-\frac{1}{N}\right)(T-i); ϵ T , i ≤ − G T , i + 2 β c 2 L 2 ( 2 − N 1 ) ( T − i ) ; (c) under continuously decaying learning rates η τ , t = c ( τ − 1 ) N + t + 1 \eta_{\tau,t}=\frac{c}{(\tau-1)N+t+1} η τ , t = ( τ − 1 ) N + t + 1 c
ϵ ~ T , i ≤ − G T , i + β c 2 L 2 2 ( 1 i N − 1 T N ) . \widetilde{\epsilon}_{T,i} \le-G_{T,i}+\frac{\beta c^2L^2}{2}\left(\frac{1}{iN}-\frac{1}{TN}\right). ϵ T , i ≤ − G T , i + 2 β c 2 L 2 ( i N 1 − T N 1 ) . Proof. We first consider the impact on task i i i τ > i \tau>i τ > i F τ , t \mathcal{F}_{\tau,t} F τ , t i t i_t i t [ n ] [n] [ n ]
E [ ∇ f ( w τ , t ; z τ , i t ) ∣ F τ , t ] = ∇ R S τ ( w τ , t ) , \mathbb{E}[\nabla f(w_{\tau,t};z_{\tau,i_t})\mid\mathcal{F}_{\tau,t}]=\nabla R_{S_\tau}(w_{\tau,t}), E [ ∇ f ( w τ , t ; z τ , i t ) ∣ F τ , t ] = ∇ R S τ ( w τ , t ) , E [ ∥ ∇ f ( w τ , t ; z τ , i t ) ∥ 2 ∣ F τ , t ] = 1 n ∑ j = 1 n ∥ ∇ f ( w τ , t ; z τ , j ) ∥ 2 . \mathbb{E}[\|\nabla f(w_{\tau,t};z_{\tau,i_t})\|^2\mid\mathcal{F}_{\tau,t}]=\frac{1}{n}\sum_{j=1}^{n}\|\nabla f(w_{\tau,t};z_{\tau,j})\|^2. E [ ∥∇ f ( w τ , t ; z τ , i t ) ∥ 2 ∣ F τ , t ] = n 1 j = 1 ∑ n ∥∇ f ( w τ , t ; z τ , j ) ∥ 2 . The function R S i R_{S_i} R S i β \beta β
E [ R S i ( w τ , t + 1 ) − R S i ( w τ , t ) ∣ F τ , t ] ≤ − η τ , t ⟨ ∇ R S i ( w τ , t ) , ∇ R S τ ( w τ , t ) ⟩ + β η τ , t 2 2 n ∑ j = 1 n ∥ ∇ f ( w τ , t ; z τ , j ) ∥ 2 ≤ − η τ , t ⟨ ∇ R S i ( w τ , t ) , ∇ R S τ ( w τ , t ) ⟩ + β L 2 η τ , t 2 2 . \begin{aligned}
\mathbb{E}[R_{S_i}(w_{\tau,t+1})-R_{S_i}(w_{\tau,t})\mid\mathcal{F}_{\tau,t}]
&\le-\eta_{\tau,t}\langle\nabla R_{S_i}(w_{\tau,t}),\nabla R_{S_\tau}(w_{\tau,t})\rangle\\
&\quad+\frac{\beta\eta_{\tau,t}^2}{2n}\sum_{j=1}^{n}\|\nabla f(w_{\tau,t};z_{\tau,j})\|^2\\
&\le-\eta_{\tau,t}\langle\nabla R_{S_i}(w_{\tau,t}),\nabla R_{S_\tau}(w_{\tau,t})\rangle+\frac{\beta L^2\eta_{\tau,t}^2}{2}.
\end{aligned} E [ R S i ( w τ , t + 1 ) − R S i ( w τ , t ) ∣ F τ , t ] ≤ − η τ , t ⟨ ∇ R S i ( w τ , t ) , ∇ R S τ ( w τ , t )⟩ + 2 n β η τ , t 2 j = 1 ∑ n ∥∇ f ( w τ , t ; z τ , j ) ∥ 2 ≤ − η τ , t ⟨ ∇ R S i ( w τ , t ) , ∇ R S τ ( w τ , t )⟩ + 2 β L 2 η τ , t 2 . where the last inequality uses the gradient bound implied by Assumption 1. Taking the full expectation and accumulating from t = 0 t=0 t = 0 N − 1 N-1 N − 1
E [ R S i ( w τ ) − R S i ( w τ − 1 ) ] ≤ − ∑ t = 0 N − 1 η τ , t E ⟨ ∇ R S i ( w τ , t ) , ∇ R S τ ( w τ , t ) ⟩ + β L 2 2 ∑ t = 0 N − 1 η τ , t 2 . \mathbb{E}[R_{S_i}(w_\tau)-R_{S_i}(w_{\tau-1})]
\le-\sum_{t=0}^{N-1}\eta_{\tau,t}\mathbb{E}\langle\nabla R_{S_i}(w_{\tau,t}),\nabla R_{S_\tau}(w_{\tau,t})\rangle+\frac{\beta L^2}{2}\sum_{t=0}^{N-1}\eta_{\tau,t}^2. E [ R S i ( w τ ) − R S i ( w τ − 1 )] ≤ − t = 0 ∑ N − 1 η τ , t E ⟨ ∇ R S i ( w τ , t ) , ∇ R S τ ( w τ , t )⟩ + 2 β L 2 t = 0 ∑ N − 1 η τ , t 2 . Then, summing over the subsequent tasks gives
ϵ ~ T , i ≤ − G T , i + β L 2 2 ∑ τ = i + 1 T ∑ t = 0 N − 1 η τ , t 2 . (28) \widetilde{\epsilon}_{T,i}\le-G_{T,i}+\frac{\beta L^2}{2}\sum_{\tau=i+1}^{T}\sum_{t=0}^{N-1}\eta_{\tau,t}^2. \tag*{(28)} ϵ T , i ≤ − G T , i + 2 β L 2 τ = i + 1 ∑ T t = 0 ∑ N − 1 η τ , t 2 . (28) We next discuss the different learning rates. Under constant learning rates η τ , t = c \eta_{\tau,t}=c η τ , t = c
ϵ ~ T , i ≤ − G T , i + β c 2 L 2 2 N ( T − i ) . \widetilde{\epsilon}_{T,i}\le-G_{T,i}+\frac{\beta c^2L^2}{2}N(T-i). ϵ T , i ≤ − G T , i + 2 β c 2 L 2 N ( T − i ) . Under intra-task decaying learning rates η τ , t = c / ( t + 1 ) \eta_{\tau,t}=c/(t+1) η τ , t = c / ( t + 1 )
ϵ ~ T , i ≤ − G T , i + β c 2 L 2 2 ( T − i ) ∑ t = 0 N − 1 1 ( t + 1 ) 2 ≤ − G T , i + β c 2 L 2 2 ( T − i ) ( 1 + ∫ 1 N d x x 2 ) = − G T , i + β c 2 L 2 2 ( 2 − 1 N ) ( T − i ) . \begin{aligned}
\widetilde{\epsilon}_{T,i}\le-G_{T,i}+\frac{\beta c^2L^2}{2}(T-i)\sum_{t=0}^{N-1}\frac{1}{(t+1)^2} \\
&\le-G_{T,i}+\frac{\beta c^2L^2}{2}(T-i)\left(1+\int_1^N\frac{dx}{x^2}\right) \\
&=-G_{T,i}+\frac{\beta c^2L^2}{2}\left(2-\frac{1}{N}\right)(T-i).
\end{aligned} ϵ T , i ≤ − G T , i + 2 β c 2 L 2 ( T − i ) t = 0 ∑ N − 1 ( t + 1 ) 2 1 ≤ − G T , i + 2 β c 2 L 2 ( T − i ) ( 1 + ∫ 1 N x 2 d x ) = − G T , i + 2 β c 2 L 2 ( 2 − N 1 ) ( T − i ) . Under continuously decaying learning rates η τ , t = c / ( ( τ − 1 ) N + t + 1 ) \eta_{\tau,t}=c/((\tau-1)N+t+1) η τ , t = c / (( τ − 1 ) N + t + 1 )
ϵ ~ T , i ≤ − G T , i + β c 2 L 2 2 ∑ k = i N + 1 T N 1 k 2 ≤ − G T , i + β c 2 L 2 2 ∫ i N T N d x x 2 = − G T , i + β c 2 L 2 2 ( 1 i N − 1 T N ) . \begin{aligned}
\widetilde{\epsilon}_{T,i}\le-G_{T,i}+\frac{\beta c^2L^2}{2}\sum_{k=iN+1}^{TN}\frac{1}{k^2} \\
&\le-G_{T,i}+\frac{\beta c^2L^2}{2}\int_{iN}^{TN}\frac{dx}{x^2} \\
&=-G_{T,i}+\frac{\beta c^2L^2}{2}\left(\frac{1}{iN}-\frac{1}{TN}\right).
\end{aligned} ϵ T , i ≤ − G T , i + 2 β c 2 L 2 k = i N + 1 ∑ T N k 2 1 ≤ − G T , i + 2 β c 2 L 2 ∫ i N T N x 2 d x = − G T , i + 2 β c 2 L 2 ( i N 1 − T N 1 ) . This completes the proof.
Appendix E: Forgetting in Expectation
Proof of Theorem 8
Proof. By (4) and Theorems 1 and 4,
F T ≤ 1 T − 1 ∑ i = 1 T − 1 ( ϵ i , i + ϵ T , i + ϵ ~ T , i ) . F_T\le\frac{1}{T-1}\sum_{i=1}^{T-1}(\epsilon_{i,i}+\epsilon_{T,i}+\widetilde{\epsilon}_{T,i}). F T ≤ T − 1 1 i = 1 ∑ T − 1 ( ϵ i , i + ϵ T , i + ϵ T , i ) . We apply the convex stability bounds and the EF bound under each learning-rate schedule. (a) under constant learning rates η τ , t = c \eta_{\tau,t}=c η τ , t = c
F T ≤ 1 T − 1 ∑ i = 1 T − 1 ( ϵ i , i + ϵ T , i + ϵ ~ T , i ) ≤ − 1 T − 1 ∑ i = 1 T − 1 G T , i + 1 T − 1 ∑ i = 1 T − 1 [ β c 2 L 2 2 N ( T − i ) + 4 c L 2 N n ] = − 1 T − 1 ∑ i = 1 T − 1 G T , i + 1 T − 1 [ β c 2 L 2 N T ( T − 1 ) 4 + 4 c L 2 N ( T − 1 ) n ] = − 1 T − 1 ∑ i = 1 T − 1 G T , i + β c 2 L 2 N T 4 + 4 c L 2 N n . \begin{aligned}
F_T\le\frac{1}{T-1}\sum_{i=1}^{T-1}(\epsilon_{i,i}+\epsilon_{T,i}+\widetilde{\epsilon}_{T,i}) \\
&\le-\frac{1}{T-1}\sum_{i=1}^{T-1}G_{T,i}
+\frac{1}{T-1}\sum_{i=1}^{T-1}\left[\frac{\beta c^2L^2}{2}N(T-i)+\frac{4cL^2N}{n}\right] \\
&=-\frac{1}{T-1}\sum_{i=1}^{T-1}G_{T,i}
+\frac{1}{T-1}\left[\frac{\beta c^2L^2NT(T-1)}{4}+\frac{4cL^2N(T-1)}{n}\right] \\
&=-\frac{1}{T-1}\sum_{i=1}^{T-1}G_{T,i}+\frac{\beta c^2L^2NT}{4}+\frac{4cL^2N}{n}.
\end{aligned} F T ≤ T − 1 1 i = 1 ∑ T − 1 ( ϵ i , i + ϵ T , i + ϵ T , i ) ≤ − T − 1 1 i = 1 ∑ T − 1 G T , i + T − 1 1 i = 1 ∑ T − 1 [ 2 β c 2 L 2 N ( T − i ) + n 4 c L 2 N ] = − T − 1 1 i = 1 ∑ T − 1 G T , i + T − 1 1 [ 4 β c 2 L 2 N T ( T − 1 ) + n 4 c L 2 N ( T − 1 ) ] = − T − 1 1 i = 1 ∑ T − 1 G T , i + 4 β c 2 L 2 N T + n 4 c L 2 N . (b) under intra-task decaying learning rates η τ , t = c t + 1 \eta_{\tau,t} = \frac{c}{t+1} η τ , t = t + 1 c
F T ≤ 1 T − 1 ∑ i = 1 T − 1 ( ϵ i , i + ϵ T , i + ϵ ~ T , i ) ≤ − 1 T − 1 ∑ i = 1 T − 1 G T , i + 1 T − 1 ∑ i = 1 T − 1 [ β c 2 L 2 2 ( 2 − 1 N ) × ( T − i ) + 4 c L 2 ln ( e N ) n ] = − 1 T − 1 ∑ i = 1 T − 1 G T , i + 1 T − 1 [ β c 2 L 2 2 ( 2 − 1 N ) T ( T − 1 ) 2 + 4 c L 2 ln ( e N ) ( T − 1 ) n ] = − 1 T − 1 ∑ i = 1 T − 1 G T , i + β c 2 L 2 T 4 ( 2 − 1 N ) + 4 c L 2 ln ( e N ) n . \begin{aligned}
F_T \le\frac{1}{T-1}\sum_{i=1}^{T-1}(\epsilon_{i,i}+\epsilon_{T,i}+\widetilde{\epsilon}_{T,i}) \\
&\le-\frac{1}{T-1}\sum_{i=1}^{T-1}\mathcal{G}_{T,i}+\frac{1}{T-1}\sum_{i=1}^{T-1}\left[\frac{\beta c^2L^2}{2}\left(2-\frac{1}{N}\right)\times(T-i)+\frac{4cL^2\ln(eN)}{n}\right] \\
&= -\frac{1}{T-1}\sum_{i=1}^{T-1}\mathcal{G}_{T,i}+\frac{1}{T-1}\left[\frac{\beta c^2L^2}{2}\left(2-\frac{1}{N}\right)\frac{T(T-1)}{2}+\frac{4cL^2\ln(eN)(T-1)}{n}\right] \\
&= -\frac{1}{T-1}\sum_{i=1}^{T-1}\mathcal{G}_{T,i}+\frac{\beta c^2L^2T}{4}\left(2-\frac{1}{N}\right)+\frac{4cL^2\ln(eN)}{n}.
\end{aligned} F T ≤ T − 1 1 i = 1 ∑ T − 1 ( ϵ i , i + ϵ T , i + ϵ T , i ) ≤ − T − 1 1 i = 1 ∑ T − 1 G T , i + T − 1 1 i = 1 ∑ T − 1 [ 2 β c 2 L 2 ( 2 − N 1 ) × ( T − i ) + n 4 c L 2 ln ( e N ) ] = − T − 1 1 i = 1 ∑ T − 1 G T , i + T − 1 1 [ 2 β c 2 L 2 ( 2 − N 1 ) 2 T ( T − 1 ) + n 4 c L 2 ln ( e N ) ( T − 1 ) ] = − T − 1 1 i = 1 ∑ T − 1 G T , i + 4 β c 2 L 2 T ( 2 − N 1 ) + n 4 c L 2 ln ( e N ) . For the continuous schedule, we use the finite harmonic-sum estimate
∑ i = 1 T − 1 1 i − T − 1 T ≤ 1 + ∫ 1 T − 1 d u u − T − 1 T = ln ( T − 1 ) + 1 T . (29) \begin{aligned}
\sum_{i=1}^{T-1}\frac{1}{i}-\frac{T-1}{T}\le1+\int_1^{T-1}\frac{du}{u}-\frac{T-1}{T} \\
&= \ln(T-1)+\frac{1}{T}. \tag*{(29)}
\end{aligned} i = 1 ∑ T − 1 i 1 − T T − 1 ≤ 1 + ∫ 1 T − 1 u d u − T T − 1 = ln ( T − 1 ) + T 1 . (29) This also holds for T = 2 T=2 T = 2
(c) under continuously decaying learning rates η τ , t = c ( τ − 1 ) N + t + 1 \eta_{\tau,t}=\frac{c}{(\tau-1)N+t+1} η τ , t = ( τ − 1 ) N + t + 1 c
F T ≤ 1 T − 1 ∑ i = 1 T − 1 ( ϵ i , i + ϵ T , i + ϵ ~ T , i ) ≤ − 1 T − 1 ∑ i = 1 T − 1 G T , i + 1 T − 1 [ ∑ i = 1 T − 1 β c 2 L 2 2 N ( 1 i − 1 T ) + 4 c L 2 ln ( e N ) n + ∑ i = 2 T − 1 4 c L 2 n ln ( 1 + 1 i − 1 ) ] = − 1 T − 1 ∑ i = 1 T − 1 G T , i + 1 T − 1 [ β c 2 L 2 2 N ( ∑ i = 1 T − 1 1 i − T − 1 T ) + 4 c L 2 ln ( e N ) n + 4 c L 2 n ln ( T − 1 ) ] ≤ − 1 T − 1 ∑ i = 1 T − 1 G T , i + β c 2 L 2 2 N ( T − 1 ) ( ln ( T − 1 ) + 1 T ) + 4 c L 2 n ( T − 1 ) ln ( e N ( T − 1 ) ) . \begin{aligned}
F_T
\le\frac{1}{T-1}\sum_{i=1}^{T-1}(\epsilon_{i,i}+\epsilon_{T,i}+\widetilde{\epsilon}_{T,i}) \\
&\le-\frac{1}{T-1}\sum_{i=1}^{T-1}\mathcal{G}_{T,i}+\frac{1}{T-1}\left[\sum_{i=1}^{T-1}\frac{\beta c^2L^2}{2N}\left(\frac{1}{i}-\frac{1}{T}\right)+\frac{4cL^2\ln(eN)}{n}+\sum_{i=2}^{T-1}\frac{4cL^2}{n}\ln\left(1+\frac{1}{i-1}\right)\right] \\
&= -\frac{1}{T-1}\sum_{i=1}^{T-1}\mathcal{G}_{T,i}+\frac{1}{T-1}\left[\frac{\beta c^2L^2}{2N}\left(\sum_{i=1}^{T-1}\frac{1}{i}-\frac{T-1}{T}\right)+\frac{4cL^2\ln(eN)}{n}+\frac{4cL^2}{n}\ln(T-1)\right] \\
&\le-\frac{1}{T-1}\sum_{i=1}^{T-1}\mathcal{G}_{T,i}+\frac{\beta c^2L^2}{2N(T-1)}\left(\ln(T-1)+\frac{1}{T}\right)+\frac{4cL^2}{n(T-1)}\ln\bigl(eN(T-1)\bigr).
\end{aligned} F T ≤ T − 1 1 i = 1 ∑ T − 1 ( ϵ i , i + ϵ T , i + ϵ T , i ) ≤ − T − 1 1 i = 1 ∑ T − 1 G T , i + T − 1 1 [ i = 1 ∑ T − 1 2 N β c 2 L 2 ( i 1 − T 1 ) + n 4 c L 2 ln ( e N ) + i = 2 ∑ T − 1 n 4 c L 2 ln ( 1 + i − 1 1 ) ] = − T − 1 1 i = 1 ∑ T − 1 G T , i + T − 1 1 [ 2 N β c 2 L 2 ( i = 1 ∑ T − 1 i 1 − T T − 1 ) + n 4 c L 2 ln ( e N ) + n 4 c L 2 ln ( T − 1 ) ] ≤ − T − 1 1 i = 1 ∑ T − 1 G T , i + 2 N ( T − 1 ) β c 2 L 2 ( ln ( T − 1 ) + T 1 ) + n ( T − 1 ) 4 c L 2 ln ( e N ( T − 1 ) ) . Here, the generalization terms use ∑ t = 1 N 1 / t ≤ ln ( e N ) \sum_{t=1}^{N}1/t\le\ln(eN) ∑ t = 1 N 1/ t ≤ ln ( e N )
∑ i = 2 T − 1 ln ( i i − 1 ) = ln ( T − 1 ) . \sum_{i=2}^{T-1}\ln\left(\frac{i}{i-1}\right)=\ln(T-1). i = 2 ∑ T − 1 ln ( i − 1 i ) = ln ( T − 1 ) . The last inequality follows from Equation (29) . When T = 2 T=2 T = 2
Proof of Theorem 9
Proof. By Equation (4) and the generalization bounds,
F T ≤ 1 T − 1 ∑ i = 1 T − 1 ( ϵ i , i + ϵ T , i + ϵ ~ T , i ) . F_T\le\frac{1}{T-1}\sum_{i=1}^{T-1}(\epsilon_{i,i}+\epsilon_{T,i}+\widetilde{\epsilon}_{T,i}). F T ≤ T − 1 1 i = 1 ∑ T − 1 ( ϵ i , i + ϵ T , i + ϵ T , i ) . We evaluate these three contributions under each learning-rate schedule.
(a) Under intra-task decaying learning rates η τ , t = c t + 1 \eta_{\tau,t}=\frac{c}{t+1} η τ , t = t + 1 c
1 T − 1 ∑ i = 1 T − 1 ϵ ~ T , i ≤ − 1 T − 1 ∑ i = 1 T − 1 G T , i + β c 2 L 2 2 ( T − 1 ) ( 2 − 1 N ) ∑ i = 1 T − 1 ( T − i ) = − 1 T − 1 ∑ i = 1 T − 1 G T , i + β c 2 L 2 T 4 ( 2 − 1 N ) . \begin{aligned}
\frac{1}{T-1}\sum_{i=1}^{T-1}\widetilde{\epsilon}_{T,i}
\le-\frac{1}{T-1}\sum_{i=1}^{T-1}\mathcal{G}_{T,i}+\frac{\beta c^2L^2}{2(T-1)}\left(2-\frac{1}{N}\right)\sum_{i=1}^{T-1}(T-i) \\
&=-\frac{1}{T-1}\sum_{i=1}^{T-1}\mathcal{G}_{T,i}+\frac{\beta c^2L^2T}{4}\left(2-\frac{1}{N}\right).
\end{aligned} T − 1 1 i = 1 ∑ T − 1 ϵ T , i ≤ − T − 1 1 i = 1 ∑ T − 1 G T , i + 2 ( T − 1 ) β c 2 L 2 ( 2 − N 1 ) i = 1 ∑ T − 1 ( T − i ) = − T − 1 1 i = 1 ∑ T − 1 G T , i + 4 β c 2 L 2 T ( 2 − N 1 ) . Under the condition 2 c L 2 ( e N ) c β ( T − 1 ) < N 2cL^2(eN)^{c\beta(T-1)}<N 2 c L 2 ( e N ) c β ( T − 1 ) < N i ∈ [ T − 1 ] i\in[T-1] i ∈ [ T − 1 ]
2 c L 2 ≤ 2 c L 2 ( e N ) c β ( T − i ) ≤ 2 c L 2 ( e N ) c β ( T − 1 ) < N . 2cL^2\le2cL^2(eN)^{c\beta(T-i)}\le2cL^2(eN)^{c\beta(T-1)}<N. 2 c L 2 ≤ 2 c L 2 ( e N ) c β ( T − i ) ≤ 2 c L 2 ( e N ) c β ( T − 1 ) < N . Thus, the interior expressions in Theorems 3 and 6 apply to all historical tasks. The IGG bound is the same for every task, so
1 T − 1 ∑ i = 1 T − 1 ϵ i , i ≤ c β + 1 n c β ( 2 c L 2 ) 1 c β + 1 N c β c β + 1 − 2 L 2 β n . \frac{1}{T-1}\sum_{i=1}^{T-1}\epsilon_{i,i}\le\frac{c\beta+1}{nc\beta}(2cL^2)^{\frac{1}{c\beta+1}}N^{\frac{c\beta}{c\beta+1}}-\frac{2L^2}{\beta n}. T − 1 1 i = 1 ∑ T − 1 ϵ i , i ≤ n c β c β + 1 ( 2 c L 2 ) c β + 1 1 N c β + 1 c β − β n 2 L 2 . For CGG, setting j = T − i j=T-i j = T − i
∑ i = 1 T − 1 ϵ T , i ≤ c β + 1 n c β ( 2 c L 2 ) 1 c β + 1 N c β c β + 1 ∑ j = 1 T − 1 ( e N ) c β j c β + 1 − 2 L 2 β n ∑ j = 1 T − 1 ( e N ) c β j . \sum_{i=1}^{T-1}\epsilon_{T,i}\le\frac{c\beta+1}{nc\beta}(2cL^2)^{\frac{1}{c\beta+1}}N^{\frac{c\beta}{c\beta+1}}\sum_{j=1}^{T-1}(eN)^{\frac{c\beta j}{c\beta+1}}-\frac{2L^2}{\beta n}\sum_{j=1}^{T-1}(eN)^{c\beta j}. i = 1 ∑ T − 1 ϵ T , i ≤ n c β c β + 1 ( 2 c L 2 ) c β + 1 1 N c β + 1 c β j = 1 ∑ T − 1 ( e N ) c β + 1 c β j − β n 2 L 2 j = 1 ∑ T − 1 ( e N ) c β j . The two geometric sums are
∑ j = 1 T − 1 ( e N ) c β j c β + 1 = ( e N ) c β ( T − 1 ) c β + 1 − 1 1 − ( e N ) − c β c β + 1 , \sum_{j=1}^{T-1}(eN)^{\frac{c\beta j}{c\beta+1}}=\frac{(eN)^{\frac{c\beta(T-1)}{c\beta+1}}-1}{1-(eN)^{-\frac{c\beta}{c\beta+1}}}, j = 1 ∑ T − 1 ( e N ) c β + 1 c β j = 1 − ( e N ) − c β + 1 c β ( e N ) c β + 1 c β ( T − 1 ) − 1 , ∑ j = 1 T − 1 ( e N ) c β j = ( e N ) c β ( T − 1 ) − 1 1 − ( e N ) − c β . \sum_{j=1}^{T-1}(eN)^{c\beta j}=\frac{(eN)^{c\beta(T-1)}-1}{1-(eN)^{-c\beta}}. j = 1 ∑ T − 1 ( e N ) c β j = 1 − ( e N ) − c β ( e N ) c β ( T − 1 ) − 1 . Both denominators are positive since e N > 1 eN>1 e N > 1 c β > 0 c\beta>0 c β > 0 T − 1 T-1 T − 1 (9) . When T = 2 T=2 T = 2
(b) Under continuously decaying learning rates η τ , t = c ( τ − 1 ) N + t + 1 \eta_{\tau,t}=\frac{c}{(\tau-1)N+t+1} η τ , t = ( τ − 1 ) N + t + 1 c t 0 ∈ { 0 , … , N } t_0 \in\{0,\ldots,N\} t 0 ∈ { 0 , … , N }
ϵ T , i ≤ 1 n [ t 0 + 2 c L 2 ( T N ) c β ∑ k = t 0 + 1 N 1 ( ( i − 1 ) N + k ) c β + 1 ] . \epsilon_{T,i} \le\frac{1}{n}\left[t_0+2cL^2(TN)^{c\beta}\sum_{k=t_0+1}^{N}\frac{1}{((i-1)N+k)^{c\beta+1}}\right]. ϵ T , i ≤ n 1 [ t 0 + 2 c L 2 ( T N ) c β k = t 0 + 1 ∑ N (( i − 1 ) N + k ) c β + 1 1 ] . The summand is nonnegative and nonincreasing in k k k (17) and substituting v = ( i − 1 ) N + u v=(i-1)N+u v = ( i − 1 ) N + u i ∈ [ T − 1 ] i\in[T-1] i ∈ [ T − 1 ]
ϵ T , i ≤ 1 n ∫ ( i − 1 ) N i N min { 1 , 2 c L 2 ( T N ) c β v c β + 1 } d v . \epsilon_{T,i}\le\frac{1}{n}\int_{(i-1)N}^{iN}\min\left\{1,\frac{2cL^2(TN)^{c\beta}}{v^{c\beta+1}}\right\}\,dv. ϵ T , i ≤ n 1 ∫ ( i − 1 ) N i N min { 1 , v c β + 1 2 c L 2 ( T N ) c β } d v . The integrand is the same for all tasks. Summing the integrals over their adjacent intervals yields
∑ i = 1 T − 1 ϵ T , i ≤ 1 n ∫ 0 ( T − 1 ) N min { 1 , 2 c L 2 ( T N ) c β v c β + 1 } d v . \sum_{i=1}^{T-1}\epsilon_{T,i}\le\frac{1}{n}\int_0^{(T-1)N}\min\left\{1,\frac{2cL^2(TN)^{c\beta}}{v^{c\beta+1}}\right\}\,dv. i = 1 ∑ T − 1 ϵ T , i ≤ n 1 ∫ 0 ( T − 1 ) N min { 1 , v c β + 1 2 c L 2 ( T N ) c β } d v . The two arguments of the minimum are equal at
v ^ 0 = ( 2 c L 2 ) 1 c β + 1 ( T N ) c β c β + 1 . \hat v_0=(2cL^2)^{\frac{1}{c\beta+1}}(TN)^{\frac{c\beta}{c\beta+1}}. v ^ 0 = ( 2 c L 2 ) c β + 1 1 ( T N ) c β + 1 c β . If 2 c L 2 T c β < N ( T − 1 ) c β + 1 2cL^2T^{c\beta}<N(T-1)^{c\beta+1} 2 c L 2 T c β < N ( T − 1 ) c β + 1 v ^ 0 < ( T − 1 ) N \hat v_0<(T-1)N v ^ 0 < ( T − 1 ) N v ^ 0 \hat v_0 v ^ 0
∑ i = 1 T − 1 ϵ T , i ≤ v ^ 0 n + 2 c L 2 ( T N ) c β n ∫ v ^ 0 ( T − 1 ) N v − c β − 1 d v = v ^ 0 n + 2 L 2 ( T N ) c β β n [ v ^ 0 − c β − ( ( T − 1 ) N ) − c β ] = c β + 1 n c β ( 2 c L 2 ) 1 c β + 1 ( T N ) c β c β + 1 − 2 L 2 β n ( T T − 1 ) c β . \begin{aligned}
\sum_{i=1}^{T-1}\epsilon_{T,i}\le\frac{\hat v_0}{n}+\frac{2cL^2(TN)^{c\beta}}{n}\int_{\hat v_0}^{(T-1)N}v^{-c\beta-1}\,dv \\
&=\frac{\hat v_0}{n}+\frac{2L^2(TN)^{c\beta}}{\beta n}\left[\hat v_0^{-c\beta}-((T-1)N)^{-c\beta}\right] \\
&=\frac{c\beta+1}{n c\beta}(2cL^2)^{\frac{1}{c\beta+1}}(TN)^{\frac{c\beta}{c\beta+1}}-\frac{2L^2}{\beta n}\left(\frac{T}{T-1}\right)^{c\beta}.
\end{aligned} i = 1 ∑ T − 1 ϵ T , i ≤ n v ^ 0 + n 2 c L 2 ( T N ) c β ∫ v ^ 0 ( T − 1 ) N v − c β − 1 d v = n v ^ 0 + β n 2 L 2 ( T N ) c β [ v ^ 0 − c β − (( T − 1 ) N ) − c β ] = n c β c β + 1 ( 2 c L 2 ) c β + 1 1 ( T N ) c β + 1 c β − β n 2 L 2 ( T − 1 T ) c β . If 2 c L 2 T c β ≥ N ( T − 1 ) c β + 1 2cL^2T^{c\beta}\ge N(T-1)^{c\beta+1} 2 c L 2 T c β ≥ N ( T − 1 ) c β + 1 v ^ 0 ≥ ( T − 1 ) N \hat v_0\ge(T-1)N v ^ 0 ≥ ( T − 1 ) N 1 1 1
∑ i = 1 T − 1 ϵ T , i ≤ ( T − 1 ) N n . \sum_{i=1}^{T-1}\epsilon_{T,i}\le\frac{(T-1)N}{n}. i = 1 ∑ T − 1 ϵ T , i ≤ n ( T − 1 ) N . For IGG, the same integer-cutoff comparison gives
ϵ 1 , 1 ≤ 1 n ∫ 0 N min { 1 , 2 c L 2 N c β u c β + 1 } d u . \epsilon_{1,1}\le\frac{1}{n}\int_0^N\min\left\{1,\frac{2cL^2Nc\beta}{u^{c\beta+1}}\right\}\,du. ϵ 1 , 1 ≤ n 1 ∫ 0 N min { 1 , u c β + 1 2 c L 2 N c β } d u . If 2 c L 2 < N 2cL^2<N 2 c L 2 < N u ^ 0 = ( 2 c L 2 ) 1 / ( c β + 1 ) N c β / ( c β + 1 ) < N \hat u_0=(2cL^2)^{1/(c\beta+1)}N^{c\beta/(c\beta+1)}<N u ^ 0 = ( 2 c L 2 ) 1/ ( c β + 1 ) N c β / ( c β + 1 ) < N
ϵ 1 , 1 ≤ u ^ 0 n + 2 c L 2 N c β n ∫ u ^ 0 N u − c β − 1 d u = c β + 1 n c β ( 2 c L 2 ) 1 c β + 1 N c β c β + 1 − 2 L 2 β n . \begin{aligned}
\epsilon_{1,1}\le\frac{\hat u_0}{n}+\frac{2cL^2Nc\beta}{n}\int_{\hat u_0}^{N}u^{-c\beta-1}\,du \\
&=\frac{c\beta+1}{nc\beta}(2cL^2)^{\frac{1}{c\beta+1}}N^{\frac{c\beta}{c\beta+1}}-\frac{2L^2}{\beta n}.
\end{aligned} ϵ 1 , 1 ≤ n u ^ 0 + n 2 c L 2 N c β ∫ u ^ 0 N u − c β − 1 d u = n c β c β + 1 ( 2 c L 2 ) c β + 1 1 N c β + 1 c β − β n 2 L 2 . If 2 c L 2 ≥ N 2cL^2\ge N 2 c L 2 ≥ N 1 1 1 [ 0 , N ] [0,N] [ 0 , N ] ϵ 1 , 1 ≤ N / n \epsilon_{1,1}\le N/n ϵ 1 , 1 ≤ N / n i ≥ 2 i\ge2 i ≥ 2 t 0 = 0 t_0=0 t 0 = 0 (20) gives
ϵ i , i ≤ 2 L 2 β n [ ( 1 + 1 i − 1 ) c β − 1 ] . \epsilon_{i,i}\le\frac{2L^2}{\beta n}\left[\left(1+\frac{1}{i-1}\right)^{c\beta}-1\right]. ϵ i , i ≤ β n 2 L 2 [ ( 1 + i − 1 1 ) c β − 1 ] . For 0 ≤ x ≤ ln 2 0\le x\le\ln2 0 ≤ x ≤ ln 2 e c β x e^{c\beta x} e c β x
e c β x − 1 ≤ 2 c β − 1 ln 2 x . e^{c\beta x}-1\le\frac{2^{c\beta}-1}{\ln2}x. e c β x − 1 ≤ ln 2 2 c β − 1 x . Taking x = ln ( 1 + 1 / k ) x=\ln(1+1/k) x = ln ( 1 + 1/ k ) k = 1 , … , T − 2 k=1,\ldots,T-2 k = 1 , … , T − 2
∑ i = 2 T − 1 ϵ i , i ≤ 2 L 2 β n ∑ k = 1 T − 2 [ ( 1 + 1 k ) c β − 1 ] ≤ 2 L 2 ( 2 c β − 1 ) β n ln 2 ∑ k = 1 T − 2 ln ( k + 1 k ) = 2 L 2 ( 2 c β − 1 ) β n ln 2 ln ( T − 1 ) . \begin{aligned}
\sum_{i=2}^{T-1}\epsilon_{i,i}\le\frac{2L^2}{\beta n}\sum_{k=1}^{T-2}\left[\left(1+\frac{1}{k}\right)^{c\beta}-1\right] \\
&\le\frac{2L^2(2^{c\beta}-1)}{\beta n\ln2}\sum_{k=1}^{T-2}\ln\left(\frac{k+1}{k}\right) \\
&=\frac{2L^2(2^{c\beta}-1)}{\beta n\ln2}\ln(T-1).
\end{aligned} i = 2 ∑ T − 1 ϵ i , i ≤ β n 2 L 2 k = 1 ∑ T − 2 [ ( 1 + k 1 ) c β − 1 ] ≤ β n ln 2 2 L 2 ( 2 c β − 1 ) k = 1 ∑ T − 2 ln ( k k + 1 ) = β n ln 2 2 L 2 ( 2 c β − 1 ) ln ( T − 1 ) . For T = 2 T=2 T = 2 2 c L 2 < N 2cL^2<N 2 c L 2 < N
∑ i = 1 T − 1 ϵ i , i ≤ c β + 1 n c β ( 2 c L 2 ) 1 c β + 1 N c β c β + 1 + 2 L 2 β n [ 2 c β − 1 ln 2 ln ( T − 1 ) − 1 ] . \sum_{i=1}^{T-1}\epsilon_{i,i}\le\frac{c\beta+1}{nc\beta}(2cL^2)^{\frac{1}{c\beta+1}}N^{\frac{c\beta}{c\beta+1}}+\frac{2L^2}{\beta n}\left[\frac{2^{c\beta}-1}{\ln2}\ln(T-1)-1\right]. i = 1 ∑ T − 1 ϵ i , i ≤ n c β c β + 1 ( 2 c L 2 ) c β + 1 1 N c β + 1 c β + β n 2 L 2 [ ln 2 2 c β − 1 ln ( T − 1 ) − 1 ] . When 2 c L 2 ≥ N 2cL^2\ge N 2 c L 2 ≥ N
∑ i = 1 T − 1 ϵ i , i ≤ N n + 2 L 2 β n 2 c β − 1 ln 2 ln ( T − 1 ) . \sum_{i=1}^{T-1}\epsilon_{i,i}\le\frac{N}{n}+\frac{2L^2}{\beta n}\frac{2^{c\beta}-1}{\ln2}\ln(T-1). i = 1 ∑ T − 1 ϵ i , i ≤ n N + β n 2 L 2 ln 2 2 c β − 1 ln ( T − 1 ) . Finally, the finite harmonic sum satisfies
∑ i = 1 T − 1 1 i − T − 1 T ≤ 1 + ∫ 1 T − 1 d u u − T − 1 T = ln ( T − 1 ) + 1 T . \begin{aligned}
\sum_{i=1}^{T-1}\frac{1}{i}-\frac{T-1}{T}\le1+\int_1^{T-1}\frac{du}{u}-\frac{T-1}{T} \\
&=\ln(T-1)+\frac{1}{T}.
\end{aligned} i = 1 ∑ T − 1 i 1 − T T − 1 ≤ 1 + ∫ 1 T − 1 u d u − T T − 1 = ln ( T − 1 ) + T 1 . Combining this inequality with Theorem 7 gives
1 T − 1 ∑ i = 1 T − 1 ϵ ~ T , i ≤ − 1 T − 1 ∑ i = 1 T − 1 G T , i + β c 2 L 2 2 N ( T − 1 ) ( ln ( T − 1 ) + 1 T ) . \begin{aligned}
\frac{1}{T-1}\sum_{i=1}^{T-1}\widetilde{\epsilon}_{T,i} \\
&\le-\frac{1}{T-1}\sum_{i=1}^{T-1}G_{T,i}+\frac{\beta c^2L^2}{2N(T-1)}\left(\ln(T-1)+\frac{1}{T}\right).
\end{aligned} T − 1 1 i = 1 ∑ T − 1 ϵ T , i ≤ − T − 1 1 i = 1 ∑ T − 1 G T , i + 2 N ( T − 1 ) β c 2 L 2 ( ln ( T − 1 ) + T 1 ) . The two IGG cases and the two cumulative CGG cases give the four combinations in Equation (10) after division by T − 1 T-1 T − 1
1 T − 1 ( N n + ( T − 1 ) N n ) = N T n ( T − 1 ) . \frac{1}{T-1}\left(\frac{N}{n}+\frac{(T-1)N}{n}\right)=\frac{NT}{n(T-1)}. T − 1 1 ( n N + n ( T − 1 ) N ) = n ( T − 1 ) N T . At 2 c L 2 = N 2cL^2=N 2 c L 2 = N N / n N/n N / n 2 c L 2 T c β = N ( T − 1 ) c β + 1 2cL^2T^{c\beta}=N(T-1)^{c\beta+1} 2 c L 2 T c β = N ( T − 1 ) c β + 1 ( T − 1 ) N / n (T-1)N/n ( T − 1 ) N / n T = 2 T=2 T = 2
Appendix F: Experiments on Split MiniImageNet with ResNet-18
Experimental setting on Split MiniImageNet. The Split MiniImageNet dataset is constructed by dividing the 100 classes of MiniImageNet into 20 sequential tasks, each containing 5 classes. We use a ResNet-18 backbone, following a similar architecture to that used by Lopez-Paz and Ranzato [35 ] . We vary the number of epochs per task in { 10 , 25 , 50 , 75 , 100 } \{10,25,50,75,100\} { 10 , 25 , 50 , 75 , 100 } { 10 − 4 , 5 × 10 − 4 , 10 − 3 , 5 × 10 − 3 , 10 − 2 , 5 × 10 − 2 , 10 − 1 , 5 × 10 − 1 } \{10^{-4},5 \times10^{-4},10^{-3},5 \times10^{-3},10^{-2},5 \times10^{-2},10^{-1},5 \times10^{-1}\} { 1 0 − 4 , 5 × 1 0 − 4 , 1 0 − 3 , 5 × 1 0 − 3 , 1 0 − 2 , 5 × 1 0 − 2 , 1 0 − 1 , 5 × 1 0 − 1 } { 500 , 1000 , 1500 , 2000 } \{500,1000,1500,2000\} { 500 , 1000 , 1500 , 2000 } c = 0.1 c=0.1 c = 0.1 c = 0.1 c=0.1 c = 0.1 N = 1600 N=1600 N = 1600
Figure 5. IGG, CGG, EF, F T F_T F T The top row shows results for different initial learning rates c c c
Measurement of cumulative gradient alignment. For each task, we construct a measurement buffer by uniformly sampling batches without replacement from its fixed training-set evaluation partition. We retain four batches on Split CIFAR-100 and two batches on Split MiniImageNet, with up to 64 samples per batch, giving maximum buffer sizes of 256 and 128 samples per task, respectively. At step t t t τ \tau τ g τ , t g_{\tau,t} g τ , t i < τ i<\tau i < τ g ^ i , τ , t \widehat{g}_{i,\tau,t} g i , τ , t g ^ i , τ , t \widehat{g}_{i,\tau,t} g i , τ , t g τ , t g_{\tau,t} g τ , t w τ , t w_{\tau,t} w τ , t
G ^ T , i = ∑ τ = i + 1 T ∑ t = 0 N − 1 η τ , t ⟨ g ^ i , τ , t , g τ , t ⟩ . \widehat{G}_{T,i}=\sum_{\tau=i+1}^{T}\sum_{t=0}^{N-1}\eta_{\tau,t}\langle\widehat{g}_{i,\tau,t},g_{\tau,t}\rangle. G T , i = τ = i + 1 ∑ T t = 0 ∑ N − 1 η τ , t ⟨ g i , τ , t , g τ , t ⟩ . Each inner product is multiplied by the learning rate used for that update and accumulated over all subsequent updates, without normalization by gradient norms, the number of updates, or the number of tasks. The buffers are used exclusively for measurement. We plot − G ^ T , i -\widehat{G}_{T,i} − G T , i i i i
Figure 6. EF and CGA under different learning-rate schedules on Split MiniImageNet. C, ID, and CD denote constant, intra-task decaying, and continuously decaying learning rates, respectively. Curves show averages over three seeds, and shaded regions indicate one standard deviation.
Figure 7. IGG and CGG with different numbers of training samples per task on Split MiniImageNet.
Figure 8. ACC and BWT for original CL, GEM, and A-GEM under different learning-rate schedules on Split MiniImageNet. Higher ACC indicates better predictive performance, while higher BWT indicates less forgetting.
