Putting Theory to Work: From Learning Bounds to Meta-Learning Algorithms
Authors: Quentin Bouniot
Ievgen Redko
Romaric Audigier
Angélique Loesch
Amaury Habrard
Venue:  (2021)
Keywords: meta-learning
few-shot learning

Abstract: Most of existing deep learning models rely on excessive amounts of labeled training data in order to achieve state-of-the-art results, even though these data can be hard or costly to get in practice. One attractive alternative is to learn with little supervision, commonly referred to as few-shot learning (FSL), and, in particular, meta-learning that learns to learn with few data from related tasks. Despite the practical success of meta-learning, many of its algorithmic solutions proposed in the literature are based on sound intuitions, but lack a solid theoretical analysis of the expected performance on the test task. In this paper, we review the recent advances in meta-learning theory and show how they can be used in practice both to better understand the behavior of popular meta-learning algorithms and to improve their generalization capacity. This latter is achieved by integrating the theoretical assumptions ensuring efficient meta-learning in the form of regularization terms into several popular meta-learning algorithms for which we provide a large study of their behavior on classic few-shot classification benchmarks. To the best of our knowledge, this is the first contribution that puts the most recent learning bounds of meta-learning theory into practice for the popular task of few-shot classification. 

Under review as a conference paper at ICLR 2021
PUTTING THEORY TO WORK: FROM LEARNING BOUNDS TO META-LEARNING ALGORITHMS
Anonymous authors Paper under double-blind review
ABSTRACT
Most of existing deep learning models rely on excessive amounts of labeled train- ing data in order to achieve state-of-the-art results, even though these data can be hard or costly get in practice. One attractive alternative is to learn with little supervision, commonly referred to as few-shot learning (FSL), and, in particular, meta-learning that learns to learn with few data from related tasks. Despite the practical success of meta-learning, many of its algorithmic solutions proposed in the literature are based on sound intuitions, but lack a solid theoretical analysis of the expected performance the test task. In this paper, we review the recent ad- vances in meta-learning theory and show how they can be used in practice both to better understand the behavior of popular meta-learning algorithms and to improve their generalization capacity. This latter achieved by integrating the theoretical assumptions ensuring efficient meta-learning in the form of regularization terms into several popular meta-learning algorithms for which we provide a large study of their behavior on classic few-shot classification benchmarks. To the best our knowledge, this is the first contribution that puts the most recent learning bounds of meta-learning theory into practice for the task of few-shot classification.
INTRODUCTION
Since the very seeding of the machine learning field, its algorithmic advances were inevitably fol- lowed or preceded by the accompanying theoretical analyses establishing the conditions required for the corresponding algorithms learn well. Such a synergy between theory and practice reflected in numerous concepts and learning strategies that took their origins in the statistical learning theory: for instance, the famous regularized risk minimization approach is directly related to the minimiza- tion of the complexity of the hypothesis space, suggested by the generalization bounds established for supervised learning [Vapnik] 1992). while most of the adversarial algorithms in transfer learn- ing (e.g., DANN from (Ganin & Lempitsky 2015)) follow the theoretical insights provided by the seminal theory of its domain (Ben-Davite et al. 2010).
Even though many machine learning methods recent advances the field are still in their preliminary state which requires the hypotheses put forward by the theoretical studies be implemented and verified in practice. One such notable example is the emerging field of meta-learning, also called learning to learn (LTL), where the goal to produce a model on data coming from set of (meta-train) source tasks use it as a starting point for learning successfully new previously unseen (meta-test) target task with little supervision. This kind of approach comes in particularly handy when training deep learning models as their performance crucially depends on the amount of training data that can be difficult and/or expensive to get in some applications. Several theoretical studies (Baxter, 2000 Pentina & Lampert 2014] Maurer et al. 20166] Amit & Meir 2018 Yin et al. [2020] I provided probabilistic meta-learning bounds that require the amount of data in the meta-train source task and the number of meta-train tasks to tend to infinity for efficient meta-learning While capturing the underlying general intuition, these bounds do not suggest that all the source data is useful in such learning setup due to the
enjoy solid theoretical justification, some more
We omit other works for meta-learning via online convex optimization (Finn et al. 2019 Balcan et al. Khodak al. 2019 Denevi et al. 2019) as they concern different learning setup.
2019

---

Under review as a conference paper at ICLR 2021
additive relationship between the two terms mentioned above. To tackle this drawback, two very recent studies (Du et al. [020 Tripuraneni et al. (020) aimed at finding deterministic assumptions that lead to faster learning rates allowing meta- meta-learning algorithms to benefit from all the source data. Contrary to probabilistic bounds that have been used to derive novel learning strategies for meta-learning algorithms (Amit & Meir, 2018 Yin et al., 2020), there
attempt to verify the validity of the assumptions leading to the fastest known learning rates in practice or to enforce them through an appropriate optimization procedure.
In this paper, we bridge the meta-learning theory with practice by harvesting the theoretical results from Tripuraneni et al. (2020) and Du et al. (2020), and by showing how they can be implemented algorithmically and integrated, when needed, to popular existing meta-learning algorithms used for few-shot classification (FSC). This latter task consists in classifying new data having seen only few training examples, and represents one of the most prominent examples where meta-learning has shown to be highly efficient. More precisely, our contributions are three-fold:
1. We identify two common assumptions from the theoretical works on meta-learning and show how they can be verified and forced via a novel regularization scheme.
2. We investigate whether these assumptions rithms and observe that some of them naturally satisfy them, while others do not.
satisfied for popular meta-learning algo-
3. With the proposed regularization strategy, we show that enforcing the assumptions to be valid in practice leads to better generalization of the considered algorithms.
The rest of the paper is organized as follows. After presenting preliminary knowledge on the meta- learning problem in Section we detail the existing meta-learning theoretical results with their cor- responding assumptions and show how they can be enforced via a general regularization technique in Section 3 Then, we provide an experimental evaluation of several popular few-shot learning (FSL) methods Section
9 and highlight the different advantages brought by the proposed regularization in practice. Finally, we conclude and outline future research perspectives in Section
2 PRELIMINARY KNOWLEDGE
We start by formally defining the meta-learning problem following the model described in Du et al. 2020). To this end, we assume having access T source tasks characterized by their respective data generating distributions {14 )T- supported over the joint input-output space x Y with X S Rd and Y C R. We further assume that these distributions are observed only through finite size samples of size nı grouped into matrices X, = (X..I...., Xt.ng) E RRii xd and vectors of outputs Vt (Wt,1.-... :.......,,,,,) (1,m1) E RmI, Vl [[7]] := (1....,7)
Given this set of tasks, our goal is to learn a shared representation ø belonging to certain class of functions = {Øl o: % + V, V R$ and linear predictors w, IRt,, Vt [[T']] grouped in matrix W E xx More formally, this is done by solving the following optimization problem:
W
arg min WER.WERT xk 2T
ΣΣ
U( ((x,,)))
(I)
t=1 ==
where E: X R. is loss function. Once such representation is learned, we want to apply
to a new previously unseen target task observed through pair (Xr+1 E R +r+1 E R²*) containing n2 samples generated by the distribution (T+11- We expect that linear classifier w learned on top of the obtained representation leads to a low true risk over the whole distribution μT+1. More precisely, we first use Ô to solve the following problem:
Σ E(yT+1, (w, d(x++1)))).
Wr+1 arg min
WER T22
Then, we define the true target risk of the learned linear classifier WT+1 as:
L(Φ, WT+1) (x.)) [6(1, (WT-1, {(x))]
and want it to be small and as close as possible to the ideal true risk L(0", wi+1) where
Vt E [T + 1]] and (x, pe, y = (wi o0 (x)) + e e~~000 ((0
(2)
2

---

Under review as a conference paper at ICLR 2021
Equivalently, most of the works found in the literature seek to upper-bound the excess risk defined (R, Wr+1) L(Ø, WT+1) L(Ø", WT+1) with quantities involved in the learning process.
Remark We note that many popular meta- meta-learning algorithms used for FSL do not follow exactly the approach described above. However, we believe that the exact way of how this is done algo- rithmically (with or without the support set, with or without learning episodes) does not change the stutistical challenge of which is to learn model that can provably generalize with little supervi- sion. Supervised learning theory tells us that generalization in this case poor (not enough target data and it is difficult rely data coming from different probability distributions), while the theo- retical works we built upon suggest that source data may contribute in improving the generalization of the learned model alongside the target data if the assumptions described below are satisfied.
FROM THEORY TO PRACTICE
In this section, we highlight main theoretical contributions that provably ensure the success of meta- learning in improving the performance on the previously unseen target task with the increasing number of source tasks and the amount of data available for them. We then concentrate our atten- tion on the most recent theoretical advances leading to the fastest learning rates and show how the assumptions used to obtain them can be forced in practice through a novel regularization strategy.
3.1 WHEN DOES META-LEARNING PROVABLY WORK?
One requirement for meta-learning to succeed in FSC is that a representation learned on meta-train data should be useful for learning good predictor on the meta-test data set. This is reflected by bounding the excess target risk by quantity that involves the number of samples in both meta-train and meta-test samples and the number of available meta-trail tasks.
To this end, first studies in the context of meta-learning relied on probabilistic assumption (Baxter 2000 Pentina Lampert 2014, Maurer et al. 2016; Amit & Meir 2018: Yin al. 2020) stating that meta-train and meta-test tasks distributions are all sampled i.i.d. from the same random distri- bution. This assumption, however, is considered unrealistic as in FSL source and target tasks' data are often given by different draws (without replacement) from the same dataset. In this setup, the above-mentiona works obtained the bounds having the following form:
ER(ă, WT+1) So
1
VT
This guarantee implies that not only the number of source data, but also the number of tasks should be large in order to draw the second term to O. An improvement was then proposed by Du et al. (220 and Tripuraneni al. (2020) that obtained the bounds on the excess risk behaving
kd
k
Ô kd n1T
k
o
and
VniT
Vm2
T
72
respectively, where k & d is the dimensionality of the learned representation and Ô(-) hides loga- rithmic factors. Both these results show that all the source and target samples are useful in minimiz- ing the excess risk: in the FSL regime where target data is scarce, all source data helps to learn well. From a set of assumptions made by the authors in both of these works. we note the following
The matrix of optimal predictors W should cover all the directions in T& evenly. More formally, this can be stated as
Assumption 1.
01 (W*) OK (W*)
Ro (W")
O(1),
where (:): denotes the th singular value of W As pointed out by the authors, such assumption can be seen as a measure of diversity between the source tasks that are expected to be complementary to each other in order to provide meaningful representation for previously unseen target task.
3

---

Under review as a conference paper at ICLR 2021
Souron
space
Sourow
spacs
Source task in 0 space
Source task 2 in space
R, wi
+x0
Wi 1
(.(W)
Figure Illustration of the example from Section 3.2 with 0.02.
Assumption 2. The norm of the optimal predictors w should not increase with the number of tasks seen during meta-training" This assumption says that the classification margin of linear predictors should remain constant thus avoiding over- or under-specializattoo to the seen tasks.
While being highly insightful, the authors did not provide any experimental evidence suggesting that verifying these assumptions in practice helps to learn more efficiently in the considered learning setting. bridge this gap, we propose to use a general regularization scheme that allows us to enforce these assumptions when learning the matrix of predictors in several popular meta-learning algorithms.
3.2 PUTTING THEORY TO WORK
As the assumptions mentioned above are stated for the optimal predictors that are inherently linked the data generating process, one may wonder what happens when these latter do not satisfy them. To this end, we aim to answer the following question:
Given W such that (W())) >> 1, can we learn W with R2 (W) ss while solving the underlying classification problems equally well?
It turns out that we can construct example illustrated in Fig. for which the answer to this question is positive, To this end, let us consider a binary classification problem over X C R with labels Y {-1,1} and two source tasks generated for k, J0, 1], as follows:
1. μi is uniform over {1 ke, k 1) x (1) U (1 ke, - x {-1}:
2. H2 is uniform over {1 + ka, k 8-1 x (1) ke, 1+ x {-1}.
We now define the optimal representation and two optimal predictors for each distribution as the solution to Eq. over the two data generating distributions and Φb {Øl o(x) oxx, $ 3322];
6², W
arg min 6E WeR2X2
E E(y, (w. o(x))), (x.y)~<s
One solution to this problem can be given as follows:
1 0 0
11
W
-8
where 6* projects the data generated by μe to two two-dimensional space by discarding its third dimen-
sion and the linear predictors satisfy the data generating process from Eq. 2 with e = 0. One can verify that this case W have singular values equal to v and /2e, so that the ratio R. (W+)) = when e - 0, the optimal predictors make the ratio arbitrary large thus violating Assumption 1.
While not stated as separate assumption, in Du al. (2020) assume to derive the Assumption I men- tioned above. See p.5 and the discussion after Assumption 4.3 in their pre-print.
4

---

Under review as a conference paper at ICLR 2021
Let us now consider a different problem where want to solve Eq. 4 with constraint that forces linear predictors to satisfy Assumption 1:
W
arg min
Σ
E (x.2))pp
Ely.
(w,,
s.t. ( 1.
(5)
dE WeRxx2
i=1
Its solution is different and is given by
0 1 0 60011
0
W - 0
1 -8)
T5
Similarly to d., 2 projects to two-dimensional space by discarding the first dimension of the data 2 with & 0, but contrary to
generated by p4. The learned predictors in this case also satisfy Eq.
2+t2+tVE=+4 tends to when e - 0. W (W) 2+62-cV6244
Several remarks are in order here. First, it shows that even when W does not satisfy Assumption in the space induced by ø², ,i may still be possible to learn
representation space & such that the optimal predictors in this space will satisfy Assumption 1. This can be done either by considering the constrained problem from Eq. 5 or by using more common strategy that consists in adding Ro (W) directly as regularization term
T
m
arg min ΦE WERTH 27
Eve ((x,)( À (W).
1=1==1
Below, we explain how to implement this idea in practice for popular meta-learning algorithms.
Ensuring assumption 1. We propose to compute singular values of W during the meta-training stage and follow its evolution during the learning episodes. In practice, this can be done by per- forming the Singular Value Decomposition (SVD) on W E RRx with a computational cost of O(TK²) floating-poing poiiiinggppintttoo operations (flop). However, as T is typically quite large, propose more computationally efficient solution that is to take into account only the last batch of N predictors (with N < 2) grouped in the matrix W N E IR xk that capture the latest dynamics in the learning process. We further note that a. WW N W x) = (W.N,, Vi E [[]]] implying that we can calculate the SVD of W W (or W N W. for & S N) and retrieve the singular values from afterwards.
We now want verifyy whether the optimal linear predictors w, cover all directions in the embedding space by tracking the evolution the ratio singular values R.(W (Wx) during the training process. For the sake of conciseness, we use R, instead of R. (WW)) thereafter. According the theory, expect RG to decrease during training thus improving the generalization of the learned predictors and preparing them for the target task. When we want enforce such a behavior in practice, we propose to use R2 as a regularization term in the training loss of popular meta-learning algorithms.
Alternatively, as the smallest singular value N [Wn N be close and lead numerical errors, we propose to replace the ratio of the vector of singular values by its entropy as follows:
N
H, N)
Σ softmax(o(Wwx)))
(W w)); log softmax(o((W)))) x))...
where softmax(-)) ;)= is the 5th output of the softmax function. As with Rg, we write Ho instead of H. (W.)) from now on. Since uniform distribution has the highest entropy, regularizing with R, or H. leads to a better coverage of & by ensuring a nearly identical importance regardless of the direction. We refer the reader to the Supplementary materials for the derivations ensuring the existence the subgradients for these terms.
Ensuring assumption 2. In addition to the full coverage of the embedding space by the linear predictors, the meta-learning theory assumes that the norm of the linear predictors does not increase with the number of tasks seen during meta-training, i.e., ||w||2 = O(1) equivalently. || (TT). If this assumption does not hold in practice, we propose to regularize the norm of linear predictors during training directly normalize the obtained linear predictors w [
5

---

Under review as a conference paper at ICLR 2021
The final meta- veta-training loss with the theory-inspite regularization terms is given as:
T m2
min ΦE WERTXL 2T
Kyy,, (We, (xx,,))) + X Ro (Wx) + >2 Well W
(7)
and depending on the considered algorithm, we can replace Rg by - H, and/or replace w, by We instead of regularizing with [W 1/-- In what follows, we consider \1 Xa and we refer the reader to the Supplementary materials for more details and experiments with other values.
To the best of our knowledge, such regularization terms based on insights from the advances in meta- learning theory have never been used in the literature before. We also further use the basic quantities involved in the proposed regularization terms as indicators of whether given meta-learning algo- rithm naturally satisfies the assumptions ensuring an efficient meta-learning in practice or not.
3.3 RELATED WORK
Below, we discuss several related studies aiming improving the general understanding of meta- learning, and mention other regularization terms specifically designed for meta-learning.
Understanding meta-learning While complete theory for meta-learning is still lacking, several recent works aimed to shed light on phenomena commonly observed in meta-learning by evaluat- ing different intuitive heuristics. For instance. Raghu et al. (2020) investigated whether the popular gradient-based MAML algorithm relies on rapid learning with significant changes in the representa- tions when deployed on target task, or due to feature reuse where the learned representation remains almost intact. They establish that the latter factor is dominant and propose a new variation of MAML that freezes all but mask-specific layers of the neural network when learning new tasks. In another study (Goldblum et al., 2020) the authors explain the success of meta-learning approaches by their capability to either cluster classes more tightly in feature space (task-specific adaptation approach), or to search for meta perammarsssters that lie close in weight space to many task-specific minima (full fine-tuning approach). Finally, the effect of the number of shots on the classification accuracy was studied theoretically and illustrated empirically in Cao et al. (2200) for the popular metric-based PROTONET algorithm. Our paper is complementary to all other works mentioned above as it inves- tigates new aspect of meta-leariing that has never been studied before, while following a sound theory. Also, we provide a more complete experimental evaluation as the three different approaches of meta-lcarning (based on gradient, metric or transfer learning). separately presented in Raghu al. 2020), Cao et al. (2020) and Goldblum et al. (2020). are now compared together.
Other regularization strategies Regularization is common tool to reduce model complexity dur- ing learning for better generalization, and the variations of its two most famous instances given by weight decay (Krogh & Hertz 1992) and dropout (Srivastava et al., 2014) are commonly used as a basis in meta-learning literature as well. In general, regularization in meta-learning is applied to the weights of the whole neural network (Balaji et al., 2018: Yin et al. 2020), the predictions (Jamal & Qi 2019: Goldblum et al.] 2020) is introduced via prior hypothesis biased regularized empirical risk minimization (Pentina & Lampert| 2014; Kuzborskij & Orabona 2017 Denevi et al. 2018a bj 2019). Our proposal is different from all the approaches mentioned above for the following reasons. First, we do not regularize the whole weight matrix learned by the neural network but the linear predictors of its last layer contrary to what was done in the methods of the first group, and, more specifically, the famous weight decay approach (Krogh & Hertz 1992). The purpose of the regu- larization in our case is also completely different: weight decay is used to improve generalization through sparsity in order to avoid overfitting, while our goal is to keep the classification margin unchanged during the training to avoid httrr/udddr-sppcalizzttee
to some source tasks. Similarly, spectral normalization proposed by Miyato et al. (2018) to satisfy the Lipschitz constraint in GANs through dividing W values by mmux (W does not affect the ratio between 7 (W) and mmin (W) and serves completely different purpose. Second, we regularize the singular values (entropy or ra- tio) of the matrix of linear predictors instead of the predictions, as done by the methods of the second group (e.g., using the cnmreticiiffommation quantities in Jamal & Qi 2019) and Yin et al. (2020)) ). Finally, the works of the last group are related to the online setting with convex loss functions only, and, similarly to the algorithms from the second group, do not specifically target the spectral proper- ties of the learned predictors. Last, but not least, our proposal is built upon the most recent advances in the meta-learning field leading to faster learning rates contrary to previous works.
6

---

Under review as a conference paper at ICLR 2021
4 PRACTICAL RESULTS
In this section, we use extensive experimental evaluations to answer the following two questions:
Q1) Do popular meta-learning methods naturally satisfy the learning bounds assumptions?
Q2) Does ensuring these assumptions help to (meta-)learn more efficiently?
For Q1, run the original implementations of popular meta-learning methods to what is their natural behavior. For Q2, we study the impact of forcing them to closely follow the theoretical setup.
4.1 EXPERIMENTAL SETUP
Datasets & Baselines We consider few-shot image classification problem on three benchmark datasets, namely: 1) Omniglot (Lake et al., 2015) consisting of 1,623 classes with 20 images/class of size 28 x 28; 2) minilmageNet (Ravi Larochelle 2017) consisting of 100 classes with 600 images of size 84 x 84 per class and 3) tieredImageNet (Ren et al.) 2018) consisting of 779,165 images divided into 608 classes. For each dataset, we follow the commonly adopted experimental protocol used in Finn al. (017)) and Chen et al. (2019) and use a four-layer convolution backbone (Conv- 4) with 64 filters as done by Chen et al. (2019). On Omniglot, we perform 20-way classification
with I shot and 5 shots, while on minil and tieredImageNet we perform 5-way classifica- tion with 1 shot and 5 shots. Finally, we evaluate four FSL. methods: two popular meta-learning strategies, namely, MAMI. (Finn al. 2017). a gradient-based method, and Prototypical Networks (PRotONET) (Snell et al. 2017). a metric-based approach; two popular transfer learning baselines, termed as BASELINE and BASELINE++ (Ravi & Larochelle) 2017 Gidaris & Komodakis 2018) Chen et al. 2019) Even though these baselines are trained with the standard supervised learning framework, such training can also be seen as learning a single task in the LTL framework.
Implementation details Enforcing Assumptions 1 and 2 for MAML is straightforward as it closely follows the L.TI. framework of episodic training. For each task, the model learns a batch of linear predictors and we can directly take them as Wx to compute its SVD. Since the linear predictors are the weights of our model and change slowly, regularizing the norm [ wIl and the ratio of singular values Rs does not cause instabilities during training. Mcanwhile, metric-based methods do not use linear predictors but compute a similarity between features. In the case of PROTONET, the similarity is computed with respect to class prototypes (ie. the mean features of the images of each class). Since they act as linear predictors, a first idea would be to regularize the norm and ratio of singular values of the prototypes. Unfortunately, this latter strategy hinders the convergence of the network and leads to numerical instabilities. Most likely because prototypes are computed from image features which suffer from rapid changes across batches. Consequently, we regularize the entropy of singular values H, instead of the ratio Rs to avoid instabilities during training to ensure Assumption and we normalize the prototypes to ensure Assumption by replacing w; with w, in Eq. Z For transfer learning methods BASELINE and BASELINE++, the last layer of the network is discarded and linear predictors are learned during meta-testing. Thus, we only regularize the norm ||W N F of predictors learned during the finetuning phase of meta-testing. Similarly to MAML, we compute R2 with the last layer of the network during training and fine-tuning phase.
Remark 2 We choose well-establishe meta- leta-lea algorithms for our comparison, but the pro- posed regularization can be integrated similarly into their recent variations (Park & Oliva 2019 Lee et al. (019) (see Supplementary materials for results obtained with the method Park & Oliva (2019)) ). Finally, using models that do not rely on linear predictors is also possible but might be more difficult as it would require upstream work to understand which part of the model acts as predictors (as done for PROTONET in this paper) and how to compute and track the desired quantities.
4.2 INSIGHTS
Q1 Verifying the assumptions According to theory, || N |F and Rs should remain constant or converge toward a constant value when monitoring the last N tasks. From Fig. aa, we can see that for MAML (Fig, 2 a) top). both [Wwlle and R2 increase with the number of tasks seen during training, whereas PROTONET (Fig. Daa bottom) naturally learns the prototypes with a good cover- age of the embedding space, and minimizes their norm. This behavior is rather peculiar as neither
7

---

Under review as a conference paper at ICLR 2021
MAML
MAML-reg
MAML
MAML+reg
MAML
MAML+reg
8:46
020
0:0
04
27k
27%
30c
41g
57k
678
01
30N
20h
30c
63
28c
266
36
53.
6%
(a)
Proto+norm
Proto
Proto+norm
Proto
Proto+norm
10000
6030
6830
2800
Accusvyy
6430
6030
1832
4030
2000
4090
2000
2000
13c
206
606
20
Iteration
Tra rongn loratin
Tratning Beration
Baseline
teredimageNet Omnigiot
Baseline Basclie reg
teredimageleet
Omniglot
reg
2000
(b)
Training Iteratoon
Training epochs
Saselinet+
tie ecllmageeit
Baseline--
konnddmagehiet
Baseline- +-rg
Cmniglot
Baseline-- rrg
Omniglot
Rusiin 1150
410
Cco
Train ng Iteration
Training apachs
Figure 2: (a) Evolution of || I (left), R. (middle) and validation accuracy (right) when train- ing of MAMI. (top) and PROTONET (bottom) on minilmageNet (1 shot for MAMI., 5 shots for PROTONET). (b) Evolution of Rs (left) and validation accuracy (right) when training BASELINE (top) and BASELINE+ (bottom) Omniglot (dashed lines) and tieredImageNet (solid lines). All training curves were averaged over different random seeds. For MAML, || [ N || and R2 increase during training and violate Assumptions 1-2. PROTONET prototypes naturally cover the embedding space, while minimizing their norms. Rg converges during training on both datasets for BASE- LINE+ (similarly PROTONET) whereas it diverges for BASELINE tieredImageNet. With our regularization, W w || and R₂ are constant during training in accordance with theory.
of the two methods specifically controls the theoretical quantities of interest, and still, PROTONET manages to do implicitly, As for the transfer learning baselines (Fig. 2 top and bottom), we expect them to learn features that cover the embedding space with R2 rapidly converging towards constant value. As can be seen in Fig. (b). similarly PROTONET, BASELINE++ naturally learns linear predictors that cover the embedding space. As for BASELINE, it learns a good coverage for Omniglot dataset, but fails to do so for the more complicated tieredImageNet dataset. The observed behavior of these different methods leads to conclusion that some meta-learning algorithms inherently more explorative of the embedding space.
Q2 Ensuring the assumptions Armed with our regularization terms, we now aim to force the considered algorithms to verify the assumptions when it is not naturally done. In particular, for MAML regularize both || W x || and RS in order to keep them constant throughout the training. Similarly, we regularize R, during the training of BASELINE and BASELINE++, and both || F and R2 during the finetuning phase of meta-testing. For PROTONET, we enforce normalization of
8

---

Under review as a conference paper at ICLR 2021
Dataset
Episodes
MAML.
PROTONET
BASELINE
BASELINE++
20-way 1-shot
+3.95*
+0.33*
-13.2
-7.29*
Omniglot
20-way 5-shot
+1.17"
+0.01
+0.66*
-2.24
5-way 1-shot
+1.23"
+0.76*
+1.52
+0.39
minilmageNet
5-way 5-shot
+1.96*
+2.03*
+1.66*
-0.13
5-way 1-shot
+1.42"
+2.10*
+5.43*
+0.28
migredl
5-way 5-shot
+2.66*
+0.23
+1.92"
-0.72
Table 1: Accuracy gap (in p.p.) of the considered algorithms when using the regularization (or normalization in the case of PROTONET) enforcing the theoretical assumptions. All accuracy results are averaged over 2400 test episodes and 4 different seeds. Statistically significant results (out of confidence intervals) reported with * Exact performances are on par with those found in the literature and are reported in the Supplementary materials.
the prototypes. According to our results for Q1, regularizing the singular values of the prototypes through the entropy Ho not necessary Based on the obtained results, we can make the following conclusions. First, from Fig. 2aa) (left, middle) and Fig. bb) (left), we note that for all methods con- sidered, our proposed methodology used enforce the theoretical assumptions works as expected, and leads to desired behavior during the learning process. This means that the differences in terms of results presented in Table D are explained fully by this particular addition to the optimized ob- jective function. Second, from the shape of the accuracy curves provided in Fig. 2aa (right) and the accuracy gaps when enforcing the assumptions given in Table [ we can see that respecting the assumptions leads to several significant improvements related to different aspects of learning. On the one hand, we observe that the final validation accuracy improves significantly in all benchmarks for meta-learning methods and in most of experiments for BASELINE (except for Omniglot, where BASELINE already learns to regularize its linear predictors). In accordance with the theory, we at- tribute the improvements bound on the excess target risk and, consequently, to a better generalization performance. On the other hand, we also note that our regularization reduces the sample complexity of learning the tar- get task, as indicated by the faster increase of the validation accuracy from the very beginning of the meta-training Roughly speaking, less meta-training data necessary to achieve performance comparable to that obtained without the proposed regularization using more tasks. Finally, we note that BASELINE+ and PROTONET methods naturally satisfy some assumptions: both learn diverse linear predictors by design, while BASELINE++ also normalizes the weights of its linear predictors. Thus, these methods do not benefit from additional regularization as explained before.
the fact that fully utilize the training data which leads to tighter
5 CONCLUSION
In this paper, studied the validity of the theoretical assumptions made in recent papers applied to popular meta-learning algorithms and proposed practical ways of enforcing them.
On the one hand, we showed that depending on the problem and algorithm, some models can natu- rally fulfill the theoretical conditions during training. Some algorithms offer a better covering of the embedding space than others. On the other hand, when the conditions our proposed regularization terms allows to learn faster and improve the generalization capabilities of meta-learning methods. The theoretical framework studied in this paper explains the observed performance gain. Notice that no specific hyperparameter tuning was performed as we rather aim showing the effect of ensuring learning bounds assumptions than comparing performance of the methods. Absolute accuracy results are detailed in the Supplementary materials.
not verified, learning with
While this paper proposes an initial approach bridging the gap between theory and practice in meta-learning, some questions remain open on the inner workings of these algorithms. In particular, being able to take better advantage of the particularities of the training tasks during meta-tran veta-training could help improve the effectiveness of these approaches. Self-supervised meta-learning and multi- ple target tasks prediction are also important future perspectives for the application of meta-learning.
"The effect of entropic regularization PROTONET is detailed in the Supplementary materials.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended pac-bayes theory. In International Conference on Machine Learning, 2018.
Yogesh Balaji, Swami Sankaramarayanan, and Rama Chellappa. MetaReg: Towards Domain Gener- alization using Meta- Regularization. In Advances in Neural Information Processing Systems, pp- 998-1008, 2018
Maria-Florina Balcan, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees for gradient- based meta-learning. In International Conference on Machine Learning, 2019.
Jonathan Baxter. A Model Inductive Bias Learning. Journal of Artificial Intelligence Research, 12:149-198, 2000.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wort- man Vaughan. A theory of learning from different domains. Machine Learning, 79(1-2):151-75,, 2010.
Tianshi Cao, Mare T. Law, and Sanja Fidler. A theoretical analysis the number of shots in few-shot learning. In ICLR, 2020.
Wei-Yu Chen, Yu-Chiang Frank Wang, Yen-Cheng Liu, Zsolt Kira, and Jia-Bin Huang. closer look at few-shot classification. In ICLR, 2019.
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Incremental learning- to-learn with statistical guarantees. Conference on Uncertainty Artificial Intelligence, pp- 457-466, 2018a.
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Learning to learn around common mean. In Advances in Neural Information Processing Systems, pp. 10169-10179, 2018b.
Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to-lean stochastic gradient descent with biased regularization. In International Conference on Machine Learning. 2019.
Simon S. Du, Wei Hu, Sham M. Kakade, Jason D. Lee, and Qi Lei. Few-Shot Learning via Learning the Representation, Provably. In 2.XXiv:2002.094344, 2020.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Monel-Agnostic Meta-Learning for Fast Adapta- tion of Deep Networks. In International Conference on Machine Learning, 2017.
Chelsea Finn, Aravind Rajeswaran, Sham M. Kakade, and Sergey Levine. Online meta-learning. In International Conference Machine Learning, 2019.
Yaroslav Ganin and Victor Lempitsky. Unsupervised Domain Adaptation by Backpropagation. In International Conference on Machine Learning, pp. 1180-1189 2015.
Spyros Gidaris and Nikos Komodakis. Dynamic Few-Shot Visual Learning Without Forgetting. In CVPR, pp. 4367-4375, 2018.
Micah Goldblum, Steven Reich, Liam Fowl, Renkun Ni, Valeriia Cherepanova, and Tom Goldstein. Unraveling Meta-Learning: Understanding Feature Representations for Few-Shot Tasks. In In- ternational Conference on Machine Learning, 2020.
Muhammad Abdullah Jamal and Guo-Jun Qi. Task Agnostic Meta-Learming for Few-Shot Learning. In CVPR, 2019.
Mikhail Khodak, Maria-Florina Balcan, and Ameet S. Talwalkar. Adaptive gradient-based meta- learning methods. In Advances in Neural Information Processing Systems, 2019.
Anders Krogh and John A. Hertz. A simple weight decay can improve generalization. In Advances in Neural Information Processing Systems, 1992.
10

---

Under review as a conference paper at ICLR 2021
Iija Kuzborskij and Francesco Orabona. Fast rates by transferring from auxiliary hypotheses. Ma- chine Learning, 106(2):11-1155,22) 2017.
Brenden M. Lake, Ruslan Salakhutdinov, and Joshua B. Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350(6266): (332-66))3332133333 2015.
Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, and Stefano Soatto. Meta-learning with differentiable convex optimization. In CVPR, pp. 10657-10665, 2019.
Adrian S. Lewis and Hristo S. Sendov. Nonsmooth Analysis of Singular Values. Part I: The- ory. Ser- Valued Analysis, 13(3):213-241, September 2005. ISSN 1572-932X, doi: 10.1007/
$11228-004-7197-7 URL https:
Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research, 17:81:1-81:32, 2016.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In ICLR, 2018.
Eunbyung Park and Junier Oliva. Meta-curvature. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alché-Buc, Emily B. Fox, and Roman Gareett (eds.), NeurIPS, pp. 3309-3319, 2019.
Anastasia Pentina and Christoph H. Lampert. A pac-bayesian bound for lifelong learning, In Inter- national Conference on Machine Learning, 2014.
Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals. Rapid learning or feature reuse? Towards understanding the effectiveness of MAML. In ICLR, 2020.
Sachin Ravi and Hugo Larochelle. Optimization as model for few-shot learning. In ICLR, 2017.
Mengye Ren, Eleni Triantafillou, Sachin Ravi, Jake Snell, Kevin Swersky, Joshua B. Tenenbaum, Hugo Larochelle, and Richard S. Zemel. Meta-Learning for Semi-Supervised Few-Shot Classifi- cation. In ICLR, 2018.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet large scale visual recognition challenge. International Journal of Computer Vision, 115 (3):2112252, 2015.
Jake Snell, Kevin Swersky, and Richard S. Zemel. Prototypical Networks for Few-shot Learning. In Advances in Neural Information Processing Systems, 2017.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way prevent neural networks from overfitting. Journal of Machine Learning Research, 1989-19999999988 2014.
Nilesh Tripuraneni, Chi Jin, and Michael I. Jordan. Provable Meta-Learning of Linear Representa- tions. In arXiv:2002.11664 2020.
Vladimir Vapnik. Principles of risk minimization for learning theory. Advances in Neural Infor- mation Processing Systems, 1992.
Mingzhang Yin, George Tucker, Mingyuan Zhou, Sergey Levine, and Chelsea Finn. Meta-learning without memorization. In ICLR, 2020.
11


Reviews:
[{"review_id": "xJ6wWTQcOB", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "To improve the practical performance of meta-learning algorithms, this paper proposes two regularization terms that are motivated by two common assumptions in some recent theoretical work on meta-learning, namely (1) the optimal (linear) predictors cover the embedding space evenly, and (2) the norms of the optimal predictors remain bounded as the number of tasks grow. Numerical experiments show that the proposed regularization terms help achieve better performance of meta-learning in some tasks.\n\nThis work serves as a nice attempt to instruct the practice of meta-learning with theoretical insights. Below are some of my concerns.\n\n- In some experimental results, the improvement due to the proposed regularization seems to be at the same level of the standard deviation, as well as the difference between the reproduced results of existing meta-learning algorithms and those reported in earlier papers. This casts doubt on the true efficacy of the proposed methods.\n\n- For the loss function in Eq. (4), it is more reasonable and natural to introduce two weighting parameters (as tunable hyperparameters) for the proposed regularization terms.\n\n- The authors often talk about \"enforcing/ensuring the assumptions\". However, from my understanding, whether the assumptions (on the optimal linear predictors, or \"ground-truth\" predictors) hold or not depends on the learning problem itself, NOT on the algorithms. Therefore, there is no way we can enforce/ensure these assumptions. I would prefer using the phrase \"respecting the assumptions\" (used by the authors on Page 8); this seems more accurate and reasonable. \n\n- Following the previous point, I'm curious about one question: if the learning problem actually doesn't satisfy the two assumptions, then is it still helpful to add the proposed regularization terms to the loss function? (I'm not sure, but my guess is no; indeed, it might even hurt.) To solve puzzles like this, I would encourage the authors to conduct some synthetic experiments, where they can design the data generating process (e.g. they can control whether the true linear predictors satisfy the assumptions or not). Since this work is a connection between theory and practice, I believe that experiments with synthetic data can help explain things more clearly and make the claims more convincing.", "extra_scores": {}, "extra_text": {}}, {"review_id": "w8T96h1n7jE", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\nSummary:\n \nThe paper reviews common assumptions made by recent theoretical analysis of meta-learning and applies them to meta-learning methods as regularization. Results show that these regularization terms improve over vanilla meta-learning.\n\n##########################################################################\nReasons for score: \n\nOverall, I vote for reject. The main idea of applying theory to practice is reasonable, but the regularization methods proposed are mainly known. Regularizing the singular value is similar to the spectral normalization proposed in [1]. The Frobenius norm regularization is similar to the commonly used weight decay.\n\n##########################################################################\n1.\tAssumption 1 in Du et al. states that the ground truth weight should cover all directions evenly. It cannot be ensured when the tasks are fixed. The proposed regularization penalizes the condition number of the weight matrix during training, which is more similar to the spectral normalization proposed in [1]. As to regularizing the Frobenius norm, there exist a line of literature showing weight decay works for general settings apart from meta-learning. Thus, I think the regularization proposed in this paper is known.\n2.\tThe experimental results indeed improve over vanilla meta-learning. However, as shown in [2], even by with some simple tricks, meta-learning can be more stable and achieves better results. This casts doubt on the value of the proposed method.\n\n[1] Spectral Normalization for Generative Adversarial Networks, ICLR 2018\n[2] HOW TO TRAIN YOUR MAML, ICLR 2019\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "rFEvcC0xEkH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The main motivation of this paper is based on the theoretical results of meta-learning. To ensure the assumptions of the theories, the authors propose a novel regularizer, which improves the generalization ability of the model. Some results on few-shot learning benchmarks show the proposed method improves w.r.t. those baselines.\n\nHere are the main concerns of this paper:\n1. The proposed method in this paper is based on the meta-learning theory as stated in Section 2. However, the theoretical setting here is not fully consistent with the few-shot learning setting. For example, there is no validation set in Eq. 1. The authors should make more discussions here to show will these differences influence the final results.\n2. One main theoretical assumption in meta-learning theory is the task distribution. Could the authors make this notion clear? Should we do empirical results on those tasks with different kinds of task distributions?\n3. The meta-learning loss in Eq. 4 is a bit different from the popular meta-learning objective. For example, in MAML, we do not optimize the classifier W till convergence while only a limited number of gradient steps are used. \n4. The authors should list those baseline values in Table 1, which are still important for reference.", "extra_scores": {}, "extra_text": {}}, {"review_id": "DQYVztNHIyL", "reviewer": "AnonReviewer1", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nIn this paper, the authors aim at bridging the gap between the practice and theory in meta-learning approaches. Specifically, they propose two regularization terms to 1) capture the diversity of the tasks and 2) control the norm of the prediction layer, thereby satisfying the assumptions in meta-learning theory.\n\nStrength:\n+ The motivation of this paper is interesting, before proposing the methodology. These theoretical assumptions have not been paid enough attention before.\n+ The paper is well-organized and clearly written. \n+ The experimental setting is designed in a good manner and the results are promising.\n\nWeakness:\n- I am skeptical of the novelty of the second regularize in Eq.(4). According to Section 3.2, it is equivalent to ||w||_{2}=O(1). So what is its difference to a simple l2 weight decay?\n- According to Section 2, the outer-level parameters are restricted as a linear layer. Is this means the proposed regularizes would become trivial while applied on top of a more complicated model, e.g., LEO[1]?\n- Too few competitors. It would be better to add some comparisons with recent methods.\n- The details to calculate the subgradients of the singular values, which is quite complicated, are missing. Especially seeing that there is no guarantee that an auto-differentiation tool will do that correct.\n\nRef:\n[1] Andrei A. Rusu, Dushyant Rao, Jakub Sygnowski, Oriol Vinyals, Razvan Pascanu, Simon Osindero, Raia Hadsell: Meta-Learning with Latent Embedding Optimization. ICLR 2019\n\nAbove all, since the contribution and the technical details to calculate the subgradients are not clear to me, I have to currently recommend a weak reject. \n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is a systematic study of how assumptions that are present recent theoretical meta-learning bounds are satisfied in practical methods, and whether promoting these assumptions (by adding appropriate regularization terms) can improve performance of existing methods. The authors review common themes in theoretical frameworks for a meta learning setting that involves a feature learning step, based on which linear predictors for a variety of tasks are trained. Statistical guarantees for such a framework (that is, statistical guarantees for the performance of trained on an additional target task) are based on the assumption that the set of weight vectors of the linear predictors span the space (ie exhibit variety) and that the training tasks all enjoy a similar margin separability (that is, that the representation is not significantly better suited for some of the tasks than others).

The current submission, cleanly reviews the existing literature, distills out these two properties and then proposes a regularization framework (that could be added to various meta-learning algorithms) to promote these properties in the learned feature representation. 

Finally, the authors experimentally evaluate to what degree the properties are already observed by some meta learning methods, and whether the proposed additions will improve performance. It is established that adding the regularization terms improves performance on most tasks. The authors thus argue that incorporating insights obtained form recent theoretical frameworks of analysis, can lead to improved performance in practice. Naturally, the purpose of the presented results is not to establish a new state of the art on a set of benchmark tasks, but to systematically study and compare the effect of adding regularization terms that will promote the properties that are desirable for a  feature representation based on statistical bounds.

I would argue that the research community should support this type of studies. The work is well presented and conducted. Most importantly, the study has a clear and general message, that will be valuable for researchers and practitioners working in on meta-learning.  

However, the reviewers did not recommend publishing this type of study for ICLR. The authors are encouraged to resubmit their work to a different venue.
Decision: Reject