Algorithm Design for Online Meta-Learning with Task Boundary Detection

Authors: daouda  sow
sen  lin
yingbin  liang
junshan  zhang
Venue: CPAL_cc_2024_Conference
Published: 2023-10-31 03:44:51

Abstract: Online meta-learning has recently emerged as a marriage between batch meta-learning and online learning, for achieving the capability of quick adaptation on new tasks in a lifelong manner. However, most existing approaches focus on the restrictive setting where the distribution of the online tasks remains fixed with known task boundaries. In this work, we relax these assumptions and propose a novel algorithm for task-agnostic online meta-learning in non-stationary environments. More specifically, we first propose two simple but effective detection mechanisms of task switches and distribution shift based on empirical observations, which serve as a key building block for more elegant online model updates in our algorithm: the task switch detection mechanism allows reusing of the best model available for the current task at hand, and the distribution shift detection mechanism differentiates the meta model update in order to preserve the knowledge for in-distribution tasks and quickly learn the new knowledge for out-of-distribution tasks. In particular, our online meta model updates are based only on the current data, which eliminates the need of storing previous data as required in most existing methods. We further show that a sublinear task-averaged regret can be achieved for our algorithm under mild conditions. Empirical studies on three different benchmarks clearly demonstrate the significant advantage of our algorithm over related baseline approaches.

Main paper: 
 introduction: 
 Two key aspects of human intelligence are the abilities to quickly learn complex tasks and continually update their knowledge base for faster learning of future tasks. Meta-learning [1] [2] [3] and online learning [4] [5] [6] are two main research directions that try to equip learning agents with these abilities. In particular, meta-learning aims to facilitate quick learning of new unseen tasks by building a prior over model parameters based on the knowledge of related tasks, whereas online learning deals with the problem where the task data is sequentially revealed to a learning agent. To achieve the capability of fast adaptation on new tasks in a lifelong manner, online meta-learning [3, 7, 8] has attracted much attention recently. Considering the setup where online tasks arrive one at a time, the objective of online meta-learning is to continuously update the meta prior based on which the new task can be learnt more quickly after the agent encounters more tasks.In online meta-learning, the agent typically maintains two separate models, i.e., the meta-model to capture the underlying common knowledge across tasks and the online task model for solving the current task in hand. Most of the existing studies [3, 9] in online meta-learning follow a "resetting" strategy: quickly adapt the online task model from the meta model using the current data, update the meta model and reset the online task model back to the updated meta model at the beginning of the next task. This strategy generally works well when the task boundaries are known and the task distribution remains stationary. However, in many real-world data streams the task boundaries are not directly visible to the agent [7, 10, 11] , and the task distributions can dynamically change during the online learning stage. Therefore, in this work we seek to solve the online meta-learning problem in such more realistic settings.Needless to say, how to efficiently solve the online meta-learning problem without knowing the task boundaries in the non-stationary environments is nontrivial due to the following key questions: (1) How to update the meta model and the online task model? Clearly, the "resetting" strategy at the moment of new data arriving is not desirable, as adapting from the previous task model is preferred when the new data belongs to the same task with the previous data. On the other hand, the meta model update should be distinct between in-distribution (IND) tasks, where the current knowledge should be preserved, and out-of-distribution tasks (OOD), where the new knowledge should be learnt quickly. (2) How to make the system lightweight for fast online learning? The nature of online meta-learning precludes sophisticated learning algorithms, as the agent should be able to quickly adapt to different tasks typically without access to the previous data. And dealing with the environment non-stationarity should not significantly increase the computational cost, considering that the environment could change fast during online learning.Our main contributions can be summarized as follows.(1) (Novel algorithm design) We propose a novel online meta-learning algorithm in non-stationary environments without knowing the task boundaries, which appropriately addresses the problems above. More specifically, we first propose two simple but effective mechanisms to detect the task switches using the classification loss and detect the distribution shift using the Helmholtz free energy [12] , respectively, as motivated by empirical observations. Based on these detection mechanisms, our algorithm provides a finer treatment on the online model updates, which brings in the following benefits: (1) (task knowledge reuse) The detection of task switches enables our algorithm to reuse the best model available for each task, avoiding the "resetting" to the meta model at each step as in most previous studies; (2) (judicious meta model update) The detection of distribution shift allows our algorithm to update the meta model in a way that the new knowledge can be quickly learnt for out-of-distribution tasks whereas the previous knowledge can be preserved for in-distribution tasks;(3) (efficient memory usage) Our algorithm does not reuse/store any of the previous data and updates the meta model at each online episode based only on the current data, which clearly differs from most existing studies [8, 10, 13] in online meta-learning.(2) (Extensive experiments) We conduct extensive experiments in three different standard benchmarks for online meta-learning. As indicated by the experimental results, our algorithm significantly outperforms the related baselines methods on all benchmarks. The ablation study also verifies the effectiveness of the proposed detection mechanisms.(3) (Theoretical analysis) We provide a regret analysis of the proposed algorithm by taking task boundary detection into account, where a sublinear task-averaged regret can be achieved under mild conditions. In particular, our result captures a trade-off between the impact of task similarity on the performance of standard online meta-learning with known task boundaries and the performance under task boundary detection uncertainty. Namely, when tasks are more similar, better performance can be achieved due to less task variations over time, but it is harder to detect task switches.Related Work: Meta-learning. Also known as learning to learn, meta-learning [3, 14, 15] is a powerful tool for leveraging past experience from related tasks to quickly learn good task-specific models for new unseen tasks. As a pioneering method that drives recent success in meta-learning, model-agnostic meta-learning (MAML) [3] seeks to find good meta-initialization such that one or a few gradient descent steps from the meta-initialization leads to a good task-specific model for a new task. Several variants of MAML have been introduced [16] [17] [18] [19] [20] [21] [22] [23] . Other approaches are essentially model based [2, [24] [25] [26] and metric space based [1, 14, 27, 28] .Online Learning. In online learning [4, 6, 29] , cost functions are sequentially revealed to an agent which is required to select an action before seeing each cost. One of the most studied approach is follow the leader (FTL) [4] , which updates the parameters at each step using all previously seen loss functions. Regularized versions of FTL have also been introduced to improve stability [30, 31] . Similar in spirit to our work in terms of computational resources, online gradient descent (OGD) [32] takes a gradient descent step at each round using only the revealed loss. However, traditional online learning methods do not efficiently leverage past experience and optimize for zero-shot performance without any adaptation. In this work, we study the online meta-learning problem, in which the goal is to optimize for quick adaptation on future tasks as the agent continually sees more tasks.Online Meta-learning. Online meta learning was first introduced in [13] . Pioneering methods [8, 13, 33] follow a FTL-like design approach, which requires storing previous tasks and leads to a linear growth of memory requirement. Follow-the-regularized-leader (FTRL) [31] approach has also been extended to the online meta learning setting in [34, 35] , resulting in a better memory requirement. [9] proposed a memory-efficient approach based on summarizing previous task experiences into one state vector. However, these approaches require knowledge of task boundaries and "reset" the task model to the meta model at each online episode [3, 36] . Similar to [9] , our algorithm also overcomes the linear memory scaling. But unlike their method, we do not need to know task boundaries and consider dynamic environments. [10] alleviates the "resetting" issue by updating the online model always starting from its previous state, which however needs to store previous models and has limited performance especially in dynamic environments where successive tasks can be very different.None of the methods above considered the online meta-learning problem in a dynamic environment setting where the task distributions change substantially over time without knowing the task boundaries. [11] is the first work that empirically evaluated the proposed algorithm in a dynamic environment, but did not propose a method to quickly learn the knowledge for out-of-distribution tasks. In contrast, we update the meta representations in a way that preserves the in-distribution knowledge while continually improving fast adaptation for out-of-distribution tasks. 
background and problem formulation: 
 Background. We first briefly introduce some related concepts about online meta-learning.Meta-learning via MAML. Meta-learning [3, 14, 15] , a.k.a., learning to learn, seeks to quickly learn a new task with limited samples by leveraging the knowledge from similar tasks. More specifically, the objective therein is to learn a meta model based on a set of tasks {T i } M i=1 drawn from some unknown distribution P(T ), from which task-specific models can be quickly obtained for new tasks from the same stationary distribution P(T ). Taking MAML as an example, the objective therein is to learn a model initialization θ such that one or a few gradient descent steps from θ can lead to a good model for a new task T ∼ P(T ), by solving the following problem with training tasks {T i } M i=1 :EQUATIONwhere task model ϕ i = U i (θ) = θ -α∇ fi (θ), fi and f i are the training and test losses for task T i .Online learning. In the general online learning problem, loss functions are sequentially revealed to a learning agent: at each step t, the agent first selects an action θ t , and then a cost f t (θ t ) is incurred. The goal of the agent is to select a sequence of actions to minimize the following static regretEQUATIONi.e., the gap between the agent's predictions {f t (θ t )} T t=1 and the performance of the best static model in hindsight. A successful agent achieves a regret R(T ) that grows sublinearly in T . Online learning is a well studied field and we refer the readers to [37] for more information.Online meta-learning. As a marriage between online learning and meta-learning, online meta-learning [7, 8, 13] aims to achieve the following two features: (i) fast adaptation to the current task (the meta-learning aspect); (ii) learn to adapt even faster as it sees more tasks (the online learning aspect). Specifically, the agent observes a stream of tasks S = {T 1 , T 2 , ..., T T } sampled from P(T ), where tasks are revealed one at a time. For each task T t , the agent has access to a support set S t for task-specific adaptation and a query set Q t for evaluation. The goal here is to select a sequence of meta models {w t } for achieving sublinear growth of the following regretEQUATIONwhere U t is the task adaptation function depending on the support set S t , and the cost function f t is evaluated using the adapted parameters U t (w t ) on the query set Q t . Intuitively, the agent seeks to learn a better meta model which leads to better task models for future tasks after seeing more tasks.Online meta-learning in non-stationary environments. Differently from most online meta-learning studies [7-10, 13, 33] , in this work we consider a more realistic scenario:Pre-trained meta model. In many real applications, there is plenty of data available for pre-training, and it is unrealistic to deploy an agent in complex dynamic environments without any basic knowledge of the tasks at hand [11] . Therefore, following the same line as in [11] , we assume that there is a set of training tasks {T 0 i } M i=1 drawn from some unknown distribution P 0 (T ). And as standard in meta-learning, each pre-training task T 0 i has a support dataset S 0 i and a query dataset Q 0 i . In this work, we employ MAML over the training tasks to learn a pre-trained meta model.During the online meta-learning phase, we assume that the task boundaries are unknown, i.e., the so-called task-agnostic setup [11] , in the sense that the agent does not know if the new coming data at time t belongs to the previous task or a new task. To model the uncertainty about task boundaries, we assume that at any time t the new data belongs to the previous task with probability p ∈ (0, 1) or to a new task with probability 1 -p.Non-stationary task distributions. During the online meta-learning phase, the agent could encounter new tasks that are sampled from other distributions instead of the pre-training one P 0 (T ). To capture this non-stationarity in task distribution, we assume that whenever a new task arrives during online learning, it will be sampled either from P 0 (T ) with probability η ∈ (0, 1) or from a new (w.r.t. P 0 (T )) distribution with probability 1 -η. Note that we do not restrict the number of new distributions that can be encountered during online learning and the task distributions can be revisited. 
proposed algorithm under distribution shifts: 
 To address the online meta-learning problem mentioned above for non-stationary environments, we next propose a simple but effective algorithm, called onLine mEta lEarning under Distribution Shifts (LEEDS), based on the detection of task switches and distribution shift to assist fast online learning. Following most studies [10, 11] in online meta-learning, we maintain two separate models during the online learning stage: θ for the meta model and ϕ for the online task model.To enable fast learning of a new task in online learning, the detection mechanisms can not be overly sophisticated, but have to be efficient with high detection accuracy. Towards this end, we propose two different methods for detecting the task switch and the distribution shift, respectively, which work in concert as key components of LEEDS.Detection of task switches. To understand the learning behaviors under task switches, we evaluate the classification loss of the previous task model using the newly coming data, i.e., L(ϕ t-1 ; S t ) for time t, where L is the loss function, ϕ t-1 is the previous online model at time t -1, and S t is the current support set. The left plot in Fig. 1 shows the empirical results on an online few-shot image recognition problem. As depicted, the loss value keeps decreasing as the agent receives more data from the same task but suddenly increases whenever a new task arrives. This is clearly reasonable as the learnt online model for the previous task does not fit the new task anymore. Inspired by this empirical observation, we use a simple mechanism based on the value of L(ϕ t-1 ; S t ) to detect the task boundaries: there is a task switch whenever the loss is above some pre-defined threshold. As demonstrated later in Section 5, such a simple mechanism is indeed quite effective as corroborated by its high detection accuracies on various online meta-learning problems.Detection of distribution shift. To efficiently determine if a new task is IND or OOD, i.e., sampled from the pre-training task distribution or not, we consider an energy-based OOD detection mechanism with a binary classifier C τ (•; θ) defined as followsEQUATIONwhere E(x; θ) = -δ log K k=1 exp (-g k (x; θ)/δ) corresponds to the Helmholtz free energy for input x, g k (•; θ) is the k-th component of the prediction model's output, and δ is the temperature parameter. The hyperparameter τ is a threshold that can be set using the pre-training tasks. As shown in [12] , the negative energy is linearly aligned with the likelihood of the of input x under model θ, making it a useful score for distinguishing IND and OOD tasks.Ours O(1)[10] O(T ) [11] O( 1 1-p ) [9]O(1) [13] O(T )Figure 1 : Left plot: Variations of the online loss for a pre-trained meta model using MAML which is deployed for online learning. Red dot at 0 means no task switch at that time, and at 1 means the task switched at that time. Right table : Comparison of the memory requirements among different methods. T is number of online rounds and p ∈ (0, 1) is non-stationarity level.Based on the two detection schemes, the next question is how to update the meta and task models for fast adaption in dynamic environments.Without such detection mechanisms, previous online meta-learning algorithms [9, 13] typically adapt the task model from the meta model using a support set, evaluate the adapted model on a query set, and reset the task model to the meta model when new data is received from the online data stream process, and then repeat the process again. However, such a "resetting" scheme can be sub-optimal in realistic scenarios. For instance, if the newly received data belongs to the same task with the previous data, the agent should update the task model by starting from previously adapted parameters instead of from the meta model.In contrast, the simple but effective detection mechanisms in this work enable a more elegant treatment to the knowledge update during online learning:(1) If there is a task switch at time t, i.e., L(ϕ t-1 ; S t ) > ℓ where ℓ is the threshold, adapting from the meta model is generally better than adapting from the task model of the previous task. Therefore, we first obtain the online task model ϕ t from the meta model using the new data:ϕ t = θ adapt = θ t-1 -α 1 ∇ θt-1 L(θ; S t), and then update the meta model no matter if there is a distribution shift, so as to incorporate the knowledge of the new task to the meta model:θ t = θ t-1 -α 2 ∇ θ L(θ adapt ; Q t ).(2) If there is no task switch, i.e., L(ϕ t-1 ; S t ) ≤ ℓ, we continue to update the task model from the previous task model using the new data, different from the "resetting" scheme in the literature:ϕ t = ϕ t-1 -α 1 ∇ ϕt-1 L(ϕ t-1 ; S t ).To accelerate the knowledge learning for the new domains, we further distinguish the meta model update for IND and OOD tasks. In particular, if the current task is an IND task, we will only update the meta model once at the beginning of this task. That is to say, the meta model will not be further updated within the same task. In stark contrast, if the current task is an OOD task, we continue to update the meta model whenever new data for this task arrives as follows:θ adapt = θ t-1 -α 1 ∇ θ L(θ t-1 ; S t ), θ t = θ t-1 -α 2 ∇ θ L(θ adapt ; Q t ).The details of LEEDS can be found in Algorithm 1. Note that the performance of LEEDS is indeed robust to the threshold parameters ℓ and τ as shown later in our experimental results, and we also explain the heuristics for setting the thresholds in a more effective manner in the appendix.One important feature of the proposed algorithm LEEDS is that the meta model update is only based on the current data. In contrast, most of the previous studies store the previous data in the memory for the meta model update. A comparison of the memory requirements among Algorithm 1 onLine mEta lEarning under Distribution Shifts (LEEDS) 1: Input: Dynamic stream S, pre-training distribution P 0 (T ), stepsizes α1 and α2, thresholds ℓ and τ . 2: Perform pre-training phase using MAML method on tasks drawn from P 0 (T ) 3: while stream S is ON do 4:Dt ←-S // receive current data from online data stream St, Qt 5:St, Qt ←-Dt // split data into support and query 6:if L(ϕt-1; St) ≤ ℓ (i.e., no switch) then 7: end if 17: end while different approaches is summarized in the right table in Fig. 1 . As will be shown later in the experiments, LEEDS significantly outperforms the related baselines without the need of storing any previous data. This encouraging result suggest that the community could also learn from careful explorations of simpler designs, besides emphasizing algorithmic complexities.ϕt = ϕt-1 -α1∇ ϕ t-1 L(ϕt-1; St) // 
theoretical results: 
 In the online meta-learning with distribution shifts, it is clear that the static comparator in Equation ( 3) is not sufficient to capture the non-stationarity, as one cannot expect to have a single meta-model for all task distributions. Hence, we consider a task-averaged regret (TAR) by following [34] EQUATION)where T is the number of tasks, K t is the number of steps within task t, and ϕ * t is the dynamic comparator for each task t. For simplicity, we denote f k t as the within-task loss function in step k of task t (evaluated on the query set). As shown in [34] , one cannot expect to achieve a TAR that decreases w.r.t. T because the dynamic comparators {ϕ * t } t can force a constant loss for each task t. However, the average is still not taken w.r.t. the total number of steps T t=1 K t , but only w.r.t. the number of tasks T . Therefore, the objective here is to achieve a TAR that is sublinear in K t . Note that the within-task loss functions {f t t } Kt k=1 are usually non-adversarial in many practical online meta-learning problems. For example, in few-shot online image classification problem, {f t t } Kt k=1 correspond to different evaluations of the same classification loss function on different query sets for the same task. In what follows, we can show that a constant TAR is achievable for the non-adversarial case even after taking the detection errors of task boundaries into consideration.Let the comparator ϕ * t be a minimizer of each of the loss functions f k t , k = 1, ..., K t . To formally characterize the non-adversariality of the within-task loss functions {f t t } Kt k=1 in online meta-learning, we make the following assumptions. , ϕ 2 , U k t (ϕ 1 ) -U k t (ϕ 2 ) ≤ ρ k t ϕ 1 -ϕ 2 .Assumption 4.1 characterizes the property of the dynamic comparator ϕ * t . It is clear that Assumption 4.1 will hold when there exists a task model ϕ that can perfectly achieve zero loss on all data points sampled from the data distribution for task t. For example, in over-parameterized regime, one can always train a model to perfectly predict all training data points with near-zero loss. Assumption 4.2 can be easily satisfied in online meta-learning [13] . For example, the one step gradient descent mapping, i.e., U k t (ϕ) = ϕ -α∇ f k t (ϕ), satisfies Assumption 4.2 when the function f k t is β-smooth and µ-strongly convex, and the stepsize α is chosen in (0, 2 β ). Define ρ = max t,k ρ k t . Assumption 4.3. Each function f k t is L-smooth. Note that we do not make any assumption on the convexity of the within-task loss functions f k t . For any step r in the online meta-learning process (where each task t includes K t steps), let P r be the current data distribution and ϕ r be the task model obtained after adaptation. To analyze the error probability of the detection mechanisms proposed in this work, we make the following assumption on the single-data loss function ℓ: Assumption 4.4. Let ℓ(•, ξ) be the loss on a data point ξ and 0 ≤ ℓ(•, ξ) ≤ M . We assume that there exist constants ℓ m ≤ ℓ p such that the following holds for any step r and s:(1) E ξ∼Pr ℓ(ϕ r , ξ) ≤ ℓ m ; (2) E ξ∼Pr ℓ(ϕ s , ξ) ≥ ℓ p if P r ̸ = P s .Assumption 4.4 characterizes the comparison of the expected loss w.r.t. a certain data distribution between 1) the model adapted on this distribution and 2) the model adapted on another distribution. This essentially means, in expectation, the loss after adaptation is less than the loss of another task model, which is crucial for a threshold-based detection scheme to be applicable.By updating the meta-model using OGD [32] K t be the total number of online rounds, and S = c log R be the number of data points used for adaptation at each step, where c is some positive constant. Then the expected TAR is bounded asE[Ravg] ≤ O σ 2 * + log T T 1 -ρ 2 + R - c(ℓp -ℓm ) 2 2M 2 -2, where the expectation is taken over the task-boundary detection uncertainty.σ 2 * = 1 T T t=1 ϕ * t -ϕ * 2 and ϕ * = 1 T T t=1 ϕ *t denote the variance and the mean of the comparators {ϕ * t } T t=1 , respectively. In particular, a constant expected TAR can be achieved by selecting c > 4M 2 (ℓp-ℓm) 2 . Intuitively, the first term in the upper bound in Theorem 4.5 captures the TAR for online metalearning with known task boundaries, whereas the second term characterizes the impact of the task-boundary detection uncertainty. As shown in Theorem 4.5, when the tasks become more similar, the first term will decrease because the variance σ 2 * is smaller, whereas the second term can increase because the constants ℓ p and ℓ m become closer (i.e., it is harder to detect task switches if tasks are more similar). Therefore, Theorem 4.5 captures a trade-off between the impact of task similarity on the performance of standard online meta-learning and the performance under the task boundary detection uncertainty. In practice, the optimal actions ϕ * t are usually not available for the meta updates. Thus, in our algorithm we use the alternative MAML-like updates which has been shown to be effective for learning meta parameters. As demonstrated in the different experiments in the next section, such updates can indeed serve as a good practical alternative. 
experiments: 
 Experimental setup. We investigate the performance of LEEDS on three standard online metalearning benchmarks, Omniglot-MNIST-FashionMNIST, Tiered-ImageNet and Synbols, compared to multiple related baseline algorithms. Specifically, we pre-train the meta model in one domain and then deploy it in a dynamic environment where tasks can be drawn from new domains. We evaluate all the algorithms using the average of test losses obtained throughout the entire online learning stage. To investigate the impact of the non-stationary level on the learning performance, we further consider two different cases of the environment non-stationarity: A moderately stationary case where the probability of not switching to a new task is set to p = 0.9, and a low stationary case where p = 0.75. We do not consider the cases where p is very small, as an algorithm that just assumes task switches at each round should perform well in such cases. We compare algorithms over 10000 episodes unless otherwise stated. See more details about datasets and baselines in Appendix C. More comprehensive results and training curves of different methods are also provided in Appendix B. For all the experiments, whenever a new task needs to be revealed, it will be drawn from either the pre-training domain with probability 0.5, or from one of the OOD domains with probability 0.5. For Tiered-ImageNet, because only ood2 is trully OOD w.r.t. the pre-training task distribution, we increase the sampling probability of ood2 to 0.5 which is consistent to the protocol 50% -50% for IND and OOD tasks in all our experiments. More details about the experimental setup including the neural network architectures and the hyperparameter search are deferred to Appendix D. The online evaluations of the compared methods are shown in Table 1 for non-stationary levels p = 0.9 and p = 0.75. For each setting we report separately the online accuracies on pre-training domain and on the other two OOD domains, to show how our method keeps improving on the OOD domains while also remembering the pretarining tasks. Clearly, our method LEEDS achieves superior performance compared to all other baseline algorithms in both settings. More specifically, on the IND domain all methods pre-trained using MAML perform similarly, but are outperformed by LEEDS and CMAML++ which can detect task boundaries. However, on the OOD domains our algorithm significantly outperforms all other baselines, including CMAML++. This is due to the key OOD adaptation module that allows LEEDS to dynamically adapt the meta model based on the task distribution. Interestingly, comparing the performance for MAML and ANIL provides some insights on the limitations of re-using pre-trained representations in non-stationary environments. In fact, the ANIL baseline, which does not adapt its inner representations, performs poorly compared to MAML on the OOD domains, but achieves similar results on the pre-training domain. Also, the results highlight some limitations of the recently introduced FOML [10] method, which achieves lower performance than other competitive baselines. This is because FOML requires the tasks to be not mutually exclusive, which may not hold for the standard few-shot benchmarks considered in our experiments. We report the online accuracies on all domains and on OOD domains for these two benchmarks in Table 3 . Because the distribution of the pre- training tasks is similar to the OOD ones for the Tiered-ImageNet benchmark, methods such as MAML can perform reasonably well. In fact, in the lower non-stationary case (p = 0.75), MAML is able to outperform the more complex CMAML++ baseline. However, our algorithm still achieves the best performance under both non-stationary levels and in both benchmarks. Note that in the larger TI dataset case, the FOML algorithm, which stores all previously seen tasks, runs out of memory after around 6500 online episodes. Again because of similarity between OOD and IND tasks in the TI benchmark, static representations learned by ANIL are useful for all domains.Task boundaries detection. The table in the right of Figure 2 provides the precision and recall scores of the task switch detection schemes for our method and CMAML++. Our detection scheme outperforms that of CMAML++ in all metrics. This is because, the detection scheme in CMAML++ is based on comparing successive losses, which could lead to over detection of task boundaries, especially when the task loss is too high at the first time the task is revealed to the online algorithm.Importance of domain adaptation module. We investigate the importance of the distribution shift detection module that allows our algorithm LEEDS to update the meta model differently for indistribution and out-of-distribution tasks. Fig. 2 shows the performance of our algorithm with and without the distribution shift detection module. The performance of the algorithm significantly improves (∼ 4.3% improvement) with this module. This shows that such a simple mechanism can effectively boost the online learning performance by allowing the agent to learn more from OOD data while also remembering pre-training knowledge.Sensitivity to frequency of task switches. Fig. 2 shows the performance of our algorithm for different values of the probability p of task switches. The performance increases with p, which shows that our algorithm LEEDS can successfully re-use previous task knowledge to increase performance. 
conclusions: 
 In this work, we study the online meta-learning problem in non-stationary environments without knowing the task boundaries.  
 
 Appendix: Figures 3 and 4 illustrate the sensitivity of our algorithm LEEDS with respect to the thresholds ℓ and τ and the temperature parameter δ in the energy-based detection module. As depicted in Figure 3 , when the threshold ℓ is too small, the algorithm tends to over detect task switches (as indicated by low Recall for ℓ = 0. ineffective reuse of task knowledge. On the other hand when ℓ is too large, the high misdetection rate (e.g., indicated by low Precision for ℓ = 5) results in the algorithm mostly fine-tuning the online task model ϕ t with the current task support data. As expected, this results in a failure mode (the algorithm diverges) due to the adversariality of different tasks. We find that values of ℓ in the rage [1.5, 2.3] yield the best performance of our algorithm.Figure 4 (a) shows that larger values of τ , which collapse to updating the meta-model at each step (even for pretraining task distribution), does not substantially improve the performance. This demonstrates the advantage of the distinct meta-update scheme proposed for in-and out-of-distribution tasks, which avoids unnecessary frequent meta-updates for the pretraining tasks and thus allows a more judicious usage of computational budget. Lower values of τ (e.g. τ = 15) tend to detect all task distributions as the pertaining one, and thus corresponds to eliminating the domain adaptation component of our algorithm. We also find that simply setting the temperature δ = 1 in the energy expression yields the best performance, and large values of δ also eliminates the effectiveness of the energy-based detection module (Figure 4 (b)). This is in fact in accordance to the finding in [12] , which also suggests setting δ = 1.ℓ Precision Recall ℓ = 0.5 99.9 68.0 ℓ = 1.5 99.9 98.4 ℓ = 1.9 99.9 99.3 ℓ = 2.3 99.9 99.7 ℓ = 5 38.13 99.9 performance of the methods that do not adapt meta-parameters during online learning phase (such as MAML and ANIL) drops drastically when OOD tasks are far away from the pre-training ones (as shown in Table 1 for Omniglot-MNIST-FashionMNIST). For settings in which OOD tasks are close to the pre-training ones (such as in the Tiered-ImageNet dataset), MAML can perform similarly to CMAML++.The superior performance of LEEDS even for the pre-training domain particularly shows that the re-use of task knowledge is beneficial for online meta-learning, as opposed to the usual practice of "resetting" to meta-parameters at each step.By comparing the two plots in Figure 10 , it can be seen that the advantage of our domain adaptation module is more significant when the OOD domains are far away from the pre-training one, as is the case for the FashionMNIST OOD domain compared to the Omniglot pre-training domain.We study dynamic online meta-learning on the following benchmarks:Omniglot-MNIST-FashionMNIST dataset. For this dataset, we consider 10-ways 5-shots classification tasks. We pre-train the meta model on a subset of the Omniglot dataset and then deploy it in the online learning environment where tasks are sampled from either the full Omniglot dataset, or from one of the OOD datasets, i.e., the MNIST or FashionMNIST datasets.Tiered-ImageNet dataset. We consider 5-ways 5-shots classification tasks for this dataset. Following Synbols dataset. We consider 4-ways 4-shots classification tasks in this dataset. The meta model is pre-trained on characters from 3 different alphabets and deployed on characters from a new alphabet (ood1). We also consider font classification tasks as additional OOD tasks (ood2). We compare our algorithm with the following baseline methods for online meta-learning.(1) C-MAML [11] and C-MAML++: the continual MAML approach (C-MAML) pre-trains the meta model using MAML and employs an online learning strategy based on task boundaries detection. Since C-MAML does not evaluate the task models on separate query sets, for a fair comparison we adapt it to do so and call the resulting algorithm C-MAML++. (2) FOML [10]: the fully online meta-learning method updates online parameters using the latest online data and maintains a concurrent meta-training process to guide the online updates regularized by the meta model.(3) MAML [3] and ANIL [18] : the MAML baseline consists of an offline pre-training phase and an online deployment phase. During offline pre-training the method learns a common meta-initialization that will be used for all tasks, and the meta-initialization will never be updated at the online stage. The task model is adapted from the meta-initialization using the support set and evaluated on the query set. ANIL is similar to MAML but with partial parameter adaption, i.e., only the last layer is adapted for each task.(4) MetaBGD [11] and BGD [48] : the baseline MetaBGD combines MAML and the Bayesian gradient descent method during online learning.(5) MetaOGD [32] : the meta online gradient descent method simply updates the meta-model at each step using a MAML-like meta-objective evaluated on the current task data. In all our experiments, we consider classification tasks. The cross-entropy loss between predictions and true labels is used to train all models. We use the same convolutional neural network (CNN) architectures widely adopted in few-shot learning literature [3, 11, 13] , which include four convolutional blocks followed by a linear classification layer. Each convolutional block is a stack of one 3 × 3 convolution layer followed by BatchNormalization, ReLU, and 2 × 2 MaxPooling layers. For the Omniglot-MNIST-FashionMNIST benchmark, we use 64 filters in each convolutional layer and downsample the gray-scale images to 28 × 28 spacial resolution so as to have 64-dimensional feature vectors before classification. For Tiered-ImageNet and Synbols datasets, the inputs are respectively 3 × 64 × 64 and 3 × 32 × 32 RGB images, resulting respectively in 1024-and 256-dimensional feature vectors for 64 filters in each convolution layer. The implementation of FOML [10] method is not released yet, and hence we compare with our own implementation of their algorithm. For all other baselines, we used their publicly available implementations. Codes for our algorithm LEEDS and all other baselines are provided in the supplementary materials of our submission. All codes are tested with Python 3.6 and Pytorch 1.2.For example to run our algorithm LEEDS with the best hyperparameters that we obtained for the Omniglot-MNIST-FashionMNIST dataset under p = 0.9, one can run the following command: python main . py --a l g o l e e d s --u s e _ b e s t 1The experiment setting (e.g., the dataset to use) can be changed in configurations.yaml file. We run all methods on a single NVIDIA Tesla P100 GPU. All compared algorithms except FOML were able to run on 16GB GPU memory. FOML requires at least 32GB to reach 12000 online episodes for the Tiered-ImageNet dataset.For the energy threshold τ , we follow the strategy in Liu et al. (2020), i.e., we set the threshold τ using the pre-training tasks. More specifically, we set τ so that 95% of the pre-training inputs are correctly detected as pre-training data. In standard few-shot learning experimental setups, the true labeling for each individual task is usually randomly chosen. When there is a task switch, the task specific model learnt from the previous task generally does not fit the new task anymore, where the learning performance could be similar to that of a random model. Thus motivated, we find that a good heuristic to choose a starting value for the threshold ℓ is to use the loss value evaluated on a random model. For example, for 10-ways classification tasks that value would be ℓ r = -log(1/10) = 2.3.Recall the task-averaged regret:R avg = 1 T T t=1 Kt k=1 f k t ϕ k t - Kt k=1 f k t (ϕ * t ) .We consider the setting where at each round the agent can perform some task-specific adaptation before evaluation on the loss function f k t [13] . Let U k t be the mapping that defines the adaptation procedure at each round. For instance, a popular choice of the mapping function U k t is the one step gradient descent mapping:U k t (ϕ) = ϕ -α∇ f k t (ϕ), where α is a learning rate and f k t is an approximation of the loss function f k t , e.g., computed on a small support set from task t. Denote fr (ϕ r-1 ) = 1 |Sr| ξ∈Sr ℓ(ϕ r-1 , ξ) := fr,r-1 as the adaptation loss at round r, where ℓ(•, ξ) is a classification loss on data point ξ. We first provide an upper bound on the detection error.The total probability of error of the threshold-based detection scheme at round r is given by: P error = P (P r ̸ = P r-1 ) P fr,r-1 < τ P r ̸ = P r-1 + P (P r = P r-1 ) P fr,r-1 > τ P r = P r-1 (6) where the first term characterizes the probability of miss detection of the task boundary, and the second term is the probability of false alarm when the underlying task does not change.Based on Assumption 4.4, for a data distribution P r and support set S r drawn i.i.d. from P r , the Hoeffding inequality yields: . Thus, we obtain P fr,r-1 > τ P r = P r-1 ≤ expEQUATION)Combining Equations ( 6), ( 7) and ( 8), and using the fact that P (P r ̸ = P r-1 ) = 1-P (P r = P r-1 ) can yield the following upper bound on the probability of error when the threshold is set to τ = ℓm+ℓp 2:EQUATIONBased on Assumption 4.3, we have for any ϕ:f k t (ϕ k t ) ≤ f k t (ϕ) + ∇f k t (ϕ), ϕ k t -ϕ + L 2 ϕ k t -ϕ 2 .Therefore, by setting ϕ to be the comparator ϕ * t and using Assumption 4.1, we obtain:f k t (ϕ k t ) -f k t (ϕ * t ) ≤ L 2 ϕ k t -ϕ * t 2 .Thus, summing over k = 1, ..., K t yields Kt k=1EQUATION)We next bound the term Kt k=1 ϕ k t -ϕ * t 2 from above. It follows thatEQUATIONwhere the first inequality uses Assumption 4.2. Therefore, combining Equations ( 10) and (11) gives that Kt k=1EQUATION)Hence, summing Equation ( 12) over t = 1, ..., T yieldsT t=1 Kt k=1 f k t ϕ k t - Kt k=1 f k t (ϕ * t ) ≤ L 2(1 -ρ 2 ) T t=1 ϕ 0 t -ϕ * t 2 .The task-averaged regret is therefore upper bounded as followsEQUATION.Next, we show that the term 1 T T t=1 ϕ 0 t -ϕ * t 2 converges as T → ∞. We have,EQUATION)where ϕ * = 1 T T t=1 ϕ * t is the mean of the dynamic comparators. Note that ϕ * is the minimizer of the summation T t=1 ϕ * t -ϕ * 2 . Thus, if we use an algorithm such as OGD [32] to update the initialization ϕ 0 t with loss ϕ 0 t -ϕ * t 2 then summation in the first term at the right hand side of Equation ( 14) corresponds to the regret of OGD on a stream of strongly-convex functions, which is well-known to be O (log T ). The second term 1 T T t=1 ϕ * t -ϕ * 2 = σ 2 * corresponds to the variance of the dynamic comparators. Hence, combining Equations ( 13) and ( 14) we obtainEQUATION)Using Equation ( 9) for R = (ℓp-ℓm) 2 ensures a constant expected task-averaged regret.First Conference on Parsimony and Learning (CPAL 2024). 


Decision: (This is an invited paper, so only one meta-review is provided)

This work proposed a new, task-agnostic online meta-learning algorithm for dynamic environments. It addresses key challenges in the field by allowing for the algorithm to operate without fixed task distributions or known task boundaries. The introduction of mechanisms to detect task switches and distribution shifts based on empirical observations is particularly commendable. These mechanisms are crucial for the algorithm's adaptability, enabling it to maintain performance on in-distribution tasks while swiftly adapting to new, out-of-distribution tasks. The avoidance of data storage from previous tasks and the demonstration of sublinear task-averaged regret are also impressive features that suggest significant improvements over existing approaches. Empirical validation across multiple benchmarks substantiates the algorithm's efficacy. Therefore, the paper appears to be a valuable contribution and is recommended for acceptance.