Year: 2021

Abstract:
One of the objectives of continual learning is to prevent catastrophic forgetting in learning multiple tasks sequentially. The memory based continual learning stores a small subset of the data for previous tasks and applies various methods such as quadratic programming and sample selection. Some memory-based approaches are formulated as a constrained optimization problem and rephrase constraints on the objective for memory as the inequalities on gradients. However, there have been little theoretical results on the convergence of continual learning. In this paper, we propose a theoretical convergence analysis of memory-based continual learning with stochastic gradient descent. The proposed method called nonconvex continual learning (NCCL) adapts the learning rates of both previous and current tasks with the gradients. The proposed method can achieve the same convergence rate as the SGD method for a single task when the catastrophic forgetting term which we define in the paper is suppressed at each iteration. It is also shown that memory-based approaches inherently overfit to memory, which degrades the performance on previously learned tasks. Experiments show that the proposed algorithm improves the performance of continual learning over existing methods for several image classification tasks.

heading: 1 INTRODUCTION
text: Learning new tasks without forgetting previously learned tasks is a key aspect of artificial intelligence to be as versatile as humans. Unlike the conventional deep learning that observes tasks from an i.i.d. distribution, continual learning train sequentially a model on a non-stationary stream of data (Ring, 1995; Thrun, 1994). The continual learning AI systems struggle with catastrophic forgetting when the data access of previously learned tasks is restricted (French & Chater, 2002). To overcome catastrophic forgetting, continual learning algorithms introduce novel methods such as a replay memory to store and replay the previously learned examples (Lopez-Paz & Ranzato, 2017; Aljundi et al., 2019; Chaudhry et al., 2019a), regularization methods that penalize neural networks (Kirkpatrick et al., 2017; Zenke et al., 2017), Bayesian methods that utilize the uncertainty of parameters or data points (Nguyen et al., 2018; Ebrahimi et al., 2020), and other recent approaches (Yoon et al., 2018; Lee et al., 2019). In this paper, we focus on the online continual learning with replay memory. The learner stores a small subset of the data for previous tasks into a memory and utilizes the memory by replaying samples to keep the model staying in a feasible region corresponding to moderate suboptimal region. Gradient episodic memory (GEM) (Lopez-Paz & Ranzato, 2017) first formulated the replay based continual learning as a constrained optimization problem. This formulation rephrases the constraints on objectives for previous tasks as the inequalities based on the inner product of loss gradient vectors for previous tasks and a current task. However, the theoretical convergence analysis of the performance of previously learned tasks, which implies a measure of catastrophic forgetting, has not been rigorously studied in the literature. Without convergence analysis, this intuitive reformulation of constrained optimization does not provide theoretical guarantee to prevent catastrophic forgetting.
Nonconvex finite-sum optimization problem offers a solution to analyze catastrophic forgetting by measuring the convergence of previously learned tasks, which is related to the performance. Most deep learning problems are defined as nonconvex optimization, and the target objective is composed of the sum of objectives for each data point. Now we express our continual learning problem of the
form
min x∈Rd
f(x) = 1
n n∑ i=1 fi(x), (1)
where we assume that each objective fi(x) with a model x and a data point i is nonconvex with Lipschitz gradient. Here, we expect that a stochastic gradient descent based algorithm reaches a stationary point instead of the global minimum in the nonconvex optimization. This generic form is well studied to demonstrate the convergence and complexity of stochastic gradient methods for a nonconvex setting (Zhou & Gu, 2019; Lei et al., 2017; Reddi et al., 2016a; Zaheer et al., 2018). Unlike the convex case, the convergence is generally measured by the expectation of the squared norm of the gradient E‖∇f(x)‖2. The theoretical complexity is derived from the -accurate solution, which is also known as a stationary point with E‖∇f(x)‖2 ≤ . Suppose we divide the entire sum of objectives into two terms for previous tasks and current tasks, and measure the convergence on each term. Then, we can observe the transition of convergences on the previous and current tasks respectively while learning sequentially from a data stream. We consider this transition of convergence on the previous task as catastrophic forgetting if E‖∇fP (x)‖2 with the set of data points from previous tasks P increases over iterations.
In this work, we formulate continual learning problem as a nonconvex finite-sum optimization with stochastic gradient descent algorithm that updates both previously learned tasks from replay memory and the current task simultaneously, and present a theoretical convergence analysis of continual learning problems by leveraging the replay-based update method. This extends the continual learning algorithm such as ER-Reservoir (experience replay with reservoir sampling) with fixed and same learning rates on both two tasks to our adaptive method which controls the relative importance between tasks at each step with theoretical guarantee. In addition, the replay-based continual learning has the critical limitation of overfitting to memory, which also degrades the performance of previously learned tasks like catastrophic forgetting by interference. It is known that choosing the perfect memory for continual learning to prevent catastrophic forgetting is an NP-hard problem by (Knoblauch et al., 2020). We present that the inductive bias by replay memory, which prevents perfect continual learning is inevitable in view of optimization.

heading: 2 BACKGROUNDS
text: The continual learning algorithm with a replay memory with size m cannot access the whole dataset of the previously learned tasks with nf samples, but uses limited samples in the memory when a learner trains on the current task. This limited access does not guarantee to completely prevent catastrophic forgetting, and causes the overfitting problem with the biased gradient on a memory. In Section 3, we provide the convergence analysis of the previously learned tasks f(x), which are vulnerable to catastrophic forgetting.
As we denote fi(x) as the component, which indicates the loss of sample i from the previously learned tasks with the model parameter x, we define ∇fi(x) as its gradient. We use It, Jt as the mini-batch of samples at iteration t and denote the mini-batch size |It| and |Jt| as bf , bg throughout the paper. We also note that gj(x), which denotes the loss for the current task and will be defined in Section 3.1, satisfies the above and following assumptions.
To formulate the convergence over iterations, we introduce the Incremental First-order Oracle (IFO) framework (Ghadimi & Lan, 2013), which is defined as a unit of cost by sampling the pair (∇fi(x), fi(x)). For example, a stochastic gradient descent algorithm requires the cost as much as the batch size bt at each step, and the total cost is the sum of batch sizes ∑T t=1 bt. Let T ( ) be the minimum number of iterations to guarantee -accurate solutions. Then the average bound of IFO complexity is less than or equal to ∑T ( ) t=1 bt.
To analyze the convergence and compute the IFO complexity, we define the supremum of loss gap between a local optimal point x0 and the global optimum x∗ as
∆f = sup x0 f(x0)− f(x∗). (2)
Suppose that sup f(x0) is same with f(x∗), then we have ∆f = 0, which might be much smaller than the loss gap of general SGD. Without the continual learning scenario, a general nonconvex SGD
updates the parameters from an randomly initialized point, which is highly likely to have the large loss f(x0). Then, ∆f > 0 is the key constant to determine the IFO complexity for convergence as ∆f is in the numerator of Equation 11. However, a continual learning algorithm has already converged to a local optimal point x0 for the previous task f(x) and might get a much smaller ∆f than the general SGD. It means that ∆f for nonconvex continual learining in Equation 11 dose not have a large impact on the IFO complexity. To generalize the theoretical result, we define the worst local minimum to explain the upper bound of convergence rate in Equation 2. This implies that ∆f is not a critical reason for moving away from stationary points of f by catastrophic forgetting, which we will explain in Section 3.
We also define σf and σg for f and g, respectively, as the upper bounds on the variance of the stochastic gradients of a given mini-batch. For brevity, we write only one of them σf ,
σf = sup x
1
nf nf∑ i=1 ‖∇fi(x)−∇f(x)‖2. (3)
Throughout the paper, we assume the L-smoothness. Assumption 1. fi is L-smooth that there exists a constant L > 0 such that for any x, y ∈ Rd,
‖∇fi(x)−∇fi(y)‖ ≤ L‖x− y‖ (4)
where ‖·‖ denotes the Euclidean norm. Then the following inequality directly holds that
−L 2 ‖x− y‖2 ≤ fi(x)− fi(y)− 〈∇fi(y), x− y〉 ≤ L 2 ‖x− y‖2. (5)
We derive the inequality in Appendix B. With Assumption 1, we can successfully handle individual noncovex objectives for each data point. In the next section, we investigate nonconvex continual learning with adaptive learning rates to overcome catastrophic forgetting.

heading: 3 NONCONVEX CONTINUAL LEARNING
text: We first present a theoretical convergence analysis of memory-based continual learning in nonconvex setting. We use the convergence rate of stochastic gradient methods, which denotes the IFO complexity to reach an -accurate solution for smooth nonconvex finite-sum problem (Reddi et al., 2016a). This generic form enables both deep learning and optimization communities to formulate various accelerated gradient methods with theoretical guarantee. We seek to understand why catastrophic forgetting happens in terms of the convergence rate, and propose non-convex continual learning (NCCL) algorithms with theoretical convergence analysis.

heading: 3.1 PROBLEM FORMULATION
text: Given two finite sets P and C at the initial time step t = 0, we let two sets denote the sets of indices for previously learned data points and upcoming data points, respectively. Note that the task description for a continual learner is two separate sets. In this section, we will show a convergence analysis of the model parameter that we have trained on P and starts to learn C. Thus, we simply denote a data stream of continual learning as two consecutive sets P and C.
We consider our goal as a smooth nonconvex finite-sum optimization problem with two objectives
min x∈Rd
F (x) = f(x) + g(x) = 1
nf ∑ i∈P fi(x) + 1 ng ∑ j∈C gj(x), (6)
where fi(x) and gj(x) denote the objectives of data points i ∈ P and j ∈ C, respectively. In addition, nf and ng are the numbers of elements for P and C. To ease exposition, we use a different notation gj(x) for a data point j ∈ C, which is usually the same objective function for a data point i ∈ P . To formulate a theoretical convergence analysis of continual learning, we consider a replay memory based method of which memory is a subset of P ∪ C. Let a random variable Mt ⊂ P ∪ C be the replay memory at time step t ∈ [0, T ], whose union is of the form M := ∪tMt. We focus both the
episodic memory and the replay memory with dropping rule. The episodic memory based methods include GEM (Aljundi et al., 2019), A-GEM (Chaudhry et al., 2019a), and ORTHOG-SUBSPACE (Chaudhry et al., 2020). ER-Reservoir (Chaudhry et al., 2019b) is a replay memory based method with dropping rule, which replaces the dropped sample d ∈Mt with a sample in the stream for C. We now define the gradient update of continual learning
xt+1 = xt − αHt∇fIt(xt)− βHt∇gJt(xt), (7) where It ⊂Mt and Jt ⊂ C denote the mini-batches from the replay memory and the current data stream, respectively. Here, Ht is the union of It and Jt. The adaptive learning rates of ∇fIt(xt) and ∇gJt(xt) are denoted by αHt and βHt which are the functions of Ht. Strictly speaking, the mini-batch It from Mt might contain a datapoint d ∈ C for ER-Reservoir. We describe the details of the problem in Appendix B and assume that the notation It indicates a subset of P for convenience. Equation 7 is a generalized version of continual learning algorithms, which is our novelty to prove the convergence rates in the nonconvex setting for the proposed method, A-GEM, and ER-Reservoir later.

heading: 3.2 MEMORY-BASED NONCONVEX CONTINUAL LEARNING
text: Unlike the conventional smooth nonconvex finite-sum problem where each mini-batch is iid-sampled from the dataset P ∪ C, the replay memory based continual learning encounters a non-iid stream of data C and has access to a small sized memory M . Algorithm 1 presents the pseudocode of NCCL by Equation 7. By the limited access to P , the gradient update for f(x) in Equation 7 is a biased estimate of the gradient∇f(xt). Specifically, at the timestep t,
∇fMt(xt) = EIt [ ∇fIt(xt)|Mt ] = EIt [ ∇f(xt) + et|Mt ] = ∇f(xt) + eMt ,
where et and eMt denote the error term ∇fIt(xt)−∇f(xt) and the expectation value over It given Mt, respectively. We note that the given replay memory Mt with small size at timestep t induces the inevitable overfitting bias. We first state an intermediate result for a single gradient update of NCCL. For ease of exposition, we define the overfitting term Bt and the catastrophic forgetting term Γt as follows:
Bt = (Lα 2 Ht − αHt)〈∇f(x t), et〉+ βHt〈∇gJt(xt), et〉, Γt = β2HtL
2 ‖∇gJt(xt)‖2 − βHt(1− αHtL)〈∇fIt(xt),∇gJt(xt)〉,
where L is a constant for Lipschitz smoothness. Under Assumption 1, a single gradient update by Equation 7 satisfies the following bound by letting x← xt+1 and y ← xt:(
αHt − L
2 α2Ht
) ‖∇f(xt)‖2 ≤ f(xt)− f(xt+1) + Γt +Bt + L
2 α2Ht‖et‖ 2. (8)
This reveals the basic qualitative difference between the conventional nonconvex SGD and NCCL in the convergence rate. Compared to the nonconvex SGD, there exist two terms Bt and Γt in Equation 8. We group the terms containing et as Bt and the other terms as Γt. We note that the catastrophic forgetting term Γt has 〈∇fIt(xt),∇gJt(xt)〉, which is the key aspect of interference and transer (Riemer et al., 2018), and Bt includes the error term between the batch of M and the entire dataset P . Then, we can quantify the amount of overfitting by tracing Bt.
To compute the expectation over the stochasticity of NCCL, we derive the expectation of ∇fMt(xt) over the sampling rule of Mt. The episodic memory Mt = M0 for all t is uniformly sampled once from the random sequence of P , and ER-reservoir iteratively samples the replay memory Mt by the selection probability P (Mt|Mt−1). Lemma 1. Let the history of Mt be M[0:t] = (M0, · · · ,Mt). If M0 is uniformly sampled from P , then both episodic memory and ER-reservoir satisfies
EM[0:t] [ ∇fMt(xt) ] = ∇f(xt) and EM[0:t] [eMt ] = 0. (9)
We provide the detailed proof in Appendix B. Note that taking expectation iteratively with respect to the history M[0:t] is needed to compute the expected value of gradients for Mt. Since taking the expectation over the stochasticity of NCCL implies the total expectation
E = EM[0:t] [ EIt [EJt [ · |It]] |M[0:t] ] ,
Algorithm 1 Nonconvex Continual Learning (NCCL)
Input: Previous task P , K task data stream {D1, · · ·DK}, initial model x0, memory M0 ⊂ P for k = 1 to K do
for t = 0 to T − 1 do Uniformly sample a mini-batch It ⊂Mt with |It| = bf Uniformly sample a mini-batch Jt ⊂ Dk with |Jt| = bg Compute learning rates αHt and βHt with∇fIt(xt) and∇gJt(xt) xt+1 ← xt − αHt∇fIt(xt)− βHt∇gJt(xt) Store Jt into Mt+1 by the rule of replay memory scheme end for x0 ← xT−1 P ← P ∪ ⋃ t Jt
M0 ←MT−1 end for
we know that E[Bt] is also 0. We note that considering a random choice of M0 allows us to analyze the convergence on f(x), even if M0 cannot access the all datapoints in P to compute ‖∇f(xt)‖2. Our first main result is the following lemma that provides the stepwise change of upper bound.
Lemma 2. Suppose that Assumption 1 holds and 0<αHt ≤ 2L . Then for x t updated by Algorithm 1, we have the following bound
E‖∇f(xt)‖2 ≤ E
[ 1
αHt(1− L2 αHt) ( f(xt)− f(xt+1) +Bt + Γt ) +
αHtL
2(1− L2 αHt) σ2f
] , (10)
where the effect of Bt vanishes by E[Bt] = 0.
The proof is presented in Appendix B. Surprisingly, taking the expectation over M0 ⊂ P in Equation 10 to handle the stochasticity of choosing M0 allows us to analyze the convergence of f(x) in Section 3.3. We also note that the individual trial with a randomly given M0 cannot cancel the effect by Bt, although its total expectation over the whole possible trials E[Bt] is zero. More specifically, the worst case supM0‖∇f(x
t)‖2 definitely contains the non-zero value of Bt in the upper bound term. We discuss the more details of the overfitting to memory in Appendix D.

heading: 3.3 THEORETICAL CONVERGENCE ANALYSIS
text: We now describe our convergence analysis of the stochastic gradient descent by Equation 7. Without any continual learning scheme, the model xt eventually converges to M ∪ C, not P ∪ C. A local optimal point x0 for P at time step t = 0, which we have already trained before the continual learning step starts, loses the performance on P very quickly over time. This phenomenon is called catastrophic forgetting. We also note that the overfitting to replay memory is another reason of degrading performance for each trial when the model trains on samples in M with replacement after learning on P for previous tasks. We obtain the convergence rate of NCCL to a stationary point of f as the following theorem. Theorem 1. Let αHt = α = c√T for some 0 < c ≤ 2 √ T L and t ∈ {0, · · · , T − 1}. By Lemma 2, the iterates of NCCL satisfy
min t E‖∇f(xt)‖2 ≤ A√ T
( 1
c
( ∆f +
T−1∑ t=0 E [Γt]
) + Lc
2 σ2f
) , (11)
where A = 1/(1− Lα/2).
For completeness we present a proof in Appendix A. The loss gap ∆f and the variance of gradients σf are fixed values. We first note that there exists the cumulative sum of E[Γt] unlike the convergence rate of SGD. Most of novelty in our analysis lies in dealing with ∑ E[Γt]. The ∑T−1 t=0 E[Γt]/ √ T
is not guaranteed to converge to 0. This fact gives rise to catastrophic forgetting in terms of the nondecreasing upper bound.
Before showing a bound on IFO calls made by NCCL, we present the convergence rate for g(x). To simplify the proof, we assume that learning rates αHt , βHt are a same fixed value β = c ′/ √ T . The assumption is reasonable, because we can observe that RHS of Equation 10 is not perturbed drastically by the learning rates with small value 0 < αHt , βHt ≤ 2/L 1. Then we have the following lemma. Lemma 3. Suppose that It ∩ Jt = ∅, and the datapoints d ∈M ∩P use the same objective function gd = fd. Taking expectation over It ⊂Mt and Jt ⊂ C, we have
min t
E‖∇g(xt)‖2 ≤ √ 2∆gL
T σg, (12)
where ∆g and σg is the version of loss gap and the variance for g on M ∪ C, respectively. In fact, we note that the convergence rate of g is on M ∪C. Despite the convergence rate is not on C, it also converges to C trivially.
Now we can get the upper bound of ∑
E[Γt] by Lemma 3. Then we have the following main result. Corollary 1. The IFO complexity of Algorithm 1 to obtain an -accurate solution is:
IFO calls = { O(1/ 2), ∑ E[Γt] = O(1),
∞, ∑ E[Γt] = O(T ). (13)
The proofs of both Lemma 3 and Corollary 1 are presented in Appendix B. Here, we denote∞ as the impossibility of convergence. This result reveals that catastrophic forgetting is inevitable without minimizing the cumulative sum ∑ E[Γt]. With replay memory, we know that the inner product in Γt can be negative by the result of A-GEM (Chaudhry et al., 2019a). This observation shows that there exists the chance that Γt becomes negative, and ∑ E[Γt] can converge to a constant O(1) as t→∞. Now we have the proper convergence rate of f(x), and the model can keep the performance on P after learning on C. On the other hand, when αHt = 0 for all time step, E[Γt] is always larger than 0. Intuitively, this case implies SGD on C without the replay memory M or other supports, and the cumulative sum ∑ E[Γt] monotonically increases over time. Then, f(xt) diverges as t→∞. We emphasize that the reason of catastrophic forgetting can be explained remarkably by the nonconvex optimization perspective.
The optimization problem of nonconvex continual learning. The local optimal point xt after learning on C might be different from x0, because xt moves towards x∗P∪C as described in Figure 1. The above observation motivates the following formulation of continual learning to induce ∑ E[Γt] to converge as t→∞ and keep -accuracy of f during T iterations. More specifically, we solve the following problem over T :
minimize αHt , βHt T−1∑ t=0 Γt
subject to 0 < αHt , βHt ≤ 2/L for all t < T. (14)
Recall that we have the condition of two learning rates to prove Theorem 1 and Lemma 3. This condition needs to be constraints of the above optimization problem.
Finally, we note that our result first shows a theoretical convergence analysis of memory based nonconvex continual learning in the setting of Corollary 1. More precisely, we can now explain this method by Problem 14 with theoretical guarantee.

heading: 3.4 ADAPTIVE LEARNING RATES
text: As discussed in Section 3.3, the minimization problem 14 leads to tight the upper bound of convergence rate in nonconvex setting. The result of convergence analysis provides a simple continual learning framework that only adjusts two learning rates in Equation 7. First, we review A-GEM and other methods with fixed learning rate such as GSS (Aljundi et al., 2019) and ER-Reservoir (Chaudhry et al., 2019b) through our result.
A-GEM (Chaudhry et al., 2019a) propose a surrogate of∇gJt(xt) as the following equation to avoid violating the constraint when 〈∇fIt(xt),∇gJt(xt)〉 ≤ 0:
∇gJt(xt)− 〈 ∇fIt(xt) ‖∇fIt(xt)‖ ,∇gJt(xt) 〉 ∇fIt(xt) ‖∇fIt(xt)‖ .
We can interpret the surrogate as boosting the learning rate αHt to cancel out the negative component of ∇fIt(xt) on ∇gJt(xt). After applying the surrogate, E[Γt] is reduced but still nonnegative, which we show in Appendix C. A-GEM also fails to fully use the advantage of the case 〈∇fIt(xt),∇gJt(xt)〉 > 0. Fixed learning rates imply that building a replay memory is the key to success in continual learning. It means that this memory setting is an abundant pool to sample It, which satisfies 〈∇fIt(xt),∇gJt(xt)〉 > 0, as much as possible. This can reduce ∑ E[Γt].
However, two above methods cannot enjoy the case 〈∇fIt(xt),∇gJt(xt)〉 > 0 enough. As discussed above,we note that Γt is a quadratic polynomial of βHt where βHt > 0. We can solve the minimum of the polynomial on βHt when 〈∇fIt(xt),∇gJt(xt)〉 > 0. By differentiating on βHt , we can easily find the minimum Γ∗t and the optimal learning rate β ∗ Ht
β∗Ht = (1− αHtL)〈∇fIt(xt),∇gJt(xt)〉
L‖∇gJt(xt)‖2 , Γ∗t = − (1− αHtL)〈∇fIt(xt),∇gJt(xt)〉 2L‖∇gJt(xt)‖2 .
We integrate the above result to propose a better nonconvex continual learning algorithm with the theoretical guarantee. More specifically, we propose an adaptive learning rate method that can reduce∑
E[Γt] in both cases of 〈∇fIt(xt),∇gJt(xt)〉 ≤ 0 and 〈∇fIt(xt),∇gJt(xt)〉 > 0. Then, the proposed adaptive learning rate scheme is as follows.
αHt =
{ α(1− 〈∇fIt (x t),∇gJt (x t)〉
‖∇fIt (xt)‖2 ), 〈∇fIt(xt),∇gJt(xt)〉 ≤ 0
α, 〈∇fIt(xt),∇gJt(xt)〉 > 0 (15)
βHt = { α, 〈∇fIt(xt),∇gJt(xt)〉 ≤ 0 (1−αL)〈∇fIt (x t),∇gJt (x t)〉
L‖∇gJt (xt)‖2 , 〈∇fIt(xt),∇gJt(xt)〉 > 0
(16)
We derive the details of the above result in Appendix C. In addition, our result shows that A-GEM can be viewed as an adaptive learning rate scheme using samples in Mt directly. This fact implies that there is no difference between A-GEM and experience replay methods. Figure 1 illustrates intuitively how scaling learning rates achieve the convergence to a mutual stationary point x∗P∪C as we proved the theoretical complexity in Corollary 1.

heading: 4 EXPERIMENTS
text: We evaluate the proposed NCCL and the state of the art online continual learning baselines on the following benchmarks. We report detailed experimental materials and results in Appendix.
Datasets. We demonstrate the experimental results on standard continual learning benckmarks: Permuted-MNIST (Kirkpatrick et al., 2017) is a MNIST (LeCun et al., 1998) based dataset, where each task has a fixed permutation of pixels and transform data points by the permutation to make each task distribution unrelated. Split-MNIST (Zenke et al., 2017) splits MNIST dataset into five tasks. Each task consists of two classes, for example (1, 7), (3, 4), and has approximately 12K images. Split-CIFAR10 and 100 also split CIFAR-10 and 100 datasets (Krizhevsky et al., 2009) into five tasks and 20 tasks, respectively.
Baselines. We report the experimental evaluation on the online continual setting which implies a model is trained with a single epoch. We compare with the following continual learning baselines. Fine-tune is a simple method that a model trains observed data naively without any support, such as replay memory. Elastic weight consolidation (EWC) is a regularization based method by Fisher Information (Kirkpatrick et al., 2017). ER-Reservoir chooses samples to store from a data stream with a probability proportional to the number of observed data points. The replay memory returns
a random subset of samples at each iteration for experience replay. ER-Reservoir (Chaudhry et al., 2019b) shows a powerful performance in continual learning scenario. GEM and A-GEM (Lopez-Paz & Ranzato, 2017; Chaudhry et al., 2019a) use gradient episodic memory to overcome catastrophic forgetting. The key idea of GEM is gradient projection with quadratic programming and A-GEM simplifies this procedure. We also compare with iCarl, MER, ORTHOG-SUBSPACE (Chaudhry et al., 2020), and stable-SGD (Mirzadeh et al., 2020).
Architecture and Training detail. For a fair comparison, we follow the commonly used model architecture and hyperparameters of Lee et al. (2020); Chaudhry et al. (2020). For Permuted-MNIST and Split-MNIST, we use fully-connected neural networks with two hidden layers of [400, 400] or [256, 256] and ReLU activation. ResNet-18 with the number of filters nf = 64, 20 (He et al., 2016) is applied for Split CIFAR-10 and 100. All experiments conduct a single-pass over the data stream. It is also called 1 epoch or 0.2 epoch (in the case of split tasks). We deal both cases with and without the task identifiers in the results of split-tasks to compare fairly with baselines. Batch sizes of data stream and memory are both 10. All reported values are the average values of 5 runs with diffrent seeds, and we also provide standard deviation. Other miscellaneous settings are the same as in Chaudhry et al. (2020). We implement the baselines and the propose method on Tensorflow 1. For evaluation, we use an NVIDIA 2080ti GPU along with 3.60 GHz Intel i9-9900K CPU and 64 GB RAM.

heading: 4.1 RESULTS
text: The following tables show our main experimental result, which is averaged over 5 runs. We denote the number of example per class per task at the top of each column.
Overall, NCCL variants outperforms baseline methods especially in the forgetting metric. Our goal is to demonstrate the usefulness of the adaptive learning rate scheme to reduce the catastrophic forgetting, and verify the proposed theoretical convergence analysis. We remark that our adaptive learning rates successfully suppress forgetting by a large margin compared to baselines. Note that NCCL also outperform A-GEM, which does not maximize transfer 〈∇fIt(xt),∇gJt(xt)〉 > 0. Now, we can empirically demonstrate our theoretical guaranteed method by minimizing ∑ Γt is valid.
We clipped βHt to increase the performance. As we discussed earlier, we can prevent forgetting when 〈∇fIt(xt),∇gJt(xt)〉 > 0. However, we observe that ‖∇fIt(xt)‖2 suddenly increases because of the interference at the previous step t − 1. The very large learning rate βHt by the increased ‖∇fIt(xt)‖ can force the model to fall into an arbitrary point that is likely to increase the loss of f . Clipping the learning rate reduces this problem and still has the effect of reducing the catastrophic forgetting term Γt. By the property of quadratic polynomial, the catastrophic forgetting term is negative because the clipped value is smaller than the original learning rate.
We show that NCCL is a potentially powerful alternative for continual learning. Even with tiny replay memory, NCCL still performs better than some baselines. We note that NCCL shows the best performance on the forgetting metric. It implies that NCCL prevent catastrophic forgetting more efficiently than others by minimizing the catastrophic forgetting term in the proposed optimization problem. However, the accuracy is slightly lower than other baselines, which include experience replays. The purpose of our adaptive learning rate scheme is to prevent catastrophic forgetting, so the performance of current task is slightly lower than ER-Ring, stable-SGD, and ORTHOG-subspace. This result shows that the plasticity to learn a new task is restricted by NCCL variants with tiny memory. In particular, we would expect that NCCL would benefit from the additional enhancements in ORTHOG-SUBSPACE and stable SGD by introducing their techniques. In appendix, we add more results with larger sizes of memory, which shows that NCCL outperforms on the average accuracy. We conclude that the transfer effect by the small size of memory for NCCL is less effective.

heading: 5 RELATED WORK
text: We extend the memory based continual learning (Lopez-Paz & Ranzato, 2017; Chaudhry et al., 2019a; Riemer et al., 2018; Chaudhry et al., 2019b) to the nonconvex optimization problem to provide the theoretical guarantee of previous methods. Our problem setting is related to the theoretical convergence analysis of smooth nonconvex optimization. Smooth nonconvex finite-sum optimization problem has been widely employed to derive the theoretical complexity of computation for stochastic gradient methods (Ghadimi & Lan, 2013; 2016; Lei et al., 2017; Zaheer et al., 2018; Reddi et al., 2016a). Unlike the convex optimization, the gradient based algorithms are not expected to converge to the global minimum but are evaluated by measuring the convergence rate to the stationary points in the nonconvex case. Prior works have only focused on analyze the problems with two objectives where the additional term is for regularization (Yao & Kwok, 2016). Here, we instead focuses on the continual learning problem, which has two objectives for both datapoints of the previous task and the current task. This setting is interesting since we can observe the convergence of each task respectively. Otherwise, (Knoblauch et al., 2020) first develops a theoretical approach on continual learning by set theory, and shows that optimal continual learning algorithms and building a perfect memory is equivalent. This is analogous to our result that we cannot handle the overfitting bias for each trial of continual learning.

heading: 6 CONCLUSION
text: In this paper, we have presented the first generic theoretical convergence analysis of continual learning. Our proof shows that a training model can circumvent catastrophic forgetting by suppressing the disturbance term on the convergence of previously learned tasks. We also demonstrate theoretically and empirically that the performance of past tasks by nonconvex continual learning with replay memory is degraded by two separate reasons, catastrophic forgetting and overfitting to memory. To tackle these problems, nonconvex continual learning uses two methods, scaling learning rates adaptive to mini-batches and sampling mini-batches with small size from the replay memory. Finally, it is expected the proposed nonconvex framework is helpful to analyze the convergence rate of other continual learning algorithms.

heading: A ADDITIONAL EXPERIMENTAL RESULTS AND DETAILS
text: A.1 HYPERPARAMETER GRIDS
We report the hyper-paramters grid we used in our experiments below. Except for the proposed algorithm, we adopted the hyper-paramters that are reported in the original papers. We used grid search to find the optimal parameters for each model.
• finetune - learning rate [0.003, 0.01, 0.03 (CIFAR), 0.1 (MNIST), 0.3, 1.0] • EWC - learning rate: [0.003, 0.01, 0.03 (CIFAR), 0.1 (MNIST), 0.3, 1.0] - regularization:
[0.1, 1, 10 (MNIST,CIFAR), 100, 1000] • AGEM - learning rate: [0.003, 0.01, 0.03 (CIFAR), 0.1 (MNIST), 0.3, 1.0] • ER-Reservoir - learning rate: [0.003, 0.01, 0.03 (CIFAR), 0.1 (MNIST), 0.3, 1.0] • ORTHOG-SUBSPACE - learning rate: [0.003, 0.01, 0.03, 0.1 (MNIST), 0.2, 0.4 (CIFAR),
1.0] • MER - learning rate: [0.003, 0.01, 0.03 (MNIST, CIFAR), 0.1, 0.3, 1.0] - within batch
meta-learning rate: [0.01, 0.03, 0.1 (MNIST, CIFAR), 0.3, 1.0] - current batch learning rate multiplier: [1, 2, 5 (CIFAR), 10 (MNIST)]
• iid-offline and iid-online - learning rate [0.003, 0.01, 0.03 (CIFAR), 0.1 (MNIST), 0.3, 1.0] • ER-reservoir - learning rate: [0.003, 0.01, 0.03, 0.1 (MNIST, CIFAR), 0.3, 1.0] • NCCL-Ring (default) - learning rate α: [0.003, 0.001(CIFAR), 0.01, 0.03, 0.1, 0.3, 1.0] • NCCL-Reservoir - learning rate α: [0.003(CIFAR), 0.001, 0.01, 0.03, 0.1, 0.3, 1.0]
A.2 ADDITIONAL RESULTS

heading: B THEORETICAL ANALYSIS
text: In this section, we provide the proofs of the results for nonconvex continual learning. We first start with the derivation of Equation 5 in Assumption 1.
B.1 ASSUMPTION AND ADDITIONAL LEMMA
Derivation of Equation 5. Recall that
|fi(x)− fi(y)− 〈∇fi(y), x− y〉| ≤ L
2 ‖x− y‖2. (17)
Note that fi is differentiable and nonconvex. We define a function g(t) = fi(y + t(x − y)) for t ∈ [0, 1] and an objective function fi. By the fundamental theorem of calculus,∫ 1
0
g′(t)dt = f(x)− f(y). (18)
By the property, we have |fi(x)− fi(y)− 〈∇fi(y), x− y〉|
= ∣∣∣∣∫ 1 0 〈∇fi(y + t(x− y)), x− y〉dt− 〈∇fi(y), x− y〉 ∣∣∣∣
= ∣∣∣∣∫ 1 0 〈∇fi(y + t(x− y))−∇fi(y), x− y〉dt ∣∣∣∣ .
Using the Cauchy-Schwartz inequality,∣∣∣∣∫ 1 0 〈∇fi(y + t(x− y))−∇fi(y), x− y〉dt ∣∣∣∣
≤ ∣∣∣∣∫ 1
0
‖∇fi(y + t(x− y))−∇fi(y)‖ · ‖x− y‖dt ∣∣∣∣ .
Since fi satisfies Equation 4, then we have |fi(x)− fi(y)− 〈∇fi(y), x− y〉|
≤ ∣∣∣∣∫ 1
0
L‖y + t(x− y)− y‖ · ‖x− y‖dt ∣∣∣∣
= L‖x− y‖2 ∣∣∣∣∫ 1
0
tdt ∣∣∣∣ = L
2 ‖x− y‖2.
Lemma B.1. Let p = [p1, · · · pD], q = [q1, · · · , qD] be two statistically independent random vectors with dimension D. Then the expectation of the inner product of two random vectors E[〈p, q〉] is∑D d=1 E[pd]E[qd].
Proof. By the property of expectation,
E[〈p, q〉] = E[ D∑ d=1 pdqd]
= D∑ d=1 E[pdqd]
= D∑ d=1 E[pd]E[qd].
B.2 PROOF OF MAIN RESULTS
We now show the main results of our work.
Proof of Lemma 1. To clarify the issue of EMt [EIt [et|Mt]] = 0, let us explain the details of constructing replay-memory as follows. We have considered episodic memory and reservoir sampling in the paper. We will first show the case of episodic memory by describing the sampling method for replay memory. We can also derive the case of reservoir sampling by simply applying the result of episodic memory.
Episodic memory (ring buffer). We divide the entire dataset of continual learning into the previous task P and the current task C on the time step t = 0. For the previous task P , the data stream of P is i.i.d., and its sequence is random on every trial (episode). The trial (episode) implies that a continual learning agent learns from an online data stream with two consecutive data sequences of P and C. Episodic memory takes the last data points of the given memory size m by the First In First Out (FIFO) rule, and holds the entire data points until learning on C is finished. Then, we note that Mt = M0 for all t ≥ 0 and M0 is uniformly sampled from the i.i.d. sequence of P . By the law of total expectation, we derive EM0⊂P [EIt [∇fIt(xt)|M0]] for any xt, ∀t ≥ 0 as follows.
EM0⊂P [ EIt [ ∇fIt(xt)|M0 ]] = EM0⊂P [ ∇fM0(xt) ] .
We know that M0 was uniformly sampled from P on each trial before training on the current task C. Then, we take expectation with respect to every trial that implies the expected value over the memory distribution M0. We get
EM0⊂P [ ∇fM0(xt) ] = ∇f(xt)
for any xt, ∀t. We can consider ∇fMt(xt) as a sample mean of P on every trial for any xt, ∀t ≥ 0. Although xt is constructed iteratively, the expected value of the sample mean for any xt, EM0⊂P [∇fM0(xt)] is also derived as∇f(xt). Reservoir sampling. To clarify the notation for reservoir sampling first, we denote the expectation with respect to the history of replay memory M[0:t] = (M0, · · · ,Mt) as EM[0:t] . This is the revised version of EMt . Reservoir sampling is the more tricky case than episodic memory, but EM[0:t] [EIt [et|Mt]] = 0 still holds. Suppose that M0 is full of the data points from P as the episodic memory is sampled and the mini-batch size from C is 1 for simplicity. The reservoir sampling algorithm drops a data point in Mt−1 and replaces the dropped data point with a data point in the current mini-batch from C with probability p = m/n, where m is the memory size and n is the number of visited data points so far. The exact pseudo-code for reservoir sampling is described in [1]. The replacement procedure uniformly chooses the data point which will be dropped. We can
also consider the replacement procedure as follows. The memory Mt for P is reduced in size 1 from Mt−1, and the replaced data point dC from C contributes in terms of ∇gdC (xt) if dC is sampled from the replay memory. Let Mt−1 = [d1, · · · , d|Mt−1|] where | · | denotes the cardinality of the memory. The sample mean of Mt−1 is given as
∇fMt−1(xt−1) = 1 |Mt−1| ∑ di ∇fdi(xt−1). (19)
By the rule of reservoir sampling, we assume that the replacement procedure reduces the memory from Mt−1 to Mt with size |Mt−1| − 1 and the set of remained upcoming data points Ct ∈ C from the current data stream for online continual learning is reformulated into Ct−1 ∪ [dC ]. Then, dC can be resampled from Ct−1 ∪ [dC ] to be composed of the minibatch of reservoir sampling with the dfferent probability. However, we ignore the probability issue now to focus on the effect of replay-memory on∇f . Now, we sample Mt from Mt−1, then we get the random vector∇fMt(xt) as
∇fMt(xt) = 1
|Mt| |Mt−1|∑ j=1 Wij∇fdj (xt), (20)
where the index i is uniformly sampled from i ∼ [1, · · · , |Mt−1|], and Wij is the indicator function that Wij is 0 if i = j else 1.
The above description implies the dropping rule, and Mt can be considered as an uniformly sampled set with size |Mt| from Mt−1. There could also be Mt = Mt−1 with probability 1− p = 1−m/n. Then the expectation of ∇fMt(xt) given Mt−1 is derived as
EMt [∇fMt(xt)|Mt−1] = p  1 |Mt−1| |Mt−1|∑ i 1 |Mt| |Mt−1|∑ j=1 Wij∇fdj (xt) + (1− p) (∇fMt−1(xt)) = ∇fMt−1(xt).
When we consider the mini-batch sampling, we can formally reformulate the above equation as
EMt∼p(Mt|Mt−1) [ EIt⊂Mt [ ∇fIt(xt)|Mt ] |Mt−1 ] = ∇fMt−1(xt). (21)
Now, we apply the above equation recursively. Then,
EM1∼p(M1|M0) [ · · ·EMt∼p(Mt|Mt−1) [ EIt⊂Mt [ ∇fIt(xt)|Mt ] |Mt−1 ] · · · |M0 ] = ∇fM0(xt).
(22) Similar to episodic memory, M0 is uniformly sampled from P . Therefore, we conclude that
EM0,··· ,Mt [∇fMt(xt)] = ∇f(xt) (23)
by taking expectation over the history M[0:t] = (M1,M2, · · · ,Mt). Note that taking expectation iteratively with respect to the history M[t] is needed to compute the expected value of gradients for Mt. However, the result EM0,··· ,Mt [EIt [et|Mt]] = 0 still holds in terms of expectation.
Proof of Lemma 2. We analyze the convergence of nonconvex continual learning with replay memory here. Recall that the gradient update is the following
xt+1 = xt − αHt∇fIt(xt)− βHt∇gJt(xt)
for all t ∈ {1, 2, · · · , T}. Let et = ∇fIt(xt)−∇f(xt). Since we assume that f, g is L-smooth, we have the following inequality by applying Equation 5:
f(xt+1) ≤ f(xt) + 〈∇f(xt), xt+1 − xt〉+ L 2 ‖xt+1 − xt‖2
= f(xt)− 〈∇f(xt), αHt∇fIt(xt) + βHt∇gJt(xt)〉+ L
2 ‖αHt∇fIt(xt) + βHt∇gJt(xt)‖2
= f(xt)− αHt〈∇f(xt),∇fIt(xt)〉 − βHt〈∇f(xt),∇gJt(xt)〉
+ L
2 α2Ht‖∇fIt(x t)‖2 + L 2 β2Ht‖∇gJt(x t)‖2 + LαHtβHt〈∇fIt(xt),∇gJt(xt)〉
= f(xt)− αHt〈∇f(xt),∇f(xt)〉 − αHt〈∇f(xt), et〉 − βHt〈∇fIt(xt),∇gJt(xt)〉+ βHt〈∇gJt(xt), et〉
+ Lα2Ht
2 ‖∇f(xt)‖2 + Lα2Ht〈∇f(x
t), et〉+ Lα2Ht
2 ‖et‖2 + Lβ2Ht 2 ‖∇gJt(xt)‖2 + LαHtβHt〈∇fIt(xt),∇gJt(xt)〉
= f(xt)− ( αHt − L
2 α2Ht
) ‖∇f(xt)‖2 + L
2 β2Ht‖∇gJt(x t)‖2 − βHt(1− αHtL)〈∇fIt(xt),∇gJt(xt)〉
+ ( Lα2Ht − αHt ) 〈∇f(xt), et〉+ βHt〈∇gJt(xt), et〉+ L
2 α2Ht‖et‖ 2. (24)
To show the proposed theoretical convergence analysis of nonconvex continual learning, we define the catastrophic forgetting term Γt and the overfitting term Bt as follows:
Bt = (Lα 2 Ht − αHt)〈∇f(x t), et〉+ βHt〈∇gJt(xt), et〉, Γt = β2HtL
2 ‖∇gJt(xt)‖2 − βHt(1− αHtL)〈∇fIt(xt),∇gJt(xt)〉.
Then, we can rewrite Equation 24 as f(xt+1) ≤ f(xt)− ( αHt − L
2 α2Ht
) ‖∇f(xt)‖2 + Γt +Bt + L
2 α2Ht‖et‖ 2. (25)
We first note that Bt is dependent of the error term et with the batch It. In the continual learning step, an training agent cannot access ∇f(xt), then we cannot get the exact value of et. Furthermore, Γt is dependent of the gradients∇fIt(xt),∇gIt(xt) and the learning rates αHt , βHt . Taking expectations with respect to It on both sides given Jt, we have
EIt [ f(xt+1) ] ≤ EIt [ f(xt)− ( αHt − L
2 α2Ht
) ‖∇f(xt)‖2 + Γt +Bt + L
2 α2Ht‖et‖
2 ∣∣∣Jt]
≤ EIt [ f(xt)− ( αHt − L
2 α2Ht
) ‖∇f(xt)‖2 + L
2 α2Ht‖et‖ 2
] + EIt [ Γt +Bt ∣∣∣Jt] . Now, taking expectations over the whole stochasticity we obtain
E [ f(xt+1) ] ≤ E [ f(xt)− ( αHt − L
2 α2Ht
) ‖∇f(xt)‖2 + Γt +Bt + L
2 α2Ht‖et‖ 2
] .
Rearranging the terms and assume that 11−LαHt/2 > 0, we have( αHt − L
2 α2Ht
) E‖∇f(xt)‖2 ≤ E [ f(xt)− f(xt+1) + Γt +Bt + L
2 α2Ht‖et‖ 2 ] and
E‖∇f(xt)‖2 ≤ E
[ 1
αHt(1− L2 αHt) ( f(xt)− f(xt+1) + Γt +Bt ) +
αHtL
2(1− L2 αHt) ‖et‖2
]
≤ E
[ 1
αHt(1− L2 αHt) ( f(xt)− f(xt+1) + Γt +Bt ) +
αHtL
2(1− L2 αHt) σ2f
] .
Proof of Theorem 1. Suppose that the learning rate αHt is a constant α = c/ √ T , for c > 0, 1− L2 α = 1 A > 0. Then, by summing Equation 10 from t = 0 to T − 1, we have
min t E‖∇f(xt)‖2 ≤ 1 T T−1∑ t=0 E‖∇f(xt)‖2
≤ 1 1− L2 α
( 1
αT
( f(x0)− f(xT ) +
T−1∑ t=0 (E [Bt + Γt])
) + L
2 ασ2f
)
= 1
1− L2 α
( 1
c √ T
( ∆f +
T−1∑ t=0 (E [Bt + Γt])
) + Lc
2 √ T σ2f
)
= A√ T
( 1
c
( ∆f +
T−1∑ t=0 E [Bt + Γt]
) + Lc
2 σ2f
) . (26)
We note that a batch It is sampled from a memory Mt ⊂M which is a random vector whose element is a datapoint d ∈ P ∪ C. Then, taking expectation over It ⊂Mt ⊂ P ∪ C implies that E[Bt] = 0. Therefore, we get the minimum of expected square of the norm of gradients as follows:
min t E‖∇f(xt)‖2 ≤ A√ T
( 1
c
( ∆f +
T−1∑ t=0 E[Γt]
) + Lc
2 σ2f
) .
Proof of Lemma 3. By the assumption, it is equivalent to update on M ∪ C. Then, the non-convex finite sum optimization is given as
min x∈Rd
g(x) = 1 ng + |M | ∑ i∈M∪C gi(x), (27)
where gi is the same function as fi, and |M | is the number of elements in M . This problem can be solved by a simple SGD algorithm (Reddi et al., 2016b). Thus, we have
min t
E‖∇g(xt)‖2 ≤ √ 2∆gL
T σg. (28)
Lemma B.2. Let an upper bound β > βHt > 0. For the worst case, the expectation of summing the catastrophic forgetting term over iterations T is
T−1∑ t=0 Γt = O(T ).
Proof. First, we derive the rough upper bound of E[Γt]:
E [Γt] = E
[ β2HtL
2 ‖∇gJt(xt)‖2 − βHt(1− αHtL)〈∇fIt(xt),∇gJt(xt)〉
] (29)
≤ E [ β2HtL
2 ‖∇gJt(xt)‖2 + βHt(1− αHtL)‖∇fIt(xt)‖‖∇gJt(xt)‖
] (30)
= O ( E [ β2L
2 ‖∇gJt(xt)‖2
]) (31)
where ‖∇gJt(xt)‖ ≥ ‖∇fIt(xt)‖.
In addition, the supremum of the variance of the mini-batch gradient∇gJt(xt) is derived as
sup x E‖∇gJt(xt)−∇g(xt)‖2 = sup x ng − bg (ng − 1)bg · 1 ng ng∑ j=1 ‖∇gj(xt)−∇g(xt)‖2 (32)
= ng − bg
(ng − 1)bg σ2g , (33)
where ng and bg denotes the size of C and minibatch Jt, respectively. The detailed derivation is shown in [1]. By the triangular inequality, we get
E‖gJt(xt)‖2 ≤ E‖gJt(xt)− g(xt)‖2 + E‖g(xt)‖2 (34)
≤ E‖g(xt)‖2 + ng − bg (ng − 1)bg σ2g . (35)
By plugging the above equation into E[Γt], we conclude that
E[Γt] = O
( E [ β2L
2 ‖∇gJt(xt)‖2
]) (36)
= O ( E [ β2L
2 ‖∇g(xt)‖2 ] + β2L(ng − bg) 2(ng − 1)bg σ2g ) . (37)
The sum of catastrophic forgetting term ∑ Γt is corrected as ∑ E[Γt]. We use the technique for summing up in the proof of Theorem 1, then the cumulative sum of catastrophic forgetting term is derived as
T−1∑ t=0 E[Γt] = T−1∑ t=0 β2L 2 O ( E [ ‖∇g(xt)‖2 ] + (ng − bg) (ng − 1)bg σ2g ) (38)
≤ β 2L
2 T−1∑ t=0 O ( 1 β [ g(xt)− g(xt+1) ] + Lβ 2 σ2g + (ng − bg) (ng − 1)bg σ2g ) (39)
≤ β 2L
2 O
( 1
β ∆g +
TLβ
2 σ2g + T (ng − bg) (ng − 1)bg σ2g
) (40)
= O ( β∆g + σ 2 g ( Lβ3
2 +
(ng − bg)β2
(ng − 1)bg
) T ) . (41)
Rearranging the above equation, we get T−1∑ t=0 E[Γt] = O ( σ2g ( Lβ3 2 + (ng − bg)β2 (ng − 1)bg ) T + β∆g ) . (42)
Therefore, we can write ∑T−1 t=0 E[Γt] = O(T ). We note that the rough upper bound of ∑ Γt increases monotonically with training step as in the previous result in the paper.
Now we provide the rigorous derivation of the convergence rate by the result of Corollary 1 as follows:
O ( σ2g ( Lβ3
2 +
(ng − bg)β2
(ng − 1)bg
)√ T +
β∆g√ T
) = O( √ T ). (43)
This result is obtained by dividing ∑ E[Γt] by √ T as in the proof of Thm. 1.
On the other hand, Γt can be negative when 〈∇fIt(xt),∇gJt(xt)〉 > 0. It implies that the cumulative sum of Γt does not increase monotonically. Therefore, for some large number N , we can denote the cumulative sum of Γt over the finite steps T as follows:
T−1∑ t=0 Γt ≤ N = O(1). (44)
Proof of Corollary 1. To formulate the IFO calls, Recall that T ( )

heading: T ( ) = min {T : min E‖∇f(xt)‖2 ≤ }.
text: Additionally, a single IFO call is invested in calculating each step. As seen in Theorem 1, NCCL has a convergence rate of
O (∑T−1 t=0 Γt√ T ) . (45)
We note that the convergence rate for the worst case is O (√ T ) , (46)
where the given model diverges on the convergence of f(x). Then, IFO calls are denoted as∞. For the case of Equation 44, we obtain the convergence rate O(1/ √ T ). Thus we get O(1/ 2) in this case.

heading: C DERIVATION OF EQUATIONS IN SECTION 3.4
text: Derivation for A-GEM Let the surrogate∇g̃Jt(xt) as ∇g̃Jt(xt) = ∇gJt(xt)− 〈 ∇fIt(xt) ‖∇fIt(xt)‖ ,∇gJt(xt) 〉 ∇fIt(xt) ‖∇fIt(xt)‖ , (47)
where αHt = α(1− 〈∇fIt (x t),∇gJt (x t)〉
‖∇fIt (xt)‖2 ) and βHt = α for Equation 7.
Then, we have E[Γt] = E [ β2HtL
2 ‖∇g̃Jt(xt)‖2 − βHt〈∇fIt(xt),∇g̃Jt(xt)〉 ] = E [ β2HtL
2
( ‖∇gJt(xt)‖2 − 2 〈∇fIt(xt),∇gJt(xt)〉2
‖∇fIt(xt)‖2 + 〈∇fIt(xt),∇gJt(xt)〉2 ‖∇fIt(xt)‖2
) − βHt〈∇fIt(xt),∇g̃Jt(xt)〉 ] = E [ β2HtL
2
( ‖∇gJt(xt)‖2 − 〈∇fIt(xt),∇gJt(xt)〉2
‖∇fIt(xt)‖2
) − βHt ( 〈∇fIt(xt),∇gJt(xt)〉 − 〈∇fIt(xt),∇gJt(xt)〉 )] = E [ β2HtL
2
( ‖∇gJt(xt)‖2 − 〈∇fIt(xt),∇gJt(xt)〉2
‖∇fIt(xt)‖2
)] . (48)
Note that this result is smaller than the original E[Γt].
Derivation of optimal Γ∗t and β∗Ht For a fixed learning rate α, we have
0 = ∂E[Γt] ∂βHt = E [ ∂Γt ∂βHt ] = E [ βHtL‖∇gJt(xt)‖ − (1− αL)〈∇fIt(xt),∇gJt(xt)〉 ] .
Thus, we obtain
β∗Ht = (1− αHtL)〈∇fIt(xt),∇gJt(xt)〉
L‖∇gJt(xt)‖2 ,
Γ∗t = − (1− αHtL)〈∇fIt(xt),∇gJt(xt)〉
2L‖∇gJt(xt)‖2 .

heading: D OVERFITTING TO REPLAY MEMORY
text: In the main text, we discussed a theoretical convergence analysis of continual learning for a smooth nonconvex finite-sum optimization problems. The practical continual learning tasks have the restriction on full access to the entire data points of previously learned tasks. Unlike taking expectation
over It ∼M and M ∼ P ∪ C, we have to compute on the given memory in the practical scenario. Then, we note that E[Bt|M ] 6= 0. Now we rewirte Equation 26 for the worst case as follows.
T sup‖∇f(x)‖2 ≤ 1 α(1− αL/2)
( ∆f + ∑ (Bt + Ct) + L
2 α2σ2f
) (49)
sup‖∇f(x)‖2 ≤ A√ T
( 1
c
( ∆f + ∑ (Bt + Ct) ) + Lc
2 σ2f
) . (50)
We note that ∑ Bt is a random variable, which is unpredictible, and choosing ∇fM (t) = ∇f(xt) over entire period is impossible. Then, the cumulative sum of Bt is increasing over T . Therefore, we conclude that for the overfitting to memory degrades the convergence rate of NCCL empirically.

Review summaries:
The authors propose a stochastic gradient descent algorithm with adaptive learning rates for continual learning providing an  analysis of convergence. The main idea is to formulate the problem as a finite sum of non-convex objective functions with each component of the sum corresponding to a different task. The authors claim that the use of adaptive learning rates allow them to better control the relative importance of different tasks. 

In this paper, the authors analyses the convergence rate of episodic memory-based continual learning methods. The authors formulate the continual learning problem as a nonconvex finite-sum optimization problem. Based on the analysis, the authors propose an adaptive learning rate scheduling methods to adjust the learning rates based on the gradients computed in each iteration. The results on several benchmarks show that the proposed method can achieve better results  than the baselines.

This paper provides a convergence rate characterization for a continual learning problem where the objective functions (for two consecutive tasks) are generally nonconvex and have a finite-sum form over data samples (which belong to current and previous tasks). The analysis uses the tools from nonconvex optimization, with a goal to find a stationary point for current and previous tasks. Under the setting of continual learning, the authors consider the standard replay memory based method, focusing on both the episodic memory and the replay memory with sample dropping. For the analysis, the authors first address two important types of errors: gradient estimation bias at time t and the catastrophic forgetting error. They show that for these two memory based methods, with a good initialization of replay memory, the gradient estimation error vanishes. They further show that in term of the convergence rate of previous task, i.e., $f$ in its context, the catastrophic forgetting error seems to be inevitable and can be even unbounded. To address this error, they further propose some adaptive learning rate schemes, which show some effectiveness in several experiments.