How Fine-Tuning Allows for Effective Meta-Learning
Authors: Kurtland Chua
Qi Lei
Jason D. Lee
Venue: NeurIPS 2021 Poster (2021)
Keywords: Meta-learning
Few-Shot Learning
Rademacher Complexity
Statistical Learning Theory

Abstract: Representation learning has served as a key tool for meta-learning, enabling rapid learning of new tasks. Recent works like MAML learn task-specific representations by finding an initial representation requiring minimal per-task adaptation (i.e. a fine-tuning-based objective). We present a theoretical framework for analyzing a MAML-like algorithm, assuming all available tasks require approximately the same representation. We then provide risk bounds on predictors found by fine-tuning via gradient descent, demonstrating that the method provably leverages the shared structure. We illustrate these bounds in the logistic regression and neural network settings. In contrast, we establish settings where learning one representation for all tasks (i.e. using a "frozen representation" objective) fails. Notably, any such algorithm cannot outperform directly learning the target task with no other information, in the worst case. This separation underscores the benefit of fine-tuning-based over “frozen representation” objectives in few-shot learning.

How Fine-Tuning Allows for Effective Meta-Learning
Kurtland Chua Princeton University kchua@princeton.co edu
Qi Lei Princeton University qi lei deeeipprinnetoo..mm edu
Jason D. Lee Princeton University
jasonlee@princetoon.ee
Abstract
Representation learning has served as a key tool for meta-learning, enabling rapid learning of new tasks. Recent works like MAML learn task-specific representa- tions by finding an initial representation requiring minimal per-task adaptation (i.e. fine-tuning-bet based objective). We present theoretical framework for analyzing a MAML-like algorithm, assuming all available tasks require approximately the same representation. We then provide risk bounds predictors found by fine- tuning via gradient descent, demonstrating that the method provably leverages the shared structure. We illustrate these bounds the logistic regression and neural network settings. In contrast, we establish settings where learning one represen- tation for all tasks (i.e. using "frozen representation" objective) fails. Notably, any such algorithum cannot outperform directly learning the target task with no other information, in the worst case. This separation underscores the benefit of fine-tune te--ttnnnnn--sse over "frozen representation" objectives in few-shot learning.
Introduction
Meta-learning (Thruu & Pratt 2012) has emerged as an essential tool for adapting prior knowledge tasks under data and computational constraints. In this context, meta-learner has access to related source tasks from a shared environment. The learner aims to uncover inductive biases from the source tasks to reduce the sample/computationaal complexity of learning new tasks from the same environment. A common approach is representation learning (Bengio et al.) 2013). i.e. learning feature extractor from the source tasks. At test time, learner adapts to new task by fine-tuning the representation and retraining the final layer(s) (see, e.g., prototype networks (Snell al. 2017)). Substantial improvements over directly learning a single task has been shown few- shot learning (Antoniou et al. (1122018) natural setting in many applications including reinforcement learning (Mendonca al. 2019 Finn al. 2017), computer vision (Nichol al. 2018). federated learning (McMahan et al. 2017 and robotics (Al-Shedivat et al.) 2017).
The empirical success of representation learning has led to increased interest in theoretical anal- yses of underlying phenomena. Recent work assumes an explicitly shared representation across tasks (Du al., 2020; Tripuraneni et al. 2020bla) a Saunshi et al. 2020 Balcan al.) 2015). For instance. Du et al. (2020) prove a generalization bound consisting of representation error term and an estimation error term. However, without fine-tuning the whole network, the representation error accumulates to the target task and is irreducible, even with an infinitely large target task dataset. This result is consistent with empirical findings. which suggest that fine-tuning the whole network provides substantial performance gains, compared to just learning the final linear layer (Chen et al.) 2020 Salman et al. 2020). Due to the lack of (representation) fine-tuning while training on the source tasks, we refer to methods above as making use of "frozen representation" objectives.
Linear separability of tasks on the same features poses additional problems, being an unrealistic assumption when transferring knowledge to other domains (e.g. from ImageNet to medical images (Raghu et 2019)). Therefore, consider more realistic setting where the available tasks only approximately share the same representation. In this setting, we propose a theoretical framework for
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

analyzing the sample complexity of fine-tuning, using an initial representation from a MAML-like algorithm. We show that fine-tuning quickly adapts new tasks, requiring fewer samples certain cases compared to methods using "frozen representation" objectives. To the best of our knowledge, no prior theoretical studies exist beyond fine-tuning a linear model (Denevi et al. 2018 Konoheev et al. 2020; Collins et al.] 2020a] [ee et al. 2020) or only the task-specific layers (Du et al. 22020) Tripuraneni et al. 2020b a: Mu et al., 2020). Tripuraneni et al. (2020b), in particular, acknowledge that their work does not incorporate representation fine-tuning, leaving such analysis to future work. is this gap which we now seek to address.
The following outlines this paper and its contributions:
In Section 2 outline the general setting and our overall assumptions. Additionally, we introduce ADAPTREP, the representative ine-tuning-base algorithm we analyze in this work. As a baseline, also formally define FROZENREP, which makes use of a "frozen representation" objective.
we provide an in-depth analysis of the (d-dimensional) linear representation setting, when learning k-dimensional representation. First, we show that ADAPTREP achieves rates of
In Section g
T Tsource 0
ldd TgT
+
k +
t ng
and Ttarget = =0 =0 +00
tr oT
+ +ssurree
ng
on the source and target tasks. Here, ns and or are the number of available samples, T is the number of source tasks, ōy is the norm of the representation change, and Σ is the input covariance. Thus, fine-tuning can handle the misspecified setting. In contrast, FROZENREP has a minimax rate of (dd/rr) the target task under certain task distributions, matching standard linear regression. We provide a formal construction and an experimental verification of the gap Section C.
In Section we extend the analysis to general function classes. We provide risk bounds of the form
ÉOPT + SEST SREPR
where SOPT, SEST, SREPr are the optimization, estimation, and representation errors, respectively,
The optimization error SOPT quantifies the error from using approximate minima found during optimization. To control EOPT, our analysis accounts for nonconvexity introduced by representation fine-tuning, and is presented as a self-containg result in Section H.
The estimation error EEST stems from fine-tuning to the target task with finite or samples. therefore scales with //VTUT and is controlled by the complexity of the target fine-tuning set.
The representation error EREPH is the error incurred by representation learning the source tasks while adapting to them. It consists of two terms: one scaling as 1/ /ngT for learning an initialization using all T' source tasks, and the other scaling 1/ /Tg for learning task-specific adaptations.
In Section 5 we instantiate our guarantees in the two-layer neural network setting. Additionally, we provide analysis for logistic regression in Section F. Furthermore, extend the linear hard case to nonlinear setting in Section G.
1.1 Related Work
The empirical success of MAML (Finn et al. 2017). and meta-learnin in general, has elicited further theoretical analysis from both statistical and optimization perspectives. flurry of work engages in developing more efficient and theoretically-sound optimization algorithms (Antoniou
Nichol et al. 2018 Li et al. 2017) or convergence analyses (Fallah et al., 20200] Zhou et al. 2019 Rajeswaran et al.] 2019 Collins et al. (2020b). Inspired by MAMI,, a subseqent line of gradient-based meta-learning algorithms have been developed and widely used (Nichol et al. 2018
al. 2018
Al-Shedivat et al. 2017 Jerfel et al., 2018). Much follow-up work focused the online setting,
with accompanying regret bounds (Denevi et al. 2018 Finn et al. 2019
2019 Khodak et al. 2019 Balcan
ct al. 2015 Alquier et al. 2017 Bullins et al. 2019 Pentina & Lampert 2014).
The statistical analysis of meta-leaming traces back Baxter (2000): Maurer Jaakkola 2005
which focused on inductive bias learning. Following the same setting, AAit & Meir (0018); Konobeev al. (2020): Maurer al. Pentinna & Lampert (2014) fix a meta-distribution for source task sampling, and measure the average generalization error/gap over the meta distribution.
Another line of work connects the target performance to source using distance measures between
distributions (Ben-Davite & Borbely 2008 Ben- et al. 2010 Mohri & Medina 2012). Finally,

---

another series of works studied the benefits of using additional "side information" provided with task for specializing the parameters of an inner algorithm (Denevi et al. 2020 2021
The hardness of meta-learning has also been investigated under various settings. Recent work has studied meta-learning performance in worst-case settings (Collins et al. [2020b) Hanneke & Kpotufe 2020a b Kpotufe & Martinet [0018] Lucas et al. 2020). Hanneke & Kpotufe (2020a) provide no- free-lunch result with a problem-independent minimax lower bound, while Konobeev al. (2020) also provide problem-dependent lower bound on simple linear setting.
2
General Setting
2.1 Notation
Let [n] = (1....,m} m). We denote the vector L2-norm as |1-112, and the matrix Frobenius norm as ||- Additionally, ()-)) can denote either the Euclidean inner product or the Frobenius inner product between matrices.
For matrix A, we let a,)) denote its 7th largest singular value. Additionally, for positive semidef- inite A, write (A) and ( for its largest and smallest eigenvalues, and 1 for its principal square root. We write PA for the projection onto the column span of A, denoted Col A, and P = / PA for the projection onto its complement.
We use standard O θ, and Ω notation to denote orders of growth. We also use a S or a < to indicate that (b). Finally, we write x for ((b).
2.2 Problem Setting
Preliminaries. Fix an imput space X' C Rd and label space y C R. We assume that the learner has access to T source tasks. Each task t E [T] is associated with a distribution f4 over the set x y of input-label pairs. From each μę, the learner observes ns i.i.d. samples {( yi,e) i E [ns] } which we collect into matrix X, E IR's xd and a vector Ye E R=s, Finally, we measure learner performance using the loss function f:
y + R.
We aim to find common structure among the source tasks that could be leveraged for future tasks. In this work, such common structure is defined using representations, mappings Φ X' 2 from the input space to latent space Z C R These representations lie in some function class parameterized by normed space. However, unlike prior work, we do not assume that all tasks use single representation. Instead, there is a fixed 0n such that the predictor for task t can be written as æ + (w,, de, (z)),, with O, lying near Ou (that is, 10, - 0pl is small).
ADAPTREP Procedure. Following the discussion above, consider the objective
T nss
min 0g
min ME
E(wwe, do, (I;,)) Ve.e)
(1)
n
||0 10--0oll:60
S60
for some fixed dg O. which will be the main focus of this work. We refer to ①1 as ADAPTREP, as it finds an initialization de, for which every task has a good representation nearby, ensuring ease of fine-tuning. ITP can be viewed as iMAML (Rajeswaran et al.] 2019) and Meta--MinibttchProx (Zhou et al., 2019). However, we do not use train- vali--allitionn splits, as is widespread in practice. This is motivated by results in Bai ctt al. (2020), which show that data splitting may be undesirable, assuming realizability. Furthermore, empirical evaluations have demonstrated successes despite the lack of such splits (Zhou et al. 2019).
constrained form of algorithms found in the literature such
FROZENREP Procedure. As a baseline, we will also be studying the ubiquitous "frozen representa- tion" objective, which is analyzed in detail in Du et al. (2020): Tripuraneni et al. (2020b). Formally, this objective can be written as follows:
1
T
ng
min min Op
((ww, da (Ix,e) Vis))
(2)
Tgg
3

---

Since 08, is frozen for all source tasks, we refer to the method above as FROZENREP. In Sections 3.4 and G, we will prove that unlike ADAPTREP, there are cases where FROZENREP is unable to leverage the latent structure in the presence of misspecifications.
Learning Target Tasks. Let Oo be solution (T or (2) The learner obtains nr i.i.d. samples {( 3i)} from a new task with distribution je, which we collect into X E [Rrxx and y E I as before. We adapt the target task using by solving
min 8.
110-60l1 58
for some 2 This learned predictor is evaluated via its population loss over ja, which given by ((x:))) [e((w: &o (z)) .y]. We focus on the few-shot learning setting for the target task, where 'r small, and a learner needs to effectively use the source tasks to sufficiently learn the target task.
Statistical Assumptions and Optimization Oracles. For ADAPTREP to be sensible, we need to ensure that a desirable initialization exists. Accordingly, we assume that for some fg. every task t is associated with (07, wf) where -0 - 0 I 80. so that the associated distribution μr is given by
T~ y x q(- (wi, Øo; (x))).
Here, is an input distribution (same for all tasks), while models label noise. Specifically, in regression, we set y xx] (w, do; (zz)). With an appropriate choice of loss function e, we can guarantee that the optimal predictor under the population loss x + (wf. Øog (x)).
Throughout the paper, we assume access to an oracle for solving [I or (2) similar to Du et al. (2200) Tripuraneni al. (2020b). For detailed analyses of source training optimization, we refer the reader to et al. (2020): Wang et al. (2020). On the other hand, representation fine-tuning introduces nonconvexity during target time not present in prior work, where one simply optimizes a final linear layer (a convex problem). Thus, our bounds explicitly incorporate optimization performance (3). We focus on using projected gradient descent (PGD), which applies to a wide variety settings, under certain loss landscape assumptions. These standalone results are also provided in Section H.
3 ADAPTREP in the Linear Setting
We first examine ADAPTREP in the linear setting to illustrate key ideas. Here, representations are linear transformations Rd + & for d > k so that (z(x) = B x, with distances measured by the Frobenius norm. In this setting, we provide a performance bound for ADAPTREP, and then exhibit specific instance for which FROZENREP fails, establishing our claimed sample complexity gap.
3.1 Statistical Assumptions
Data Sampling. We specialize the statistical assumptions of Section 2.2 Assume that the
input distribution p is zero-mean and has co- variance Σ. Let λ = Amax (E)/ Amin (X) be the condition number of Σ. As in Du et al. (2020).
07
R d
Aj
B"wi
Aiw]
01
we impose the following tail condition on p:
Assumption 3.1. There exists 0 such that if x ~ P. then Σ 1/2x is p--sub- "au-Gaussiar
B* B'wi,
Col B*
This assumption guarantees probabilistic tail bounds for our proofs, and can be replaced with other suitable tail conditions. Finally, we define q (4) NV (n, (²) for a fixed a > 0.
Figure 1: Illustrating the geometry of task param-
eterization in the linear representation setting.
Parameterizing the Tasks. Let B" be the initial representation, and A; be the task-specific change for task t, where ||A; pr & dg- Furthermore, let w e R& be the task-specific weights. The predictor for task t is then given by x (x. (B* A7)w[). We define 0f (B* Ai )uy, and combine (wf) into matrix n [wi...... ......... w E B We illustrate the parameterization in Figure [
A zero-mean random vector is -ub Sub-Gaussian if for any fixed u, E [exp(Ae T u)] S X ||ll p² /2.

---

Assumption 3.2 (Source task diversity). For any t [T]. loo 11 = ( and (W-) = (2(T/k).
Since EiE(H) (Ww* || 1 (TT) by Assumption 3.2, the bound on (W())) implies that the weights covers all directions in IR roughly evenly. This condition is satisfied with high proba- bility when the wę are sampled from sub sub-Gaussian distribution with well-conditioned covariance.
Note that 0r w" + 67, where | = || = O(őg) by Assumption 3.2 Thus, the predictor weights lie near the rank-k subspace determined by B" as illustrated by Figure As convention since the parameterization is not unique, we require (B*) E
for any t E [7].
This is without loss of generality,
can always redefine relevant quantities as needed.
Finally, we evaluate the learner on a target task 0* 3 w" 8* for some wt and ||6* do-
3.2 Training Procedure
Source training, We consider the following regularized form of
min min A. 2nsT
Σ ll X.
A,) (,) A
+
| + ? 1|wel12
(4)
In Section B, we show that the regularization is equivalent to regularizing /xy | consistent with the intuition that A W has small norm. This additional regularization is necessary, since ① only controls the norm of A., which is insufficient for controlling A,W;-
Target training. Let Bo be the output of after orthonormalizing. We adapt to the target task via
1
w) = 2n y 3X (AB, + A) (wo + +
(5)
where AB, = [Bo Bo] E Rdx2 and wy = [u, -u] | for a fixed unit-norm vector u E R This
corresponds to training predictor of the form x (x,, (A + (1 w)). We optimize ( by
performing TPGD steps of PGD) with stepsize on 5 with
C3 = {(A, w) |||| S c |wl|2 S c2/B}
as the feasible set, where we explicitly define and 02 in Section B.
To understand the procedure, note that the predictor has parameter 0 (AA,, B, Awn + Aw), since AB, W/ = of Within Cg, the first two terms have O(1) norm, while || | = (1/3). Thus, for large 3,, the cross term A w is negligible perturbation, and the predictor is approximately linear in (A, w). Consequently, LB is approximately convex in (A, w) within CN, allowing PGD to find near-optimal solution in the constraint
3.3 Performance Bound
Now, we provide performance bound on the performance of the algorithm proposed in Section 3.2 We define the following rates of interest, where Ry(w", 5o) > 0:
rs(ns,T) = o²
+ σōg ||>I|
1/2
kd
2²k
σ
tr
ns
nsT
Tis
2²k k
Vtr + σōn
(1(D))
+
min
krs (rs T), Rs(w", 50) krs(ns, T)
v ttr Σ
nt
/TT
TTT
Theorem 3.1 (Performance guarantee, linear representations), Assume that Assumptions 3.1 and 3.2 hold, ns > p² pd ()))) and nr > 0² ((o(llgg///))) Then there are (), B, TPGD. C₁ 02 (specified in Section B) such that the training procedure in Section 3.2 with high probability, finds 0 achieving excess risk bounded as
ad
E [ix 0" - TT) S min (T())),
2 "This "symmetrization" via Ase commonly used in the neural tangent kernel literature (Chizat et al. 2019 Zhhang et al. 2020), allowing us to set fo, (x) = 0 while ensuring Ap, w E Col B for any us
LLog factors and non-dominant terms suppressed for clarity. Full rates presented in the appendix.
5

---

We prove this result in Section B. Nevertheless, we give an interpretation of r' and Pr below.
Source Training. The rate rs represents the performance of the learner during source training. De- spite misspecifications, the algorithm is able to pool the aggregate nş? 7 samples to learn a common (kd-dimensional) initialization, rate achieved on each task upon inferring the initialization, and therefore decays only with ng. The first is the cost of learning wj. while the second is the cost of learning 87.
shown by the first two terms. The last two terms represent the
Target Training. The rate Fr represents the performance of the learner with fine-tuning. The first two terms and their interpretations analogous to that of the last two terms in rs- On the other hand, the minimum indicates two ways to handle the representation error from source training:
Ignore source error. In the most data-starved regime, we ignore the iniple source error, re- stricting fine-tuning to only learn 8*, Thus, we incur an irreducible error in the form of krs(ns, TD
Fix source error. Alternatively, with more data, we can use fine-tuning to fix the source representa- tion error. This additional complexity captured by the second argument, indicating fine-tuning to vector with norm Rx(w", do) (ns, T). Note that the additional norm shrinks to 0 mg + cc.
Finally, by ignoring the representation Bo completely, we can obtain the alternative trivial o WT rate, which matches the minimax lower bound for standard linear regression (see e.g., Duchi 2016 )
3.4 A Hard Case for FROZENREP
In this section, we present sample complexity separation between ADAPTREP and FROZENREP in the linear setting. We provide the formal construction and an experimental verification of the gap in Section C. Nevertheless, we provide the following informal result:
Theorem 3.2 (FROZENREP-ADAPTU))
Sample Complexity Separation). Assume k = (1) < d.
There exists a family of task distributions T satisfying the conditions of Section 3.1 such that with high probability over the draw of nt Z d target samples, we have the minimax bound
x(0 Bi -w- 8)11
odd
min 60,6
max
E
2
TET 0" Esupp
TT
FROZENREP is provided with infinitely many source tasks and per-task samples from to learn B, and Ne samples from O* to learn (w,, 8). In contrast, by specializing Theorem for the same family, ADAPTREP (with only finitely many source lasks and per-task samples) achieves excess risk bounded as
22d
E TT xT0 -
$ min
VNT
Te
Interpreting the minimax result. Observe that the rate is achievable by performing standard linear regression directly the target samples, with other information. Thus, FROZENREP fails to cap- ture the shared structure from source tasks, in the worst case. Furthermore, in the high-dimensional setting when nt x d, there exists a strict separation between ADAPTREP and FROZENREP that widens as n& + oc.
The minimax bound applies regardless of the target fine-tuning procedure in use, including those used in practice, e.g. iMAML, MetaOptNet (Lee et al. 2019). and R2D2 (Bertinetto et al.] 2019). As FROZENREP is provided with infinitely many source tasks and samples, this failure is thus tirely due to the representation learning algorithm. Altogether, we have established a case where incorporating representation fine-tuning is provably sufficient for handling misspecifications, unlike ubiquitous "frozen representation" objectives.
3.4.1 Intuition
In this section, we provide brief intution behind our construction. Recall that in the linear setting, FROZENREP uses the following objective for obtaining a representation:
B argmin
min
1
11 X,Bw,
ig
100
10;-Bu;13
(6)
B
2ngT
2T
[E(T]
[E[T]
For average target performance, (rs(ns, T) be replaced by rs(ns, T'): see Section F: Du al.
2020

---

By optimizing with respect to the Σ-norm, FROZENREP seeks k-dimensional subspace that cap- as much the predictive signal across all source tasks. However, in general, the E-norm is not aligned with the parameter norm. In other words, small ||0 - Bwlly does not imply that ||0 Bw is small, and thus it may be the case that Bu is difficult to learn during fine-tuning.
A prototypical example of this difference is il- lustrated by Figure where & = The dashed red vector has small parameter norm, and is thus easily learnable by fine-tuning (as demon- strated by norm-based generalization bounds). Thus, a meta-learner should opt learn the space captured by the solid green vector. How- ever, if the 3 is structured so that || " llx > [[B",īll:: then FROZENREP will learn the space spanned by the dashed red vector instead. By appropriately tuning the ratio of the lengths of the two vectors, we obtain the desired result.
Parameter space
"Prediction" space
AiwZ
H"wi
13" mt
Figure 2: Prototypical hard case. While wf smaller (left ligure). FROZENREP learns Ai since it has a larger predictive signal (right figure).
We provide a formal construction in Section C.1.1, including the extension to general k.
4 ADAPTREP in the Nonlinear Setting
We now describe a framework for analyzing fine-tuning in general function classes. To simplify notation, modify the setting in Section 2.2 so that both the representation & and predictor weights w are captured by a parameter 0 E +, with corresponding predictor go-
Loss Notation. We denote the population and excess risk of predictor g with respect to the true predictor g" as
L (o = Expp (Ex- [<(g()),))) C (g. (g.g")== (g.9g" Loo (g" .²)
respectively. Additionally, we let L(g.9") denote the corresponding finite-sample quantity f
Feasible Predictors. For initialization and fine-tuning set C C θ, we define the set Ac = {ge- 0 C}.
Intuitively, this set contains all feasible predictors given initialization 0 and feasible fine-tuning set C. For convenience, we also define the set
[Ac(0] = = {<)))er + (ge (gI(Fa))eE(T) 9I. E Ac(0))
which is a collection of functions mapping X y." This set represents all feasible T-tuples of predictors, for a given initialization and fine-tuning set C.
4.1 Training Procedure
Source Training. Fix a set of possible initializations O, C O, and fine-tuning set Cs. With ni samples for each task (with optimal predictor g;), we consider the objective
Aa
Oo E argmin
Σ min C(ge,97)
(7)
0o
01
# Ecg
By
Note that this corresponds to the ADAPTREP objective in (1) using the combined parameter 0. We illustrate the objective in Figure 3
1 T ==1
Target Training. Fix fine-tuning set CT (not necessarily Cs). Given NT samples from a new task (with true predictor g²), we run PGD on L(ő) = L(go,+5, gī) with feasible set Cr. In this process, PGD is run with TPGD timesteps and step size 77.
min 0ee,
Σ min C(g., g5) SvE.og (0)
Figure 3: An illustration of source training.
NNote that have omitted the samples from the notation for brevity.
7

---

4.2 Assumptions
We rephrase the statistical assumption from Section 2.2 in terms
Aug
of feasible sets Ac( as follows:
Assumption 4.1. There exists 0 such that for every t [T].
Oi E Ac, (0)).
0
0
We illustrate Assumption 4.1 in Figure We also impose the following standard regularity conditions the loss function & Assumption 4.2. For any E V, ((:.y) is 1-Lipschita and convex, and [e(0, y)1 B.
01
Figure 4: Assumption 4.1 If Ac has low complexity, then fine-tuning quickly finds good task-specific parameters for all tasks.
Task Diversity. To ensure transfer from source target, we impose the following condition, a specific instance of which was proposed by Du et al. (2020) in the linear setting, and proposed by Tripuraneni et al. 2020b) for general settings:
Assumption 4.3 (Source tasks are (u, eivveriies.... There exists constants (u,E) such that if p is the distribution of target tasks, then for any 0 E Oo.
2 (5,0g))) (0)
inf
inf gEAc
(x
+
The (,, e)-diversity assumption connects the average source task performance (right) to the average target performance (left). Thus. it ensures that optimizing results in controlled target perfor- mance. We weakened the condition in Tripuraneni et al. (2020b) to bound average target perfor- mance rather than worst-case, as is more suitable for higher-dimensional settings.
Target Loss Landscape. Finally, we impose conditions ensuring that PGD finds a near-optimal solution in Cr. We remark that these assumptions specific to our choice of fine-tunin algorithm. Assumption 4.4 (Approximate linearity in fine-tuning). Let #1....; Then, there exists B, T. such that
; Fur be the set of target inputs.
WT (og0+ B² and
nr
sup BECT VIT
sup B V1
Vogo (1:) L²3
i=1
Assumption 4.5. supsec, |0012 I for some R.
4.3 Performance Bound
Recall that for set H of functions Rdd n samples is given by
R samples, its Rademacher complexity R, (7L)
Rr (H)) = Ex,x
sup NEH
Sighy(aa))
where (Eir) are i..dd. Rademacher random variables and (2x) are i.i.d. samples from some (preset) distribution. We now proceed with our performance guarantee.
Theorem 4.1 (General Performance Bound). Assume that all assumptions in Section 4.2 hold. Let (0.) be the set of iterates generated by PGD following the procedure in Section 4. (step size specified in Section D). Then, with probability at least 5 over the random draw of samples,
Eyanp min C 90).99))) $ 3R +R
I2 + R2
sup Ray [Ac, (0)) + BEEN
B /
TPGD
coPr
FEST
Rug
U [Acs (0))
B
+e.
8T
8vngT
EREPR
TTii not restrictive simply rescale the loss, and is assumed for simplicity of presentation.

---

Note that the Roy complexity term samples from p. Meanwhile, the Rug complexity term samples from T which concatenates T ii.d. samples from p (one for each task) for every draw.
We prove Theorem
in Section D. The Rademacher complexity terms decay in most settings as
U AAc (0) =0 C(OO) LOE
diam Vas
7
Rug
V
sup Rny (Ar (0)) =0
(
diam Cr
0e@n
VIT
where ((Og) measures the complexity of Og and diam Cg and diam CT measures the size of the fine-tuning sets Cs and CT.
Understanding the Bound. We briefly outline out how the assumptions Section 4.2 contribute to the final bound. Let 8opt denote the best solution found by PGD, and define the parameters
OBRM = argmin C(ge, 9²) and == argmin Loo (oo (ge,9"). De (9u)
BEAc, (0o)
That is, ÕRRM is the minimizer of the empirical risk while 0 is the minimizer of the population risk, both within Ac, (0o).
Optimization error (EOPT). The difference in performance between θOPT and PERM. iee. the error due to PGD, is controlled by the assumptions on the target loss landscape.
Ac, (96)
6
Estimation error (EEST). By uniform convergence, ÓERM performs similarly 0, with the difference bounded using Rademacher complexity. By extension, dOpT performs
COPT
0
CREPR
Figure 5: Illustrating the excess risk bound in Theorem 4.1
similarly to 0.
Represntation/aproiiattoo error (EREPR). The average best case excess risk (i.e., the ex- cess risk of 0) is bounded via the performance of the initialization Gg on the source tasks, using (u, e)-diversity Since (7) is a finite-sample estimate of desired bound, we again use uniform convergence arguments, which manifest as the second Rademacher complexity term.
We have included illustration of these three components in Figure
5
Case Study: Two-Layer Neural Networks
We now illustrate our framework by instantiating our bounds in concrete settings. We focus on specializing Theorem 4.1 the two-layer neural networks (this section) and logistic regression (provided in the appendix, Section F). For this section, we fix an activation function a + R.
Assumption 5.1. For any E [-2, 2], (o)()) < L and lo" (t)l < p. Furthermore, o00) 0.
Then, for a constant 3 and 0 = (B, w). where B E Bdx22 2k and w E R², we define the neural network 1/ (x:) Bw" T a (Txx)), z), where is applied elementwise.
5.1 Statistical Assumptions
Data Sampling. For all tasks, the inputs sampled from 1-norm-bounded distribution p. Fur- thermore, g(- (4) is generated as f + n for some ((1)-bounded additive noise 77, similar to Tripu- raneni al. (2020b).
Parameterizing the Tasks. We fix representation B Rdx22 and a linear predictor w R2
In this setting, we consider representation changes lying in a k-dimensional subspace, determined

---

by an orthonorma set of matrices ...... Ai in R unit-norm vectors wi, o7 so that task has parameter
Then, for each t E [T), we have two
1
0: = B' + 3
Σ (6)) w z"i
TE[A]
We assume diversity condition on (w., 67) similar in spirit to the linear version in Assumption 3.2 see Assumption E.2.
With appropriate assumptions on the initialization and large enough 8, the source task predictors behave like their linearizations, i.e. there exists feature vectors ΦB. and war so that
fot (x) F ΦB- (x) ue + BB (I))
Σ [E
5 64
We make use of these assumptions throughout for our result, see Assumption E.1 for the formal statement. Note that ΦB- and B correspond the "activation" and "gradient" features, re- spectively, that are empirically evaluated by Mu et al. (2020).
5.2 Training Procedure
We use the squared error loss train in this setting. Additionally, the training procedure in Section 4.1 with the function class {fg}, with a minor caveat: we set y = 3 during source training, and y O (VTTT) during target training.
With the procedure above, we now define the relevant feasible sets. We set Og the set of initial- izations satisfying Assumption E.1. Finally, we set the constraint sets
Cs [(A, w)
||||| ||ll|2 s 1/5} and C7 (A. w)
|all 1 s 0(1/1))
5.3
Performance Guarantee
With the above assumptions in hand, we proceed with the performance guarantee.
Theorem 5.1 (Neural net performance bound), Assume that Assumptions 5.1 E. and E.2 hold.
Then, if ng 2 nr, there exists setting of the training parameters (see Section E) such that with probability at least 1 - 8, the iterates (6t) satisfy
k
1./2
( I
11
E Esrmp min C (fo,, I
+LL 14)
VnsT +
LVk.
VuT
where log factors have been suppressed for clarity.
6
Conclusion
We have presented. to the best of our knowledge, the first statistical analysis of fine-tuning-batt based meta-learning. We demonstrate the success of such algorithms under the assumption of approxi- mately shared representations between available tasks. contrast, we show that "frozen represen- tation" objectives analyzed by prior work fail under this weaker assumption.
An interesting line of future work is determine ways to formulate useful shared structure among MDPs, i.e. formulate settings for which meta-reiinforemenn learning succeeds and results in im- proved regret bounds for downstream tasks.
7
Acknowledgements
KC is supported by National Science Foundation Graduate Research Fellowship, Grant DGE- 2039656. QL is supported by NSF #2030859 and the Computing Research Association for the CIFellows Project. JDL acknowledges support of the ARO under MURI Award W91 INF-11-1- 0304, the Sloan Research Fellowship, NSF CCF 2002272, NSF IIS 2107304, and an ONR Young Investigator Award.
"Orthonormal with respect the Frobenius (i.e. entrywise) inner product matrices.
10

---

References
Al-Shedivat, M., Bansal, T., Burda, Y. Sutskever, I., Mordatch, I,, and Abbeel, P. Continuous adaptation via meta-learning in nonstationary and competitive environments. arXiv preprint arXiv:1710.03641,, 2017.
Alquier, P., Pontil, M., et al. Regret bounds for lifelong learning. In Artificial Intelligence and Statistics, pp. 261-269. PMLR, 2017.
Amit, R. and Meir, R. Meta-learning by adjusting priors based on extended pac-bayes theory. In International Conference on Machine Learning, pp. 205-214. PMLR, 2018.
Antoniou, A., Edwards, H., and Storkey, A. How to train your maml. arXiv preprint arXiv:1810.09502, 2018.
Bai, Y., Chen, M., Zhou, P.. Zhao, T., Lee, J., Kakade, S., Wang. H., and Xiong, C. How important is the train-validation split in meta-learning? arXiv preprint arXiv:2010. 05843, 2020.
Balcan, M.-F., Blum, A., and Vempala, Efficient representations for lifelong learning and autoen- coding. In Conference on Learning Theory, pp. 191-210. PMLR, 2015.
Baxter, J. A model of inductive bias learning. Journal of artificial intelligence research, 12:149-198, 2000.
Ben-David, S. and Borbely, R. S. notion of task relatedness yielding provable multiple-task learning guarantees. Machine learning, 73(3):773-877, 2008.
Ben-David, S., Blitzer, J., Crammer, K., Kulesza, A., Pereira, F., and Vaughan, J. W. A theory of learning from different domains. Machine learning, 79(1):151-175, 2010.
Bengio, Y., Courville, A., and Vincent, Representation learning: A review and new perspectives. IEEE transactions pattern analysis and machine intelligence, 3588):1988-1828 2013.
Bertinetto, I.., Henriques, J. F., Torr, P. H. S., and Vedaldi, A. Meta-learning with differentiable closed-fone form solvers, 2019.
Bullins, B., Hazan, E., Kalai, A., and Livni, R. Generalize across tasks: Efficient algorithms for linear representation learning. In Algorithmic Learning Theory, pp. 235-246. PMLR, 2019.
Chen, T., Kornblith, S., Norouzi, M., and Hinton, G. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pp. 1597-1607, PMLR, 2020.
Chizat, L., Oyallon, E., and Bach, F. On lazy training in differentiable programming. Advances in Neural Information Processing Systems, 32:2937-2947, 2019.
Collins, L., Mokhtari, A., and Shakkoutai, S. Why does maml outperform erm? an optimization perspective. arXiv preprint arXiv:2010.1440 2020a.
Collins, L., Mokhtari, A., and Shakkottai, S. Task-robust model-agnostic meta-leamning Advances in Neural Information Processing Systems, 33, 2020b.
Denevi, G., Ciliberto, C., Stamos, D., and Pontil, M. Incremental leamiing-t--eeam with statistical guarantees. arXiv preprint arXiv: 1at..1003.00000 2018.
Denevi, G., Pontil, M., and Ciliberto, C. The advantage of conditional meta-learning for biased regularization and fine tuning. Advances in Neural Information Processing Systems, 33, 2020.
Denevi, G., Pontil, M., and Ciliberto, Conditional meta-learning linear representations. arXiv preprint arXiv: 103.1011.00 16277, 2021.
Du, S. S., Hu, W. Kakade, S. M., Lee, J. D.,, and Lei, Q. Few-shot learning via learning the representation, provably. arXiv preprint NTt::2002.004334,, 2020.
Duchi, J. Lecture notes for statisties 3/ engineering 377. URL: http:///stafoord edutclass/stats3! I I/L l/Leecurs/fflll_nnn notes. pdf. Last visited on, 2:23, 2016.
11

---

Fallah, A., Mokhtari, A., and Ozdaglar, A. On the convergence theory of mrudient-basedd model- agnostic meta-learning algorithms. In International Conference on Artificial Intelligence and Statistics, pp. 1082-1092. PMLR, 2020.
Finn, C., Abbeel, P., and Levine, S. Model-agnostic meta-learning for fast adaptation of deep net- works. International Conference on Machine Learning, 2017.
Finn, C., Rajeswaran, A., Kakade, S., and Levine, S. Online meta-learning. arXiv preprint 1rX4v:190..08438, 2019.
Hanneke, S. and Kpotufe, S. A no-free-lunch theorem for multitask learning. arXiv preprint arXiv:2006.15785, 2020a.
Hanneke, S. and Kpotufe, S. On the value of target data transfer learning. arXiv preprint wrXiv:2002.04747, 2020b.
Jerfel, G., Grant, E., Griffiths, T. L.,, and Heller, K. Online gradient-based mixtures for transfer modulation in meta-learning. arXiv preprint arXiv:1812.06080, 2018.
Ji, K., Lee, J. D., Liang Y., and Poor, H. V. Convergence of meta-learning with task-specific adaptation over partial parameters, 2020.
Khodak, M., Balcan, M.-F. F., and Talwalkar, A. S. Adaptive gradient-based meta-learning methods.
In Advances Neural Information Processing Systems, pp. 5917-5928, 2019.
Konobeev, M., Kuzborskij. I., and Szepesvári, C. On optimality of meta-learning in fixed-design regression with weighted biased regularization. arXiv preprint arXiv:2011.00344 2020.
Kpotufe, S. and Martinet, G. Marginal singularity, and the benefits of labels covariate-shift. In Conference On Learning Theory, pp. 1882-1888 PMLR, 2018.
Ledoux, M. and Talagrand, M. Probability in banach spaces: isoperimetry and processes. 1991.
Lee, J. D., Lei, Q., Saunshi, N., and Zhuo, J. Predicting what you already know helps: Provable self-supervised learning. arXiv preprint 1rXiv:2008.00066 2020.
Lec, K., Maji. S., Ravichandran, A., and Soatto, S. Meta-learning with differentiable convex opti- mization, 2019.
Li, Z., Zhou, F., Chen, F., and Li, H. Meta-sgd: Learning learn quickly for few-shot learning. arXiv preprint 1007.0/777098.... 2017.
Lucas, J., Ren, M., Kameni, L., Pitassi, T., and Zemel, R. Theoretical bounds on estimation error for meta-learning. arXiv preprint arXiv:20/0.07140, 2020.
Maurer, A. and Jaakkola, T. Algorithmic stability and meta-learning. Journal of Machine Learning Research, 6(6). 2005.
Maurer, A., Pontil, M., and Romera-Paredes, B. The benefit multitask representation learning. Journal of Machine Learning Research, 17(81):1-32 32, 2016.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication efffccien learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pp. 1273-1282. PMLR, 2017.
Mendonca, R., Gupta, A., Kralev, R., Abbeel, P., Levine, S., and Finn, C. Guided meta-policy search. In Advances in Neural Information Processing Systems, pp. 9656-9667, 2019.
Mohri, M. and Medina, A. M. New analysis and algorithm for learning with drifting distributions. In International Conference on Algorithmic Learning Theory, pp. 124-138. Springer, 2012.
Mu, F., Liang, Y., and Li, Y. Gradients as features for deep representation learning, arXiv preprint arXiv:2004.05524 2020.
Nichol, A., Achiam, J., and Schulman, J. On first-order meta-learning algorithms. arXiv preprint arXiv: 2018.
12

---

Pentina, A. and Lampert, C. A pac-bayesian bound for lifelong learning. In International Conference on Machine Learning, pp. 991-999 PMLR, 2014.
Raghu, M., Zhang, C., Kleinberg, J., and Bengio, S. Transfusion: Understanding transfer learning for medical imaging. arXiv preprint arXiv: arXiv:190..00 1900007200, 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.
Salman, H., Ilyas, A., Engstrom, L., Kapoor, A., and Madry, A. Do adversarially robust imagenet models transfer better? arXiv preprint arXiv:2007.08448 2020.
Saunshi, N., Zhang, Y.. Khodak, M., and Arora, S. A sample complexity separation between non- convex and convex meta-learning. In International Conference on Machine Learning, pp. 8512- 8521. PMLR, 2020.
Snell, J., Swersky, K., and Zemel, R. Prototypical networks for few-shot learning. arXiv preprint arXiv:1003.05175. 2017.
Thrun, S. and Pratt, L. Learning learn. Springer Science & Business Media, 2012.
Tripuraneni, N., Jin, C., and Jordan, M. I. Provable meta-learning of linear representations. arXiv preprint arXiv:2002.11684 2020a.
Tripuraneni, N., Jordan, M., and Jin, C. On the theory of transfer learning: The importance of task
diversity. Advances in Neural Information Processing Systems, 33, 2020b.
Vershynin, Four lectures on probabilistic methods for data science. 2017.
Wang, H., Sun, R., and Li, B. Global convergence and generalization bound of gradient-based meta-learning with deep neural nets, 2020.
Zhang, Y., Xu, Z.-Q. J., Luo, T., and Ma, 7. A type of generalization error induced by initialization in deep neural networks. In Mathematical and Scientific Machine Learning, pp. 144-164. PMIR, 2020.
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. 1534-1544, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] Our introduction outline where each claim appears in the paper.
(b) Did you describe the limitations of your work? [Yes] We have discussed extensively the assumptions that we require to establish our results, see Section 3.1 Section 4.2
Section 5.1 among others.
(c) Did you discuss any potential negative societal impacts your work? [No] our work focuses on analyzing existing algorithms from a theoretical perspective, we do not foresee any negative societal impacts stemming from our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yss]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material notebook is provided to run the simulation outlined Section C.3.
URL)? [Yes] A Jupyter
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section C.3, as well as the provided Jupyter notebook.
(c) Did you report error bars (c.g., with respect to the random seed after running exper- iments multiple times)? [No] Since
simulating regression problems and can sample arbitrarily many times from the task distribution, we only report the mean in experiments.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [No] Our experiments only involve simulations simple settings that do not require extensive compute.
4. If you using existing assets (c.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "janeJIARVHo", "reviewer": "Reviewer_h1FC", "summary": "The authors present a theoretical framework for analyzing the sample complexity of finetuning using an initialization from a MAML-like algorithm. The authors presented statistical analysis of fine-tuning-based meta-learning. They provide risk bounds on predictors found by fine-tuning via gradient descent. They demonstrate the success of such algorithms under the assumption of approximately shared representations between available tasks. They also establish settings where learning one representation for all tasks fails. They show that “frozen representation” objectives analyzed by prior work fail under this weaker assumption. ", "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": "The paper is well written and structured. The theoretical results could be useful for practitioners, such as fine-tuning quickly adapts to new tasks, requiring fewer samples in certain cases compared to using “frozen representation”. It is great to see the authors provide both linear and nonlinear analysis. In the linear case, they show there is a hard case that “frozen representation” fails to capture the shared structure from source tasks. In the nonlinear setting, they provide both linear regression and a two-layer network.\n\nHowever, the paper does not have any empirical verification. I would hope the theoretical result can bring more insight to the questions in practice: \n1) In the few short regimes, the frozen representation is usually preferred over end-to-end finetuning (AdaptiveRep) due to the concern of overfitting. With the theoretical result, how can we determine when to choose FrozenRep or AdaptiveRep?\n2) Ideally the more similar between the source task and the target task, the better the fine-tuning performance. Can the performance bound predict the generalization ability for different tasks?\n3) The linearity approximation in the “target loss landscape” (sec 4.2) seems to be not quite realistic. Previous practical work [1] have shown that end-to-end finetuning or adaptiveRep is often preferred when the target domain is not quite similar to the source domain and larger learning rate is preferred, which makes the linearity assumption invalid. \n\nSome claims can be made clearer, e.g., in line 43 the author claims that “no prior studies exist beyond fine-tuning a linear model or only the task-specific layers”. The authors might want to clarify that it refers to theoretical studies but not practical works. Fine-tuning pre-trained networks in an end-to-end fashion has been common in practice for transfer learning. It would be great to also clarify the difference with previous approaches in the related work section.\n\n\n[1] Li et al, Rethinking the Hyperparameters for Fine-tuning, ICLR 2020", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "OLr2UVWtZqE", "reviewer": "Reviewer_dKjD", "summary": "The paper analyses and compares two approaches (\"AdaptRep\", \"FrozenRep\") to representation-based meta-learning. Such approaches employ representations $\\phi_\\theta(x)$, defining a predictor via $<w, \\phi_\\theta(x)>$. Both $\\theta$ and $w$ are optimised on the target task, with $\\theta$ only being fine-tuned, i.e., constrained to stay close to some initialisation $\\theta_0$. \n\nThe analysed approaches differ in how the initialisation $\\theta_0$ is realised. In both cases, $\\theta_0$ is optimised on the source tasks in order to leverage shared structure, with the difference that (1) the AdaptRep approach allows fine-tuning on the source tasks, i.e., finds an initialisation s.t. every source tasks has good representation close to $\\theta_0$, while (2) the FrozenRep approach does not consider fine-tuning on the source tasks, i.e., optimises for an initialisation which is used for all source tasks without adaptation.\n\nThe authors prove performance bounds of AdaptRep in both the linear and non-linear settings. Furthermore, they provide a worst-case example where FrozenRep is not able to leverage information from the source data (i.e., does not perform better than standard linear regression on the target data), while AdaptRep achieves better sample complexity using source information. Finally, the authors apply their theoretical analysis to the concrete setting of a two-layer neural network as well as to logistic regression.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "Originality: The authors claim to provide the first statistical analysis of \"AdaptRep\"-like algorithms, while previous work focuses on \"FrozenRep\"-like approaches. They clearly work out this distinction in their Introduction and Related Work section. \n\nQuality: The problem setting as well as the compared approaches are stated clearly and in a technically sound manner. The authors make sure to clearly state relevant assumptions for their proofs. I cannot judge the soundness of the proofs themselves.\n\nClarity: The paper is written clearly. I think the authors do a good job in guiding the reader through their paper by stating the main results in simplified form in the introduction and giving intuitive explanations of the results in the main chapters. The mathematical details are quite dense and moved to the appendix. I cannot judge the presentation and clarity of the derivations and proofs. \n\nSignificance: I think that a sound theoretical analysis of MAML-like algorithms (beyond FrozenRep-like approaches) is important and therefore I think the results are interesting for the community. However, I am not familiar enough with the state of the art to fully judge the significance of this work.\n\nIn summary, I think this work is an interesting contribution and presented in a clear and well-written manner. Therefore, I recommend acceptance. However, this recommendation  is with low confidence, as I am not very familiar with the theoretical analysis of meta-learning algorithms. Therefore, I might adjust my rating after the discussion period.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No potential negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Dy0M8CCakE3", "reviewer": "Reviewer_4qNe", "summary": "This paper proposed a theoretical framework for analyzing a type of MAML-like meta-learning algorithms. The algorithm learns an initialization for the representation from a collection of source tasks, with the goal that there is a good representation close to the initialization, as well as an unconstrained predictor, for each of source tasks. Then on a target task, it fine-tunes the representation and trains a predictor altogether. The paper provides risk bounds in linear settings, and points out a separating case where the “frozen representation” approach by Du et al. (2020) cannot achieve the same guarantee. The results are also extended to the general case such as two-layer neural networks.", "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": "- The paper focused on an important formulation of initialization-based meta-learning algorithms. Different from previous work, this paper assumes source tasks, as well as the target task, share only approximately the same representation. That is, it allows for fine-tuning the representation from a learned initialization. The setting is more practical but less theoretically understood. This paper provides a series of theoretical guarantee for risks in linear and more general settings. The results are novel and may be of interest for a broad audience in meta-learning.\n- One concern is the significance of the proposed framework over the frozen representation approach by Du et al. (2020). This paper shows that allowing fine-tuning can achieve strictly better risk bounds than the frozen representation algorithms, but limited to a linear case where tasks are formulated from a shared optimal representation within a small range of perturbation. How does AdaptRep compare to FrozenRep when faced with harder tasks? In particular, how does the general performance bound in Section 4.3 advance over previous work? A detailed discussion would be helpful.\n- In practical algorithms like MAML, the whole model including the representation and predictor is often fine-tuned together. Would the proposed framework provide theoretical guarantee for this setting?\n- In introduction some quantitative results are shown without giving definitions for involved variables, which come clear only in Section 2. The main body of the paper is sometimes notationally dense. It would improve readability if more discussion is provided.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, in the Checklist.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "6naHPXKMu4m", "reviewer": "Reviewer_Jbdo", "summary": "This paper studies the problem of regret bounds for meta-learning where representations are fine-tuned for individual tasks.\n\nThe main contribution of the paper is a theoretical result, showing that (under certain assumptions) learning a fixed representation across all tasks is no better than just using an individual task's data alone. Thus, fixed representations cannot leverage having information from additional tasks. However, the paper also shows that adaptive representations (cases where the representation is allowed to be tuned a little bit for a new task) do not suffer in the same way.\n\nOverall, this provides some theoretical support to recent empirical successes using MAML-like algorithms that fine-tune representations through meta-learning.", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "This paper motivates and studies an important problem. Adding theoretical understanding to when and why meta-learning works is an important problem. This paper focuses on MAML-like algorithms, that is, algorithms that fine tune a representation for a new task. The starting point for the fine-tuning is meta-learned across a distribution of tasks.\n\nMy main concerns with the paper have to do with presentation. While the paper is largely well written, I found myself having a hard time picturing or grasping the intuition behind some of the theoretical results. Perhaps including some kind of simple graphics demonstrating the problem setting might help readers quickly grasp the framework and assumptions used to build the theoretical results.\n\nRegarding the main result, I have some questions about the assumptions made about task distributions. Intuitively, I feel like whether or not this theoretical finding is surprising rests on the assumptions made about the task distribution. How similar are tasks drawn from some task family? That is a hard question, it is not clear to me how to even define similarity across tasks. However, in order for meta-learning to be useful, there must be _some_ shared structure or information across tasks. In this paper, the shared structure across tasks is outlined in the section \"Statistical Assumptions and Optimization Oracles\". If I understand correctly, the paper assumes that:\n(1) data points across tasks are drawn from the same distribution (p)\n(2) labels for a given task are drawn from a distribution conditioned on a representation near a shared representation.\nBasically, this means that there is no model mismatch between the AdaptRep algorithm and the tasks. But there is a mismatch between the FrozenRep algorithm and the underlying data distribution--the modeling assumption of the FrozenRep algorithm (that a single representation is used across tasks) is not valid. As such, I am not sure how surprised I should be by the gap in the regret bounds.\n\nI am also left wondering, are these assumptions valid in practice? For the kinds of tasks where MAML-like algorithms have succeeded, do these assumptions roughly hold? Empirically, can you show in toy settings that the AdaptRep algorithm works when these assumptions are held, but doesn't work when the assumptions are broken?\n\nOverall, I think the paper would be improved with more intuition both on the assumptions behind the method, and on when the assumptions will or won't hold in practice.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides some theoretical insight into when and why fine-tuning is beneficial for meta-learning. Specifically, it shows how learning a single fixed representation for all tasks can fail, and under what conditions allowing the representation to be tuned for downstream tasks can be successful. Reviewers all appreciated the addition of theoretical insight and a framework for understanding meta-learning. The main criticism from reviewers was that it was hard to get intuition for the assumptions made and the settings considered. Authors should include better examples and diagrams in the camera-ready version.
Decision: Accept (Poster)