Online Constrained Meta-Learning: Provable Guarantees for Generalization
Authors: Siyuan Xu
Minghui Zhu
Venue: NeurIPS 2023 spotlight (2023)
Keywords: meta-learning; generalization

Abstract: Meta-learning has attracted attention due to its strong ability to learn experiences from known tasks, which can speed up and enhance the learning process for new tasks. However, most existing meta-learning approaches only can learn from tasks without any constraint. This paper proposes an online constrained meta-learning framework, which continuously learns meta-knowledge from sequential learning tasks, and the learning tasks are subject to hard constraints. Beyond existing meta-learning analyses, we provide the upper bounds of optimality gaps and constraint violations produced by the proposed framework, which considers the dynamic regret of online learning, as well as the generalization ability of the task-specific models. Moreover, we provide a practical algorithm for the framework, and validate its superior effectiveness through experiments conducted on meta-imitation learning and few-shot image classification.

Online Constrained Meta-Learning: Provable Guarantees for Generalization
Siyuan Xu Minghui Zhu
School of Electrical Engineering and Computer Science
The Pennsylvania State University University Park, PA 16801 (spx5032, muz16) @ psu.edu
Abstract
Meta-learning has attracted attention due to its strong ability to learn experiences from known tasks, which can speed up and enhance the learning process for new tasks. However, most existing meta-learning approaches only can learn from tasks without any constraint. This paper proposes an online constrained meta- learning framework, which continuously learns meta-knowledge from sequential learning tasks, and the learning tasks are subject to hard constraints. Beyond existing meta-learning analyses, we provide the upper bounds optimality gaps and constraint violations of the deployed task-specific models produced by the proposed framework. These metrics consider both the dynamic regret of online learning and the generalization ability of the task-specific models to unseen data. Moreover, we provide a practical algorithm for the framework and validate its superior effectiveness through experiments conducted on meta-imitation learning and few-shot image classification.
Introduction
In the setting of learning from multiple tasks, shared prior is extracted from commonalities of existing tasks, resulting in improved learning efficiency and prediction accuracy for task-specific models. Conventional approaches includes multi-task learning [I]], lifelong learning [46] 45 34).
These approaches extract the prior by vanilla learning approaches on the tasks and do not explicitly involve the task-specific learning in the prior extraction, as illustrated by 28 In contrast, meta-
learning or learning- to-learn [1] 23 47 learns a meta prior, usually a meta parameter, by evaluating and optimizing the objeetvve,, which defined by the performance of the task-specific model adapted from the prior. Meta- Meta-learning has been extended to accelerate reinforcement learning [3] 34 where the tasks are modeled by Markov decision processes.
Online meta-learning considers that the meta parameter is learned from tasks that are sequentially revealed. Papers 24 [6] shown to be no-regret with respect to the static comparator, i.e., the
gap between the aggregate performance of the meta parameter sequence and that of any fixed meta parameter is sublinear in the number of revealed tasks. The online-MAML 244 and the MOML M adopt one-step gradient descent to adapt the task-specific parameter, and paper [66 adapts it by the ridge regression. A direct evaluation of meaa-nen the performance of the sisk-specific model adapted from the meta parameter on each individual task. The methods in 4 34 consider dynamic regret [56] 4. which compares the task-specific parameter adapted from the meta parameter with the optimal counterpart for each task. The dynamic regrets of all the algorithms are shown to be bounded when there are sufficiently many tasks.
In many applications of meta-learning, such as few-shot learning in computer vision 38 and robotics 43
39
task-specific model is expected to be quickly adapted by using small amount of
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

training data of a new task and generalize to the unseen data of the task. The generalization ability
of the task specciii adaptation has been considered in [3] 20 21 BI]. Most of them consider the task-specific model to he adapted using small number of samples from the data distribution, and the generalization error is quantified by the optimality gap between the produced task-specific model and the task-specific model adapted using the best meta- perta-prrmeter. In contrast, in this paper, we explore a generalization error metric, which is defined as the optimality gap between the produced task-specific model and the optimal task-specific model, based the entire data distribution. By directly quantifying the performance of the task-specific model on the entire data (including unseen data), this metric identifies the improvement in the model's generalizability for each specifie learning task when the meta- meta-paranan parameter is employed. Despite its significance, this generalization metric is often overlooked in most meta-learning analyses. Generalization metries that are similar to ours are evaluated in 15 18 and discussed in [20].
Typically, meta-learning handles learning tasks as unconstrained optimization problems. Many real-world applications such as robot learning in [4 54 29 42 nevertheless, are subject to safety constraints that should be rarely violated. For this case, constrained meta-learning aims to learn meta-prior for constrained learning tasks, which are formulated as constrained optimization problems. As result, in constrained meta-learning, besides the generalization with respect to the objective risk, the generalization with respect to constraint violation is also required to be considered during the task-specifie adaptation. More specifically, in the constrained learning task, each constraint is also defined by the expectation over a data distribution, and only a small amount of training data sampled from the distribution is observable during the task-specific adaptation. Therefore, the adaptation can only guarantee the constraint satisfaction over the training data, while the constraint violation over the whole data distribution is required to be quantified.
Main contribution. In this paper, we develop the first approach for the online constrained meta- learning problem. In particular, we consider sequential task setting of constrained learning tasks. At each round, a learning task with hard constraints is revealed and is required to be solved, and only a small number of data for the revealed task is provided. To address the problem, we use the Follow-the- Perturbed-Leadeee revealed tasks and apply the meta-regularizatioon to solve the new task. The overall contributions are summarized as follows. (i) We apply constrained optimization with biased meta-regularie meta-reeularizztion to adapt the task-specific parameter by using small amount of data. Then, we optimize the meta- objective function, which is defined by the performance of the task-specific parameter on validation data. (ii) To handle the non-convex meta-objective function, we use the Follow-the-Perturberr Perturbed- Leader (FTPL) to update the meta-regularization from all the available tasks for the new task. (iii) We theoretically analyze and prove the upper bounds that (a) quantify both the optimality gaps on the objective functions and the constraint violations of task-specific models; (b) quantify the dynamic regrets where the comparator is dynamic and always optimal for each task; (c) quantify the generalization errors of task task-specific models to the unseen data, where only small number of training data are given in each task. The upper bounds show that the optimality gap between the and that learned by our method decreases with a rate of O11 (T)/T)). (iv) We develop a practical algorithm for the online constrained meta- meta-learning that can be used effectively on large-scal scale problems, and empirically verify the efficacy of the proposed algorithm by conducting experiments on meta-imitation learning and fhw-shot robust image classification.
(FTPL) approach to learn a metu-regularizztion at each round from the
optimal meta-parament
Table D compares the challenges of interests between this paper and previous works 44 15 24 II (8). In particular, we consider the hard constraints in each learning task, the dynamic regret in the online meta-learning problem, and the generalization ability of the task- specific models to unseen data, si- multaneously. Even if the constraints are removed, this paper provides a more general theoretical analysis than most papers, as paper [15] quantifies the empirical loss over known training data, and does not consider the generalization, and papers [2 consider a static regret.
Table 1: Challenges of interests
This paper
15
24
Constraint Online learning
X
Dynamic regret Generalization
V
N/A
X
Related works. Optimization-Dase based meta-learning algorithms usually learn an optimization parameter as the meta prior, and each algorithm consists of a meta-algorithm, which learns the

---

meta parameter, and an inner-task or within-tas algorithm, which adapts to task-specific model based on the meta parameter. Based on the type of the within-task approach, the methods can be categorized into meta-initializatio
and meta-regularization approaches 17 L5 47 32 In meta-initialization approaches, the within-task algorithm uses the meta parameter as the initial point and takes few optimization steps to minimize the empirical risk of the new task. For example, the MAML [23] algorithm takes one-step gradient descent as the within-task algorithm. In meta-regularriztionn approaches, the within-task algorithm completely solves an optimization problem, where the meta parameter serves as the bias of the regularization term for the empirical risk. In our constrained meta meta-leerning problem, the task-specific parameter should satisfy its given constraints. In the meta- inttiiiiiiaiiiiionn approaches, as the within-task algorithm only takes a few optimization steps, even if we do optimization reduce the constraint violation, the solution is far from feasible. On the other hand, the meta-regularization approaches fully solve the within-task. To prioritize constraint satisfaction, we combine the meta-regularization approach with hard constraints as the within-task algorithm for constrained meta-learning.
approaches [11 23 24
35
33
Notations. Denote the l2 norm of vectors and the spectral norm (2-norm) of matrices by I. I|- Consider multiple data distributions D = (Do: Di...., Pn J and multiple training datasets Der (DB Dír ..... Drr We use Dtr D; to represent that each data z in the dataset D.r is i.i.d sampled from the distribution Di, and D ~ 'D to represent D ~ D, for all S i S m. We use
[D]'] to denote the number of data in the dataset DJ", A notation checklist is attached in Appendix A
2 Problem Formulation
2.1 Constrained learning tasks and the sequential setting
At round f, an agent aims to solve a constrained learning task Tr which is formulated as the following constrained optimization problem:
0-- argmin EzwDo., [f)(0,=)] s.t. EENDD, [e,(0, 2)] S Ci,t, i= 1,...,,, m,
(1)
age
where each data point is denoted by = = y) E Z with æ E X' C Rdd being the input and y E y C R2d, being its corresponding output. The loss function to : 12 x 2 + R is the performance metric of model parameterized by 0 E ② C Id and the constraint functions L, RR x Z - R. 1 I,..., m evaluate the constraint metric of the model. Each performance or constraint metric the data distribution Di,,, which is a joint distribution over input-output pairs 2 = (z. v). The optimal solution of Problem (T) is denoted as 67, and the feasible set of Problem (I) is denoted as K,, _ {0 E @ REDDD. [4, =)] S Ct,,, Vi = 1.... m). The constrained learning task Te is characterized by its data distributions D, = (Do.:: Di,,. Din..} and constraint limits foi,t--.. Cm.t). J. In general, the data distributions D, are unknown the agent. Instead, the training datasets D.- = (Di. Di,,.... Dir,e} are sampled i.d.d from D; and available to the agent.
l; is computed
Consider that set of constrained learning tasks are revealed sequentially. i.e., task T, is revealed at round l. each round I, the agent updates a model once D.r is obtained. The updated model is deployed and works on Tr, i.e., predicting the outputs y of all requested inputs In the next round, the procedure repeats.
Since the data distributions Dr are unknown, the agent cannot completely solve Problem ! and obtain 02. A common solution to replace the data distribution D., Problem (T) by the sampled dataset DIr, and solving the problem for each task TT. However, when the sample number in D
is small, separately solving T. with DI leads to limited performance. Similar to 44, [5), in this paper, the learning algorithm is expected to improve the performance of the solution for task Te by exploiting the correlation between the task T, and all previous tasks (T,,.... TT
2.2 Metrics of a learning algorithm
Consider learning algorithm produces a parameter sequence 10,,..., ,r} for the task se- quence {Ti, ... }r.. At round i, the optimality gap Ro., of 0, is defined as (o.) = max { (EewDo. (f,(0,, - to (o :).. The violation for the i-th constraint denoted by R,, is defined as: (f)) = max { (E.~D., [e, =)] - c,e,, 0} i = I...., m. The task-averaged opti- mality gap (TAOG) denoted by Ro.11.7 and the task-averaged constraint violation (TACV) denoted
3

---

by RI(1 of the algorithm after T rounds are defined as
T
T
Ro. Σ Ro.,
Ri,( i i= i=1, -.....,7 m. Repp:1 T Σ
(2)
Under the sequential task setting, the goal of learning algorithm is to minimize the TAOG and the TACV of the parameter sequence (01,..- 0r The definitions of the TAOG and the TACV consider both the generalization ability of 0, to the unseen data of each revealed task T;. and a dynamic notion of the optimality regret. First, the optimality gap Ro,: and the constraint violation Ri, are defined by the expectations over the inaccessible data distribution Di.,, instead of the empirical risk over the given dataset D that is used in online meta-learning analysis 4 35). Thus, the TAOG and the TACV can be used to quantify the generalization errors. It is more challenging to minimize them, as 8, is expected to generalize the unseen data in D.,, while only the training datasets D are given, and their size could be small. Second, unlike the fixed comparator used in the FTML algorithm (4]. the comparator 0r dynamic and always optimal for each task Tz. As pointed out in 34 56 one cannot achieve the dynamic regret sublinear in T for either online learning online meta-learning.
2.3 Task dissimilarity
As mentioned in Section 2.1 We expect that the performance produced by the learning algorithm, i.e., the TAOG and the TACV, are improved the similarity and correlation among the task sequence (Ti, - are higher. Similar to 4 15 34), we define the dissimilarity between tasks by the distance between the optimal parameters of tasks. Given the optimal task-specific parameters (0 } for the task sequence (Ti, ,T), the average distance between the parameter é
and the optimal task task-specific parameters is defined by Dist(Ø, TI.T) - - ET 2 11 -112. The dissimilarity of (Ti,.... Tr } is defined as S (Ti:) & ming Dist(Ø, Ti:r). When the disclosure of (Ti,... T is stationary, i.e., the task Tr at each is sampled from the same probability distribution P(T), the task dissimilarity of the task distribution p(7) is defined as (p(T)) -
V /mnn (T-p( - -
3 Online Constrained Meta-Learning Algorithm
In this section, to handle the sequential constrained learning tasks formulated Section 2.1 we propose the online constrained meta veea-learning framework, which contains the meta- pera-parrmettr update in Section 3.2 and the spec-fpec adaptation from the meta-paramee eetta-arameter in Section 3.3
3.1 Online constrained meta-learning setting.
Online constrained meta-learning aims to handle the problem given in Section 2.1 numbers of the datasets for each task, i.e., [Dig]e are limited and the agent is required to quickly adapt new task once the task is revealed. At round t, the sasc-fpecific parameter 9₂ is updated by a within-tash task algorithm, and the meta parameter di is updated by a meta-algorithm. In particular, in the first step, the agent adapts the meta parameter Φe the task-specific parameter 0, for task Tí, by using a within-task algorithm Alg with the training datasets D = (Dir, constraint limits (cI. }. }. Next, the agent uses all available tasks T Te to update the meta parameter to Φ++1 by meta-algorithm, which will be used in the task besk-specific adaptation for the next task T++1 at round / + 1. Our task-specific adaptation algorithm Alg and meta-algorithm are discussed in the following.
where the sample
Dir,, and the
3.2 Task-specific adaptation.
At round t, the task-specific parameter 0; is adapted from the meta parameter ÓG to task Tr by the within-task algorithm Alg. In the meta-initialization approaches [41 23 24], the within-task algo- rithm Alg only takes a few optimization steps toward reducing the empirical risk and the constraint violation, and thus the solution is far from being feasible for Problem ( To prioritize constraint satisfaction, we employ the meta-regularization approach with hard constraints. In particular, the

---

task-specific adaptation from the meta- parameter di is defined by constrained optimization with the b.-bissed regularization, i.e. 02 Alg(A, Dir)) ) is defined by
argmin OEE
(0(0,2) 2) RED
Σ
> 110 Q.11 s.t.
Σ RED
((0, - Ci,1, i 1, m, (3)
D
2
D
where the regularization weight > O. By the algorithm (3, the task-specific parameter 0, satisfies the constraints over the training datasets D The objective function includes the empirical loss defined on the training dataset Di, and is regularized by a biased term 2 2 dx 1|2 [47 15], which penalizes the deviation from the meta parameter Φ2. The feasible set of the optimization problem in
m In the following sections, we consider that, the numbers of the data sampling from Do,,- i.e., |D are the same for all t, and is denoted as [D the numbers of the data sampling from Di,, i.e., [ are the same for each i and and is denoted as [D4]
(3 is denoted as XC," A { { e |P! EeEDY (((0,2) 2) I Ci,t, Vi = 1, 1,...,,,,
3.3 Meta- parameter update.
After the model parameterized by 0g is deployed, the agent obtains the dataset Di (Digl m,t) by sampling from the data distribution D, (Do,,. .mm.)) The performance evaluation of the model with parameter is defined as L (0, D [D5.7 ExeDge (o(
Here, we consider that [Dag'] is the same for all and is denoted as |Dyal].
In online meta-learning, each round the meta-pant vetaa-arrmmeter is updated by using online learning algorithm to the meta-objective functions on all revealed tasks (Ti, T.). In our meta-learning problem, as the agent has collected the validation data {Diai, ,... Drraj,, ). we can evaluate the performance of the task-specific parameter 0, for each task, then the meta-objective function at round t is defined as Et= C (Alg(),, o, Df Dyg!), where Alg is defined in 33)
24 solve online meta- meta-learning and update the meta--arameterr by using the Follow-the- Leader (FTL) 26 to their meta-objective functions. However, the FTL requires the objective function to be strongly convex, and cannot be used in our problem, where the meta-objective function is non-convex. Therefore, in this paper, we use the the problem, which is the first time that the FTPL applied to online meta-learning. At round 4, the FTPL optimizes the meta-objective function with perturbed terms over all revealed tasks to obtain the meta parameter cb+1 for task T++1- In particular, at round I, the meta parameter Φ obtained by solving the following optimization problem:
Papers
(FTPL) (50 to solve
Ø++1 argmin dEe
Σ Lual (Alg(A, o, D'), Duyl) of Φb P=1
where E Rd is the random perturbed vector and its components (or,) is i.i.d sampled from
the exponential distribution with parameter 17 > each As Alg(A, o. D included in (4) is the optimal solution of the constrained optimization in (3), Problem (4) is a constrained bilevel optimization problem 55
Algorithm 1 Online Constrained Meta- DettnnL Framework
Require: Regularization weight > O; Initial meta parameter Φ1; Perturbed parameter 7).
1: for f 1,
,T do
2: Sample the training datasets D." from the distributions D, for task Te
3: Update and deploy the task-specific parameter 0, Alg(), di, D(r) defined in 33 for task Te
4: Sample the evaluation dataset D from the distributions Do,
5: Generate the random perturbed vector o, E IRd by i.i.d sampling: {ors)]=1 ~ Exp(n)
6: Update the meta parameter Φi+1 by solving (4)
7: end for
8: Return ( 3r) for tasks {T,,'. ... ,T)T)
5

---

3,4 Algorithm statement.
The online constrained meta-leaming algorithm is formally stated in Algorithm Note that line is deterministic convex optimization problem, which has been widely studied and solved by [[0] The optimization problem (4) in line 6 a deterministic constrained bilevel optimization problem, which can be solved by the algorithm in [55] The implementation details are included in our proposed practical algorithm (Algorithm
Appendix Bp.
Theoretical Results
In this section, we derive the upper bounds of the TAOG and the TACV produced by Algorithm D which characterize the regrets of the generalization errors of the models deployed for the sequential
tasks. First, we study the generalization error bound produced by our within-task algorithm (3) for single constrained learning task (Section [.T).. Next, we show the upper bounds of the TAOG and
the TACV when the meta-parameter can be arbitrarily selected (Section 4.1). Finally, we obtain the theoretical bounds the TAOG and the TACV, when the meta-parameter is not arbitrarily selected bu produced by Algorithm D
(Section 4.2)
Before the result statements, we introduce some definitions and the required assumptions about the constraint qualifications for the optimization problems in (I and (3). The constraint qualification assumptions are usually used in constraint optimization analyses 77
We consider an optimization problem with inequality constraints: min, g(x) s.t. 1x(2)) S 0, i I A [1, and denote it as (P). Denote the feasible set of (P) as K. {o h((x) S O, Vi 1) and [(x) _ {i E I h₂(2)) = 0} for æ E K.
Definition The Linear Independence Constraint Qualifications (LICQ) holds for (P), if vectors (x) i E T(x)) are linearly independent for any E K.
Definition 2. Slater's condition (SC) holds for (P) with the margin C > 0, if there exists & such that (x) - C < 0, Vi E
Assumption (Constraint qualifications). (i) There exists a compact set with diameter B > 0 such that the following properties hold for each t: for the given data distribution Dr, the feasible set Kr of the optimization problem in ①1 is included in the compact set; with probability 1, for D sampled from Dr, the feasible set Krr of the oplimization problem in (3) is included in the compact set.
(ii) There exists C >> such that the following properties hold: for the given data distribution De, the SC holds for the optimization problem in ① with the margin C; with probability 1. for D. sampled from Dr, the SC holds for the optimization problem in (3) with the margin C.
(ili) For the given data distribution D,, the LICQ holds for the optimization problem in (..
Remark 1. sufficient condition for part (i) of Assumption iis that θ is compact set.
We also require the following assumptions on the loss function and the constraint functions, which are standard in the analysis meta-learning problems [4] 24 20).
Assumption 2 (Function properties). (i) For any E Z, the loss function fo(, 2) and the constraint
functions & (..=).... (m((,2) are twice continuously differentiable. (ūi) For any z E Z, lo(,, is Lo LipLiipchitz, i.e., [[o(w, 2) (o(u,z) < Tollw: - w|] for any w, E e. (iii) For any E 2, fo(;,)) fanaaararraaaaaaaaaaaa
p- p-smooth, ie., [V
V,, (((,u)) =]] S -||w ull for any w, u E @. (iv) For any E and
1 < i < m, E((,2) 2) is Lipsschi, i.e., [[C[[,,2) L( 2)ll < Lellw w|l for any w,u O. (v) For any z E Z and 0 < S m, (z(,)) is convex. (vi) For any t E (1.... T}. 2 E Z, w G, and 1 < < ((w, 2) Ci bounded by M.
4.1 Generalization of constrained learning with biased regularization
We begin with the generalization error bound on single constrained learning task Te, which is produced by the within-task algorithm (3) with an arbitrarily given meta-paraman parameter é, As stated in (3) the algorithm replaces all the expectations in (T) by the sample averages oven the given datasets and adds regularization term with the bias oz to the objective function.
Proposition 1. Suppose that Assumptions parameter or and regularization weight
7 and are satisfied. For any given meta-
0. the following bounds hold for task

---

Ty ED [Ro.c(Alg(A, or, Dr
2/
1107 2
0112
+
P x
In pD
and
|P'1 [
BD (Alg(Al or, Dj 0o
Vi 1....,
Proposition shows the generalization emror bounds the loss function & and the constraint violation for each E,. The coefficients of the notations O and the proof' are shown in Propositions 3 and of Appendix E As the objective function in (3) includes the biased regularization term l
where the bias serves as the prior estimation for the solution, the generalization error bound includes a term of |10 dh 1|2 which decreasing as the estimation Φe more accurate. The objective function and the constraint funetions include the sample averages over the training dataset D As
the numbers of data points ((D)" and (D4] are larger, the sample average approximation is more accurate, and then the generalization error smaller.
The generalization error bounds shown in Proposition motivate learning a good meta-parameter oe by meta-learning. Next, we study the generalization error bounds for the task sequence {71. }r}- when the meta- veta-paramettrr & is arbitrary and fixed. Proposition 2 shows the upper bounds of the TAOG and the TACV for any given meta- meta-parameter Φ, i.c., the fask-specific parameter Og in (2) is computed by 0g = AAg Φ, D(")) for all t.
Proposition 2. Suppose that Assumptions and are satisfied. Consider the task sequence (Ti.... Tr}. for any given meta parameter 6, choose the regular- ization parameter A 2vdipB+ (D
Then, the following bounds hold:
Dist(d.TT.r) 1P1
In [ DD'
DD'1 D
ED [Ro,((Al(A) o, D. 00
Dist(ø, TiTT)
and
T
1
In |nrl [
E DD [Ra.(Alg(A, o, D( so
Vi 1 ,,..,
T
The coefficients of the notations O and the proofs shown in Proposition 5 of Appendix Following the result in Proposition as the average distance between the meta-parameter & and the optimal task-specific parameters {0 07), i.e. Di Ti.)), becomes small, the upper bound of the TAOG is small. By minimizing the distance Dist( Ti.)) over Φ, we can get the optimal upper bound of the TAOG:
E
T Σ EDY (A D( so (Sr(Ti
In | D
In [D
(5)
when the meta- pattapparamtter selected by ø² = arg ming Disl(ó. Ti.T). Note that the optimal upper bound is not achievable since the optimal task-specific solution 02 is not achievable for each (. In the next section, we show that the sequence of meta petta-arameterss Φi produced by Algorithm produce comparable performance the optimal meta- meta- veeta-paramtterg 6"
4.2 Generalization of the online constrained meta-learning algorithm
Consider the meta perameerreeter is updated by 4 in Algorithm T As we apply the FTPL algorithm to the meta-objective function for the online constrained meta-learning problem, the upper bounds of the TAOG and the TACV produced by Algorithm are shown in Theorem and Corollary [ As the stochastic, which depends on the task sequence and the sampling of the training data Dir and evaluation data Deaf, we denote the expectation of the optimality gap and the constraint violations (O,) E[RR,,(O..), and the expectations of the TAOG and the TACV are denoted as E R = E Σt= (0.) for all O....,m.
algorithm to compute
Theorem 1. Suppose that Assumptions 7 and 2 are satisfied. Suppose that θ is included in compact cube with edge of length Dr, iee. || Dr for any E @. Choose the regulariza- tion parameter X 22/(ppB+++ (m( and the perturbed parameter LoveT' For the task
(TTTrr))
7

---

sequence {T1, .. ,Tr), the following bounds hold for the TAOG and the TACV of Algorithm
In [Po
In D
In Doall
E [1 3 O15 (Ti:))
and B[R s
[D
D
[PT| [Dl|
Vi 1, ,...,, m.
Corollary 1. If the task Te at each t is sampled from a fixed distribution p(T). we choose
2Vd(gB+Lo /lo (2gg)) then S (Ti:) in the upper bound of B[Ro,perr] shown in Theorem I can be (-(P(T))//P5)) replaced by the fixed constant St (p(T)).
The coefficients the notations and the proofs are shown Appendices E constrained meta-learning problem, as stated in Algorithm|] 1 after the task-specific parameter Og for
and
In the online
task T3 is deployed, the agent is usually able to sample the dataset Dgai and [Dgaf]
>> [D this
case, we can ignore the term
In [D5 [Dge]
in the upper bound of E[ in Theorem
We compare
the upper bound of the TAOG by Algorithm I with the unachievable optimal upper bound shown in
5 where the term
In [2g [Dg
is ignored. The only additional term included in Theorem is O
implies that the regret of the optimality gap between the meta-parameter Φ updated by Algorithm
1 and the optimal meta-parameter ø used in (5) is sublinear with respect to the task number T.
In particular, when the constraint is ignored from Problem ( the upper bound of the TAOG reduces In [DI D
J/), which has the same order as the upper bound shown in [88 with respect to the task dissimilarity S* (p(())), the data number [D( |. and task number T.
E [1 V OSS (p(T))
Corollary [ considers that the revealed tasks are sampled from a static task distribution. In this case, when I' is sufficiently large, Algorithm| degenerates into an offline constrained meta-learning algorithm. If we further ignore the constraints in Problem (T. the bound Corollary [ of the TAOG holds the same order as the upper bound shown in [15].
5
Applications
5.1 Meta imitation learning
Meta-imitation Learning 25 40 has been developed as a powerful tool for learner to finish a new task by observing the demonstrations of expert. However, existing methods do not consider any constraint, e.g., collision avoidance, for the new task. In this experiment, we apply the constrained meta-learning algorithm to constrained meta-imitation learning problem where the learner leams to write letters in a cluttered environment [30 29] At each round é, the expert writes different letter in free space. The learner can observe the locations and velocities of few points of the letter and is asked to write the same letter in cluttered environment where the obstacle is known. The learner learns the policy by using constrained learning, where the loss function is defined by the tracking error of the learned policy, and the constraint is defined by collision metric. Note that the expert performs the free space, and the learner performs in the cluttered environment. The additional obstacle makes the problem more difficult. To the best of our knowledge, it is the first time to study
Teste boge Iindion 8
Oid MAVL consrratt
Ondine MALL
Online 5AM2E conatriid
Consttamaa relu-eereng
0.3
Fiaaree Boak aedeec)
Rtsrnd (baak Indeo))
Rexnndl Bank axteo)
Figure 1: Results of few-shot imitation learning. Left: Loss on test data: Middle: Constrained violation metric on test data. Right: Collision probability.
8

---

the problem. We provide the details of the problem formulation and the implementation setting in Appendix
We compare the proposed method with two benchmarks: (a) starting from scratch; (b) online MAML 24 with constraint penalty. In (a); the optimization problem in (3) is solved from random initial parameter. In (b), we add weighted penalty term for constraint violation to the loss function of the online MAML. For each task, the three methods share the data points.
Few-shot imitation learning. Consider that the learner collects the locations and velocities on few points (few-shot data) from the expert for each task. Fig. [ compares the proposed constrained meta-learning with the selected benchmarks. Fig. Left shows that our approach has the fastest learning rate, i.e., its test error is smaller than 20 at around T = 10, while the online MAML achieves that at around 7 = 30, and the test error of starting from scratch is always above 20. Moreover, approach has the best learning accuracy, i.e., the steady-state test error of our approach is much smaller than those of the other two methods. In terms of constraint violation, our approach achieves the lowest collision probability in Fig. Right and the lowest constraint violation metric in Fig. Middle.
Improve full-shot imitation learning by meta-learning. We consider that the learner can collect the locations and velocities on sufficient points (full-shot data) from the ex- pert for each task, and test the proposed method and the selected benchmarks. In this experiment, we show that meta-learning can im- prove the performance of con- strained learning, even if suf- ficient data can be accessed by the learner. As shown in Fig. 2 our method can achieve superior performance than that in the two benchmark approaches (only our method can completely draw the shape of the letter). Fig. 3 shows that our method achieves comparable adaptation time to online-MAA MAML while outperforming online-MAML. terms of test error and collision avoidance. Both our method and online-MAMi much outperform starting from scratch in terms of test error, collision avoidance, and adaptation time.
Leamedd trajectories for full-shot imitation learning. Left: Starting from scratch; Middle: MAML with constraint penalty: Right: Constrained meta-learning. The blue line is the demonstration trajectory, the red line is the learned trajectory, the red circle represents the obstacle.
Figure 2:
Telere S1 Sore
ne conatrant perall
siiling
Online connaarppntty
Storing Foo siuh Cntine conneerr pemily
14
11
105
MAN wilk
Dinkent
Figure 3: Results of full-shot imitation learning. Left: Loss on test data; Middle left: Constrained violation metric on test data; Middle right: Collision probability; Right: Adaptation time.
5.2 Few-shot image classification with robustness
Meta-learning has been widely used for fhw-shot learning. Few-shot learning aims to train model with only a few data samples, which is widely solved from the perspective of meta meta-learning by learning prior knowledge from multiple tasks. Consider a problem of few-shot image classification with robust learning [57]. In particular, after it is updated by a few data points, we require that the task-specific model has high accuracy clean test data and is also robust adversarial attacks the test data. Robust learning for a single task can be formulated by a constrained optimization problem [1]. Correspondingly, in this experiment, the robust few-shot image classification is formulated as a constrained meta-learning problem and is solved by the proposed algorithm. The details of the problem formulation and the implementation setting are shown in Appendix C.2

---

We test the algorithms on two few-shot learning datasets, CUB 53 and mini-Image [52) Due to To evaluate the performance of the proposed algorithm, we test the task- specific model on two sets of each dataset: (a) the clean test dataset; (b) the corrupted test dataset which is ob- tained by adding perturbations on the clean test dataset through the Projected Gradient Descent (PGD) method [37].
Table 2: Clean accuracy (abbreviated as "Clean Ace.") ") and PGD accuracy (abbreviated as "PGD Acc. ") on the mini- -mageet dataset for 5-way 5-shot and 5-way 1-shot learning.
Method
Clean Asc.
PGD Acc.
B scoore
4AML CP
40.78 : 0.75
23,91 = 0.67
29.83 = 0.43
MAML + MOML
39.23 = 0.76
25.80 = 0.67
31.12 = 0.70
1-shat
ProtoNet
38.65 0.72
0.65
0.67
ProtoNet + MOML
35.06 1 0.70
27.24
1 0.65
30.51
= 0.66
Conresonndingy., we show the test ac- curacy on (a) as clean accuracy; the test accuracy on (b) PGD accuracy.
ROIL+
40,44
25,94
31,29
BOIL + MOML
41,22 = 0.83
27.77
0.75
32.98
0.79
CMI. (ours)
39.52 1: 0.80
33.11 0.79
36.03 0.79
MAML + CP
$6.16 : 0.72
34,85 = 0.72
42.91 = 0.71
Moreover, we use Balance Score (B- metric to evaluate the comprehensive performance of the model, which is defined as B-score 2 x (CA x PA)(CA + PA) with CA and PA denoting clean accuracy and PGD
MAML + MOMI.
1:
score) [57]
5-shol
ProtoNet + CP
0.71
39.41 = 0.73
46.93 0.71
ProtoNet + MOML
58.72 1: 0.74
41.59
0.75
48.59
0.74
ROIL+ CP
58.54 2:74
34.28 0.75
42.94 0.78
BOIL + MOML
60.21 0.79
35.47
0.78
44,37 0.78
CML (ours)
0.75
accuracy, respectively. We compare the proposed constrained meta-learning (CML) with several
benchmarks: (i) MAML [23] with constraint penalty (CP); (ii) ProtoNet [49 with CP; (iii) BOIL 44 with CP: (iv) MAML with MOML [57]: (v) ProtoNet with MOML; (vi) BOIL with MOML. As the baseline methods for few-shot learning, MAML. ProtoNet, and BOIL, can only deal with unconstrained meta-learning. at (i)ii)iii,, we add a weighted penalty term of the robustness constraint violation to their loss functions. (vv)),)(vi), MAMI., ProtoNet and BOIL. fit into multi-ohjective meta-learning (MOML) framework [57] which regards the clean accuracy and the PDG accuracy as two competing objectives. Since all baseline methods are offline meta-learning, for comparisons, we use the similar way shown in Algorithm 2 of Appendix B to adapt them to the online setting. Specifically, in each round, we sample a batch of tasks from the revealed tasks, and use the gradient- based method on their meta-objective functions over the data of sampled tasks. The modification from the offline baseline methods to their online versions are exactly following our approach in terms of optimization of the online oota-objective.
US)
Desasot ImageNec (S-may S shot
0:50
Dataset (E (E-way S-shot)
Dalaset imageNic (6 (away Sishot)
3.50
Coan Mocunso
ovo
8040
Phototatt with MON.
CML Juans
0.00
USE OANTO
Photonat with MOM
CVLL (cum)
Prosonal MODL
MOME
10C Round (S05) Indox)
256
195
150
10U
186
Round (206 Indox)
(lask Incox)
Figure 4: Test accuracy v.s. training task index on dataset mini- ImageNet. Left: Clean accuracy; Middle: PGD accuracy; Right: B-score.
the page limit, the results on the CUB are shown in Appendix C.2 Table[]showe that our method significantly improves the PGD accuracy and the B-score than the benchmarks and keeps the clean accuracy comparable. Fig. showw that our method outperforms the benchmarks in terms of both test accuracy and learning speed, i.e., its test accuracy is larger than 0.5 T = 30, while the benchmarks take at least 50 tasks to achieve so.
6 Conclusion
In this paper, we develop an online constrained meta-learning framework, which learns the meta-prior from learning tasks with constraints. We theoretically quantify the optimality gaps and constraint violations produced by the proposed framework. Both two metrics consider the generalization ability of the task-specific models to unseen data. Moreover, we propose practical algorithm for the constrained meta-learning framework. Our experiments on meta-imitation learning and few-shot image classification demonstrate the superior effectiveness of the algorithm.
10

---

Acknowledgments and Disclosure of Funding
This work is partially supported by the National Science Foundation through grants ECCS 1846706 and ECCS 2140175. We would like to thank the reviewers for their constructive and insightful suggestions.
References
[1] Durmus Alp Emre Acar, Ruizhao Zhu, and Venkatesh Saligrama. Memory efficient online meta learning. In International Conference on Machine Learning, pages 32 42. PMLR, 2021.
[2] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International Conference on Machine Learning, pages 22-31. PMLR, 2017.
[3] Pierre Alquier, Massimiliano Pontil, et al. Regret bounds for lifelong learning. In Artificial Intelligence and Statistics, pages 261-269 PMLR, 2017.
[4] Maria-Florina Balcan, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees for gradient- based meta-learming, In International Conference on Machine Learning, pages 424-433. PMLR, 2019.
[5] Suneel Belkhale, Rachel Li, Gregory Kahn, Rowan McAllister, Roberto Calandra, and Sergey Levine. Model-based meta-reinforcemennt learning for flight with suspended payloads. IEEE Robotics and Automation Letters, 6(2):1471-1478. 2021.
[6] Dimitri Bertsekas. Convex optimization theory, volume 1. Athena Scientific, 2009.
[7] Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3):334-334, 1997.
[8] Aude Billard, Yann Epars, Sylvain Calinon, Stefan Schaal, and Gordon Cheng. Discovering optimal imitation strategies. Robotics and Autonomous Systems, 47(2-3):69-77, 2004.
(9] Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. Theory of classification: A survey of some recent advances. ESAIM: probability and statistics, 9:323-375, 2005.
[10] Stephen Boyd, Stephen Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[11] Rich Caruana. Multitask learning. Machine learning, 28(1):41-75, 1997.
[12] Luiz Chamon and Alejandro Ribeiro. Probably approximately correct constrained learning. Advances in Neural Information Processing Systems, 33:16722-16735, 2020.
[13] Jiaxin Chen, Xiaoming Wu, Yanke Li, Qimai Li, Liming Zhan, and Fu-lai Chung. A closer look at the training strategy for modern meta-learning. Advances in Neural Information Processing Systems, 33:396-406, 2020.
[14] Siddharth Choudhary, Luca Carlone, Carlos Nieto, John Rogers, Henrik Christensen, and Frank Dellaert. Distributed mapping with privacy and communication constraints: Lightweight algo- rithms and object-based models. The International Journal of Robotics Research, 36(12):124) 1286- 1311, 2017.
(15) Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to-leant stochastic gradient descent with biased regularization. International Conference on Machine Learning, pages 1566-1575. PMLR, 2019.
[16] Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Incremental learning- to-learn with statistical guarantees. In 34th Conference on Uncertainty in Artificial Intelligence 2018, UAI 2018, volume 34, pages 457-466. AUAI, 2018
[17) Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Learning to learn around a common mean. Advances in Neural Information Processing Systems, 31, 2018.

---

[18] Giulia Denevi, Dimitris Stamos, Carlo Ciliberto, and Massimiliano Pontil. Online-withnn-nlliee meta-learning. Advances in Neural Information Processing Systems, 32, 2019.
[19] Yuri M Ermoliev and Vladimir I Norkin. Sample average approximation method for compound stochastic optimization problems. SIAM Journal Optimization, 23(4):2231 -2263,,, 2013.
[20] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Generalization of model-agnostic meta- learning algorithms: Recurring and unseen tasks. Advances in Neural Information Processing Systems, 34:5469-5480, 2021.
[21] Alec Farid and Anirudha Majumdar. Generalization bounds for meta-learning via PAC-bayes and uniform stability. Advances in Neural Information Processing Systems, 34:2173-2186. 2021.
[22] Anthony Fiacco. Introduction to sensitivity and stability analysis in nonlinear programming. Academic press, 1983.
[23] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adapta- tion of deep networks. In International Conference on Machine Learning, pages 1126-1 135. PMLR, 2017.
[24] Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online meta-learning. In International Conference Machine Learning, pages 1920-1930. PMLR, 2019.
[25] Chelsea Finn, Tianhe Yu, Tianhao Zhang, Pieter Abbeel, and Sergey Levine. One-shot visual imitation learning via meta-leamnin. In Conference on Robot Learning, pages 357-368. PMLR, 2017.
[26] James Hannan. Approximation to bayes risk repeated play. Contributions to the Theory of Games, 3(2):97-139, 1957.
[27] Nathan Hilliard, Lawrence Phillips, Scott Howland, Artêm Yankov, Courtney D Corley, and Nathan O Hodas. Few-shot learning with metric-agnostic conditional embeddings. arXiv preprint arXiv: 1802:008007337 2018
[28] Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey. Meta-learning in neural networks: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(9):5149-514 2021.
[29] Yanlong Huang. Ekmp: Generalized imitation learning with adaptation, nonlinear hard con- straints and obstacle avoidance. arXiv preprint 10X0v:2/03.00452, 2021.
[30] Yanlong Huang, Leonel Rozo, Joao Silvério, and Darwin G Caldwell. Kernelized movement primitives. The International Journal of Robotics Research, 38(7):833-852 2019.
[31] Yu Huang, Yingbin Liang, and Longbo Huang. Provable generalization of overparameterizee meta-learning trained with SGD. arXiv preprint XXXXv:220060011366 2022.
[32] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pages 4882-4892. PMLR, 2021.
[33] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Theoretical convergence of multi-step model-agnostic meta-learning. Journal of Machine Learning Research, 23:29-1, 2022.
[34] Vanshaj Khattar, Yuhao Ding, Javad Lavaei, and Ming Jin. A for meta-safe reinforcement learning. In International Conference on Learning Representations, 2023.
framework
[35] Mikhail Khodak, Maria-Florina F Balcan, and Ameet S Talwalkar. Adaptive gradient-basee meta-learning methods. Advances in Neural Information Processing Systems, 32, 2019.
[36] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv.1412.6980, 2014.
12

---

[37] Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. Artificial intelligence safety and security, pages 99-112. Chapman and Hall/CRC, 2018.
[38] Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, and Stefano Soatto. Meta-learning with differentiable convex optimization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10657-10665, 2019.
[39] Thomas Lew, Apoorva Sharma, James Harrison, Andrew Bylard, and Marco Pavone. Safe active dynamics learning and control: A sequential apploraion-explooitatonn framework. IEEE Transactions on Robotics, 2022.
[40] Jiayi Li, Tao Lu, Xiaoge Cao, Yinghao Cai, and Shuo Wang. Meta-imitation learning by watching video demonstrations. In International Conference on Learning Representations, 2022.
[41] Zhenguo Li, Fengwei Zhou, Fei Chen, and Hang Li. Meta-SGD: Learning to learn quickly for few-shot learning. arXiv preprint arXiv:1707.0m 09835, 2017.
[42] Shicheng Liu and Minghui Zhu, Distributed inverse constrained reinforcement learning for multi-agent systems. Advances in Neural Information Processing Systems, 35:33444-3344 2022.
[43] Anusha Nagabandi, Ignasi Clavera, Simin Liu, Ronald S Fearing, Pieter Abbeel, Sergey Levine, and Chelsea Finn. Learning adapt in dynamic, real-world environments through meta- reinforcement learning. In International Conference on Learning Representations, 2018.
[44] Jaehoon Oh, Hyungjun Yoo, ChangHwan Kim, and Se- Young Yun. BOIL: Towards representa- tion change for few-shot learning. In International Conference on Learning Representations, 2021.
[45] German I Parisi, Ronald Kemker, Jose L Part, Christopher Kanan, and Stefan Wermter. Continual lifelong learning with neural networks: A review. Neural Networks, 113:54-71, 2019.
[46] Anastasia Pentina and Christoph Lampert. A PAC-bayesian bound for lifelong learning. In International Conference on Machine Learning, pages 991-999, PMLR, 2014.
[47] Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. leta-lea with implicit gradients. Advances in Neural Information Processing Systems, 32, 2019.
[48] Sachin Ravi and Hugo Larochelle. Optimization model for few-shot learning. In Interna- tional Conference on Learning Representations, 2017
[49] Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. Advances in Neural Information Processing Systems, 30, 2017.
[50] Arun Sai Suggala and Praneeth Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. In Algorithmic Learning Theory, pages 845-861. PMLR, 2020.
[51] Sebastian Thrun and Lorien Pratt. Learning learn. Springer Science & Business Media, 2012.
[52] Oriol Vinyals, Charles Blundell, Timothy Lillicrap. Daan Wierstra, et al. Matching networks for one shot learning. Advances Neural Information Processing Systems, 29, 2016.
[53] Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongic. The caltech-uesd birds-200-2011 dataset. California Institute of Technology, 2011.
[54] Siyuan Xu and Minghui Zhu. Meta value learning for fast policy-centric optimal motion planning, Robotics Science and Systems, 2022.
[55] Siyuan Xu and Minghui Zhu. Efficient gradient approximation method for constrained bilevel optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 37(10): 12517, 2023.
13

---

[56] Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. In International Conference Machine Learning, pages 449-457. PMLR, 2016.
[57] Feiyang Ye, Baijiong Lin, Zhixiong Yue, Pengxin Guo, Qiao Xiao, and Yu Zhang. Multi- objective meta learning. Advances in Neural Information Processing Systems, 34:21338-21351 2021.
14


Reviews:
[{"review_id": "1BYGKr69pd", "reviewer": "Reviewer_FYCS", "summary": "The authors propose an online constrained meta-learning algorithm that is able to sequentially learn a  sequence of tasks that are subject to hard (and stochastic) constraints. The authors also theoretically quantify the optimality gaps and constraint violations produced by the proposed method, by considering the dynamic regret of online learning and the generalization ability of the task-specific models. They also validate the effectiveness of the proposed method on numerical experiments on meta-imitation learning and few-shot image classification.", "questions": "The constraints are random variables. This seems to be problematic. Which is the main trick you use to deal with it?\n\nThe authors use the notion of variance of the task optimal parameters to measure the similarity among the tasks, as in [14] and the paper [A] I mention here below. Could you please make a clearer comparison between your rates and those obtained in these other work, by just looking at the main important constants and leading terms w.r.t. the number of tasks and within-task points? Consider also the different assumptions.\n\n[A] Denevi et al., 'Online-Within-Online Meta-Learning'.\n\n", "limitations": "I do not see any potential negative societal impact related to this work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The authors validate their proposed method, both theoretically and experimentally.\n\nThe authors present a new meta-learning method aiming at facing the more challenging situation in which the tasks are stochastically subject to constraints.", "weaknesses": "The statements and the notation of the paper could be simplified and made more intuitive, less heavy.\n\nWhy can the constrained meta-learning framework be interesting in practical application? The authors do not well motivate the setting they consider. This is a very important aspect in my opinion. Could you please describe some examples of possible applications in which the proposed constrained setting can be useful/necessary?\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our work. Thanks for your suggestions and reference recommendation. We address your concerns as follows.\n\n> **Weakness 1.  The statements and the notation of the paper could be simplified and made more intuitive.**\n\n**Answer:** Thank you for the suggestion. We will simplify the notations and attach the notation list in the global rebuttal PDF file, and will add it to the revised appendix. \n\n> **Weakness 2.  Why can the constrained meta-learning framework be interesting in practical application and what are the motivation examples.**\n\n**Answer:** Constrained meta-learning learns a meta-parameter from existing constrained learning tasks, where each task needs to minimize its expected loss while satisfying its constraints. \nWhen a new constrained learning task is revealed, the meta-parameter is adapted to the new task, which improves the learning efficiency and reduces the expected risk and constraint violation on the new tasks. \nExisting meta-learning approaches can only learn from unconstrained learning tasks.\n\nBelow are a couple of examples that motivate the constrained meta-learning framework.\n\n* One motivated example is imitation learning with collision avoidance in changing environments, as shown in our first experiment (Section 5.1). The expert performs demonstrations in a free space. The learner can observe the demonstrations and is asked to perform the task in a new cluttered environment quickly. The new environment is uncertain and unknown to the learner until the task is revealed.\n\n* Another motivated example is robot control with different dynamics. Consider a scenario that a robot needs to quickly deploy a new control policy once its dynamics change. The problem can be formulated as constrained meta-learning, where actuation limitations are imposed as constraints for the control policy. The within-task is to find the task-specific control policy that can minimize the control cost for the robot while satisfying the actuation constraints of the robot dynamics. The meta-algorithm is to optimize a meta control policy that adapts to the task-specific control policy once the new dynamics is given.\n\nWe will include the above discussion in the revised manuscript. \n\n> **Question 1.  The constraints are random variables. This seems to be problematic. Which is the main trick you use to deal with it?**\n\n**Answer:**\n\n* In constrained stochastic optimization, it is standard to define both the objective function and the constraint functions as functions of random variables [7][16]. \n* In our proposed algorithm, we use the sample average approximation method to approximate the expectation, i.e., using the empirical average of the constraint functions on the given training data to approximate the constraint function defined by the whole data distribution, as shown in Equation (3) (line 176 in Section 3).\n* As shown in Proposition 4 of Appendix D and Appendix C.2, we quantify the error between the sample average approximation and the expectation by analyzing the Rademacher complexity [7][16] of the constraint functions.\n\n> **Question 2.  Comparison between your rates and those obtained in the related works [A][14].**\n\n**Answer:**\n\n**Comparison of assumptions.** Papers [A] and [14] assume the learning model is linear, i.e., $\\mathcal{E}(Z)=\\sum_{i=1}^n \\ell_i(\\langle x_i, w_i\\rangle)$, while ours could be any function, such as a neural network. Our paper, [14] and [A] have similar assumptions about the convexity of functions. By adding a regularizer in the meta-objective function, the overall meta-objective in [14][A] is convex, while the meta-objective function in our paper is non-convex.\n\n**Comparison of metrics.** Paper [14] considers offline meta-learning and quantifies the expected optimality gap of the task-specific parameters over the task distribution. Paper [A] considers online meta-learning and the dynamic regret of the expected optimality gaps over sequential tasks. Similar to [A], we consider the dynamic regret of the expected optimality gaps.\nBeyond [A], we consider the constraints, and thus need to (a) quantify the constraint violations and (b) quantify the error on the loss function introduced by the inexact constraint approximation.\n\n**Comparison of rates.** If all the constraints are removed from our problem, our result has the same order as the upper bound shown in Corollary 7 of [A] and Theorem 6 of [14], in terms of the number of tasks $T$ and within-task points $n$. \n\nWe will include the above discussion in the revised manuscript. "}, {"review_id": "h1VealeqTT", "reviewer": "Reviewer_CTub", "summary": "The paper studies the theory of biased-regularization meta-learning under the sequential task setting. Despite there having been previous works in this area, this paper distinguishes itself by introducing the concept of the Online Constrained Meta-Learning problem and presenting a straightforward solution. It applies constrained optimization with biased meta-regularization, utilizing Follow-the-Perturbed-Leader (FTPL) FTPL to handle the non-convex meta-objective function, providing theoretical analysis and proofs of upper bounds, and developing a practical algorithm for large-scale problems. Empirical experiments validate the effectiveness of the proposed algorithm in meta-imitation and meta-reinforcement learning.", "questions": "- Why define $D(\\phi, \\mathcal{T}_{1:T})$, $\\mathcal{S}^*(\\rho(\\mathcal{T}))$ in square root form?\n\n- What will happen if we only learn the same task, i.e., $\\mathcal{S}^*(\\rho(\\mathcal{T})) \\to 0$, then the coefficient will be infinitely large $\\lambda \\to \\infty$. Do the results still hold true in such a degenerate case?\n\n- Is Assumption 1 should hold $\\forall t$? If it is, please make it clear.\n\n- As mentioned above, what does big-O notation mean in the results?", "limitations": "N/A pure theoretical work.\n\n\n**References**:\n\n[1] Denevi, Giulia, Massimiliano Pontil, and Carlo Ciliberto. \"The advantage of conditional meta-learning for biased regularization and fine-tuning.\" Advances in Neural Information Processing Systems 33 (2020): 964-974.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "- This paper first studies the online constrained meta-learning, which is rarely concerned. To this end, this paper gave the formal problem formulation of constrained sequential learning. \n\n- The author distinguishes the assumptions proposed by this paper and follows others. It makes it easier to examine the assumptions applied in this paper.\n\n- A solid work that follows the setting of learning with biased regularization. The author gives a detailed discussion of different cases.", "weaknesses": "- Of a particular relevant missing work, [1] can also be deemed as the constrained (conditional) meta-learning. The author should further discuss this work since [1] also shows the generalization results. \n\n- More implications are needed to explain the results, i.e., Corollary 1. \n\n- The bounds of the derived results have not been examined. For instance, the second term in RHS of Prop 3 is the order of $\\mathcal{O}(d^2\\mathcal{B} L_0^2 \\ln |\\mathcal{D}^{tr}_0|)$, which can be a dominate term.  Furthermore, the diameter $\\mathcal{B}$ and model size $d$ can also be large enough. This result may not be applied to overparameterized settings.\n\n- The relationship between $\\mathcal{D}_t$ and $\\mathcal{D}$ is vague. Suppose $\\mathcal{D}$ refers to any $t$ in $\\mathcal{D}_t$. The statement of Propositions and Theorems should clarify this point.\n\n- From the Proofreading of Appendix 4, I found the bounds in Proposition 3 & 4 depend on many terms. However, in Prop.1 & 2, the author removes the small terms (in Big-O notation) without discussing the orders of these terms in what limits. \n\n——Minors——\n- Confusing statement about “Problem (1), (3)”. Since the author refers to Equations (1) and (3) as “Algorithms” and “Problems” simultaneously, it may be better to define the “Problems” officially.\n\n- Adding a notation cheatsheet in the appendix may be more readable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our work. Thanks for your suggestions and reference recommendation. We address your concerns as follows.\n\n> **Weakness 1.  Discussion of connections with conditional meta-learning.**\n\n**Answer:** Thanks for the reference. Constrained meta-learning and conditional meta-learning aim to achieve different goals.\n\nIn meta-learning, the goal of the within-task is minimizing the expected loss.  Meta-learning aims to learn a shared meta-parameter for all tasks that can improve the learning of new tasks. \n\nIn conditional meta-learning, the goal of the within-task is minimizing the expected loss, which is the same as meta-learning. Different from meta-learning, conditional meta-learning aims to learn a map from the task information to its meta-parameter to facilitate within-task learning, rather than learning a shared meta-parameter for all tasks in meta-learning.\n\nIn our constrained meta-learning, the goal of the within-task is minimizing the expected loss while satisfying imposed constraints. The constraints are not included in meta-learning and conditional meta-learning. The approaches of solving them are also different. \n\n> **Weakness 2.  More implications of Corollary 1.**\n\n**Answer:** Here is the implication of Corollary 1. We will include the discussion in the revised manuscript. \n\nCorollary 1 considers that the revealed tasks are sampled from a static task distribution. In this case, when $T$ is sufficiently large, the online meta-learning algorithm degenerates to an algorithm for offline meta-learning. If we further ignore the constraints in our problem setting, the bound of Corollary 1 holds the same order as the upper bound shown in [14]. \n\n> **Weakness 4. The relationship between $\\mathcal{D}\\_t$ and $\\mathcal{D}$.**\n\n**Answer:** Sorry about the confusion. We denote ${D}(\\phi, \\mathcal{T}\\_{1:T})$ as the parameter distance, denote $\\mathcal{D}\\_t$ as the data distribution for task $\\mathcal{T}\\_t$, and denote the edge length as $D$. These notations are too close. We will modify ${D}(\\phi, \\mathcal{T}\\_{1:T})$ to $\\mathcal{D}ist(\\phi, \\mathcal{T}\\_{1:T})$, and modify $D$ to $D\\_l$ in the revised manuscript.\n\n> **Weakness 5 and Question 4. The Big-O notation with respect to what limits/ what does big-O notation mean in the results.**\n\n**Answer:** We consider the Big-O notation only with respect to the limits of (i) the data numbers including $\\|\\mathcal{D}\\_{0}^{tr\\}|$, $\\|\\mathcal{D}\\_{0}^{val\\}|$ and $|\\mathcal{D}\\_{+}^{tr}|$ (ii) the task similarity $\\mathcal{S}^{\\*}( \\mathcal{T}\\_{1:T})$ (iii) the task number $T$.\n\n> **Weakness 6.  Refer about Equations (1) and (3) as “Algorithms” and “Problems” simultaneously.**\n\n**Answer:** Sorry about the confusion. Equation (1) is a problem. Equation (3) is an algorithm to approximate the solution of Equation (1). Equation (3) includes an optimization problem. We will clarify them in the revised manuscript. \n\n> **Weakness 7. Adding a notation checksheet in the appendix may be more readable.**\n\n**Answer:** Thank you for the suggestion. We attach the notation list in the global rebuttal PDF file, and will add it to the revised appendix. \n\n> **Question 1.  Why define $D\\left(\\phi, \\mathcal{T}\\_{1: T}\\right), \\mathcal{S}^{\\*}(\\rho(\\mathcal{T}))$ in square root form.**\n\n**Answer:** Following [14], we would like to define $D\\left(\\phi, \\mathcal{T}\\_{1: T}\\right)$ and $\\mathcal{S}^*(\\rho(\\mathcal{T}))$ as metrics of the parameter distance, and thus consider the square root of the quadratic sum $\\frac{1}{T}\\sum_{t=1}^T \\frac{1}{2}\\|\\|{\\theta}^{\\*}_t-{\\phi}\\|\\|^2$.\n\n> **Question 2.  What will happen if we only learn the same task, i.e., $\\mathcal{S}^{\\*}(\\rho(\\mathcal{T})) \\rightarrow 0$, then the coefficient will be infinitely large $\\lambda \\rightarrow \\infty$. Do the results still hold true in such a degenerate case?**\n\n**Answer:** The result still holds in the degenerate case. Here is the reason.\n\nWhen $\\lambda \\rightarrow \\infty$, the term $\\frac{\\lambda}{2}\\|\\|\\theta-\\phi_t\\|\\|^2$ totally dominates in the objective function of the optimization problem of Equation (3), then the problem reduces to\n\n${\\theta}\\_t = \\mathcal{A}lg(\\lambda,\\phi\\_t, \\mathcal{D}\\_{t}^{tr})=\\arg\\min_\\theta \\|\\|\\theta-\\phi_t\\|\\|^2, s.t. \\frac{1}{|\\mathcal{D}\\_{i,t}^{tr}|} \\sum\\_{z \\in \\mathcal{D}\\_{i,t}^{tr}}\\ell_i(\\theta,z) \\leq c\\_{i,t}, \\ i=1, \\ldots, m. $\n\nAs we can see, the the solution ${\\theta}\\_t$ will not depend on $|\\mathcal{D}\\_{0}^{tr}|$ and only depend on $|\\mathcal{D}\\_{+}^{tr}|$, $|\\mathcal{D}\\_{0}^{val}|$, and $T$. This result corresponds to Theorem 1 with $\\mathcal{S}^*(\\rho(\\mathcal{T})) \\rightarrow 0$, where the result will not depend on $|\\mathcal{D}\\_{0}^{tr}|$ and only depend on $|\\mathcal{D}\\_{+}^{tr}|$, $|\\mathcal{D}\\_{0}^{val}|$, and $T$. So the results still hold in such a degenerate case.\n\n> **Question 3.  Is Assumption 1 should hold for all $t$ ?**\n\n**Answer:** Yes, we will clarify it in the revised manuscript. "}, {"review_id": "cXZ8sZtP71", "reviewer": "Reviewer_jLc8", "summary": "In this paper, a novel online constrained meta-learning framework is presented. The framework is designed to facilitate continuous learning from sequential tasks while ensuring that these tasks adhere to strict constraints. In addition to existing analyses of meta-learning, this study goes further by presenting the upper bounds for optimality gaps and constraint violations that arise from the proposed framework. \nThis framework takes into account the dynamic regret of online learning and the generalization capability of the task-specific models. Finally, the paper offers a practical algorithm to implement the framework, and its superior effectiveness is validated through experiments conducted in the domains of meta-imitation learning and few-shot image classification.", "questions": "- In section 2.1, the proposed constrained optimization paradigm in the paper requires that different tasks satisfy certain constraints on errors under any task-adaptive parameters. Intuitively, this may seem contradictory to improving the performance of specific tasks. Task-adaptive parameters should ideally be focused solely on specific tasks, so why is there a need to ensure the performance of other tasks simultaneously? Is it more reasonable to constrain the meta-parameters?", "limitations": " It should compare with existing online meta learning bounds.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper consider that the meta-objective is non-convex.\n- Study the dynamic regrets.\n- Two elaborate applications demostrate the superior effectiveness of the algorithm.", "weaknesses": "- The bound is scaled with $\\mathcal{O}(\\frac{1}{\\sqrt{T}})$. This seems to ignore the size of every training datasets.\n- The comparion with existing online meta learning bounds is necessary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our work. Thanks for your suggestions. We address your concerns as follows.\n\n> **Weakness 1. The bound is scaled with $\\mathcal{O}\\left(\\frac{1}{\\sqrt{T}}\\right)$. It seems to ignore the size of training datasets.** \n\n**Answer:** The upper bound in Theorem 1 is \n$\\mathcal{O}\\left(\\mathcal{S}^*\\left(\\mathcal{T}\\_{1: T}\\right) \\sqrt{\\frac{\\ln \\left|\\mathcal{D}\\_0^{t r}\\right|}{\\left|\\mathcal{D}\\_0^{t r}\\right|}}+\\sqrt{\\frac{\\ln \\left|\\mathcal{D}\\_{+}^{t r}\\right|}{\\left|\\mathcal{D}\\_{+}^{t r}\\right|}}+\\sqrt{\\frac{\\ln \\left|\\mathcal{D}\\_{0}^{val}\\right|}{\\left|\\mathcal{D}\\_{0}^{val}\\right|}}+\\frac{1}{\\sqrt{T}}\\right)$.\nAs shown in Appendices E and F, the coefficients of the notations $\\mathcal{O}$ are independent of the size of training datasets and only depend on some constants, such as the Lipschitz constant $L_0$.\n\n* The first term $\\left(\\mathcal{S}^*\\left(\\mathcal{T}\\_{1: T}\\right) \\sqrt{\\frac{\\ln \\left|\\mathcal{D}\\_0^{t r}\\right|}{\\left|\\mathcal{D}\\_0^{t r}\\right|}}+\\sqrt{\\frac{\\ln \\left|\\mathcal{D}\\_{+}^{t r}\\right|}{\\left|\\mathcal{D}\\_{+}^{t r}\\right|}}+\\sqrt{\\frac{\\ln \\left|\\mathcal{D}\\_{0}^{val}\\right|}{\\left|\\mathcal{D}\\_{0}^{val}\\right|}}\\right)$ depends on the size of training datasets. As shown in Equation (5) and Proposition 2, the term quantifies the generalization error when limited training data is given. \n\n* The last term $\\left(\\frac{1}{\\sqrt{T}}\\right)$ is independent of the size of training datasets. \nThe term $\\mathcal{O}\\left(\\frac{1}{\\sqrt{T}}\\right)$ is the gap of the meta-objective function $\n\\sum_{t^{\\prime}=1}^{t} \\mathcal{L}^{val}(\\mathcal{A}lg(\\lambda,\\phi, \\mathcal{D}\\_{t^{\\prime}}^{tr}),\\mathcal{D}\\_{0,t^{\\prime}}^{val} ) \n$ (defined in line 193) between the meta-parameter $\\phi=\\phi_t$ produced by our algorithm and the optimal meta-parameter $\\phi=\\phi^*$.\nThe size of the training dataset will not influence the gap of the meta-objective function values between $\\phi_t$ and $\\phi^{\\*}$, because the values on both $\\phi_t$ and $\\phi^*$ use $\\mathcal{A}lg$ in Equation (3) with the same training data (limited data size) to obtain the solutions. No matter whether the size of the training data is large or small, the size is shared for $\\phi\\_t$ and $\\phi^{\\*}$ and imposes the same error on $\\phi\\_t$ and $\\phi^{\\*}$.\n\n> **Weakness 2. Comparison with existing online meta-learning bounds.** \n\n**Answer:** In Table 1, we compare the used metrics in our paper and existing works [3] [14] [1] [21]. The metrics used in this manuscript are harder to quantify than most existing papers, in terms of constraint, generalization, and dynamic regret. Here, we compare our results with [3] [14] [1] [21] [R1].\n\n* We consider the constraints in each learning task, and thus need to (a) quantify the constraint violations and (b) quantify the error on the loss function introduced by the inexact constraint approximation. These are not considered in all existing works.\n* If all the constraints are removed from our problem, our result $\\mathcal{O}(\\mathcal{S}^{\\*}(p(\\mathcal{T})) \\sqrt{\\frac{\\ln{|\\mathcal{D}\\_{0}^{tr}|}}{|\\mathcal{D}\\_{0}^{tr}|}}  +\\frac{1}{\\sqrt{T}})$ has the same order as the upper bound ${\\mathcal{O}}(\\ln(n) / \\sqrt{n})+\\mathcal{O}(1 / \\sqrt{T})$ shown in [R1] and [14], in terms of the number of tasks $T$ and the number of the within-task data points $n$ or $|\\mathcal{D}_{0}^{tr}|$. \n* Paper [3] does not consider the generalization error produced by the limited data size, and considers a strongly-convex meta-objective (ours is non-convex). Then, the bound is $\\mathcal{O}(\\mathcal{S}^{*}(p(\\mathcal{T}))+\\frac{1}{{T}})$, which is independent of $|\\mathcal{D}_{0}^{tr}|$ and has the order of $\\mathcal{O}(\\frac{1}{{T}})$ because of the strongly convexity.\n* Paper [1] consider a strongly-convex meta-objective (ours is non-convex) and a static regret (ours is a dynamic regret) and has the order of $\\mathcal{O}(\\frac{1}{{T}})$. \n* In conclusion, for the degenerate case where the constraints are removed, our bound has the same order as the state-of-art works. If we further impose stronger assumptions (such as strong convexity) or consider a simpler metric (such as generalization ignored), the bound could be better. \n\nWe will include the above discussion in the revised manuscript. Here is the reference.\n\n[R1] Denevi et al., 'Online-Within-Online Meta-Learning'.\n\n> **Question 1. In section 2.1, the proposed constrained optimization paradigm in the paper requires that different tasks satisfy certain constraints on errors under any task-adaptive parameters. Intuitively, this may seem contradictory to improving the performance of specific tasks. Task-adaptive parameters should ideally be focused solely on specific tasks, so why is there a need to ensure the performance of other tasks simultaneously?**\n\n**Answer:** In section 2.1 and other sections of the manuscript, the task-specific parameter always only needs to satisfy the constraints for its specific task, and doesn't require that different tasks satisfy certain constraints. \n\nIn section 2.1, the task $\\mathcal{T}_t$ is characterized by its data distributions $\\mathcal{D}\\_{t}=\\{\\mathcal{D}\\_{0,t},\\mathcal{D}\\_{1,t}, \\ldots, \\mathcal{D}\\_{m,t}\\}$. Here, $\\mathcal{D}\\_{i,t}$ is the constraint dataset only for task $\\mathcal{T}_t$, the constraint satisfaction of $\\mathbb{E}\\_{z \\sim \\mathcal{D}\\_{i,t}}\\left[\\ell_i(\\theta,z)\\right] \\leq c\\_{i,t}$ with $\\mathcal{D}\\_{i,t}$ is specific for task $\\mathcal{T}\\_t$. From Equation (1), different tasks (e.g., $\\mathcal{T}\\_{t_1}$ and $\\mathcal{T}\\_{t_2}$) have different constraint datasets ($\\mathcal{D}\\_{i,t_1}$ and $\\mathcal{D}\\_{i,t_2}$ for $i$-th constraint), and should satisfy different constraint functions ($\\mathbb{E}\\_{z \\sim \\mathcal{D}\\_{i,t_1}}\\left[\\ell_i(\\theta,z)\\right] \\leq c\\_{i,t_1}$ and $\\mathbb{E}\\_{z \\sim \\mathcal{D}\\_{i,t_2}}\\left[\\ell_i(\\theta,z)\\right] \\leq c\\_{i,t_2}$)."}, {"review_id": "fzmyXRlo59", "reviewer": "Reviewer_MvUS", "summary": "The paper studies the problem of online meta-learning with constraints. After a formalization of the problem, the paper proposes an algorithm in the case where the loss function is convex, using Follow-the-Perturbed-Leader (FTPL) to update the meta-objective.\nThen the paper theoretically prove upper bounds on the regret and the violation of the constraints for their constrained learning setting.\nFinally, the paper presents experimental results on two different applications, meta imitation learning with collision avoidance and robust few-shot image classification.  ", "questions": "I would like the authors to describe how the methods are evaluated on the robust few-shot image classification benchmarks:\n- The models are trained on how many tasks ? \n- Are the tasks different between meta-training and meta-testing ? If so, how many meta-testing tasks are considered ? Otherwise, I would like to see results of online meta-learning methods on this benchmark.\n- It's not totally clear to me why the algorithm would be specific to the constrained case.  ", "limitations": "The paper does not include a discussion of the limitations of their approach. The algorithm presented seems to be more costly to run than online MAML. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "### Originality\n\n- The paper presents a detailed theoretical analysis in the constrained setting.\n- The algorithm is a combination of iMAML [1] using FTPL instead of FTL for the online setting.\n\n### Quality\n\n- The paper presents and proves theoretical upper bounds in the constrained setting with their proposed algorithm, with a lot of theoretical developments in the appendix. It shows the soundness of their approach.\n\n### Clarity\n\n- The formalization of the problem is clear.\n\n### Significance\n\n- Results on the different benchmarks and applications presented show strong performance compared to baselines.\n\n[1]: Rajeswaran, A., Finn, C., Kakade, S. M., & Levine, S. (2019). Meta-learning with implicit gradients. Advances in neural information processing systems, 32.", "weaknesses": "### Clarity\n\n- The relation of the proposed algorithm to previous work is quickly dismissed. The authors introduce online meta-learning algorithms in l.23-33, and in the related works section (l.88 - 98), the paper presents only optimization-based meta-learning algorithm. However, there is no discussion to clearly explain the differences with their proposed algorithm.\n- The way the tasks are set up in the applications are not very well described. Specifically in the robust few-shot classification benchmarks, it is not clear how the benchmark is adapted for this *online* setting, since these datasets are more commonly used for few-shot meta-learning. \n\n\n### Quality\n\n- If I understand correctly, the approach presented is a combination of iMAML with FTPL for the online setting and with the constraint penalty. Thus, it would make sense to add other meta-regularization algorithm baselines in the benchmarks, such as iMAML at least.\n- In the robust few-shot classification application presented, the other baselines are not designed for *online* meta-learning. The comparison seems unfair.\n- The authors state that their approach speeds up the adaptation to new tasks (l.357), but we can see in Figure 3 (right) that it is the opposite, their algorithm takes more time to adapt.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our paper. We address your concerns as follows.\n\n>**Weakness of Clarity 1.**\n\n**Answer:** Sorry about the missing discussion. Here are the relation of the proposed algorithm to previous works and the intuition of our algorithm design. We will add them to our revised manuscript. \n\nIn constrained meta-learning, the task-specific parameter should satisfy its given constraints.\nWe employ the meta-regularization approach with hard constraints as the within-task algorithm, and use the follow-the-perturbed-leader to handle the meta-objective of sequential tasks.\nIn the meta-initialization approaches shown in [38, 20, 21, 3, 32], as the within-task algorithm only takes a few optimization steps, even if we do optimization to reduce the constraint violation, the solution is far from feasible. On the other hand, the meta-regularization approaches shown in [15, 14, 43, 29] fully solve the within-task.\nTo prioritize constraint satisfaction, we combine the meta-regularization approach with hard constraints for constrained meta-learning.\n\n>**Weakness of Clarity 2.**\n\n**Answer:** Sorry about the missing description. Here, we will show the experiment settings in the robust few-shot classification and how to modify them to the online setting.\n\n>> What are the online setting and the data setting for meta-training and meta-test.\n\nTake the mini-Imagenet dataset as the example (similar for the CUB dataset).\nThe mini-Imagenet dataset includes 100 classes of images.\nWe have 64 classes for training images, 16 classes for validation images, and 20 classes for test images.\nDuring the online meta-training, in each round, we sample a task only from the 64 training data classes and regard it as the revealed task, i.e., sample a 5-way k-shot task (5 classes and k images for each class). There are 200 rounds of online learning, and thus we sample 200 tasks from the training data. In the meta-test for Table 2, we use the test dataset with 20 classes. From the 20 test classes, we sample 600 tasks, i.e., 600 times of 5-way k-shot data from the 20 test classes, which means that the image classes in the 600 meta-test tasks are unseen in training tasks.\n\n>>How are the baseline methods adapted for this online setting.\n\nSince the baseline methods are offline, for comparisons, we use a similar way to Algorithm 2 (shown in Appendix A) to adapt them to the online setting. Specifically, in each round, we sample a batch of tasks from the revealed tasks, and use the gradient-based optimization method on their meta-objective functions over the data of sampled tasks. The modification from the offline baseline methods to their online versions exactly follows our approach in terms of optimization of the online meta-objective. Moreover, the dataset setting is the same for all baseline methods and our approaches.\n\nWe will include the discussions in the revised manuscript.\n\n>**Weakness of Quality 3.**\n\n**Answer:** As the existing meta-regularization algorithms cannot handle neither the constraints for tasks nor online meta-learning (sequential task setting), we cannot directly compare our performances on the online constrained meta-learning problem.\n\nWe compare our method with online-MAML. It is an online meta-learning method, and we add the constraint penalty loss to enable it to handle the constraints. As shown in the iMAML paper, the difference in the accuracy of MAML and iMAML is small (not larger than 1\\%) in the two datasets. So, we think that online-MAML and an online version of iMAML will have comparable performance, and we only compare with online-MAML for convenience.\n\n>**Weakness of Quality 4.**\n\n**Answer:** As shown in response to weakness 2, since the baseline methods are offline, to do comparisons, we modify them to their online versions. The modification from the offline baseline methods to their online versions exactly follows our approach in terms of optimization of the online meta-objective. If it is the first time to study an offline learning problem, it is a standard practice to modify existing offline methods to solve the new online problem and compare the modified methods with newly developed methods [21][R2]. Thus, the comparisons are fair. \n\n[R2] Yao, Huaxiu, et al. \"Online structured meta-learning.\"\n\n>**Weakness of Quality 5.**\n\n**Answer:** Sorry about the confusion. We want to claim that \"Figure 3 shows that our method achieves a comparable adaptation time to with online-MAML while outperforming online-MAML in terms of test error and collision avoidance.\" We will modify the statement in our revised manuscript.\n\n>**Question 1. The models are trained on how many tasks.**\n\n**Answer:** As shown in response to weakness 2, the mini-Imagenet dataset includes 100 classes of images. We have 64 classes for training images, 16 classes for validation images, and 20 classes for test images. From the 64 training image classes, we sample 200 tasks (5-way k-shot learning tasks) for meta-training. From the 20 test image classes, we sample 600 tasks for the meta-test. So the test tasks used to test the performance are unseen in the meta-training phase.\n\n>**Question 2. Are the tasks different between meta-training and meta-test? How many meta-test tasks are considered?**\n\n**Answer:** As shown in responses to Weakness 2 and Question 1, the tasks between meta-training and meta-test are different. The test tasks used to test the accuracy (Table 2) are unseen in the meta-training phase. We have 600 tasks sampled from the test dataset as the meta-test tasks.\n\n>**Question 3. Why the algorithm would be specific to the constrained case.**\n\n**Answer:** Algorithm 2 (in Appendix A) uses the primal-dual approach to solve constrained optimization in Equation (3) (line 3 of Algorithm 1), and uses the constrained bilevel optimization analysis [50] to compute the gradient of the constrained bilevel objective function in Equation (4) and minimize the function (line 6 of Algorithm 1)."}]

Author rebuttal:
We are grateful and indebted for the time and effort invested to evaluate our manuscript by all reviewers, and for all the suggestions and reference recommendations to make our manuscript a better and stronger contribution. Please find below our detailed replies to all the comments of the reviewers.

We notice that some reviewers suggest to attach a notation checklist. We attach a notation list in the global rebuttal PDF file for the convenience of our discussion and also add it to the revised appendix. 

Meta-review: This paper provides original contribution in online constrained meta-learning under the sequential task setting. The paper proposes further analysis with respect to state of the art by deriving theoretical results in the form of upper bounds for optimality gaps and constraint violations. The proposed framework takes into account the dynamic regret of online learning and the generalization capability of the task-specific models. Some effective experimental evaluation meta-imitation learning and few-shot image classification are presented.  

Reviewers recognized the quality and interestingness of the paper.  
Some issues about the notations, some statements, and precisions with respect to other methods and settings were raised by the reviewers.  
During the rebuttal, authors have provided explanations to the points of the reviewers, they also joined a notation checklist about the notations used.  
All reviewers have acknowledged that their concerns have been addressed.  
  
Based on all the proviso remarks I propose then acceptance.  
I recommend to the authors to insert the notation checklist in the revised appendix of the paper, in line with their commitment, and to revise the paper by including all the precisions and discussions evoked during the discussion with reviewers.
Decision: Accept (spotlight)