Meta-Learning with Neural Bandit Scheduler
Authors: Yunzhe Qi
Yikun Ban
Tianxin Wei
Jiaru Zou
Huaxiu Yao
Jingrui He
Venue: NeurIPS 2023 poster (2023)
Keywords: Meta Learning
Contextual Bandits

Abstract: Meta-learning has been proven an effective learning paradigm for training machine learning models with good generalization ability. Apart from the common practice of uniformly sampling the meta-training tasks, existing methods working on task scheduling strategies are mainly based on pre-defined sampling protocols or the assumed task-model correlations, and greedily make scheduling decisions, which can lead to sub-optimal performance bottlenecks of the meta-model. In this paper, we propose a novel task scheduling framework under Contextual Bandits settings, named BASS, which directly optimizes the task scheduling strategy based on the status of the meta-model. By balancing the exploitation and exploration in meta-learning task scheduling, BASS can help tackle the challenge of limited knowledge about the task distribution during the early stage of meta-training, while simultaneously exploring potential benefits for forthcoming meta-training iterations through an adaptive exploration strategy. Theoretical analysis and extensive experiments are presented to show the effectiveness of our proposed framework.

Meta-Learning with Neural Bandit Scheduler
Yunzhe Qi
Yikun Ban"
University of Illinois at Urbana-Champaign
University of Illinois Urbana-Champaiin Champaign, IL yikuub20illingg
Champaign, IL yunzheq20: 1iin0ii edu
Tianxin Wei
Jiaru Zou
University of Illinois at Urbana-Champaign Champaign, IL twei sweil00illiois edu
University of Illinois Urbana- Chaaa-Champaain Champaign, IL jiaruz20iliinois edu
Huaxiu Yao
Jingrui He
University of North Carolina at Chapel Hill Chapel Hill, NC huaxiuEcs. unc edu
University of Illinois at Sibana-Champan Champaign, IL jingrui@illinois.c
Abstract
Meta-learning has been proven an effective learning paradigm for training machine learning models with good generalization ability. Apart from the common practice uniformly sampling the meta-training tasks, existing methods working on task scheduling strategies mainly based on pre-defined sampling protocols the assumed task-model correlations, and greedily make scheduling decisions, which can lead sub-optimal performance bottlenecks of the meta-model. In this paper, we propose a novel task scheduling framework under Contextual Bandits settings, named BASS, which directly optimizes the task scheduling strategy based the status of the meta-model. By balancing the exploitation and exploration in meta- learning task scheduling, BASS can help tackle the challenge limited knowledge about the task distribution during the early stage of meta- veta-training, while simultane- ously exploring potential benefits for forthcoming meta artt-training iterations through an adaptive exploration strategy. Theoretical analysis and extensive experiments are presented to show the effectiveness of our proposed framework.
Introduction
Meta-learning algorithms [19 have been receiving increased attention due to their strong general- ization performance across wide range of tasks 332 20) Most existing meta-learning methods often assume a uniform distribution when drawing meta- tetta-traiiing tasks, treating each task as equally important [19]. However, this assumption can possibly fail in real-world scenarios. For example, during data collection, candidate training tasks can be subject to noise perturbation, leading to perfor- mance bottlenecks in the meta-model if noisy and clean tasks are treated an equal footing 43 45 In addition, some tasks can pose greater challenges for the meta- meta-model to adapt to, necessitating a more flexible allocation of computational resources during the meta-tran meta-training process. Furthermore, the task distribution may be skewed, with "tail" tasks receiving inadequate attention under uniform have been proposed for
sampling. As result, the task scheduling methods [14 51 31 refined meta-training strategy.
24
29
Equual Contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Existing scheduling approaches mainly aim to improve meta-training strategies based on various pre-defined eri- teria and assumptions, including both non-adaptive and adaptive methods. Among them, non-adaptive methods working on the gradient that updates trainable parameters [3 have proven their superiority over meta-training methods with uniform sampling. But they are unable to adjust the task scheduling strategy adaptively based on the status of the meta-moded On the other hand, adaptive meth- ods aim to schedule the tasks based on Curriculum Learning [4 (2 [50] adaptively sample the tasks based the task adaptation difficulty (loss) [51]. However, the existing approaches all greedy algorithms, which means that they tend to make locally optimal decisions based on the current knowledge (i.e., exploitation only). As the learner only has limited knowledge regarding the task and data distribution the early stage of meta-training, the greedy strategy can lead to the sub-optimal meta-model due to multiple reasons, such as being misled by the noisy tasks or affected by the skewness of the task distribution. Here, we use Figure to illustrate an example where the greedy approach (only exploitation) may be trapped in sub- sub-optimal solutions.
Meta learner:
+
Tesk-learner:
Meta-Searning:
Learning/adaptationn:
O
V
0
(e))
VL,
+
R
VL3
θ
0
0,
VL
VL4
2
0
Exploitation
VS.
Exploration
iteration Exploitation and exploration in meta-training [K]. E.g.. tasks 2, 3 are "frequent" tasks in skewed task distribution, and tasks 4, 5, are from task distribution "tail". Exploring the "tail" tasks help improve the meta-model generalization performance (Subsec. (.2).
Figure I:
One intuitive solution for the aforementioned problems is tackling the exploitation-exploraee dilemma [4] in meta-training process: balancing the exploitation of current knowledge of selected tasks, and the exploration of under-explored tasks for potential long-term benefits. Therefore, unlike existing approaches with greedy strategies, we propose a novel task scheduling framework under the Contextual Bandits settings [15] 28
53 21. named BAndit TaSk Scheduler (BASS). In each meta-training iteration, we formulate each candidate meta-training task as an arm under the contextual bandit settings, and the corresponding arm reward will naturally be the meta-model generalization ability score after including this candidate task (arm) into the meta-tran meta-training process. To achieve this objective, BASS directly learns the mapping from the meta- parametersss to the meta-model generalization ability score, instead of depending on the hand-crafted criteria or assumptions. This design also enables us to update meta-parameters and BASS simultancously within one round of metaaoptimizztionn In particular, instead of greedily scheduling the meta-training tasks solely based on the current knowledge (i.e., exploitation), BASS leverages an additional adaptive exploration module with two different exploration objectives to explore for unrevealed benefits. Our main contributions can be summarized as follows:
[Problem and Proposed Framework] We are the first to formulate the meta-learning task schedul- ing problem under the Contextual Bandits settings, where we optimize the meta-model model w.r.t. chosen task batches in each meta-traing meta-training iteration. To tackle this problem, we propose a novel bandit- based meta- meta-learning task scheduling framework named BASS, which is model-agnostic and can be applied to various meta-learning frameworks. Different from existing works, BASS directly learns the relationship between the meta-model parameters and the meta-model generalization ability. In addition, instead of greedily exploiting the current knowledge as in existing works, BASS utilizes a novel exploration module to adaptively plan for the future meta-training iterations.
[Theoretical Analysis] Under the general meta-learning settings as well as standard assumptions of over-parameterized neural networks and neural bandits, we derive the theoretical performance guarantee for the proposed BASS framework in terms of regret bound.
[Experiments] To demonstrate the effectiveness of BASS, we compare our method against seven strong baselines on three real data sets, with different specifications. In addition, complementary experiments as well as case study on Ensemble Inference are also provided to better understand the property and behavior of BASS.
2 Related Works
In this section, we briefly review the related works of our proposed BASS framework from the aspects of task scheduling in meta- meta-learning and contextual Bandits.

---

Task Scheduling in Meta-Learning. By considering each meta- veea-traininng task to be equally important, many existing works sample the training tasks uniformly from the given task distribution [9 40]. Then, with fixed sampling strategies, [24 propose to assign the task sampling probability based on the quantity of task information, and 31 utilizes a probabilistic sampling method based on
35
class-pairs. Meanwhile, there are also works try to improve task- gradients for the randomly
sampled tasks [3 34]. On the other hand, Burriculum-basee approaches [44 [22 50] schedule the
tasks based on the difficulty of task adaptation, and (51] propose to adaptively schedule the tasks based on the assumed correlation between the difficulty of meta-training tasks and the meta-model generalization ability. However, the existing works are all greedy approaches that solely focus on the instant benefits, which can lead to sub-optimal meta- redalsodeels due to the potential performance bottleneck. Compared with existing works, our proposed BASS directly learns the mapping from the meta-parameters to the generalization loss with no pre-defined criteria. With the adaptive exploration strategy, our proposed BASS helps tackle the insufficient knowledge regarding the task distribution by balancing the exploitation and exploration, as well as focusing on the long-term effects.
Contextual Bandits. Contextual bandits algorithms aim to solve the sequential decision making problem under the online learning settings, such as online recommendation [28 49 6.. Assuming that the mapping from arm contexts to rewards is linear, linear upper confidence bound (UCB)
algorithms [15] 28 4] are proposed to solve the sxploitation-epporatiio dilemma. After kernel-based
methods [46 17 being applied to deal with the non-linear setting where the reward mapping is
assumed to be a function in Reproducing Kernel Hilbert Space (RKHS), neural bandit algorithms
53 7 5 39 g are proposed to utilize neural networks for the reward and confidence bound estimation. In particular, neural handit algorithms have demonstrated their superior performance over linear and kernel- algorithms (54), thanks the representation power of neural networks. Moreover, instead of using non-negative UCB, EE-Net 9 10 achieves adaptive exploration by adopting an additional neural network estimate the potential gain of reward estimations. In this paper, we model the task scheduling problem under the Contextual Bandit settings to balance the exploitation and exploration dilemma regarding the meta-task scheduling.
[54
3 Problem Definition and Learning Objective
Under the settings of few-shot supervised meta-lcarning 19] our goal is to train a meta-model O): with parameters O E IR that can generalize well to meta-testing tasks, where p is the number of trainable peta--aaaamtter. The meta-model parameters are initialized as ( Note that in this work, the trainable parameters are all represented by column vectors, for the simplicity of notation. Following similar settings in [99 [T], in each training iteration E [K], we will receive a
pool of candidate training tasks 2 [Te. where its cardinality | Nusk and the index set A = .ussk) Given a task distribution P(T), we draw each candidate task T from P(T) to form the candidate pool, i..., Tk,s ~ P(T). Each task Te. is also associated with support data set Di, and a query data set D where the samples (including their labels) of D Di, are drawn from the corresponding task data distribution DT.,, of task Tr.
Meta Meta-training Process. Then, need to choose a batch of B tasks S2 (TR,iiiEN, 2 for
each meta- veta-training iteration & E [K], where Ni C C refers to the indices of chosen tasks. With O (k-1) being the meta-model parameters after completing the (k - 1)-th meta-training iteration, for each chosen meta- meta- training task Tr.3. ā E Ni, we run Gradient Descent (GD) for J steps on its support
set D to obtain the task-specific parameters (J) This refers to the inner-loop optimization. In k,7 this work, we consider a loss function C(;--) that maps the meta-model parameters and the input sample (or sample set) to the loss value, with the range [0, (e.g., the MSE loss on normalized user (0) =0 (K-1) in meta-training iteration k, each GD step is represented as k
A.7
ratings (27) Denoting
(i) = 0 1) k.7
A. m VoL(Di
Vj E [J]
A.7:
where 7h E R$ is the learning rate of GD. For the simplicity of notation, we formulate the above J-iteration inner-loop optimization as operator I(.,.) T x O + O such that
I[Tg3 e (k- ()).
(2)
k
3

---

Meto-Troining with 92
Parameter Update for BASS Meto-model
TTa
Chosen
Task
Arm Reward Est. Fxr
into
Meta-model Fecpliiity
tasks f4
Select Arms Benefit Scores Fu.
Explatationn O
Sample Candidate Tosks Tbokk
8/h-1
BASS
Gurrent Meta paramsters
Arm (task)
2OCO COC
Exploration Score Est.
Contexts
Candidate Arn Plol
Explonation Fa()
Task Dist. P(T)
1. Arm. (Tesk) Context Derivation
Reward & Exploration Score Estimation
Arm Selection
Figure 2: In meta-training iteration k E [K], the BASS framework overview. We only need one round of the optimization process (LHS of the figure) update the meta-model and BASS.
Then, we optimize the meta meta-parameter through the outer-loop optimization with query sets
( [ = (k-1)) - 722 Vel
Σ
C(D
SR
(3)
where 7/2 E R+ the learning rate. Here, the trained meta-model parameters ( expected to minimize the generalization loss (TTPPTT), (x;; I(T, ())]) where we let Dy being the associated data distribution of task T.
Evaluating Task Batch Benefits. Recall that in meta-training iteration [K], the meta-model will be updated based on the chosen batch of B tasks (Eq. B), and we will need to evaluate the benefit in terms of the whole task batch. By the task scheduling problem definition, the learner will
select one task batch 24 C 1 based on its strategy, and the chosen task batch Qz will be used for eata-training in this iteration k. Here, we define the reward of the corresponding task batch f2 as
o (K-1))22)
I(T, e (k-1) BT- (((-)))))
(4)
where @ (k-1)(((a)) refer to the meta perameerrsss after adapting e (k-1) 1) to task batch S4 based on Eq. 3 For simplicity, we let h R which maps the trained meta model parameters e (k [[2]] to task batch rewards.
be the mapping function conditioned on distribution P(T).
Learning Objective. Up to meta-training iteration k, we have ((*(K) {Si.... ......... 2ik} be- ing series of unknown optimal task batches that minimizes the generalization loss. Each opti- mal batch is 22 = (T&,s brev C [(k) k E [K] including a total of |S2]] = B tasks, with indices Ng C N. The corresponding optimal meta-parameters are defined as (K),
arg infeew E TTTP(T)) I(T,
where W C RRP refers the reachable param-
eter space, which contains the possible trained meta-parameter values, after observing the available candidate tasks {D($) 1, k e [K] and the randomly initialized meta-parameters (0), Meanwhile, denoting our selection of the meta-training task batches as Ω(K)) = {Ω),.... 92 }. we will have the corresponding trained meta pettaparaseteess (K), Here, define the K -iiteration regret as
R(K) ET~P(TT [(x:I(T, L(=; (() ((K).)))
(5)
which measures the difference of the generalization ability between the trained meta-parameters (K) and the optimal meta-parameters @ (K).+ after K meta-training iterations.
4 Proposed Framework: BASS
In this section, we introduce proposed BASS framework, which simultaneously optimizes the meta-model and the task scheduling strategy on the fly. The pseudo-code presented Algo. [ and the illustration for each meta-training iteration & [K] is shown in Figure 2

---

Algorithm BAndit TaSk Scheduler (BASS)
1: Input: Task distribution P(T). Iterations K. GD steps J. Number of chosen tasks B. Learning
rates for meta-model 171. 7/2. Learning rates for BASS nf n2. Exploration coefficient E (].
2: Output: Trained meta-parameters (
3: Initialization: Randomly initialized meta-model parameters (()), and BASS parameters (())
4: for each meta-training iteration lo E [K] do
5: Sample pool of Nusk candidate meta- meta-training training tasks S from the task distribution P(T).
>
Task Scheduling
6: for For each candidate task Th.; E (44 do
7: Derive two arm context vectors Xk. Xki [Eq. 6
8: Calculate arm benefit score Sk,i a fi(:: (1th
f with BASS. [Eq.
9:
end for From (2A) choose the top-B tasks Q2 C 12th) with the highest scores F lask?
D
Parameter Updating
for each chosen training task TA, E Ω4 do
12: Derive the corresponding rewards T and exploration score ē [Eq. 8
13:
end for
14: Update meta- mota--arrametes to (k) based on chosen arms (tasks) Tg, Ωz. [Remark
Eq.
Update BASS parameters to ((k) with chosen arms. [Eq. Subsec. 4.4
15:
16:
end for
Remark 1 (Task Scheduling with Contextual Bandits). By the problem definition, there Nbatch (Nmat) candidate task batches in each meta-training iteration, which can be large number. In this case, enumerating all possible task batches and estimating their rewards will be time consuming. Therefore. under the Contextual Bandits settings, BASS alternatively considers each candidate task
TK,s E 12 as an arm, and directly chooses arms as the meta-training tasks Q4 C $2/1)) As result, BASS can (1) reduce the arm space size from ((N to O while (2) enjoy the performance guarantee (Section) 5) in terms of regret bound (Eq. 5).
Section Outline. Here, we will first present our definition of the arm contexts (Subsec. 4.1
whose formulation is challenging, because our settings are different from conventional Contextual Bandits where arm contexts are readily available from the environment. Then, applying two neural networks f1. fa for exploitation and exploration respectively, we formulate the arm benefit score (Subsec. 4.2 which measures the benefit if we include the corresponding arm (task) into the current meta-tramin metainraining process. Next, we define the arm rewards and exploration scores as the labels for training Si, /2 respectively. In particular, to deal with the challenge of achieving exploration in task scheduling, we incorporate the information and the dynamics w.r.t. meta-optimizations, and formulate two separate exploration objectives for refined exploration strategy (Subsec. 4.3) Finally, we update BASS with GD (Subsec. 4..4. and train the meta-model with chosen tasks.
4.1 Formulating Arm Contexts
To encode the information from both the task side and the meta-model side, for each candidate task (i.e., arm) T E 52 in meta-training iteration &: E [K]. we formulate its arm contexts as the meta-parameters after task adaptations, denoted by
X = 0 I[Th., Olk
x², == e (k" [Tx..]
(k- VeL(D) ki ( (6)
where θ (J) the task-specific parameters after adapting meta-parameten (k-1) 1) to task Tx.s with
inner-loop optimization (Eqs. 2 while (k-1) [Tx.e] refer to the meta-parameters after adapting the current (k-1) to task Te.ss with both inner-loop and outer-loop optimization (as in Eq. 3) In particular, we assign each arm Te, with two different arm contexts to model the dynamics of meta-parameters w.r.t. inner-loop optimization and outer-loop optimization respectively. the variance of the corresponding data distribution DT., can be high. In this case, the support set Di and the query set D will be considerably different, which tends to make the corresponding
example,
5

---

arm contexts x X divergent. As a result, the gradient vectors Vefi(xi.)). Vofi(xE.) .) will likely be distinct from each other. Alternatielyy, if the support set Di, and the query Di, not significantly distinct (the distance between X and X is also likely to be relatively small), these two gradient vectors tend to change dramatically when adapting to Tk. The reason is possibly that the exploitation model fi is not well adapted to this task T For both scenarios above, it can be beneficial to include more exploration for the task Tk. and the target helping fi better learn the reward for this task by actively acquiring the knowledge of it. And the two formulated arm contexts can provide important reference for our exploration module.
Remark 2 (Recycling Arm Contexts), In order to derive the arm contexts (Eq. 6. the gradients for the outer-loop optimization VeL(Di 1, No of the chosen arms Tx. Qk are calculated. As a result, these gradients can be recycled to update the meta- meta-model parameters based on Eq. 3 (line 15, Algo. D. which helps reduce the compulational cost when updating the mela-model.
k. f.
4.2 Estimating Benefit Scores for Tasks
To determine which arms (tasks) should be included to the meta-training iteration k; we formulate
the arm benefit score estimation for each candidate arm Tk. ( The estimated benefit score consists of two parts: (1) the estimated arm reward of choosing this task based on existing knowledge (i.e., exploitation); (2) and the exploration score for the future potential benefit (i.e., exploration). Inspired by recent advances in neural bandits [9] we introduce two separate neural networks, (= and f2(5; 02). to estimate the arm reward and exploration score respectively. The exploitation network f)):0,) aims to learn the mapping h(-) from arm contexts (i.e., meta- patttmeerrrmesss) to rewards, while the exploration network f: 02) aims to learn the uncertainty of reward estimations the exploration criterion. Different from conventional bandit models, c.g. [9]. that works on static arm contexts given by the environment, our design alternatively leverages the evolving information from both the task (arm) side and meta-paraman parameters side, across meta-training iterations. In addition, we consider the dynamics of cettaattimizaiinns for more comprehensive modeling of the exploration aspect, and
the details will be introduced later. Here, given a candidate arm Tk, E (k) its estimated benefit score k is formulated as
k Fk.i + ετ,i a 0 fa (Vo Vofi(x..)l
where E (0, 1] is the exploration coefficient to balance exploitation and exploration. Notice that f2 02) will take the concatenated gradient of fi(:;) w.r.t. both arm contexts Xi. xi. as the input, represented by [Vefi
fi (x2. .)1- And the output will be the exploration score estimation é To obtain Voli (2/i(x we also calculate fi fx(X 01) and run the back-propagation. Afterwards, choose the top-B B arms with the highest estimated benefit scores šn,,, i e N, as the
chosen task batch 24 C (2) (line 10, Algo. D.
Design Intuition. First, recent advances of neural Contextual Bandits 55
9 38
have shown
that the uncertainty of reward estimations directly related to the gradients of the estimation model. Therefore, we leverage exploration module fz(:; 02) to directly learn this unknown relationship. Second, since Di, are from the same data distribution DT... if these two gradients Feff(xxi.)) Vefi (x1,) are distinct, the reason can be: (1) the variance of the data distribution Dr., is high (due to the potentially noisy or difficult task); or (2) the gradients of (-; 01) tend to change significantly when adapting to task Te., In both cases, it can be harder for fi 01) to accurately predict the arm reward Tk.., and the meta- meta-model can fail to properly adapt the task Tk. In this case, we apply the concatenated gradients w.r.t. both arm contexts as the input of fz in order to provide the information for fz(:: 02) evaluate exploration scores.
Network Architecture and Parameter Initialization. Here, we consider (1), f2(:: 02) to be
two L-layer fully-connected (FC) networks with network width m. while 0 = (0,, 02) refer to
their trainable parameters. For their randomly initialized parameters g = (0) (()) the weight
matrix entries for the first I. T-1 1 layers are drawn from the Gaussian distribution (0, //m,, while the entries of the last layer ( (I-thh layer) are sampled from N 1 1/m).
Remark 3 (Reducing Input Complexity). The input of f1)::1)) is the arm context Xh. whose dimensionality is the number of meta parameersssssrss p. A similar situation also exists for the exploration

---

network f2(:;2). Inspired by the idea of learning dense low now-dimensional representations with Convolutional Neural Networks (CNNs) (e.g.. (441), we apply the average pooling approach to approximate original inputs for reducing the running time and space complexity in practice. To show its effectiveness, we will apply this approach on BASS for all the experiments Section
4.3 Formulating Arm Rewards and Exploration Scores
Different from the conventional neural bandit algorithms [53
where the reward is provided by
the environment oracle, we need to carefully design the arm rewards to reflect the arm benefit in terms
of the meta-model's generalization ability. Analogous to task batch rewards (Eq. 4 we formulate the
single arm reward a h( ((@)(-1) [Tx,,))
-T-P(T) [<( O ((-1110 (Tx,,))) for
arm Tk. Since it is impractical to calculate the arm reward by enumerating over P(T), sample
batch of validation tasks Sppalid to derive the unbiased reward approximation, denoted by
Σ I(D
O (T.,))
Tk
(8)
Here, we adopt the single-step inner-loop optimization
19 40 to derive I(T O (k-1) (T..)) in Eq.
[ in order to save the computational cost in practice. Under the few-shot settings, the computation of arm rewards is efficient, since the support set is generally small for inner-loop optimization. The approximation error here can be bounded by the concentration inequality, as the validation tasks Dalld are sampled from P(T)-
On the other hand, to formulate the exploration score ex,, (i.c., the label for f2(: 02)), we consider two separate exploration objectives: (I) the prediction uncertainty for the exploitation module fi(;01) 01), which is TR,: - fi (Xl,,5 01): (2) the validation loss of the meta-model, which represents the difficulty of adapting to Te inspired by the "task difficulty measurer" in Curriculum Learning
52 50]. As result, with Lr C(D) O ( being the validation loss of arm Tk we formulate
a1) a) Lx Analogously, with the approximated reward FRi (Eq. 8), we calculate the exploration score approximation by 1)) + (1 (1--a) a) Lx
the exploration score as GK₁ = (rk. fx 0 0)* +1--a)
Êk = a (Fi,s fi fi
Here, the exploration coefficient E (0, (in Eq. 7 is also used to balance our two exploration objectives, which are (1) prediction uncertainty Tk f-(::1): if the exploitation model fi 01) under-estimating the arm reward, leading to the positive residual rk fi 01). will have high exploration score to enhance the exploration for this arm; otherwise. when Tk,s - fi(:; is negative, it indicates excessively high estimation, which will alternatively lower the exploration score to compensate for the ever-estimation. With a higher a value, our exploration strategy will focus more the behavior of the exploitation model fi f:))): (2) the difficulty of task adaptation (i.e., validation loss) L : the current meta- model does not generalize well to arm T2 the validation loss La, will be high, which will also lead high exploration score. In this way, our formulation considers two different exploration objectives as well as the dynamics of meta-optimizations (base on concatenated network gradients), for refined exploration strategy.
4.4 Updating Bandit Scheduler Parameters
After updating the meta perameersssssss (Line 14, Algo. Remark 2 with tasks 2 = (Tr we proceed to update the parameters of BASS (Line 15, Algo. []. Recall that fi (1) tries to learn the reward mapping function ht()), and fz(; 02) aims to learn the exploration score. Given the selected arms QR with vf v2 E R+ being the learning rates, we apply the GD and quadratic loss to update the
parameters of BASS, denoted by ((*) 0f* 11) of Vo, t ET_ En [x((X k, 0(*-11) -
0 0 1-) 2 Va, ( Σx, =E, sn, [ (x ( Vosi (): 01 - - 19. We refer Eqs. for calculating the approximated arm reward " and exploration score "
Theoretical Analysis
Recall that in each iteration l E [K], we receive candidate arms (tasks) (2(+)) = (TE,)iEN and each arm Tk. is associated with two context vectors Xf, XL.- For the sake of analysis, we normalize these
7

---

two contexts such that Ix ll22 = Ix 1, and set the exploration coefficient a = 1. Following the existing work [47 48]. we let the meta-model F(:; ) be a Læ-layer FC network with Gaussian Initialization, with the network width m.. Note that our results can also be generalized to other network architectures, such CNN and ResNet [22], based on the analysis of over-parametterized neural networks [11 [8,33. For the theoretical analysis, we adopt Sigmoid activation for fı and ReLU for f2, in order to make fi Lipschitz smooth under over- pver-parameterrzzatonn settings. Then, we draw
trained parameters of BASS with {0 . (0()) 00 TrE Here, starting from the randomly
initialized parameters (0 ) each parameter pair {0)
(T)
02 J,T E [K] is separately trained 0(-)),
on past arm rewards (r ) MEE.,,,EN. and exploration scores () "'EE,,,,E, with Jg-iteration GD. Next, similar to existing neural bandit works (e.g., (54 9 53) and the works on meta-model convergence analysis (e.g., 47 (8),, we have the following separateness assumption.
Assumption 5.1 (p- Se-pepaattenesss.. After K meta mheinng iterations, for every pair of arm contexts X4. Xke with k. k' E [K] such that the corresponding arms Tk, E Og Tw E Say, if (k. +
(K', f'), we have l1x2, .l2 2 where 0 < p S (
The assumption above is mild because of two main reasons: (1) since L is manually chosen (e.g.. L = 2). we can easily satisfy the condition < p S O(2)) as long as no two arm contexts are identical; (2) since the meta parameerrsssssss (*),, k E [K] are constantly changing, the corresponding arm contexts will also be distinct across different meta-training iterations. Additional discussions on this assumption are in Appendix Section B With standard settings of over- par-matammtteeedd neural networks 47 1 and the definition of regret R(K) in Eq.[5)
we have the following Theorem 5.2 max E2).
Theorem 5.2. Define
E E(0,1). 0 < E1 S O(IKK), E, (ce) Suppose the network width m Z (Poly((K, L, Niask P 1 log(1/0)); m 2 [((Poly(K, LF,, Nuus)) (lok))log(1//)). Then, let the learning . = O (Poll K.oKKNNww
P S O(/LL), Cg > 0, 77
p-m-! rates be Th; 1/2 = O Poty(K N L.) ); nh ni 0 Potyl K
MNa.. J.
Naaill -log( (t).
pist
Following Algo.
with probability at least 1 8, the K K-round R(K) of BASS could be bounded by
R(K) S o
1
(V
(v
2E,
3L.
+(1 (1+ (1--20 (1+2%)) 2 log(K/ O
S KJBBBTT )+ +im (10)
VK
V2
VIFF
where Tm = 0( m 1/04 ), > 1, and m (1) with sufficient network width of BASS.
1
The proof is presented in Appendix Section D Here, the first term on the RHS is scaled by the 1/VK term, which means the regret bound will shrink along with more iterations K. The second term on the RHS is scaled by m/ym which makes it diminutive term under the over-parameterization settings. Since the network depth L of BASS is a small integer (we apply L = 2 for experiments in Section O). EL will also be relatively small constant. Meanwhile, Ym will also decrease significantly with increasingly large network width m of BASS, In contrast, with a convex loss function (e.g., L2 loss or cross-entropy loss) and the same prrerrraramttiiiatioon settings, the regret upper bound of the uniform sampling strategy 19 40 can possibly scale up to for the worst-case scenario, and the upper bound will not decrease with more iterations K (Appendix Lemma D.13 Alternatively, BASS works under the bandit settings, by directly measuring the meta-model performance difference w.r.t. the chosen task batch and the optimal one. With more iterations K, BASS tends to make more accurate scheduling decisions, which makes our regret bound possible. For the existing works, [51] prove that they can improve the optimization landscape with the assumed correlation of task difficulties and meta-model generalization ability. [3] show that their self-paced strategy can improve the model robustness when facing noisy training tasks. Different from previous works, we provide the performance guarantee for the proposed BASS under the neural bandit framework.
6 Experiments
In this section, we compare BASS against seven strong baselines, including: (1) Uniform Sampling: non-adaptive self-paced methods and task schedulers (2) SPL [26]. (3) Focal-Loss (FOCAL) (30] (4) DAMI. (29. (5) GCP BI) (6) PAMI. (24; and the adaptive task scheduler (7) ATS (5I) Since GCP is not originally compatible with our problem settings and can only work with classification
8

---

problems, we properly adapt it by choosing the tasks with the highest probabilities, and apply it on the classification data sets. ANIL 40 adopted as the backbone meta-learning framework. Due to page limit, we include the complementary experiments (e.g., parameter study for effects of different levels of task skewness), and the configurations to Appendix Section
6.1 Real Data Sets with Noisy Meta-Trainine Tasks
We adopt Drug [6.. Mini-ImageNet (M-ImageNet) 42 and CIFAR-100 (CIFAR) [25] data sets under the few-shot learning scenario. Similar [51, apply classification accuracy the evaluation criterion for the Mini- Imai-ImaeeNet and CIFAR-I00 100 data sets, and consider the squared Pearson coefficient for the Drug data set. For each meta-learning iteration A E [K]. the learner is
given a candidate pool of 10 tasks (i.e., (k) = Nusk = 10), and it will need to choose batch of B 2 tasks as the training tasks 02g for this iteration. For the Mini-ImageNee and CIFAR-100 data sets, we consider half of the meta- teat-ttaiining tasks are perturbed by the label flipping noise (2]. where the chance of label being flipped is [0, 1]. As the Drug data set stands for regression problem, we draw the label noise from the Gaussian distribution N(0,, c²). The experimental settings are under 1-shot 5-shot, Way (for classification data sets) learning scenario with the noise level c= 0.5. The experiment results are shown in Table and Figure 3 For the average ranking column, we exclude results from the M-ImageNet (1) setting, since BASS and the baselines tend to train a meta-model performing "random guessing". More discussions are in the next paragraph.
Table 1: Results on real data sets [data set (shot); results + standard deviation]. For 1-shot M- ImageNer, all the methods end up with an invalid meta-model performing "random guessing".
Algo. \Data
Drug (1)
Drug (5)
M-ImageNet (1)
M-ImageNet (5)
CIFAR (I)
CIFAR (5)
Arg. Rank
Uniform
0.210:0.013
0,220
0.201 002
0.234=0.029 0.0025
0.526=0.011
4.4
SPL
0.244100.008
0.236:10.004
0.203:10.002
0,240:0.018
0.200=0.002
0.367=0.039
5.0
FOCAL
0.222::00024
0.223:1.000
0,2001:0.0 000
0.31610.029
0.231=0.024
0.485-0.006
4.4
DAML
0.146:00.099
0.177:10.003
0.201 00/
0.31010.016
0.247=0.003
0.41410.025
5.4
GCP
N/A
N/A
0,201 001
0,282=00011
0,243-0.007
0.508=00009
6.0
PAML
0.192::.020
0,205 009
0.1991:0.00 001
0.218:100013
0.199=0.004
0.316:10022
7.2
ATS
0.230:0.002
0.237-+00014
0.201
0.334=0.053
0.257=0.048
0.515-00015
2.4
BASS
0.242:10012
0.245:10.006
0.198:100004
0.351
0.272-0.025
0,553
1.2
Here, BASS can generally outperform the baselines by directly learning the mapping from the meta- parameters to the rewards, as well as balancing the exploitation and exploration. ATS also achieves good performance as it adaptively learns the correla- tion between the task adaptation difficulty and task scheduling, which proves that it necessary to apply the adaptive scheduling strategy instead of staying with fixed protocol. Meanwhile, BASS can gener- ally train the meta-model more efficiently (Figure 3 leading to good performances at the early stage of
M-ImagoNet (S-i y: 0.3)
CFAI (5-ahtt e: 0.3)
0.25
0.32
0.30
Ap
1:53
3.6
424
3.2
0.25
100AL L100
22003
2040
2003
23003
20300
Figure 3: Accuracy results (5-shot, O.5), BASS achieve good performance at early meta-training stage.
meta-training. In particular, for the Mini-ImageNe data set under the 1-shot, 5-way settings, all the algorithms fail to train an effective meta-moda Here, under the 5-way classification scenario, all the methods will likely generate a meta-model performing "random guessing" (around 20% accuracy). In this case, utilizing Ensemble Inference techniques [2]66] can help alleviate this problem, and we include further discussion in the case study (Subsec. 6.3
6.2 Effects of the Skewed Task Distribution
The skewed task distribution P(T) commonly exists in real-word cases.
Table 2: CIFAR-100 100 with skewed task distribution (5-shot, 5-way/ 10-way).
Data Algo.
Uniform
SPL
ATS
BASS
For instance, consider an animal im-
5-way
0.375+0.009 0.26410.044
0.279=0.002
0,382-10.007
0.408-10.008
age classification data set where each
10-way
0.065 0.283:1.0339
0.320:10.021
class (i.e., task) corresponds to one kind of animals. In this case, felid classes can be considered "frequent" tasks in the task distri-
bution due to their large quantity and strong mutual correlations, compared with "tail" tasks like
kangaroo classes. In this case, paying insufficient attention to the "tail" classes can impair the

---

generalization performance of the trained meta-modes Thus, to investigate the effects of when the task distribution P(T) is skewed, we randomly choose some tasks from P(T), and assign them with higher sampling probabilities (weights). This corresponds to the situation when P(T) is skewed, so that sampling from P(T) will likely lead to similar tasks. Here, with the CIFAR-100 data set, we sample 10 tasks and assign them with higher sampling probabilities (weights) (5 tasks with 10%, 5 tasks with 5%), while the rest of the tasks equally share the remaining 25 probability.
acsodi www.e-rranneeee tests (Swwe)
Accuresy far altara 12C-nay)
From Table our proposed BASS maintains the best performance due its adaptive scheduling strategy and the ability of balancing exploitation and explo- ration. On the other hand, the baselines are unable to adjust their meta-training strategies towards explo- ration, when the meta- model has already well adapted to the "frequent" tasks. This can possibly lead to the sub-optimal performance of the meta-model. ticular, based on Figure when facing a skewed task distribution, BASS can actively explore the "tail" tasks, after sufficiently exploring the "frequent" tasks. BASS is also able to achieve good performances with fewer meta- meta-trainin training iterations.
Explorin
acow
Darge meg Towks
25.0
Farmitore
BASS
ATS
par-
unifom
Figure 4: Average weights of chosen meta-training tasks. The testing accuracy vs. iterations needed. BASS actively explor- ing for "tail" tasks, and requires much fewer iterations for the same performance (as fow as ~ 1/3 of baselines' iscrations).
6.3 Case Study: BASS-aided Ensemble Inference
From Figure we notice that BASS can train a meta- metal that achieves good generalization performance at the early stage of meta-training. One application of this property is using BASS to assist meta-learning models under the Ensemble Inference settings, where separate models are combined to enhance the generalization ability. One renowned ensemble approach is the model- parameter ensemble 41 33 With a collection of NE individual models (F(:; (i)liE(Na) of the
same architecture, the ensemble model will be FE(-; θg), and its parameters θ = NE Exe[Ne] O; the averaged parameters across individual models. Then, the ensemble model FE(: +&) will be applied as the inference model for downstream problems. Here, one natural way of obtaining the individual models [(; + i E [Ng]] is deeming the models from different training iterations as the individual models for ensemble 112 16). Here, we conduct experiments using the ensemble techniques with individual models F(:: + trained by baselines and BASS. We choose the top Ng = 10 models with the smallest validation loss across different meta-training iterations as the individual models [- he(N)) for ensemble. The results are shown in Table We label the ensemble version of BASS as "BASS-E", and the non- non-ensemble version as "BASS-S".
Compared with the non-ensemble settings [Table we see that the BASS- aided en- semble model can generally perform bet- ter. In particular, the ensemble model can improve the meta-model inference perfor- mance in significantly difficult cases, such the Mini-ImageeNet under the 1-shot set- ting (Subsec. I. As result, BASS can help generate high-quality ensemble model with the mota-models trained in different iterations. While the ensemble inference technique can also benefit the other baselines, BASS still maintains decent performances.
Table 3: Ensemble study [dataset (Shot): results standard devintion).
Alpo. Data
M ImageNeet (1)
Mr (5)
CIFAR
CIFAR (5)
Uniform
0.231=0014
0.313:00:27
0.270=0004
0.544:0.012
SPI.
0.218-0.006
0.298-0.004
0.219-0.05
0333--0.038
POCAL
0.204-00005
0.347=0.030
0:25-00015
0.99=00.00
DAML
0.222-0011
0.326::0.031
0.261=00088
0.422=0.019
GCP
0.206.00.066
0.29710.001
0,268-0019
0.51210.0055
PAML
0.213-00:01
0.252.10.009
0,223-00009
0.336.10.029
ATS
0,202:00002
0.354:20.522
0313=0008]
0.517:00017
BASS-S BASS-E
0.198=00004
0.351=0.012
0.272=0.025
0.553=0.008
0.242:0..04
0.366100003
0.317=00.010
0.551
Conclusion
In this paper, we formulate the task scheduling problem in meta-learning under the Contextual Bandits settings, and propose novel bandit- based task scheduling framework named BASS. It directly optimizes the task sampling strategy based on the status of the meta-model rather than applying fixed task scheduling protocols. Instead of greedily making decisions, BASS can help deal with the insufficient knowledge problem at the early stage of meta-training, as well as plan for the future meta-training iterations with the adaptive exploration strategy. We include both theoretical analyses and comprehensive set of experiments to demonstrate the effectiveness of our proposed framework as well as its key properties.
10

---

Acknowledgments and Disclosure of Funding
This work is supported by National Science Foundation under Award No. IIS-1947203, 119-2117902. IIS-2137468, IIS-2002540, and Agriculture and Food Research Initiative (AFRI) grant no. 2020- 67021e33799/project accession no. no. 1024178 from the USDA National Institute of Food and Agricul- ture. The views and conclusions those of the authors and should not be interpreted representing the official policies of the funding agencies or the government.
References
[1] Yasin Yadkor, Dávid Pál. and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances neural information processing systems, 24:2312-2320, 2011.
[2] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In ICMI, pages 127-135. PMLR, 2013.
[3] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-paramcterization. In International Conference on Machine Learning, pages 242-252. PMLR, 2019.
[4] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235 256, 2002.
[5] Yikun Ban and Jingrui He. Convolutional neural bandit: Provable algorithm for visual-aware advertising. arXiv preprint arXiv:2107.07438. 2021.
[6] Yikun Ban and Jingrui He. Local clustering in contextual multi-armed bandits. Proceedings of the Web Conference 2021, pages 2335-2346, 2021.
[7] Yikun Ban, Jingrui He, and Curtiss B Cook. Multi-facet contextual bandits: A neural network perspective. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 35-45, 2021.
[8] Yikun Ban, Yunzhe Qi, Tianxin Wei, and Jingrui He. Neural collaborative filtering bandits via meta learning. arXiv preprint arXiv: 13395, 2022.
[9] Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. EE-net: aeooiitaiio-exploratttt neural networks in contextual bandits. In International Conference Learning Representations, 2022.
[10] Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. Neural exploitation and exploration of contextual bandits. arXiv preprint arXiv:2305.03784 2023.
[11] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in Neural Information Processing Systems, 32: 11110083188866 2019.
[12] Junbum Cha, Sanghyuk Chun, Kyungjae Lee, Han-Cheol Cho, Seunghyun Park, Yunsung Lee, and Sungrae Park. Swad: Domain generalization by seeking flat minima. Advances in Neural Information Processing Systems, 34:22405-22418, 2021.
[13] Dong Chen, Lingfei Wu, Siliang Tang, Xiao Yun, Bo Long, and Yueting Zhuang. Robust meta- learning with sampling noise and label noise via eigen-reptile. arXiv preprint arXiv:2006.01944, 2022.
[14] Yudong Chen, Xin Wang, Miao Fan, Jizhou Huang, Shengwen Yang, and Wenwu Zhu. Curricu- lum meta-learning for next poi recommendation. Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, pages 2692-2702, 2021.
[15] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In AISTATS, pages 208-28 208-214, 2011.

---

[16] Xu Chu, Yujie Jin, Wenwu Zhu, Yasha Wang, Xin Wang, Shanghang Zhang, and Hong Mei. Dna: Domain generalization with diversified neural averaging. In International Conference on Machine Learning, pages 4010-4034. PMLR, 2022.
[17] Aniket Anand Deshmukh, Urun Dogan, and Clay Scott. Multi-task learning for contextual bandits. In NeurlPS, pages 4848 4856, 2017.
[18] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pages 1675-1685. PMIR, 2019.
[19] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. In International conference on machine learning, pages 1126-1135. PMLR, 2017.
[20] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference on Machine Learning, pages 1568-1577. PMLR, 2018.
[21] B Han, Q Yao, X Yu, G Niu, M Xu, W Hu, I Tsang, and M Sugiyama. Robust training of deep neural networks with extremely noisy labels. In Thirty-fourth Conference on Neural Information Processing Systems (NeurIPS), volume 2, page 4, 2020.
[22] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[23] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemnll: Convergence and generalization in neural networks. arXiv preprint arXiv:1806.07572, 2018. 2018.
[24] Jean Kaddour, Steindór Sæmundsson, al. Probabilistic active meta-learning. Advances in Neural Information Processing Systems, 13-2222,,, 2020.
[25] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[26] M Kumar, Benjamin Packer, and Daphne Koller. Self-paced learning for latent variable models. Advances in neural information processing systems, 23, 2010.
[27] Hoyeop Lee, Jinbae Im, Seongwon Jang, Hyunsouk Cho, and Sehee Chung. Melu: Meta-learned user preference estimator for cold-start recommendation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1073-1082, 2019.
[28] Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual-bandi approach to personalized news article recommendation. In WWW, pages 661-670, 2010.
[29] Xiaomeng Li, Lequan Yu, Yueming Jin, Whig Fu, Lei Xing, and Pheng-Ami Ann Heng. Difficult--wwan meta-learning for rare disease diagnosis. In International Conference on Medical Image Computing and Computer- Assisted Intervention, pages 357-366. Springer, 2020.
[30] Tsung- Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. In Proceedings of the IEEE international conference on computer vision, pages 2980-2998 2988, 2017.
[31] Chenghao Liu, Zhihao Wang. Doyen Sahoo, Yuan Fang, Kun Zhang, and Steven CH Hoi. Adaptive task sampling for meta-learning. European Conference on Computer Vision, pages 752-769. Springer, 2020.
[32] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv:1806.000 09055, 2018.
2018.
12

---

[33] Shiwei Liu, Tianlong Chen, Zahra Atashgahi, Xiaohan Chen, Ghada Sokar, Elena Mocanu, Mykola Pechenizkiy, Zhangyang Wang, and Decebal Constantin Mocanu. Deep ensembling with no overhead for either training or testing: The all-round blessings of dynamic sparsity. arXiv preprint arXiv:2 14568, 2021.
[34] Zhuoqun Liu, Yuankun Jiang, Chenglin Li, Wenrui Dai, Junni Zou, and Hongkai Xiong. Adaptive task sampling and variance reduction for gradient-based meta-learning. 2022.
[35] Ricardo Luna Gutierrez and Matteo Leonetti. cotimattioo--hooretti task selection for meta- reinforcement learning. Advances in Neural Information Processing Systems, 33:20532-20542, 2020.
[36] Eric J Martin, Valery R Polyakov, Xiang- Wei Zhu, Li Tian, Prasenjit Mukherjee, and Xin Liu. All-assay-max2 pqsar: activity predictions as accurate as four-concentration ic50s for 8558 novartis assays, Journal of chemical information and modeling, 59(10)4450-4459, 2019.
Xiang-Wei
[37] Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching for multi-source domain adaptation. Proceedings of the IEEE/CVF international conference computer vixion, pages 1406-1415, 2019.
[38] Yunzhe Qi, Yikun Ban, and Jingrui He. Neural bandit with arm group graph. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 1379-1389, 2022.
[39] Yunzhe Qi, Yikun Ban, and Jingrui He. Graph neural bandits. Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1920-1931, 2023.
[40] Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals. Rapid learning or feature reuse? towards understanding the effectiveness of maml. In International Conference on Learning Representations, 2019.
[41] Alexandre Rame, Matthieu Kirchmeyer, Thibaud Rahier, Alain Rakotomamoniy. Patrick Galli- nari, and Matthieu Cord. Diverse weight averaging for out-of-distribution generalization. arXiv preprint arXiv:2205.09779, 2022.
[42] Sachin Ravi and Hugo Larochelle. Optimization as a model for few-shot learning. 2016.
[43] Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In International conference on machine learning, pages 4334-4343 PMLR, 2018
[44] Yelong Shen, Xiaodong He, Jianfeng Gao, Li Deng, and Grégoire Mesnil. Learning semantic representations using convolutional neural networks for web search. In Proceedings of the 23rd international conference on world wide web, pages 373-374, 2014.
[45] Jun Shu, Qi Xie, Lixuan Yi, Qian Zhao, Sanping Zhou, Zongben Xu, and Deyu Meng. Meta- weight-net: Learning an explicit mapping for sample weighting. Advances in neural information processing systems, 32, 2019.
[46] Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint 1rXiv:130966869 2013.
[47] Haoxiang Wang, Ruoyu Sun, and Bo Li. Global convergence and generalization bound of gradient-based meta-learning with deep neural nets. arXiv preprini arXiv:2006. 1466000006660,,... 2020.
[48] Haoxiang Wang, Yite Wang, Ruoyu Sun, and Bo Li. Global convergence of maml and theory- inspired neural architecture search for few-shot learning. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 9797-9808, June 2022.
[49] Qingyun WU, Huazheng Wang, Quanquan Gu, and Hongning Wang. Contextual bandits in collaborative environment. In SIGIR, pages 529-538, 2016.
13

---

[50] Tongtong Wu, Xuekai Li, Yuan-Fang Li, Gholamreza Haffari, Guilin Qi, Yujin Zhu, and Guoqiang Xu. Curriculum- meta learning for order-robust continual relation extraction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 10363-10369, 2021.
[51] Huaxiu Yao, Yu Wang, Ying Wei, Peilin Zhao, Mehrdad Mahdavi, Defu Lian, and Chelsea Finn. Meta-leaming with an adaptive task scheduler. Advances in Neural Information Processing Systems, 34:7497-7509, 2021.
[52] Ji Zhang, Jingkuan Song, Yazhou Yao, and Lianli Gao. Curriculum-based meta-learning. In Proceedings of the 29th ACM International Conference Multimedia, pages 1838-1846, 2021.
[53] Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. arXiv preprint arXiv:2010.00827, 2020.
[54] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. International Conference on Machine Learning, pages 11492-11502 PMLR, 2020.
14

---

A Appendix: Experiments (Continue)
A.1 Further Details for the Experiment Settings
For the data partitioning, we have the Mini-ImageNet and CIFAR-100) data sets divided into the partitions 64 16 20, which correspond to the training set, validation set and the testing set respectively. Each class is corresponding to a task. Then, for the Drug data set, we partition the tasks into 4100 : 76: : 100 representing the training set, validation set and the testing set.
For our BASS, we apply two 2-layer FC networks for fi 01), f2(:) 02) respectively, and set network width m 200. For deriving approximated arm rewards, we let | = 5. Recall that apply the approximation approach mentioned in Remark 3 to reduce the space complexity and time complexity in practice for the experiments. Here, we tune the pooling step such that the inputs of (=;00))) fi (1; 01) 1 are approximately 50 and 20 respectively. For the learning rate, we find the learning rate for BASS with grid search from (0.01, 00.01,, 0.0001); ). and choose the learning rates for the meta-model 77) = 0.01, 7/2 = 0.001. The meta-model architecture as well as its learning rates will stay the same for all the baselines and our proposed BASS. For the CIFAR- 100 and Mini-ImageNet data sets, we use the the meta-model with four convolutional blocks where the network width of each block is 32, followed by an FC layer the output layer. For the Drug data set, we apply meta-model with two FC layers, where the network width is 500. All the experiments are performed on a Linux machine with Intel Xeon CPU, 128GB RAM, and Tesla V100 GPU. Code will be made available at htttss://giiie
cww waw.chhoow///annttttoo.aa Task-_sshccuulerr
A.2 Effect of the Task Noise Magnitude
We conduct the experiments to show the effects of the noise magnitude factor the Drug and CIFAR-100 data sets. The experiment results are shown in Table
Table 4: Comparison with baselines with different noise magnitude [data set (noise magnitude e) final results + standard deviation].
Algo. Data
Drug (0.3)
Drug (0.5)
CIFAR100 (0.3)
CIFAR100 (0.5)
Uniform SPL.
0.21810.007
0.220
0.65510.000
0.526110011
0.243+-0.008
0.236+00.00
0.625+0.017
0.367+0.039
FOCAL
0.2241100019
0.223110.003
0.63810.010
0.48511.000
DAML
0.182++0.025
0.177+00000
0.543++0.017
0.414+0.005
GCP
N/A
N/A
0.653++0.005
0,508++0.000
PAML
0.186:10.006
0.205
0.537-10.009
0.316
ATS
0.239:t00011
0,237=t0.014
0.651#0.001
0.505
BASS (Ours)
0.258
0.245
0.657++0.05
0.553+10.008
With increasing noise magnitude e, the performances of the meta-model trained by baselines and our BASS tend to drop, which is intuitive. In particular, for the CIFAR-100 data set, when we increase e, the performance difference between BASS and the other baselines tends to increase. This can be the reason that the greedy baselines with no exploration strategies can be more susceptible to the task noise perturbation, which can lead to the sub-optimal performances of the moda-.
Table 5: Experiment results of noise-free settings on three real data sets (5-way, 5-shot).
Data \ Algo.
Unifomm
SPI.
POCAL-L.OSS
DAMI.
GCP
PAMI.
ATS
BASS
Drug
0.20620.012 0.200:0.006
0.2400:0.003
0.19020.002
N/A
0.200100100
0.233:00000
0.256
M-InageNet
0.576=0.016
0.554=0.004
0.582=00.005
0.437=0.015
0.564=0.002
0.467+00.07
0.561=00004
0.586=20008
CIFAR 0.68110.010
0.68110.008
0.692.10.033
0.662:10.27
0.68L10.016
0.61010.011
0.695.0.033
0.697:10.029
From the Table we can see that when there is no noise, the overall performance does not differ significantly across different methods. The reason could be that since the heta-ne backbone remains the same for all the methods, the meta-model performance upper bound can be similar for different scheduling algorithms, without the presence of other confounding factors (e.g., noise, task distribution skewness). In the practical application scenarios with noisy data, BASS-guides meta-models tend to perform well presence of task noise and skewness compared with baselines, as presented by our experiments in the main body.
15

---

A.3 Parameter Study for Exploration Coefficient
As in Eq. and Eq. 9 BASS involves an exploration coefficient to balance the exploitation- exploration and the two exploration objectives. Here, we conduct the parameter study for the exploration coefficient a, and include the results with no exploration (i.e., removing f2).
Table 6: Comparison among different a values [dataset (shot): final results + standard deviation].
Algo. \ Data
Drug (1)
Drug (5)
(I)
CIFARI00 (5)
No Exploration
0.234=00003
0.239:0.012
0.256=0.027
0.537=0.012
a = 0.1
0.201=0.005
0.233+00013
0.264=0.051
0.522=0.024
0.3
0.228=0.013
0.231+0.000
0.268=0.047
0.528=0.014
0.5
0.236=0.004
0.245+0.006
0.272=0.025
0.553=0.008
a = 0.7
0.242:000012
0,227=0.000
0.241=0.005
0.543=0.021
a: = 1.0
0.236:10.002
0.205:10.013
0.206
0.537=10.005
From the results in Table 6 we see that the exploration module can indeed improve the performance of BASS compared with the performance with no exploration. This also fits our initial argument that the greedy algorithm alone can lead to sub-optimal performances of meta-model. By properly choosing the a value, we will be able to achieve good balance between exploitation and exploration, as well as between the two exploration objectives. Here, setting [0.5, 0.7] will be good enough to achieve satisfactory performances. Mcanwhile, we also note that even with no exploration, our BASS still achieves good performances by directly learning the correlation between the adapted meta- parameter and the generalization score, and refining the scheduling strategy based on the status of the meta-model.
A.4 Running Time Comparison
In Figure 5, we include the running time comparison with baselines. We can see that BASS can achieve significant improvement in terms the running time, and can take as little as 50% of ATS's running time. The intuition is that our proposed BASS only needs one round of the optimization process to update the meta-model and BASS, On the other hand, from Algorithm I of the ATS paper [51], we see that ATS requires two optimization rounds for each meta-training iteration to (1) update the scheduler with the temporal meta-model, and (2) update the actual meta-model respectively. Based the figure on the RHS, we also see that BASS can achieve relatively good balance between computational cost and performance.
Sumning thee
Running Time on Mini-inapeNie (S-thot)
0.32
VOCALLOSS
DALL
Snnttm Sumpring
0.28
0.2
5PL
600
208
10.00
D'54700
D124000
Time
Figure 5: Running time results (including training both the scheduler and the meta-model). "D", "M" and "C" refer to the "Drug". Mini-ImageNNrt "CIFAR-100 100" data sets respectively. BASS can take as little as approximately 50% of ATS's running time. On the RHS, we have the scatter plot in terms of running time vs. performance on the Mini- Mini-ImageNee dataset.
A.5 Performances with Different Task Skewness Settings
In Table 7. we include the experiments with different levels of skewness. Here, we see that with less skewness levels (the skewness level reduces from Setting Setting 3), the accuracy of BASS as well as the basclines will continue improve, while BASS still maintains decent performances.
16

---

Skewness Setting \ Algo
Uniform
ATS
BASS
Skewness Setting 1
0.375+00.00
0.382:10.007
0,408++0.008
Skewness Setting 0.429++0.012
0.460++0.013 0.448+00.006
Skewness Setting 3
0.497=0.0008
0.502=10.010
0.539=0.000
Table 7: Results for different skewness levels on CIFAR-100 data set (5-shot). (1) Setting is the original setting in paper Subsec. 5.2. (2) For Setting 2, we assign 5 tasks with 8% sampling probability, 5 tasks with 3%, and the rest of the tasks equally share the 45% probability. (3) For Setting 3, assign 5 tasks with 5%, tasks with 2%, while the rest of the tasks equally share the 65% probability.
A.6 Performances with Different Batch Size
With Table we include additional experiments with different batch sizes B, in comparison with the ATS and the uniform sampling approach. Here, we see that with larger B values, the accuracy of BASS as well as the baselines will generally improve.
B (batch size) Algo.
Uniform
ATS
BASS
1
0.459+00.009
0,449++0.010
0.472=0.012
2
0.526=10.011 0.570=0.012
0.515
0.553=0.008
3
0.563=0.007
0.588=0.010 0.586=0.009
5
0..005
0.571
Table 8: Results for different B values (batch sizes) CIFAR-100 data set (5-shot).
A.7 Performances with Different Embedding Approaches of Arm Contexts
In Table | we include additional experiments with different levels of average pooling, such that after the average pooling, the dimensionality of the pooled vector representation will fall into (20, 100, 500). We see that overly small dimensionality of the average-pooled vector representation (e.g., 20) can lead sub-optimal performance of the BASS framework. addition, we see that setting the dimensionality to 50 can generally lead to good enough performance.
Dimensionality
20
50
100
500
Accuracy
0.553+00008 0.541400008
0.555++0.010
Table 9: With CIFAR- 100 (5-shot), different dimensionality of the average-pooled vector representa- tion (Remark of the meta-parameters.
Here, we also include additional experimental results using MIP to map the original context into the lower dimensional space instead of using our proposed average pooling (Remark 3). Results are shown in Table [0] Here, we use the one-layer MLP with the ReLU activation to embed the original meta-parameters to the low-dimensional vector representations. We can see that the MLP- based method can indeed lead to some performance improvement. But in general, the performance difference between MLP-based embedding and the average-pooling vector representation is subtle. We also note that the MLP- based mapping approach is more time consuming compared with the average pooling approach, since also need to train the additional embedding layer, which has considerable number trainable parameters.
Dimensionality Original avg-pooled (50) Accuracy
50
100
200
0.553+0.008
0.558+0.013
0.560=10.012
0.553+0.015
Table 10: With CIFAR- (5-shot), different dimensionality of the one-layer MLP(with ReLU)- embedded vector representation of the meta-parameters. "original avg-pooled (50)" refers to the average-pooled vector representation (Remark 3) with dimensionality of 50.
17

---

A.8 Additional Experiments on the "DomainNet" data set
In Table IT. we include additional experiments on the new "DomainNet" data set [37]. Within the "real" domain, we filter 100 classes that have at least 600 images. In this way, with each class being a task with 600 images, we will have a total of 100 tasks. Compared with image data sets in our paper (Mini-ImageNet and CIFAR- 100), we increase the image resolution of "DomainNet" by resizing its images to 128x 128 pixels. Following the settings in our paper, we divide tasks into 64 : 16 20 portions that correspond to the training set, validation set and the test set respectively. For the few-shot settings, we formulate the problem to be 5-shot, 5-way 7-way with uniform sampling and ATS as baselines. With higher image resolution of the "DomainNet" data set, BASS can still maintain the good performance compared with the baselines.
Setting
\ Algo.
Uniform
ATS
BASS
5 5-way
0.475=10.002 0.411#0.005
0.483=0.006 0.372=0.009
0.511
7-way
0.435+000008
Table 11: Results for the "DomainNet" data set (noise level 0.5, 5-shot settings).
B Appendix: Additional Discussion on the Necessity of Assumption 5.1
We would like to mention that in order to finish the convergence and generalization analysis for the neural Contextual Bandit works (e.g.. [54] 2 9. the separateness assumption of the arm context is the minimum requirement of the data set. This is because the training data needs be non-degenerate (i.e., every pairs of samples are distinct) to ensure that the neural network can consistently converge, as indicated by Assumption 2.1 in (3. Therefore, our Assumption 5.1 regarding the arm separateness aims to ensure that the BASS is able to adequately learn the underlying reward mapping function with sufficient information. Comparing with the existing works, in the convergence analysis works on meta-learning [47 48), they measure the arm separateness in terms of the minimum eigenvalue Ao (with Ao > 0) of the Neural Tangent Kernel (NTK) (33 matrix, which is comparable with our Euclidean separateness
For existing neural bandit works. Assumption 5.1 in [9] is similar to our separateness assumption. Meanwhile, Assumption 4.2 in (54] and Assumption 3.4 from (53] also
imply that no two arms are the same in terms of the minimum NTK matrix eigenvalue Ào > 0.
C Appendix: Limitation
One potential limitation of BASS is that its improvement over baselines may not be significant when dealing with noise-free settings and non-skewed task distributions (Table 5). Meanwhile, the non-adaptive FOCAL-LOSS [30] tends to achieve a similar performance comparing with the adaptive method ATS [11, while enjoying an advantage in terms of the computational cost. In practical terms, although BASS can generally achieve the decent performance and enjoys a smaller computational cost than ATS, the practitioner still needs to consider whether their task distribution is noisy or skewed in order to strike a good balance between the computational resource needed and the meta- meta-model performance, as BASS can achieve a more significant advantage over baselines given the noisy or skewed task distribution.
D Appendix: Theoretical Analysis
In this section, we present the proof for Theorem 5.2 Here, instead of directly going for the batch
522 B)), we first introduce the results of the single-task setting (Subsec. D.I i.e., [22 | = 2 = 1. Then, the results will be extended to the batch settings as in Subsec. D.2 Recall that for the meta-model, we first
setting where we adopt training task batch Ω4 for each iteration k E [K] (94
consider it to be Ly-layer fully-con conlecedd (FC) network (of width m. for the theoretical analysis (lines 237-239). In particular, we follow the settings in k for the Gaussian initialization of weight matrices. For the weight matrix elements in meta-model's first (L, 1) layers, we draw each of them from the Gaussian distribution (0, 2/mz). Then, for the weight matrix elements of the last layer (L layer), we draw each of them from the Gaussian distribution (0 1).
18

---

D.1 Single-task settings
For the brevity of notation, we denote the scheduler output 0f + (x Voli J): 0 which corresponds to the definition in
(T 0())))))))
Eq- 7 In this case, T(K)= = (Ti..... Tk} } refer to the chosen tasks and T (K) = .T...... .Tk
the optimal ones. Based the problem definition, we will have
(K) = BTTP(T)) (T DNDD (T: ((101)) - BT ((::I((,6)()))
C [T
O(K ((K-) -ET-P(T) .wDD -
BT~
-(( [T]] ((0(K-1) [T])
= -( 1), [TR])- - f(x:: 0(K-11) + f(xixx;x +xxxx:0( f(xx: 0(K-1)
+ f(xx: (1(- -(@@( ((((())([TT))
S sh( (K- 1). (TR]) - -[(K;:
0 (K (K-1), ("-))- +f(Xk:
0 0KK-1)) 10((0(K-1) [T [ 11)
+ +f(k:
(1 (
h(0 [xxx)
-(( (K - 1), [TR]] 5(0 (K 1), [Tk]:
[T]]: 0 0(K-1)) + (11)+ [T]]: (K)) - (K 11) 1 11)
1).
+ +/( (K -1) [T<]: 0(k (0(K-1)(TH)
< 111 (K- 1). (I
0 ) +I((O(K-Di)(TA)) 0K1-)
(1-K ((0 (
(1K-1)1)
+ (T) -M))
where the first inequality is due to the arm pulling mechanism, i.e., f(O(K-)) [Tx] O(K- =
(e [T [ ((K-)). Here, f(:: (1::0K-1) (k-1)) is defined as the "shadow" bandit model that are trained on optimal tasks (Ti', T2" ..... - and the corresponding meta-model parameters. Here, denote Xx = (k-)) [Tk] E IRP as the arm context given the arm Tk and the meta-model parameter o lK 1), similarly, we have X = @ 1).* [TRl E RRP being the arm context given the arm Tx and the meta-model parameter θ KK 1).a Thus, for the term to on the RHS, we have
lo 1 ((k-11) 1(O (k)) [Tk 0 (1)1)))1
-I((0(K))))TTT (K-K)) )
f(O(K K 0()):((--1)
+ (K K- -1), (T(T O(K-11) 5(0) (K-1) [Tx]: O(K-1)g1
< ( (K-
+ +I (K [T); (
f(O(K K-
11) (1)---1)-))) (T): 0(K-11)1
f(o (K-0) | 11K-
Then, inserting the inequality will lead to
R(K) S I (K [()) [kl)
f(x:: ( 0(K-1))
|f 0 1 (K (10 (Tx))
[(0 1).- [T 0 (K- -s(0 1)," [Tx] (1K)1)))
5 [Tk: O(K (K-K-)
s(OlK 11 [T] (K-1)))
Here, the terms I, In refer to the approximation error for the two bandit models (our possessed model {(; OLK-1)) and the pseudo model ((: (KK-)) )). Then, the third term /3 bounds the output
difference when given the same input @ (K (K),),+ [Tk] to two separate bandit models, and the final
19

---

term 1 refers to the difference of the meta- meta-model parameters when adapted to the same task with two individual sets of parameters. Here, the terms I,, 12 can be bounded by Lemma [.]] Corollary D.2 Then, the point is to bound the difference term /4 when given different inputs to the bandit model.
D.1.1 Bounding error terms and assembling the regret bound
[Bounding term I3] For error term 13, focuses on bounding the output difference between two bandit models f(:: 0 (KK D) f;; given the same input @ [T and we have
I3 |f( K- 1),² [T
(K
0( 11)] = 1f(xx 0 )) 1(Xx: 0 ((K- ((K-1)))
1 01 (K-1))
13.1
f2 VVli(xi)); Voli(k))) (x; + 1/2 (Vli(x)) Vali(x))) ));02 K-1)
With the defined EL, applying Lemma D.11 as well as Corollary D.12 we will have
13.1 S (1+0l KL 5/6 (m)))((())
)
L
12 log (1/0(mm))
O
log(m)) o
pm/3m 1/6
P/m
pm 166
Then, for term 12.2, we have
T.2 = 1/2 (VVSi( Voli(x"));: 0
(( 1/ (o(VVo/((x)) Voli : 1
$ $15e (Vooi(xx²)) Vafi )); 0 0 -1 (V Vafi(k )1: -
f2
+152 (ol1(x)))
Vali )); )):0 0 S2 (Vos((x))) Voli }}; 0 (1)
Here, for the first term on the RHS, we apply Lemma D.II as well as Corollary D.12 to bound.
Then, for the second term, with Gaussian initialization of weight matrices, for the over peeepparameterized FC network ff with Lipschitz-smoot activation functions (e.g.. Sigmoid), we can have If || æ'|| due to its Lipschitz continuity / smoothness property 47 [8]. Meanwhile, we also have the Lipschitz continuity property for over-parameterizze FC network I' with ReLU activation B. such that [='(x) ('(=')"')''))))) < ||æ æ'Il. By the Gaussian initialization of BASS's weight matrices and the properties of purrpparameteiized neural networks
f(x'),, [ - [='') <
3, (8) we have & max(E, < O(cE)) being the Lipschitz constant for our fI, f2, where
<: > 1 is small constant. Applying the conclusion above, we will have
fee (afi((x)) Vafi(x) 01.0 fo (Vofi(x))) Vefi 01
S [Voh((x)) Vor(2 En (Vof((2)) Vofi
< EL (ofi(x - Vefi + (/Vof((x)) vof(x()
KL* log 5/ (m)) (m)
SE
p²/ m2/3m_/
where the last inequality is by Theorem 5 in 3 and the proof of Lemma D.11 results, it will give us
With the above
KL log 5/0 (m),
L log(m)) + +0
K L2 log 11/6 (m)
K EuKL*log"s log (m) pm/3m!/ 1/6
1a < 1 1 1 /333ml
00
+
Pmm
pm33m 1/6
20

---

[Bounding term 4 On the other hand, applying the analogous procedure for term 14, denoting
xk O K 11, [Tkl and Xx 2 (K-1) [Tk] for the brevity of notation, we can have
4 If K- -),** [T ((K-1)) - f (K-1) [T>]: ())
EL ||0 ||0(K-1), [Tx] O (K (1 [Tx]
+ life (Voi(())) (ofi(x)))):0) (1-)) fo Vofi(())); Vofi(x)"): (K--1)
14.2
where XK Xx respectively represents the support set and query set for task Tx and the meta- parameters O ( 1),* Similar notation also applies to Xx O 9(K-D|(T) And the inequality is due to the fact that ReLU networks are naturally Lipschitz continuous w.r.t. some coefficient &r. when they wide enough B1, we have discussed above.
[Bounding term 11.1] Based on the meta-optimization procedure (inner-loop optimization outer- loop optimization), we have
4.1 εt. 11
O 111-11111 [T [|0(K-I)
[Tk] [TRl
-Er. (((K-D)+- 1/2 VoLLD ) ()(K1))
- 12
(0(K-1) -1
V o 112
where O is the task-specific parameter of Tk after adapting on (K--)), with inner-loop optimization, and the (/)) is the similar parameter after adapting (K-1), Here, we simplify the formula by representing the gradient derivation (inner-loop + outer-loop) with the mapping
H T + + R', which leads to
||0 (K-
[T
a (K [Till2
= -1(00K-115+ -/22 VoLID;,(("1) (0(K-1)- -(00))))0001---- 1/2 VoL(D?;
=I(0(K-2) -((K11)) 1122
H(TK: 0(K-1)))) -H(KK 0(K- 112
1/2
-I(( 2), -o(K-2)) 1/2
[H(Tk. - 0((-11))
(1x
-1/2 [[(Tk-,, -1T 1 0((--1)) 112
S Σ 12 kE[A]
(k- ((8-))))) H(T θ (1
Recall that the past arms. including the actual chosen anms {T1, .2...., Tx} } as well as the opti- mal ones {Tr", Tz..... } are all from the candidate pool where each candidate arm is drawn i..dd from the task distribution P(T). Therefore, denoting the bound as [ (K-)))
H[T (K-K))) < (KK), we can have the upper bound as TA11 I 1/2 &L K (K).
Then, for the term (K)), by definition we have [H(T,, (K-)),+) H θ K |K)))||| SK),, applying mean-reduction for the sample loss will further leads to
[[ (K-)),, H(TR, ( VeL(D (1)
VoL(D 0 x2222
K
= 11 D
Σ
Vol(n:
Σ VeL(E: θ @24 )|1
D
D
x
Σ RED
Voe( - VoL(x; e (3) )22
D
This inequality essentially bound the gradient difference when given the same input task T w.r.t. different sets of model parameters. Based on the conclusion from Lemma 9 of [47] and Lemma
21

---

B.3 of [., we have [Ve IVe.lllll. C(;; & <()m))) 4I E [Lx] for any set of parameters within the sphere 0x E B( w) where Og the center and w is the corresponding radius (which is small value). With total of L layers for the meta-model and each layer of m,
hidden units, this will give us VV O (J):*) 1|2 VeL(o; + ( lll I O(ympLz) (Lemma D.15 And this makes S1 (K) I (L)))F)) Since we have 71 m22 I O myy summarizing the results above, the upper bound can then be derived.
[Bounding term 4.21 Next, we proceed to bound 4.2, which will be
4.2 = 1/2 [Vof(x))); Voli(xk 01:00
f2 (Vsi((i)); Vo (K-1))
< [[Vefi(*)); Veri(x))] -Vof(x()) (x
1 l1 Vofi(x)) - Vofi(x))) 012 + EL Voo - Vo
< ||xx" xx + 1|* X ll2
where the inequalities are due to the Lipschitz continuity / smoothness properties of over- parameterized FC networks we discussed above. Here, we notice that the second term on the RHS can be bounded by directly applying the proving procedure of term 4.11- Then, for the first term on the RHS, we can following a similar procedure as for 4.11 by
1|xx*
XA 11a |I(TE ((--1),)) I(T
A (k- 11 111
= || 1 (((K-))+ - 7
Σ
VoL(D 0
0 (K-1)) -
Σ
VoL(D o
SE(M
SE[
[(0(K-)), - -O(K22))
(m Σ
Vol k- k-1) -nn-
VoL(D θ x4
jE[J]
JE(J]
-(1 Σ VeL(D
K 0 - -
Σ VeL(D* ())*) l12
K
JELJ
SE(J]
m
Σ VeL(D k) 111 Σ
VoL(D 0 [()))
l|
KE[K]
SE[J]
JEM
S Omn KJ mm
where the last inequality is due to Lemma D.15 and by iterating through K meta-training iterations. Summing up the results above, we will have I.. S O K +V
+
KJvmpLy)
[Summing up the results] Then, combining all the results, would have
1 1)
(V
3L + (1 + 2m) pn) ( 2oog ( + + /mz
S.K.VLF + 7m
Rsingle (onntte(KK))) S 0
VK
V2
where
L
I²K
01 2 2
log m
+
p//3m=/6 log 100 (m)
Pvm
7'm (1+
KL log 5/6 (m)
log(m)) + 0 K < loggl/((mm) pym
L
ELKL* log 5/6 (m)
O
p1/3m-17
1//3m1
p1/3m116 1/6
Note that the majority of the terms above can be cancelled to ((1) with proper networks width m indicated in Theorem 5.2 With increasingly large network width m. these terms will also become diminutive enough to achieve our regret bound in the main body.
D.2 Extending the result to the batch settings (Proof of Theorem 5.2
With the results and conclusions from Subsection D.I
proceed to provide the proof of Theo- rem 5.22 the batch settings. Recall that in our original problem formulation and Algorithm I we expected to select a batch of B arms in each meta-training iteration, denoted by (St ( Note
that each of the candidate arms from (1( are drawn i.idd from the task distribution P(T). Mcantime,
22

---

we will have the corresponding optimal arm batches, denoted by {92 ke(()), which minimizes the loss objective in Eq.
[
Recall that we update the meta-model parameters with
(k) = + ( 1 Ve
1 [Aa
Σ Ta
:.D.:: = (x-1))
12
Σ Vo
co(CLUz. 0
S2
Te
where O is the task-specific parameter for T after the inner-loop optimization for J steps.
Analogously, for the notation brevity and the sake of analysis, we denote f(O ( 1()
Ji (x): 0/--)) + /2 (Voli(x)); Voli = where we have x := θ (K- [(xx being
the parameasss adapted to batch of tasks 22k, and the batch-specific parameter is defined as O ( Then, the regret under the batch setting can be denoted by R
X = [2 ET
R(K) Rounch (K) BTNP(T), BT I(T
ETWPIT) [( [x; ((
(K- ETT 6(k
E, -ET-P(T) (( 1221))
11, = -M(O ((10(-1))-004)) (0x]) - h( (((x)))
- - (0x]) - f(0(K-)))())) [2xx 8k ((0 0000))
h( + (( - (1-))
h
and after applying properties of the arm pulling mechanism, is equivalent to
R(K) ((((-1))((0))) /(0 (1), (0 (K-1)
+ +
11, "000 ) j Oxl 0 1)
+ f( (( -(00 kk f(olk-1) - [0
+ * 112 11) [(( 0 (K)-1) +
- -1)0((()))))
(0 (2x() 1(0(K (K-), [2 ")) + l
(K (1 10xx 11 (1) 0
(K)))K-)))100)) 101]] 0 1)) ((0(KK)) (K- [ 0 (1))) + (k(0 - ((x) (xx (((-1)))
+
-
where the average value of estimated benefit scores for individual tasks TK E UK is represented as f(0(K-1) [2x] ETKcEEx [(o(K-
[axl ΣTK, ((O(k-1) 1/2
VeL(DR K.; 2 : (1),,,, and the inequality is due to the pulling mechanism of BASS. Here, Js, Ty individually correspond to J,, Jn in the single-task setting and can be bounded by Lemma [D3 Corollary D..4 Term Ta be upper bounded by Ja 14 from the single-task setting above. Then, for the rest terms 16, Is. we proceed to bound them separately.
D.2.1 Bounding error terms and assembling the regret bound
We begin with the term 1g. and then proceed to 1e. For the chosen batch of tasks 2g in the round K, we will have Si
fi (O - Ve [ax ΣTK, L(D), O (3) k))) 0(K-1)) In this case, the average value of estimation sampling probabilities for tasks TK,s E Qg is
f(e [xx] = (k- + (2
Σ
(11)) + fo ((Vori(()))) Vofi(xk,)); (11))
10
TR.
23

---

[Bounding the fi output difference] Next, let us first proceed to bound the output difference with respect the exploitation module fi. where we can transform this term into
((O(K-)) (<xx)) - (x(((((1)))
[[x])
= fi 0 (0 - 1/2 Vo
Σ
C(D :0k :()
TRi
Σ
(01--1) 12 VeL(D 2 K (((
10xl
Tk. ElK
fi [(((-11)) 7/2 Vel
L(D k.t 2 kk:)) 1(k-11)
|9
TR
TK,
- -i((0 (1-1)-1) 7/22 Vel(D) 0f (K(1))
Then, applying the Lipschitz continuity property will lead to
((((K))((2x)) - (k [(xx)
172 EL. s
Σ
Σ
[(Dk;:0k) ())
VoL(D) O 2.ll..
[2x
Qg
TR.ERR
TR.
Here, by the definition of the outer-loop optimization of first-order meta-learning, we will have an alternative form the inequality, denoted by
(K ((O(K-P((x)) (1(0(K-11))
[xx])
S
T2 EL
Σ
Σ vo(((Dk,;)k)) VeC(D k.s 2))11
[0xl
[K
TRAEERKK
TK,
For the term in the parentheses the RHS, substituting the backward operation with the (:::)) mapping function, we have
Σ
Σ
VeL(Dk, @ 2
ΩK
TR.eexx
Tk.
Σ
Σ
Ve(C(Dk : [xx
Σ
VeL(D
Axl
TR
Σ
Σ
Voo(DD) k.j x VeL(D) 12
$ |0xl
TR Tx.yESt
1
Σ
Σ
[[(T,, ((K-1)) H(T,j, (K-2))
[Ω TR Tx., EDk
< <9pk (K).
with 2x = B. Therefore, the S1 part of enror term Is could be bounded by (e (K=))[x]) < '12 Ez. B Si (K). where the upper bound S1 < O (()m=LF) can be -
found in the procedure bounding term 142-
[Bounding the f2 output difference] Then, with Xx = e (K- [[x]. we proceed to bound the output difference with respect to the exploration module, which is represented by
12 (K (1-1k [(K)) (x)))))
=f((Vof(((k) Vofi Vofi(x
fa([Voi((Xk.): 11 -1) Tk,
Σ
[x
Σ
(a((Vof((xk): Vef((())l:0 (K ( f((VVef((x)))) 111; (0111
=[k
TRIEERK
24

---

By adopting the Lipschitz continuity property of f2, we will have (=(0(=)((xx) (2(0(K [xx))
Σ
[[Vo)((xk); - (Vol((kk)) Volkk
[2
TR
Σ VVoi((x))
[2g
Tkl
Li
< [0g
Σ
|| Xkill2+ + 1|x - 8ksl12
TR
G. 112
Σ
Σ
C(Dk, : Vel(D : 2)
[xx
[x
Tkk
E
+ [2g
||xx Xk.il12
Tk, E0x
. 771 |9
n/ BB (K)
Σ
Σ
Σ
Kalla
[K
Ax
TR,
Tie
where the last inequality is by applying the conclusion when bounding the output difference w.r.t the exploitation module f1. Then, for the second term on the RHS,
Σ
Σ TK
Σ
| K. θ
0%2 l12
Ag
Tk. E0K
Tx
Tk,
Σ
Σ
Σ
VoL(Di 0k2))
(0K-1-
Σ
VoL(Di 0
Tk., ENx TR,
TEVo
TE(J]
Σ
E
VeL(Di
K.
Σ VoL(DK TEMM
[ix
TR, TRaeflK rE[M]
[A O( O(VmpL)) where the last inequality is due Lemma D.15 Summing up all the results above will give us
the upper bound for f2 output difference f2 ([(])) (2 (00 [[x]) S O(n E B
VmyLf + 7/1 BJ Ly)
[Similar procedure for term [&] Analogously, we can apply the same derivation for the error term Jt, which leads to
I ((O(K 1). [[k]] (11-1)
/( (K-
1). 10x: o(K-1)
fi ( 1/2 Vo(
Σ O( )): 0(K-11)
To TeE
Σ fr - - " (11
19
T.
Following similar procedure that of term I3 will give similar bound as
1s ((0 [0]]] (K ( f(e) I). [00] (k)
S O E. B VmyLF + BJ VmpLem).
((2)) where the learning rate 171, 1/2 S 0 my small value. Then, the upper bounds for error terms 16, Iy are given as desired. [Assembling the results] Then, combining all the results, we would have
1 } (V R(K) S 0(
3L
+ (1 + 27) 2log( 2 )
+0 +
S.KBJVTT + 7m
V2
mm
25

---

where
L
L2K1
n1 2 0
log O
log" (m))))))) (m)
Pvm m
1//3ml/6
KL 7' (1+
5/0 log" (m)
L Pvm log(m)) + +0 K=L² KLL22log0 (mm))))))))))))))))()))))
EL LLKL (m)
0
+
pl/3m22/6
p4/3m
p2/3m226
Similarly, with proper networks width m as in Theorem 5.2 the majority of the terms above can be cancelled to O(1). With increasingly large network width under the paramtterizaaiinn settings, 71, 7m will also become diminutive.
D.3 Performance Guarantee for the Exploitation and Exploration Modules
In this subsection, we would like to give the performance guarantee for the proposed BASS framework, and the corresponding performance bound can be applied derive an upper bound for the error terms I1, 1z for the single-task settings and Is, Ig under the batch settings. Up to meta-training iteration E [K] (before updating the meta-parameters and BASS), we denote all the past records received as PA-1- Before presenting the main lemmas, we first introduce the following operator. Inspired by [3] with two arbitrary vectors X. X such that || I 1, |l Xll2 = 1, we have the following operator
x x
olx x)
V2
2 2
(11)
as the concatenation of the two vectors
_x X and one constant c, where c = V 2
V22 2
And this operator transforms the transformed vector into unit norm, || x) 2 1. The idea of this operator is to make the gradients fe (1) of the exploitation model, which is the input of the exploration model f=(:: 22.. comply with the normalization requirement and the separateness assumption (Assumption 5.1) For the sake of analysis, we will adopt this operation in the following proof. Note that this operator just one possible solution, and our results could be easily generalized to other forms of input gradients under the unit-length and separateness assumption. Similar ideas are also applied previous works lemma.
(
We begin to bound the single-task -aak settings with the following
Lemma D.1. For the constants dg 0, S ( and & E (0, given the past records
PE-1, we suppose m. 71, 1/2 satisfy the conditions Theorem 5.2 and randomly draw the parameter
(0(H) 3 (0 (7))
}re(H). Consider the past records Pa-1 up to round are generated by a fixed policy when witness the candidate arms ( Then, with probubility at least 1 given an arm-reward pair (TR3)' k.))), we have
PEE [152 or
[ofi(x;;))
xx,,) : 004-10 - (T+ Tr (r-- 11(x211 014-11) 10 Pk-1
1
(V2S
3L
2 loog( h 7) + (1 +2111
+
Vk
22
where
k L Pym
p4/3m!/6 log 11/6 (m))
L2k4
= 2 200
log m
+0
Proof. The proof of this lemma is inspired by Lemma C.I from First, we can derive the output upper bound
(of((()))
Vofi(2?))
x2 :1::0011111 - rr (Te
fi k. 00: )11
fz 6l
Vofi(( Vofi(x2
05 0
+ Fi o 111-119// +1
f2 0
cg
< 1 2711
26

---

by triangle inequality and applying the generalization result of FC networks (Lemma D.5 on fi(::1))
(ofi( :): (2
For the brevity of notation, we use (T( to denote of (XeeTh) rw) as (x7,7 (x.5)) for the following proof. Define the difference sequence as
and apply
%
V E f2 fi 3): 05-
- fi(x::
02:00 05 0 r+- fix:
Sa
V
Since the past rewards and the received arm-reward pairs (Xr: [r) are generated by the same reward mapping function, we have the expectation
0 - (Txx ]
E F+1
=E
f2
V
(T
(r,- ( f1 1) F, = 0.
E
fa VTT((T=)::
where Fr denotes the filtration given the past records Pr, up to round [k). This also gives the fact that v2 is a martingale difference sequence. Then, after applying the martingale difference sequence over [At], we have
f2
V (TT(T=))::
( - fx==((x;
k
k
TE(M]
rE(K]
1
Σ
f2
V 3): 0 "1) -1----(-xxxx f(
TEJK]
Then, by applying the Azuma-Hoeffdiigg inequality, it leads to
E 2 (1+ + 2 logg(1/0) 1/8)
P
(1)
Σ
<
k
FE(R]
tE
Since the expectation of ()()) is zero, with the probability at least 1 8 and an existing set of
parameters 02 s.t. ||0g 0 I 5o6
kaa pvm
log m ) the above inequality implies
2 (108(1/8)
( S (1+ + v1+
TE(M
f2 V (T=((==)):0 -
E
PT.T 10(1-1) -/
Σ Σ
f/
v (T ) 0 - (rx -11=-f((xt100 ((x=(xx=-ff-11)
FE|K]
< Σ
f2 (T ): 05 05-11) - (r,- -
( + (1 +27i)
2 log(118)
k
Σ 81 TETK
12 (VA(T.)):0)) (1=)))(--1xx:0000
+
3L
+ +(1+ + (1++1
22 (l/g(1/))
V2k
k
1
Σ rE(K]
/2 [)((T,)))0))
2
+
3L
+ (1+ 11+ii/
2 2og (1/)
15
22k
h:
2
3L
21og(1/8)
(1+ + 22+)))
k
12k
k
27

---

where the first equality is due to the sampling of candidate tasks and the model parameters. Here. the upper bound (i) is derived by applying the conclusions of Lemma D.6 and Lemma D.10 and the inequality (ii) is derived by adopting Lemma wh6le
while defining the empirical loss to be
E J2 (T,T)))) (1+ (+--
- 1i(x;00/-1)
)
E Finally, applying the union bound
would give the aforementioned results.
Here, analogous to the trained parameters, we consider the shadow parameters as (0(1)) (()),
(0(")" 82 "0""" }T(())- Similarly, each pair (0)")> _ is separately trained on past received rewards of the optimal arm(s) (rr', "relr,,T eRt and past exploration scores of the optimal arm(s)
(err),rre En; with Jo-iteration GD, starting from the random initialization {0 )
Corollary D.2. For the constants < < O(1LL) and & E (0.1) given the past records Pk-1. we suppose m, 1/. satisfy the conditions in Theorem 3.2] and randomly draw the parameters
{o(h), 0..),*) {0] .02 JEE] For the optimal arm TR, E D consider its union set with the the collection of past optimal arms Pi-1 U (T Tk, J are generated by fixed policy
[()),* (T),**
Then, with probability at least [T(M). with Pk-1 being the collection chosen by this policy.
when witness the candidate arms (
have
152 00 Vofi(xt Vofi(x Xx
(++ -+-- fi(xt :0t-1);;))
ET,, ET.,.-((T)
xx
9.
/ Pk-11
EgL
(V25, + Vk
1
v2 + (1 (1+ logl 2200(
3L
+ +Tk
where V7 is the corresponding reward generated by the mupping function given an arm Xx,i and
T& = (1 1 O 1 1og"/((m)) (m)) (m))((((m))
)) /133m11/6
(m)) 00
k
log(m)) + 0 k I.2 log (1/1110mmm)) (m)
Pvm
p3/3m22/ 1/6
This corollary the direct application of Lemma D.1 by following similar proof procedure. First, suppose the shadow models (-;0;22, fz(:; 02) are trained on the alternative trajectory P
Proof.
Analogous the proof of Lemma D.I we can define the following martingale difference sequence
with regard to the previous records P up to round E [4]
00-0111))) - - (t-1;)))11)) 11:)
v(1)+ = E f2 (TT.)))))
fa (T - (1=-11(xxxx 0f" 1)-
);
Since the records in set p are sharing the same reward mapping function, we have the expectation
E
f2 V (TT
(r; - (1:- (1;= of
F
f2 V
(T((T.:):
r (1;- 1..)) FF = 0.
where Fü denotes the filtration given the past records P The mean value of v,(1), across different time steps will be
E
fz
V (T((Trs)::0(
rr; (r:- fi(x;: (())))))))))))
TE(K]
TE(M]
(T 7 (:= (1; - -1
Σ f2
(()))))))))
TE(M]
28

---

with the expectation of zero. Afterwards, applying the Azuma-HHoffidee inequality, with a constant 8 E (0, 1), leads to
P
1 Σ TE|0
( Σ rE(M]
(1 + 2%))
2log(1/6) k
S
To bound the output difference between the shadow model fi(:; (1:::0000000 () fz(: 05 ))²) and the
model trained based received records fi(:0(( fe(:: 0 1 we apply the conclusion from Lemma D.11 which leads to that given arbitrary imput vectors a, x', we have
[i 0 ((-)) (1 0(--1)), 1f2(2'; 100-1111 1)x) f2(x' 0 01
I + O 1:1,3 log log"/((m)
AoI."og"'1 p1/3m226
))
O k. L
log(m)) + +0 h: log (m))
PVm
p4/3m
Finally, combining all the results will finish the proof.
We will also be able to have the performance guarantee under the batch settings. Recall that given batch of chosen tasks 24 C ( & E [K], we have the meta-parameters adapted to this batch of tasks being θ {{xx), which we consider as the input for the (=(;01) model, where the tasks within each collection are sampled from the task distribution. Thus, chosen task batches from different iterations are also independent from each other. Intuitively, we can also define the corresponding reward for arm batch 24 as Tkk = h(@ (K- (S2e). Then, we bound the batch settings with the following lemma and corollary.
Lemma D.3. For the constants dy > 0, p (0, (()) and & (0,1), given the past records PE-1, we suppose m. 7/,, 7/1 satisfy the conditions in Theorem 5.2 and randomly draw the parameter (0()) 0 (0)") ( }re[e). Consider the past records Pk-1 up to round is are generated by fixed policy when witness the candidate arms (9 (nn TE[K)- Then, with probubility at least 1 ô given the pair of chosen arm batch and the reward (Sk, Tk) in round k, we have
E ET.,
(TTT)P((T) 152 oi
Voli(x(); Voli(x2)
x
- - 01t 1
(K) Pk-1
L
1
(VZEi
3L
s
+
2 log 51) + (1 + (1+22)1
Vk
V2
where
71 2
LL pym
log m
+
///3m!!6 log 11/6 (0(m)
L²
(m))
Proof. The proof of this lemma is analogous to the proof of Lemma output upper bound
D.I First, we can derive the
(ooi( vofi(20)
x2)
fe d
EL
< f2 Ør or
(ofi(xt); Vefi(x2) x2): 02);05 o + +1
Lgb
11 27
by triangle inequality and applying the generalization result of FC networks (Lemma D.5) on (: 01), fz(:;2)) where dg > 0 is positive number to scale the concatenated gradient vector.
For the brevity of notation, we use (fi ) to denote o( (ao (xf): (ofi
xxi) and apply (Xk, rk)
as (x.. rk) for the following proof. Define the difference sequence as
v = E fz (2.)))))
(Tx- - fi(x-:o(--1))
fz ((((()): (1. (r- f((x::((-111
29

---

Since the past rewards and the received arm batch-reward pairs (xr: are generated by the same reward mapping function, we have the expectation
- (ro- - (10-1((x;0ff )
- r+ fi 06 ")) Fr =0 (
F+]
E
f2
TE
f2
(2.));
where Fr denotes the filtration given the past records P., up to round [k]. This also gives the fact that 12(2) is a martingale difference sequence. Then, after applying the martingale difference sequence over [kc], we have
Σ V(2) [E(
E
f2
((((0.):)5-1))
(r. ((xxxxx:
TE(K]
1 K TE(R]
Σ
f2 ff 0 11111 - -1
By the Azuma-Hone Hoeff--og inequality, it leads to IP 1 Er(n)) -00 E 1 N (1
2 16g]116) S 6. As we have discussed, the tasks within each collection are sampled from the task distribution, which makes chosen task batches from different iterations f2g, k [K] are also independent from each other. Since the expectation of Vi is zero, with the probability at least
1 - and an existing set of parameters O2 s.t. ||02 0 S O
log m)) the above inequality Pvm
Raa
implies
1
2 2log(1 (1/8)
V S (1 (1+27)
k
TE(M
f2 ((((())
-(--iixx0
E
PPTT)
1000 (0 10 0f 11
Σ
E
/2 V (22)):
rk rk- (r=-s((r:(( 0f11)))11111)
1
rE(A]
1
Σ
f2 ( - (++ - f1(x-: (1 + (1 + +2n))/
2log(1/5)
<
k T
l
Σ TE(A]
12 (1(())))))) - -(x--1i(x;;0
3L
+ (1 + 271)
2 (lg((1/))
V2k
h
Σ TE|K]
fz ( - (1--ii(x-:00--))
+ 2h
3L.
+ (1 + 2n)
2 (1g()/0)
VTx
k
25 +
3T,
2 2lo((1/8)
+ (1 vnn)/
V2k
k
where the first equality is due to the sampling of candidate tasks and the model parameters. Here. the upper bound (i) is derived by applying the conclusions of Lemma D.6 and Lemma D.10 and the inequality (ii) is derived by adopting Lemma while defining the empirical loss to be
Erein fa (9.)): (r- o(xx: )
Ez. Finally, applying the union bound
would give the aforementioned results.
30

---

Analogously, we consider the shadow parameters as {0(M), 0000,,) ~ {0) (0) ,02-"
TE( where
each pair {0] (T) 0fT);) is separately trained on past received rewards of the optimal arm(s) treth,T e02; and past exploration scores of the optimal arm(s) {err,- )eir) e9g
with Jæ-iteration GD starting from the random initialization {0", (
Corollary D.4. For the constants p (0, O(t)) and & (0. given the past records Pk-1, we suppose m, M7. satisfy the conditions in Theorem 5.2 and randomly draw the parameters
{0(*)r "0" ~ {0] (r), (T).
02 }re(H)- For the optimal arm batch O C D consider its union set with the the collection of past optimal arms Pk-1 (99, r are generated by a fixed policy when
rE(R, with Pk-1 being the collection chosen by this policy. Then, with probability at least 1 5, we have
witness the candidate arms {St )
TT (P(T) 152 of Vofi(xe") ); Vofi(x (x))
0
r4 --- :0
lo Ph-11
.Kk
Egb
(V25,
3L
k 2log( + T
v2 +
+1++m)
Vis
where Tr is the corresponding reward generated by the mapping capping,uunctionn function given an arm Xr.i and
P2 = 1 O kL log" 5/ (m))
))
LL Pvm
log(m)) + O k log 11/6 11mmmm)) (m)
p2/3m22/6 p
O0
p4/3m226
This corollary is directly application of Lemma D.3 and can be obtained with similar proof as in Corollary D.2
D.4 Ancillary Lemmas
Applying Pk-1 as the training data, we have the following properties for the over-parameterized FC
network f(: 0) after GD.
Lemma D.5. For the constants (0, O(+)) and & E (0, 1), given the past records Pk-1 up to time step k, we suppose m. T, J1 satisfy the conditions in Theorem 5.2 Then, with probability at least 1 - 8, given sample-labe pair (x,r) r). we have
[f(: 0 (())) ======--
1 L
log
+
+
p4/3ml log 11/6 11)m)))
1.2k1
Pv m
Proof. The LHS of the inequality could be written as
[f 0) <1f(x; 0) f(x; 0 (0)) (V (Vo f(x; 0 (())) ) )19)}
f=; (0)) + (Von ) o(0)))
Here, we could bound the first term on the RHS with Lemma D.7 second term, and recalling ||e
Applying Lemma D.8 on the
g(0) 112 S w, would give
[s( 0)1 < 2
V の ((; 00)
((0) 12+
O(w 1,2 m log (m) 110 10)
2 OL)) 10 o ( 2 + O(L2 mm log((m)) 12)
Then, applying the conclusion of Lemma D.6 would lead to
33
(0(
k3
(s 0) 2
log m
OT? m log(m))
log m)
p/m
Pvm
13 =2+ (
I.2 p//3m
log m
+0
log
11/6 (m)
=
p.m
31

---

Lemma D.6 (Theorem from (3). For any 0 < 1,0 I O Given the past records
PK-1, suppose m. Mh, satisfy the conditions in Theorem 5.2 we could have
then with probability at least 1
1. [()) & & after J iterations of GD.
2. For any [J] (10 | < O
A-a
log m
pym
In particular, Lemma abovv above provides the convergence guarantee for f(; after certain rounds of GD training on the past records PR-1-
Lemma D.7 (Lemma 4.1 in /6))3/2)
Assume
constant w such that
[log(TnI: 3/2g,_3//( (8)]
O(I m| m and training samples.
With randomly initialized ( for parameters 0, e' satisfying ||0 e Il. ll e e S w. we have
(a:; 0) f(x;; 0') (Vor (ax; ), 0')1 O(w 1, m log(m)) with the probability at least
0'1
Lemma D.8. Assume m, m7.J satisfy the conditions in Theorem 5.2 and g is randomly initialized. Then, with probability at least 1 8 and given arm | we have
1. [x; 0 (0)) 2
2. V f(; 0 0 - O()).
Proof. The conclusion (1) is a direct application of Lemma 7.1 in [3. Suppose the parameters of the L-layer FC network
(0....., (.). For conclusion (2), applying Lemma 7.3 in 3 for each layer 0, {0I..... O we have
12 where D is the diagonal matrix corresponding to the activation function. Then, we could have the conclusion that
Ve, / fa; 0 (
DL-1..... Di-10:41) (1++10++1.. -.,))
O(VL).
g f(x; 0 (0))
Vo, @ )1 O(L).
V
[E(Z)
Lemma D.9 (Theorem 5 in (3). Assume J satisfy the conditions in Theorem 5.2 and O (0) being randomly initialized. Then, with probability least - 8, and for all parameter O such that | 0 12 S w. we have
(V)f((; of f 00
1/3 (Vlogmm)
Lemma D.10. Assume satisfy the condition in Theorem 5.2 For notation brevity, suppose the training comple-label pairs are (x..rr)re(4 With the probability least 5, we have
3Lv2k
Σ lf(x,;0()) - Σ 0 -r/+ TEIM]
TE(k]
Proof. With the notation from Lemma 4.3 in []], set R ka log(m)) V R², and V2rk" considering the loss function to be ((0) :- Er
LR Then,
r- would complete the proof. D
Lemma D.11. Consider randomly initialized L-layer ReLU fully-connected network f(; 0o). For any 0 &a 1,0 p O Let there be two sets of training samples Pk, Pk, with the unit-length and the p-separateness assumption, and let be the trained parameter on Ps: while 0' the trained parameter Pt-- Suppose the conditions in Theorem 5.2 are satisfied. Then, with probability at least 1 8, we have
0') < (1+ 0
O KL log lmn))))))) O Pym
LL log(m)) (m) + 0 1/33
k2 11/6
11/6 11/6mm)
p1/3ml/6
when given new sample E Rd.
32

---

Proof.
First, based on the conclusion from Theorem 1 from
3 and regarding the samples, the
trained the parameters satisfy ||0 0lll,, l|o' Oollz
O ka
log(m)) where dg is the pym
randomly initialized parameter. Then, we could have
Vo Vof( 12 - (a: 00)ll2 + (Voo((2;0) Vor
(1 + 0 L log (m)),
))
(L)
/1/3m1/6
w.r.t. the conclusion from Theorem and Theorem 5 of 3 Then, regarding the Lemma 4.1 from would have
ff 0) f(z; (V f(:; 0') s 1( V /llgmm)) ||0 - 0'1l2.
Therefore, the our target could be reformed as
(f 0) f(x; 0') S Vo (2; 02) + O(w m loggmm)) 110 0'
(1 1 O KL log logg/ ( OLL) w O 3//4///33 2 log(m)
p'/3m
Substituting the w with its value would complete the proof.
Corollary D.12. Following similar settings in Lemma D.17 consider randomly initialized L-layer fully-connected network [(:0g) with Sigmoid activation. For any 0 &2 S 1, < p S O. 3. Let there be two sets of training samples Pk, Pk with the unit-length and the p-separateness assumption, and let f be the trained parameter Pk while O' is the trained parameter 'P Suppose the conditions in Theorem 5.2 are satisfied. Then, with probability at least 5, we have
KL L (m)) pm3 ))
kt L log 11/6 11m(mm)
[(x; fx; 0') s (1+0) 0( -
00
log(m)) + +0 Pvm
p4/3m
when given a new sample x E Rd.
Proof. This corollary is an intuitive extension of Lemma D.II Since the result from Theorem I of 3 also applies to Lipschitz-smool (i.e., Sigmoid) activation functions, combining the proof of Lemma D.Il and the result from Lemma in [7 will give the conclusion.
D.5 Regret Bound for Uniform Sampling
Lemma D.13 (Regret Bound for the Uniform Sampling Approach). When applying the uniform
sampling as in most meta-learning frameworks, we denote the corresponding sampled task series as
Py (K). We will have Ry (K) BTTP(TT) awDT I(T,
I(T, (TT ((K)+)))
where
( refer to the peela-parameters trained with uniform sampling. With ( - (K)) S w.
have the regret bound for the uniform sampling as
Ra, (TTP(T))END)
L(x; , (k)).)))
LF
I Vmyls. w O(w4/3 1 my log(m))) + +06
<min foinfooKLst K3/3 L 11/3
v log(m5)
LF mF
1/6
m
Proof. Here, for the simplicity of notation, we denote I(T, O), and neglect the expectation terms. Note that the difference between adapted meta- veta-parameters and the original meta-parameters is
33

---

small enough and can be well-bounded. We will then have
(R(K)= = -BT-P(T),
- [(x:I(T, )
= (K) 2(0 (10( -
where the two sets of meta parameters are trained with uniformly sampled tasks and the optimal tasks, and @ is used to denote the adapted mela-parameters I(T, )) for simplicity. With any convex loss function (e.g., L2 loss or cross-entropy loss) under the over-parameterization settings, we will have the generalization loss being almost convex w.r.t. the meta meta-parsmeters as in Lemma D.14 which leads to
2 (K) - -6 s (Vo (K)
(K) -6(K) +e ),
Vg 1 (K) ②
(K)
(k),
1|2 +
* Vo )l2110 (K)*
112 + 71 O my Lz) te
12 Mmyly O(w 4/3
1,-
my log(ms)) +0(1
mF
2 0 Khr++
11/3 K4/3 LF
Mog(mF)
L5 V
m
mr
m ( - 2(0 (K),
S min fo KLb
{o(KLo
K4/3 11/3
v /log(m)) (mF)
Top mF
1/6
m
where O(w4/3 Lie mF (mg) O, and |10(K), ( 112 < Here, the first in- equality is due to Lemma D.14 and the convexity of the loss function. The third inequality is due to the upper bound for meta-model gradients (Lemma D.15). The (i) is due to Lemma D.16 and sufficiently small learning rate 1n S 0
(K)
Based on Lemma D.15 we will have
(J), l|,, V[ 0% ll S OVVLLLF). Since we have 7), 1/2 S ( start- k
ing from randomly initialized e the parameter shift caused by GD can be upper bounded by The implication (iii) is because the loss function ((::))
(K(K** (K) l|2 S w O(K
Lx my
has the value range [0, 1].
Here, we notice that the RHS of the regret bound in Lemma D.13 has two terms. Although the second term can be reduced to O(1) with sufficiently large meta-model width m, > (Poly K, L, p ))) the first term tends to grow along with more iterations K and the larger meta-model width m.. The reason is that the radius for the parameter shift during meta-training w can be as large as O /
which means that it cannot cancel out the effects of gradient norms, which have the order of O (VMF). In this case, we will not able to include a my term to the denominator to scale down the regret with my, and make the upper bound narrower than 1.
Lemma D.14. Given an arbitrary sample a and label, let ž(@) = L(x:; O). Suppose my, 7/, 772
satisfy the conditions in Theorem 5.2 With probability at least 1 1- O(K -xxpp cxpl-s((m=='
over randomness of θ (0) for all k E [K], and e O' satisfying ||@ - (0)) l| S w and ||
θ (0)) I w with
OL7 (log m=) 3/2), it holds uniformly that
Ž Σ(O')= s (Ve tc.
with 1(34/3 L3 log mF)) being small constant.
proof. This proof follows an analogous approach as the proof of Lemma 4.2 in [ Let (
be the derivative of E with respective to F(æ; +). Then, it holds that |V=ī(e')) < O(1) based on
34

---

Lemma D.15
Then, by convexity of we have
((0))-((0)
@
V>L(o) (F(x; F(;;))))
-
(VF(x; (), - -F{(; () 6' -
m (Ve(()), - - 13
2 ()) @' 0 -
where (i) is to the convexity of the loss function L, (ii) is an application of triangle inequality, and (iii) the application of and Lemma 1.16 Finally, denoting e = O / log my) will complete the proof.
Lemma D.15. Suppose m,, 171, 12 satisfy the conditions in Theorem 5.2 With probability at least
2/3 1 1-O(KLy) cxp( 2mm
over the random initialization, 2 satisfying | - || S 9/2 [log m -3), it holds uniformly that with w - O(.5
Ly)) L,y)
VeF((; +)) S (01000mmmm myLr);
VoL(z; O) S O(v m))L)
Proof. This lemma is direct application of Lemma 9 of [4] and Lemma B.2, B.3 [1].
Lemma D.16. Suppose my. -, 1/2 satisfy the conditions in Theorem least OKKT) exp( 2xp(-S(mmmw2131 Lr)), for all t E [T], E [k). O θ (or O O' satisfying
With probability at
9/2 [log m it holds uniformly that | - 12,1 - e(() 12 S w with w S (
[F O) F(x; O') (e 0' θ 0`\l | S /3 my (og(og(m=)))
O'112.
Proof. The proof for this lemma directly follows the proof of Lemma 4.1 in and Lemma 7 in
35


Reviews:
[{"review_id": "wwYFWuiE4z", "reviewer": "Reviewer_XGJX", "summary": "This paper proposes to adaptively sample the meta-training tasks by optimizing the task scheduling strategy based on the status of the meta-model. The proposed method treats task scheduling as a contextual multi-arm bandit problem with a reward function balancing the exploitation and exploration. The authors provide theoretical analysis about the regret bound of the proposed method and conduct experiments on real data sets to show the effectiveness.", "questions": "* How is the K-round regret bound in Theorem 4.2 compared with the existing work?\n* How is the performance of the proposed method compared with the existing method when the data is noise-free and unskewed?", "limitations": "The authors discuss the limitation in the appendix.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "**DISCLAIMER:** I have not checked the proof thoroughly and cannot verify the correctness of the theorems.\n\n* The presentation of the paper is clean and clear.\n* It seems to be novel to formulate the curriculum learning as a contextual bandit in the context of meta-learning.", "weaknesses": "* The authors claim the proposed method can deal with the data scarcity problem at the early stage of meta-learning. However, I cannot further elaboration anywhere in the paper nor any experimental results supporting this claim.\n* Since the proposed method involves extra computation efforts, the quantitative comparison of computation cost is not included in the experiment results.\n* If the proposed method outperforms the existing method, especially when the data is noisy and skewed, the authors should include experiments with different levels of noise $\\epsilon$ and different levels of skewness to show the trends of improvements.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the valuable questions and comments. Here, we will try our\nbest to address the questions and concerns in the form of Q&A. Since we are unable to submit the\nimproved manuscript based on reviewers’ comments, we will describe these modifications on the current\nmanuscript instead. **To better answer reviewer’s questions, we also include additional experiments in\nthe 1-page PDF file.** *If you have any additional questions or comments, please kindly let us know.\nThank you!*\n\n**Q1: How is the K-round regret bound in Theorem 4.2 compared with the existing work?**\n\nTo the best of our knowledge, this is the first work to incorporate bandit ideas for the task scheduling problem in meta-learning, and it is also the first work that introduces the performance guarantee for the task scheduling problem. \n\nMeanwhile, instead of our carefully designed modeling, if we directly apply the existing bandit works to the task scheduling problem, we will (1) introduce additional assumptions for the sake of analysis (e.g., Lin-UCB [1] assumes the reward mapping function $h(\\cdot)$ is linear), or (2) introduce additional terms to the regret bound (e.g., Neural-UCB [2] will need an additional $\\tilde{d}$ in the regret bound, which is the effective dimension of the related NTK matrix).\n\nIn our discussion in the main body (lines 266-269), we also show that the uniform sampling approach can lead to $\\mathcal{O}(1)$ regret under the worst-case scenario, which is significantly worse compared with our derived regret bound (Eq. (10)).\nPlease also refer to our discussion on the regret bound (lines 261-276 of the main body).\n\n**Q2: How is the performance of the proposed method compared with the existing method when the data is noise-free and unskewed?**\n\n\nPlease refer to Table 2 (Subsec. B.1.1) in the Appendix for the experimental results when the data is noise-free and unskewed. We show that BASS can still achieve the best performance compared with baselines. Please also see the results from Table 1 (Appendix) for the experimental results with different noise levels.\n\nMeanwhile, we also include the experiments with different levels of skewness. Please see Table 1 in the uploaded PDF file for details. Here, we see that with less skewness levels (the skewness level reduces from Setting 1 to Setting 3), the accuracy of BASS as well as the baselines will continue to increase, and BASS can still maintain the best performance.\n\n\n\n\n\n\n\n**Q3: The claim of the data scarcity problem?**\n\nIn the abstract and the conclusion, we mention that \"BASS can deal with the data scarcity problem at the early stage of meta-training, and plan for the future meta-training iterations\".\nHere, we mean that, due to the insufficient knowledge regarding the task and data distributions in the early stage of meta-training, existing greedy meta-task schedulers may lead sub-optimal meta-models, since they tend to make scheduling decisions solely based on the limited existing knowledge, without performing exploration for potential benefits. \nAlternatively, with the exploration strategy, our method can be less likely to be significantly affected by the insufficient knowledge issue (e.g., the skewed data distribution example).\nThat is why we need exploration for task scheduling, especially during an early stage of meta-training when the learner's knowledge is limited.\n\nIn the experiments, we have shown BASS can achieve the same accuracy as baselines using less number of training round (Figure 4, main body). This fact can be interpreted as the support for the exploitation-exploration strategy used in our approach, which is able to maximize the long-term benefit.\n\n\nSince this narrative may confuse the reviewer and the future readers,\nwe have updated the abstract as well as the conclusion sections for better presentation, by mentioning the importance of exploration at the early stage of meta-training, due to the insufficient knowledge with respect to the task and data distributions.\n\n\n\n**REFERENCE**\n\n[1] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff\nfunctions. In AISTATS, pages 208–214, 2011.\n\n[2] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration,\n2020."}, {"review_id": "O78SfBXmC2", "reviewer": "Reviewer_nu6A", "summary": "This paper proposed a task scheduling framework BASS based on the status of meta-model based on contextual bandits setting. BASS addressed the performance bottleneck of meta-models by balancing exploitation and exploration and handled the data scarcity in the early stages of meta-training iterations with planning future meta-learning iteration strategies. The experimental and theoretical analysis showed the effectiveness of BASS.", "questions": "1 [Refer to Weakness 1] How about the assumption on various datasets? Does the assumption independent of each other? Will the results vary with different initialization? \n\n2 [Refer to Weakness 1] What are the constraints or the policy of batch size B? How will the performance vary with different settings of B?\n \n3 [Refer to Weakness 2] How about the bound of regret? How about the distribution of arms? Whether the performance change with different settings/assumptions of regret/arms?\n\n4 [Refer to Weakness 3] How about the performance on various kinds of datasets? For example, image dataset, textual dataset, vision dataset, or dataset represented by deep features. Furthermore, the data dimension, data sparsity, even the image resolution may also affect the performance.", "limitations": "The target problem is interesting and worth studying. However, the detailed explanation of theory analysis needs to be clarified, and more experiments should be conducted to verify the superiority of the proposed method.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1 [Writing & Presentation] This paper is well-written and easy to follow. \n\n2 [Motivation] The previous work about task schedulers aimed to improve meta-training strategies based on the various pre-defined criteria and assumptions, ignoring the global knowledge. It may result in a sub-optimal meta-model affected by noise perturbation or skewed task distributions. Motivated by this limitation, the authors proposed a novel framework to solve the meta-learning task scheduling problem. \n\n3 [Contribution] Different from the existing methods that exploit the current/local knowledge for greedy scheduling, the proposed method leveraged a novel method to adaptively learn the relationship between the meta-model parameters and meta-model generalization ability. \n\n4 [Experiments] The experiments demonstrated the effectiveness of BASS compared with seven strong basslines on three real datasets. \nThe experimental results showed superiority in terms of accuracy and efficiency. Besides, BASS can explore the ‘tail’ task and enjoy a good performance in the ensemble inference setting, which further enhanced the generalization ability of meta-learning models.", "weaknesses": "1 [Algorithm] In Algorithm 1. How about the detailed setting of the initialization? Intuitively, the meta-model parameters would rely on the various data distributions. \n\n2 [ Theory] In Section 4, the $k$-iteration regret is the assumption of Theorem 4.2. However, the detailed setting of regret was not given. For example, the explanation of independence of regret bounds is not well illustrated. \n\n3 [Experiment] In Section 5.1, the experimental analysis was on three datasets, the Drug dataset is a textual dataset, and both ImageNet and CIFAR are visual/image datasets. Since the proposed method focused on the generalization ability, it would be better to verify the performance on various categories of datasets. \n\n4 [Experiment] In Table.1, the performance for 1-shot of BASS increased slightly. Does it mean the meta-model is invalid? If so, what is the main point of BASS leading to this result?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the valuable questions and comments. Here, we will try our best to address the questions and concerns in the form of Q\\&A. Since we are unable to submit the improved manuscript based on reviewers' comments, we will describe these modifications on the current manuscript instead.\n**To better answer reviewer's questions, we also include additional experiments in the 1-page PDF file.**\n*If you have any additional questions or comments, please kindly let us know. Thank you!*\n\n**Q1: How about the assumption on various datasets? Does the assumption independent of each other? Will the results vary with different initialization?**\n\nAnalogous to other bandit-based works (e.g., Neural-UCB), in this paper, our regret bound considers the worst-case scenario. Therefore, as long as the separateness assumption (Assumption 4.1) is satisfied, we do not impose additional assumptions on the data or task distribution.\nMeanwhile, the separateness assumption is applied because we need the training data of the scheduler to be non-degenerate, in order to derive the performance guarantee.\nPlease also see lines 244-254 (main body) as well as the Appendix Section C for the discussion on Assumption 4.1.\n\nFor the meta-model, we first consider it to be a $L_{\\mathcal{F}}$-layer fully-connected (FC) network (of width $m_{\\mathcal{F}}$) with Gaussian initialization for the theoretical analysis (lines 237-239). In particular, we follow the settings in [1] for the Gaussian initialization of weight matrices. \nFor the weight matrix elements in meta-model's first $(L_{\\mathcal{F}}-1)$ layers, we draw each of them from the Gaussian distribution $\\mathcal{N}(0, 2/m_{\\mathcal{F}})$. Then, for the weight matrix elements of the last layer ($L_{\\mathcal{F}}$-th layer), we draw each of them from the Gaussian distribution $\\mathcal{N}(0, 1)$. \nMeanwhile, as we mentioned in lines 239-240 of the main body, our results can be generalized to other meta-model architectures (e.g., CNN and ResNet). For those architectures, we also can apply analogous Gaussian initialization procedures. Please see the parameter initialization details for these two architectures in Appendix Section B and Appendix Section C of [1].\n\nTo avoid possible confusion from the readers, we have added the above details to the Appendix.\n\n\n\n**Q2: What are the constraints or the policy of batch size B? How will the performance vary with different settings of B?**\n\nFor the regret bound, we do not have constraints for $B$. Instead, for the second term of the regret bound (RHS of Eq. 10), we see that the term $B$ is in the numerator. Since we are considering the worst-case scenario, with larger $B$, the bandit-trained meta-parameters ($\\mathbf{\\Theta}^{(K)}$) will be more likely to deviate from the the optimal ones ($\\mathbf{\\Theta}^{(K), *}$), which may lead to a larger regret bound.\n\nHere, we include additional experiments with different batch sizes $B$, in comparison with ATS and the uniform sampling approach. \nThis is because ATS is generally the second-best method.\nPlease see Table 2 in the uploaded PDF file for detailed settings and results. \nBased on the results, we see that with larger $B$ values, the accuracy of BASS as well as the baselines will generally improve, and BASS still maintains the best performance.\n\n\n**Q3: How about the bound of regret? How about the distribution of arms? Whether the performance change with different settings/assumptions of regret/arms?**\n\n\nAs we have discussed in the answer to Q1, since the data / task distributions are unknown, our regret bound considers the worst-case scenario. In this case, as long as the conditions in Section 4 are met, our derived regret bound can deal with various arm / task / data distributions. \n\n\n\n\n**Q4: Experiment results for 1-shot settings?**\n\nFirst, we would like to recall that under the 5-shot settings where information for task adaptation is relatively sufficient, our proposed BASS can achieve considerable improvements over the existing baselines, which shows the effectiveness of our proposed approach.\n\nThen, with the accuracy results and the corresponding standard deviation results, we would like to note that our proposed BASS can achieve statistically comparable (or better) performances, in comparison with baselines. This is because under the 1-shot settings, regardless of the scheduling approaches, the meta-learning models will have relatively insufficient information regarding the task adaptation, which would lead to unsatisfactory performances and make the 1-shot settings more challenging. Meanwhile, our improvements over the uniform sampling approach also support the effectiveness of our task scheduling strategy.\n\nIn particular, to deal with the challenging 1-shot settings, we offer a practical solution in our case study (Subsec. 5.3, main body) by utilizing the ensemble inference to improve the meta-model's generalization ability. In this way, our proposed BASS can achieve more significant advantage over the baselines. \n\n\n\n**Q5: How about the performance on other datasets with different specifications?**\n\nThank you for your suggestion, and we agree that data set specifications (e.g., the image resolution) can considerably affect the model performance. Therefore, we include additional experiments on the \"DomainNet\" data set [Moment Matching for Multi-Source Domain Adaptation (ICCV 2019)], which has a higher resolution ($128\\times128$) for the image data. \n\nPlease see our general response for the detailed experiment settings (bullet point 6).\nFor experimental results, please see Table 5 in the uploaded PDF file. Here, we see that with a higher image resolution of the \"DomainNet\" data set, BASS can still maintain the best performance compared with the baselines.\n\n\n\n\n\n\n\n**REFERENCE**\n\n[1] Allen-Zhu, Zeyuan, Yuanzhi Li, and Zhao Song. \"A Convergence Theory for Deep Learning via Over-Parameterization.\" arXiv preprint arXiv:1811.03962 (2018)."}, {"review_id": "b9MELVjob4", "reviewer": "Reviewer_Z8mk", "summary": "The paper presents a task scheduling approach in meta-learning under a contextual bandit framework. The proposed methodology, named BASS, treats each meta-learning task as an arm, prioritizing the selection of these arms according to exploration and exploitation scores. These scores are computed by a trainable neural network with the input being the meta-model's status. The authors provide theoretical proof demonstrating the convergence of the regret bound. Empirical results indicate that BASS outperforms baselines in meta-learning tasks, particularly those involving noisy or skewed datasets.", "questions": "**Q1.** The explanation provided from Line 179 to Line 185 is somewhat unclear. Could the authors provide further clarification on this matter?\n\n**Q2.** The notations used in Line 108 and Line 326 appear to be inconsistent. Could these be typos?\n\n**Q3.** It's great that BASS employs all parameters of the meta-model to infer its status. However, BASS uses average pooling to reduce millions of parameters to about 50. Can this average-pooled feature truly encompass all necessary information about the status of the meta-model?\n\n**Q4.** In relation to Q3, the use of average-pooling seems to be due to the high dimensionality of the input. Have the authors considered employing other encoding techniques, such as an MLP with smaller hidden layers?", "limitations": "The authors have adequately addressed their limitations regarding the computational cost and the marginal improvement for standard dataset in the appendix.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "**S1. Clarity**\n\nThe authors present their work with high clarity. The notations, a critical aspect in avoiding confusion in this complex subject, are well-defined. Also, the authors have strategically placed numerous remarks in the main section, which significantly assist readers in comprehending the principal concepts.\n\n**S2. Advantages from the use of bandits**\n\nThe application of the contextual bandit in place of the previously used greedy update offers multiple strengths.\n-\tIt eliminates the need for unstable bi-level optimization\n-\tIn naturally manages the balance between exploration and exploitation. The way the extrinsic and intrinsic rewards are formulated is both intriguing and intuitive. Notably, the exploration factor, which takes into account both task uncertainty and difficulty, stands out as a significant advantage of this work.\n-\tAs a consequence of the bandit application, the regret bound can be theoretically limited. The authors have put in considerable effort the substantiate their theoretical analysis in the appendix.", "weaknesses": "**W1. Experimental results**\n\nWhile the proposed method demonstrates significant enhancements over baseline models for noisy or skewed training tasks, it appears to yield marginal or negligible improvement on standard datasets, as acknowledged by the authors. Incorporating additional data regarding computation cost could provide valuable insight, especially when comparing the effect of noise or skewness on different datasets and assessing the increased computation demand posed by BASS.\n\n**Minor comment** \n\nIt is recommended to incorporate the 'Related Works' section into the main body of the manuscript instead of including it in the appendix. Given that all submissions adhere to the same page limit, placing this section in the appendix can disrupt the contextualization of the work within the existing literature.\n\n**Acknowledgment Following Rebuttal**\n\nThe author's rebuttal successfully addressed concerns about the experiment. The inclusion of additional results on average-pooling is particularly noteworthy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the valuable questions and comments. Here, we will try our best to address the questions and concerns in the form of Q\\&A. Since we are unable to submit the improved manuscript based on reviewers' comments, we will describe these modifications on the current manuscript instead.\n**To better answer reviewer's questions, we also include additional experiments in the 1-page PDF file.**\n*If you have any additional questions or comments, please kindly let us know. Thank you!*\n\n\n**Q1: Could the authors provide further clarification on Line 179 to Line 185?**\n\nRecall that for task (arm) $\\mathcal{T}\\_{k, i}$, the exploration module $f_{2}$ takes two gradient vector $\\nabla_{\\theta} f_{1}(\\chi_{k, i}^{s})$, $\\nabla_{\\theta} f_{1}(\\chi_{k, i}^{q})$ as the input. \nAnd this paragraph (lines 176-185, main body) aims to show our intuition of this design.\n\nHere, we show two cases as the examples:\n(1) The variance of the corresponding data distribution $\\mathcal{D}\\_{\\mathcal{T}\\_{k, i}}$ is high. In this case, the support set $D\\_{k, i}^{s}$ and the query set $D\\_{k, i}^{q}$ can be considerably different, which makes the corresponding arm contexts $\\chi\\_{k, i}^{s}$, $\\chi\\_{k, i}^{q}$ divergent. As a result, the gradient vectors $\\nabla_{\\theta} f_{1}(\\chi_{k, i}^{s})$, $\\nabla_{\\theta} f_{1}(\\chi_{k, i}^{q})$ will likely be distinct from each other. \n(2) Alternatively, suppose the support set $D_{k, i}^{s}$ and the query set $D_{k, i}^{q}$ are not significantly distinct (which means that $\\chi_{k, i}^{s}$ does not significantly differ from $\\chi_{k, i}^{q}$). Then, if these two gradient vectors still tend to change dramatically when adapting to task $\\mathcal{T}\\_{k, i}$, we can consider that the exploitation model $f_{1}$ is not well adapted to this task $\\mathcal{T}\\_{k, i}$.\n\nFor the above two cases, we give two scenarios where more exploration is needed for the task $\\mathcal{T}\\_{k, i}$, and this is to help $f_{1}$ better learn the reward for this task.\nIn this case, the information from these two gradient vectors can help us make better exploration decisions, since they can encode information regarding the dynamics of the meta-model parameters and the exploitation model $f_{1}$ parameters. And we apply the exploration model $f_{2}$ to learn from these two gradient vectors.\n\nWe have also updated this part in the manuscript for better clarify and presentation.\n\n\n\n\n**Q2: The notations used in Line 108 and Line 326 appear to be inconsistent. Could these be typos?**\n\n\nThank you so much for spotting this typo, and it should be $\\mathcal{P}(\\mathcal{T})$. We have updated the manuscript, and will also double-check the manuscript for other potential typos / mistakes.\n\n\n\n\n\n\n\n**Q3: BASS uses average pooling to reduce millions of parameters to about 50. Can this average-pooled feature truly encompass all necessary information about the status of the meta-model?**\n\n\nHere, we include additional experiments with different levels of average pooling, such that after the average pooling, the input dimensionality will fall into $\\\\{20, 50, 100, 500\\\\}$. \nPlease see Table 3 in the uploaded PDF file for the experiment results. \nHere, overly small dimensionality of the average-pooled vector representation (e.g., 20) can lead to the sub-optimal performance of the BASS framework. Meanwhile, we see that setting the dimensionality to 50 can generally lead to good performance, which means the average pooling method can effectively preserve the characteristic of meta-parameters.\n\n\n\n**Q4: Have the authors considered employing other encoding techniques, such as an MLP with smaller hidden layers?**\n\n\nThank you for your suggestion, and we include additional experimental results using MLP to map the original context into the lower dimensional space instead of using our proposed average pooling (Remark 3). \nPlease see Table 4 in the uploaded PDF file for experiment results. \nHere, we use the one-layer MLP with the ReLU activation to embed the original meta-parameters to the low-dimensional vector representations. We can see that the MLP-based method can indeed lead to some performance improvement. But in general, the performance difference between MLP-based embedding and the average-pooling vector representation is subtle.\n\n\nMeanwhile, we also note that the MLP-based mapping approach is considerably more time consuming compared with the average pooling approach, since we also need to train the additional embedding layer, which has a large number of trainable parameters.\nAlternatively, the computation cost of the average pooling is trivial.\n\nWe have also included these experiment results in the paper Appendix.\n\n\n\n**Q5: Running time results?**\n\nPlease refer to the running time results shown in Figure 1 of the PDF file. \nHere, we include the running time comparison results compared with ATS on 6 different settings.\nThis is because ATS is generally the second-best task scheduling method, and it is also the only baseline method that can achieve adaptive task scheduling in meta-learning. \nFrom the figure, we can observe that BASS can achieve significant running time improvements, and take as little as 50\\% of the ATS's running time.\n\n\n**Q6: Move \"Related Works\" section to the main body?**\n\n\nThank you for the suggestion, and we agree with the reviewer that the \"Related Work\" should be moved to the main body for the sake of consistency. Therefore, we have updated the manuscript and moved this section to the main body.\n\n\n\n\n\n"}, {"review_id": "ryGGTMcaDq", "reviewer": "Reviewer_zT5d", "summary": "This paper considers the problem of task scheduling in meta-learning. Under the gradient-based meta-learning framework, the authors propose BASS, which uses contextual bandits parameterized by neural networks. The tasks in each batch (arms) are selected in an optimistic manner, with the reward estimated using a validation set and its uncertainty estimated using errors in the neural network predictions. A theoretical analysis of the regret is done in the overparameterized neural network setting. Experiments are done on Mini-ImageNet, CIFAR100, and Drug datasets, showing competitiveness with SOTA and outperforming them when there is task imbalance.", "questions": "1. How does the computation time of BASS compare to the other algorithms?\n2. How would BASS scale with the size of the classifier, e.g. if we were to meta-learn an initialization for 100 layers?", "limitations": "The paper proposes a new meta-learning algorithm, so I think the authors are ok in not including a broader impact section. The authors do adequately discuss limitations in the appendix.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors provide detailed mathematical motivation for their algorithmic choices.\n2. The use of contextual bandits for meta-learning is novel, as far as I know.\n3. The authors provide theoretical analysis of their algorithm.\n4. Experiments are done on a range of datasets, with ablations.\n5. BASS is able to lead to statistically significant improvements when there is task imbalance and is competitive otherwise.", "weaknesses": "1. There is no discussion of the computational burden of BASS. It would strengthen the work to provide wall clock times or plots of the performance as a function of time.\n2. It is not clear how BASS would scale, as it takes the parameters of one neural network as input into another neural network.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the valuable questions and comments. Here, we will try our best to address the questions and concerns in the form of Q\\&A. Since we are unable to submit the improved manuscript based on reviewers' comments, we will describe these modifications on the current manuscript instead.\n**To better answer reviewer's questions, we also include additional experiments in the 1-page PDF file.**\n*If you have any additional questions or comments, please kindly let us know. Thank you!*\n\n\n**Q1: Running time of BASS?**\n\nThank you for the feedback.\nWe have included additional running time comparison results, compared with ATS [1] on 6 different settings.\nThis is because ATS is generally the second-best task scheduling method, and it is also the only baseline method that can achieve adaptive task scheduling in meta-learning. \nPlease refer to the running time results shown in Figure 1 of the PDF file. \nFrom the figure, we can observe that BASS can achieve significant running time improvements, and take as little as 50\\% of the ATS's running time.\n\nWe have also updated the manuscript Appendix by adding these results.\n\n\n\n\n\n**Q2: How would BASS scale with the size of the classifier?**\n\n\nIn general, it can be challenging to train large meta-models.\nIn this case, we propose the approximation method by applying the average pooling to reduce the bandit scheduler input in practice (Remark 3).\nThis method is simple, but it can preserve the characteristics of meta-parameters, and we can adjust the converted dimensionality based on the complexity of meta-models. \n\n\nPlease see our additional experiment result in Table 3 of the uploaded PDF file for reference.\nHere, we see that setting the dimensionality to 50 can generally lead to the good performance, and the BASS framework can also deal with higher dimensional average-pooled vector representations (e.g., dimensionality $= 500$). \nMeanwhile, for the experiments in the paper, the effectiveness of BASS is tested on two different types of meta-models (Fully-connected networks for the Drug data set, and CNNs for the Mini-ImageNet and CIFAR-100 data sets).\nMeanwhile, compared with the state-of-the-art baseline ATS, we can achieve effective task scheduling with relatively small computational cost. Please also see the results of running time for reference (Figure 1 in the PDF file).\n\n**REFERENCE**\n\n[1] Huaxiu Yao, Yu Wang, Ying Wei, Peilin Zhao, Mehrdad Mahdavi, Defu Lian, and Chelsea Finn.\nMeta-learning with an adaptive task scheduler. Advances in Neural Information Processing Systems,\n34:7497–7509, 2021."}, {"review_id": "uIfyG49mOb", "reviewer": "Reviewer_ua81", "summary": "This paper proposes scheduling tasks for meta-learning using context bandits.", "questions": "1. What’s the definition of $\\mathbf{\\theta}$ in Equation (7)? Is it $\\theta_1$?\n2. Why not simply use $\\tilde r_{k,i}+\\tilde e_{k,i}$ as the benefit score? In that case, there would be no need to learn $f_2$. Moreover, I believe that, with a little more effort, $f_1$ could be removed either.\n3. Could you please detail the average pooling process in Remark 3?", "limitations": "This work does not involve some potential negative social impacts.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The idea of applying context bandits to select tasks for meta-learning is novel\n2. The experimental results are strong, especially when the task distribution is skewed", "weaknesses": "1. The method is computationally inefficient in two aspects: a) The arm context requires computing both the adapted parameters and the meta-parameters for every task. While some of these gradients can be reused, the computational cost can still be significant as the number of training tasks increases. b) The networks $f_1,f_2$ used to compute the benefit score take parameters as inputs, which is huge in practice. Although, in Remark 3, the authors mention applying the average pooling to reduce the cost, it is unclear how it is done in practice. Moreover, $f_2$ requires computing the gradients of $f_1$ for two different parameter sets.\n2. There is no training time comparison between different methods. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the valuable questions and comments. Here, we will try our best to address the questions and concerns in the form of Q\\&A. Since we are unable to submit the improved manuscript based on reviewers' comments, we will describe these modifications on the current manuscript instead.\n**To better answer reviewer's questions, we also include additional experiments in the 1-page PDF file.**\n*If you have any additional questions or comments, please kindly let us know. Thank you!*\n\n**Q1: What’s the definition of $\\theta$ in Equation (7)? Is it $\\theta_{1}$?**\n\nYes, the $\\theta$ notation here refers to $\\theta_{1}$, and this is because the exploration module $f_{2}$ takes the gradients of $f_{1}$ (with respect to $\\theta_{1}$) as input.\nWe have updated the manuscript for this part to avoid any confusion.\n\n**Q2: Why not simply use $\\tilde{r} + \\tilde{e}$?**\n\n*As we may not fully understand this question, we will really appreciate it if the reviewer let us know whether our initial response below could adequately address your concerns. **If not, please kindly let us know, and we will try our best to make ourselves clear. Thank you!** *\n\nRecall that for an arm (task), we have $\\tilde{r}$ being the output of $f_{1}$, which refers to the estimated arm reward, and it measures the instant benefit (reward) of including this task (arm) into the meta-training. \nThen, $\\tilde{e}$ refers to the corresponding exploration score, and it measures the uncertainty of $\\tilde{r}$. Note that since $\\tilde{e}$ is the output of $f_{2}$, we need the exploration model $f_{2}$ to estimate $\\tilde{e}$ on the fly. In this way, $\\tilde{r} + \\tilde{e}$ will equal to the addition of $f_1$ and $f_2$ outputs.\n\nNext, \nas we mentioned in the paper, we apply $\\alpha\\cdot \\tilde{r} + \\tilde{e}$ to balance the exploitation and exploration, where higher $\\alpha$ values lead to higher levels of exploitation. Meanwhile, $\\alpha$ is also used to balance our two exploration objectives (lines 208-224).\nPlease also refer to the experimental results in Table 3 (Appendix) for the effects of $\\alpha$. Based on Table 3 (Appendix), we can generally choose $\\alpha\\in [0.5, 0.7]$, because in this way we can balance the exploitation-exploration as well as balance our two exploration objectives (lines 83-91, Appendix).\nThis also supports our claim that $f_{2}$ is necessary for our proposed BASS model.\n\n\nFurthermore, we would like to include additional discussions on our adaptive exploration strategy.\nOur proposed BASS adopts $f_{2}$ to adaptively learn the exploration score, which can be either positive or negative. \nHere, the intuition is that the exploitation model (i.e., $f_{1}$) can \"provide the overly high estimation of the arm reward\", and applying the upper confidence bound (UCB) exploration strategy can amplify the mistake, as the UCB is non-negative. \nFor notation simplicity, let us denote the expected reward of an arm $x$ as $\\mathbb{E}[r] = h(x)$, where $h$ is the unknown reward mapping function. The corresponding reward estimation is denoted as $\\hat{r} = f_{1}(x)$ where $f_{1}(\\cdot)$ is the exploitation model. \nWhen the estimated reward is lower than the expected reward ($f_{1}(x) < h(x)$), we will apply the \"upward\" exploration (i.e., positive exploration score) to increase the chance of arm $x$ being explored. On the contrary, if the estimated reward is higher than the expected reward ($f_{1}(x) > h(x)$), we will apply the \"downward\" exploration  (i.e., negative exploration score)  instead to tackle the excessively high reward estimation. \nIn this work, we apply the exploration model $f_{2}$ to adaptively learn the relationship between the network gradients of $f_{1}$ and the reward estimation residual $h(x) - f_{1}(x)$. \nMoreover, we also incorporate the task adaptation difficulty level to the exploration score, for a refined exploration strategy under the meta-learning task scheduling settings.\n\n\nWe have also added the above discussion to the Appendix for readers' reference.\n\n**Q3: Details of the average pooling process in Remark 3?**\n\nAs we have discussed in the paper, since the dimensionality of original meta-parameters could be high, inspired by CNNs, we apply average pooling to embed them into low-dimensional vectors. For instance, suppose the dimensionality of the original meta-parameters is 10,000 and our average pooling step is 100. Here, the first 100 elements in the original meta-parameters will be averaged, and the mean value will be considered as the first element of the average-pooled representation vector. Applying this process for the rest elements in the original meta-parameters, we can obtain the average-pooled representation vector (of the dimensionality $10,000 / 100 = 100$) for the original meta-parameters.\n\n\nWe have also updated the Remark 3 in the manuscript for better presentation and clarity. Meanwhile, please see Table 3 in the uploaded PDF file for reference, where we compare the model performance with different levels of average pooling. \nHere, overly small dimensionality of the average-pooled vector representation (e.g., 20) can lead to sub-optimal performance of the BASS framework. Meanwhile, we see that setting the dimensionality to 50 can generally lead to the good performance, because this very simple yet effective method can preserve the local characteristic of meta-parameters.\n\n**Q4: Running time of BASS?**\n\nIn Figure 1 of the attached 1-page PDF file, we include additional running time comparison results, compared with ATS under 6 different settings.\nThis is because ATS is generally the second best task scheduling method, and it is also the only method among baselines that can achieve adaptive task scheduling in meta-learning. \nCompared with ATS, we can observe that BASS can achieve significant running time improvements, and take as little as 50\\% of the ATS's running time.\n\nWe have also updated the manuscript Appendix by adding these results.\n\n\n"}]

Author rebuttal:

We would like to take the chance to thank all the reviewers for your constructive feedback and detailed comments for our work. Your suggestions can definitely make this paper a more solid one.
Here, to better resolve the questions from reviewers, we have included supplementary experiments to provide the additional reference. **Please see the attached PDF file for details.**
Our experiments include:

1. [Figure 1] We include the running time comparison with the adaptive scheduler ATS, because ATS can generally achieve the best performance among the baselines.
    * We can see that BASS can achieve significant improvement in terms of the running time, and can take as little as 50\% of ATS's running time.
    * (Intuition) This improvement is because our proposed BASS only needs one round of the optimization process to update the meta-model and BASS. 
On the other hand, from Algorithm 1 of the ATS paper [2], we see that ATS requires two optimization rounds to update the scheduler (lines 8-12, Algorithm 1 in [2]) with the temporal meta-model, and the actual meta-model (lines 13-14, Algorithm 1 in [2]) respectively.
(Please also refer to Figure 2 in our paper main body.)

2. [Table 1] We include the experiments with different levels of skewness. 
    * Here, we see that with less skewness levels (the skewness magnitude reduces from Pattern 1 to Pattern 3), the accuracy of BASS as well as the baselines will continue to improve, while BASS still maintains the best performance.


3. [Table 2] We include additional experiments with different batch sizes $B$, in comparison with the ATS and the uniform sampling approach. 
    * Here, we see that with larger $B$ values, the accuracy of BASS as well as the baselines will generally improve, and BASS still maintains the best performance.


4. [Table 3] We include additional experiments with different levels of average pooling, such that after the average pooling, the dimensionality of the pooled vector representation will fall into $\\{20, 50, 100, 500\\}$. 
    * Here, overly small dimensionality of the average-pooled vector representation (e.g., 20) can lead to sub-optimal performance of the BASS framework. Meanwhile, we see that setting the dimensionality to 50 can generally lead to good enough performance.



5. [Table 4] Meanwhile, we also include additional experimental results using MLP to map the original context into the lower dimensional space instead of using our proposed average pooling (Remark 3). 
    * Here, we use the one-layer MLP with the ReLU activation to embed the original meta-parameters to the low-dimensional vector representations. We can see that the MLP-based method can indeed lead to some performance improvement. But in general, the performance difference between MLP-based embedding and the average-pooling vector representation is subtle. 
    * We also note that the MLP-based mapping approach is considerably more time consuming compared with the average pooling approach, since we also need to train the additional embedding layer, which has a large number of trainable parameters.




6. [Table 5] We include additional experiments on the new "DomainNet" data set [1].
    * Within the "real" domain, we filter 100 classes that have at least 600 images. In this way, with each class being a task with 600 images, we will have a total of 100 tasks. 
Compared with image data sets in our paper (Mini-ImageNet and CIFAR-100), we increase the image resolution of "DomainNet" by resizing its images to 128$\times$128 pixels. 
    * Following the settings in our paper, we divide tasks into the portions of 64 : 16 : 20 that correspond to the training set, validation set and the test set respectively. For the few-shot settings, we formulate the problem to be 5-shot, 5-way / 7-way. We include uniform sampling and ATS as baselines, since they generally perform the best among baselines.
    * Here, we see that with a higher image resolution of the "DomainNet" data set, BASS can still maintain the best performance compared with the baselines.


We will also update all these additional experiment results to the paper Appendix.


**REFERENCE**

[1] Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching
for multi-source domain adaptation. In ICCV, pages 1406–1415, 2019.

[2] Huaxiu Yao, Yu Wang, Ying Wei, Peilin Zhao, Mehrdad Mahdavi, Defu Lian, and Chelsea Finn.
Meta-learning with an adaptive task scheduler. Advances in Neural Information Processing Systems,
34:7497–7509, 2021.


Meta-review: Reviewers have reached a consensus and recognise the strengths of these papers as:
* original novel idea
* Clarity of the presentation 
* strong empirical results 

We this recommend this paper to be accepted and we encourage the authors to revise their draft to reflect the discussions of the rebuttal period.
Decision: Accept (poster)