On the Stability-Plasticity Dilemma in Continual Meta-Learning: Theory and Algorithm
Authors: Qi CHEN
Changjian Shui
Ligong Han
Mario Marchand
Venue: NeurIPS 2023 poster (2023)
Keywords: continual meta-learning; transfer learning; stability-plasticity dilemma;

Abstract: We focus on Continual Meta-Learning (CML), which targets accumulating and exploiting meta-knowledge on a sequence of non-i.i.d. tasks. The primary challenge is to strike a balance between stability and plasticity, where a model should be stable to avoid catastrophic forgetting in previous tasks and plastic to learn generalizable concepts from new tasks. To address this, we formulate the CML objective as controlling the average excess risk upper bound of the task sequence, which reflects the trade-off between forgetting and generalization. Based on the objective, we introduce a unified theoretical framework for CML in both static and shifting environments, providing guarantees for various task-specific learning algorithms. Moreover, we first present a rigorous analysis of a bi-level trade-off in shifting environments. To approach the optimal trade-off, we propose a novel algorithm that dynamically adjusts the meta-parameter and its learning rate w.r.t environment change. Empirical evaluations on synthetic and real datasets illustrate the effectiveness of the proposed theory and algorithm.

On the Stability-Plastictty Dilemma in Continual Meta-Learning: Theory and Algorithm
Qi Chen' Laval University
Changjian Shui McGill University
Ligong Han Rutgers University
Mario Marchand Laval University
Abstract
We focus on Continual Meta-Learning (CML), which targets accumulating and exploiting meta-knowledge on a sequence of non-i.i.d. tasks. The primary chal- lenge is to strike balance between stability and plasticity, where a model should be stable to avoid catastrophic forgetting in previous tasks and plastic to learn generalizable concepts from new tasks. To address this, formulate the CML objective as controlling the average excess risk upper bound of the task sequence, which reflects the trade-off between forgetting and generalization. Based on the objective, we introduce unified theoretical framework for CMI. in both static and shifting environments, providing guarantees for various task-specific learning algorithms. Moreover, first present a rigorous analysis of a bi-level trade-off in shifting environments. To approach the optimal trade-off, we propose a novel algorithm that dynamically adjusts the meta-paaameter and its learning rate w.r.t environment change. Empirical evaluations on synthetic and real datasets illustrate the effectiveness of the proposed theory and algorithm.
1
Introduction
An essential goal in real-time intelligent systems is to balance stability (preserve past knowledge; minimize catastrophic forgetting (0) and plasticity (rapidly learn from new experiences; generalize quickly (2).. For addressing this dilemma, promising direction is to incorporate meta-learning
3 with Continual Learning (CL. (5H7), which constitutes the Continual Meta-Learning (CML)
problem. Specifically, CML sequentially learns meta-model from few-shot tasks as the common prior. Then, for new tasks, quickly adapts task-specific models with this prior. CML effectively enables balancing the task-level trade-off between learning new tasks and retaining previously acquired knowledge since the performance on previous tasks can be recovered with few additional samples.
8 8110
Despite being intuitive and technically sound, most related works CML have focused on improving empirical performance. There is still much room for exploration in the theoretical aspects. In particular, there is lack rigorous understanding on (1) which factors are important for stability and plasticity, (2) how to uddress the dilemma effectively by considering these factors.
To theoretically understand these questions, we need to characterize the sequential lsk-ggnnrattnng process. In fact, many CML approaches are based on the implicit assumption that the non-i.i.d. tasks are originated from a static task environment т, where μ4 T, Vt. In addition, recent works reveal that meta- to new environment
catastrophic forgetting often occurs when transferring and start trying empirically address the forgetting in shifting environments, such as 77 16] We take this case into consideration and formally define a more general CML setting, where at each time t task μ4, is generated from possibly shifting environment T, with μ4 ~ тr (the environment
12
Coorespondence to: qi.chen. ulaval.cc
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

static if 7; =. Vt). We found a meta-level trade-off exists in shifting environments, which further induces difficulty in controlling the task-level
trade-off, as discussed in See. 4.2
In this paper, we formally study the bi-level (task- and meta-) haaming-forgetting trade-off in CML to fill the theoretical gap. Compared with previous works, our contribution highlights are as follows:
Unified theoretical framework We first introduce a novel and unified theoretical framework for CML in both static and shifting task environments. For each task, the excess risk reflects the true model performance but is intractable. Therefore, we derive a unified form of the excess risk upper bound for various base learners, which contains optimization error with the generalization gap and could be estimated from observations. Based on these, we propose to control the Average Excess Risk (AER) upper bound of all the tasks as the learning objective in CML (shown in Sec. (3). This upper bound can be further decomposed as the optimal trade-off and the algorithmic regret.
trade-off We discuss the bi-level trade-off in shifting environments with an illustrative example in Sec. 4.1] We theoretically identify in Theorem 5.1 that: (I) Inside each environment, the task-level trade-off is affected by the task similarities, which reflects on the slot diameters and variances. (2) The path length and changing points representing environment similarities and non-stationarity dominate the meta-level trade-off. (3) Task and sample numbers are important to generalization. The optimal trade-off is achieved with a minimal upper bound of AER, so it's helpful to consider these factors for optimizing the meta- meta- parameter sequence.
Understanding the bi-level Bharning-forgetiin
Theoretically grounded algorithm We propose a novel algorithm (Algo. T for addressing the bi-level trade-off in shifting environments, which dynamically adjusts both the paraapaaaeeter and its learning rate when an environment change detected. Hence, the proposed algorithm can implicitly control the AER by minimizing the dynamic regret to approach the optimal trade-off. We derive a general bound for the proposed algorithm in Theorem [. Improved complexity factors and rates theoretically demonstrate the validity of the proposed algorithm for balancing the trade-off, as illustrated in Theorem 6. and 6..2 Furthermore, empirical results on various datasets show improvements in estimated bounds and superior performance compared to baselines, demonstrating that the proposed algorithm can incrementally learn from new environments while maintaining good trade-off.
performance on the previous ones, i.e., a
2
Related work
Due to the page limit, we only briefly discuss the most related works in this section. A more detailed discussion and comprehensive investigation of various settings are provided in Appendix H
Continual learning Traditional CL approaches mainly focus on addressing catastrophic forgetting. Some methods use regularization techniques, such as Elastic Weight Consolidation (EWC) 17 and Synaptic Intelligence (SI) [18) that aim to protect important parameters of a neural network from being modified during training on new tasks. Other methods like replay-based approach 19 20) store or replay previous task examples aid in preserving knowledge of old tasks. Another line of work is parameter isolation or dynamic architecture methods, which involve creating new network pathways or modules for each new task 21 22). Riemer et al. 7 first conceptualize the learning forgetting trade-off in CL as temporally maximizing transfer and minimizing interference by enforcing gradient alignment across examples, which is implemented using experience replay and Reptile [23 to approximate the gradient alignment objective with first-order Taylor expansion.
Meta-laarning Meta-learning aims for quick generalization, allowing for efficient learning of new tasks with limited data. The foundational framework of statistical meta-learning by Baxter [24] assumes tasks are i.i.d. sampled from a task environment. Amit and Meir (25) proposed PAC Bayes bounds with a joint training algorithm, which is not straightforwardl extendable to sequential learning. Chen al. (26) derived information-theoretic bounds for MAML-like algorithms suitable for sequential few-shot learning. These works assume i.i.d. conditions for both tasks and in-task data. To break the assumption, online meta-learning introduces two main approaches for learning non-i.i.d. sequential tasks. Batch-Within Ontiiee g [2 methods, similar to CML, learn each task under a statistical batch setting. However, the theoretical analysis is limited, and none addresses shifting task environments. Online- Seree--WihnnOOiiie
(OWO) (1 methods employ online algorithms as both base and meta learners. Khodak et al. [31] were the first to consider shifting environments for OWO, providing average regret bounds for gradient-based learners.
2

---

In contrast, we consider various statistical batch algorithms in addition to the gradient-based based ones as base learners. We further propose fine-grained algorithm w.r.t environment change that has an improved rate over the bound in [11] (although not directly comparable) for gradient-based base
learners, as discussed in Sec. 6.2 This improvement implies better learning-forgetting trade-off not considered in previous meta-learning literature.
Continual meta-learning FTML extends MAML
sequential learning using Follow The Leader (FTL) as the meta-learner, which requires storing all the previous tasks. MOCA [32 incorporates Bayesian Online Changing- print Detection (BOCD) to identify unknown task boundaries during the continual meta- meta-learning process. The above methods can address the task- trade- off under static task environment. However, a meta-level trade-off exists when facing shifting environments, He et al. [8] combines MAML with Bayes Gradient Descent (BGD), slowly updating mera-paaameters of small variance to stabilize the learning from non-i.i.d. sequential tasks. Caccia et al. loss.
13 address the environment shift with a soft modulation on meta-updates with the empirical [5), , and [16] incorporate additional memory with different environment shift detection methods to address the meta-level trade-off. []4] and [15 model the meta-paramele distribution with a Dirichlet Process Mixture Model (DPMM) and Dynamic Gaussian Mixture Model (DGMM), respectively, which can detect new environments and store the corresponding K meta-parameters with ( memory. [66] grows K subnets by detecting the environment shift with BOCD and stores M tasks from previous environments, thus having memory complexity of O + M).
Instead of the memory- approaches, we focus on the more challenging fully online experimental setting first proposed by Caccia et al. [33. Our algorithm consumes ((1) memory and better balances the meta-level trade-off in the online setting. In addition, we consider different levels of non-stationarity and more environment shifts compared to previous works.
Theory on the paaiilitypplasticie dilemma Raghavan and Balaprakash (33 explicitly study the task-level trade-off in continual learning by formulating the problem as a two-player sequential game and prove the existence of a balance point for each task. However, the cost function based on empirical loss without considering generalization on unseen data. Based on NTK (34] regime, the generalization and forgetting property of orthogonal gradient descent (35] are separately studied in (36] and (77 for continual learning. To the best of our knowledge, we are the first theoretical work studying the aubhiltt--llsttiiin dilemma in CMI. We also first provide theoretical framework for CML in static and shifting environments, offering a formal understanding of the bi-level trade-off.
3 Problem setup
Let us consider a sequence of different task distributions {11)T= defined on the same example space Z X' x y with T - co. Specifically, at time t, the task Pe is generated from a possibly shifting environment Te with μ4 ~ Tr, which is static if T. = T, Vt. Then a dataset of m, examples T S, | are i.idd sampled from μt, where S, 14," In CML, we have two kinds of parameters: model parameter and meta- parameter, which are learned through base learner and meta learner, respectively. A visual representation of the CML process is provided in Fig. T Let the meta- parameters be defined on the same support li for all the tasks. Additionally, we assume that the same parametric hypothesis space W is used across all tasks with non-negative bounded loss function e: W x Z + [0, 1]. Given any model parameter w E W. the true risk and empirical risk of t-th task are defined as Cy, (w) del Ez~u, ((w, Z) and Ls, (w) del 1 Em ((w, Zz). To motivate the CML setting mentioned above, we also provide an analysis of how to apply CML to real-world examples like online recommendation systems in Appendix G.2
3.1 Base learner
At time 1, base learner A takes the task data St and the meta meta- parameter u, E l/ that represents the prior
knowledge learned from previous tasks as the input then outputs the model parameter W A(u, St). Specifically, A is characterized by a conditional distribution?] PW Pwi as in [38 39]. We further define the corresponding (expected) excess risk on task t as the expected gap between the true risk of the learned hypothesis W, and the optimal true risk:
It will be delta function if A(ue, Se) deterministic.
3

---

Env f
Env 7i
Current task data 8y
Tosk
Task
Task ji
ML.
Abuen
Frtor indwledge ourmet tank
prior knowledge
Data S
Data S
Sq
for newt task
Austs
Acse
لابي
Acme
Acazz
Leurned hypohheaa curuerl
Wr
W2
Figure 1: Illustration of Continual Meta-Learning (CML) process, At each time t, the CML algorithm ACML (composed of the meta learne and the base learner) takes the current task data Sy and the meea--aaameetr (prior knowledge) u, learned from previous tasks as input. Then, it outputs the learned hypothesis W; of the current task and the updated meta- parametereeeer u4+1 for the next task.
Rexcess (A, Ue) def Es, BWW, ~Pw, Seina (W: - Lyu, (wx]) w.. arg wiw Luy (w).
The excess risk of (4t is thus explicitly determined by the meta-parameter u, and the base learner, where is provided by experts random guesses in single-task learning. Although reflecting the true model performance, the excess risk is intractable due to the unknown distribution (4g-
The following theorem gives a unified form of excess risk upper bound that applies to common base learners such as Stochastic Gradient Descent (SGD), Stochastic Gradient Langevin Dynamics (SGLD), Regularized Loss Minimization (RLM), and Gibbs algorithm. In contrast to the upper bounds that contain the empirical risk, it avoids the task data access for the meta-lcarmn and can thus be used to design new CML algorithms. See detailed proof in Appendix [.5]
Theorem 3.1. For any & [T], assume that Lu, (-) has a-quadratic growth (see Definition A.2), then whenever the buse learner is SGD, SGLD, RLM, or the Gibbs algorithm, there exists fz(-) that gives
0. Rercess (excessAA we) fe(we) ne. (a3.+ bllg, well 112 + + e0 +D.) K8,, ct; B2, D. R a
Be
(1)
The meta-parameter U4 (Be, Qc) decomposes into initialization or bias or and a learning rate Be (if A (SGD, SGLD)) or a regularization coefficient (if {RLM, Gibbs}). Moreover, we denotes the (single) output for the (possibly randomized) base learner, and Eg def 2a lwl - EW&ll characterizes the randommess of the output. Finally, a and b arr constants, and Ez, Kt, De are are functions of the task sample size m, that characterize the base learner (see Appendix B and D).
Remark 3.2. (a) The above bound could be estimated from observation, so we can use it to design meta-learning algorithms control the excess risk. (b) Besides learning the initialization/bias, the corresponding learning rate/regularization coefficient should be further considered to control Rexeess (c) ft is convex w.r.t u, (proved in Appendix B.6). (d) This upper bound gives an explicit form of task- level trade-off that depends on the meta-parameterr where large 35 represents conserving less model prior (larger forgetting) and learning more from data to obtain the model wt. The similarity l|o, - w,ll between the model prior and the new task can affect the choice of 3e for a better generalization.
3.2
Meta learner
Since the tasks sequentially encountered without the i.i.d. assumption and the excess risk upper bound (cost function) fo is convex, we can naturally consider the meta-lcarning process as a repeated game, following the Online Convex Optimization (OCO) regime 40]. At each time f, the meta-learner first selects ue E Z/ with prior knowledge learned from previous tasks, then the base learner outputs wi given Uy and dataset St. After that, the cost function value fo is revealed. The goal of the meta learner is to select a sequence of meta- mnta-eera u1. So as to minimize the regret over rounds.
Static task environment In static environments, the task distributions μ4 VI E [7] are assumed to sampled from a fixed environment т. The corresponding static regret defined as the gap between the total cost of U and that of optimal meta parameter in hindsight ui::

---

RT (UITT
def - fe(u)) E fe(u)), ) uj o
arg min Et= f((u).
The hindsight wi converges to the true minimum u" w.r.t T as - oc. So the task-level trade-off can be well-balanced by designing algorithms with sub-linear regret to approach u".
Shifting task environment In more general CML setting where the task environment T. can change at each time t, using a meta-learner designed to obtain sub-linear static regret will suffer a shifting comparator. As a result, the optimal ur may not converge can be vacuous when T -> +00, which induces the meta-level forgetting. See formal justification in Appendix [A.22]] To this end, we assume the horizon T of the sequential tasks can be divided into N slots, and the reth slot contains M, tasks. We further assume that the environment does not change with within each slot. The N optimal priors, in hindsight, are noted "i.N- Consequently, we define a more versatile dynamic regret as:
fixed point, and -i=1 fe(u))
He (ui,) En Ex Mr [fn, - fn, (u,)], UG = arg min M,
1 M., (u,
m= M, = Nf + T, the definition is equivalent the conventional dynamic regret. If N + 1, recovers the static regret. To balance the meta-level trade-off, we need to find algorithms with sub-linear dynamic regret to sequentially approach the optimums in N slots (environments).
Given En
3.3 Continual Meta-Learning objective
In practice, we aim to train the task-specific model with few-shot data and hope that the model will generalize on unseen data. Hence, we formulate the CML objective as selecting u, at each time to ensure a small Average Excess Risk (AER) upper bound for the task sequence {po)T= which is defined as follows given the base learner A:
T
T
M
1 Reynamiic (ui.N) Rexcess (A, u1) S T Σ ((u))= = 7 Re
1
AERT def
Σ
M
(n,((un)))
We adopt the dynamic regret defined in shifting environments since it can recover the static setting w.l.o.g. Considering the two terms in the above upper bound of AER, the CML objective is two-fold: (a) design an appropriate online meta-learner minimize the dynamic regret. (b) choose the optimal split of the 7' tasks to V stationary slots. Based on this objective, we propose a novel continual meta-learning framework and provide corresponding theoretical analysis in the following sections.
4 Balancing bi-level learning-forgettnng trade-off
4.1 An illustrative example
The excess risk upper bound provides the intuition that we can quickly learn a new task similar to our prior knowledge by relying on this prior. In this case, the initialization/bias Ói (model prior) is close to the base learner output wy (i.e., a small distance || - we|l )1,), and the excess risk bound will be small. So we will elaborate on the ceariing-forgettin example of shifting environment visualized Fig. 2 based on the following definitions of task similarities characterized by the distances in the model parameter space [30].
D
W
8 D
trade-off on an
D/2
P D
Definition 4.1. Let us denote W as the set of all the learned Let D be the diameter W w.r.t norm ||- ||: Vw, v E W, || - u|l < D. In shifting task environments, we denote D, the corresponding diameter for n-th slot. Assume W convex set containing all the possible model parameters. Then let D be the diameter of W: Vw, v W. ||w ull 5 D.
model parameters: W [w:- A(4,, St) ( UO).
Figure 2: Illustration of parameter spaces in shifting environment, where W,, W and D, D, D,, are de- fined in Def. 4.1 d; is the n-th slot hindsight.
The task environment in Fig. changes within three slots (i.e., three circles with diameters Dus in light red). The dark red point is denoted of the optimal initialization in hindsight for each slot.
5

---

Purple points W13 are the learned model parameters in different slots. In static environments, CML can access additional few-shot data to address the task-level forgeeing. Assume the models in n-th slot can recover performance (without forgetting) of similar tasks within a distance Dn/2. Then, the optimal 6, learned by CML can cover all the tasks in the slot with diameter D,.. For instance, the two tasks in the first slot, shown in Fig. have a large distance ||w- wyll > D1/2. Directly adapting from one to another suffers catastrophic forgetting. However, keeping the optimal prior Φi can address the forgetting, where || - wi || < / and | - w>ll < /
However, this does not work in shifting environments. If we view three slots as one static environment (with large variance), the optimal overall model prior 6 will be close to the origin, and the diameter is D, which is much larger than any one of the slot D A larger diameter (e.g. - - > 1|Ø3 implies the need for more samples for each task to avoid forgetting, which is often not satisfied. A theoretical interpretation is provided in the discussion following Theorem 66.] To address this, in the next session, we propose an algorithm that dynamically adapts the meta-parandn paaamaareeeerr when environment change occurs so as to rapidly reconstruct meta-knowledge in each static slot. Moreover, is not as catastrophic as directly adapting model parameters since the forgetting is w.r.t meta-knowledge, which is constrained in core set of oi.T, which has diameter much smaller than D.
(0j-wyll) wsll)
4.2 Dynamic algorithm
As discussed in the last section, it would be prob- lematic in a shifting environment if the meta- learner adopts the same updating strategy in the static setting. Specifically, if we aim to opti- mize the static regret, the learning rate of meta- parameter decays with (1/t)) for Follow The Leader (FTL) 41 and (1//V)) for Online Gra- dient Descent (OGD). Clearly, such strategies hardly learn from new tasks in shifting environ- ment. On the other side, constant learning rate of the meta--aarameter is often adopted for op- timizing the regular dynamic regret [40]. This strategy could perform poorly when the envi- ronment only occasionally changes with huge step, whereas the theoretical optimal learning rate becomes large. A large learning rate causes the meta learner to easily forget the previous tasks, making convergence difficult inside each slot. We offer theoretical comparison with this in the discussion of Theorem 6.2
Algorithm 1 Dynamic Continual Meta-Leurning (DCML)
Convex W, 0 W,r;0 initial learning rate (2o, p}. if 3 a pre-trained model du E W then di = cho end 0,K for = 1 1' do
Input:
Sample task distribution: H4 ~V TTg Sample dataset S ~ pt:":: Learn base parameter en = S.),,
egg, K-step SGD RLM
2e = 6. K
& o Ls, (o) ))
Oc.
== - AV my argmin (w)
Ls. -
6
||u
Estimate excess risk upper bound fe Eq. environment change detected: 72
if
then
M.. k. 1 1,70 P
clse A: == k 1, = Vo/V/t
end if
Update paraa-arraeter:
V.((()) = (Ne(a- Mi. Pte.teg
To balance the learning and forgetting trade- off of meta-knowledge, we proposed the Dy- namic Continual Meta-Learning (DCML) algo- rithm (see Algo. D that dynamically adjusts the learning rate of the meta-parameter. When
8:41 Ilr(w 2x v.(u))))). ke:
041 (1
2bm )o: 1 2heer
A P ca(on mith
end for
changing point is detected, the meta-learning
rate it adapts to a large hopping learning rate p. then relaunches the decay, in O(1/V from To in each slot. Besides, the meta- parameter itself is also adaptively updated. According to 2bx+7e W, in Algo. adjusting 3r and % represent the explicit con- trol task-level and meta-level trade-off, respectively. A corresponding discussion is provided in Appendix G. For a better understanding of DCML, we present a detailed introduction to it using SGD as the base learner in Appendix. G.3
Φi+1 (1 2bx.7e
3. " )0, + B.
Finally, the changing point can be detected with a broad class of Out-OOf-istributti (OOD) detection methods, e.g., Bayes Online Changing-poin Detection (BOCD) 42) loss threshold [13, or setting
fixed-length sliding window. Specifically, when the window size equals 1, constant learning rate set to the meta learner, which recovers optimizing the typical dynamic regret as in 40)

---

Main theorem
We present general theorem for the proposed DCML framework, which could be deployed for various base learners with the same excess risk upper bound form as Eq. (
Theorem 5.1. Consider both static and shifting environments. If the excess risk's 's upper bound of the base learner A(ut, S.) can be formulated as a unifted form Eg. 47. then, the AER of DCMI. (in Algo. 7 is upper bounded by:
2 AERT
An
3
D Diaax T
ValbV? t. co + E
D V M, - 1+
2P
T
2T
n=1
optimal trade off in hindisight
average regret over slots
regret envrrnment shift
Here, Ni, -Etn Kn, A, kk No, & no where the subscript n, indicates k-th task in n-th slot. The optimal mela-parameter in hindsight of n-th slot is u = (8% (%) and the path length of N Munk Wn,k is the weighted average of the base Nn
My
slots is P - Ill, + 1. 0n >itn
Mn
learner outputs within the slot. 5 / (bV2 + + co)/a, where V22 = -EEE =1 Kr.*
K.. 1= Wn.k k l1
is the variance in n-th slot and en = > Kn.l En, Moreover, Gn is the maximal gradient norm of the cost function, Dn is the diameter of meta- pretaeparraeterss in nith slot, and Dias= = max 1 Jn=
Ki
The above theorem can be applied to static and shifting environments, where the proof is provided in Appendix D.2] For comparison, also derive general theorem from static regret in Appendix [D.]]
Important factors for bi-level trade-off (a) The first term in Theorem 5.1 indicates the optimal trade-off can be achieved with the N optimal meta-pant meta--araamttrs, which is affected by the task simi- larities within each environment (slot variance V/²) and the environment changing points. (b) The second term the average static regret over slots, which related to the task similarities
the slot diameter Dn and represents how well the algorithm can balance the task- trade-off, (c) The last term is the regret w.r.t the environmental shift, reflecting how well the algorithm can address the meta-level trade-off. and the non-stationarity (how frequently the environment changes).
affected by the path length Pr, determined by the environment similarities
Remark 5.2. The above theorem has considered different sample numbers for each task. We can the best initialization (bias) in hindsight (+7) is related to the weighted average of the task models Wn,k in n-th slot through K,,k. E.g., for SGD, Kn, = / /I/Ka + 2/m,,ka implies that the task trained on more samples will have smaller weight. Since it's easier to recover model performance for the tasks with more samples, less information on these tasks conserved in the meta- knttll-n.wleddee..
Results on specific base learners
Theorem 5.I provides general theoretical guarantees without specifying the base leaner. In this section, we discuss the theorem depth with two typical base learners: SGD within the meta-initialization setting and Gibbs algorithm for the meta-regularization.
6.1 Gibbs algorithm
Theorem 6.1. Let W C Rdd, Assume that the loss E((,z) [0, L--ipschitz V2 E Z and that C has gequadratic-rrwwe for all E [T]. Let Wi = AGuso (3r, or, St) be the output of the Gibbs algorithm (Definition B.2) on St, where de is the mean of a prior Gaussian ((or, of with at = m+ 114 1,-1/22 and B, is the inverse temperature. Consider DCML (Algo. I and further assume that each slot has equal length M and each task uses the sample number m. Then we have
AERT Gibss E -
VMN + vP-
1
Vn
MVN
m
The detailed proof is provided in Appendix E. and the static AER bound is in O ((V + +1)++/VT m 1/4
We also proved in Appendix E.2 that As we claimed before, when N (which means the environment is static), the dynamic AER bound recovers the static AER bound.
7

---

Benefits of DCML Arbitrarily setting the prior mean 62. the excess risk for single-task learning with Gibbs algorithm has an upper bound in O (LD + 1/m-, where D is the diameter of the parameter space. While the static AER becomes O((V 1)m -1/4) with rate O(I/VT). Since V the variance of all the outputs of the base learner, we have V S Đ S D. which illustrates the benefits of the proposed DCML algorithm. Moreover, in shifting environments, the bound is further improved in Theorem 6.1 where the complexity factor is decreased by NV Σx= Vn S V with rate O(L/VM) M). This means that by considering environment change, DCML can achieve the same AER with smaller M (fewer tasks), i.e., faster-constructing meta-knowledge in new environments.
6.2 Stochastic Gradient Descent (SGD)
Theorem 6.2. Let W C Rd. Consider that E(-, 2) is convex, B-smooth, L-Lipschitz Y2 E 2. Assume that Lu, (.) has e-quadratie-grower for all t E [T]. Let SGD be the base learner for each task where it outputs we = Ascu (7, 6s, St) with learning rate T and initialization dr. Consider DCML (Algo. for the SGD cost function. Further, assume each slot has equal length M, and each lask uses the sample number in and the same number of updating steps K. Then we have
((1
VMN + vn
-
AERSOD E o
VR
MVN
m
==1
The detailed proof is provided in Appendix E.4 and E.6 for each task, so the related rate of the base learner is ( OVVI/K + +1/m). which is determined by both the step number and the sample size. Let V E Vn- CML focuses on fast learning new tasks and quickly recovers the model performance on past tasks with few-shot examples (m is small), Hence, the optimal trade-off is dominated by the average deviation over slots V and the path length P* where P* reflects the environment similarities and the non non-stationariiyy
The CML setting uses offline batch-truining
Static environment If the environment is static, i.e., N 1, we have P 1, M = T. The bound
1 becomes in O (IV + D + m
which recovers the static AER bound in Appendix E.5
Shifting environment When the environment occasionally changes with a large step, as discussed in Sec 4.2 N is small, and M, pa is large. The proposed bound has an improved rate O /LLVM MM) on P compared to O(V + VM + V ps
NM an equivalent form the task average regret bound in [31] A more detailed comparison w.r.t (31 has been discussed in the proof for both static and dynamic AER. Similar to Theorem [.. the dynamic AER is improved w.r.t. the static AER with the improvement complexity factor by V < V. In addition, if the environments differ lot and frequently change, N, P' is large, and M is small. It's impossible to obtain a small AER, as demonstrated in the experiment the Synbols dataset in Tab. I
Experiments
We first conduct analytic experiments synthetic dataset to offer in-depth understanding of the theoretical counterpart. Then, we test the proposed algorithm on a recent CML benchmark - OSAKA [3), which empirically considers shifting environments a large scale. The experimental results validate the proposed theory and illustrate the superiority of DCML. shifting environments.
7.1 Moving 2D Gaussian
We introduce simple synthetic dataset, where the data is generated by the following strategy. Let the environment be a 2D Gaussian distribution with a moving mean. Initially, To (6 12) with कं (-6,6) Then time point t, т, NV I12) updated by: おū = - + (1,1) with probability p and 0ū = Φं_ with probability - p. Then we have N changing points {tn J At each time step, we first sample wi 7; from the current environment т as the mean of the task distribution μe = [w,,, 0.1I2), which is also 2D Gaussian. For task t. we sample m examples Str 14th as train data, m' samples Sif pi as test data. Then the corresponding empirical risk is
8

---

ted Iedireanantt ant Bhdligt predkteed
Avemoo 1r0 1o00mmn d 10000
0.89
0.66
0.66
0.84
0.0
0.62
dows)
MAML CMAM
DCV, (oraci))
0.81
0.00
0.4
Us
0.8
(a)
(b)
Probabillty
Figure 4: Average test acc at final step ing example, (b) visualization test loss, static and dy- t 10000 w.r.t environment change namic AER, learning rates of base and meta learners.
Figure 3: Moving 2D Gaussian mean estimation: (a) track-
probability p on the OMF dataset.
(w) -x= | 12 SGD uses oe as initialization and a learning rate to optimize this objective, and outputs Wy AsaD (?,, Φt, (. Since Wy is obtained from limited data, it can be far away from w²_ If the environment shifts to the n2thh slot at t, then the predicted environment mean 0ú -t,. We denote o; mean of n-th slot as 6 1 2imt, fn+111 W/.
or. the mean of the actual environment, and the hindsight environment
In Fig. (a), we visualize an example of tracking the environment shifts, where the task mean estimation is wt: the output of SGD. The other three terms are described above. We further visualize the test loss, the dynamie, and the static AER bounds Fig. (b). The red dotted lines represent the actual environment-change than the dynamic AER, consistent with the result in Theorem 6.2 In addition, the evolving trend of dynamic AER is the same as the average test loss, which does not hold for static AER. We also find that the learning rate of the initialization Φe (meta Fig is scheduled by the changing points, and the base learning rate is adjusted automatically by the algorithm. Additional experimental settings and results are provided in Appendix
points. We observe that the static AER is much larger
7.2 OSAKA benchmark
Experimental set-up OSAKA considers task-agnostic setting of unknown task boundaries and simultaneously switches the task and environment with low probabilities. We slightly modify the setting to introduce more non-stationarity by always switching to new task and changing the environment with probubility p at each timestep. We pre-train a meta-model as initialization from one environment. The new environment is selected with probability 0.5 as the pre-trained one and 0.25 for each of the two unseen environments, consisting of OOD tasks. We further test DCML on two representative datasets in OSAKA. For Synbols characters from an alphabet on randomized backgrounds. During CML time, the model is exposed to the pre-trained environment, new alphabet for character classification, and heterogeneous environment that conducts font classification, which induces significant concept shift. For Omniglot- MNISS--asshionMNISTTT (OMF), we pre-train the meta-men model the first 1000 classes of Omniglot 44. Then, it is exposed to the full Omniglot dataset and two unseen datasets MNIST (5) and FNSS [46 at CML time. More details and baselines are deferred Appendix F.I.1
43 dataset, the model is pre-trained to classify
We tested 5-level of non-stationarity with = (0.2, 0.4, 0.6, 0.8, 1.0) for OMF and for Synbols we p (0.2, 0.4, 1.0). The average test accuracy of all encountered tasks is used the performance metric, which reflects the AER. In addition, we denote DCML (oracle) for the algorithm as offering correct enwiromment-cchaniinn points and DCML (window) as using fixed-length sliding window.
The average test accuracies at the last timestep for environments and every single environment are reported in Tab[T for OMF with p = 0.4 and Synbols with 0.2. Additional experimental results can be found Appendix F.2.2] Clearly, DCML constantly outperforms all the baselines with improvements of 2% points on OMF data and 0.7% points on Synbols data compared to the best baseline method. comparison w.r.t powerful baselines is presented in Fig for OMF data, where the average test accuracy over rounds in three environments is visualized separately.
Results

---

Table 1: Average test accuracy (%)
OMF & Synbols datasets of OSAKA benchmark
pMP.p=D
SYNBOLS, p
MODEL
ALL ENV.
OMNIGLOT
MNIST
FMNIST
ALL ENV.
ALPHA.
NEW ALPHA.
FONT
FINE TUNING
10.32 1.3
11.24 2.2
0.84
10.3+
25.34
25,44
25.1
25.2= 0.5
METACOG
0.9
54.4+
1.2
25.6+ 0.9
2.49+
0.8
0.9
2.8
25.1=
METABGD 8
54.54 7.1
70.3+
8.5
40.24 5.5
36.8+ 5.8
29.9+
31.8+
28.1
27.5+ 3.6
ANIL E+
0.3
99.1
0.1
73.9+
6.12+
6,.5+
77.6
0..640.2
32.7=
MAMI
83.8+ 0.4
99.3+
0.1
75.4+ 0.1
61.0+
76.74
96.8+ 0.1
73.140.1
40 40.5=
CMAML
85.9+
98.1= 0.3
83.8+
0,92+
6.59+
76.2
3.2
37.9= 2.4
(OMALE)
86.51 0.7
97.42 0.6
85.74 2.6
65.92 1.4
77.22 0.5
96.02 0.3
73.42 0.1
42.42 0.6
(CML(WWINDO))
97.2.1 0.7
86.81
66.7.1
77.41
73.8.1
42.41
1.00
6196
0164
Average Tee
0.66
0.00
0.44
0.00
(MAV
0.00
DCVL sonade
(CVV
0/66
DC1L crudi
0134 (erdin
CO4. Suaces
(a)
(b)
(c)
Figure 5: Average test accuracy (a) Omniglot, the pre-trained environment, (b) MNSSS.
and (c) MNIST, the two unseen environments where the environment shifts with probability = 0.2.
Analysis of learning and forgetting In Fig. 5 for OMF data, MAML and ANIL do not suffer forgetting since they never update meta veeta-aramettrs. The proposed algorithm forgets a bit more than CMAML but learns much faster in new environments, illustrating better trade-off. The fine-grained adjustment for the meta-learning rate makes it possible to quickly reconstruct meta-knowledde w.r.t environment change and constantly learn in new environments. On the other hand, MetaBGD and MetaCOG perform poorly since using BGD hinders acquiring new knowledge. All the methods perform worse Synbols data in Tab. where each environment is more diverse than OMF, and the environments differ lot, indicating large D,, and p Moreover, of CMAML on Synbols. Since CMAML uses empirical loss for modulation, it is prone to overfitting and can cause difficulty of convergence inside each slot when D, is large, as discussed in Sec. 4.1
observe performance drop
Analysis of stability w.r.t shifting probability We conduct an ablation study OMF w.r.t environ- ment change probability in Fig. The results demonstrate the stability of the proposed algorithm and the increase performance w.r.t p. Since the environments have high similarities in OMF, the meta-model is better learned by seeing more tasks given the fixed time steps with a larger
Analysis of environment change detection Empirical results suggest that DCML (window) per- forms better than DCML (oracle). This is reasonable when slots of small length exist where adapting to new environments causes additional context-switch costs (justified in Appendix F22.I. Given the changing probability p, the expected slot length 1/p, used as the sliding window size. In practice, though p is unknown, papammerrr searching for the one- -indinnnnional window size is much easier. Because the similarity between any two environments can differ a lot, it's hard to find a single optimal hyper- peremmereeterr for change detection methods like BOCD loss threshold.
8 Conclusion
This paper theoretically studies the stability and plasticity dilemma in CML. Based on the novel AER objective, proposes continual meta-lea framework both static and shifting environments. The proposed DCML algorithm can quickly reconstruct meta-knowlede to alleviate forgetting and quickly adapt to new environments when change occurs. The corresponding theory provides tighter bounds and more flexible base learner selections. In addition, adaptively learning the meta-parameter can facilitate the training process in deep learning. Empirical evaluations on both synthetic and real datasets demonstrate the superiority of the proposed method.
10

---

Acknowledgments and Disclosure of Funding
We appreciate constructive feedback from anonymous reviewers and meta-reviewers. This work is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant, the Collaborative Research and Development Grant from SSQ Assurances and NSERC, and the China Scholarship Council.
References
[1] Michael McCloskey and Neal J Cohen. Catastrophic interference in connectionist networks: The sequential learning problem. In Psychology of learning and motivation, volume 24, pages 109-165. Elsevier, 1989.
[2] Gail A Carpenter and Stephen Grossberg. A massively parallel architecture for a self-organizing neural pattern recognition machine. Computer vision, graphics, and image processing, 37(1): 54-115, 1987.
[3] Sachin Ravi and Alex Beatson. Amortized bayesian meta-learning, In International Conference on Learning Representations, 2018.
[4] Chelsea Finn, Picter Abbecl, and Sergey Levine. Model-agnostic meta-learning for fast adapta- tion of deep networks. In ICMI., 2017.
[5] Matthias De Lange, Rahaf Aljundi, Marc Masana, Sarah Parisot, Xu Jía, Ales Leonardis, Gregory Slabaugh, and Tinne Tuytelaars. Continual learning: A comparative study on how to defy forgetting classification tasks. arXiv preprint arXiv: (tt:::9990008888 2(6):2, 2019.
[6] Chen Zeno, Itay Golan, Elad Hoffer, and Daniel Soudry. Task agnostic continual learning using online variational bayes. arXiv preprint arXiv:/803: 10123, 2018.
[7] Matthew Riemer, Ignacio Cases, Robert Ajemian, Miao Liu, Irina Rish, Yuhai Tu, and Ger- ald Tesauro. Learning to learn without forgetting by maximizing transfer and minimizing interference. arXiv preprint arXiv:1810.1191 2018
[8] Xu He, Jakub Sygnowski. Alexandre Galashov, Andrei A Rusu. Yee Whye Teh, and Razvan Pascanu. Task agnostic continual learning via meta learning. arXiv preprint arXiv: 1906.05201, 2019.
[9] Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online meta-learning. In International Conference on Machine Learning, pages 1920-1930. PMLR, 2019.
[10] Antreas Antoniou, Massimiliano Patacchiola, Mateusz Ochal, and Amos Storkey. Defining benchmarks for continual few-shot learning. arXiv preprint arXiv:2004.11967, 2020.
[11] Mengye Ren, Renjie Liao, Ethan Fetaya, and Richard Zemel. Incremental few-shot learning with attention attractor networks. Advances in neural information processing systems, 32, 2019.
[12] Sung Whan Yoon, Yeon Kim, Jun Seo, and Jackyun Moon. Xtarnet: Learning to extract task-adaptive representation for incremental few-shot learning. In International Conference on Machine Learning, pages 10852 10860. PMLR, 2020.
[13] Massimo Caccia, Pau Rodriguez, Oleksiy Ostapenko, Fabrice Normandin, Min Lin, Lucas Page-Caccia, Issam Hadj Laradji, Irina Rish, Alexandre Lacoste, David Vázquez, et al. Online fast adaptation and knowledge accumulation (osaka): new approach to continual learning. Advances in Neural Information Processing Systems, 33: 33:16532-16545, 2020.
[14] Ghassen Jerfel, Erin Grant, Tom Griffiths, and Katherine A Heller. Reconciling meta-learning and continual learning with online mixtures of tasks. Advances Neural Information Processing Systems, 32, 2019.
[15] Qiang Zhang. Jinyuan Fang, Zaiqiao Meng, Shangsong Liang, and Emine Yilmaz. Variational continual bayesian meta-learning. Advances Neural Information Processing Systems, 34: 24556-24568, 2021.

---

[16] Zhenyi Wang, Li Shen, Tichang Duan, Donglin Zhan, Le Fang, and Mingchen Gao. Learning to learn and remember super long multi-domain task sequence. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 7982-7992, 2022.
[17] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Frrabska-Barwinskeee et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114(13)33521-33 2017.
[18] Friedemann Zenke, Ben Poole, and Surya Ganguli. Continual learning through synaptic intelligence. In International Conference on Machine Learning, pages 3987-3995, PMLR. 2017.
[19] David Lopez-Paz and Marc' Aurelio Ranzato. Gradient episodic memory for continual learning. Advances in neural information processing systems, 30, 2017.
[20] Hanul Shin, Jung Kwon Lee, Jaehong Kim, and Jiwon Kim. Continual learning with deep generative replay. Advances in newral information processing systems, 30, 2017.
[21] Jachong Yoon, Eunho Yang, Jeongtae Lee, and Sung Ju Hwang. Lifelong learning with dynamically expandable networks. arXiv preprint 17Xiv:1708.015444 2017.
[22] Jonathan Schwarz, Wojeiech Czarnecki, Jelena Luketina, Agnieszka Grabska-Barwinska. Yee Whye Teh, Razvan Pascanu, and Raia Hadsell. Progress & compress: A scalable framework for continual learning. In International Conference on Machine Learning. pages 4528 4537. PMLR, 2018.
[23] Alex Nichol and John Schulman. Reptile: a scalable metalearning algorithm. arXiv preprint arXiv:1803.02999, 2(3))4, 2018.
[24] Jonathan Baxter. A model of inductive bias learning. Journal of artificial intelligence research, 12:149-199 2000.
[25] Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended pac-bayes theory.
In International Conference on Machine Learning, pages 205-214, 2018.
[26] Qi Chen, Changjian Shui, and Mario Marchand. Generalization bounds for meta-learning: An information-theonn analysis. Advances in Neural Information Processing Systems, 34, 2021.
[27] Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms. arXiv preprint arXiv: 1803.099,, 2018.
[28] Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to-ler to-le stochastic gradient descent with biased regularization. In International Conference on Machine Learning, pages 1566-1575. PMLR, 2019.
[29] Pierre Alquier, Massimiliano Pontil, al. Regret bounds for lifelong learning. In Artificial Intelligence and Statistics, pages 261-269. PMLR, 2017.
[30] Maria-Florina Balcan, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees for gradient- based meta-learning. In International Conference on Machine Learning, pages 424 433. PMLR, 2019.
[31] Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Adaptive gradient- based meta- learning methods. arXiv preprint 1rXiv:1906.000 02717, 2019.
[32] James Harrison, Apoorva Sharma, Chelsea Finn, and Marco Pavone. Continuous meta- without tasks. Advances in neural information processing systems, 33:17571-17581, 2020.
[33] Krishnan Raghavan and Prasanna Balaprakash. Formalizing the generalization-forgette trade- off in continual learning. Advances Neural Information Processing Systems, 34:17244-17297,
2021.
12

---

[34] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[35] Mehrdad Farajtabar, Navid Azizan, Alex Mott, and Ang Li. Orthogonal gradient descent for continual learning. In International Conference on Artificial Intelligence and Statistics, pages 3762-3773. PMLR, 2020.
[36] Mehdi Abbana Bennani, Thang Doan, and Masashi Sugiyama. Generalisation guarantees for continual learning with orthogonal gradient descent. arXiv preprint arXiv:2006. 1942, 2020.
[37] Thang Doan, Mehdi Abhana Bennani, Bogdan Mazoure, Guillaume Rabusseau, and Pierre Alquier. A theoretical analysis of catastrophic forgetting through the ntk overlap matrix. In International Conference on Artificial Intelligence and Statistics, pages 1072-1080. PMLR, 2021.
[38] Ankit Pensia, Varun Jog, and Po-Ling Loh. Generalization error bounds for noisy, iterative algorithms. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 546-550. IEEE, 2018.
[39] Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. In Conference on Learning Theory, pages 1774-173. PMLR, 2017.
[40] Elad Hazan et Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4): 2016.
[41] Shai Shalev-Shwartz al. Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2):107-194, 2012.
[42] Ryan Prescott Adams and David JC. MacKay. Bayesian online changepoint detection. arXiv preprint arXiv:0710.3742,, 2007.
[43] Alexandre Lacoste, Pau Rodríguez López, Frédéric Branchaud-Charonr Parmida Atighehchian, Massimo Caccia, Issam Hadj Laradji, Alexandre Drouin, Matthew Craddock, Laurent Charlin, and David Vázquez. Synbols: Probing learning algorithms with synthetic datasets. Advances in Neural Information Processing Systems,
2020.
[44] Brenden Lake, Ruslan Salakhutdinov, Jason Gross, and Joshua Tenenbaum. One shot learning of simple visual concepts. Proceedings of the annual meeting of the cognitive science society, volume 33, 2011.
[45] Yann LeCun. The mnist database of handwritten digits. hilp://yann. lecun. comfexdb/mnist// 1998.
[46] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Jun- young Chung. David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster in starcraft using multi-agent reinforcement learning. Nature, 575(7782):350-33 -344,0 2019.
[47] Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals. Rapid learning or feature reuse? towards understanding the effectiveness of maml. arXiv preprint arXiv: arXiv:1909009157 2019.
[48] Aolin Xu and Maxim Raginsky. Information- theooretc analysis of generalization capability of learning algorithms. In Advances in Neural Information Processing Systems, pages 2524-2533, 2017.
[49] Maxim Raginsky, Alexander Rakhlin, Matthew Tsao, Yihong Wu, and Aolin Xu. Information- theoretic analysis stability and bias of learning algorithms. In 2016 IEEE Information Theory Workshop (/TW), pages 26-30. IEEE, 2016.
[50] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. International conference on machine learning, pages 1225-1234. PMLR, 2016.
13

---

[51] Shai Shalev-Shwart and Shai Ben-Davin Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[52] gwgundersen. Bayesian online changepoint detection. https://githun cow.aauoccccoogggggddeeeeee
bocd. git, 2020.
[53] Changjian Shui, Gezheng Xu, Qi Chen, Jiaqi Li, Charles X Ling, Tal Arbel, Boyu Wang, and Christian Gagné. On learning faimess and accuracy on multiple subgroups. Advances in Neural 2022.
Information Processing Systems,
[54] Changjian Shui, Qi Chen, Jiaqi Li, Boyu Wang, and Christian Gagné. Fair representation learning through implicit path alignment. In International Conference on Machine Learning, pages 20156-20175. PMLR, 2022.
[55] Min Wen, Oshert Bastani, and Ufuk Topeu. Algorithms for fairness in sequential decision making. In International Conference Artificial Intelligence and Statistics, pages 1144-1152. PMLR, 2021.
[56] Gido M Van de Ven and Andreas S Toliia.. Three scenarios for continual learning, arXiv preprint arXiv: 1904. 0773444 2019.
[57] Yen-Chang Hsu, Yen-Chene Liu, Anita Ramasamy, and Zsolt Kira. Re-evaluating con- tinual learning scenarios: A categorization and case for strong baselines. arXiv preprint 18/0 /448,, 2018.
[58] Mare Masana. Xialei Liu, Bartlomiej Twardowski. Mikel Menta, Andrew D Bagdanov, and Joost Van De Weijer. Class-incremental learning: survey and performance evaluation on image classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(5):
5533, 2022.
[59] Sang- Woo Lee, Jin-Hwa Kim, Jaehyun Jun, Jung-Woo Ha, and Byoung- Tak Zhang. Overcoming catastrophic forgetting by incremental moment matching. Advances in neural information processing systems, 30, 2017.
[60] Khurram Javed and Martha White. Meta-learning representations for continual learning. Ad- vances in Neural Information Processing Systems, 32, 2019.
[61] Gunshi Gupta, Karmesh Yadav, and Liam Paull. Look-ahead meta learning for continual learning, Advances in Neural Information Processing Systems, 33:1 1888-11598, 2020.
[62] Sebastian Thrun and Lorien Pratt. Learning to learn: Introduction and overview. In Learning learn, pages 3-17. Springer, 1998.
[63] Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Learning to learn around common mean. In ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 3/ (NIPS 2018), volume 31. NIPS Proceedings, 2018.
[64] Sebastian Thrun. Is learning the n-th thing any casier than learning the first? Advances in neural information processing systems, 8, 1995.
[65] Anastasia Pentina and Christoph Lampert. A pac-bayesian bound for lifelong learning. In International Conference on Machine Learning, pages 991-999, 2014.
[66] Anastasia Pentina and Christoph H Lampert. Lifelong learning with non-iid tasks. Advances in Neural Information Processing Systems, 28, 2015.
[67] Giovanni Cavallanti, Nicolo Cesa-Bine Bianchi, and Claudio Gentile. Linear algorithms for online
multitask classification. The Journal of Machine Learning Research, 11:2901-29344. 2010.
[68] Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. The Journal of Machine Learning Research, 17(1):2853-2884, 2016.
[69] Chelsea Finn, Kelvin Xu, and Sergey Levine. Probabilistic -odel-agiostic meta-learning. In Advances in Neural Information Processing Systems, pages 9516-9527, 2018.
14

---

[70] Erin Grant, Chelsea Finn, Sergey Levine, Trevor Darrell, and Thomas Griffiths. Recasting gradient- based meta-learning hierarchical bayes. International Conference on Learning Representations, 2018.
[71] Jaesik Yoon, Taesup Kim, Ousmane Dia, Sungwoong Kim, Yoshua Bengio, and Sungjin Ahn. Bayesian -agnosic meta-learning. In Advances in Neural Information Processing Systems, pages 7332-7342, 2018.
[72] Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. Advances in neural information processing systems, 32, 2019.
[73] Qin Wang, Olga Fink, Luc Van Gool, and Dengxin Dai. Continual test-time domain adaptation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7201-7211, 2022.
[74] Qi Chen and Mario Marchand. Algorithm-dependnnt bounds for representation learning of multi-source domain adaptation. In International Conference on Artificial Intelligence and Statistics, pages 10368-10394. PMLR, 2023.
[75] Changjian Shui, Qi Chen, Jun Wen, Fan Zhou, Christian Gagné, and Boyu Wang. A novel domain adaptation theory with jensen-shannon shannon divergence. Knowledge-Baud Based Systems, 257: 109808, 2022.
15

---

Appendix
Table of Contents
A
Preliminaries
17
A
Definitions
17
A.2
Online Convex Optimization (OCO)
17
Missing Proofs in Section
B.1
Excess risk bound for Gibbs algorithm
19
B.2
Excess risk bound for SGD
21
B.
Excess risk bound for SGLD
23
B.4
Excess risk bound for Regularized Loss Minimization (RLM)
24
B.5
Unitied form of excess risk upper hound
25
B.6
Convexity of the unified upper bound
26
Table Notations
27
D Missing Proofs in Section
28
D. AER hound in static environments
28
D.2 AER bound in possibly shifting environments (Proof of Theorem 5.1
31
E
Missing Proofs in Section
35
E.1
Cost lunction Gibbs base learner
35
Static AER Gibbs
37
F.3
Proof of Theorem (Dynamic AER of Gibbs)
38
E,4
Cost function for SGD base leaner
39
E.S
Static AER of SGD
40
F.6
Proof of Theorem 6.2 Dynamic AFR of SGD)
41
F
Experiments
43
F
Experimental settings
F2
Additional results)
................................
45
F3
Experimental details
47
F4
Bayes Online Changing-pone Detection
48
G
Additional Discussion
50
Learning-forgetting w.r.t meta-updates
50
G.2
Real-world examples for practicality and necessity of CMI..
50
More details on DCML
50
4
Limitation
51
G.5
Broader Impacts
51
H
Additional Related Works
52
H.
Summary and comparison related settings
52
H.2
Continual Learning
................................
52
Centa-Contiuul Learning
53
H.4
Continual Meta-Learnn Learning
53
11.5
Meta-Leaming
54
16

---

A Preliminaries
In the appendix, we assume that all sets are convex subsets of R2, and we use - to denote the Euclidean norm.
A.1 Definitions
Definition A.1 (Lipschitzness). A function f W - IR is L-Lipschitz w.r. norm || if for all W1, W2 E W. If(w)) f(w2)) & L||w1 w2el
Definition A.2 (Quadratic Growth). A function f W + R has a-quadratic-growth w.r.t || for 0 if for any w W, we have:
w - w² 5 - f(w"),
where w" denotes the global minimum point of f which is closest to w.
Definition A.3 (Convex). A function f W > R is convex w.r. norm || if f is everywhere sub-differentiable and Vv, y E W,
f(y) f(x) (Vf(z), z),
where fx) is subgradient of at x. Definition A.4 (Strongly Convex). A function f W + R is a-strongly convex w.r.t norm || everywhere aub-differentiable and if vf W.
(w) 2 f(x) (VF(s), 2) lly x11
where fz)) is subgradient of f at z. Definition A.5 (Smoothness). A function f W - 3-smooth w.r.t norm ||-|] is everywhere sub-differentiable and if Vx, y E W,
3 1ly 1
f(y) S f(x) + (Vf(x), -
where fz)) is subgradient of f at
Definition A.6 (Bregman divergence). Let + be an everywhere sub-differentiable strongly convex regularization function. Then the Bregman divergence w.r.t function R for any y E U is defined as:
Ba(xlly) det R(x) R(v) (VR()), (r v))
A.2 Online Convex Optimization (OCO)
A.2.1 Definitions of regrets
Definition A.7 (Static regret). The static regret of OCO algorithm the action set 14 w.r.t sequence of cost functions : + R) is defined as:
Rr def Σ Se(wx)
min Σ Se(v) uell t=1
Definition A.8 (Traditional dynamic regret [40]). The dynamic regret of an OCO algorithm on
action set 24 w.r.t sequence of cost functions {Se u + R] and the comparator sequence WI.r, Vah. E 24 is defined as:
T
RT
del
Σ S((1))
1=1
17

---

A.2.2 Static regret may be vacuous in shifting environments
Proof. For a shifting environment that has ui = arg min, 7. EE Se(u) changing with T, we can prove that the static regret may be vacuous T goes to infinity.
Let us denote Fr Di. fe(u)), FT-1 Σ f 0.
Assume that the cost functions are non-negative, which is usually the case. Whenever have fe(u))- fe( 2 a > O, we can obtain
T-1 Fr Fr-1 E (f((t))) - fr(u7) 2 a - fr(u7).
The above inequality holds for any T 2 1, so we can rewrite it as F. Pt- a(l - Je By
summing each side from t = 1 to t T, we have Fr 2 F aT(T- + Σi= f((u,) (T
Consequently, we have FT = Σ fe(uT) 2 a(T-l), which means the static regret will be vacuous when 7 + 00.
A.2.3 Online algorithms
Definition A.9 (Follow The Leader (FTL)). Given a sequence of strongly convex cost functions {fi ( - R}2,, FTL plays for > 1:
Ue arg min
Σ f((u).
well
Definition A.10 (Follow The Regularized Leader (FTRL)), Given a sequence of convex cost func- tions {fe 44 + R/221 strongly convex regularization function R U + I,, and the starting point U1 arg min R(u), FTRL plays for 1: uEll
arg min uell
f(()) R(u).
Khodak et al. 31 write FTRL as u, arg mim Σi=1 Si(u) + BR(ullu)), while we follow Shalev-Shwartz et al. 41 and Hazan et al. 44)
Definition A.11 (Online Mirror Descent (OMD)). Given a sequence of convex cost functions {fr 44 |221, strongly convex regularization function R plays for t >> 1:
R, and in VR" (0), OMD
Ut
VR (-11
Vill))),
where R¹ R*) max(u, u, i) R(u) is the Fenchel conjugate of R(u).
There exists an equivalent linearized version of the above FTRL and lazy OMD through the lineariza- tion of the convex cost functions.
Definition A.12 (Lazy OMD). Given a sequence of convex cost functions {f: U - R) strongly convex regularization function R U + R, and VR(ūi) = O, in = arg min (R(u((i).
then lazy OMD and FTRL play for / >>>> 1:
Ür arg min (n (1, u) + BR(u(lu--1) "
Uy = arg min By (n( wEll
The proof of the equivalence can be found in Hazan et al. [40
18

---

B Missing Proofs in Section 3
Definition B.1. Consider any base learner A that takes fixed prior information with a data set S ~ 1e" as input and outputs W = A(S, u) Pwis,u- Define the expected generalization gap of algorithm A as
gen A) del (...sCc u)) Ls(A(S, u))] Bw.s(C,(W) -
and the expected excess risk as
Rexcess (A, u) EA,S (e (A(S, u)) (w [w Ly((")))
where w arg wiw Lp is the hypothesis that achieves the minimum risk.
B.1 Excess risk bound for Gibbs algorithm
Lemma B.2. Let be an arbitrary distribution on W and let 3 > be the inverse temperature that balances fitting and generalization. Then, we can jointly denote u = (3,Q). Let S ~ μm" be sample of examples. The solution the optimization problem
PW]s,a arg inf [W.ssLs(W)) + Dkswi((l))l)))) Pwis
given by the Gibbs algorithm which satisfies
e --Bls(10) -L(((1))((w)) Ewnq (e (B)]
dPW (Piiss (w)
See Proof of Theorem
48
Theorem B.3 (Excess risk bound for Gibbs algorithm of meta- reta-parammttr (3, Suppose
W = Rd and assume that e((,z) E [0, 1] is I--Lipschitz for all = E Z. Let W, Pw, denote the output of the Gibbs algorithm applied data set S with peeta-prramtter
(B, Q). Let w" be the hypothesis that achieves the minimum true risk among W. The excess risk of W, satisfies
Rexcess (Gibbs, u) def (W,)(
inf Lu(w)
WEW
B < 2m
(oLVā+ DKL(N(w" (er(((("",'1a)))000 oo11)))IQ)
+ inf
0z0
Specifically, if we assume Q is the Gaussian distribution ((, o 0²1a) with o = m 10-114d-1/41-1 and denote (8, 6), then we have
3 2m
m2 1/2
Reaers (Gibbs, u)
114 2/2
110 16--w111 w²1
23
Proof. The original proof can be found Corollary 3 48 we provide the proof below with more
details and some tiny modifications. Consider an arbitrary data-free distribution related to the unknown minimum w" of the true risk, Lee,, i.e. N(w", ,( 201)). Then for any a >> O, we have:
Ew,, Eww.s(C.uu (W,)) = Ew, Sw,,slCsse slCs(W,,,)))))) + gen(u, Gibbs)
B
< Ew, Ew,,s[s(WW))]
2m
s Fw,,s(Cs(W. 1
1
Rs DRL (Pw, 2m 3
$ / EsLs(w)N(w; w', o² 12l)) + DKL(N(WO ,d1a))1lQ)) + 2m
1 (
_
Lu(w)N(w; w², o 1 DKI(N(w" ( +
2m
'In some definitions, the output of the Gibbs algorithm is the optimal distribution itself. Here, we consider sampling from this distribution.
19

---

The first step is obtained with previous work's 's results that Gibbs algorithm is (3 0) -iiifferrettialyy private 4 The second inequality makes use of the non-negativity KL divergence. The last inequality derives naturally from the fact that the output of the Gibbs algorithm follows the optimal distribution for the objective function Lemma B.2
Since f(.,z) z) is L-Lipschitz for all E 2, we can obtain the following by combining the Jensen's inequality:
(C Lu(w")l S E 1l Z) - , L|[ w" M. W.
Then we have
Js Lulw)N(w;," ool""",o'lluu""" S / (Lu(w") + L||w w" IDN(w;;" 1a
w
s [l(w")) Lovd.
So we have for any o > O,
(W)) inf wEW
(p(w) -
8
+ inf
oLvd
+ DKI(N(W Dxu(N(wr,ouaa))))) (oWa))lQ)
2m a>0
3
+ inf
<LVVd + DKI(N(W ('LL))
2m
a20
3 + inf
aTvvd +
1
11 w²13)
2m
a20
2/002
8
+ m 1/4
1/2 14
a2/2m
1/21
1
2m
23
The last three lines are obtained with the assumption that Q is the Gaussian distribution (d 02 and setting m 1 1/2
20

---

B.2 Excess risk bound for SGD
Theorem B.4 (Excess Risk Bound for SGD of meta- veta-parameter
()) Suppose W IR., let w² of arg wew ( be the hypothesis that achieves the minimum population risk in W. Consider the SGD algorithm with K updates starting from W1 = @: WK+1 = W 1) V]Ve(W<= Zx). where Z& is sample randomly selected from data set S. Assume the loss function E( 2) is convex,
3-smooth and L--Lipschitz for all E 2. Let the output of the algorithm be W Σx Ek=1 Wk. Then, the excess risk bound is given by:
1 1
11
L
L2K
(excea u) del Ew,s
inf (u(w) S wEW
+
2n
2
Proof. The excess risk can be decomposed as
Ew.s(Lu(W) min (w)) Ew,s (C,)s(C [s(W) + Eur
min (w(w)
"
Ew,s (w,))(C((W)) Ls(W)) + s (sW) Es [s gem((u, SGD) + (Ew.sLs(W) - EsLs(w"),
The first term the generalization gap defined Definition B.1 def
Note that the second term is not the
optimization error cpt [Ew,s [Cs(([)) Ew.s (wg)) used in (38), which is the expected gap between the SGD output W and the ERM output w The optimization error indicates how close the SGD output can approximate the possibly intractable exact ERM solution, which is an upper bound of the absolute value of the second term [Ew,sLs - [s[[s(() [[s((")) S <copt (can be derived with Lemma 5.1 in (50).
Here, we directly make use of the convexity and obtain the gap compared to the true minimum. It's easy to bound Ew,sLs(W)) (W) (EsC((w") using the method provided in Shalev-Shwartz and Ben-David [5T] with some tiny modifications.
Since we have W = W₂- VWW,, Zx). WI.K is related to the randommess introduced by the sampling path Zu.K from S. Moreover, for the convex loss function, we have:
Ew)) - -EsCsw") = Es EW Cs(W) - [s(w")
Es
Ewi.x Cs( Σ Wx) Ls(w0))
K
$ Es
Ew K
(W() - -s(
k=1
K
1
< Es
Ewa, s:K
(We w", (
K
k=1
K
1
Es
EViK-1 K
W w", VLs(WW))
1=1
K
Es
Evi. (W - w VVss(WW)
K
where V/2 Ve(W,, Zz). The incqualities are obtained by using Jensen's inequality and the last two equalities are obtained with the fact that Wi.K is determined by Vi.k-1-
Moreover, we have E[V W&] = E[VA Vi=+11] = (Ws))... The first equality comes from the update rule, where We is determined by the previous k gradients and the meta parameter u = (17 ø). Note that u is not a random variable and hence no randomness needs to be considered. The second equality holds because Za uniformly sampled from S, so Vj is an unbiased estimator of (WR)).
Hence,
21

---

B
1
Σ
(w. (
w", Vic)
Vv (WW w0, Vail
K
K k=1
By 1WW - w, Viell
Ey Ev, 1/W - w", Va) V1:k-1]
K
By 1W -0",
, Bv, [V.|Vi:k-11
K
Ev RW - w", VLs(WW))
By using Lemmal4.1 in Shalev-Shwartz and Ben-David [TT,
can obtain that
K
Ew.sLs(W) F.sLs((")) S Es
Rvi
W
w,, Vit)
K
k=1
|
w² 11
K
+
V11
2nK
2K
k=1
Since the loss function L-Lipschitz, we can further obtain:
Ew,sCs(W) - (w("") = [ w01
L
21
We have assumed that the loss function is convex and 3-smooth. Therefore, following Theorem 4.7 in Hardt et al. [50]. we have the following upper bound for the generalization gap SGD if the step size is smaller than
L2K gen (G,)) - m 7
So, can conclude
16 w=11
I.2 I
Rexcess (SGD, u) Ew.s| - inf
fr(w) _
( +
).
weW
27K
2
22

---

B.3 Excess risk bound for SGLD
Theorem B,5 (Excess risk bound for SGLD of meta- meta- parameter u 6)). Suppose W R let w arg wew Lu (w) be the hypothesis that achieves the minimum population risk in W. For SGLD algorithm with adaptation starting from Wi Q: Wk+1 = Wx TyVe Zx) + Ek. where Zu is sample randomly selected from data set S, Ex is the independently injected isotropic
Gaussian noise (0, o² (a) Assume the loss function E(., 2) is convex and L-Lipschitz for all 2 Z.
And let the output of the algorithm be W = K Σ WR. Then we have the following excess risk bound:
Rewesss (SGLD, u) def Ew.s [w.](C
inf f (wr) S wEW
11 w0 112
"
r.2
do
K nb
2nK
2n
4m a
Proof. Analogous to the proof of SGD, we can decompose the excess risk as
Ew.s(Cu(W) min Cp (w)) = Ewv, (W)))(C((W) - Ls(W)) + Bw,sss(W) - min C (w) Ewvs (W) [s(WW + (W)) [ss gen(u, SGLD) -Bw,sLs(W) EsLs(w").
ar
u
According to Pensia et al. 338. we have Igen (14, SGLD) -
1 KnRL2 4m o²
In addition, we have the update for SGLD: W - V Zk) + Ex. where WI.K is related the randomness introduced by the sampling path Z1.K from S and the injected noise fi:
Denote Vi Ve(Wa, Z "j
then have EVV. E V
(Ws.W...
Conduct similar proof as the above SGD algorithm and use Lemma 14.1 in [1 we can obtain that
K
1
Ew,sLs(W) EsLs(w") s Es
Ev
Σ
( w", Vit)
K
|| wt 112
K
17
B|| Vi
2n,K
2K
Since the loss function is L-Lipschitz, we have
W w=1l 112
0²
Ew.sLs(W) (w=")
2
Combining the aforementioned generalization gap bound of SGLD, we conclude the proof.
23

---

B.4 Excess risk bound for Regularized Loss Minimization (RLM)
Theorem B.6 (Excess risk bound for RLM of meta- pettameeeettrr (B. Suppose W R ler w arg wew Lu (w) be the hypothesis that achieves the minimum population risk in W. Let us denote the oulpui of RLM with Tikhonov regalarization W arg ang Lg(w) + B || l1 Suppose the loss function : W Z [0, 1] is convex and L-Lipschitz, so the excess risk of the above algorithu is bounded by:
11 - w01l
10-11
2123
Reacess (RLM, u) Ew.s(C,(W) -
inf (w)
3 +
wEW
Proof. Here, since the algorithm is deterministic, can consider Pw]S,u delta distribution centered w's A(u,S) Then, the bound becomes
(w.) Es Es(Ln(wā)]
Es L. (A(u,,
1 (w)
3 Elos w012 21223
inf wEW
which is equivalent to Corollary 13.8 in [1 with ø 0, X
To prove the above bound, we use the same decomposition of excess risk:
Ew.s(Cu(W) min [a(w]] Es (wg)) (s(w3)) EzLs(w3) min (w(
"
Ess ب (wz) Cs(w3)] EgLs(w3) Es [ss(Cs(w))) gen(u, RLM) + EsLs(ws) - EsLs(w").
From Corollary 13.6 in [51. the stability of RLM rule satisfies
2L
gen(u, RLM) (s(L,(w}) - Cs(w3)) v m
which means the RLM rule using Tikhonov regularization described above on average-replace-one- stable with rate 2128 From the definition of this algorithm, we have for any e W.
[s(wg) S Cs(ws) + 3 1 -012 - Ls(w) + g glle ø112.
Take expectation w.r. S, we can obtain EsLs(w3) S (w) + f -12, Vw E W. Finally, combining the stability bound and letting w", conclude the proof.
24

---

B.5 Unified form of excess risk upper bound
Lemma B.7. Assume that Cxp(.) has a- a-quadratic growth (defined in Appendix A.2 Vt [T] and that for a given base learner A, we have Revcess (A, ue) S detalle--ue d, : ex, with
Br
be, 6, 2 0, ct. de > Then we have Rescess ue) S f((ui), where fe(ue) is given by eq.
Proof. Let 80 EW, be the expected output, and Eo |0o well characterizes the randomness of the algorithm output, which should be small enough.
Then, using Titu's s lemma, Jensen's 's inequality, and the a-quadratic growth assumption, we get:
|| w/ 1|
| ú; + Wi wIll²
S 2| (: we| 1| + 2 |00,- wil 1|
2 (b: wr 2 + 2 IIEW, wil l|
$ 2 6: w; 2 + 2E| W w 11
s 2 we || + 4E Cy, (W,) Lue (w²)
3. + de + +4) bu lott w s 2 we| ||
a
Rearrange and put the upper bound of 10r wil 1|2 into the excess risk bound, replace va/d,3 aB; 4c, with 3e > 4ct/c a and use again the Titu's lemma, we get
Rexcess (A, ue) S 4avecd cick
| will? + Eo +
4dics Ic, a²
by
2vdec 8i
et
B/
a²
4a
40 dic
It's easy to relate Kit, As, Ee; cu to the terms in the above bound. Consequently, we have Eg = 2a60
20:|uu; 2. 2//add, 2. b = 2o, aby 8d,e 2e,, and A.
1.a,e
2voed
We prove Proposition I and Proposition E.4 without using this Lemma and provide more details in the corresponding derivations.
Theorem B.8. For any t E [T), assume that Cu, (-) has a-quadratic growth (see Definition A.2
then whenever the base learner is SGD, SGLD, RLM, or the Gibbs algorithm, there exists fel. that gives
bllg: sa((3.+ Rewenn (A, S fe(ue) = 16 1..
wrll + c + + +0.0++1) K8,, Ke, Et. 3r E E R.,bb, >0.
Be
The meta-parameter Ut (Be, de)) decomposes into an initialization or bias or and learning rate Be (if A E (SGD, SGI.D)) or a regularization coefficient (if A E {RIM, G. Moreover, we denotes the (single) output for the (possibly randomized) base learner, and en def 2al|ur - EW&ll characterizes the randomness of the oulput. Finally, a and b are constants, and E2, Kt, De are functions of the task sample size my that characterize the base learner (see Appendix B and D).
Proof. According to Theorem B.3 Theorem
B.4
Theorem B.5 and Theorem B.6 we have
d 1/2
Rexcess CeicesssGibbs, (Gibbs, (Mi, 2t)) -
1)t
+ m,
1/4 1//2 144 +
16, wil 11?
2m,
2n..
|| - will
Le L'Ke )
Rexcess Pexcess(SSD) (SGD, (x)) <
+
+
21/ K₁
2
m4
|1 wil 1|2
do²
Ke mp
Rexcess (SGLD, (M), (t)) <
+
r,2
+
+
27,
2
2n
4m,
||cb
w 1|2
2T2
Rexcess (RLM, (m,, (t))
<
+
178
m4
WWe assumed quadratic growth for e(.,2), E Z in the submitted version, which is stronger than the current assumption and is unnecessary.
25

---

Combining Lemma B.7 we observe that b, = 0, 2//2m//2 dg 2m. Ct = m, 1 ////
do² for Gibbs algorithm; by = 0, c. = 2k. de 12 + L²Ke Er for SGD; b. 2
2K, dr
La 2
+
Amp 6 for SGLD; and b, 0, C. 1,
2L
m. Et 0 for RLM. Therefore,
simply adding the transformation = / ce/de + 4ct/a inside the algorithm the algorithms mentioned above have unified form excess risk upper bound defined in eq.
B.6 Convexity of the unified upper bound
Lemma B.9. Vt E [T], the cost function that has the following form:
f((w)) = fe(3e, 01) = neeaB + bllo:
well +
c + co
+ Ke, Co Ae E ERt, RRt,abb 0.
B1
is convex W.E (Be, Φb), where dr, Wi W CR.
Proof.
bllø; W/ 21 + c ED
0g.ft ki(a
Bi
2b( - wi
Ob.f = Ki
3r
The Hessian matrix of (5t, Φt):
2nr blldr ollde-wi
wi +er 97
-2blor-wi) Kil
2
87
2h( ms)
2h Kit 3e laxd
81
Kt
For any h = (hg. ha) E ER x R4, and 3e > 0, E Rdd
we have:
(v) 2(c + co)hi + 2b holl - -we) - Behall?
2 0
B2
so fe is convex w.r. Ut.
Suuch transformation not unique, e.g., Br can be scaled by Va. depends the concrete implementation.
26

---

C
Table of Notations
Table 2: Summary of major notations
Notation
Description
T
length of task sequence
N
number slots (environments)
index task at time k-th task insider n-th slot number of tasks inside slot number of examples for cach task environment distribution task distribution
n, k
Mn. M
my, Mn.k, m
T(
Me
2 x A
example space
base leaner/learinng algorithm hypothesis/nodel parameter space task model, algorithm output
W C Rd Wt, Wn.k U
mcta-parameter space
meta-paranee parameterr
(3,
optimal meta- parammeeeeeeer hindsight model initialization/bia.
Dn.
Be, Brck
learning rate/regularization coefficient of A lcarning rate of meta parameter
Te V/n
hopping learning rate number of gradient steps for SGD diameter of W
Kr, Kink
D
diameter of all the algorithm outputs space W diameter of all meta parameters variance of all the algorithm outputs
V
DM., D..
diameter in n-th slot
D max m D
maximum of slot diameters
VT
slot variance maximum of cost function gradient path length Lipschitz constant
G.
in n-th slot
pa
quadratic growth parameter randomness of algorithm output parameter for controlling range {
6o
E.
/ojaa, V /bb2 te Eo)/a
B =
range of Bn,k. where ép c0 + cy
nn.0
GaVi
D.
theoretically optimal value
2p. D2
p
ΣN- G²
theoretically optimal hopping learning rate
27

---

D Missing Proofs in Section
5
D.1 AER bound in static environments
Algorithm 2 Meta-OGD (Static Environment)
Require: Convex set T, 01 0 E W. > 0. initial learning rate 73
for t < to T do
Sample task distribution: μ4
Sample dataset St ~ μi;
Select meta parameter = (3,, Ø1) E Ut;
Learn base parameter wi A(u,. St),
Estimate excess risk upper bound fe(we) in Eq. 1
Update learning rate of the meta mara-earameter: " = =
Update the meta- parameeer..
Ur+1 ( 7h Ve(ue)) V(c(ue) = (axe brc. we 122 traeetacco
(bb ws)
52
De
Le.:
01-1 (1
2b W + Wa BB41 -2-(an-- r.(bllor 1opee-wy Ptecteol):
2b
De
end
Theorem D.1 (AER bound static environment). Let us consider the static environment. If the excess risk's upper bound of the base learner A(ß,, 6t) can be formulated as the aforementioned Then, running Meta-OGD (Algo. 2 as the meta learner,
unified cost function form in Lemma B.6 the AER is bounded as:
AER <(2)a(VV++tte))
+
K1
K
T
T
3timax
(
bD² + Emax (4ab2 + a a? + bb222))
/T
280
is the optimal initial- ization (or bias) in hindsight, 2 ΣT Σi 110* - well is the variance of the base learner outputs, and e Ei= NaCt
where D is the diameter of the base learner outputs, 0² Et. El Ne
-Fmax maax(KITT Emax max(eiT), En = eo + E eo is the across Eis
tasks maximum corresponding term in eq. and co E If > 6V2 + we replace in the V v ((D22 +e 20)/a then, the mela-paramete set in Algo.
bound with Eg. Let dd
de B x W.
Proof. At first, in static environment, all the tasks share the same optimal prior information "" arg min Σtn (u) (the comparator in static regret). As proved in Lemma B.6 the cost functions are convex, so the sum of T convex functions ΣT fé( is convex. Then we have the minimum attained 2²" (8*,"") By solving min, Σ1 f((u), we get 0= = E
and 8 (bV2
60)/a, where >T KeE: and V2 =T E.
T
El= || -well
According to Algo. 2 di is determined by the previous base learner outputs Wia-1 and the initializa-
tion Φ1 = 0. As long as 2bw.'t: 9, < 1, Vt, we have de is always constrained within the ball (of diameter
D) that contains W. So we have 0 < l| well < D and /2 ΣT E sq 1100 w. < D².
Moreover, we constrain 8 E Vēo/a. / (bD: + +c+ 20)/a where éy cp + cy is related to the
randomness of the base learner output éo and factor e, to control the range of 3r. We will see later that e, can affect the gradient norm of the meta-parameter.
28

---

To derive the static regret bound, we need to use the following result first:
|1++1 - u²11²= = |1T1r(4 y V((()))) - -5 - 114 - 7/ Ve - u 11
- llue u 1= + >21 V 2% St, (u+ - u u²))
So we have (V.. (ug - 2²)² -
- 1
The 1
2%
Moreover, with Br E Violaa// v (bD2 + +c+60)/a E0)/aa
we have
10 Scl = Iks(a bll0: well + Et + e1
anr(bD2 emax)
| S
$7
20
2brs 1 will
2br5, D
10pfll
Be
v V
Hence, // < x²x7 tema) )2
%
In addition, l|ue -he-M u² 1|2 1 -
-
D2
bD Com
So the static regret is bounded by:
Ratatic (u') =
Σ f((u)) - f((uu) S
Σ
fcr (u+ - u²))
t=1
114 -
- 1²1
T
Y
V 112
2712
2
t=1
1
Yell V fell
|lue u 2=1
+
27
2
2
1=1
S (D²
b12
6max
1
4ab² 22
max a²
2D
Yenk
a
27T
20
2
3kmmax
VT
bi² + Emax
14ab2 D2 + (Emax + bD2)2)
2e0
a
We have the learning rate schedule 7 7 and 1/70 0. The third inequality holds because
vi
of the aforementioned bounds of l|u - u 112 and [/Vl The last step is obtained by setting Y = Eo (D24 uO2 Lae
and ΣT, 1 s 2.T, where Kmax max(KiT), Emax max(euT).
Fun v 4nbb En D2 +a (cmus + +DDay
V
According to the setting of Co we have two conditions.
If cu < 2V + 3 = / (bV2 co)/a E VVoTa, v VbD2 +e+ + a can be attained.
Then, for the optimal comparator in hindsight u² (3*, ,t),, we have the accumulated cost:
Σ felw²) Σ <e(3 + 6/ w/ 12 + a
+ co
Ae)
8r
T
T
= =(2Va(bV2 +e +e+)
Kit
+
Kr A..
[=1
t=1
29

---

Finally, we obtain:
T
AERA
S T t=1
fee
1
$
fe(u") + Pe (u"))
I
T
= (2Va(bbV2 +c+ Ea))
lit
1=1
(Viee
366max
bî2 + Emax
(4abb2 f22 + (emar + +bß2je)
+
TT
2. et > bound the cost function by replacing eo with Eg and obtain a newly attainable optimal comparator
= (6V22 + to)/ < V cannot be attained. We can simply upper
in hindsight i" (3x, )²), where 3 v(V2 + En)/a E
V V(uDe +e Eo3/a
Then, we have the accumulated cost:
Σ fe(")) = Σ (a + 6/
T
T
w/ 12 + Et + ED
+ A.)
8
T
T
= (2Va + c c 20))
+
A
[=1
t=1
Finally, we obtain:
T <
AER
(e(we)
T
1=1
1
$
fe(ū²)
Pepaaic (ū"))
T
= abV22 +E+
T
Kt
T
A
t=1
(VD=+
+
316max
bD2 +
Cmas
(4ab220 + (Emex + (D2)2)
250 TT
a
30

---

D.2 AER bound in possibly shifting environments (Proof of Theorem 5.1
Theorem D.2. Consider both static and shifting environments. If the excess risk's 's upper bound of the base learner A(u,, St) can be formulated as unified form in Eq. (V, then, the AER of DCML (in Algo. 1 is upper bounded by:
AER S
N Σ
aa tep + 60 n=1
3 2T
Σ
D Mn
I+
D Dex T
2P 72m
G2
T
optimal trade-off in hindsight
average regret over slots
regrer W.ET environment shift
Here, Ki. = =E &r, An Ek= Fin & where the subscript n. indicates k-th task in n-th slot. The optimal mela-parameter in hindsight of n-th slot is u = (8% 4%) and the path length of N slots is P Em 1 |10 u + 1. 0n- - -i
Mnn
Mn. End Wo, is the weighted average of the base k= Nn
learner outputs within the slot. 5 (bV2 + ca co)/a, where V22 Exer Nn.k
11 Wn.k 112 No.
is the variance in n-th slot and en = Ex=n Kn kn Moreover, Gn is the maximal gradient norm of the cost function, D is the diameter of meta- mneta-parrmetees in n-th slot, and D = m
Kn
Proof. A possibly shifting environment can be considered slot-wise static or static, so we need to derive the dynamic regret bound. We the subscript n. k indicate the k-th task inside the n-th slot and the corresponding timestep is Di= M, + kt To obtain such bound, we first use the following result for the meta-parameter updates inside the rith slot:
|,, 21, 21 |[T (1 Un,k Tn,k S (Wn,k)) w I ||un,k Yrak fr.kk 2,,
S |l - -2,,l 11 w
V fn,xl1 27m, (V Viikk (un,k - -1,))
So we have (n (Un,x - -(,)) S | 111 + Tm. Sm..kll
2
2
Let Gn be the upper bound of the gradient norm related to the n-th slot, iee. max V Sn, S G,, Applying the above result and the update rule in Algo. [
we have the dynamic regret:
N
M
Meynamic (ui.N)
(n,,( fm,e(ug)
R=1
M.-1
FfL (un,k unn + V.T,M, (Un.M, 2%/)
N
M
[l - urll - |1 urll
+ G2 7/kk
27nek
2
n=
[Un,M,
|1
G P
2p
The meta-parameter updates that transition between slots adopt the hopping learning rate p. which reflects the environment change.
Denote
Ti
Un.k .
11
||
+ G2 Pock
G2
2%n,
and
N Mn.M.
12 | 2/a4 11/ + || 11=1112
[1 1.1 u 11
T2
2p
==1
31

---

First, let us tackle T2.
Un,Ma
11 U2+1l
1
||,,11 + 2u 1,1 (22 - - (
T2
2p
2p
U 2/ |lu 1 U 2
2p
N
| 1|2 1/2-|11, |1 112
2, u +1+
2p
n=1
NN. uN 1|2
Iuu 1,1
ux 11
||u +1
2 1||u
2u 2u N (, -v++11
2p
N-1
Un, 2 1| ||utt,11
u
112
Juyl1
||u711
D
N-1
+
uc un--1l I
2p
2p
n=1
n=1
JUNN uNy 12
-11
22 u.
2p
N-1
[un, U 11
||
n+
112
Juy
||
D
N-1
<
u, u6-1
2p
2p
P
|uN u.y 122
+
2p
The first inequality is obtained with
1 (uh mh+1) | |l,, "h+1ll Dmax || "1+1ll
where Dmax = max { 1 J is the maximal slot-wise diameter of the set meta mneta-parameters. Since we have assumed that 0 E W, it gives |1 S Dmnx, Vn. The last inequality of the above proof
holds because -|uw 1.1 +22 1 uNy -laa - -1luN41.1-03 < 0.
2p
2p
Let D, be the diameter of the base learner outputs in n-th slot, and let Dune = max Dr 1N Mr k== ) Emax = max me max
MM max = max((n.. maxx (rax(Kn,t k=1"
m==1
constrain Bn, E Voola, V(DDz + Emax + +0))/a where En Eo + e is related to
randomness of the base learner en and factor eu to control the range of B.. We will see later that e, can affect the upper bound the gradient norm of the meta- mata-earameter. We can further verify that
Hence, 6n, is always inside the smallest ball that contains W,. Then, we can define D de D bb. +o Therefore, have
20 K.n.k Du.k
< can always hold with én < ((mmm+bD2
162
D2 max
(1 D/ ma + (Emax + E0)/a.
Now we tackle Ti. Since we scale the learning rate of the meta-parameter for shifting environments, need to set Yn.k for better tracking of the change. Then, we note that we define _ we have
Tr.0
M
Un, Un,1"
Mr
Un.k+1 - u 11
Ma -2
Un.k+1 - 11,11
[n, M.. u 11
+
27n.k
27r.k
2%m.
27,,
k=0
Mr
Un,
|| |un
u 11
27n,
2p
M
|unkk u 112
|lu,,
27
2p
32

---

In addition, we have ||un,k - 12,
11 - 02.12 + 1Ba,
-9% S D2 + 6b.
S D..
So, we can bound the dynamic regret as Rdynamic RT
(u[:N) ) Ti + T2
Mr
|| Un.k u2
||un
11
Gh 7n
Mn, 11 G2
27n
kmn
2p
unl12
||
un+ill" 112
2p
n=1
| 11
Dmax
N-1
lIN.M - "xll
+
1/ - u u +
2p
2p
n=l
M
Un.k
Unnkk - 11
Gh Ynn
+ G2 P
Ynn
Nv
Un, Mn
u1ll
N
|1x+1111
un++l 11
N
Un,,M,
u 11
2p
2p
2p
||
|
||3
Dmax
N
||u - u u 1|l
2p
n=
Ma
D
1
+ G
Ynnk
G
2%ink
2
2
12:
k=
1
ie
N-1
max
max
||u,
untill.
P
The last inequality is derived with ||5 & Dmax and ignoring the negative terms.
Denote the path length of the reference sequence as P = Σx= 1 2 |l + 1. By setting
Yn.k have
Dn G.VE
2P D (satisfies 1/7n,0 0). p V ENN G..²
and using MM
- -1 1
Vk 2/M, 1,
N
3D, Gn G -
G2
D2 p max
H
Adyaamic
(ui.N) 5
+
+
2
2
n=1
3D, GR
MM -1
N
D max
2P
Σ G
2
For each slot n, the optimal prior in hindsight is ur, (0 Bt). By solving min, EM, [n,(()), can get:
Mn
Km.k
Wo,ki 3r, = V(VV2 + + +00/aa
Jmm
k=
Kink
where 222
Σ
k=1
Mn
|1
wn and
c,
IMg Ka.eeni Ein Kn.k
Ko.k
Thus, the accumulated cost for the slot-wise optimal priors in hindsight:
N M.
M. (a, + bllØn - wnnk 112 + Cn.k +
Snu((u))
+ An.e)
n=l 1m
Mn
Ma
Σ 22 ((VV? + cn cu))
Kn,k +
Knnk Ank
33

---

Finally, we obtain the bound in the main theorem:
T
AERA
S
(u)
T
Mn
1
(u,) + HT Heynamic
(WieN)
T
N
Mn
N
M.
(2V a(bV? + + +
Kinkk
+
Ko. An
T
T
10
k=1
n=
k=1
3D Gn Mn -1
1
N
Dmaxx
21
G
T
Moreover, by limiting the range of And B det
Včo/a, VibDa + Cmux + to)//a
we have
bll@n,
Wn,kl
cn.k + C0
an
max (bD2
+
max Sp
10 1Kn,
8
2bkin 11 Wm.kll
2bm D.: Vēo/a
Don
Ba,
Therefore, fm, a (n
+ +emmy?
1ab? (w Vk:
[Mx]
%
60
Moreover, we let G a²
4ab (n replace Dn, with the tighter
22
V D2 + b and use B2 max = (1 + b/a) max + (Emux + En)/a.
Analogous the proof of static AER, if en VV22 ens 87 attained. Then, the above AER can be alternately bounded as:
VOV ten + to)/a B can be
Ma
N
1 AER & T
Σee
a(bV2 n + t. +
Knnk +
Kn,k
An.
T
1=
k=
n= 1 k=
3
V(Dg +
bDz + max
(Mr 1)V (bD + <maaa22 4ab2En Dz.
270T
1 + (a + D)D2 max
+ Cmax
+ ēp
(a² mmxx)2 ) 4ab tn)) (
2P
T
a
8; (bV2 + + co)/a < V cannot be attained by optimizing within B. We can simply upper bound the cost function by replacing eo with and obtain newly attainable optimal comparators in hindsight i;, (3: 2%), where 3% (bV? + G. + to)/a
Otherwise, if cy >
Vēo/a, / (bD² + Emax + ē0)/a Finally, the first line of the above dynamic AER bound with ēp.
obtain bound for this case by replacing eo in
34

---

E Missing Proofs in Section
E.1 Cost function for Gibbs base learner
Proposition E.1. Suppose W C Rdd, let wi be the hypothesis that achieves the minimum population risk among W. Suppose E [0, 11, and 2) is L-Lipschitz vz E Z. Assume that Lu, has e-quadratic-growth for all t E [T'. Let wi = Aldr, 3e) denote the output of the Gibbs algorithm applied on dataset So, and Qe be the prior distribution and 3r the inverse temperature of t-th task. gaussian distribution N(e,, ((),,)]1)) with dt m4 1/-11/11//// 1
Assume Qt
To meet the general form of the cost function, we replace 3r with 31 by aB; 2 Ldm, m² d' VLl. Hence, the upper bound of the excess risk of the Gibbs algorithm is given by
2allør wy 1| + ED
2 a
L
2 2v
( VT.
B1 2a
2d VT.
mr
fe(B,,0)) =
+
+
3
m
am,
Proof. From Theorem B.3 we have:
B. + m, 1/22/1 2mz
222mm/22 233
Rexeess Gibbs, un)
10:
wi 11.
Let W = EW, be the expected output of the Gibbs algorithm, and let eg = 2a|lur - well be the randomness of the algorithm, which should be small. Then, using Titu's lemma and the a-quadratic growth assumption on the loss function, we get
1 wi 11
1102 W + w.-- - w
< 2| w. 2 + 2 it w 1|
2l
w.ll 11 + 2 EW; w 112
$ 2||or
w. 2 + 2E W, w 1|?
4E c (W,) Cp (w7)]
2|[or
w..12 +
4(
f 2mn
+ 21/2 + 29
d1/3mn 1/2
10, wi 11
$ 211ør
w. 1| +
a
201ld: 20 2 2 +4m, 1/2
Then, have ||
w2
201/2 m. 172 2
Consequently, we can obtain:
d m.2 L(allor -0,12++ L - B. + 2m,
1/4 1/2
3t
-1/4 1/2 +
Rexcess (Gibbs, uz)
+ m,
2m,
a3, 22 1/2
Replace a,;- 2/2 m//2 1/2
m.
3/4 2//42//11/////
have
35

---

3/4 d 1/23g + 2d 1/2 2)/2
Rexcess (Gibbs, uz) 5
(m
+ m, 1/4 L 1/2 d/2/1/4
2m
all0 well2 + (mn 2/ /z/4 1/2 8/ +2d 12 1/3 1)/a + 2m, 1/2 2//2
m4
1/4
/d-1//1_-1/22
m4
1 m
1//4 1/2 + 1
1/2 /1/2 211/2210 + m, 1/4 L 1//21/14
2x
al
2pl1 + m, 1/4 d L 1/ + m,,"" 1/2 L + 2m, 1m,-1/ 1/4 1/2
1/4 d 1/11
m4
1
1/4 d 1/ L 1/2 1/ + m4
-1/4 11/4 1/2 + a m
1/2 / L
2a m
a a110r Wy 1|2 + 2 _mp
1/2 1/2 + 2m 1/4 ////2
+
1/4 d d-1//L--112g/
m
d VT
2 m,
1/4 1,/4
+14
1
22
mi
allo wi|l 2,, 11/2 1/222/2 + 2m,
1/4 12/2//////
B
allor we||2 + 2
L + TTdt
d LL
3
2d VT.
+
m
2x
am,
Bi.
mi
d VL.
B
2d VT.
VT.
2allo: - well + Eo
+
2
m.
d.
L + 2 2vLdd
+ 1
m.
2a
ami
3/
m
= (3 01)
36

---

E.2 Static AER of Gibbs
Theorem E.2. Consider the Gibbs algorithm as described in Proposition E. to be the base learner. Apply the Meta-OGD (Algo. 2 on the cost function fo(8%, Φ1). Further, assume that each task uses the same sample number m. Then
AER Gibls
O ((v++1)+
(
m
Proof. From Lemma B.6 we know that ft is convex w.r.t u, we can directly apply OGD. Following Proposition
E.1
we have
20/lør wx w,ll + +
2
L +
TTd
d V
Pi
2d VT.
a
0z)
+1+
m,
2a
31
mi
am?
To apply Theorem D.1
we first find a 2a
1 b 2a, Gi =
mi + ILdd
A. = 1 2d /L
m,
am
6o Wr well² and Ke dd VL Since we have assumed my m, Vt E [T', then have
1/4
- + 2
Kmax
6max
m
Taking the above values into Theorem D.I we have:
d
T 2vdL
AER Gihbs S (V2(22VV2 + co)/a++)
Tm1/1
Taym
+ 3d2
(11 402) + Av dd/ml + 4a Ld//4
26 2/
m1/4
V
d V -
LLd
x Sa
am + Dayz
Since we have assumed the bounded gradient norm for the cost function, i.e. L' L'-Liischitz, then can obtain:
D² ēoL' are
abis
which implies éμ 2 ake/L' L', where aRE/L' E O(1/vm). So it suffices to ensure éo > (m1/mm).
For the Gibbs algorithm, by the law of large numbers, have cu 2a Es. E.s...WW 2a ||| H/],::WE,, Wr] m + oc. In addition, since the variance of Gaussian is 1/4 we have 6o E Om (1).
So if we set 6, bV2 < 6V2 + with constant V, then én 60 6. satisfies the above condition. Consequently, we have
AER E <0((v+))+
m
37

---

E.3 Proof of Theorem 6.1 (Dynamic AER of Gibbs)
Theorem E.3. Let W R.. Assume that E(., 2) E [0,1] is L-Lipschitz V2 2. Assume that (.)(.) has a-quadratic-graan
for all t E [T]. Let = AGabro Φs, St) be the output of the Gibbs algorithm (Definition [ on Si where Φr is the mean of prior Gaussian N (or, ofla) with L- 1/2 and Bg is the inverse temperature. Consider Algo. (DCML) and further
at m -1/4 assume that each slot has equal length M and each task uses the sample number m. Then
1 N
N
VP
AER Gibbs
(L
M
MVN
m
I
==1
L + 2 VLdd
Proof. From Proposition E.1
we first obtain a b 2a, Cn,k
a mu.
mn,4
An,A 2d VI and Kink am n.
dt VI, Moreover, Kip m
max d VI
max 2 a
L 2 VLd
m
m
where m = ( 1. Mr
For simplicity. let us assume that each environment slot has the same number of tasks, i.e., Mn M, T N M, and each task has the same number of samples, i.e., mn,k m. So we have Kn,k Ai man d m2 and 6n,k in = 2 dd/mL + 2v /m
Taking these values into Theorem 5.1 we can obtain:
N Σ
dVVI d d'vL 2/dL
AER T Gibbs
(v
2(2a ten aco)/a)
m +
m +
N
aym
n=1
3
d VL
VM -x
NM
m
N
d - L+ + 4a D3 + 1
4a/ Ld's
d
VLd
mt (DDa + V L a²
+
am )2 802 D3
m
1
4o/TN//11
1/4 x d/AVI
60(1
D2 max 44 I I.
NM
m
m
D
d/mL + sTat )2
8aD
2P.
and
60
Since we have assumed the bounded gradient norm for the cost function, i.e., L' L'-Lipschitz, then we obtain:
D < EOL' aRE
abx
which implies éy 2 Lke/L', where ake/L' E O(IVmm). So suffices to ensure éo > (((1//m)
For the Gibbs algorithm, by the law of large numbers, we have = 2a/lw; Es. Wi +
2a 2a:lw:; |1l as m -> Do. In addition, since the variance of Gaussian is 1/4 1-1////--II_-11/// 1/2 we have co om (1). So we set 6, bV2 < bV? with constant V,, čo Co + c, satisfies the above condition. Consequently, we have
AERT Gibls o ((u+ L
VP
M
M
m
38

---

E.4 Cost function for SGD base leaner
Proposition E.4. Consider W R.. wi be the hypothesis that achieves the minimum population risk among W. Suppose f(. 2) is convex, 8-smooth, and L-Lipschitz for all E Z. Assume that (.)(.) has a-quadratic-gra growwth Vt [T]. Let wa denote the output of the SGD algoritim applied on dataset St and dr be the initialization of I-th task, nt is the learning rate, and Ke is the gradient updates number. meet the unified form Eq. 4. let qh (Koom 2)ma. Then, the upper bound of the excess risk is given by
f(1e. = 22 well + cu + 2(L2 2L (K(a)
m.
+ T/1 + 2nis
1/
where K; v(I((Kaa) 2/(ma))
From Theorem B.4 we have the following excess risk bound for SGD:
Proof.
1 10--w1l² 2TJ, Kt
L
L
Rexeess (SGD, ue)
+ 1 me
m
Let W. = EW, be the expected output of the SGD algorithm of t-th task, and wy is the actual output. Let 60 2a 2a/lur - wr|l² be the randomness of the algorithm, which should be small. With the quadratic growth property, we have
1 wii 12 = |lo;
17 + W. - w 1|
s 2
w + 2| W/ w/| ||2
2|1ør
w.ll
+ 21E W, wi 11?
4E LC. (We) - Eys (wi))
2||
w
2|| w
|c wi-wwll 11? 4(
2m
12
2
L²Ke
me
mm))
a
Therefore, we can obtain
2al10: [7: + (2L2 + 4L2 K1 1
[ w/ll
a Kini
2a 2allØ: W. + ED (L² 21 KA )
L
L
Rexcoss (SGD, un)
mm
K,an: - 2
2
m
Let
2allø, w/|l + 60 + (L.2 + 21 KL )mT
L2
L.
f(,, the)
ym
K10tT -2 2
m
(L2 (L242L2
K2 mi
and replace v/c = (Kanm - 2)ree, Ki
we have
Kea
f(1. 0x) = 2allor well + co (I2 + 21 m.
Un// ()/(K)
1///Ks /Kr
2
Ke (nkk/ Ne (),()
+
+ 1
2
m4
2a wi 112 + cu +22222 + 21 Ks (K(a))
m.
1
Kr
+ 7% + 283
4/b
39

---

E,5 Static AER of SGD
Theorem E.5. Consider the SGD algorithm as deseribed in Proposition E.4 be the base learner. Apply the Meta-OGG(Algee 2 algorithm on the cost function f((n), o1). Further, assume that for each task, we have the same sample number m and that SGD performs the same number of gradient steps K. Then
AER SGD EO EO(1V+
m
(12-21.2 Kc)
Proof. According to Proposition E.4 we have Kiz
=1/=1 b 22 and ct Keo 00
2(1.3 +21.2 K1)
Kio 2x.. A. 2kg cu 2a |0/|ur
wy wrll?
For simplicity, assume the SGD step and sample number the same for different tasks. Hence, have K2 K, my
2 L and E Cmax 2n²
Fmax
Put these variable into the bound of Theorem D.I
have:
AER s <112 (2222222
2
+ 4
1
2
2 L
12 + to))
+
L
2
Ka
ma
Ka
ma
Ki
ma
3
2
+
Ka +
ma Lx
250 2
((L+ (a) + 4(
1
+
2
)22
802t0 + (Iaa + ma
2
L2 + aD²
Ka
ma
Since we have assumed the bounded gradient norm for the cost function, i.e., T T'-L.ischitz, then we can obtain:
D2 S LoLL
aRe
abk
which implies Eo 2 aRe/L', where ake/LL LL' E 0(m 3/2 + K-22)) So it suffices to ensure én E 0(m-3/2 332 + K33/2).
For SGD, by the law of large numbers, we have 2a lo, - ES 2 + 2a W.l? as
m + Do. In addition, 2a||wu W/
2 + 0 as K - oo, so we have co om (1) o (1).
Then, if we set c. 2V² 2 < bV e, s.t. Eo + c, satisfies the above condition, have
AER 0 (V + 0m (1) OK
W
VT
Considering constant variance, it gives the following bound that has the same complexity factor and rate Theorem 3.2 in (31] (Khodak al. 31 used OGD the base learner, where each step only takes one sample, i.e., K = =)).
(((
AER E (V
++1
1
m
have O, we can 6, bV2 + 1/T bV2 + e, s.t. Eo above condition. In this case, we have:
ED Ev satisfies the
AERT SGD
00
V 0m (1) +ok() VT
Om (m (1) (O+o (1++V=+11V+++
1 K m
VT
( 1 VT + om + (m)+
/
=0
when V 0, m
K
which has an additional term om (1) + ok (1) compared to Theorem 3.2 in 31 This is because the variance 2 (task similarity) in our paper calculated via the average SGD iterates. A similar term will be introduced using the same output for estimating V in [31]
40

---

E.6 Proof of Theorem 6.2 (Dynamic AER of SGD)
Theorem E.6. Let Rd Consider that E(., 2) is convex, 3-smooth, L-Lipschitz forallz Z. Assume that (..(-) has a a--quadratie-ae gronitheggrwthhhh for all E [T]. Let SGD be the base learner for each task where it outputs we ASGD (i, 6t. St) with learning rate ni and initialization or. Consider the Algo. (DCLL.) on the SGD cost function. Further, assume each slot has equal length M, each task has the sample number m, and that SGD performs the same number of updating steps K. Then
AER EO ((
P MvN
V
V 1=1
V K
Proof. For simplicity, we assume the SGD step and sample number are the same for different tasks. Hence, K K and M m. Based on Proposition E.4 we have 1/2, b = 2a. Then, we
get K Ka
Cn 2k², and A k 2
ma
Put these variable into the bound of Theorem 5.1 we can obtain:
N
AER
Σ
2(2aV 1 + +
+ _
2
L2 + tw)
V
Ka +
+ 2(
+ 2
)
N
Ka
ma
ma
Ka
ma
==1
3
2
Ka + LVM -I
28 M
ma
4
8 )
1
(1+44y) Da +
(aDa
+
)L + S
N
Ka
ma
Ka
ma
n=l
1
1
V
(1 + 4 + 4L2
Ka + + x
+ L
M
Ka
2P
N
(aDz + (Ka + mn
1,2)2
Sa²D2
x
N
é0
Since we have assumed the bounded gradient norm for the cost function, i.e., L' Lippschit,, then we obtain:
D EoL' aRE
abn
which implies Eo ake/L', where ake/ E O(m 3322 3/2 K 3/2). So it's sufficient ensure
Eo E 12 3/2 K 3/2).
For SGD, by the law of large numbers, we have 6p = 2o lw; - ES... W. + 20 W as
m - oc. addition, 2x||w,, W + 0 as + co, so we have Eo E om (1) + og (1).
Then, if we set = =b < 6V e.st ēy + satisfies the above condition, we have
(( Σ Vn + om (1) + (1) n=1
AER I O
V
N
VM
M
K
The above bound has additional 0m (1) + (1) compared to Theorems in 31 Since the variance V (task similarity) in this paper is calculated via the average SGD iterates. A similar term will be introduced using the same algorithm outputs for estimating V in [31]. Moreover, bound is in terms of average task excess risk, while [T upper bounds the average task regret for online base leamners using different meta-learning algorithm.
Considering a constant variance, we have
N (C
VP MVN
AER E O
VM
K
==1
When we have large P* with small N (the environment occasionally changes with large shift), the above bound has improved rate of (LIV/M) or /p= on the path length p (reflecting
41

---

environment similarities and shifts) compared to O
En= Vn + vit + +minf
1
pa PM
NMr1)
MN
the equivalent form of Theorem 3.3 [3 in this case.
If we have V, - 0, we can set DV + 1/M1/4 > bV + s.t. 8o cD co satisfies the aforementioned condition. In this case, have:
N
V + 0m + (1x
+
1+ <0+V"+1/MV
+0+V2+1/MU7
N
1
N
VM
M
K
+ 0m(() + ox(11) )
-o
P
--
1+
when V, +
VM
NM
K
m
The above bound has improvement of rate O (M/ P Vn equivalent term O
compared to the
NM + Om (1) + ox(1)) of Theoree 3.3 in
p
VM
42

---

Experiments
In this section, we provide experimental settings, some additional experimenta results, and experi- mental details. The code is available in mtttpe//gggaabb..co///////////aa
F1 Experimental settings
E,
Emvironment
Environment 2
Envfronment
B2
T50--112
TKy
Fyy
Random Intialzztion Pre-trained Env
Task
Task j.s
Task Px
Task
Task Mal
t
0.5
P
Omniglot (A)
Alphabet (A)
B
2.
E
0.25
New Alphabet (B)
0,20A
0,20%
FMNIST
Moving 2D Gaussian
Omniglot-WNIST-FMMIS (OMF) Dataset
Large Concept Shift Synbols
En Eg ... Es.. number enviromeett:: N
Every emdronment distinct:
Re-vistable environmentis. number of environments: N - P(E;1 4) 0.5, P(E B 0.25, P(Eq.1
0.25.
enviromment changes probability i
P(7m1 E.-1) p. P( B2)
Figure 6: Summary of experimental settings
F.111 Detailed setting OSAKA
Task data generating process Following OSAKA, we use pre-trained meta-model as initializa- tion. The datasets in OSAKA contain three environments. One is used for pre-training, and the other two are considered unseen, consisting of OOD tasks compared to the pre-trained environment. We run 10 CML episodes for each method, where each episode has length of 10000 time steps.
At each time step, we choose to change to another environment with probability p. We select the new environment with probability of 0.5 for the pre-trained environment and 0.25 for of the other two. Then, a task is sampled from the selected environment. The above generation process slightly different from the original OSAKA, which mainly considers a task-agnostic setting (i.e., unknown task boundary). They used a single probability for switching the task and environment simultaneously. In contrast, we focus on shifting environments under the task-aware setting, where the task switches with probability 1, and the environment changes with the process described above. visualization of the generatinn process is presented Fig. (6
Datasets test DCML on two representative datasets in OSAKA.
The Synbols dataset uses characters from different alphabets on randomized back- grounds as the pre-training environment. A new alphabet and font classification tasks are considered unseen environments. This is a large and complex dataset including heteroge- neous environment (font) with extremely large concept shift w.r.t other environments. We conduct a 4-way 5-shot classification for this dataset.
we pre-train the meta-mode on the first 1000 classes of Omniglot 44. Then, at CML time, the models are updated on stream of tasks generated by the process discussed in the previous section exposed to the full Omniglot dataset and two OOD datasets MNIST 45) and FashionMNIST 46 In this study, we conduct 10-way 5-shot classification the benchmark does.
For Omniglot-MNNI DWNISTTFFrhhooMMMMSTOMMMMM
43

---

Table Comparison of computational complexities with baselines
Methods
Computational complexity
Fine-tuning
O K)
MetaCOG
O x (K + M))
MetaBGD
O (K+ M))
ANIL
O K)
MAMI.
O K)
CMAML
1)) O(T (K+1))
DCML
Baselines We compared the proposed algorithm with different baselines. For a fair comparison, further use the same meta-model pre-trained with MAML 4 for all the methods. During the continual learning phase, all the methods adapt with few-shot data and are then evaluated on separate test data for each task.
ANIL is a variation of MAMI. that only adapts the network's head w.r. new tasks. Following OSAKA, MAMI,, and ANIL do not update the meta-model during the CL phase. they will not suffer from forgetting but lack the plasticity to learn from tasks in new environments. They are compared show the problem with static representations shifting environments.
CMAML K includes an update modulation phase and a prolonged adaptation phase. The former uses function gx R + (0, 1) modulate the learning rate of the meta-model proportionally to the loss value. The latter updates the meta-model with buffered tasks when the environment changes or task switch detected. Otherwise, keeps updating w.r.t the previous model. When À 0, CMAML is equivalent to MAML, which never updates the meta-model. When + oc, CMAML updates the meta-model with a constant learning rate.
MetaBGD and MetaCOG 8 perform CML based on MAML and Bayesian Gradient Descent (BGD), where Meta-COG introduced a per- per-parameter mask.
Fine-tuning uses the meta-model as initialization and consistently updates this model w.r.t the tasks encountered. which can be considered lower bound in the setting to illustrate catastrophic forgetting.
Remark F.1. Two modifications w.r.t original OSAKA benchmark: (1) We consider task-aware setting, where the task constantly shifts at each timestep. (2) The cumulative performance in the original OSAKA is evaluated the model before updating to current task data, which does not the support query splits. Instead, we follow the CML setting and evaluate all the baseline algorithms on the model after updating to the current task.
Computational Complexity The computational complexities of all the methods are provided in Tab. where the run time is measured in terms of the number of gradient computations. All the methods are assumed to use a K K-step SGD as the inner algorithm.
Fine-tuning uses the meta-model as initialization and consistently updates this model w.r.t the tasks encountered. MAML and ANIL do not update the meta-model during the learning phase. Therefore, these methods need to compute T K gradients for the T encountered tasks.
MetaBGD and MetaCOG perform CML based on MAML and use Bayesian Gradient Descent (BGD) for meta-model adaptation, which requires M Monte Carlo samplings for the meta-gradient computation. Hence, the computation complexity is O(T (K + M)).
DCML and CMAML need one meta- gradiet and K inner gradients computations for each task, so the complexity is O(T (K + 1)).
44

---

200
25
200
(a) Average test loss w.r.t changing probability
(b) Bayes online changing-poiee poingt detection
Figure 7: Additional experiments for moving 2D Gaussian
F.2
Additional results
F.2.1 Moving 2D Gaussian
Comparison of different environment shiftt detection methods Fig. (a), we plot the average test loss at t 200 w.r.t the environment changing probability in log scale, where we set the window size 10 for "window". We can see that the "window" performs similarly the "oracle" when the environment changes occur not too frequently. "Static" shows the worst result, then the "detect." " We simply (without carefully adjusting the hyper-paramens Changing point Detection (BOCD) to the algorithm output, which, in fact, highly depends on the performance of the base learner. Fig. (b) illustrates the detection results of BOCD, where the green lines are the detection results and the red lines are the actual changing points. The upper figure shows one the dimensions the algorithm output wi with blue points. The lower figure illustrates the run-length posterior at each time step using logarithmic color scale, where darker indicates higher setting, detection results are delayed
adapted the Bayes Online
probability. We can see that with the current compared to the actual changing points. BOCD is more likely to miss detecting some changing points rather than conducting false detection. The pseudo-code for BOCD is provided in Algo.
Not always necessity for the exact detection of changing points We observed a better perfor- mance of "window" than "oracle" for the OSAKA dataset in the main paper, which implies that the exact changing points detection may not be necessary.
This result related to the algorithm, which does not necessarily hold for other methods that maintain multiple meta-models. By updating a single meta-model online, the context switch cost exists reconstructing the meta-knowledge in each slot. Setting a fixed window size can ensure the meta-knowledge quality of each slot and yield good performance average.
In addition, the phenomenon is related to the overlap between the consecutive environment distribu- tions and the environment shift probability p. We empirically tested these factors, and the result is presented in Fig. 8 In Fig. "oracle" better than "window" when p 0.1, and the gap becomes more evident when the distribution overlap is smaller.
Remark F.2. A larger overlap between distributions indicates that they are more similar, which can provide better transfer performance (smaller test loss in Fig. (a) than in (b)). In this case, the two distributions are close, so it's hard to determine precisely which distribution the encountered task belongs to. When two distributions are well-separated, it's easy to detect the shift correctly, but the transfer error is larger.
E.2.2 OSAKA benchmark
We present in Tab. 6 additional results for the Synbols dataset with the environment changing probability p 0.4 and p = 1.0. We can see DCML. performs much better than baselines on new environments, especially the hardest one Font.
45

---

Awee Soprrraee bestt Boos (hg SC0 E-2000
direct
stare
delect
state
(b)
Figure 8: Justification of "Oracle" and "Window" (window size 1/p) methods on the Moving 2D Gaussian mean estimation: (a) Consecutive environment distributions with large overlap, where ग .V [2), and कं أं + (1, with probability of p. (b) Consecutive environment distributions with a small overlap, where т = N62, 0.1I2), and कī = o (2, 2) with probability of p.
avg. test far
avg test so far omniglot
Showing first 10 runs
Showing firtt runs
CHAML
DCML..or aoracle - DOML.win MAYL
CHAML
DOML_.in DCML_oracle MAML
ANIL
ANIL
0.995
0.88
0.99
0.86
0.885
0.98
Stop
(b)
avg test acc_ [0__s____ far far_rarrrfaaaa www.ffassonnnnge mnist
avg test acc__cC___ S0C_00__000 farrssofaa____ea_______ee j_rmnsstt
Showing
Showing runs
CHANL
DOML_or acle
DOML_wn
MAML
CMWL
DOML_win
DCML, MAML
0.68
0.66
0.85
0.62
0.5
0.75
Stop
Step-
4k
6k
(c)
(d)
Figure 9: Average test accuracy on (a) all environments (b) Omniglot, the pre-trained environment (c) Fashion MNIST, the unseen environment (d) MNIST, the unseen environment when the environment changes with probability p == 0.8.
In addition, provide the experimental records in wandb for the OMF dataset when the environment changes with probability p = 0.8. The average test accuracies w.r.t timesteps in the CL phase are plotted in Fig. g
46

---

Table 4: Average test accuracy (%) at 10000 Synbols datasets of OSAKA benchmark
SYNBOIS, 0.4
SYNBOLS, 1.0
MODEL
ALL ENV.
ALPHA.
NEW ALPHA.
FONT
TOTAL
ALPHA.
NEW ALPHA.
FONT
FINE TUNING
2..
1.2
25.23
25.1 0.3
25.
25.4
25.24
25.T+
METACOG X
3.919:0.9
25.1 1.3
25.04 0.7
25.04 0.3
25.0 0.8
25.7 0.9
25.0 0.8
25.01 1.0
27.01
2..41.4.6
ANIL 27
60.6+
77.52 0.1
53.42
32.64 0.2
60.42 0.1
77.62 0.1
53.72
32.82
MAML
4
77.0+
96.8+ 0.1
0.2
40.34
76.8 0.1
96.8- 0.2
73.0+
40.2+
CMAMI
IR
64.9+ 1.5
79.04 3.8
6..24.0.6
40.34
63.1
77.0+ 3.1
58.6++
40.1+
(OMLOO
07.1
93.8
0.3
42.34
0..1
93.
0..1=:0.4
43.4
DCMI-(WINDOOW
77.24 0.5
96.04 0.3
73.4 0.4
42.24 0.8
77.24 0.2
95.6 0.6
73.2 0.5
44.2+ 1.6
F.3 Experimental details
F.311 Moving 2D Gaussian
Model As described in the main paper, the hypothesis space of the moving 2D Gaussian is R2. And we adopt mean square loss ||w--rj x|I². which is 2-strongly convex, so it's 2-quadratic growth with 2. Moreover, limited the data to 10, 10] [-10, 10). Thus, for the given loss function, the Lipshitz constant
20,2, and we set 30 in the code.
Training Details The hyper parameter settings and training details for Moving 2D Gaussian are with the Algorithm [ provided in the main paper. There is
presented in Table [ We need to set the hyper-parameters for the base learner. They are automatically adapted to the derived equations. Moreover, the initial learning rate of the meta learner is controlled by D p__aa_guess. Then, it's also scheduled automatically with time and environment changing points.
Table 5: Moving 2D Gaussian experimental details
Hyper-parameters
Fig. 3 ())
Fig. a)
task horizon T
200
loss I Lipschitz constant L a hopping Ir p D D_hat_ D_hat_guess guess sample numbers m
mean square loss
30
0.8
5
100 1
100
inner epoch K changing prob
2
0.05
[0.025, 0.063, 0. 158, 0.398, 0.631, 1, 1]
Computing Resource All experiments for Moving 2D Gaussian tested on Mac with an Intel Core CPU and 8G memory.
F.3.2 OSAKA benchmark
Model for OMF dataset We used CNN network architecture the basic model. The four modules are identical: A 3 2d convolution layer with 64 filters, stride I, and padding The following a batch normalization layer, Relu layer, and max-pooling layer of stride 2. The image data passing the aforementioned modules form a 64 x x 1 feature map, which was further taken into a fully connected layer. Then the fully connected layer outputs the logits for 10-class classification. At last, the cross-entropy loss is calculated with the logits and the corresponding labels.
Model for Synbols dataset We used CNN network architecture the basic model. The four modules are identical: A 3 x 2d convolution layer with 64 filters, stride 1, and padding 1. The following are batch normalization layer, Relu layer, and max-pooling layer of stride 2. The image data passing the aforementioned modules form 64 x 2 x feature map, which was further flattened and taken into fully connected layer. Then, the fully connected layer outputs the logits for 4-class classification. At last, the cross-entropy loss is calculated with the logits and the corresponding labels.
Training Details The hyper-parameter settings and training details for OSAKA data sets are outlined in T
47

---

Computing Resource The experiments for OSAKA were run server node with CPUs and 1 GPU of 32GB memory.
Table 6: OSAKA experimental details
Hyper-parametes parameters
OMF
Synbols
task horizon
10000
loss Q D hat guess
cross entropy
100
image size
28
32#32
image channel
n_shots
n_shots_test
15
15
1_ways
10
4
prob_statio
0.0
0.0
sample number m -n_shoos n_ ways
50
20
inner epoch
grob_env_switer p Lipsehitz constant
[0.2, 0.4, 0.6, 0.8, 1.0]
[0.2, 0.4, 1.0]
200
100
hopping Ir cta cta_0 cailon_O_ratee
1.0
0.2
6.0
1.0
4.0
prree--arrmettr Search Following OSAKA, the hyper-parameters were tuned by random search, and the same number of trials were allocated for each algorithm. For each trial, we sampled hyper- parameter combinations uniformly from the search space presented Tab. for baselines and in Tab. 8 for DCML.
According to the experimental setting of OSAKA, do need validation dataset for searching the hyper-parametery parameters. New CML episodes (task sequences) generated with different random seeds can be considered held-out data, The results reported in the paper are tested on 10 new CML episodes using the learned hyper-parametery,
Table Hyper-paramette search space for baselines
Hyper-parameters
Search space
meta-learning 1)
0.0001, 0.0005, 0.001, 0.005, 0.01 0.0005, 0.001, 0.005, 0.01, 0.05, 0.1, 0.5
base learning rate inner steps first-order modulation À
2, 4, 8, 16 True, False
0.25, 0.5, 0.75, 1.0, 1.25, 1.5, 2.0, 0.0001, 0.1 0.5, 1.0, 10
parameter variance o
step-size for parameter mean MC samples
threshold for task switch
E44 Bayes Online Changing-poii point Detection
We modify the implementation of BOCD in (52 for our experiments. The detailed method is presented in 42). Given sequence of tasks, we use the base leaner outputs wia observations of BOCD to be divided into non-overlapping product partitions. Each partition can be considered as sampled from the same static environment slot. BOCD model the detection of changing point as estimating the posterior distribution over the current run-length ra E [0, 1,... t), i.e., P(r. ((r((w::) = P(r.waa) Thus, T₁ means to start partition. P(wr:)
We treat the hypothesis as factorized Gaussian and apply BOCD on each dimension of the algorithm output W. For Moving 2D Gaussian, we detect the whole wr, since it's just 2D. Here, we provide the pseudo-code in Algorithm 3 with Gaussian Prior for each dimension applied in our experiments.
48

---

Table 8: Hyper-parameter search space for DCML
Hyper-pane Plyper-parameters
Search space
quadratic growth parameter a
0.05, 0.5, 1, 4, 8, 10 50, 100, 150, 200, 250, 300, 350, 400
Lipschitz constant L
number of inner steps K
1, 4, 8, 16
slot diameter guess / hopping learning rate p initialization 31
50, 100, 200, 400, 600
0.2, 0.4, 0.6, 0.8, 1.0
2, 4, 6, 8, 10, 12, 14, 16, 18, 20
initialization of 60
2, 8, 10
Algorithm 3 Pscudo code for detecting environment change
Require: P(ro 0) I, prior mean μ prior precision 8f 1/0.1, changing probability p. data precision 6.. = 1 for < to T do observe new algorithm output w.
evaluate the predictive probability oं P(wr (00rraT,00 67)
calculate the growth probability P(r: = r--1 + 1,, 11:11:)) P(r--1, w1 11 p) calculate the changepoint probability P(re O, (..e)) =E.., P(r w1a-1)=;p
calculate evidence P(w1+)) Er, P(r,, wi:))
update run length distribution P(r((wia) P(re: p update statistics:
04+1 = -6, 8.41 5% + 8
Mi+1 14 1411 r+1 1//541
(5) [ + w(ww)
if arg max, P(r, = k)w).))
arg max, P(re-1 k(wr=-1) then
changing point detected
end end
49

---

G Additional Discussion
G.1 Learning- w.r.t meta-updates
In this section, we offer some intuitive interpretations for the adaptive updates of the meta- parameter of the base learner.
The updates of the meta-parameter (o and 3) in Algo. 1 and 2 can be separately expressed as:
2bx.7z )d, 2bc wy and Be+1 Be Yia (ar, ne (e w +er++e)
0++1 =
B.
Considering the case that all the tasks have the same sample number. 3g reflects the confidence of AA on the given initialization for learning the task t. For example, 3r is the learning rate (step size) for SGD. A large learning rate means that the learner relies more the data, and small one means believing the prior. From the update of 33 we can see a large 3t-1 implies that the current task output is far from its initialization (llé wzll is large), which indicates the current task may be outlier, exceeding the range of meta-model for recovering its performance. Hence, the environment may have changed. So in the next task, the base learner learns more from the task data instead of keeping close to the initialization (3++1 is large).
8 The learning rate the initialization (or bias) is determined by 2b, As mentioned above, large
distance from the initialization indicates that the current task t may be an outlier. So from t + step, the tasks are treated with low confidence to update the common initialization Φ++1 with 2hx%, being 3,41
small (f++1 is large). Then until the distance w.r.t the common initialization holds small value for several rounds, /3 also decays to smaller value. The tasks start contribute more to updating the initialization.
The above mechanism works well for static environments and address forgetting in shifting environments. But it will lose tracking ability in the shifting environment, so we need slot-wise adjusting for 7/t obtain a better trade-off.
G.2 Real-world examples for practicality and necessity of CML
A typical real-world application of CML is the online recommendation system, where we aim to predict the user's preference for various products. Different users' preferences are considered as different task distributions. The distribution of users can be regarded as task environment. The recommendation system maintains a meta-mode meta-model that predicts the recent preferences shared across users and adapts task-specific models that predict the user-specific preferences.
The user queries for displaying products arrive sequentially, and the system randomly distributes several (e.g., m, 200) products in response to the query. Denote the products and the corresponding preferences for t-th user (X,, Yi) ~ pe, Vi [m,]] which are i.i.d.. The labels are initially unknown for this setting, but few labels can be acquired through the following interaction:
The meta-model predicts the preferences over products and displays them according to the predicted preference order.
Normally, the user will only view small part (m² = 50) of the distributed products, and the preference can be determined with the clicks or view time over these products, which gives the few-shot labeled samples.
Then, the task-specific model is adapted from the meta-mode with these examples. We hope the model can generalize on the rest of the unseen examples with correct preference prediction, which can provide new recommendations.
Finally, the task-specific model of each user is used for updating the meta-model. Since the shared preferences change with the season, fashion trends, and accidental events, the task environment is shifting.
G.3
More details on DCML
Relate parameters in eq. I to specific base learner Since the proposed framework is valid for different base learners, the parameters like a, b, and in the unified form of excess risk upper bounds
50

---

(cost function) are related to the specific algorithm. Since all of the experiments adopt SGD, we give here detailed description it.
According to Proposition D.4, the Ksstep SGD with learning rate f and initialization oe for the 1-th task has the following cost function:
2allor - wel1 + 6o + 2n²
[(3r, 01) = Fig
(5 x +
+ 2xie)
3e
where a 3. 20, K2 = LV
The learning rate of the base learner 7/: ( + (K)) is related to the sample number m, of each task via Ke, which can reflect the generalization.
2 maa = 2nq, A.
2xg..
Ka
Impact of the initial meta-paraan parameter on the model's behavior The initial meta parameter sub- stantially affects the model's behavior. For instance, the aforementioned recommendation system suffers from well-known cold-sturt problem. A well-pertained model initialization Φ1 can help address the problem.
Given a good initialization Φ1. 31 also affects the performance substantially. According to the meta-parant mnea--aaamettr adaptation, if is too large. the algorithm tends keep the prior knowledge and will not learn from the data. If 31 is too small, the algorithm will ignore the initialization and learn from scratch.
How does DCML adjust the meta-parameter The updates in Algo. | for the meta-parameter (Be, )x) are:
Φc+1 = (1 26k 7 )r +
2br
3, Wh, Bc+1 = 3r - - (b we 112 + e =Eo)).
Br
3e
We adjust the learning rate of the meta-parameter (7t) with the following strategy:
For k-th task inside the n-th environment (slot), "
7// Vk, where the initialization is
(1+b/a)(2+a/aa
determined by the theoretical optimal value " ma 4at2 aa
When an environment change is detected, " is set large hopping rate y = p. which is related to the path length.
How to set hyper-parameters In the experiments, we tune the following hyper- parameerss a, K, T., D 6o. 31 by random search on the defined space in Tab. Specifically for the sim- ple moving 2D Gaussian: since the loss function 2-strongly convex, we have 2.
G.4 Limitations
The proposed theory works for non-convex loss when using the Gibbs algorithm. However, We do not offer analysis for SGD with non-convex loss, where it's hard to find an easily optimizable form for the excess risk upper bound. Excess risk analysis for gradient- based learning algorithms with non-convex loss is promising but challenging direction for the deep learning community. We hope to work on this topic in the future.
In this paper, we do not provide theoretical guarantees for memory- based approaches, which can better address meta-level forgetting with additional memory cost. Future theoretical studies can be conducted to complete the framework.
G.5 Broader Impacts
In general, this work is fundamental. It aims to understand the bi-level Marming-forgettion trade-off CML and improve the model performance real-time intelligent systems with better trade-off balance. The potential negative impacts depend on the specific application.
51

---

Potential negative impacts Since the main objective is to obtain the optimal average excess risk over rounds, when each task relates to a person in some applications like personalized recommendation systems or medical diagnosis systems, it may cause some fairness issues for individuals, especially those who appear around the changing points.
How to address? The aforementioned potential unfairness can be mitigated by adding calibration providing more training data for tasks around changing points.
modules in [53 55
H
Additional Related Works
H.1 Summary and comparison of related settings
Table 9:
Comparison of different settings adapted from 13 where S and Q represent the train and
test data from the same distribution, respectively. Train data S = S U is further divided into the support and query sets, be a sub-task in CL with i.i.d. data, CLP1.M represent whole CL problems of infinite non-i.i.d data stream and P(T) is the distribution over them.
Seitings ST.
Tink Tatasess
Tooks Enemenments
Tad Farameeer (bose)
Man Updaees
Exalusion
5.0 P
Q)
CL
Suryuur Qua to Par
Pig mor (ami) ) HUz or Our (shifting)
x == AculSaar)
Ens Civ Qc)
MI.
Shar Pins (tramn usks). Pana (test makks)
W [M].M V.
V. Ei 81..8)
E 8),
CML
Sua Qur - Pai
Pir eu (sati)) Hey did (shifting)
ay S.)
E, 50.00
MCL.
B, Muar CLB W [M]
CLPA ((T)
P. E, (.Arzz(s...rr)B...
S> E, (a.A))/(..S.rre...
We present different settings related to the Continual Meta-Learning (CML) problem studied in this paper in Tab. 9
The detailed discussions in each setting can be found in the following sections.
Supervised Learning (SL) methods learn as a single task from the train data and evaluate on inde- pendent test data. The data points are assumed, i.idd. sampled from the same distribution. Continual Learning (CL) aims to learn from a sequence of non-i.i.d. tasks, where the data points inside each task are i..dd. Meta- Meta-Learning (ML) has many settings. Here, we present the statistical version. All the tasks are assumed to be i.i.d. sampled from the same task environment. The evaluation is conducted on test tasks to measure the generalization performance of the algorithm new tasks.
In Meta-Continun Learning (MCL), continual learning prediction problem (CLP) is defined as a non-i.i.d. data stream, which is a task sampled from the stationary distribution p(T). Random subsequences of dependent data points of length are sampled from each CLP task for training. The major difference between CML and MCL settings is that the non-stationarity of CML comes from the sequentially encountered non-i.i.d. task distributions. In contrast, the non-stationarity of MCL comes from the non-i.i.d. data points within task.
H.2 Continual Learning
Except for the taxonomy w.r.t different approaches mentioned in the main paper, CL can also be divided into the following three scenarios w.r.t the different properties of the task distributions
[56] 57]. Class Incremental Learning (CIL) (58) involves learning new classes over time without having access to all classes once during training. The label space is growing over time, where De C Ve+1, Vt. In the final step. the predictor is aimed to be capable of classifying all the seen classes. Domain Incremental Learning (DIL) [59] defines on the same label space y that has fixed associated semantic meaning, and the marginal distributions on input space ih (2') varies over time. Task Incremental Learning (TIL) [5] can define on different label spaces D1 & Vi+1, Vt or the same label space Y' associated to different semantic meanings over tasks. In conventional definitions, CIL and DIL are under a weak task agnostgi setting (the task identities or task boundaries are unknown during testing but known during training), while TII. is under the task- setting with known task identities. However, with increasing research diversities, TII. has also been studied in task task-agnostic settings recently. In this paper, we study CML within similar TIL scenario of CL.
52

---

Key Differences between CL and CML The two settings share the common objective of address- ing the data. Their key differences are:
dilemma, which the typical objective for learning from non-stationary
Continual Learning:
Standard CL methods sequentially adapt a task model and aim for a final model that performs well on all the tasks encountered. (Some memory-basee approaches like dynamic architecture grow a subnet for each task.)
The current task model is adapted from the previous task model.
Standard CL. reports the final performance of the agent on all the tasks the end of its lifetime.
Standard CL approaches mainly focus on minimizing catastrophic forgetting without con- sidering quick generalization for tasks with few-shot data, e.g., the replay-based and regularization- based methods.
Continual Meta-Learning:
CML methods sequentially adapt a meta-model and aim to recover the performance on previous tasks by adapting the meta-model with few additional samples. Therefore, it's more suitable for learning few-shot tasks. (Some semory-based approaches grow subnet for each environment.)
The current task model is adapted from the meta-model.
CML reports the cumulative performance of the agent throughout its lifetime.
CML focuses on quick generalization for new tasks and fast recovering performance of previous tasks with few-shot data.
H.3 Meta-Continual Learning
Javed and White 600 and Gupta et al. [6] study a different continual learning prediction problem (CLP) is defined non-i.i.d. data stream, which can be considered a CLP task T. The CLP tasks are sampled from a stationary distribution p(7), where for each CL.P task, random subsequences of dependent data points sampled from the task for training. (60) conducts offline meta-representttion learning w.r. two objectives MAML-REP and OML. MAML-REP uses batch data for inner adaptation. OML is calculated with single data point for each inner adaptation, which can reflect the degree of forgetting in CLP tasks. Gupta al. [6] proposes La-MAML, which adopts a replay buffer and conducts meta inttainitiaaization with optimization on the OML objective in online manner. In addition, La-MAML adopts modulation of per-parameter learning rates in the meta-learning updates. The optimization of learning rates in La-MAML is w.r.t empirical loss, while our learning rates optimization is based on the excess risk upper bound. So, our approach suffers less from over-fitting.
Learning (MCL) setting.
H.4 Continual Meta-Learning
Static environments Harrison et al. (32] studies continual meta-learning (CML) under task agnostic setting, where the task boundaries are unknown. It proposed algorithmic framework MOCA that incorporates different meta-learning methods with Bayesian Online Changing-pon -pint Detection (BOCD) to identify unknown task boundaries during the meta-learning process. The task environment is still assumed static. On the contrary, we focus on the bi-level trade-off in shifting task environments with known task boundaries, where we detect the environmental distribution shift, not the task distribution shift.
Shifting environments To address the environment shift, Jerfel al. proposes a non- parametric Dirichlet process mixture of hierarchical Bayesian models that allows adaptively adding new task clusters and selecting over a set learned meta-inittiliiztiin parameters for the newly encountered task. A similar approach is also used to detect the task shift in task-agnostic setting. For both task-agnostic and task-aware settings, [14] has tested the proposed algorithm on datasets with two times environment shifts. The proposed method requires additional O(K) memory for
53

---

storing the initialization parameters for the detected K clusters. For each task, it needs to update the task-specific model and the meta-model for all the K initializations. K can grow with the time.
Zhang et al. 15 use Dynamic Gaussian Mixture Model (DGMM) to model the distribution of the meta-parameterss Different from [14], which applies point estimation during inference, (15) derived a structured variational inference method that can reduce overfitting. The experiment is conducted with three times environment shifts of four datasets. [15] needs (K) extra memory for storing the meta-parameters.
Wang et al. [16] studies slightly different setting where each environment has super long task sequence. In this case, the cartographic forgetting for meta- eootalnnoweegee is more obvious. To address this, they use memory buffer to store small number of training tasks from previous environments and a shared representation for different task environments and grow the subnets when a new environment is detected on latent space using BOCD. For deciding which cluster the task belongs to, they store the average embedding for each environment for calculating the distances. Hence, its memory complexity is O(K- + M).
H.S Meta-Learning
Statistical Learning to Learn (LTL) LTL [62] has been intensively studied with various theoretic tools. The early theoretical framework was proposed by Baxter 24 where they first defined the
notion of the task environment and derived the uniform convergence bounds. And the tasks are ii.d sampled from the environment. Denevi et [63 (8) provided excess risk for ridge regression and discussed the train-validation split impact. Amit and Meir (25] applied PAC Bayes theory and provided generalization bounds for stochastic neural networks. They also derived a joint training algorithm that simultaneously updates the meta-parameter and task parameters, which cannot be extended to the sequential learning scenario. Recently, Chen al. [26] derived an information- theoretic generalization bound for the MAML-like algorithm, which provides non-vacuous bounds for deep few-shot learning and can be applied to sequential task learning.
Statistical Lifelong Learning The difference between Lifelong learning and LTL is that the tasks are observed sequentially. while LTL has all the tasks in hand. Pentina and Lampert [65] first applied PAC Bayes theory to Lifelong Learning, where they also assumed that all the tasks are, i.i.d. sampled from the task environment. In a subsequent work [66), they relaxed the i.i.d. assumption with two scenarios. The first is that the tasks are dependent, but dependency graph is known so that they can prove statistic bound. In the second, they also consider a shifting environment change. However, they assume that the base learner output of the current task only depends on the current and the previous task data, and the expected performance of the base learner does not change with time. Under these assumptions, they obtain statistical guarantees for the gradually changing environment.
64
Online LTL The online LTL methods have all the tasks in hand, but at each round f, they sample a task from the N tasks in hand. Cavallanti et al. [67] works on this setting for online multi-tase learning. Multi-task learning often treated simplified version of LTL in previous works [68]
Online Meta-Learning Two main settings to meta-learn sequential tasks in an online manner are referred to as online-vilhin-online (OWO) 31 and batch-wiihin-online (BWO) + 27 The former applies online algorithms for both base and meta learners. The latter treats task-level learning differently as statistical batch setting. The BWO setting is close to the CML. studied in this paper, while the theoretical work is rare, and none of the previous BWO methods considers shifting task environments. Khodak et al. [1I first considered shifting environments in the OWO setting, where the base learner is the madieent-based online learner. In contrast, we consider more choices of batch base learners and fine- fine-grained algorithm w.r.t environment change. Even though their bounds are not w.F. AER and the results are not directly comparable, we make an intuitive comparison, which suggests the proposed algorithm in this paper has an improved rate for gradient- gradient-based base learners in slot-wise stationary environments over their related results. Moreover, we conducted a rigorous analysis of the bi-level trade-off, which is missing the related works mentioned above. Finally, although not clearly defined in previous meta-learning literature, we note Meta Continual Learning (MCL) (+) 61 can be named in a similar way as Online- Within-Bate (OWB), where the tasks are processed in one batch, but the data within each task are processed online.
54

---

Other related works Model-Agnostic Meta-Learning (MAML) 4 that uses the higher-order gradients for meta-updates has gained tremendous success practice. Therefore. lot of work emerges to improve MAML. Finn et al. 669, Grant et al. [70], Yoon et al. 77] combine MAML. with Bayesian methods. Rajeswaran et al. 722 improves MAMI. with implicit gradient calculation for the meta-updates. Since meta-learning considers learning and generalization for both seen and unseen tasks, has not only been applied to CL for addressing catastrophic forgetting but has also been applied to Test-Time Domain Adaptation (DA) for quick generalization. For more related works in Test-Time Time DA or DA, please refer to 773755)
55


Reviews:
[{"review_id": "3nG0yRK4LD", "reviewer": "Reviewer_JcdX", "summary": "The paper presents a comprehensive theoretical framework for continuous meta-learning in both static and shifting task environments. It also conducts a theoretical analysis of the bi-level trade-off in shifting environments. Furthermore, the paper proposes a method to adapt meta-parameters and the corresponding learning rate.", "questions": "1. See Weakness 1 \n2. To better evaluate this method, it would be valuable to provide a comparison of the computation costs with other existing methods.\n", "limitations": "adequately addressed", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The main contribution of the paper is the theoretical analysis of continual meta-learning, particularly in the shifting task environment section, which illustrates the concept of meta-level forgetting.\n2. The paper provides theoretical evidence of the task-level trade-off and meta-level trade-off in continual meta-learning, offering valuable insights for optimizing the sequence of meta-parameters.\n3. The paper introduces a novel AER objective and presents the DCML algorithm, which effectively mitigates forgetting and accelerates adaptation to new environments.\n", "weaknesses": "1. In my opinion, both continual meta-learning and continual learning share the common objective of addressing the stability-plasticity dilemma, albeit in different settings.  What is the key difference between them? And are there any real applications where the settings of continual meta-learning are more suitable?\n2. It is unclear about the training efficiency compared to other methods. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's efforts to provide constructive comments which we can incorporate in the revision. Below are our responses to your comments.\n\n> Q1. \"Both continual meta-learning and continual learning share the common objective,\" \"What is the key difference between them?\"\n\n* Yes, the two settings share the common objective of addressing the stability-plasticity dilemma, which is the typical objective for learning from non-stationary data.\n\n* Their key differences are:\n  - Continual Learning (CL)\n    - Standard CL methods sequentially adapt a ***task model*** and aim for a final model that performs well on all the tasks encountered. (Some memory-based approaches like dynamic architecture grow a subnet for each ***task***.)\n    - The current task model is adapted from the ***previous task model***.\n    - Standard CL reports the ***final performance*** of the agent on all the tasks at the end of its lifetime.\n    - Standard CL approaches mainly focus on minimizing catastrophic forgetting without considering quick generalization for tasks with few-shot data, e.g., the replay-based and regularization-based methods.\n  - Continual Meta-Learning (CML)\n    - CML methods sequentially adapt a ***meta-model*** and aim to recover the performance on previous tasks by adapting the meta-model with few additional samples. Therefore, it's more suitable for learning ***few-shot*** tasks. (Some memory-based approaches grow a subnet for each ***environment***.)\n    - The current task model is adapted from the ***meta-model***.\n    - CML reports the ***cumulative performance*** of the agent throughout its lifetime.\n    - CML focuses on quick generalization for new tasks and fast recovering performance of previous tasks with few-shot data.\n\n> Q2. \"And are there any real applications where the settings of continual meta-learning are more suitable?\"\n\n* Yes. Maintaining a separate meta-model provides more plasticity to quickly generalize, which is more suitable for some online systems using few-shot labeled data or real-time feedback.\n* A representative real-world application is the online recommendation system, where we aim to predict each user's preference for various products. \n  - Different users' preferences are considered as different task distributions, and the distribution over users can be regarded as a task environment. \n  - The recommendation system maintains a meta-model that predicts the recent preferences shared across users and adapts task-specific models that predict the user-specific preferences.  \n\n* The queries for displaying products of each user arrive sequentially, and the system randomly distributes several (e.g., $m_t = 200$) products in response to the query. Denote the products and the corresponding preferences of the $t$-th user as $(X_i, Y_i) \\sim \\mu_t, \\forall i \\in [m_t]$, which are i.i.d.. The labels are initially unknown for this setting, but few labels can be acquired through the following interaction:\n  - The meta-model predicts the preferences over products and displays them according to the predicted preference order.\n  - Normally, the user will only view a small part ($m_t^\\prime=50$) of the distributed products, and the preference can be determined with the clicks or view time over these products, which gives the few-shot labeled samples.\n\n* Then, the task-specific model is adapted from the meta-model with these examples. The hope is that the model can generalize on the rest of unseen examples with a correct preference prediction, which can provide new recommendations.\n\n* Finally, the task-specific model of each user is used for updating the meta-model. The task environment is shifting since the shared preferences change with the season, fashion trends, and accidental events.    \n\n> Q3. \"Computation costs compared to other methods.\"\n\n* The computational complexities of all the methods are provided in the following table, where the run time is measured in terms of the number of gradient computations. All the methods are assumed to use a $K$-step SGD as the inner algorithm.\n  - Fine-tuning uses the meta-model as initialization and consistently updates this model w.r.t the tasks encountered. MAML and ANIL do not update the meta-model during the learning phase. Therefore, these methods need to compute $T*K$ gradients for the $T$ encountered tasks.\n  - MetaBGD and MetaCOG [8] perform CML based on MAML and use Bayesian Gradient Descent (BGD) for meta-model adaptation, which requires $M$ Monte Carlo samplings for the meta-gradient computation. Hence, the computation complexity is $\\mathcal{O}(T*(K+M))$.\n  - DCML and CMAML need one meta-gradient and $K$ inner gradients computations for each task, so the complexity is $\\mathcal{O}(T*(K+1))$.  \n\n\n\n| Methods | Computational complexity |\n| --- | --- |\n| Fine-tuning | $\\mathcal{O}(T*K)$ |\n| MetaCOG | $\\mathcal{O}(T*(K+M))$ |\n| MetaBGD | $\\mathcal{O}(T*(K+M))$ |\n| ANIL | $\\mathcal{O}(T*K)$ |\n| MAML | $\\mathcal{O}(T*K)$ |\n| CMAML | $\\mathcal{O}(T*(K + 1))$ |\n| DCML | $\\mathcal{O}(T*(K + 1))$ |\n"}, {"review_id": "3eagmGF6mg", "reviewer": "Reviewer_Rxnp", "summary": "The authors present a framework for continual meta-learning, that is the training of meta-learning models through exposure to a sequence of tasks. The paper presents a formalism for the setting which allows for non-stationary task distributions.\nTheoretical analysis is provided both for the framework and for the proposed method, and experimental validation is reported for a reasonable set of continual learning tasks.\n", "questions": "\nN/A", "limitations": "\nN/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "\n- The problem setting is interesting, and the work is thorough.\n- The experimental verification is convincing.\n", "weaknesses": "\n- I am not sure if the comparison with non-continual meta-learning method is fair.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for appreciating our work and the constructive comments. Below are our responses.\n\n> \"...if comparison with non-continual meta-learning method is fair.\"\n\n* Thanks for mentioning this point. Due to the page limit, the detailed description for the baselines was not included in the main paper, and was deferred to Appendix E.1.1. We will move these discussions to the main paper in a revised version.\n\n  - Following OSAKA , we compared the proposed algorithm with different baselines. For a ***fair comparison***, we used the *same meta-model* pre-trained with MAML for all the methods. During the continual meta-learning phase, all the methods adapt with few-shot data and are then evaluated on separate test data for each task.\n    - *ANIL* is a variation of *MAML* that only adapts the network's head w.r.t new tasks. Following OSAKA, MAML, and ANIL, we *do not update* the meta-model during the CML phase. \n    - *CMAML* includes an update modulation phase and a prolonged adaptation phase, which updates the meta-model with buffered tasks when the environment changes or a task switch is detected. Otherwise, it keeps updating w.r.t the previous model. \n    - *MetaBGD and MetaCOG* perform CML based on MAML and Bayesian Gradient Descent (BGD), where *BGD* considers randomized parameters with factorized Gaussian, slowly updating the parameters of small variance to alleviate catastrophic forgetting. In addition, Meta-COG introduced a per-parameter mask. \n    - *Fine-tuning* uses the meta-model as initialization and consistently updates this model w.r.t the tasks encountered.   \n  - As we can see, the **non-continual meta-learning** methods of the aforementioned baselines are MAML, ANIL, and Fine-tuning. \n    - MAML and ANIL do not update the meta-knowledge (so they will not suffer from forgetting) but lack the plasticity to learn from tasks in new environments. They are compared to show the problem with static representations in shifting environments. \n    - Fine-tuning is a trivial method that continually learns from data, which can be considered a lower bound in the setting to illustrate catastrophic forgetting.\n"}, {"review_id": "GdWv5PgYcI", "reviewer": "Reviewer_iCpz", "summary": "This paper theoretically studies the stability and plasticity dilemma in Continual Meta-Learning (CML). \n\nThis paper formulates the CML objective as selecting u_t at each time t to ensure a small Average Excess Risk (AER) upper bound for the task sequence. Based on the AER objective, it proposes a continual meta-learning framework in both static and shifting environments.\n\nThe proposed Dynamic Continual Meta-Learning (DCML) algorithm can quickly reconstruct meta-knowledge to alleviate forgetting and fast adapt to new environments when change occurs. \n\nThe corresponding theory provides tighter bounds and more flexible base learner selections. \n\nExperiments demonstrate the superiority of the proposed method.", "questions": "Can you discuss what applications this paper will have to memory-based approaches and what theoretical explorations can be done in the future?", "limitations": "The proposed theory works for non-convex loss when using Gibbs algorithm. However, this paper does not offer an analysis for SGD with non-convex loss.\n\nThis paper does not provide theoretical guarantees for memory-based approaches, which can better address the meta-level forgetting with additional memory cost. \n\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper first introduces a novel and unified theoretical framework for CML in both static and shifting task environments.\nAdaptively learning the meta-parameter can facilitate the training process in deep learning. \n\nThe paper is written and organized well.\n\nThe source code is provided.\n\nThe paper has good and relevant citations.\n\nThe results are quite extensive and convincing.", "weaknesses": "The paper lacks a clear figure that contextualizes the base model, learner, and how continual meta-learning fits into the setup. This visual representation would enhance understanding for readers.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe sincerely thank the reviewer for appreciating the strength of our work and the constructive suggestions. Below are our responses to your comments.\n\n\n> The paper lacks a clear figure that contextualizes the base model, learner, and how continual meta-learning fits into the setup. This visual representation would enhance understanding for readers.\n* Thanks for the helpful suggestion. We have ***added a figure for the corresponding visualization in the rebuttal file***. Please refer to ***Figure A.1***.  \n\n* At each time t, $\\mathcal{A}\\_{\\text{CML}}$ takes the knowledge $u_t$ learned from previous tasks and current task data $S_t$ as input, then outputs the learned hypothesis $W_t$ for the current task and the updated prior knowledge $u_{t+1}$ for the next task. The task environment is static if $\\tau_t = \\tau, \\forall t \\in [T]$.\n\n* The whole CML algorithm $\\mathcal{A}\\_{\\text{CML}}$ is a composition of the meta learner and base learner. In the paper , we have $\\mathcal{A}\\_{\\text{base}} \\in \\\\{\\text{SGD, SGLD, Gibbs, RLM}\\\\}$. However, the illustrated continual meta-learning process is valid for other algorithm choices. \n \n\n\n> Can you discuss what applications this paper will have to memory-based approaches and what theoretical explorations can be done in the future?\n\n* The DCML algorithm proposed in the paper maintains only one meta-model. The primary idea for incorporating memory-based approaches is to maintain multiple meta-models and choose the closest meta-model or the weighted majority one as initialization for each task. We can derive regret bounds for this setting. \n* However, the challenge lies in deciding whether to grow a new meta-model or to update previous meta-models when an environment shift is detected within the predefined memory budget. Providing the corresponding theoretical guarantees for this would be valuable.\n* Another exciting direction for theoretical exploration is to quantify the amount of memory needed for successful continual meta-learning as those conducted for continual learning in [1,2].\n\n[1]  Jeremias Knoblauch, Hisham Husain, and Tom Diethe. Optimal\ncontinual learning has perfect memory and is NP-hard. In\nInternational Conference on Machine Learning, pages 5327–\n5337, 2020.\n\n[2] Chen, Xi, Christos Papadimitriou, and Binghui Peng. \"Memory bounds for continual learning.\" 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022.\n"}, {"review_id": "Be50c1j6ys", "reviewer": "Reviewer_9fyt", "summary": "The paper considers a continual meta-learning setting with both static and dynamically changing environments and seeks to study the trade-off between learning and forgetting. It derives an upper bound on the excess risk, i.e. the expected gap between the true risk of the predictor and the optimal true risk and uses the average excess risk across tasks as a meta-objective to develop an algorithm that can meta-learn online. The resulting algorithm is empirically evaluated on a synthetic task and a subset of the OSAKA continual meta-learning benchmark. ", "questions": "1. Could you please comment to what extent the assumption of $\\alpha$-quadratic-growth in Theorem 3.1 is justified in the context of the loss of neural networks and the settings considered empirically?\n2. In Figure 2b is the plotted AER computed from the equation in Theorem 5.1 or is it measured independently? I am asking to understand whether this entails an empirical verification of the theory or a visualisation of it.\n3. In Figure 2b BOCD only detects few change points and seems to do so mostly incorrectly. Could you clarify where your algorithm uses these? The plot over the \"meta lr\" suggests that the ground truth change points are used and neither \"oracle\" nor \"window\" rely on empirically detected change points.\n4. Why does \"window\" perform better than \"oracle\" in Figure 3? Would we not expect the opposite?\n5. In line 358-359 you state \"MAML and ANIL do not suffer forgetting since they never update meta-parameters.\" In light of this, why does their performance vary over time in Figure 4? Does this also hold true for Figure 3? If so have they been pre-trained for the Moving 2D Gaussian task?\n6. In Figure 4, why is there already such a clear gap between algorithms at $t=0$?\n7. How are the hyperparameters tuned? Specifically how have they been tuned for baselines for the modified OSAKA tasks? Could you please report these details?\n  ", "limitations": "Limitations have been addressed appropriately.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper derives novel upper bounds on the average excess risk across a number of methods.", "weaknesses": "- Despite its framing, the general approach of using a bound to derive a meta-objective is not completely novel and related work should be more prominently referenced (e.g. [1]).\n\n- The method introduces many hyperparameters and it is unclear where improvements result from. An empirical verification of the theory in the considered settings is missing and ablations on different components of the algorithm that are not necessarily prescribed by the theory (e.g. annealing $\\gamma_t$) are missing.\n\n- The presentation of the paper needs to be improved by better motivating and contextualizing theorems and ensuring that all symbols are defined in the main text.\n\n[1] Amit, Ron, and Ron Meir. \"Meta-learning by adjusting priors based on extended PAC-Bayes theory.\" International Conference on Machine Learning. PMLR, 2018.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments on the experimental details.  Below are our responses.  \n\n> Weakness 1. Novelty and citation\n\n- We appreciate the suggestion for a more prominent citation of [1], which used a bound to derive the meta-objective for ***statistical meta-learning***. Due to the page limit, we have briefly discussed [1] in the appendix, which will be moved to the main paper in the revised version.\n- In contrast to [1], we focus on the more challenging problem of learning from **non-i.i.d. sequential** tasks originating from a **possiblely shifting** environment. [1] assumes a **static** task environment, and the algorithm derived from the meta-objective requires a joint training process (simultaneously updating the meta-parameter and task parameters), which cannot be extended to the **sequential** learning scenario. \n- Moreover, we want to highlight our theoretical contribution of the first formal analysis of the **bi-level trade-off** for CML in shifting environments, which provides a better understanding of the non-trivial online statistical mixture learning problem. \n\n> Weakness 2. Unclarities\n\n* Thanks for mentioning these points. We will add corresponding discussions in the revised version.  \n  * Due to the formulation of a unified theory, it seems that we have introduced many hyper-parameters. However, by setting the base learner as SGD, we only need to tune the hyper-parameters shown in Table 2 (**rebuttal file**), no more than the previous methods.\n  * The improvements come from the adaptive updates of the meta-parameter and its learning rate that considers the sample number and the environment change, providing a better forgetting-generalization trade-off, as discussed in Sec.4 and 6.\n  * Annealing $\\gamma_t$ is theoretically grounded with online convex optimization and proved in Theorem 5.1, where the theoretical optimal value of $\\rho$ and $\\gamma_0$ are presented in the proof. In the experiments, we directly tune $\\rho$ and use the theoretical optimal value for $\\gamma_0$, which is tuned with other hyper-parameters like the slot diameter $\\hat{D}$.\n  \n> Weakness 3. Presentation \n\n* Thanks for the suggestion. We will add a notation table for better presentation.\n\n> Q1. $\\alpha$-quadratic-growth\n\n* As discussed in Appendix E.3.1, we have $\\alpha=2$ for a moving 2D Gaussian since the square loss is 2-strongly convex. The lasso, sparse logic regression also satisfies the quadratic-growth condition. Whether the condition can be satisfied for deep learning depends on the loss function and the hypothesis set $\\mathcal{W}$. However, tuning $\\alpha$ as a hyper-parameter can achieve satisfactory results.\n\n>Q2. Figure 2b, AER\n  \n* In Figure 2(b), we have empirically verified the inequality in Theorem 5.1 by estimating both sides for SGD. \n  - For the left-hand side, we have $AER_{\\mathcal{A}}^T = \\frac{1}{T}\\sum\\_{t=1}^T R_{excess}(\\mathcal{A}, u_t) ≈ \\frac{1}{T} \\sum\\_{t=1}^T \\mathcal{L}\\_{\\mu_t}(w_t) - \\frac{1}{T}\\sum_{t=1}^T\\mathcal{L}\\_{\\mu_t}(w_t^*)$, where the first term is estimated by the ***average test loss*** (the first subplot). In addition, we have $X\\sim \\mathcal{N}(w_t^*, 0.1 I_2)$. Hence, $\\mathcal{L}_{\\mu_t}(w_t^*) = \\min_w \\mathbb{E}_X \\|\\|w -X\\|\\|^2 = \\mathbb{E}_X[\\|\\|\\mathbb{E}[X] - X\\|\\|^2] = 0.2$.\n  - The right-hand side (the AER bound) was computed by empirically estimating the slot diameter (of the base learner outputs) $D_n$, the slot variance $V_n$, and the path length.  \n\n>Q3. BOCD\n\n* Sorry for the confusion caused. In Figure 2b, we did not use BOCD. We used BOCD and compared different detection methods in Figure 6 in Appendix E.2.1.\n\n> Q4. Window better than oracle\n\n* This result is related to the algorithm, which does not necessarily hold for other methods that maintain multiple meta-models. By updating a **single meta-model online**, the context switch cost exists (Line 373) for reconstructing the meta-knowledge in each slot. Setting a fixed window size can ensure the meta-knowledge quality of each slot and yield good performance on average. \n* In addition, the phenomenon is related to the **overlap between the consecutive environment distributions** and the **environment shift probability $p$**. We empirically tested these factors, and the result is presented in Figure A.2 (**rebuttal file**). \n  - In Figure A.2, \"oracle\" is better than \"window\" when $p < 0.1$, and the gap becomes more evident when the distribution overlap is smaller.\n\n> Q5. MAML, ANIL\n\n* Figure 4. illustrates the *running performance* for **each environment**. \n  - Given a fixed meta-parameter $u$, the average performance inside each environment is a proxy of the expectation, e.g., $\\frac{1}{T} \\sum_{t=1}^T \\mathcal{L}\\_{S_t}(w_t) ≈ \\mathbb{E}\\_{\\mu \\sim \\tau_{mnist}} \\mathbb{E}\\_{S\\sim \\mu}\\mathcal{L}\\_{\\mu}(\\mathcal{A}(u, S))$. \n  - In the figure, MAML and ANIL only slightly vary at the early stage where $T$ is small. The variation decreases as $T$ grows according to the law of large numbers.\n* This does not hold for Figure 3 since it reports the *final performance* w.r.t different $p$ on the **overall environment $\\tau$**, where $\\tau$ changes with $p$.\n* We did not use a pre-trained model for the Moving 2D Gaussian, since the data is very simple.\n\n> Q6. Why clear gap at $t=0$?\n\n- Figure 4. compares the average performances in **each environment** over ten episodes.\n- The initial **learning rates of the base learner** of compared methods are different since they are tuned to achieve their best performance for the **overall environment**. \n- Hence, as observed, there is a gap at t=0 though the meta-model is the same.\n\n> Q7. Hyper-parameter tuning\n\n* Following OSAKA, the hyper-parameters were tuned by random search, and the same number of trials were allocated for each algorithm. \n* For each trial, we sampled hyper-parameter combinations uniformly from the search space presented in Table 1 for baselines and in Table 2 for DCML (see the **rebuttal file**). "}, {"review_id": "tC4URdJ3zm", "reviewer": "Reviewer_HjRj", "summary": "This paper aims to address the balance between stability (preserving past knowledge) and plasticity (rapid learning from new experiences) in Continual Meta-Learning (CML). The authors propose a novel theoretical framework for CML in both static and shifting task environments. They discuss the bi-level (task- and meta-) trade-off in shifting environments and theoretically identify factors that affect stability and plasticity. They then propose a novel algorithm, Dynamic Continual Meta-Learning, that addresses the bi-level trade-off in shifting environments. DCML minimizes the expected regret by dynamically adjusting the meta-parameter and its learning rate when an environment change is detected.", "questions": "1. Could the authors provide more details on how the algorithm dynamically adjusts the meta-parameter and its learning rate when an environment change is detected? Also, it would be helpful to see how beta actually moves during training.", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper is theoretically robust, proposing a unified framework for understanding CML in both static and shifting task environments.\n2. The paper is the first theoretical work studying the stability-plasticity dilemma in CML with bi-level shifts.\n3. Based on the theoretical findings, the authors introduce a novel and practical algorithm which show improved estimated bounds and superior performance compared to baselines.", "weaknesses": "1. From a non-expert perspective, the practicality and necessity of the problem the paper addresses are unclear to me. While meta continual learning is understandable (non-stationarity comes from the non-i.i.d data points within a task), it's not clear why continual meta-learning (non-stationarity comes from the task changes for each time step) is a practical scenario. More real-world examples or explanations of why continual meta-learning is required would be beneficial.\n2. The paper lacks a clear, detailed explanation of the robustness of the proposed algorithm. For instance, it's unclear how to set parameters such as a, b, and kappa for DCML. Additionally, the impact of the initial meta parameters (beta) on the model's behavior is not well-explained.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe sincerely thank the reviewer for appreciating the strength of our work and the constructive comments we can incorporate into the revision. Below are our responses to your comments.\n\n> Weakness 1. “Real-world examples for practicality and necessity of CML.”\n\n* A representative real-world application of CML is the online recommendation system, where we aim to predict each user's preference for various products. \n  - Different users' preferences are considered as different task distributions, and the distribution over users can be regarded as a task environment. \n  - The recommendation system maintains a meta-model that predicts the recent preferences shared across users and adapts task-specific models that predict the user-specific preferences.  \n\n* The queries for displaying products of each user arrive sequentially, and the system randomly distributes several (e.g., $m_t = 200$) products in response to the query. Denote the products and the corresponding preferences of $t$-th user as $(X_i, Y_i) \\sim \\mu_t, \\forall i \\in [m_t]$, which are i.i.d.. The labels are initially unknown for this setting, but few labels can be acquired through the following interaction:\n  - The meta-model predicts the preferences over products and displays them according to the predicted preference order.\n  - Normally, the user will only views a small part ($m_t^\\prime=50$) of the distributed products, and the preferences can be determined with the clicks or view time over these products, which yields the few-shot labeled samples.\n\n* Then, the task-specific model is adapted from the meta-model with these examples. And we hope that the model can ***generalize on the rest of unseen examples*** with correct preference prediction, which can provide new recommendations.\n\n* Finally, the task-specific model of each user is used for updating the meta-model. The task environment is shifting since the shared preferences change with the season, fashion trends, and accidental events.    \n\n> Weakness 2. \"detailed explanation of the robustness of the proposed algorithm...\"\n\n* How to set parameters like $a,b,\\kappa$\n  - Since the proposed framework is valid for different base learners, the parameters like $a$, $b$, and $\\kappa$ in the unified form of excess risk upper bounds (cost function) are related to the *specific algorithm*. \n  - We have related these parameters for the Gibbs algorithm and SGD in Proposition D.1 and Proposition D.4, respectively. A more general derivation for all the algorithms is provided in Theorem 3.1. \n  - Since all of the experiments adopt SGD, we give here a detailed description for it.\n    - According to Proposition D.4, the $K$-step SGD with learning rate $\\eta_t$ and initialization $\\phi_t$ for the $t$-th task has the following cost function:\n        $f(\\beta_t, \\phi_t)=\\kappa_t\\left(\\frac{1}{2}\\beta_t + \\frac{2\\alpha\\|\\|\\phi_t-w_t\\|\\|^2 + \\epsilon_0 + 2\\kappa_t^2}{\\beta_t} + 2\\kappa_t\\right),$\n    where $a=\\frac{1}{2}, b=2\\alpha, \\kappa_t=L\\sqrt{\\frac{1}{K\\alpha}+\\frac{2}{m_t\\alpha}},\\epsilon_t=2\\kappa_t^2, \\Delta_t=2\\kappa_t$. \n    - The learning rate of the base learner $\\eta_t=(\\frac{\\beta_t}{\\kappa_t} + 2)/(K\\alpha)$ is related to the sample number $m_t$ of each task via $\\kappa_t$, which can reflect the generalization.  \n\n* Impact of the initial meta-parameter on the model's behaviour. \n  - The initial meta-parameter affects substantially the model's behaviour. For instance, the aforementioned recommendation system suffers from a well-known **cold-start** problem. A well pertained model initialization $\\phi_1$ can help addressing the problem.\n  - Given a good initialization $\\phi_1$, $\\beta_1$ also affects the performance substantially. According to the meta-parameter adaptation, if $\\beta_1$ is *too large*, the algorithm tends to keep the prior knowledge and *will not learn* from the data. If $\\beta_1$ is *too small*, the algorithm will ignore the initialization and *learn from scratch*. \n\n> Q1. \"more details on how the algorithm dynamically adjusts the meta-parameter and its learning rate\"\n\n* Adjust the meta-parameter:\n\n  - The meta-parameter adaptation $u_{t+1} = \\Pi_{\\mathcal{U}}(u_{t} - \\gamma_t \\nabla f_t(u_t))$ corresponds to:\n    \n    - $\\phi_{t+1} = (1 - \\frac{2b\\kappa_t\\gamma_t}{\\beta_t})\\phi_t + \\frac{2b\\kappa_t\\gamma_t}{\\beta_t} w_t$  and $\\beta_{t+1} = \\beta_t- \\gamma_t (a\\kappa_t - \\frac{\\kappa_t(b\\|\\|\\phi_t-w_t\\|\\|^2 + \\epsilon_t + \\epsilon_0)}{{\\beta_t}^{2}})$.\n* Adjust the learning rate of the meta-parameter ($\\gamma_t$):\n  - For $k$-th task inside the $n$-th environment (slot), $\\gamma_t = \\gamma_0/\\sqrt{k}$, where the initialization is determined by the theoretical optimal value $\\gamma_0=\\frac{\\epsilon_0}{\\kappa_t}\\sqrt{\\frac{(1+b/a)\\hat{D}^2 + \\epsilon_t/\\alpha}{4ab^2\\hat{D}^2\\epsilon_0+a^2(b*\\hat{D}^2+\\epsilon_t^2)^2}}$.\n  - When an environment change is detected, $\\gamma_t$ is set to a large hopping rate $\\gamma_t=\\rho$, which is related to the path length.\n\n\n* How to set hyper-parameters:\n  - In the experiments, we tune the following hyper-parameters $\\alpha, K, L, \\hat{D}, \\epsilon_0, \\rho, \\beta_1$ by random search on the defined space in Table 2 (***rebuttal file***). Specifically for the simple moving 2D Gaussian: since the loss function is 2-strongly convex, we have $\\alpha=2$.\n\n* How $\\beta$ actually moves?\n  - In Figure A.3 (***rebuttal file***), we plot the adaptation process to show how $\\beta_t$ and $\\gamma_t$ move during the continual meta-learning process.\n  - In the figure, meta_lr is the learning rate of the meta-initialization $\\phi_t$, which equals $\\frac{2b\\kappa_t\\gamma_t}{\\beta_t}$. The base learner learning rate (base_lr) is $\\eta_t=(\\frac{\\beta_t}{\\kappa_t} + 2)/(K\\alpha)$. \n  - We can observe from Figure A.3 that meta_lr $\\propto\\gamma_t , \\frac{1}{\\beta_t}$ and base_lr $\\propto \\beta_t$, which is consistent with their mathematical definitions."}]

Author rebuttal:

We appreciate the diligent efforts of the reviewers in thoroughly reviewing our paper and providing insightful feedback. In response to the valuable comments, we have included supplementary figures and tables to better address the raised concerns.

Meta-review: The paper presents a framework for continual meta-learning, a setting that trains meta-learning models via a sequence of non-stationary tasks. Theoretical analysis and a practical method is proposed for the framework. Experimental validation is reported for a reasonable set of continual learning tasks.

After the rebuttal, all reviewers are in favor of accepting the paper. Most concerns from the reviewers are sufficiently addressed (a minor outstanding issue is to improve the writing for a wider audience).
Decision: Accept (poster)