How Does the Task Landscape Affect MAML Performance?
Authors: Liam Collins
Aryan Mokhtari
Sanjay Shakkottai
Venue: ICLR 2022 Submitted (2022)
Keywords: Meta-learning
MAML
multi-task linear regression
two-layer neural networks

Abstract: Model-Agnostic Meta-Learning (MAML) has become increasingly popular for training models that can quickly adapt to new tasks via one or few stochastic gradient descent steps. However, the MAML objective is significantly more difficult to optimize compared to standard non-adaptive learning (NAL), and little is understood about how much MAML improves over NAL in terms of the fast adaptability of their solutions in various scenarios. We analytically address this issue in a linear regression setting consisting of a mixture of easy and hard tasks, where hardness is related to the rate that gradient descent converges on the task. Specifically, we prove that in order for MAML to achieve substantial gain over NAL, (i) there must be some discrepancy in hardness among the tasks, and (ii) the optimal solutions of the hard tasks must be closely packed with the center far from the center of the easy tasks optimal solutions. We also give numerical and analytical results suggesting that these insights apply to two-layer neural networks. Finally, we provide few-shot image classification experiments that support our insights for when MAML should be used and emphasize the importance of training MAML on hard tasks in practice.

Under review as a conference paper at ICLR 2022
How DOES THE TASK LANDSCAPE AFFECT MAML PERFORMANCE?
Anonymous authors Paper under double-blind review
ABSTRACT
Model-Agnostic Meta-Learning (MAML) has become increasingly popular for training models that can quickly adapt to new tasks via one or few stochastic gradient descent steps. However, the MAML objective is significantly more dif- ficult to optimize compared to standard non-adaptive learning (NAL), and little is understood about how much MAML improves over NAL in terms of the fast adaptability of their solutions in various scenarios. We analytically address this issue linear regression setting consisting of a mixture of easy and hard tasks, where hardness is related to the rate that gradient descent converges on the task. Specifically, we prove that in order for MAML to achieve substantial gain over NAL, (i) there must be some discrepancy in hardness among the tasks, and (ii) the optimal solutions the hard tasks must be closely packed with the center far from the center of the easy tasks optimal solutions. We also give numerical and analytical results suggesting that these insights apply to two-layer neural networks. Finally, we provide few-shot image classification experiments that support our insights for when MAMI should be used and emphasize the importance of training MAML on hard tasks in practice.
INTRODUCTION
Large-scale learning models have achieved remarkable successes in domains such as computer vision and reinforcement learning. However, their high performance has come the cost of requiring huge amounts of data and computational resources for training, meaning they cannot be trained from scratch every time they are deployed to solve a new task. Instead, they typically must undergo a single pre-training procedure, then be fine-tuned to solve new tasks in the wild.
Meta-learning aims to address this problem by extracting an inductive bias from a large set of pre-training, meta-training, tasks that can be used to improve test-time adaptation. Model-agnostic meta-learning (MAML) (Finn et al., 2017), one of the most popular meta-learning frameworks, formulates this inductive bias as iniial model for few gradient-basse that for the model can be fine-tuned on any meta-test task before evaluating its performance, MAML aims to learn the best initialization for fine-tuning among a of meta-training tasks. To do so, it executes an episodic meta- meta-trainte training procedure in which the current initialization is adapted to specific tasks in an inner loop, then the initialization is updated in an outer loop. This procedure has led to impressive few-shot learning performance in many settings (Finn et al. 2017 Antoniou et al. 2018).
tnn-tuning steps. Given
However, in some settings MAML's inner loop adaptation and the second derivative calculations resulting thereof may not justify their added computational cost compared to traditional, no-inner-loop pre-training Multiple works have suggested that MAML's few-shot learning performance may not drop when executing the inner loop adaptation for only fraction of the model parameters (Raghu) al. 2019 Oh al. 2020) or, in some cases, by ignoring the inner loop altogether (Bai al. 2020 Chen al. 20019) Unfortunately, the underlying reasons for MAML's behavior are still not well-understood, making it difficult to determine when inner loop adaptation during meta-training yields meaningful benefit.
In this work, we investigate when and why MAML's inner loop updates provide significant gain for meta-test time adaptation. To achieve this, focus how the meta-training loss landscape induced by the MAML objective affects adaptation performance compared to the loss landscape induced by the classical objective without inner loop adaptation, which we term the Non-Adaptive

---

Under review as a conference paper at ICLR 2022
Small Aviyy
Aviy
Small
Hard lasic so uitioon
Fany reak soliations
Prees
Plars
VAL HGML
Mipel
MAML
10
0.00
0:35
3:39
835
Excess Risk
Excess
Excess Risk
Excess
(a)
(b)
(c)
(d)
Figure I: MAML, NAL excess risks and optimal solutions in various environments.
Learning (NAL) method. Notably, MAML should always perform at least as well NAL because its meta-training procedure aligns with the meta-test time evaluation of performance after a few steps of task-specific SGD. Thus, our goals are to quantify the gain provided by MAML and determine the scenarios in which this gain is most significant. We start by studying the multi-task linear regression setting since it allows us to compare the exact solutions and excess risks for MAML and NAL.. In doing so, we obtain novel insights on how MAML deals with hard tasks differently than NAL, and show that MAML achieves significant gain over NAL only if certain conditions are satisfied relating to the hardness and geography of the tasks. These observations provide a new understanding of MAML that is distinct from the representation learning perspective considered in recent works (Raghu et al. 2019 Du et al. 2020; Tripuraneni et al. 2020). We then give theoretical and empirical evidence generalizing these insights to neural networks.
In particular, our main observations are best captured in the setting in which tasks are either "hard" or "easy". We let PH be the hardness parameter for the hard tasks, and pg be the hardness parameter for the easy tasks, where Pg > PH (smaller hardness parameter means more hard). As we measure the hardness a task by the rate at which gradient descent converges for the task, in this case, the hardness parameter is the task loss function's strong convexity parameter. For particular task environment, we let R be the dimension-normallzee distance between the average of easy tasks' optimal solutions and the average of hard tasks' optimal solutions, and let rH quantify the variance, or dispersion, of the hard tasks' optimal solutions. Assuming that @H (1 fx )² >> Pg
d m. where is
Ps
the problem dimension and m is the number of samples used for adaptation, then the ratio of the expected excess risks after task-specific adaptation of the NAL and MAML solutions approximately
(Corollary 2) En((WRR)))
(WMMMMM))) x= + R², Thus, the largest gain for MAML over NAL occurs when the TMr
lask environment satisfies (informal):
Hardness discrepancy: the hard tasks are significantly more difficult than the easy tasks
PM < 1, without being impossibly hard (pH 2 0), and
og II. Benign geography: the optimal solutions of the hard tasks have small variance TH, and the distance between the hard and easy task centers R is large.
Figure summarizes observations (I) and (II) by plotting locations of the easy and hard tasks' optimal solutions sampled from four distinct task environments and the corresponding solutions and excess risks for NAL and MAML. The environment in subfigure (a) violates (I) since ar = 1. Subfigures (b)-(c) show environments with either small R or large The so (II) is not satisfied. In contrast, the environment in subfigure (d) has small rH, large R, and en = 0.2, in which case as expected MAML A...)
achieves the largest gain over NAL E.. (WMAMEL) 2V 3.
Summary Why MAML. We show theoretically and empirically that MAML outperforms standard training (NAL) in linear and nonlinear settings by finding a solution that excels on the diff-diffiu to-optimize (hard) tasks, as long the hard tasks are sufficiently similar. Our work thus highlights the importance of task hardness and task geography to the success of MAMI..
1.1 RELATED WORK
A few works have explored why MAML is effective. Raghu et al. (201)) posed two hypotheses for MAML's success in training neural networks: rapid learning. meaning that MAML finds a set of parameters advantageous for full adaptation tasks, and feature reuse, meaning that
2

---

Under review as a conference paper at ICLR 2022
MAML learns a set of reusable features, among the tasks. The authors' experiments showed that MAML learns a shared representation, supporting the feature reuse hypothesis. Motivated by this idea, (Saunshi et al. (2020) proved that Reptile (Nichol et al., 2018), similar algorithm to MAML, can learn a representation that reduces the new-task sample complexity in a two-task, linear setting. Conversely, Oh et al. (2020) gave empirical evidence that MAML performance does not degrade when forced to learn unique representations for each task, and Goldblum et al. (2020) showed that while some meta-learning algorithms learn more clustered features compared to standard training, the same cannot be said of MAML. Moreover, a series of works have shown that removing the inner loop and learning a distinct classifier for each class of images in the environment can yield representations as well-suited for few-shot image classification as MAML's (Chen et al. 2019). In this work, we take a more general, landscape-based perspective on the reasons for MAML'S 's success, and show that MAML can still achieve meaningful gain without necessarily learning representation.
Much of the theory surrounding MAML and meta-learning more broadly has focused on linear settings, specifically multi-task linear regression or the related linear centroid problem (Denevi et al. 2018). Some works have studied how to allocate data amongst and within tasks (Cioba et al.) 2021 Bai et al. 2020 Saunshi et al. 2021). Denevi et al. (2018) considered meta-learning common mean for ridge regression, and Kong et al. (020)) studied whether many small-data tasks and few large-data tasks is sufficient for meta-learning. Other works have examined the role of the inner loop SGD step size in meta-learning approaches (Bernacchia 2021; Charles & Konečný 2220)] Wang et al.. 2020b), while Gao & Sener (2020) studied the trade-off between the accuracy and computational cost of the NAL and MAML training solutions. However, unlike our work, these works either did not consider or did not provide any interpretable characterization of the types of task environments in which MAML is effective. Other theoretical studies of MAML and related methods have focused on
convergence rates in general settings (Fallah et al. 2020 Rajeswaran et al. 2019 Zhou et al.) 2019)
Ji et al., 2020aa b Collins et al. 2020 Wang et al. 2020a) and excess risk bounds for online learning
(Finn et al. 2019: Balcan et al. 2019 Khodak et al., 2019). Like the current work, Fallah et al. (2020)
noticed that the MAML solution should be closer than the NAL solution to the hard tasks' global
minima, but the authors neither quantified this observation nor further compared MAML and NAL.
PROBLEM SETUP: TRAINING TO ADAPT
We aim to determine when and why MAML yields models that are significantly more adaptable compared to models obtained by solving the traditional NAL. problem in multi-task environments. To this end, we consider the gradient-basee meta-learning setting in which meta-learner tries to use samples from a set of tasks observed during meta-training to compute a model that performs well after one or a few steps of SGD on new task drawn from the same environment at meta-test time.
Specifically, we follow Baxter (1998) by considering an environment which is distribution over tasks. Each task T, composed of a data distribution μ4: over an input space X' and a label space V. We take our model class to be the family of functions {lw X + y w E RD} where h is a model parameterized by w. The population loss (i(w) on task is the expected value of the loss of low on samples drawn from 14, namely fi(w) == (x.x))) (e(h (x),y), where e is some loss function, such as the squared or cross entropy loss.
During training, the meta-learner samples tasks from p and n points ((x,, vz b ~ pa for each sampled task T. The meta-learner uses this data to compute an initial model w, which is then evaluated as follows. First, the meta-learner samples a new task Tr ~ p and m labeled points {($/, (R(.0)) b3 ~ ,.T. Next, it updates w with one step of stochastic gradient descent (SGD) on the loss function f. using those m samples and step size a. Namely, letting X, Rma and ý; E R denote the matrix and vector containing the m feature vectors and their labels, respectively, the update of w is given by w; == w a fi fi (w; v:), where fa 8,) == 1 ΣØ ((hw (x/), o/) is the empirical average of the loss on the m samples in (X,, 8t). The test loss of w is the expected population loss of w;, where the expectation is taken over tasks and the m samples, specifically
Fm (w) = E,E, 8.)
Xw;
(1)
3

---

Under review as a conference paper at ICLR 2022
where we have used the shorthand E;;= TB;=ETT,p TT and 9(), == = (8 measure solution quality by the excess risk
For fair evaluation,
Em(w) = Fm (w)
inf W'ERD
(w"(")
(2)
The excess risk the difference between the average performance of after one step of task-specific adaptation from the performance of the best possible initialization for fast adaptation. To find a model with small excess risk, one can solve one of two problems during training. NAL or MAML.
NAL. NAL minimizes the loss fi(w) on average across the training tasks, which may yield small excess risk En (w) with less computational cost than MAML (Gao & Sener 2020). Denoting the training examples for the i-th task as X; E Ruxd and their labels as E
NAL solves
min F WER
NAL
= == - ((w y.),
which is a surrogate for the expected risk minimization problem defined as min E, [f(]. We let wi Ar. denote the unique solution of the expected risk minimization problem, and let W.NL denote the unique solution to (3). We emphasize that in our study we evaluate the solution of NAL by its expected error after running one step of SGD using the m samples from new task that are
released at test time, and this error is captured by the excess risk En (W.. defined 2
MAML. In contrast to NAL, MAML minimizes a surrogate loss of [T during training. According to the MAML framework, the n samples per task are divided into training "episodes", each with 72 "inner" samples for the inner SGD step and nı "outer" samples for evaluating the loss of the fine-tuned model. Thus, have that T(n + n2) n. We denote the matrices that contain the outer samples for the j-th episode of the i-th task as X E R xd and y.y E R"1, and the matrices that contain the inner samples X. E 12 and y E R22 The MAML objective is then
min FMAML (w) WERD
TF
Σ
fl( a
yly
(4)
We denote the unique solution to by WaSAME and the unique solution to the population version [ by WMAML We expect Em (MM) S Em (WNAl) since (4) a surrogate for the true objective of minimizing (T). However, the gain of MAML over NAL may not be significant enough to justify its added computational cost (Gao & Sener 2020), necessitating a thorough understanding of the relative behavior of MAML and NAL.
3 MULTI-TASK LINEAR REGRESSION
We first explore the relative behaviors of MAML and NAL in a setting in which we can obtain closed-form solutions: multi-task linear regression. Here, the model hw maps inputs to predicted labels by taking the inner product with w, i.e. /ww lx) = (w, x). The loss function E is the squared loss, therefore fi(w)= - )~ [[(w,x) (.w,x)-nil x)) and f:( X, y:) y;)= 1 X w-wwwy x-ill for all i. We consider a realizable setting which the data for the i-th task Gaussian and generated by a ground truth model w;, Eldd That is, points (x;: M4) are sampled from μu by first sampling ~VO, E.). then sampling V/4 NN(W,.., X4), 2)) i.e. y: = (W.,,, X,) + 2 where 24 (0(,0 In this setting the population-optinet solutions for NAL and MAML are given by:
(5) E E E Note that these ²²"²) matrices are composed of two terms: a preconditioned covariance matrix Σ, (I, o,), and a perturbation matrix due to the stochastic gradient variance. We provide expressions for the empirical solutions W and w AAMML for this setting and show that they converge to w w and w n. T, do in Appendix D Since focus is ultimately on the nature of the solutions sought by MAML and NAL, not on their aom-tsympo behavior, we analyze w' and w MAML in the remainder of this section, starting with the following result.
W = Σ - E E,,,", and WMAML E, Q (2
'E,
Q
(12) wil.
where for any 8 E N. we define Q =
is most helpful to interpret the solutions w MAML and AL and their corresponding excess risks through the lens of task hardness. In this strongly convex setting, we naturally define task hardness
4

---

Under review as a conference paper at ICLR 2022
as the rate at which gradient descent converges to the optimal solution for the task, with harder tasks requiring more steps of gradient descent to reach an optimal solution. For step size a fixed across all tasks, the rate with which gradient descent traverses each f. is determined by the minimum eigenvalue of the Hessian of fi. namely Amin(E.). (E.). So, for ease of interpretation, we can think of the easy tasks as having data with large variance in all directions (all the eigenvalues of their Σ, large), while the hard tasks have data with small variance in all directions (all X(E;) are small).
Note that both WMAML and w WNAL are normalized weighted sums of the task optimal solutions, with weights being functions of the S, For simplicity, consider the case in which m and m2 are large. thus the Q; matrices are dominated by E E. Since the weights for w WNAL are proportional to the Σ; matrices, AL is closer to the easy task optimal solutions, as Σg has large energy for easy tasks and small energy for hard tasks. Conversely, the MAMI. weights are determined
by (I, a )² which induces a relatively larger weight on the hard tasks, so w LAML is closer to the hard task optimal solutions.
Note that easy tasks can be approximately solved after one step of gradient descent from far away, which is not true for hard tasks. We therefore expect (I) MAML to perform well on both hard and easy tasks since wM MAME, is closer to the optimal solutions of hard tasks, and (II) NAL to perform well on easy tasks but struggle on hard tasks since wivAL is closer to the optimal solutions of easy tasks. We explicitly compute the excess risks of w AL and w MAML as follows. Proposition 1. The excess risks for WNNL and w AML are:
Em(WWAAl L E. Σ
EV E (w; wj]] 9.
(6)
Em -
= - EB [Q]
-Ex Ev [Q[ (w? w()] (m)
We next formally interpret these excess risks, and develop intuitions (I) and (II), by focusing on two key properties of the task environment: task hardness discrepancy and task geography.
3.1 HARDNESS DISCREPANCY
We analyze the levels of task hardness that confer a significant advantage for MAML over NAL in this section. To do so, we compare w AML and A in environment with two tasks of varying hardness. We let n2 =-= m, Σ1 Pa and Σ₂ -g where PH < <gg. thus task I is the hard task
In this setting, the NAL and MAML solutions defined in 5 can be simplified as
PH
PE W PE
OH
WNAL=
w
WAML aæ + ag
W
W
(8)
PH + PE
PH + P
HH ag
where ag = (pE(1 ap + a+Ia² ph:) and az (px ap=) + d+1 a² phr) Note that the natural choice of is the inverse of the largest task smoothness parameter (") in this case). Setting PE
a 1 yields ag = d+1 Pg and ag = PH ) (d+1)/²
myg As a result, we can easily see that for sufficiently large values of m, have ar ag. This observation shows that the solution of MAML. is closer to the solution of the harder task, i.e., wi. On the other hand, ANAL is closer to W2z the solution to the easy task, since PH < PE.
Considering these facts, we expect the performance of MAML solution after adaptation to exceed that of NAL. Using Proposition I
the excess risks for NAL and MAML in this setting are
Em (WNAL))
aEPH + anre
Em (m(WMAML)
AguH
(PE + 2H)
ag + aH
Recalling that ag x 0 for m > d, we conclude that MAML achieves nerr-zero excess risk in the case of large m. In particular, we require that (1
PH )2 dpg otherwise the (d/m)) terms
'The effects of task hardness could be removed by scaling the data so that it would have covariance a - -La-- However, the current setting is useful to build intuition. Further, one can imagine similar setting in which the first dimension has variance and the rest have variance Pg, in which scaling would not be possible (as it would result in gradient descent not converging in the first conrdinate).
5

---

Under review as a conference paper at ICLR 2022
Location Soh.tooz.. di -0 2003
Location Solation, 0y
P
P1
(a)
(b)
(c)
(d)
Figure 2: First coordinates of w MMML- ANAL and their excess risks for various PH for large m (in
subplots (a)-(b) for m 2000) and small m (in subplots (c)-(d) for m= 100).
in ag and a:r are non-negligible. Meanwhile, for NAL we have &m (W AT.) aupk may be significantly larger than zero if Pir < 1, i.e the harder task is significantly harder than the Pg easy task. Importantly, the error for NAI. is dominated by poor performance on the hard task, which MAML avoids by initializing close to the hard task solution. Thus, these expressions pinpoint the level of hardness discrepancy needed for superior MAML performaccr.... 2a must be much smaller than I, but also larger than such that oH 2H PE
(2 which
pR
)2 > m
PE
Figure 2 visualizes these intuitions in the case that w Subfigures (a) and (c) show the locations of the first coordinates of w. and WMAML for varying PH, and m 2000 and = 500, respectively. Subfigures (b) and (d) show the corresponding excess risks. We observe that unlike NAI., MAMI, initializes closer the optimal solution of the harder task as long as pæ
d 10 and x² 0.01.
is not close to zero or one, which results in significantly smaller excess risk for
MAML compared to NAL in such cases, especially for large m.
Figure further shows that the MAML and NAL excess risks go to zero with pg. This is also shown in (9) and the definition of ag. and points the fact that too much hardness discrepancy causes no gain for MAML. The reason for this is that Pи ->0 0 corresponds to the hard task data going to zero (its mean), in which case any linear predictor has negligible excess risk. Consequently, both NAL and MAML ignore the hard task and initialize at the easy task to achieve near-zero excess risk here.
nu requires that m >> d. However, this condition arises due to the simplification tr(E,) = O(d), where tr(Z.) can be thought of as the effective problem dimension (Kalan et al. 22220). In realistic settings, the effective dimension may be o(d), which would reduce the complexity of m accordingly.
Remark 1. The condition CH C
pg
PE
3.2 TASK GEOGRAPHY
The second important property of the task environment according to Proposition 1 is the location, i.e. geography, of the task optimal solutions. In this section, we study how task geography affects the MAML and NAL excess risks by considering task environment with many tasks. In particular, the task environment fs is mixture over distributions of hard and easy tasks, with mixture weights 0.5. The optimal solutions w E Rd for hard tasks are sampled according to w ~ ((R1,, TH La) and for easy tasks are sampled as w ~ (O rgla). Therefore is the -onenniiionnoomliieeddde distance between the centers of the hard and easy tasks' optimal solutions, and and capture the spread of the hard and easy tasks' optimal solutions, respectively. The data covariance E, = Pz L for the hard tasks and Σ; Lg for the easy tasks, recalling that pr and Pg parameterize hardness, with smaller oи meaning harder task. In this setting the following corollary follows from Proposition [
Corollary 1. In the setting described above, the excess risks of W'NAL and WMAML are:
Em Em(WWAL) Mog+on (OEPÉ + 20еPEPH)тЕ + agp R²)
+ (OHPH + 20 aap R²)
(10)
Em (m(WAAM))) Martou)
(a2 + 20 20gan)ra (a + 22 2 )H
+ ( + R² a (TH R²)
(11)

---

0.5 in Under review as a conference paper at ICLR 2022
Halto Coless (estmme))
Colmos Welmowel
Downg 3225.1
Rooks
Fmneical Theontiic
(a) 0.5,
10
(b)
122
0.5,
10
(c)
R² R²
10,
0.5
(d)
10,
n² 0.5
VR
Figure 3: Theoretical and empirical excess risks for NAL and MAML and ratios of the NAL to MAML excess risk in the setting described in Section 3.2
a2 p'p and az = (m(11app)2-- d+1 a² where ag == p= app)² a
m Each excess risk a normalized weighted sum of the quantities rg. and R². So, the comparison between MAML and NAL depends on the relative weights each algorithm induces on these task environment properties.
m
PH (1 )² > m then aи > ag and the dominant weight in Ps
Em (o.WWe " AMLL ) is on the Lи term, while the dominant weights in Em( (WNAA) are on the LHH + R² and
TH terms. This observation leads us to obtain the following corollary of Proposition
Corollary 2. In the above setting, with a = 1/PE and
PH PH )a
PE
PE
>>
m
d the relative excess risk
for NAL compared to MAML satisfies
Em (W Em (MMA
R²
(12)
TH
Corollary 2 slshows that MAML achieves large gain over NAL when: (i) the hard tasks' solutions are closely packed (TH is small) and (ii) the hard tasks' solutions are far from the center of the easy tasks' solutions (R is large). Condition (i) allows MAML to achieve a small excess risk by initializing in the center of the hard task optimal solutions, while condition (ii) causes NAL to struggle on the hard tasks since it initializes close to the easy tasks' solutions. These conditions are reflected by the fact that the MAML excess risk weighs r'H (the spread of the hard tasks) most heavily, whereas the NAL excess risk puts the most weight on R² (distance between hard and easy task solutions) as well as
Note that the above discussion holds under the condition that ag >> ag- In order for az >> ag we pv. ) )2 >> d. i.c. >> d and 0 < 28 < 1, as observed in our discussion hardness discrepancy. Now, see that
must have 2s pee (1
pv with appropriate hardness discrepancy, the hard tasks must be both closely packed and far from the center of the easy tasks in order for MAML to achieve significant gain over NAL.. This conclusion adds greater nuance prior results (Balcan al. 2019 Jose & Simeone, 2021), in which the authors argued that gradient-based meta-learning (e.g. MAML) only effective when all of the tasks' optimal solutions close each other (in case, all of TE. and It are small). Crucially, our analysis shows that NAL would also perform well in this scenario, and neither rg nor R need to be small for MAML to achieve small excess risk.
To further explain these insights, we return to Figure T in which easy and hard task optimal solutions are each sampled from 10-dimensional Gaussian distributions of the form described above, and 100 random task optimal solutions are shown, along with the oopulation-optime solutions. In subfigures (b), (c) and (d), we set pe = 0.9, PH = 0.1, and m = 500. Among these plots, the largest gain for MAMI. is in the case that the hard tasks' optimal solutions are closely packed (small rH), and their centers are far from each other (large R), demonstrating the the primary dependence of relative performance on R² /TT-
MAML and NAL
We plot more thorough results for this setting in Figure 3 Here, we vary R and compare the performance of w AI. and w AA in settings with relatively large ти and small rg, specifically choosing TH and rE such that R (c)-(d), Here we also plot the empirical solutions AI and outperforms NAL when R² /TH is large (subfigures (c)-(d)), but not otherwise.
0.5 and
10 in (a)-(b), and R² = 10 and
Again, MAML significantly
4 TWO-LAYER NEURAL NETWORK
In this section, we consider a non- non-linear setting in which each task is a regression problem with a two-layer neural network with fixed second layer. The k-th neuron in the network maps Rdd -, TR.
7

---

Under review as a conference paper at ICLR 2022
via o(ww", x)), where R + R is some activation function and E is the parameter vector. The network contains M neurons for a total of D = .Md parameters, which are contained in the matrix W == [w'..... ....,,, ww]] I MM The predicted label for the data point is the sum of the neuron outputs, namely hw (x) == Ei= ((w*, x)) The loss function is again the squared loss, i.e. f((W)- = 2 (xxx))))m [(o 2k=1 I (w". x,)) -. Ground-truth models W.,, generate the data for task i. We sample (xi, 31) ~ p4 by first sampling x, ~ (O2,, Σ,) then computing y1 =K= M objective function in the two-task version of this setting.
k= or ((w".. x.)). The following result demonstrates an important property of the MAML
Theorem 1. Suppose that in the setting described above, the task environment is the uniform distribution over two tasks, and is the ReLU,, Softplus, Sigmoid, tanh function. Let E, = I and define 8i,k as the k-th singular value of W Ki == (..l1//s.,,M and X D for i {1,2). Further, define the regions S = { |W -Ws.ll2 S 1,,
S1 and the parameters Bg = o2 and Li == c3M for i E {1,2} und absolute constants c, C1, 02 and ez. Let 31 < <32 and L1 < Lz. For any stationary point W MAML of the population MAML objective 4 with full inner gradient step (m = 20), such that W MMML E Si n2, must satisfy for all a S 1/L2:
X,R?
1- 22 (Vf((WMAML)) S -
+0(22)
(13)
Interpretation: MAML prioritizes hard tasks. In the setting above, 3r and L; are strong convexity and smoothness parameters, respectively, of the function fa on the region S. Here, task 1 is the harder task since 81 and 8g control the rate with which gradient descent converges to the ground-truth solutions (Zhong et al. 2017), with smaller 3; implying slower convergence, and 3 < 32. Thus, Theorem | shows that, any stationary point of the MAMI. objective S₁ n S2 has smaller gradient norm the hard task than on the casy task long there is sufficient hardness discrepancy, specifically 82 > L1. Physically, this condition means that the curvature of the loss function for the easy task is more steep than the curvature of the hard task in all directions around their ground-trutt solutions. The smaller gradient norm of MAML stationary points on the harder task suggests that MAML solutions prioritize hard-task performance. In contrast, we can easily see that any stationary point AL of the NAL population loss must satisfy the condition [i (r. |/V [2(W N...) [|, meaning that NAL has no such preference for the hard task.
Figure 3 demonstrates the importance of task hardness in comparing NAL and MAML in this setting. Here, for ease of visualization we consider the case in which M and d = 2, i.c. the learning model consists of one neuron (with Softplus activation) mapping from 1 - IR. Each subfigure plots the NAL or MAML population loss landscape for different task environments with m m= 250, as well as the ground-trute -ruth neuron for each task. In light of prior work showing that the number of gradient steps required to learn a single neuron diminishes with the variance of the data distribution (Theorem 3.2 in Yehudai & Ohad (2020)) we again control task hardness via the data variance. In all plots, E; = 0.5Ig for hard tasks and Σ, = In for easy tasks. Note that the MAML loss (evaluated after one step of adaptation) is the evaluation metric we ultimately care about.
We observe that when all tasks are equally hard, the MAML and NAL solutions are identical (subfigures (a)-(b)), whereas when one task is hard, MAML initializes closer to the hard task and achieves significantly better post-adaptation performance than the NAL solution, which is closer to the centroid of the easy tasks (c)- This supports our intuition that MAML achieves significant gain over NAL in task environments in which it can leverage improved performance on hard tasks.
EXPERIMENTS
We next experimentally study whether our observations generalize to problems closer to those seen in practice. We consider image classification on the Omniglot (Lake et al., 2019) and FS-CIFARIOO 100 (Oreshkin et al. 2018) datasets. Following convention, tasks are N-way, K-shot classification problems, i.c., classification problems among N classes where K labeled images from each class available for adapting the model. For both the Omniglot and FS-CIFARIOO 100 experiments, the layer CNN used in Finn et al. (2017); Vinyals et al. (2016). NAL is trained equivalently to MAMI. with inner loop and n no + 12g. Further details and error bounds are in Appendix C
use
8

---

Under review as a conference paper at ICLR 2022
24.
NAL Loss Lanoscare Sorplis
Loss Landscape Sohpaus
XUAL Loss Landscape Soltppus
MAML Lona Landscage- Solpli
Hard Tack
04
65
50
04
-1
-15
-13
(a)
(b)
(c)
(d)
Figure 4: Loss landscapes and ground-truth neurons for NAL (a,c) and MAMI. (b,d) for two distinct, four-task environments and Softplus activation.
Table I: Omniglot accuracies.
Table 2: FS-CIFAR 100 accuracies.
Setting
Train Tasks
Test Tasks
Setting
Train Tasks
Test Tasks
TH
Alg.
Easy
Hard
Easy
Hard
p
Alg.
Easy
Hard
Easy
Hard
Large
MAML
99.2
96.0
98.0
81.2
NAL
78.2
9.9
74.8
9.5
0.99
Large
NAL-1
69.4
41.5
57.8
45.2
MAML
92.9
50.1
84.6
21.7
Large
NAL-10
70.0
45.3
67.2
47.9
NAL
81.9
9.5
76.5
8.6
0.5
Small
MAML
99.2
99.1
98.1
95.4
MAML
93.6
41.1
84.3
17.9
Small
NAL-1
69.2
46.0
55.8
45.8
NAL
82.4
7.6
76.9
8.2
0.01
Small
NAL-10
70.2
44.0
67.8
48.9
MAML
94.0
15.7
85.0
11.8
Omniglot. Omniglot contains images of 1623 handwritten characters from 50 different alphabets. Characters from the same alphabet typically share similar features, so are harder to distinguish compared to characters from differing alphabets. We thus define easy tasks classification problems among characters from distinct alphabets, and hard tasks as classification problems among characters from the same alphabet, consistent with prior definitions of semantic hardness (Zhou et al., (2200). Here we use N = 5 and K = 1. For NAL, we include results for K = 10 (NAL-10) in addition to K= (NAL-1). We split the 50 alphabets into four disjoint sets: easy train (25 alphabets), easy test (15), hard train (5). and hard test (5). During training, tasks are drawn by first choosing 'easy' or 'hard' with equal probability. easy train alphabets are selected. If "hard' is chosen, a hard alphabet is selected from the hard train alphabets, then N = 5 characters are drawn from that alphabet. After training, we evaluate the models on new tasks drawn analogously from the test (unseen) alphabets as well as the train alphabets.
"easy" is chosen, 5 characters from distinct alphabets among the
Table I gives the average errors after completing training for two experiments: the first (Large) when the algorithms use all 5 hard train and test alphabets, and the second (Small) when the algorithms use only one hard train alphabet (Sanskrit) and one hard test (Bengali). The terms 'Large' and 'Small' describe the hypothesized size of TH in each experiment: the optimal solutions of hard tasks drawn from ten (train and test) different alphabets are presumably more dispersed than hard tasks drawn from only two (train and test) similar alphabets. By our previous analysis, expect MAML. to achieve more gain over NAL in the Small ти setting. Table ] supports this intuition, as MAML's performance improves significantly with more closely-packed hard tasks (Small), while NAL's does not change substantially. Hence, MAML's relative gain over NAL increases with smaller ти.
FS-CIFARIO0, FS-CIFARIO0 has 100 total classes that are split into 80 training classes and 20 testing classes. We further split the 600 images in each of the training classes into 450 training images and 150 testing images in order to measure test accuracy on the training classes in Table 2 Here we use N and K as proxies for hardness, with larger N and smaller K being more hard as the agent must distinguish more classes with fewer training samples/class. Specifically, easy tasks have (N, K) = (2. 10), and the hard tasks have (N, K) = (20, 1). During training, hard tasks are sampled with probability p and easy tasks with probability 1 1-p. Observe that the largest performance gains for MAML in Table are the hard tasks, consistent with our conclusion that MAML outperforms NAL primarily by achieving relatively high accuracy on the hard tasks. However, the improvement by MAML on the hard tasks disappears when the hard tasks are scarce (p 0.01), supporting the idea of oversampling hard tasks during training in order to improve MAML performance (Zhou et al.
2020 Sun al. 2020

---

Searning-Volume Volume 70, Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
We believe that our paper does not have any potential ethical concerns.
7 REPRODUCIBILITY STATEMENT
The proofs for all theoretical results are the Appendix. Experimental details can also be found in the Appendix, and we have provided our code, well as instructions how to use it, in zip file as part the supplementary material.
REFERENCES
Antoniou, A., Edwards, H., and Storkey, A. How to train your maml. International Conference on Learning Representations, 2018.
Bai, Y., Chen, M., Zhou, P., Zhao, T., Lee, D., Kakade, S., Wang, H., and Xiong, C. How important is the train-validation split meta-learning? arXiv preprint arXiv:2010.05843, 2020.
Balcan, M.-F., Khodak, M., and Talwalkar, A. Provable guarantees for gradient-bast based meta-learning. In International Conference on Machine Learning, pp. 424 433. PMLR, 2019.
Baxter, J. Theoretical models of learning to leam. In Learning to learn, pp- 71-94. Springer, 1998.
Bernacchia, A. Meta-learning with negative learning rates. arXiv preprint
2021.
Charles, Z. and Konečnj, J. On the outsized importance of learning rates in local update methods. arXiv preprint arXiv:2007.00878 2020.
Chen, W.- Liu, Y.-C., Kira, Z., Wang, Y.-.. F., and Huang, J.-B. A closer look at few-shot classification. arXiv preprini arXiv: 1XXiv:194..4420 04232, 2019.
Cioba, A., Bromberg, M., Wang, Q. Niyogi, R., Batzolis, G., Shiu, D.-s., and Bernacchia, A. How to distribute data across tasks for meta-lcarning? arXiv preprint arXiv:2103.08465 2021.
Collins, L.,, Mokhtari, A., and Shakkottai, S. Task-robust model-agnostic meta-learning. In Advances in Neural Information Processing (NeurIPS), 2020.
Denevi, G., Ciliberto, C., Stamos, D., and Pontil, M. Learning learn around a common mean. Advances in Neural Information Processing Systems, 31:10169-10179 2018.
Du, S. S., Hu, W. Kakade, S. M., Lee, J. D., and Lei, Q. Few-shot learning via learning the representation, provably. arXiv preprint arXivv2002.00 09434, 2020.
Fallah, A., Mokhtari, A., and Ozdaglar, On the convergence theory of gradient-based model- agnostic meta-learning algorithms. In International Conference Artificial Intelligence and Statistics, pp. 1082-1092, 2020.
Finn, C., Abbeel, P., and Levine, S. Model-agnostic meta-learning for fast adaptation of deep networks. In Proceedings of the 34th International Conference on Machine Learning- pp. 1126-1135. JMLR. org, 2017.
Finn, C., Rajeswaran, A., Kakade, S., and Levine, Online meta-learning. International Conference on Machine Leurning, pp. 1920-1930, 2019.
Gao, K. and Sener, O. Modeling and optimization trade-off in meta-learning. Advances in Neural Information Processing Systems, 33, 2020.
Goldblum, M., Reich, S., Fowl, L., Ni, R., Cherepanova, V., and Goldstein, Unravel- ing meta-learning: Understanding feature representations for few-shot tasks. arXiv preprint arXiv:2002.06753, 2020.
Ji, K., Lee, J. D., Liang, Y., and Poor. H. V. Convergence of meta-learning with task-specific adaptation over partial parameters. arXiv preprint 200,:20000004486,, 2020a.
10

---

Under review as a conference paper at ICLR 2022
Ji, K., Yang. J., and Liang. Y. Theoretical convergence of multi-step model -anel-agnostic meta- veta-learning. arXiv e-prints, pp. arXiv- 2002, 2020b.
Jose, S. T. and Simeone, O. An informatiinn analysis of the impact of task similarity meta-learning. arXiv preprint 1xXi:22011.08399 2021.
Kalan, S. M. M., Fabian, Z., Avestimehr, A. S., and Soltanolkotabi, M. Minimax lower bounds for transfer learning with linear and one-hidden layer neural networks. arXiv preprint arXiv:2006. 10581, 2020.
Khodak, M., Balcan, M.-F. F,, and Talwalkar, A. S. Adaptive gradient-based meta-learning methods. In Advances in Neural Information Processing Systems, pp. 5915-5926, 2019.
Kong, W., Somani, R., Song, Z.., Kakade, S., and Oh, S. Meta-learning for mixed linear regression. In International Conference on Machine Learning (ICML), 2020.
Lake, B. M., Salakhutdinov, R., and Tenenbaum, J. B. The omniglot challenge: A 3-year progress report. Current Opinion in Behavioral Sciences, 29:97-104, 2019.
Nichol, A., Achiam, J., and Schulman, J. On first-order meta-learning algorithms. arXiv preprint arXiv: 02999, 2018.
Oh, J., Yoo, H., Kim, C., and Yun, S.-Y. Does maml really want feature reuse only? arXiv preprint arXiv:2008. 08882, 2020.
Oreshkin, B. N., Rodriguez, P., and Lacoste, A. Tadam: task dependent adaptive metric for improved few-shot learning. In Proceedings of the 32nd International Conference Neural Information Processing Systems, pp. 719-729, 2018.
Raghu, A., Raghu, M. Bengio, S., and Vinyals, O. Rapid learning or feature reuse? towards understanding the effectiveness of maml. In International Conference on Learning Representations, 2019.
Rajeswaran, A., Finn, C., Kakade, S. M., and Levine, S. Meta-learning with implicit gradients. In Advances in Neural Information Processing Systems, pp. 113-124, 2019.
Saunshi, N., Zhang, Y., Khodak, M., and Arora, A sample complexity separation between non- convex and convex meta-learning. In International Conference on Machine Learning (ICML), 2020.
Saunshi, N., Gupta, A., and Hu, W. A representation learning perspective on the importance of train-validation splitting in meta-learning, In International Conference on Machine Learning, pp. 9333-9343, PMLR, 2021.
Schudy, W. and Sviridenko, M. Concentration and moment inequalities for polynomials of in- dependent random variables. Proceedings of the Twenty-Third Annual ACM-SIAM Sympo- sium on Discrete Algorithmss, Jan 2012. doi: 10.11377.9781661193099939 URL http:
7/dx. //dx.doi. hetgg//..111.///1 9737/1.971111193333333
Sun, Q., Liu, Y., Chen, Z.., Chua, T.-S., and Schiele, B. Meta-transfer learning through hard tasks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
Tripuraneni, N., Jin, C., and Jordan, M. I. Provable meta-learning of linear representations. arXiv preprint arXiv:2002.11684 2020.
Tropp, J. A. An introduction to matrix concentration inequalities. arXiv preprint arXiv:1501.015: 2015.
Vershynin, R. High- DinensiDmmsion Probability: An Introduction with Applications in Data Science, volume 47, Cambridge University Press, 2018.
Vinyals, O., Blundell, C., Lillicrap, T., Kavukcuoglu, K., and Wierstra, D. Matching networks for one shot learning. arXiv preprint arXiv: (aao:::666000000 2016.

---

Under review as a conference paper at ICLR 2022
Wang, H., Sun, R., and Li, B. Global convergence and induced kernels of gradient-based meta- learning with neural nets. arXiv preprint arXiv:2006.14666, 2020a.
Wang, X., Yuan, S., Wu, C., and Ge, R. Guarantees for tuning the step size using learning-to-lear approach. arXiv preprint arXiv:2006. 16495, 2020b.
Yehudai, G. and Ohad, S. Learning a single neuron with gradient methods. In Conference on Learning Theory, pp. 3756-3786. PMLR, 2020.
Zhong, K., Song, Z., Jain, P., Bartlett, L., and Dhillon, I. S. Recovery guarantees for one-hidden- layer neural networks. In International conference on machine learning, pp. 4140-4149. PMLR, 2017.
Zhou, P., Yuan, X., Xu, H., Yan, S., and Feng, J. Efficient meta learning via minibatch proximal update. In Advances in Neural Information Processing Systems, pp. 1532-1542, 2019.
Zhou, Y., Wang, Y., Cai, J., Zhou, Y., Hu, Q., and Wang, W. Expert training: Task hardness aware meta-learning for few-shot classification, arXiv preprint urX1::2007.062400 2020.
12

---

Under review as a conference paper at ICLR 2022
APPENDIX
A PROOFS FOR SECTION 3
A.I PROOF OF PROPOSITION
For all i, let y X." w.. + 2 and y?th = X w 2 In other words, 2 E R is the vector containing the additive noise for the inner samples and out E g is the vector containing the additive noise for the outer samples.
From and 43 we have that
W NAL = E,
E EE, E,
(14)
W AMAAL E, (2) - QQ
(22
(15)
Next, compute closed-form expression for Fm (w) (defined in (T) For all i, let W. and y/ x, W,, + 24. In other words, z!" E I is the vector containing the additive noise for the inner samples and 2; E R is the scalar additive noise containing the outer (evaluation) sample. Then we have
((x,, w X (8, 91)) -vi) )
F(w)= 2 Ex (()
a x x 2i)) -]
Ex
E (1)
(x.,P((w- - (w))) + (2+ +
2
m
E, Ex (8)
(x, P.(: - wi)) + 22 +
a
x,
T X 2,
2
m
E, Ex (2)
Pi..P((W -wi))² + +0² +
tr(x; X 2:27 8
2
m
1
+ + a²0²
= Es Ex, P w/)ll. 2
tr {
where P; = La
a X & Hence,
inf (w) 0² a²o² tr())))
(16)
wERd
m
Thus we have
Em (WNAL) FmI(WNA)) 2 Eg 0² a²0² tr (x
m
= =E,B%, [P((WNAL - 1
=E5,8,, [(WNAL - w;) T E, (W w()]
-E,Ex, [ (F4 [Ep]] -'R, EE,
w()l)
P. P.P.PEE, Ex] - Ex (W2 w[)]]
E. (By E E (w/ w()l)
Ex, [P. E.P.
EEpr Ew - EE (W? w;)))
E,,
(E.
E
E
EE (w? w(D
(m)
(, [
E.r E. (w: ww))))
(17)
E,
[E,
Σx
Exp
Eg (w? wl)1)>ll
(18)
13

---

Under review as a conference paper at ICLR 2022
where 17
follows from Lemma
2 Similarly, for MAML we have the following chain of equalities
for Em W WMAML)
Em (AMM)))
o²0² tr( mEE)))
Fm (WMMMM))) 2 B, 0² +
Ex
[P(WWMMML w E
E,
[WMAME w)) P. E.P P. (WMAMM
w;)]
E,
wel :w:) (Ev1Q (2)) 1000)-111111 E. Q (nn) w - w:) P.E.P. ( -,, |,, 10/
(m2)
Ex
(E (2)) (22) - Ey Q
(mz) (w will)
P.
E. Q2 (12) - 10 (w:- - -w?]]
BB QQ. (mz)
Ey Q (mz) (w? - ww)l)
E.
xx
P.
P;P
E 12 100 E5 (2 (1د)) (w,: - ww]]]
E, ( Ev Q (E
[mn)]
Es Q (nz) (w wi))) Q (m)
E. 1 (ma))
Ez+ 1Q (m2) (w? (w:
w3)l
(19)
(E. [nal]
-E (Q, (122) (w3 w;)) km)
E,
(20)
where 199 follows from Lemma 2
A.2 PROOF OF COROLLARY
We first write out the dimension wise excess risks for NAL and MAML, using the results in Propo- sition Let wi,, denote the I-th element of the vector w Since each E, is diagonal, we have
that Q (78) is diagonal. Let Aæ denote the I-th diagonal element of the matrix Σ, and let gar denote
the 1-th diagonal element of the matrix Q (mm) thus (ú, Ar,1 (1 aA²)²² (tr (tr(E))).r + A..))
Recall that we assume n22 m. The error for NAL in the I-th dimension is:
Ey Drr ( m
g0 (WixL)
91.1
Ev [Nv,ll
E,
[E [E (gr Adm (wā wi,)) (wār wi,)]]]
2E,
[Ar.]]
2
Likewise, the error for MAML in the 1-th dimension is:
(0 wot 1)
27
Ex
1
E0 (Wi
2 Ex
9i,1
Ex,r
[g
E, E. Ep
19,.gee .16"r, (wo wi,1) (wirr w[l)]l]
2E, [gr.1]
14

---

Under review as a conference paper at ICLR 2022
Next use the definitions of A for the easy and hard tasks. For the easy tasks, note that
a²
casy 05,1
Xi,1 (1 a
(tr (1(( x².1)
m
(d + 1)a² PE
P app)) +
m
=: aF
(21)
and similarly for the hard tasks, namely
PH(1 -xpp)² (d 1)a²
hand 9el
0:
(22)
Next, recall that the task distribution is mixture of the distribution of the hard tasks and the distribution of the easy tasks, with mixture weights (0.5, 0.5). Let in be the index of task drawn from the distribution of hard tasks, and ig be the index of task drawn from the distribution of easy tasks. Then using the law of total expectation, the excess risk for MAML in the I-th dimension can then be written as:
cl) (MMAM))
27
Ey
qu'1 (w3 -
=
2
1i.1
Ep (asral
IB [aw (wzn. - ) )}² BBve [ag (w: - -wf,,) )]² -
E,
81E, [qr.)]
B aH (wit) - witt) Bii a (wig. w3.1)
an.Bu, an (Wig) wi ] a Bey [ar (wit w )1
Eig
16E, [qr.1]
2a Bun, aaxs (wig)) winn)) Bin [E (wtg. moigzet
E5g ag Ei'y ag (wh wiss!) )]² + aglEVE ag (wig. wz )
16IE, [qr.1]
22g at (wit11 - win!))
Bi's ar (wig. - who
(oHTH + and (r + R²) + 20 aETH
16E, [q..]
ag R²) a + 20T
(23)
1
4HTH aHa (TH + Ra) 20 HTTH
4(ag + aH)
aagoi R²) T + 2a 20T
15

---

Under review as a conference paper at ICLR 2022
where 23 NAL we have
follows by the properties of the distributions of the hard and easy tasks. Likewise, for
E/ (WNAL)
EE
Dve ( - w5s11
1
2
91.1
Ey [ev
an | (mi d winn .1 )]² an Byy [PB (wi winn:)]
Biss
16E, [Ar,]]
+ 2a Ee'r (P (Wp wine Byga Pe (w winn!)
a aEEir aa Wpint -wwser winns)] I agliy Ie (wiri wiss!! ]
+
Eig
16E, [Ar,]] 2
+ 2arBBr an (wZnn - -iin-wiis! win:)) ) Bosa |a (wige - wim.))
1
CHUPTTH + aнpE(rи + R²) 2анPиPETH+
4(ag + az
appl (E R²) aEPETE 20EPHPB
Note that in the this setting the excess risks are symmetric across dimension. Thus multiplying by d completes the proof.
A.3 PROOF COROLLARY
For the case that = 1/pF and weights that are placed on rH- TE, TH + R and Fg + R² in their excess risks. Using the fact that
PH (1 PH )2 > we can compare MAML and NAL by the
PE
= 1/pE, the expressions in 21 and (2 can be simplified as
(d + 1)PF
ag
m
PH )a + (d 1)p PE
a = PH (1
(24)
mp
Under the assumption that (1 PE PE
the bias term PH (1 - eu )2 dominates the gradient PE
variance term (d+1)eg thus 0g dominates ag- As result, we can ignore in the expressions. Furthermore, PH (1 eu )a dominates mpg
(d+1)ph within the expression for ag, meaning we can also
ps
drop the latter term. Thus we have
d
dp (1
Ag
(25)
4o
4
and
daz p3 2daнPEPH
da P
(rH R²)
TH 4(pH + PF)
4(pH + PF))
dpu (1 30
on )
2 PE
PM )2
rH
R²
(26)
4
4(pH p0)
16

---

Under review as a conference paper at ICLR 2022
Dividing 26 by 25 yields
Em Em(( (W (ANA))
dp
ez )²
dpHPE (1
22)2
/
dp
(1 PE
PH )²
PE
TH +
PE R²
Em (W AMML)
4
4(pH + pF:)2
P
R22
+
r1
(pH PE
P
R
1 +
(PH
PB)
R²
(27)
HH
A
where the last approximation follows since
(pstPH)² $ 1.
B PROOF OF THEOREM 1
In this section we prove Theorem [ We first show general result.
Lemma 1. Let WMML E RDD be a stationary point of the MAMI. objective 1 Twith m = oc whose Hessians of the task loss functions bounded and positive definite, ie. WAML satisfies
B 3 2 (WWMMMMM I L1ID: 32ID 3 J2(WMAML)) 3 L
(28)
for some I 2 31 > and L2 2 B2 > 0. Suppose that 32 > 31. Define W1 == WMMML
a ( and W2 = WMAML a (Vf((MMAML) Then the following holds for any a <
1/ max L1, L2):
0,3 V22(w2) O(a2).
[Vi(w))
2 1- aLi
(29)
Proof. For some vector WMAML E RD, let H (WMAML) = ('S((MMANL)) and H2 (AML) (2WM(MMM and (WWML))) = (i((1) and (2(WMAML) = (f2(W2), recalling that W1 = WMAML ( and W2 = WMAML - (Vf2(WMAMM).
Recall that the MAML objective in this case is given by
(w) = / fi( aV)((w)) + + - (VllwaVf((w))
(30)
After setting the gradient of (.)(.) equal to zero at WMAML, we find that any stationary point WMAML of the MAML objective must satisfy
(LD aH, (WMAML))gi (w1) = - aH2 (o0-oHHg (WMAM))
(31)
Since H2 (WWWM) = LıIa and < 1/ max L1, L2). Ia- (WMMML) is positive definite with minimum eigenvalue at least aL2 0. Thus we have
(ID (WM((WMMML))
oH, (WMAML)))I((1) = g2 (we))
(32)
Taking the norm of both sides and using the fact that ||Av|22 2 miin (A) | for any matrix A and vector v, along with the facts that I 3 H, (WMAML) I L I and BIID I Hz(WMAME)) = LgIp by assumption, yields
(222)l) = II(TD aH, (wMMMM))))
2 mix (ID (V (W.M
- oH, (Wbb(((.)))))))ll...
aLi
2 - aB2 |g (w1)ll2
(33)
Next, note that using Taylor expansion,
(W1) = V V/i(wwn (V(((MMML)) (Ww +((a))
= =(In aH, (WMAMI))) (W
(34)
8a (W2) = VVfe(WMAML) - - ( (fWWAAAA
=(In -oH (WWAA)))))
(35)
17

---

Under review as a conference paper at ICLR 2022
Landrape Solato
Landxapee Sptalas
Sohpluu
221
-19
-13
-10
-1
(a)
(b)
(c)
(d)
Figure 5: Task loss functions fI, f2, f3, fa for task environment in Figure 4 (a-b).
Therefore
ga (W(MMMM))12++ O(a2)
aH2 aHH((WaAM)))ommd aH1 (WM(WM))))) 1 1- l-aL1
o max (ID
gg (w1)ll2
1- a:
2
A
|gi (WMMT))))))
(36)
0332
i..,, [VAI(WMAML)] (t-ak)
Now we are ready to prove Theorem
Proof. We first show that IIINa I (')((W) I L,IN for all W E S; for i E {1.2), where (²)((W Ndx is the Hessian of the loss of the vectorized W and each 3; and is defined in Theorem In other words, we will show that each f; is 3,-strongly convex and L--smotth within
S, This will show that any stationary point W MAME that lies within S S satisfies the conditions
of Lemmal] I
For any 21 and for any W E BRdN we have by Weyl's Inequality
fff ..) [ (..
3 VVW)(W) (W,,(,,..) + [[V)((W) v V'
(37)
Thus, we will control the spectrum of V2 (WW by controlling the spectrum of V ft (W (.) and by upper bounding / (W) (W,.,W....)
To control the spectrum of V ('W,,....) ;..) we use Lemma D.3 from Zhong et al. (017), which shows
that for absolute constants 6₁ and 02 and each of the possible a functions listed in Theorem
(ci/ A)) NA (W......) A (c2N LNa-
(38)
Next, we apply Lemma D.10 from Zhong et al. (0077), which likewise applies for all the mentioned to obtain
v ((W)- V 122 S No sf IW
Wi.ll2
(39)
for constant c3. Next, for any W E S,, we have IW Wa. = ((1 (xNT Therefore, obtain that IaI 3 (')(W) 3 L.INa for all W e S,
by combining (37
38 and 39
Finally we apply Lemma to complete the proof.
Note that the constant used in Theorem T is the homogeneity constant for which or satisfies Property 3.1 from Zhong et al, (2017). namely, d((z) & a a|2/c Vz
IR.
18

---

Under review as a conference paper at ICLR 2022
NA. Loos uindespe Siydod
LAME Lest Lardscace Sggold
thospe- Sgmzz
03
Dxgget
-00
-16
-3.0
-10
-10
1810 1M
-20
(b)
(c)
(d)
Figure 6: Loss landscapes for NAL (a.c) and MAML (b,d) for two distinct task environments and Sigmoid activation.
Table 3:
Effect of up- weieetttingg hard tasks for NAL.
NAL
NAI., v = 2
NAL, = 5
NAI., v = 10
MAMI.
Avg. coord.
0.18 + .02 0.78 + .11
0.33 - .02
0.61 + .03
0.87 + .03
1.58 + 0.01
Test error
0.64 = .08
0.51 + 04
0.39 + .05
0.26 + 0.10
C ADDITIONAL EXPERIMENTS AND DETAILS
C.I LINEAR REGRESSION
In all of the linear regression experiments, to run SGD on the MAML and NAL objectives, we sample one task from the corresponding environment on each iteration for 5,000 iterations. Each task has 11 = 25 outer loop samples and varying n2 inner loop samples for MAML, and n. -2 + 12 samples for NAL. We appropriately tuned the 'meta-learning rates', i.e. the learning rate with which WM AMM and WAAL updated after each full iteration, and used n2// /10000 for MAML and 0.025 for NAL. After 5,000 iterations, the excess risks of the final iterates were estimated using 3,000 randomly samples from the environment. We repeated this procedure ten times to obtain standard deviations.
We also ran an experiment to test whether up- weighting the hard tasks improves NAL performance, in light of our observation that MAML achieves performance gain by initializing closer to the hard task solutions. We use a similar environment as in Section 3.2. Tasks are 10-dimensional linear regression problems with n22 25 inner loop samples and πı 500 outer loop samples, and noise variance 0.01. To implement up- weighting for NAL, we introduce parameter which is the ratio of the weight placed on the hard tasks the weight placed on the easy tasks within each batch of tasks. We normalize the weights to sum to 1. For example, if a task batch consists of 6 hard tasks and 4 easy tasks, then NAL with v 2 places a weight of 6 = 1 on the hard task loss functions and 62-44
8
1 16 on the easy task loss functions (as opposed to To on all tasks for standard NAL).
Easy tasks have hardness parameter PB = 1 and optimal solution drawn from (0,, Ia), and hard tasks have hardness parameter PH = 0.1 and optimal solution drawn from (21,,, Ia). We run NAL and MAMI. for 4000 iterations and use task-batch size of 10 tasks per iteration, sampling easy and hard tasks with equal probability. We report the average coordinate value for the final solutions ANLL and WMAML and their test error (averaged across randomly sampled hard and easy tasks), plus or minus standard deviation over independent random trials.
Note that average coordinate value closer to 2 means the solution is closer to optimal solutions of the hard tasks, while closer to means it is closer to the optimal solutions of the easy tasks. Indeed see that when NAL places more emphasis correspondingly increases and approaches that of MAML. Indeed, it illustrates that MAML can be interpreted reweighing of tasks based their level of hardness for GD.
the hard tasks. i.c. v is large, its performance
19

---

Under review as a conference paper at ICLR 2022
146
Coordiarz in Rest dmmrison
MAML
Hard Task
Easy Task
Excess RiSk (w))
1033
34
Pla 3.
06
P1.
Figure 7: Logistic regression results in analogous setting to m = 500 column in Figure 2 (I' tasks, d 10 dimensions). Recall that pnr is the strong convexity parameter (data variance) for the hard task, which determines its hardness, while the strong convexity parameter of the easy task is 1. MAML again initializes closer to the harder task, and has smaller excess risk for appropriate ps.
50,
1.0
0.5
0.5
0.5
0.0
Task
0.0
Coordrate
Wy Easy Tark
-0.5-
-0.5
-0.5
-1.0
0.2
0.4
0.8
10
0.2
0.4
0.8
0.2
0.4
0.8
4.0
4.0
4.0
3.5
Foteons temp.)
35
3.5
Elmon (thoory)
(emp.)
Elmon ") (thoory)
2.0
2.0
2.0
15-
1.
1.5
1.-
1.0
1.0
0.0
0.2
0.4
0.5
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
100
Figure Version of Figure 2 with corresponding empirical results, including 95% confidence intervals. The hardness parameter pn varies along the z-axis.
C.2 LOGISTIC REGRESSION
We also experimented with logistic regression, please see Figure for details.
C.3 ONE-LAYER NEURAL NETWORKS
We approximate loss landscapes for two types of activations: Softplus (Figures and and Sigmoid (Figure 6). To approximate each landscape, we sample Gaussian data as specified Section 4 and compute the corresponding empirical losses as in equation (3) for NAL and (4) for MAMI. We use n = 500 for NAL and n 20 and т 25 for MAML in all cases. We use n2 = m 250 for 80 for Sigmoid. Figure 6 shows that when the hard and easy task solutions have similar centroids (R small, as in subfigures (a) (a)-(b)), then the NAL and MAML solutions are close and achieve similar post-ade aas-aadattaiion loss (b). On the other hand, if the centroids
Softplus and n2
spread and the hard tasks are close (large R, small r as in subfigures (c)-(d)), then the NAL and MAML solutions are far apart and MAML. obtains significantly smaller post-adaptation loss (d)
20

---

Under review as a conference paper at ICLR 2022
SETTING
TRAIN TASKS
TEST TASKS
FH
ALG
EASY
HARD
EASY
HARD
LARGE
MAMI
99.2+.2
96.0+.6
98.0 + .2
81.2 .3
LARGE
NAL-1
69.4 +
41.5 +
57.8 +
45.2
LARGE
NAL-10
7..
45.3 .9
67.2 .3
47.9 +
SMALL
MAML
99.1 +
98.1 +
95.4 + .3
SMALL
NAL-1
69.2
46.0 66
55.8
45.8 + 1.0
SMALL
NAL-10
7
44.0
67.8
48.9 +
Table 4: Omniglot accuracies with 95% confidence intervals.
Setting
Train Tasks
Test Tasks
Alg.
Easy
Hard
Easy
Hard
NAL
78.2 .4
9.9 = 1.0
74.8 + .4
9.5 + ..6
0.99
MAML
92.9 3
50.1 1.0
84.6 + .4
21.7 = 3
NAL
81.9
9.5-1.00
76.5 1 .4
8.6 3
0.5
MAML
93
41.1=33
84.3
17.9 + .4
NAL
1.44
7.6
76.9
8.2 .A
0.01
MAML
1.2
15.7
85.0
11.8 +
Table 5: FS-CIFARI00 accuracies with 95% confidence intervals.
C.4 OMNIGLOT
The full version of Table 1 with error bounds, is given in Table
We use the same 4-layer convolutional neural network architecture as in (Finn et al. 2017). using code adapted from the code that implements in PyTorch the experiments in the paper (Antoniou et al., 2018). We ran SGD on the MAML and NAL objectives using 10 target samples per class for MAML, 10. Likewise,
Lee. n1 5 x iteration, for n2 = 5 x K. Eight tasks were drawn on each iteration for total of 20,000 iterations.
n1 5 n22 samples were used in each task to update WNAL each
1016111 6 and selected as 10-3 Similarly, the learning rate for NAL was tuned in {10-2 10 10-4 10 10-5, 10-9) and selected 10 Both MAMI. and NAL used task-specific adaptation (inner) learning rate of 10-1 as in Antoniou et al. (211)). To select the alphabets corresponding to hard tasks, we ran MAML on tasks drawn from all 50 Omniglot alphabets, and took the 10 alphabets with the lowest accuracies. The train/test split for the other (easy) alphabets was random among the remaining alphabets.
The outer-loop learning rate for MAML was tuned in {10- 10 10 10 10
To compute the accuracies in Table I we randomly sample 500 tasks from the training classes and 500 from the testing classes, with easy tasks and hard tasks being chosen with equal probability, and take the average accuracies after task-specific adaption from the fixed, fully trained model for each set of sampled tasks. MAMI. uses 1 step of SGD for task-specific adaptation during both training and testing, and NAL uses for testing. The entire procedure was repeated 5 times with different random seeds to compute the average accuracies in Table I and the confidence bounds in Figure
C.5 FS-CIFAR100
First, we note typo from the main body: we used 5x as many samples for task-specific adaptation as stated the main body for both easy and hard tasks, that is, (N, K) = (2, 50) for easy tasks and (N, K)) (20,3 5) for hard tasks.
The full version of Table with error bounds is given in Table
We use the same CNN as for Omniglot but with different number of input nodes and channels to account for the larger-sized CIFAR images, which are 32-by-32 RGB images (Omniglot images 28-by-28 grayscale). We ran MAML and NAL (SGD the MAML and NAL objectives, respectively) using 10 target (outer loop) samples per class per task for MAML, and 15 samples per class per task for NAL (recalling that NAL has no inner loop samples). Fight tasks were drawn
21

---

Under review as a conference paper at ICLR 2022
each iteration for total of 20,000 iterations. The outer-loop learning rate for MAML tuned
in {10-2 2, 2.10 10
10-10 10 15. 10--0-- and selected as 10 1003 Similarly, the learning rate for NAL was tuned in {10 (10-2,10)) 2, 9.10- 4,10 11009 =6 and selected as 10-6, Both MAML and NAL used
task-specific adaptation (inner loop) learning rate of 10-1 as in Antoniou et al. (018)).
We trained for 10,000 iterations with task batch size of 2, with hard tasks being chosen with probability p and easy tasks with probability 1 1-p. As the Omniglot experiment, after completing training we randomly sample 500 tasks from the training classes and 500 from the testing classes, with easy tasks and hard tasks being chosen with equal probability. We then take the average accuracies after task sask-specific adaption from the fixed, fully trained model for each set of sampled tasks. NAL uses 5 steps of task-specific adaptation for testing and MAML uses I for both training and testing. The entire procedure was repeated 5 times with different random seeds to compute average accuracies in Table and the confidence bounds in Figure
D MULTI-TASK LINEAR REGRESSION CONVERGENCE RESULTS
We motivate our analysis of the NAL and MAML population-optinng solutions for multi-task linear regression by showing that their respective empirical training solutions indeed converge to their population-optimal values.
First note that the empirical training problem for NAL can be written as
1 T
min WER"
X Wi..) -z:12:
(40)
where the j-element of z, RR contains the noise for the j-th sample for task Tr Taking the derivative with respect to w and setting it equal to zero yields that the NAL training solution is:
T
WNAL = X
Σ
X
X.
+ x.).
(41)
1
i=1
assuming E X X; is invertible. Similarly, using vi and u to denote noise vectors, as well
as Qu P. Pi. (X:yt) T x Pig where Pis- = =Ia-
X
in
iij we have that the empirical
training problem for MAML is
T
min weRd
T
X out P.. (w Wt,) (w.,), - z
out
122
x
out
i,j
in xijj
Zijll
(42)
therefore
W WMAML
T
T ΣΣ Qn., +P.s z.y
Q
P a
P.)((
X
[X
in
no
(43)
To show that WNAL and WMAML indeed converge to their population-optimal values as T, n. RI,T > 20, we first make the following regularity assumptions.
Assumption 1. There exists B S... || B Vi.
Assumption 2. There exists B, L 0 s.t. AI 3 Σ, LI, Vi.
Assumption Tensures that the task optimal solutions have bounded norm and Assumption 2 ensures that the data covariances are positive definite with bounded spectral norm.
Remark 2. We would like to note that Gao & Sener (2020) achieve a similar results as our Theorem 2 aand3 3 However, we arrive at our results using distinct techniques from theirs. Moreover, our MAML convergence result (Theorem 3) accounts for convergence
task instances to the population- optimal solution for MAML when a finite number of samples are allowed for task-specific adaptation stochastic gradient step), whereas the analogous result Gao & Sener (0200) (Theorem 2) does
22

---

Under review as a conference paper at ICLR 2022
not: it assumes = and shows convergence n1 T2 - oC. Since their result relies T22 co. shows convergence to the population MAML solution when an infinite amount of samples allowed for the inner task-specift update. i.e. full gradient step. Our is significantly worse, than theirs, which suggests the extra complexity of the MAMI. objective with finite samples allowed for task-specific adaptation.
dependence
D.1 NAL CONVERGENCE
Define Var(E.) | B, [E,])]] and Var E,W.,) = [E,
By Ex [E 11
Theorem 2. (NAL Convergence) Under Assumptions 7 and 2 the distance of the NAL training
solution 47 to iovplaaiionoppinnne value (3) is bounded as
é' c'v 3 (0g(200n)
dK c²
+ ot
K log((00n))
log (20g)200)
WNAL WiAAll2 &
8²
82n
Var(E, Wi, log 200d) LB v Var( E,, log(2000)
(44)
BVT
32vT
with probability at least 0.96, where is the maximum sub-exponential norm of pair- wise products of data and noise samples, for some absolute constants c,d, and z
2
4 cLVa+ / and 1333((vrr + Var(E,w;))/9 Informally,
23
Vd 1 vn
WNNL Wiaalle 5
+
(45)
VT
with probability at least 1 - o(1), as long = (((d) and T S?(Var(E)) + Var(E, where Ô and Åt exclude log factors.
Proof. We first introduce notation to capture the dependency of the empirical training solution on T
and n. In particular, for any T, n 2 1, we define
(T.n) w NAL Tn
x
1 Tn Σ X,
1 Tn
x
x,4 2
Tn
We next fix the number of tasks T' and define the asymptotic solution over T tasks as the number of samples approaches infinity, i.e., n + co, namely we define
T
W NAL
E
E w.
2ml
Using the triangle inequality we have
I
(T(Taa
(T.a) NAL WA || || (T.n)
NAL
w
WNAL
(T)s
WN w'alll
(T)=
< | (T.n)
(2'>
||
(2)x NAL wiaall
(46)
NAL
NAL
We will first bound the first term in 46) which we denote as 0 -= || N...
(T.) w NAF. for convenience.
(T)-
For this part we implicitly condition on the choice of training tasks to obtain a bound of the
form P[ > c)(T)).) < 1 8. Since this holds for all (Tet will obtain the final result P[[@] 2 e) < 1 8 by the Law of Total Probability. We thus make the conditioning on {T:);
implicit for the rest of the analysis dealing with 0.
23

---

Under review as a conference paper at ICLR 2022
We use the triangle inequality to separate I into term dependent on the data variance and term dependent on the noise variance as follows:
T
-1
T
-1
X
X
Σ
w
Tn
Tn
T
T
x'=1
T
-1
T
Σ
x
X
Σ
x Z
Tn
I'
i=l
i=1
T
T
-1
1 T
X
x X;
ΣΣ
Σx'
W
In
Tn
T Mmm
T
T
1 Tn
X
Σ
X wi
(47)
where (47) follows from the triangle inequality. We analyze the two terms in with the first term, which we denote by e) namely
47
separately, starting
Tn
Σ
x
Tn
X,
{
T
1
T
Ex
T
1
Σ
W
(48)
P=1
We define the matrix A; for each i:
T Σ
A,
1
X X
X,
1
Σ
Ex
E
(49)
Tn
Tn
T
T
which implies that 9 = with high probability. Note that if we define C as
E/-
Awwi We proceed to bound the maximum singular value of A;
C = Tn P=1
X
then A; can be written as
1 _ x, Tn
1 Σ x,
)
(+
T
1
A
-C
(50)
Tn P=1
P=1
where, defining A == + +
Ene for notational convenience,
B.
x
1
1
Σ
X.s
A -
Tn
Tn
P=1
1
1
A A- 1-11-1) E
x
X
Tn
T'
T
T
X X
xTxxa
A A-
T2p 8=1
T2n s/=1
1 (X X
(51)
T2n P=1
24

---

Under review as a conference paper at ICLR 2022
Adding and subtracting terms, we have
T
B:
x X,A
- - -
- -XX,AA''
T
f==1
T
+ T P=1
Σ;A -1 E2 - EEA-'E)
1
1 X X; Σ1
1-
1
1
ΣΦ
1 X x,,
A A'
T
T
72
n
T
T
1 + T
Σ,A- -1
T Σg
1
Eg
A
1-
T P=1
T
T P=1
- x -2 -
1
+
1
Σ
_
X;'
1 1-
[==1
where the last line follows by the definition of A.
Next, define
Z: = E, 1 - x,
Σ
n
Σ,
x (x: )
h=1
for all i = 1, I.,,,, T, where x!") E Rd is the h-th sample for the i-th task (the hith row of the matrix X,). Using this expression we can write
1 T
B
Z
Z.
T Vm1
Note that each Z₁ is the sum of independent random matrices with mean zero.
Using Lemma 27 from Tripuraneni et al. (2020) with each = 1, we have that
P | S ci mima max (c2(Vd/n + 4/n) =
(4/n))) 2 2 2exp(-13)
(52)
for any 4 > 0, and for each E [m]]
Next, considering the expressions for 8, A, B,, C, and Zi we can write that
T
T
W
Σ
C
B
w
B B,w, w
i=1
C
-Z, +
Ze
E
wi
(53)
T
T F=1
Next replace A by its definition
+
EP'=1
ET
En obtain
T
0
C
1
Z + Σ Ze
Σ
En
E,
Wi
T
i=1
V=1
====1
-1 T
C-1
Z
- +
Σ
Σ E,w,
(54)
T
p=1
1=1
where in equation
54
we have swapped the summations. This implies
c
Z
Σ,
E.(w; wi))
T
C
Σ
Σ
Σg (w$ w/)
(55)
i=1
25

---

Under review as a conference paper at ICLR 2022
where (5) follows by the Cauchy-Schwarz Schwarz and triangle inequalities. Using these inequalities and and we can further bound as:
Assumptions
T
T
||
s |
Σ
Σ
Σ
E (w) - ww-1ll
y==
T Σ
< <|C V=1
1
Σ
Σ
Σ
E Eilll - w3
s CC '1
- Σ
1
Σ
Σ
2TLB
Next, by the dual Weyl inequality for Hermitian matrices, we have Amin -
2
Ei Amin (2.). Thus by Assumption 2
we have Amin
E i=1 Eg)
T3, so
2LB
|C |
Zel
(56)
T3
By union bound and Lemma 27 from Tripuraneni et al. (2020) with each a; = 1, the probability that any
Zil 2 c1 C1 (x;) max (/) +t//)))+++++))))))))
(57)
is most 2 Σ 1= exp( -t,). Thus, with probability at least - 2 -'= expl -t,)
T
T
1 < |C-
2LB T3 1=1
Σ
ci Amx (E.) max (ealv (ealv//n+t//)) + t//n)2)
Let & == max, 4ú then using Assumption we have
B
< ||C-1|--
3 Ci max
t/nn))
(58)
with probability at least
2T exp (-P) for some absolute constants e₁ and 02 and any t > 0.
Next we bound |I, where C is the random matrix
T C= Σ
x
x,
(59)
Tn
Using the dual Weyl inequality again, we have
1 T Amin
X
Amin (C)
(60)
T
n
Next, using again using Lemma 27 from Tripuranení et al. (2020) with each a; 1, as well Weyl's Inequality (Theorem 4.5.3 in Vershynin (2018)), we have
Amin
x
> Amin (E,) - ci E max (o2
1/m1²)
11
2 3 - L max
= 3 -3-cL(vie (dd////n/ + t/ t/n) =:
(61)
with probability at least 1 1 2 exp (-t2) for any > 0 and sufficiently large n such that Φ > 0. where C1 C2 and absolute constants (note that since L B, in order for ø to be positive must be such that e² cd// + t/n) < 1 assuming 1, so can eliminate the maximization. In
26

---

proceed provide an upper bound for Under review as a conference paper at ICLR 2022
2
cLvd+t CAL
particular, we must have union bound over i, we have
Now combining (61 with (60) and using
20
T
||C
Amin
Σ. B -clly d/n+
(62)
B 3-cllVd/n+1//
for any t >> 0 and n sufficiently large, where is an absolute constant, with probability at least 1 2T exp (-t²). Using 62) with (58). and noting that both inequalities are implied by the same
2
event so no union bound is necessary, and N cLVd+ CLVatveL2d--Baa L3d--188Li
sufficiently large, we have
05 d( d(dd/n+t/n)
LAB
(63)
cl(v //////++///
with probability at least
27 exp (-)²) for some absolute constants c and c' and any f >> 0.
So far, we derived upper bound for the first term in 47 which denoted by 9. Next, we consider the second term of (47). which is due to the effect on the additive noise on the empirical solution. To be more precise,
Th (
1 2:) xi)
Using the Cauchy-Schwarz inequality, we can bound
this term as
T
T Σ x
Σ
X
x
zi
T
T
1=1
1=1
T
T
T
s
x,
z
s c
2i
(64)
T
We have already bounded ||C-||| so we proceed to bound the term + Σ
π X 2 Note that each element of the vector X z; is the sum of products of a Gaussian random variable with another Gaussian random variable. Namely, denoting the (h, s)-th element of the matrix X; as x! (h)
(s) and
(h) the s-th element of the vector 2; as (+), then the s-th element of X, 2, is E. 2; (s)) The products 2²a)
(M)(s)) (s) (s) are each sub-exponential. since the products of subgaussian random variables is cub-exponentiall (Lemma 2.7.7 in Vershynin (2018)), have mean zero, and are independent from each other. Thus by the Bernstein Inequality,
< 2exp (-d" min
62
Σ ( (s) 2
(65)
Dd K. max, K,
for some absolute constant c and any > O, where K, is the sub-exponential norm of the random variable x; (b) (s)2((s) (for any h, since the above random variables indexed by h are i.i.d). Define K == max, K, Using a union bound over h E [n]. we have
201 =
x
(s)
2 nb²
<
IP
(s)
26
1=1
s=1
12 b
(-d" (-c"min
< 2n exp
min
dK' K
27

---

Under review as a conference paper at ICLR 2022
for any b > 0. Thus have | z,|
b/yn with probability at least
2n exp (-d" min( o k)) Combining this result with (64) with (47) and (63, we obtain
1.B 0 = 8 cL( v +t/n)
d d(vd/n + t/n)
b
+
B
vn 3 cl (lVd//+t///
1
(cvv+ 3b
LL3B
+
(66)
8 B- cllVVl/V+tt
Byn
Bn
with probability at least
6² b dK' K)
1 27 exp (-t)
2n exp
(-d" min
(67)
for any b, > 0 and 2
23
Now that we have bounds for the terms in we proceed to bound the second term in 46). We have
[w
( NAL
WiNALll
=
Σ
T
-1
1
E,w;
E, -B,
T
- -1G
T
Σ
-1
1
Σ
T
E
E
-(7
Σs -
T
1 T
T 1=1
T
+
(7 Σ
B, - E& [E [
1=1
< Σ
-1 1
7 Σ
E:
Σ Σ. Ex)
Es E.1
+1(
T
-1
+
En
E. -E E.Wll
(68)
f=1
( Σ
T
T
<
Σ w - E, E.
1=1
T
-1
Σ
B, E
(69)
3 T Σ
1
:
E, E will
+
(
T
-1
E
Σ
-1
LB
(70)
where in equations (68
and 69 we have used the triangle and Cauchy-Sehwarz inequalities,
respectively, and in 77)
we have used the dual Weyl's inequality and Assumption We first consider
the second term in (70). We can bound this term as
|| +
T
E,
7
D
E,
E2p
[Ex1)
R.
i=1
t=1
T
T
Σ - E. E 11
Σ
1
1
<
Σ
[
-2 [2D1
(71)
32
T
1=1
28

---

Under review as a conference paper at ICLR 2022
using Assumptions and
We use the matrix Bernstein inequality (Theorem 6.5 in Tropp (015 to bound Σ (E Er Exl noting that each Σ; E
[Epp] is an iid matrix with mean zero. Recall that Var 2i)) =
[[B Ex [E>])]]|- By matrix Bernstein and equation (1 we obtain
T
-1 - EE
1 8 Var(E,)
E
-
(72)
VT
i=1
82 ( (-
with probability at least
- 2d
for any 6 > 0. Similarly, we have that
1
Var (ar(Z,
Σg w
E. [
S
(73)
3 T
VT
Var(I, (-1+B80/BVV)
with probability at least - 2d Thus (7))
reduces to:
18 Var Wi..))
LB 8 Var Ei)
1| (T) NAL
w. S
(74)
VT
ga
VT
with probability at least edx
(-
8 V2r 2dexp
(-
83 V. w 1/2
(I445//3VV)
1+LB8//3VT
We combine this result with (47 and (66) via union bound to obtain
cCv 36
tL2B
|NAAL - wivall S
B cl( cLLdd/n + t/n)
Byn
Bn
Var W.,))
Var(LBE.
(75)
OVT
B2vT
with probability at least
- 2nexp (-d" min
dK K ))
b² b.
82 Var (ar/2,)/2
1 - 27 2227eexpp exxpppp-"
2d 2ddexp exp
(++0
82 Var E, w( w )/2
2dexp
(76)
1+ LB8/(3VT)
cliva+ 12122448c1
as long as n
Finally, choose Vlog(200T), b
2/
dK oT
log (200m) +
K log (200n) and 8
(v Var E.)
log(200d) and re- and T
el. cLv7+ 431.244866L
strict
n 2
such that B-cL(
23
Var(E. E. This ensures that each negative term in the high probability bound (14) is at most 0.01 and thereby completes the proof.
B² (log(200)/(/)) Var E
29

---

Under review as a conference paper at ICLR 2022
D.2 MAML CONVERGENCE
We first state and prove the following lemma.
Lemma 2. Let A be a fixed symmettic matrix Idddd and let a random matrix in Rnxd whose rows are i..d. mullivariate Gaussian random vectors with mean and diagonal covariance E. Then
Ex ((=x (xxxxx)
A x xxxx]
(1 n
EAE+ (I(EEA)aa ΣAJE
(77)
Proof. Letting X₁K denote the k-th row of X, we have
1 x
Ex
x
A
x
n1
11
n
Ex
X
Xk
A
X Xk
n2
72
k=1
n
1 n
Exi
x Xv Ax
+ Exi
x x X
112
n2a
k=
k1=1,//
1 Ex Ex, Axx
EAE
(78)
n
Let C2 = x xx Ax,. for k E [n]. and let A, be the i-th diagonal element of 2 for i E [d]. Then for any k, using the fact that the elements of x are independent, have all odd moments equal and have fourth moment equal to 3X, for the corresponding i, it follows that
Ar Ej Ajajs + AM (Ar,s + As,r),
i otherwise
B(Cr.a] =
(79)
Using 79 we can write
E C(Cr] trEEAE E(A A
-t(EAAj + 2EAΣ
(80)
where 80) follows by the symmetry of A. Plugging
80
into 78 completes the proof.
L
Now we have the main convergence result. Analogously to Theorem
2 we define Var(Q) (Q.)
=
|E (Q: E,, [x1)) and (a..Q..;..)) = [[E, Q.,,, E.p Q2 W;,, lll
Theorem 3. (MAML Convergence, General Statement) Define 3 = B(1 aL)² + (a+1 and = T(1 a² + ad+1) If A'Assumptiins// and hold, the distance of the MAML training solution to its population-optimal value is bounded as
16LBd
L log" (1000d))
WMAML WMMM
Ba VF
Var Q W (200d)
LB (ar(Q.) log (200d)
(81)
/VT
BT
with probubility at least 0.96, for some absolute constants c. and d, and any a2d log"(1000) (100Td)) (c3) and T > BB
+ Var (a)(Q.:)))).
Proof. The proof follows the same form as the proof of Theorem 2 Here the empirical covariance matrices LX, X; and their means Σ, are replaced by the empirical preconditioned covariance matrices Qu, and their means Q., respectively. As before, critical aspect of the proof will be to
30

---

and Under review as a conference paper at ICLR 2022
show concentration of the empirical (preconditioned) covariance matrix to its mean. To do so, re-define the perturbation matrices Z,
Z
Qui Q:
(82)
TR
j=1
where
Q = P. (X
rout X Pi.j
E
Q
1=1
E
yout i,j
Xout b.
Pij.]
(83)
b.
Th11
/=1
E
Ia
x
E:
F1
(x x
7R1
72
112
j=1
Σ; 2a
[x
X (X
X (X:
Tm
72
j=l
(L. - -E aE,)
(Tr E + Σイソ)
(84)
n22
where (84) follows by Lemma 2
Note that here Z; has higher-order matrices than previously. Lemma nevertheless gives the key concentration result for the Z; 's, which we will use later. For now, we argue as in Theorem for any
T, r 2 1, we define
(T.r) MAML
T ΣΣQ., PP
Q
P 12
X
TTRi
Trnj
(T) We next fix T and define the asymptotic solution over T tasks as 7 - co, namely w MAME. =
( Dr Q:) T Σr Q.w Again using the triangle inequality we have
I (1.r)
MAMM WMAMLl [| (T:)
MAML MAML WMAM w
(1))
(T)x
WMAMLll
< || (T.r)
MAML w MAMMLl + || (T)+
(T)
MAML wMAMMll
(85)
The first term in 885 captures the error due to have limited samples per task during training. and the second term captures the error from having limited tasks from the environment during training. We
first bound the first term in (85. which we denote as O = | WMMML Note that by Assumption we have
(T,z)
w WAMell for convenience.
(T')
L Q
LL
Vi
(86)
where 3 3(1 2
a² (d+1) and i = L(1 a.8² + a (d+11) Thus, using the argument from 47 to 556 in the proof of Theorem with 1 X Xi, replaced by 2 Σ5= Qu. and Σ; replaced by Q. we obtain
n2
n2
0 S 0
Q
Trnı
1=1
T
Pa.
(Xoux T out
a P (Xot)
Touut in b,g
(87)
Trm
n2
i=1 1=1
31

---

Under review as a conference paper at ICLR 2022
where
( T
1
1
0
Σ
7
Qii
T
T
Qr
T
Q
wi
/=1
Defining C =
Ex=
1
2j=1
Q
we have,
mst
2 TB
Σ
Qu. C
Σ
P
Q3
W;
$
IIC
(88)
where obtain the inequality have swapped the order of the summations as in bound each |Z with high probability, by first showing element-wiss -iise convergence to
54
Next
Lemma 3. Consider a fixed i E [T]. k E [d], and E [d]. and let Qus (kc s) be the (k, s)-th element of the matrix Qi, defined in 93
The following concentration result holds for the random variable
Tm Ej= Qua (ki 2ig (k, s):
(-(cota2))
1/6
1 L
I
(k. ((((kss S> 2 e
exp
caa
(89)
for some any y > O, where Q; -1 Tm1 Σj=1 Quyy as defined in e.g. (83).
Proof. We start by computing the (kt, s)-th element of Z₁ First we compute the (k. 1)-th element of the matrix D., = (I4 na (X;)) XX) T X Here, define x R as the 71 dimeensiional vector of the r-thh-dimensional elements from all of the nı outer samples for the j-th
instance of task and {(A)) E "R=2 as the ni-dimensional vector of the k-th-dimensional elements from all of the ma outer samples for task i. Then we have
(i,(k,1)
E (1
x
n2
(x
x
(
(90)
n2
Then, the s)th element of Q is
(k,
P P X,, Pis (k)
Dig (h, (1
a
(2 x(!))
d
Σ (1|=s
12 (11))
(
(k)
Σ n2
(K)
n22
(x
(k)
d
a
712
20x
(x
11
(91)
32

---

Under review as a conference paper at ICLR 2022
Therefore the (k, s) element of 1 rmy
Σj=1 Qu, is
Σ 2is 2nn (k,,)
2a
(x
Th1 j=1
TRi
2
(92)
As we can see, this polynomial in the independent Gaussian random variables (1) and {
(T) (e for a total of dr(n1 + n2) random vari-
ables. Moreover, my Ej= Qis (kt s) is the average of T iidd. random variables indexed by j. Define these random variables as My for j E i.).
2a
xx x
U 111
71
(93)
To
1=1
such that
Σ (ky(kss) = 1 Σ "j
(94)
T1
==1
Then the variance of Thi
Eラ=1 Qid (ks (ki
s) decreases linearly with since
27
Var
Σ (k.
Qks 8) (k;
TR
Tn1
1=1
j=1
BI(
1
Σ
Uj
Σ
Blu
j=1
B((uy R(u,])
Bl(u, Elu B(uy))
(95)
j=1 8 =1,1 $1
EE(uu 3
where 95 follows from the independence of the uy 's. Next, recall the definition of u, given in (93).
11
1
(x
2a
((())
(x(,))))))
n1
n1
r=1
d
(96)
The second moment of is dominated by the higher-order terms in ui since these terms have the largest expectation (being of the highest order) and are the most populous. To see that they are the most populous, note that úq has d d monomials with six random variables, and only dn monomials with four random variables and n, monomials with two random variables. Thus E[u most constant times the expectation of the d' n' monomials of 12 variables in uf. Each of
33

---

Under review as a conference paper at ICLR 2022
these monomials in 12 variables is the product of 12 one-dimensional, mean-zero Gaussian random variables, corresponding to inner-loop samples and corresponding to outer-loop samples. The maximum expected value of each of these monomials is thus the eighth moment of the inner loop random variable with maximum variance times the fourth moment of the outer-loop random variable with maximum variance. Since the variables are Gaussian with maximum variance T., the maximum expected value of each monomial is 105L* x 3L = 315LS. This yields our upper bound on the variance. The following analysis formalizes this argument:
Var
Qislke s)
T
j=1
B(u]]
2a d (M))
(k) I
2,1 (1))
Σ Z= +
E
7
ca
R1
ΣΣΣΣΣΣ
E
n
0
ΣΣΣΣE>
R1
(1)=
Σ
n n
Σ
( (1) 2
Σ
(
)
Σ 2 B
(97)
By independence, each term in the above summation has expectation zero unless (i) r = and = P' or (ii) r', 1 l' and h h There are nf distinct values of (h, h², 1,,) that satisfy (i), and d2 < nd distinct values of (h, h r', 2') that satisfy (ii). For simplicity we treat each term the summations over n2 as having non-zero mean, although this can tightened. Since the expectation of each non-zero-mean monomial is at most 315L5, we have
7
Var
Σ
(k.sk)
(98)
Thi
T
for some absolute constant c. With this bound on Var Tii Σj=1 (k, 8)), the result directly
8) follows from Theorem 1.9 in Schudy & Sviridenko 2012). noting that 1 Σj= (k) The is degree 6 polynomial in centered independent Gaussian random variables. Note that by the argument in SShuudy & Sviridenko (2012), the bound on the elements of Z, given in Lemma 3s tight up logarithmic factors.
Next, we show that this result implies high probability bound on each |Z:11-
Lemma 4. For all task indices i, any y > and some absolute constant e, the following holds:
1/6
P ZI S <>) 2 1 ed exp (-
T22
(99)
34

---

Under review as a conference paper at ICLR 2022
Proof. By Lemma 3 have high-probability bound the size of the elements of Z
Using this bound, we can bound the spectral norm of Z, using the Gershgorin Circle Theorem, which says that every cigenvalue of Z lies within one of the Gershgorin disks D2 defined by
D {A À E [Z, k) Rg Zi(k, k) R&]
(100)
where R₁ Es=1, (k 8) This implies that
max (i( k) R2 ked
(101)
attempt to bound the RHS of the above. By union bound over k. have that for any y >
P PRR 2 (d 1)n) < P(U, (1i - ((k, s)s 2 r
e² exp (-(car Ty²
1/6
c2
T-2
1/6
(d- 1)e² exp
(102)
where (102) follows from Lemma
We also have that
P ((ZZ(((,)) 7) S e² exp (-
T-?
1/6
(103)
again using Lemma 3 Combining (102) and [03 via a union bound yields for some particular
P (k, k) + Rg S 7) 2 IP (R S (d -
7))
1 1 ((RR ((( 2
2 - P (1R 2 (d-1)))) - P((Z(kk)) 7))
1/6
1 - e² dexp
(104)
Therefore, via union bound over k, we have
m
R& 5>) 11- (P((LE {Zi(ks k.) + Rx 2 7})
kE[d]
2 e² exp
(-(ootaetz
792
2/6
(105)
for any 7 > 0. As a result, using 101 we have
Ty2
1/61
P (I 7) 2 edd exp
(106)
We continue with the proof of Theorem 3 by bounding ||C-|]] Using an analogous argument as in
the proof Theorem based on Weyl's Inequality (Theorem 4.5.3 in (Vershynin, (018)), we have
T Q |Z.
Amin (C) > Amin
(107)
where 107
follows by (86) and Lemma 4 with high probability, for any >> 0. Thus choosing
3. we have
|C-1|l <
(108)
35

---

Under review as a conference paper at ICLR 2022
Using this with 88
and Lemma 4
and using union bound over i [T]. we have
2LB
S Td exp (- (-(axt ry?
1/6
P 0
2
(109)
3-7
Next, we turn bounding the second term in 887 which is the enror term due to the additive noise in the linear regression setting. We will do this by again making an argument based on the concentration of polynomial in independent, centered Gaussian random variables around its mean. First, note that the term we must bound is
T
P Gi (x(9))
X.
TRIT
T
P Pig
out Pag (x
Zin
xout - Pi. (x91)
T X
oout (x:3)) 2i.
TRiT
i=1
j=1
(x
out X
TRIT
1
(X
Zio
out
P
out)
X
(110)
THiT
112
j=1
c-
out out Zij
P
out
T
X
out
(X
in
(111)
Tni
72
isj
i=1==1
where (10)) follows from the
Inequality. Define
T
g(k) =
P
(X
T out 1.
a P. (x:u)
out
out
(k) 2
(112)
TRiT
n2
=1
for each & [d], i.e. g(k) is the k-th element of the d-dimensional vector
THIT Ei
z a (X (x X (X Tz? and let n2
[g(k)l Note that each gkk is a degree-6 polynomial in independent, centered Gaus- sian random variables. One can that it is degree-6 because after expanding the Pt.j matrices, there are five data matrices and a noise vector (six total matrices) in the highest-order product. Also note that this polynomial has mean zero since the noise has mean zero and independent of the data, Its variance [k( [] can be upper bounded using a similar argument as in Lemma 3 We will not write the full calculations and argument since they are very similar to those in Lemma We again use the fact that the polynomial in question is the sum of n1 i.i.d. random variables to obtain variance decreasing linearly r. The differences are that in the highest-order monomial of g(k)), there are there are six inner-loop samples, four outer-loop samples, and two noise samples, for a maximum expectation
15L x 3L" a². There are 2 n of these terms, but as before, only d nÊ of these terms have nonzero expectation due independence, and the nfnng coefficient cancels. Thus, the variance upper bounded as
Var(g())) SC Ad DT E L302
(113)
T272
for absolute constant e, which implies, via Theorem 1.9 in Schudy & Sviridenko 2012). that
(-(
Tb²
1/0
P (1g(k)) 2 b) - e² exp (-(eatd-I>02
(114)
thus we have via union bound over 1: E [d].
762 (-(ottta
(-
1/6
P P s vab) eddexp
(115)
36

---

Under review as a conference paper at ICLR 2022
for any b > O. Combining this with 111 via a union bound, we have that
1
X iis
T
1=
T
ThiT
(
T out
n2
P
Pis
(x:
Xout
i.j
in (X
Zij
i=1
1=
Vdb
(116)
3-
with probability at least
(-(cotrei3r
Tb2
1/6
Td exp (-(orti2
ry
1/6
- eex
L
cf
L6
(117)
This completes the bound on O. Next, must bound
||
(T)*
WMaAsElk lll We have
MAMM
x
WMMMLl |I
MAML
Σ
Q
Q.wq-
T
1
11
T
=
0
Q:
Q
[.[Q.w:]]
i=1
T
Q
E,
Q
1=1
T
T 5
Q
Q :
Q.) Q wwi
1=1
Q:
E.Q.w -,,,E--E, Q
(118)
<
Σ
Qwi E.Q.:w;] +
1
T
Q
-1
E,
E, (Qw::] 1|
T
i=1
(119)
1 T 3
+|(
T
7
Σ T 1=1
-
+
Q
-
EQ
LB
(120)
1=1
where in equations (18) and 119 we have used the triangle and Cauchy-Schwarz inequalities, have used the dual Weyl's inequality and Assumption We first
respectively, and in 120 consider the second term in (20). Continuing to argue as in the proof of Theorem
2 we have
LB 32
(T) w MAME WMMMM |1 <
T Q [.Qw]]
Σ
Q
E. Q
(121)
T
As in the proof of Theorem to upper bound | Σ
will use the matrix Bernstein incquality (Theorem 6.1.1 in Tropp 2015))
Q E.(Q.w:) will and || Σ Q: E.[Q.]] with high probability.
Doing so yields
1 18 Var Qiw?)
LB Var(Q.)
(T) ||
MAML wMAMEll
(122)
9
VT
VT
with probability at least 1- - -2dexp
(-
82 Var(Q.
2ddexp
(- (ar(2
8²
for any > 0.
1+L8/(3VT)
(1-LB6/3VT)
37

---

Under review as a conference paper at ICLR 2022
Combining 122 with our bound on & (from 87).
109 and (166) via union bound and rescaling
7 Ynew
Vold V yields
2LB7
db
1
Var(Q.w;
LB 6 Var(Q.)
WERM WEEM v iVT 3/V7
Vi
7/V7
3
vT
B
vT
(123)
with probability at least
(-
ey2 2/6
dbb
1/6
1 - Td exp
edd dxp
Var(QQ..s.))
8² Var( Q.1/2
2d exp
2d -xpexp
(124)
1+ Lo/(vTT)
1 LB6/ (3vT)
for some absolute constants and c', and any b and 8 O, and
(0, VTū).
Finally, choose 7 4d a4Le log (100Td), b 2d 2 log 2 (100d), and
(v Var Q + Var Q:w?)) -1 log 200d) and restrict 7 > 32d a L (100Td))c) such that /- 3/ and T > L B² log 200d)/(9(Var) (Q;) + Var(Q.
This ensures that each
negative term in the high probability bound (224) is at most 0.01 and thereby completes the proof.
38


Reviews:
[{"review_id": "ofPS6AiV_fA", "reviewer": "Reviewer_oNs8", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\n1. Gain of MAML over NAL based on the dispersion of hard tasks is interesting. However, I have concerns that the assumptions are too strong (see below).\n2. Experimental comparison of MAML and NAL on real datasets is interesting. Particularly, it is interesting to see that MAML gets smaller error on hard tasks under some conditions from the theoretical results. However, this is not entirely surprising as NAL is never used in practice.\n3. This is also validates the popular notion that MAML is better at adapting to hard tasks than baselines.\n\n## Weaknesses\n1. Sec 3.1: \na. $\\rho_H/\\rho_E(1-\\rho_H/\\rho_E)^2 \\gg d/m$ is a very strong condition, even if $d$ is the effective dimension. This seems like a negative result (not that there is anything wrong with negative results), because when $d/m=o(1)$, each of the tasks may be separately solved using standard linear regression algorithm. For example, in Fig 1(b) with $d=10$ and $m=2000$, it would be interesting to know the average Excess risk of separately solving each of the tasks. This is an important baseline missing from all analysis and the experiments. I hope the authors can provide these in the next revision.\n\nb. It is not clear what the hardness means. Why can’t we use different stepsize for each task during adaptation?\n\nc. Why isn’t the main result collected into a well-defined theorem?\n\nd. It is not clear if the same conclusion holds true when first coordinate of $\\Sigma_i$ is $\\alpha^{-1}$. In that case, for large $m$, $a_H = \\rho_H (1-\\alpha \\rho_H)^2$, $a_E = \\rho_E (1-\\alpha \\rho_E)^2$. \n\ne. The problem considered seems too simple. For example, when the eigenvalues of covaraince matrices are different, or if the eigenvectors of the tasks do not match, the conclusions will differ.\n\n\n2. Sec 4: \na. Thm 1: It is not clear why, when $m=\\infty$, we have to use MAML instead of standard regression. This assumption on $m$ is too strong for the results to be interesting. \n\nb. Interpretation: Since hard tasks have smaller Lipschitz constant than strong convexity of easy tasks, it is not too surprising that the gradient of the hard tasks are smaller than gradient of the easy tasks.\n\nc. Interpretation: How are they the strong convexity and smoothness of the function? This needs to be derived.\n\nd. What happens here when there are multiple tasks? Can we make similar comparison between MAML and NAL then?\n\ne. Fig 4: Specific experimental details are missing. \n\nf. Fig 4: Why does the Thm 1 and Fig 4 use different notion of hardness. In Thm 1, $\\Sigma_i$ are identical, but later $W_i$ controls the hard\n\n3. Sec 5: Current theory seems too simplistic to capture the reality of non-convex MAML. The non-convex experiment shows huge improvement of MAML over NAL, which is expected and known. However, in convex theory and experiments it is not clear whether the simple baseline of separately learning the tasks could be better or comparable to MAML.\n\n4. Overall it is not clear why NAL is the only baseline that is compared with MAML.\n\n## Minor comment\n1. Pg 5, after eqn (8): Value of $a_H$ when settiing $\\alpha$ is wrong.\n2. Fg 2(c): Is $m=500$ or $m=100$?\n3. Fig 1: What are the values of $R$, $r_H$, $r_E$ used?\n4. Sec 4: Is the neural mapping a sum of activations or activation of the sum?\n5. Interpretation: For ease of reading please prove that NAL gradients are the same for hard and easy tasks. \n", "summary_of_the_paper": "This paper analytically compares the excess risk of two meta-learning methods: MAML and NAL. NAL is the simple baseline where the initialization for optimizing the test tasks is learned as parameter which minimizes the average loss of train tasks. \n\n1. For a particular simple setting of linear regression, authors show that MAML achieves lower excess risk than NAL when (1) there is a considerable difference in hardness of the tasks, and (2) if the true parameter of the hard tasks are closer together relative to the distance between the mean of the hard and easy tasks. \n2. For another case of simple neural network, where the output is the sum of many neurons outputs, authors show that MAML achieves smaller gradient for harder tasks than easier tasks under some condition.\n", "summary_of_the_review": "Although the motivation of the paper is valid, it is not clear if the conclusion is interesting due to strong assumptions.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "nOMar2XTAK-", "reviewer": "Reviewer_Y5kt", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "MAML is a widely-used meta-learning method that can quickly adapt to new tasks via one or a few stochastic gradient descent steps, so it is interesting and important to understand on which conditions MAML works well, and based on which, it may be further improved. The conditions provided in this paper are well supported by both numerical and analytical results in the linear regression setting. Since, in most scenarios, deep neural networks (DNNs) are used, the conditions would be more practically useful if the authors could provide more experimental results in the case where DNNs are applied.\n\nOne more suggestion: the analysis is based on the ratio of excess risk. It would be more convincing if the authors could explain why this measure is used and what are the other possible measures.\n", "summary_of_the_paper": "This paper is about finding the conditions under which MAML outperforms standard multi-task learning. In particular, the authors focus on a linear regression setting and show that MAML outperforms NAL under the following two conditions: (i) there must be some discrepancy in hardness among the tasks, and (ii) the optimal solutions of the hard tasks must be closely packed with the center far from the center of the easy tasks optimal solutions. The authors also give numerical and analytical results in two-layer neural networks.\n", "summary_of_the_review": "Interesting problem, solid numerical and analytical results in the linear regression setting, need more experimental results in the case where DNNs are used", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XV8T-2YJQ4O", "reviewer": "Reviewer_g4W9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths:**\n- The authors analyze the effect of the hardness of task loss on the solution of MAML algorithm, and suggested situations where MAML gains advantage over NAL.\n- The paper shows that MAML is going to pay more attention to the hard tasks to facilitate the boost of overall performance.\n- The paper shows how the geometry of optimal solutions can have impact the effectiveness of MAML, which is novel\n\n**Weaknesses:**\n- The hardness of tasks is characterized by the eigenvalue of Hessian, which is a local quantity. This notion of task hardness seems to be difficult to generalize to other tasks with rough landscape and varying Hessian.\n- The analysis shows that having the optimal solutions of hard problems packed together would benefit more from MAML, and in practice we do not get to know where are the optimal solutions for each task. The theoretical result does not seem to be able to guide practical applications of MAML effectively.\n- It is not convincing enough why NAL is made into comparison as we do not often use NAL for meta learning.\n\n**Correctness:**\n- There is no false claims to the best of my knowledge.\n\n**Clarity:**\n- The arrangement of the paper is clear and structured.\n\n**Additional Comments:**\n- What are the possible suggestions that this theoretical conclusion could be able to make on applications of MAML tasks, given that the pool of tasks is often determined not by their hardness of each task but their usefulness in practice? Would adding more simple tasks beyond target tasks help the learning?", "summary_of_the_paper": "This paper analyzes the performance of MAML algorithm under linear regression setting and compares that with the NAL under the same tasks. The authors show that the excess risk is smaller if there is more discrepency in the hardness of tasks and if the optimal solutions of hard tasks locate close to each other while those for easy tasks are far away. Related analysis and simulation results are also available for two-layer neural networks.", "summary_of_the_review": "The conclusions of this paper are interesting, and some of the analyses come from a novel perspective. However, the contribution of this paper still remains in doubt as it is unclear how the insights can prove to be useful in practical applications.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RQljuCcy-hp", "reviewer": "Reviewer_EaUw", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Strengthes \n1. I think the research topic is interesting and valuable. Understanding adaptive learning methods and their relationships/tradeoffs with the tasks/data is important. The topic is certainly relevant to the ICLR audience.\n\n2. The text is clear and I can easily follow the story.\n\n3. The authors provide the code and a comprehensive appendix for reproducibility.\n\n4. I think the analysis of MAML at the beginning of Section 3.1 is interesting. I would be interested to see it extended for multiple tasks, with different degrees of hardness and possibly orthogonal relationships between them (i.e., $w_i$ orthogonal to $w_j$). \n\n# Weaknesses\n1. The setting seems to be a bit oversimplified. I believe that the authors should explain/justify why a linear setting is a useful framework to validate their ideas and to justify their theory. Why wouldn't it fail in a more complicated setting?\n\n2. I suspect there might be an unfair advantage for the MAML model in the demonstrated comparison. It stems from the problem definition described at the beginning of Section 3. In this section, it is mentioned that each task $y_i$ is concentrated around a dot product $\\langle w_{i,\\*},xi\\rangle$, where $w_{i,\\*}$ is some ground-truth parameter associated with the $i$'th task. In addition, the MAML setting allows each task ($i$) to be solved by a function with a different parameter that depends on the data of the specific task. On the other hand, the NAL model does not enjoy the same degree of freedom and all of the tasks share the same solution w that is not dependent on the data of a specific task, rather the aggregation of all data. For instance, in the NAL case, we expect w to converge to their mean (assuming that $\\Sigma_i=I$ for all $i$). In particular, if $w_{i,\\*}$ are very far from each other, then, we do not really learn anything useful. It stems from the fact that NAL tries to model a function $h(x,i)=\\langle w_{i,\\*},x\\rangle$ that depends on the tasks using a function that is not dependent on $i$. \n\nSuggestions: \na. Emphasize why it is a fair/interesting comparison between the two models. \nb. Reconsider the comparison with NAL and compare it with an adaptive method instead. For instance, in a typical transfer/meta-learning setting, we have a function $f:\\mathbb{R}^d\\to \\mathbb{R}^k$ that is shared between the tasks and a specific classifier $g_i:\\mathbb{R}^k\\to\\mathcal{Y}$ for each task individually (e.g., $g_i$=linear). Would it be possible to replace w in the NAL case with a function of the form $\\langle v,Wx\\rangle$, where $W$ is a matrix shared between tasks and v is solved using linear regression on $(Wx_{ij},y_{ij})^{n}_{j=1}$? If so, would the theory change? how?\n\n4. Maybe I am missing something, in the proof of Lemma 1, what are $g_1$ and $g_2$? It seems that only $g_1(w_{MAML})$ and $g_2(w_{MAML})$ are defined but not $g_i(w)$. It makes it very hard to judge the soundness of this proof.\n\n5. The $O(\\alpha^2)$ in Theorem 1 (and Lemma 1) measures the scale w.r.t. alpha. Does it depend also on $\\|w_1\\|$ and $\\|w_2\\|$? If it may depend on these, the argument that $\\|\\nabla f_1(w_1)\\| \\leq \\|\\nabla f_2(w_2)\\|$ could be false. This should be explained.\n\n6. It seems that the task hardness is measured by the variance of the samples in the given task. Why is it referred to as the 'rate at which gradient descent converges to the optimal solution for the task'? I think it should be explained at least intuitively.\n\n7. What does it mean: \"NAL is trained equivalently to MAML with no inner loop\"?\nIn MAML, we have a shared model $f_{w}$ and for each task we adapt w given the corresponding data. \nHow do we compute the predictions for each one of the tasks with NAL?\nSuppose we have two binary classification tasks $T_1$ and $T_2$ that are exactly the same but the labels are switched, how $f_{w}$ handles them? \n\n8. \"The terms ‘Large’ and ‘Small’ describe the hypothesized size of $r_H$ in each experiment: the optimal solutions of hard tasks drawn\nfrom ten (train and test) different alphabets are presumably more dispersed than hard tasks drawn from only two (train and test) similar alphabets. By our previous analysis, we expect MAML to achieve more gain over NAL in the Small $r_H$ setting.\"\nAre there any experiments supporting this statement?\n\n# Clarity/minor comments\n1. \"has large *energy* for easy tasks and small energy for hard tasks\". -- what does energy mean here?\n2. \"after one step of gradient descent *from far away*, which is not true for hard tasks\". -- unclear to me.\n3. Maybe I am missing something, but I am not sure what is $\\| \\dots \\|_{Q^{(m)}_i}$ in (6-7).\nIt seems to be a non-standard notation, which needs to be defined before the statements of (6-7).\n4. What is the difference between $w_{i,\\*}$ in the definition of $y_i$ and $w^*_i$ in (5)?\n5. I think that the term 'geography' might not be the best choice. As far I as know, it is not a standard mathematical term. \n6. What is the inequality in (29) standing for? Is it smaller up to multiplicative constant? If so, why do you need $O(\\alpha)$ instead of $\\alpha$?\n7. Several undefined notations: $\\sigma_{\\min}, \\tilde{\\Omega}, \\tilde{O}$.\n8. In Theorem 2: is there a reason why you chose prob $\\geq 0.96$ instead of a parameter delta as we typically see in standard generalization/concentration bounds? What would be the dependence on such delta?\n", "summary_of_the_paper": "The authors aim to compare theoretically and empirically the ability of MAML and Non-Adaptive Learning (NAL) to different tasks in a multi-task setting, where tasks are sampled independently from the same distribution. They argue that MAML is better suitable for adapting to hard tasks, while NAL is unable to do so. Task hardness is measured by the noise of the samples in each task. ", "summary_of_the_review": "I believe that the overall direction is interesting and there is room to study which kind of adaptive learning method is better suitable for a different set of tasks (having many similar tasks/multiple hard and multiple easy tasks/etc). In addition, the paper makes an effort for laying some definitions of task hardness and tries to demonstrate different tradeoffs between adaptivity and hardness. \n\nHowever, I believe that the comparison itself is not in the right place and MAML should be compared within a set of adaptive methods. I do not think it is impressive that MAML is more adaptive than the non-adaptive learning method, which does not seem to be practical. I also think that the definition of hardness is a bit oversimplistic (or at least not sufficiently motivated) as it measures the variance of the samples in the task.    ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper compares MAML and NAL for meta-learning, and provides theoretical explanations on some very simple models when MAML can be significantly better than NAL, related to a definition of task hardness. The findings are also supported by experimental results.
While the results are plausible and can mark the starting point of a useful analysis, the models analyzed in the paper are too simplistic to warrant publication at ICLR. The authors are encouraged to extend their methodology to more complicated task models, as well as to, e.g., multi-step versions of MAML (since the considered version of MAML makes a single step, the proposed problem hardness may not be applicable in more general situations). It is also not clear how the derived insights can guide the practical applications of MAML.
Decision: Reject