Few-Shot Learning via Learning the Representation, Provably
Authors: Simon Shaolei Du
Wei Hu
Sham M. Kakade
Jason D. Lee
Qi Lei
Venue: ICLR 2021 Poster (2021)
Keywords: representation learning
statistical learning theory

Abstract: This paper studies few-shot learning via representation learning, where one uses $T$ source tasks with $n_1$ data per task to learn a representation in order to reduce the sample complexity of a target task for which there is only $n_2 (\ll n_1)$ data. Specifically, we focus on the setting where there exists a good common representation between source and target, and our goal is to understand how much a sample size reduction is possible. First, we study the setting where this common representation is low-dimensional and provide a risk bound of $\tilde{O}(\frac{dk}{n_1T} + \frac{k}{n_2})$ on the target task for the linear representation class; here $d$ is the ambient input dimension and $k (\ll d)$ is the dimension of the representation. This result bypasses the $\Omega(\frac{1}{T})$ barrier under the i.i.d. task assumption, and can capture the desired property that all $n_1T$ samples from source tasks can be \emph{pooled} together for representation learning. We further extend this result to handle a general representation function class and obtain a similar result. Next, we consider the setting where the common representation may be high-dimensional but is capacity-constrained (say in norm); here, we again demonstrate the advantage of representation learning in both high-dimensional linear regression and neural networks, and show that representation learning can fully utilize all $n_1T$ samples from source tasks.

Published as a conference paper at ICLR 2021
FEW-SHOT LEARNING VIA LEARNING THE REPRESENTATION, PROVABLY
Simon S. Du' Wei Hu²*, Sham M. Kakade Jason D. Lee and Qi Lei2*
University of Washington PPrinceton University Microsoft Research (ssdu, sham) @cs. washington. (huwei@cs., jasonleeß, qilei princeton.edu
ABSTRACT
This paper studies few-shot learning via representation learning, where one uses source tasks with n1 data per task to learn a representation in order to reduce the sample complexity of a target task for which there is only nz( < n1) data. Specifi- cally, we focus the setting where there exists good common representation between source and target, and our goal is to understand how much a sample size reduction is possible. First, we study the setting where this common representation is low-dimensional and provide risk bound of Ō T Re
di .k) on the target task for
the linear representation class; here is the ambient input dimension and k(<<< d) is the dimension of the representation. This result bypasses the 22( ())) barrier under the i.i.d. task assumption, and can capture the desired property that all n I samples from source tasks can be pooled together for representation learning. We further extend this result to handle general representation function class and obtain a similar result. Next, we consider the setting where the common representation may be nigh-dimensional but is demonstrate the advantage of representation learning in both high-dimensional linear regression and neural networks, and show that representation learning can fully utilize all RTT samples from source tasks.
constrained (say in norm); here, we again
INTRODUCTION
A popular scheme for few-shot learning, i.e., learning in a data-scarce environment, is representation learning, where one first learns feature extractor, or representation, e.g., the last layer of con- volutional neural network, from different but related source tasks, and then uses simple predictor (usually a linear function) on top of this representation the target task. The hope is that the learned representation captures the common structure across tasks, which makes linear predictor sufficient for the target task. If the learned representation is good enough, it is possible that a few samples sufficient for learning the target task, which can be much smaller than the number of samples required to learn the target task from scratch.
While representation learning has achieved tremendous success in a variety of applications (Bengio lt al. 2013), its theoretical studies are limited. In existing theoretical work, the most natural algorithm explicitly look for the optimal representation given source data, which when combined with (different) linear predictor on top for each task can achieve the smallest cumulative training error on the source tasks. Of course, it is not guaranteed that the representation found will be useful for the target task unless one makes some assumptions to characterize the connections between different tasks. Existing work often imposes probabilistic assumption about the connection between tasks: each task is sampled i..d. from an underlying distribution. Under this assumption, Maurer et al. (016) showed an Ö VT + vmz ) risk bound on the target task, where T is the number of source tasks, 71 is the number of samples per source task, and n2 is the number of samples from the target lask Unsatisfactorily, this bound necessarily requires the number of tasks T' to be large, and it
Alphahetical Order.
We only focus on the dependence T, nı and in this paragraph. Note that Maurer et al. 2016 only considered ni ng, but their approach does not give better result even if n n2.

---

Published as a conference paper at ICLR 2021
does not improve when the number of samples per source task, 71, increases. Intuitively, one should expect more data to help, and therefore an ideal bound would be vn: + vha realizable case). because ne T is the total number of training data points from source tasks, which can be potentially pooled to learn the representation.
(or R1T + in the
Unfortunately, as pointed out by Maurer et al. (2016). there exists example that satisfies the i.i.d. task assumption for which 92 (TT) is unavoidable (or ( in the realizable setting). This means
that the i.i.d. assumption alone is not sufficient if we want to take advantage of a large amount of samples per task. Therefore, natural question is:
What connections between tasks enable representation learning to utilize all source data?
In this paper, we obtain the first set of results that fully utilize the n, T data from source tasks. We replace the ii.. assumption over tasks with natural structural conditions the imput distributions and linear predictors. These conditions depict that the target task can be in some sense "covered" by the source tasks, which will further give rise the desirable guarantees.
First, we study the setting where there exists a common well-specified low-dimensional representation in source and target tasks, and obtain an Ö di + & ) risk bound on the target task where d is the nT
vng
ambient input dimension, &(<<< d) is the dimension of the representation, and ng is the number of
data from the target task. Note that this improves the d rate of just learning the target task without my
dk indicates that we can fully exploit all ni data in the using representation learning. The term n.T source tasks to learn the representation. We further extend this result to handle general representation function class and obtain an Ö ((+) n; + nez risk bound on the target task, where & is the representation function class and (+) is a certain complexity measure of $.
Second, we study the setting where there exists common linear high-dimensional representation for +
source and target tasks, and obtain an Ō( R (T(TE RV RVIE21,) rate where R is a normalized nuclear norm control over linear predictors, and Σ is the covariance matrix of the raw feature. This also improves over the baseline rate for the case without using representation learning. We further extend this result to two-layer neural networks with ReLU activation. Again, our results indicate that we can fully exploit n source data.
Vnz
A technical insight coming out of our analysis is that any capacity- controlled method that gets low test error on the source tasks must also get low test error on the target task by virtue of being forced to learn good representation. Our result on -ighndiiensional representations shows that the capacity control for representation learning does not have to be through explicit low dimensionality.
Organization. The rest of the paper is organized as follows. We review related work in Section 2 In Section 3 we formally describe the setting we consider. In Section]] we present our main result for low-dimensional linear representation learning. A generalization nonlinear representation classes is demonstrated in S3ction In Section 6, we present our main result for high-dimensional linear representation learning. In Section 7 we present our result for representation learning in neural networks. We conclude in Section g and leave most of the proofs to appendices.
RELATED WORK
The idea of multitask representation learning at least dates back to Caruana (997); Thrun and Pratt (1998); Baxter (2000). Empirically, representation learning has shown its great power in various domains; see Bengio et al. 2013) for survey. In particular, representation learning is widely adopted for few-shot learning tasks (Sun et al. 2017 Goyal al., 2019). Representation learning is also
closely connected to meta-learning (Schaul and Schmidhuber 2010). Recent work Raghu et al., (2019) empirically suggested that the effectiveness of the popular meta-learning algorithm Model Agnostic Meta-Learning (MAML) is due to its ability to learn useful representation. The scheme we analyze in this paper is closely related to Lee et al. (2019); Bertinetto et (2018) for meta-learning.
On the theoretical side, Baxter (2000) performed the first theoretical analysis and gave sample complexity bounds using covering numbers. Maurer et al. (2016) and follow-up work gave analyses on the benefit of representation learning for reducing the sample complexity of the target task. They
assumed every task is i.i.d. drawn from an underlying distribution and can obtain an O / + mg
2

---

Published as a conference paper at ICLR 2021
rate. As pointed out in Maurer et al. (2016), the / dependence is not improvable even if n1 oo because 1 is the rate of concentration for the distribution over tasks. VT
The concurrent work of Tripuraneni et al. (2020) studies low-dimensional linear representation learning and obtains a similar result as ours in this case, but they assume isotropic inputs for all tasks, which is special case of our result. Furthermore, we also provide results for high-dimensional linear representations, general non- con-linear representations, and two-layer neural networks. [Tripuraneni et al.) (2020) also give a computationally efficient algorithm for standard Gaussian inputs and lower bound for subspace recovery in the low-dimensional linear setting.
Another recent line of theoretical work analyzed gradient-based based meta-learning methods (Denevi et al. 2019; Finn et al., 2019 Khodak et al. (2019) and showed guarantees for convex losses by using tools from online convex optimization. Lastly, we remark that there are analyses for other representation
learning schemes (Arora et al. 2019 McNamara and Balcan 2017: Galanti et al. 2016 Alquier
al. 2016 Denevi al. 2018
3 NOTATION AND SETUP
Notation. Let [n] 21, nJ.
We use ||-|| or ||-1|a to denote the & norm of a vector or the spectral norm of matrix. Denote by |1-1|,= and |l-ll. the Frobenius norm and the nuclear norm of matrix, respectively. Let (-.-) be the Euclidean inner product between vectors or matrices. Denote by the identity matrix. Wet,V o² /N Σ) be the one-dimensionna/mulli mamaiiionammmuui--dmmnnioaaall Gaussian distribution, and (m) the chi-squared distribution with m degrees of freedom.
For matrix A Rmx, let o, (A) be its i-th largest singular value. Let span(A) be the subspace of RT spanned by the columns of A, i.e., span (A) = (Av E R"). Denote PA A(A A)TAT AT Rmxm, which is the projection matrix onto span( A). Here stands for the Poore-Pennoss pseudo- inverse. Note that 0 PA 3 I and PA = PA We also define Pt matrix onto span( (A)+, the orthogonal complement of span A) in I For a positive semidefinite (psd) matrix B, denote by Amax and Amin its largest and smallest eigenvalues, respectively: let B1/2 be the psd matrix such that (B112222 B.
- PA. which is the projection
We use the standard O(.), (2-) and ((-) notation to hide universal constant factors. We also use a S or Z a to indicate a = O(b), and use a >> oo b < a to mean that a 2 C- for a sufficiently large universal constant C > 0.
Problem Setup. Suppose that there are source tasks. Each task / E [T] associated with a distribution μr over the joint data space X x Y, where X is the input space and Y is the output space. In this paper we consider X C Rd and Y C R. For each source task t E [T]] we have access to ni i..dd samples (It,,1, .t,1),.... (Zt.n) Ut,n;) from fte- For convenience, collectively an input matrix X, E R and output vector y: R
express these nı samples
Multitask learning tries to learn prediction functions for all the source tasks simultaneously in the hope of discovering some underlying common property of these tasks. The common property consider in this paper is a representation, which is function Φ X + Z that maps an input to some feature space Z C R We restrict the representation function to be in some function class T e.g., neural networks. We try to use different linear predictors on top of a common representation function model the input-output relations in different source tasks. Namely, for each task / [7]. we set the prediction function to be + (w,, øl ((x)) (w, E R²)) Therefore, using the training samples from T tasks, we can solve the following optimization problem to learn the representation?
T
minimize d ..... tor ER
(Br.1 (w,, 2
(1)
2n,T
We overload the notation to allow ó to apply to all the samples in a data matrix simultancously, i.e. ((X,) = (d(#..),.... (0 ) E 1g Then ( can be rewritten as
T
minimize
Σ 1=1
11 ((X,) 1
(2)
& (ECt,.LL.. p0 Wr CR 2n, T
We use the f2 loss throughout this paper.
3

---

Published as a conference paper at ICLR 2021
Let ò & be the representation function obtained by solving 2 Now retain this representation and apply it to future (target) tasks. For a target task specified by distribution pr-1 over x Y, suppose receive n2 ii.d samples XT+1 R=2xd yr+1 E _= We further train a linear predictor on top of e for this task:
minimize
UT++ 6(XT+))) (
(3)
WT+1 ERR 2m1
Let ur++ be the returned solution. We are interested in whether our learned predictor + (WT+11 ((x)) works well average for the target task, i.e. we want the population loss
p (ô, wT+1) = B(a.))/TT: 2 (1br+1, o(z)))²
to small. In particular, we are interested the few-shot learning setting, where the number of samples n2 from the target task is small much smaller than the number of samples required for learning the target task from scratch.
Data assumption. In order for the above learning procedure make sense, assume that there a ground-truth optimal representation function o² E and specializations wi.... WT+1 E R for all the tasks such that for each task E [T + I], we have w [u|z]] = (w) x0 (x)). More specifically, we assume (x: y) ~ fe can be generated by
y (w) @ (x)) + 2, x p O((,
where and are independent. Our goal is bound the excess risk of learned model on the target task, i.e., how much our learned model (ő, wT4+1) performs worse than the optimal model (Ø" w)+1) on the target task:
ER(å wr++) = Tepr+ (e, uTT+1) 1) - Lor (0) w
1
(5)
Eeppri Il ( (wi+1: ( (z))))
2
Here have used the relation a random target task (i.e., 41 is random). In such case we look at the expected excess risk
44. Oftentimes
interested in the average performance
Ewiyy [RR(,, wT++1)).
LOW-DIMENSIONAL LINEAR REPRESENTATIONS
In this section, we consider the case where the representation a linear map from the original input space Rd to now-dimensional space R$ (k < d). Namely, we let the representation function class be ① = {xc + B æ B E Bdxk). Then the optimization problem
2 for learning the representation
can be written as:
T
(B, (B,W)= + arg min BeadxR w-fwe leTerke
Σ y:
X,Bw,11
(6)
2n T
The inputs from source tasks, X
Xx E B xd can be written in the form of linear operator
X' p + B xT where
x())
[ 0
4A [ Or] E Rdxx
With this notation, can be rewritten as
1
(B.W)
arg min
||Y -
X(BW) where Y = (y....., .T] E R
BeRaxk WEREET 2nTT
With the learned representation / from for the target task, we further find linear function on top of the representation:
uT arg min
yT+I XT- Bw
(8)
WER*
2nz
4

---

Published as a conference paper at ICLR 2021
As described in Section 3 assume that all T + 1 tasks share common ground truth representation
specified by a matrix B E Raxk such that a sample (x, y) ~ [4g satisfies a ~ Pr and y = o") is independent of æ. Here w, RR, and assume | || = (1) for all f. E [T + I]. Denote W = [wi,..., wi E T Then we can write
(w)) ) x + where 2
Y X (B W*) 7, where the noise matrix Z has i.i.d. (V x²) entries.
Assume Eg Ep [a]] O and let Σ, = Em [xx J for all t E [T + 1]. Note that a sample x ~ Pr
and Ee-p, (+e | = (F, is called the whitening of Pt.) In this section we make the following assumptions on the input distributions P1....,Pr+1.
can be generated from 21/²2 for Pt such that Ez [+]
Assumption 4.1 (subgaussian input). There exists > O such that, for all & [T + 1), the random vector x ~ P: is p² ossubgaussian
Assumption 4.2 (covariance dominance). There exists 0 such that E, e. fo all t [T]]
Assumption 4.1 is a standard assumption in statistical learning to obtain probabilistic tail bounds used in our proof. It may be replaced with other moment boundedness conditions if we adopt different tail bounds in the analysis.
Assumption 4.2 says that every direction spanned by Σr+1 should also be spanned by E, (t E [T], and the parameter e quantifies how "easy" is for Σg to cover Σx+1- Intuitively, the larger e is, the easier it is cover the target domain using source domains, and we will indeed see that the risk will be proportional to _ We remark that we do not necessarily need Σ, غ c ΣT+1 for all / E [T]: as long as this holds for a constant fraction of i ss our result is valid.
We also make the following assumption that characterizes the diversity of the source tasks. Assumption 4.3 (diverse souree tasks). The matrix W [wi..... w/r R satisfies (W") (
Recall that || ((),, which implies Σ 03 || (T)). Thus, Assumption 4.3 is equivalent to saying that ex(W") = O(1. Roughly speaking, this means that {w) )E([T] can cover all directions in RR* As an example, Assumption 4.3 is satisfied with high probability when w²,'s are sampled i..d. from (0, 2) with Amax
0(1.
Amiin (2)
Finally, we make the following assumption the distribution of the target task. Assumption 4.4 (distribution of target task). Assume that follows a distribution u such that
[Eusolwur (ww T]ll < 0 (
@()), the assumption || TIl < O means that the distribution of + does not align with any direction significantly more than average. It is useful to think of the uniform distribution the unit sphere example, though can allow much more general class of distributions. This is also compatible with Assumption 4.3 which says that wo 's cover all the directions.
Since we assume || |w
Assumption 4.4 can be removed at the cost of slightly worse risk bound. See Remark 4.1 Our main result this section is the following theorem.
Theorem 4.1 (main theorem for linear representations). Fix a failure probability 8 E (0, 1). Under Assumptions 4.7 4.2 4.3 a.3d 4.4 we further assume 2k min(d, (d,T) and that the sample sizes in
source and target tasks satisfy nı >> p²(dd + log 4), n2 > p² + log } and em 2 n2. Define maX Xmax(E,) mitli(()) Amin (2.) Then with probability least d over the samples, the expected excess
risk of the learned predictor x + + Ba on the target task satisfies
k log
Ewitr (RR( w wT+1) 0²
.nnTT
112
'A random vector is called pubbaauussin if for any fixed unit vector v of the same dimension, the random variable B" T x is p² subgausssi,,, i.c., Ble (a-E(a))] S ?2/22 (vs E R). 4.2 * "Note that Assumption 4.2 is significant generalization of the identically distributed isotropic assumption Ex+1
used in concurrent work Tripuraneni (2020): they require E, Eg
5

---

Published as a conference paper at ICLR 2021
The proof of Theorem 4.1
in Appendix Theorem 4.1 shows that it is possible to learn the target task using only ( samples via learning a good representation from the source tasks, which better than the baseline (dd) sample complexity for linear regression, thus demonstrating the benefit of representation learning. also shows that all nı 7 samples from source tasks can be pooled together, bypassing the ( barrier under the i.i.d. tasks assumption.
Remark 4.1 (deterministic target task). We can drop Assumption 4.4 and easily obtain the following excess risk bound for any deterministic wi++1 by slightly modifying the proof of Theorem 4.
(
(Hgl)g))))) en,TT
k2
h: +og
ER(B, uT+ S o²
CTL
122
which is only most times larger than the bound in
5 GENERAL LOW-DIMENSIONAL REPRESENTATIONS
Now return to the general case described in Section 3 where we allow a general representation function class Q. We still assume that the representation is of low dimension & like in Section and assume that inputs from all the tasks follow the same distribution, i.c., P1
Pr-1 p.
but each task t still has its own specialization function wi (c.f. (4) We overload the notation from Section and use X' to represent the collection of all the training inputs from T source tasks ,,,...,Xy E RPixx xd We can think of N' as a third-order tensor of dimension n x x T.
To characterize the complexity of the representation function class b need the standard definition of Gaussian width.
Definition 5.1 (Gaussian width). Given set C R", the Gaussian width of K. is defined as: G (KC) == () supwek (v, z).
We will measure the complexity of using the Gaussian width of the following set that depends on the input data X:
Fx = {AA= [a...... arl E RTIXT xT ||A||= 11
(10)
3d. ø' E σ s.t. ('))
We also need the following definition. Definition 5.2 (covariance between two representations). Given distribution q over Rd and two representation functions o, ø' E tb, define the covariance between & and o' with respect to to be
My (b,  = Eewn @ (x) o' (x)
R
Also define the symmetric covariance
Σg (0, Φ) Eng (0'
Σg (o. Φ') Eg (el )0)
Ag(s, 6')
E 2k
It is easy to verify Ay(o, 0') 2 0 for any o, o' and q. shown in the proof of Lemma B.2
We make the following assumptions on the input distribution p. which ensure concentration properties of the representation covariances.
Assumption 5.1 (point-wise concentration of covariance). For E (0, 1), there exists number Npoine ( p. 8) such that if n N Npoine (4, p. 6), then for any given o, o' D. i...d. samples of p will with probability at least - 8 satisfy
0.94,  = Ap(d, = 1.1),(0
where P is the empirical distribution over the n samples.
Assumption 5.2 (uniform concentration of covariance). For 8 E (0, 1), there exists a number
Nunif (L. 8) such that if 2 Nunit (T. (o.p. 8), then n i.i.d. samples of p will with probability at least 1 satisfy
0.9 3 Ag(d. Φ)) 3 16I Vá, ol EΦ.
where i is the empirical distribution over the samples.

---

Published as a conference paper at ICLR 2021
Assumptions 5.1 and 5.2 conditions the representation function class & and the input distribu- tion p that ensure concentration of empirical covariances to their population counterparts. Typically, expect Numi (R,p, 6) > Nooint (Ø, p, 6) since uniform concentration is stronger requirement. In Section 4 we have essentially shown that for linear representations and subgaussian input distribu-
tions, N Nunif Φ p. 5) = (d) and ponint (P = (k) (see Claims A.1 and A.2
Our main theorem in this section is the following:
Theorem 5.1 (main theorem for general representations). Fix a failure probability E (0, 1). & Suppose n 2 Nuii @ 3T and n2 2 point. (Q, p. 3) Under Assumptions 4.3 and 4.4 with
probability at least 1 - over the samples, the expected excess risk of the learned predictor (1-11(()) on the target task satisfies
Ew ~ [RR(Ø iT++)) o² (((xx())) + log
(
k
log
+
(11)
n2 T
72
Theorem 5. is very similar to Theorem 4. in terms of the result and the assumptions made. In bound (TI). the complexity of & is captured by the Gaussian width of the data-dependent set Fx (T) defined in (T).. Data-dependent complexity measures are ubiquitous in generalization theory, one of the most notable examples being Rademacher complexity. Similar complexity measure also appeared in existing representation learning theory (Maurer et al. 2016). Usually, for specific examples, can apply concentration bounds to get rid of the data dependency, such representations (Theorem 4.1
result for linear
Our assumptions on the linear specification functions w the same in Theorem 4.1 The probabilistic assumption on + can also be removed at the cost of an additional factor of in the bound see Remark 4.1 We defer the full proof of Theorem 5.1 Appendix B
HIGH-DIMENSIONA. LINEAR REPRESENTATIONS
In this section, we consider the where the representation is general linear map without explicit dimensionality constraint, and we will prove a norm-based result by exploiting the intrinsic dimension of the representation. Such a generalization is desirable since many applications the representation dimension is not restricted.
Without loss of generality, we let the representation function class be + - (ar - T B E RdxT), We note that dimension-TT representation is sufficient for learning T source tasks and any choice of dimension greater than T' will not change our argument. We use the same notation from Section unless otherwise specified.
In this section we additionally assume that all tasks have the same input covariance: Assumption 6.1. The input distributions in all tasks satisfy Σ
EE =
Note that each task still has its own specialization function un"" (c.f. 4)) We remark that there are many interesting and nontrivial scenarios under Assumption 6. for example, consider the case where the inputs each task are all images from ImageNet and each task asks whether the image is from specific class.
Since we not have dimensionality constraint, we modify 7 by adding norm constraints:
(,, W)
arg min
Y -X(B) + | + A
+
(12)
BER WeRTXT 2m
For the target task, we also modify ( by adding a norm constraint:
üT <- arg min
2n2 X| Bw yr41
(13)
We will specify the choices of regularization, i.e., À and in Theorem 6.1
Similar to Section the source task data relation is denoted as = xt(e")= + Z. where O* E RdXT is the ground truth and Z has i..dd o²) entries. Suppose that the target task data satisfy yr+1 = Xx+ 07 + 2T+1 E R", Similar to the setting in Section we assume the target task data is subgaussian in Assumption 4.1
7

---

Published as a conference paper at ICLR 2021
Theorem 6.1 (main theorem for nigh-dimensional representations). Fix a failure probability 8 (0, 1). Under Assumptions 4.1 and 6.1 we further assume n1 2 n2, R= ||0|| Let 2///T. R = /T and proper X specified in Lemma C.2 Let the target task model 0/+1 be coherent with the source task models @* in the sense that 0++1 ~ === (O (*())) (T) Then with probability
at least 1- 8 over the samples, the expected excess risk of the learned predictor ++ 2 w BT the target task satisfies:
VTrEE)
Eo; ~M [ER(B,
wT++1) S ò
+
+ Smi,702
(14)
VnnT
where Smimng P
Tr
E n2
is lower-order terms due to randomness of the input data.
nu
Here Ô hides logarithmic factors.
The proof of Theorem 6.1 is given in Appendix C Note that || vT when each 07 is of unit norm. Thus R | T should generally be regarded O(1) for well-behaved @ that is nearly low-dimen diwdieeniiinal. In this regime, Theorem 6.1 indicates that we are able to exploit all ny T samples from the source tasks, similar Theorem 4.1
With a good representation, the sample complexity on the target task can also improve over learning the target task from scratch. Consider the baseline of regular ridge regression directly applied the target task data:
θ + arg min
|
yr+ill2.
(15)
e 01
2nz
Its standard excess risk bound in fixed design is ER S a 2012).) Taking expectation over 0 ~ = (0*00000)
0 0 (T)))
(See e.g.
Hsu et al.
T), we obtain
| ||
Tr(E)
Ee ER [
(16)
VT
122
Compared with (16), our bound (4 is an improvement as long as
1 |
Tr(E) TXI
The left hand
side ||@1||2
is always no more than the rank of θ", and we call it the intrinsic rank. Hence we see that can gain from representation learning if the source predictors intrinsically low dimensional.
||@-1|
To intuitively understand how this is achieved, we note that a representation B is reweighing linear combinations of the features according to their "importance" on the T source tasks. We make an analogy with a simple case of feature selection. Suppose we have learned a representation vector b where b, scales with the importance of the i-th feature, i.e., the representation ((x)) (entry-wise product). Then ridge regression on the target task data (X, y). minimize|| w|l] Sr 2ng || diag(b) (b))(bbww-aa - 112. is equivalent to minimize)jdis()))>>> we see that the features with large [b, (those that were useful on the source tasks) will be more heavily used than the ones with small [b, due to the reweighed & constraint. Thus the important features are learned from the source tasks, and the coefficients are learned from the target task.
b
1 |X - From the above equation, 2nd
Remark 6.1 (The non-convex landscape). Although the optimization problem (12) is non-convex, its structure allows to apply existing landscape analysis of matrix factorization problems (Haeffele) et al. 2014) and to show that it has the nice properties of no strict saddles and no bad local minima. Therefore, randomly initialized gradient descent or perturbed gradient descent are guaranteed to
converge to a global minimum of (12) (Ge et al.) [203): Lee et al. 2016 Jin et al.) 2017).
Remark 6.2 (Multi-class problems). When both source and target have multi-class labels instead of
independent tasks, using quadratic loss on the one-hot labels, our results apply similarly and will
attain an excess risk of the form o RRŌ
TT(
VIEElla
plus lower-order terms (see e.g. Lee
el al. 2020g) ). Notice the result is independent of the number of classes.
7 NEURAL NETWORKS
In this section, we show that we can provably learn good representations in neural network.
8

---

Published as a conference paper at ICLR 2021
Consider two-layer ReLU neural network f (x) w (B" 1)=²,)+, where E R, B E R
and æ E RR Here (+)+ is the ReLU activation (z)+ max 2] defined element-wise. Namely, we let the representation function class be = {a (B3 x)+ E Rdoxd. On the source tasks
use the square loss with weight decay regularizer
X W 1
(B,W) W)
arg min
Σ 11
(X,B) w 12
BERdoxd xd Be wrr/ WTJERIXT 2n
(17)
On the target task, we simply re-train the output layer while fixing the hidden layer weights:
1 -1llr++1
uTT+1 arg min
w0l2
(18)
|w 2n2
PT+1 = p. We redefine Σ to be the covariance operator of the feature induced by ReLU, i.e., it is kernel defined by E(u, v) = E Exz=p(( [(u TuTTa x)+(w' (l for u, v on the unit sphere Sdo-1 Rdo.
Assumption 7.1. All tasks share the same input distribution: P1
Assumption 7.2 (teacher network). Assume for the source tasks that = (X₂ u + zt is generated by a teacher network with parameters B gdoxdd W' = [wi. ..... wT] E RdxT, and noise term
(0, I²1). A standard lifting of the neural network is: fa, = (ar, o(x)) where Φ(x) 3d 1 - R. Φ(z) (b x)+ is the feature map, i.e., each task, ar (b,/ ||::lll
and is zero elsewhere. We assume crr+1 that describes the target function to follow a Gaussian process μ with covariance function K ((, b') =E=raa())ay a,(b)ay(b')
Theorem 7.1. Fix a failure probability å E (0, 1). Under Assumptions 4.1
7.1 and 7.2 let m 2 n2.
R = = IP + [
Let the target task model far.1 = (AT+1. (x)) be coherent Then
with the source task models in the sense that aT ~ V. Set r2 BI + (l: TTTThe with probubility least 5 over the samples, the expected excess risk of the learned predictor
20 41 x)+ the target task satisfies:
VT(EE)
/|1|22
Barhiwy (ER(E (r
B. 1
+ Guy,ngg
(19)
VTTT
TT2
where Smimy p² R Tr
Σl
is lower-order term due to randomness of the input data.
12
To highlight the advantage of representation learning, we compare to training a neural network with weight decay directly on the target task:
B, w) = arg min
|1 - (XT+1 w)
(20)
B B, Bwll <R 2n 1=1
The error of the baseline method fixed-design is
Tr(E)
E SRR
(21)
112
We see that Equation 19 is always smaller than Equation (1 since n,T 2 n2. See Appendix for the proof Theorem 7.1 and the calculation of (2T).
8 CONCLUSION
We gave the first statistical analysis showing that representation learning can fully exploit all data points from source tasks to enable few-shot learning on a target task. This type of results were shown for both low-dimensional and high-dimensional representation function classes.
There are many important directions to pursue in representation learning and few-shot learning. Our results in Sections 6 and 7 indicate that explicit low dimensionality capacity control also forces the classifier to learn good representations. Further questions include whether this a general phenomenon in all deep learning models, whether other capacity control can be applied, and how to optimize to attain good representations.
necessary, and norm-based
Wei al. (2019) show that 17) can be minimized in polynomial iteration complexity using perturbed gradient descent, though potentially exponential width is required.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
SSD acknowledges support of National Science Foundation (Grant No. DMS-1638352) and the Infosys Membership. JDL acknowledges support of the ARO under MURI Award W91 1911NN-11-1 0303, the Sloan Research Fellowship, and NSF CCF 2002272. WH is supported by NSE, ONR, Simons Foundation, Schmidt Foundation, Amazon Research, DARPA and SRC. QL is supported by NSF #2030859 and the Computing Research Association for the CIFellows Project. The authors also acknowledge the generous support of the Institute for Advanced Study on the Theoretical Machine Learning program, where SSD, WH, JDL., and QI. were participants.
REFERENCES
Pierre Alquier, The Tien Mai, and Massimiliano Pontil. Regret bounds for lifelong learning, arXiv preprint arXiv:1610.006 08628, 2016.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. A theoretical analysis of contrastive unsupervised representation learning. In Proceedings of the 36th International Conference on Machine Learning. 2019.
Jonathan Baxter. A model inductive bias learning. Artif. Int. Res., 2000.
Yoshua Bengio, Nicolas L Roux, Pascal Vincent, Olivier Delalleau, and Patrice Marcotte. Convex neural networks. Advances in neural information processing systems, pages 123-130, 2006.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions on pattern analysis and machine intelligence, 35(8):1798-1822 1828. 2013.
Luca Bertinetto, Joao F Henriques, Philip HS Torr, and Andrea Vedaldi. Meta-lcarning with differen- tiable closed-form solvers. arXiv preprint arXiv: 018.8000008000 08136, 2018.
Rich Caruana. Multitask learning. Machine Learning, 28(1): Jul 1997. ISSN 1573-0565. doi: 10.1023/A:10077376607744
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Incremental learning-to- learn with statistical guarantees. arXiv preprint arXiv:1803.08003 2018.
Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to- tere-tto-eeen learn stochas- tic gradient descent with biased regularization. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online meta-learning. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Tomer Galanti, Lior Wolf, and Tamir Hazan. A theoretical framework for deep transfer learning. Information and Inference: Journal of the IMA, 5(2): 2099999092200 2016.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points online stochastic gradient for tensor decomposition. In Proceedings of The 28th Conference on Learning Theory, pages 797-842, 2015.
Priya Goyal, Dhruv Mahajan, Abhinav Gupta, and Ishan Misra. Scaling and benchmarking self- supervised visual representation learning. In Proceedings of the IEEE International Conference on Computer Vision, pages 6391-64001 2019.
Benjamin Haeffele, Eric Young, and Rene Vidal. Structured low-rank matrix factorization: Optimality, algorithm, and applications to image processing. International conference on machine learning. pages 2007-2015, 2014.
Daniel Hsu, Sham M Kakade, and Tong Zhang. Random design analysis of ridge regression. In Conference learning theory, pages 9-1, 2012.
10

---

Published as a conference paper at ICLR 2021
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael I. Jordan. How escape saddle points efficiently. In Proceedings the 34th International Conference on Machine Learning. pages 1724-1732, 2017.
Mikhail Khodak, Maria-Florinn Balcan, and Ameet Talwalkar. Adaptive gradient-based meta-learning methods. arXiv preprint arXiv: 02717, 2019.
Jason D Lee, Max Simchowitz, Michael Jordan, and Benjamin Recht. Gradient descent only converges minimizers. In Conference on Learning Theory, pages 1246-1257, 2016.
Jason Lec, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo. Predicting what you already know helps:
Provable self-supervised learning. arXiv preprint arXiv:2008. 01064, 2020.
Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, and Stefano Soatto. Meta-learning with differentiable convex optimization. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 10657-10665. 2019.
Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes, The benefit of multitask representation learning. The Journal of Machine Learning Reseurch, 17(1):253328844 2016.
Daniel McNamara and Maria-Florina Balcan. Risk bounds for transferring representations with and without fine-tuning In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 2373-2381 JMLR. org, 2017.
Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals. Rapid learning feature reuse? towards understanding the effectiveness of maml. arXiv preprint 1901097909.09157, 2019.
Saharon Rosset, Grzegorz Swirszez, Nathan Srebro, and Ji Zhu. 11 regularization in infinite dimen- sional feature spaces. In International Conference on Computational Learning Theory, pages 544-558. Springer, 2007.
Tom Schaul and Jürgen Schmidhuber. Metalearning. Scholarpedia, 5(6):4650, 2010.
Nathan Srebro and Adi Shraibman. Rank, trace-norm and max-norm. In International Conference on Computational Learning Theory, pages 545-560. Springer. 2005.
Chen Sun, Abhinav Shrivastava, Saurabh Singh, and Abhinav Gupta. Revisiting unreasonable effectiveness of data deep learning era. In Proceedings of the IEEE international conference on computer vision, pages 843-853 2017.
Sebastian Thrun and Lorien Pratt. Learning Learn: Introduction and Overview, pages 3-17. Springer US, Boston, MA. 1998. ISBN 978 1--411--5522211 doi: org
URL (tttpp///2bbl.oogg1000000/111113
Nilesh Tripuraneni, Chi Jin, and Michael Jordan. Provable meta-learning linear representations. arXiv preprint arXiv: /684, 2020.
Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trends@ in Machine Learning, 6(1-2):1-230) 2015.
Roman Vershynin. Four lectures on probabilistic methods for data science. luttps://axxt
prgg/ddf/6612.6666 066612.6666611 pddf 2017.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. In Advances in Neural Information Processing Systems, pages 9709-9721. 2019. 2019.
11

---

Published as a conference paper at ICLR 2021
A PROOF OF THEOREM 4.1
We first prove several claims and then combine them finish the proof of Theorem 4.1 We will use technical lemmas proved in Section A.I
Claim A.1 (covariance concentration of source tasks). Suppose nn > p' log(T/6)) for & over the imputs .I...., XT the source tasks, we have 10
(0, 1). Then with probability at least
0.90,
x, x, Xt = 1.12,
Vt E (T].
222)
n
Proof. According to our assumption on Pt, we can write X; = =X where X E RRixdd xd and the of X, hold i.i.d. samples of pt. Since pt satisfies the conditions in Lemma A.6 from Lemma A.6 we know that with probability at least 107
0.91
X, X₁ 3 1.11,
m
which implies
0.90, = //
X 1/2
x, X, 3 1.14,
The proof is finished by taking union bound over all t [7].
Claim A.2 (covariance concentration of target task). Suppose n2 >> p² + log(1/5)) for ō E (0, 1). Then for any given matrix B E Rx that is independent of X1+1, with probability at least over X1+1 we have
L n2
0.9B ET+1 B
XT+11 B 3 1.1B" ET+1B. B.
(23)
Proof. According to our assumption on PT+1, we can write XT+1 = X where XT+1 Raaxd and the rows of X hold i.i.d. samples of Pr+1- We take the SVD of x1/2 B: 2 UDVT, where U E Rdx2k has orthonormal columns. Now we look at the matrix X U E R22x2k It is easy that the rows of Xr+1U are i.i.d. 21-dimensional random vectors with zero mean, identity covariance, and are p²-subgaussian. Therefore, applying Lemma A.6, with probability at least 1 we have
0.91 = 1 LU 1 1.11,
12
which implies
1 0.9VDDV 3 VDU TT AT LLIVDDVT.
n12
Since 1 DU T XT=UUV = 1
XTT
1/2 = 1 B X XT41
and VDDVT= -VDUTUDV -B B. the above inequality becomes
0.9 Er+ - B X 1.1B
ET+IB.
Claim A.3 (guarantee on source training data). Under the setting of Theorem 4.1 least 1 8
with probubility at
we have
5
| B-W") o (KT + log((m)) + log(1/5))-
(24)
Proof. We assume that 22 is true, which happens with probability least 10
according to
Claim A.I
Let é BW and 0 B', From the optimality of / and W for 7 have x <
|| II Plugging in Y = x((e)) + Z, this becomes
| 0² 2222, 0*))
(25)
12

---

Published as a conference paper at ICLR 2021
Let A = 6 0r. Since rank( < 2k, can write A = VR [Vri, Vrrl where V Od.2 and R = [ri, TTl E 22xx Here On,,d, (d1 2 d2) is the set of orthonormal dj d2 matrices (i.e., the columns are orthonormal). For each t E [T] further write X,V U,Q.
where U+ E On, 28 and Qe E 222 Then we have
(Z,x(A))
Σ
2, XiVri
Σ 2, U.Qir
UU ze|| :1Qtrel
T
Σ 110 21 1|?
Qumil
T
|1 21 2|
U1Qer111
T
11 2/1??
|rVrr
T
| 2, 2:11? -1x(
(26)
Next we give a high-probability upper bound on Σ |,,T ze I1 using the randomness in Z. Since U,'s depend V which depends on Z, will need an e-net argument cover all possible V E Od.2k First, for any fixed V E Od.2k. we let X,V = U,Q, where U, E On The U,' defined in this way are independent of Z. Since Z has i.i.d. (N0,, o2) entries, we know that 0- E [0 z.Il² is distributed x²(2kT). Using the standard tail bound for x² random variables, know that with probability at least 8' over Z,
10, 2
S KT + log(1/8").
Therefore, using the same argument in (66 we know that with probability least 1 8',
(2, (2, R)) Sa KT log(1 [))l
Now, from Lemma A.5
we know that there exists an e-net V of O4z in Frobenius norm such that
N C d,24 and [ S
6v/2k 2kd
Applying a union bound over N, we know that with probability
at least 1 - N')
(z, (V.((R)) S SovkT KT log(1/8)) [
V.
(27)
Choosing 8'
we know that
(7 holds with probability least 1
20( Gv jakd
20
We will use
and
complete the proof of the claim. This is done in the following steps:
1. Upper bounding | p.
Since
2 1
(2 we know that with probability at least 5
20
| S o² (nI7 T log(1/5))
(28)
13

---

Published as a conference paper at ICLR 2021
2. Upper bounding ||||| p-
From 25) we have || I 2
|
which implies ||*( S 2 2
0 ov 01 T + log(1/5). On the other hand, letting the 1-th column of be o,, we have
8, X X,
t=1
0.9m1
8, Eg
(using 22
2 0.9m1
Amin (Ex) ||,11
2 0.9m/
where min Amin (E.)) Henee we obtain
|
(n T + log(1/6)
| 2 S
x
a1d
nid
3. Applying the e-net M.
Let E A such that IIV 11p Se.
Then we have
| R - VR) 1|2
Xc(V - V)rll'
|x,1| - 111 |r:11
1.1n Amax (E,)e² ||r111
(using 22
< de |R
(A Amax (E,))
tE|T
=1.1m |A
(| = I RlI ||
SniZe2 ( + log(1/6))
11n
=x2 (ni + log(1/8)).
(29)
4. Finishing the proof.
We have the following chain of incqualities:
2 |((|
< <ZZ,X(A)
(using 25
=Z, (VV)) + (Z, VR))
SOVAT + (188)) [((R))] + |Z |X(VR- -VVV-
(using 27
So KT + log (1 [2]
|
+ a m log(1)) X
+ovmm
(using 28
14

---

Published as a conference paper at ICLR 2021
[ log(1/8))) [ VR) (using k. my and 8' < <
SovkT KT + log [X(A) o log(11/8) . 2 + log(1/5))
(using (2
KT + log(1/0") [X + Ea² VE(MT log(1/0'))
Finally, let Veni*
and recall 8'
Then the above inequality implies
20 2x yard
|
max
lVVk KT + 1og((10'), V
co2Vi((ITT log(1/8)))
k
max
KT log (log(118)),))
(n1T log(1/81)
n1
max
σ KT + log
KT log 10g(1/
(using &: < n1))
-o kT + (og((//"))
/ov KT kdlog k.
+ tog
E
S sov KT kd kdllg())1)) log
8"
The high-probability events we have used in the proof are (22p. and (28). By union bound, the failure probability most + 20
6
Therefore the proof is completed.
Claim A.4 (Guarantee on target training data). Under the setting of Theorem 4.1 with probability at 26
least 1 5.
we have
1 12
|||
P
XT+ B By| S 0² (KT + :ed + log !))
en (W*)
Proof. We suppose that the high-probability events in Claims A.
A.2 and A.3 happen, which holds
with probability at least 28
Here we instantiate Claim A.2 using B²) Rdx2k
5
From the optimality of B and W in (6) we know X, Br.. = Px Pr (x, + z,) for each / E [7]. Then we have
o² (KT + kd log(kn)) + log(1/0))
2 XB@ B'
(from 24
T
X,Brü. X.B'w;l'
(X, w; + +2, X, X,B Bu;
| P. X, X X, B2. !
Σ
1 wi
+ || Pxx.B22())
(the cross term is 0)
pd x X,B'
15

---

Published as a conference paper at ICLR 2021
T
2 0.9n1
PL
21/2
/1/2
B'
wi
|
(using 22 and Lemma A.7
t=1
2 0.9cm1
P 51/2
1 "T+11 B
(using Assumption 4.2 and Lemma A.7
[=1
0.9cm1
P1
12/2 T
11/2
B WW
F
2 0.9cm1
p+
- T 1"
1/2
(W*).
Next, write B [B, B*]
BA and D" [B, B*]
BC. Recall that have
LB
X44 B 1.1BB 1.11BE++1 from Claim A.2
X
Then using Lemma A.7
we can obtain
R2
1.1
pl
TT BC
1/2
2
BA
1 BA
F
i.e.
1.1
PL
1//
B
2
p
Xr 8
X B Br+1
X
TT
F
Therefore we get
a² (KT + log((N))) + 1og(1/6))
0.9en1
pL
Xr42 oWW"),
Xr
1.1ng
completing the proof.
Proof of Theorem 4.1 We will use all the high-probability events in Claims A.l A.2
and A.4
Here we instantiate Claim A.2 using
[B, B"] E Rdx2k The success probability is at least
1 5
For the target task, the excess risk of our learned linear predictor (BrrT+1) Tx is
(a (B (BurT+
ER(B, wT+1)
E Em-pr=
B" wi+
BuTT+1 B" w'++++) T (BuTT B wT++))
Applying Claim A.2 with B = [B, B*), we have
1 BT XT+1X
0.9B LT+1B= 1
n12
(WT+1
which implies 0.90 T Ex Bu < BB x
T41 X2 Bu for v
This becomes
w
(BWrT1 B" B" Ex Bwor+ B B'+++))
(BuT+1 B" B"
X B B'w++1):
0.9n2
Therefore we have
1
ER,B, wr441)
(Bur+1 B B'w, T X XT41X B B²
1.8nz
1
XT+1 (Br0T41 - B'
1.8n2
16

---

Published as a conference paper at ICLR 2021
From the optimality of Wr+1 in (8) we know X1+1 X ix (a (XTxx1+1* BB B 2r+1).
B
follows that
ER(B, wT+1) -
P XT (x + 2r+1)
X
1/2
1
-P X B 1T+1
1/2
|2 F 1 n2
pl
X B XT+1 13 w
+
P PrTti
B2T+1
122
Recall that 47 v and denoting E = Ew [ww] T]. we obtain
|| | (uw Ti S O2))
Taking expectation over wh41 ~ and
E Ewg me (ER(B (, rZT+1]]
PL Xr X W [2]
1
|
+
P P
112
n2
Ewitr
pl
X XT+1 B BhT wT++11++
(Px
&T+IBB
]
+
&xrn182T11
2
112
112
P XT+1 B³) |
Tr pl BT+I
p
2T+1
112
n22
1
1
2
PL
X XT+1
B 1/2
+
P
&rr:82T+11
122
112
<
pll
X
X B
|2
|//
1
P 2T+1
F
T12
pp
XT X B"
P +
P
(using |
12k
112
o² (KT + kd log (ogg(n))))
+ 1oolo1(1//)
+
P
22T+1 Px B
(using Claim A.4
en1 (W-)
n22
F
0² (KT + kd log(kn) + log (1/0))
1
12
+
P xx+1
8
xT+
||r
(using of (W")
> T π
C
n2
Px, A 2T ||2
For the second term above, notice that
+
(k)),, and thus with probability at k log J Therefore we obtain the final bound
least 1 5
we have 3/2
P P
#++1
0² (KT + lod(gg)))) + log(1/8))
a² (A: log }
Eng; D [ER wT++)1 (ET(B)
eniT
n12
kdd kdllg(()1)) en1T cnnT
k. log 1 cn₁
A + log 3
=
en
722
(dlog(()
+ log 1
S 0²
+
cniT
n1
where the last inequality is due to en 2 n22
A.1 TECHNICAL LEMMAS
Lemma A.5. Let Osrds = {V E Rdixda VTV (di 2 d2), and E (0, 1). Then there exists
subset N C Odi,dn that is an c-net of Od, de in Frobenius norm such that |N| & (6v ydi i.e. for any V E Od,dd there exists V E E such that IV V'Il <
Proof. For any V Od each column of V has unit & norm. It well known that there exists an 2/d, -net (in l norm) of the unit sphere in Id with size (o/d2 dd. Using this net to cover
17

---

Published as a conference paper at ICLR 2021
all the columns, obtain set N Ie xd xd2 that is an 2 -nnt of Od in Frobenius norm and [W] S (did))
Finally, we need to transform N' into an e-net N that is a subset of d2.. This can be done by projecting each point in N" onto dd Namely, for each V A², let P(V) be its closest point in Od, dd .dz (in Frobenium norm); then define N (P(V) | V AV) Then we have I & [ S (("v (Wdeydid and N is an c-net of Od,, because for any V E Od there exists V E N such that I|V - V I 2' which implies P(V) E N and ||V P(V) VV- V V P(V) S V
2 | V v
S.
Lemma A.6. Let ai..... an be i..dd d-dimensional random vectors such that Ela,] 0, Ela.a and a, p² oS-suagaussian. For E (0, 1), suppose n p² log(1/))). Then with probability at least - 6 we have
1 R 3 Σ n
0.91
a 1.II.
Proof. Let A = 1 Ei= a.a. - J. Then it suffices to show ||||| S 0.1 with probability at least 1 1-8.
We use a standard c-net argument for the unit sphere S (u E Rd ||||| = 1}. First, consider
any fixed v 8d-1, We have T Av = = 2 [[v - From our assumptions a; we know that e a; has mean O and variance and is pussubgaussian (Note that we must have 2 1.) Therefore (v a,)² - 1 is zero-mean and -ub-ee-b-xpoo By Bernstein inequality for sub-exponential random variables, we have for any <>0, 0,
Aul > c] S 2 exp (-2 min (16p²)2 16p² 1)
Pr Tuu|
E
Next, take a g-net N c Sd-1 of g with size W < O(d), By a union bound over all v E N, we have
Pr
max DEN
l0 AAul > 2|/ exp (-2 min
n
(16p2)2'
2
16p })
6²
exp ((d)) min
(16p2)21 16p²
Plugging in e 1 and noticing >> 1, the above inequality becomes
20
1
n (1/20)²
Pr
max vEN
l0 T Au
I exp O(d) 2 (16p?)²
S 6,
20
where the last inequality is due > pt (d + log(1/))).
Therefore, with probability at least 1 - we have maxvEN t0 Aul S
1 Suppose this indeed
20
happens. Next, for any E Sd-1, there exists u' E V such that ||u u'll S g. Then we have
lu T Aull < (u') Au'l| + [| (0))= = + (1 u²) A(u u')ll
1
<
+
2
||u
- u'll ||A||| |/241| + -u--uuu - -111" ||A||
20
1
1
2
<
+
2
||A||| 1+
5 |||||
20
5
1
<
+
||A||
20
2
Taking a supreme over E Sd we obtain |||| <
1 + |||||, i.c., ||||| < TO 26
1
Lemma A.7. two matrices An and A₂ (with the same number of columns) satisfy AT A1 then any matrix B (of compatible dimensions), we have
AJ Ag.
AT PA,BA1 2 A PA.
18

---

Published as a conference paper at ICLR 2021
As a consequence. for any matrices B and B' (of compatible dimensions), have
|| B B'I 2 B2
Proof. For the first part of the lemma, it suffices to show the following for any vector
A PA B 2 r Ag PA. A2
which is equivalent
min || and 2 min |A2Bw A2u112
Let wn E arg min
|| Bw - A Then we have
min |l Bu A 211 ||A1 Bw" Aivl12
(Bw" u) A A (Bww" 4)
2 (Bw" - T) A A2 (Bw" - V)
|A22B - A2v112
2 min |A, A2u 1
finishing the proof of the first part.
For the second part, from A PA A = A PA A2 we know
(B') T PL B 2 (B') T Aob.'
Taking trace both sides, obtain
B 2 21 BAB'l
which finishes the proof.
B PROOF OF THEOREM 5.1
Here first prove important intermediate result the in-sample risk, which explains how the Gaussian width of Fx (b) arises.
Claim B.1 (analogue of Claim A.3). Let â and w wi.... uT be the optimal solution 2 Then with probability at least 1 ö we have
T Σ
((()) (X)))x S02 (OLFF(()))) + log 1
Proof. By the optimality of å and uū wi...., uy for (), we know
Σ y: o(X,) u
1 o' (X))
Plugging in y: = 6² (f + 21 (z) NN(0 1) independent Xt), we get
T
(Xi)) + -xx(x)(00 < z
which gives
(((x)) - -x'(X))w;
_ 12, 2( ((x)) w'(
19

---

Published as a conference paper at ICLR 2021
Denote Z = 12 .r| 6 (Xt)w,? Then the above inequality reads ||Al] - 2(Z, A). Notice that follows that
R and A = [[11... .arl E RFIX7 where a, o(X,)
A E Fx(2) (c.f. (00)
|| = 2 22(22
A
S 2
sup (2, A). (EFx(O)
(30)
||A||
By definition, we have Ez sup (o 12, A\ ( Furthermore, since the function
Z SupA (2, A) is 1-Lipschitz in Frobenius norm, by the standard Gaussian concentration inequality, have with probability least 1 6,
sup (0 (0-1 + V log 1 (AEFx(D)
1
sup (0 Z, R
((Fx(()) + 1o8
(EFx(o)
Then the proof is completed using (30
The proof is conditioned on several high-probabiliyy events, each happening with probability least 1- (6)). By a union bound at the end, the final success probability is also at least - 2()). We can always rescale 5 by constant factor such that the final probability is at least 1 8. Therefore, will not carefully track the constants before in the proof. All the 8's should be understood as (2)6).
We the following notion of representation divergence.
Definition B.1 (divergence between two representations), Given distribution q over R&d and two representation functions o, o' E Φ, the divergence between e and o' with respect to q is defined as
(g. Eg (d' 0') Eg (Ø', Φ) (Eg o))² Eg (0, 0')
R bxk
It is easy to verify (6 0¹) = 0, (6 Φ) = 0 for any o, o' and q. See Lemma B.2 proof. The next lemma shows relation between (symmetric) covariance and divergence. Lemma B.2. Suppose that two representation functions Φ, o' E & and two distributions q. of over Rd satisfy (o o') 2 a Ag (é, d') for some a > 0. Then it must hold that D,( Φ¹) 2 a Day (0, d¹).
Proof. Fix any u E R* We will prove o Dy(0, 6'v v Do o' Yu which will complete the proof of the lemma.
We define a quadratic function f RR - as f(w) [
- d')
w -
According to
Definition 5.2 we can write
f(w) w T (0, - 2w Li o') u 2o
= -Ery (wT o(x) - vT [T'(xx))"
Therefore we have f(w) 2 for any w g This means that must have a global minimizer in & Since f is convex, taking its gradient ( 2I, (ò, o)w (0,(0, o') you and setting the
gradient to O, we obtain a global minimzer w" = (Eg (6, t 6. o' yo. Plugging this into the definition of f, we obtair?
min f(w) = f(w=) = Dy(0 d')o. WERL
(31)
Similarly, letting g(w) = [wo - v [A o (0, Φ5)
w
we have
-
min g(w) r D& Φ')0. weRz
Note that we have proved (,  ) 2 0.
NNoe that 33 implies (6 )²) 0.
20

---

Published as a conference paper at ICLR 2021
From 0') = a (r) we know f(w) 2 ag(w) for any R Recall that w² arg we weR f(w). We have
av Dy(o, = a min g(w) S ag(w") S f(w")
weRt
min wE
f(w)= = v T Dy(0. 6')o.
This finishes the proof.
Claim B.3 (analogue of Claim A.4 we have
Under the setting of Theorem 5.1 with probability at least 1 -
x² (G(Fx log }
P
P x0 (X1+2)
722
Proof. We continue the notation from Claim B.1 and its proof.
Let P. be the empirical distribution over the samples in X₂ (t E [T+1]). According to Assumptions 5.1 and 5.2 well as the setting in Theorem 5.1 at least 1 8:
we know that the followings satisfied with probability
0.9 Ap, (0, ~
= 1.1A, Vo, E E0,
(32)
0.94 の²) 3 A (6. Φz) = (.
Notice that à and 6 are independent of the samples from the target task, so 2 N poiut ④ P. 3) is
sufficient for the second inequality above to hold with high probability. Using Lemma B.2 we know that (32 implies
0.9D,(0,0') = Dp. (e, Φ¹) 21.1,((000)) Vo, E (
(33)
0.9D 3 Drrr (2, 6²) 3 1.1,(0,0").
By the optimality of & and úi,... un for we know ((X)).n Pa(x)
P (oxx)(6(((())) + z1). Then we have the following chain of inequalities:
a² ((Fx(()) + log 1 8 ((xx)io 60 (X.)))))
(Claim B.1
Pa(x,) (0= (X,) + 21) - -x'06xxx (X.)wr |
Σ
Σ
|| 1 p (' (Xx))xt + Po(x))22 1
p.t ((xx) 80 (x.) /
*||Poxxx)=000
(cross term is 0)
Po(x. 13* x,)=o:l''
(ww)) (Xx) (1- x(xx) (((x))T(Xx.) (xxx)))((xx))) (X.)))
T
(wi)) Dp, (0.
21

---

Published as a conference paper at ICLR 2021
T (wm)) T Dp
2.9mm
Σ
(')
33
t=1
(Dp(0) 1/2
0.9m,
W*
F
(Do(a. 1/2 o2(W")
2 0.9n1
D2(0 (3) oZ(W")
0.9n Tr
0.9m1 Tr
Ppr+. (2, 63) oZ(W))
38
1.1
0.9n1
T_d
(X ol()))
1.
completing the proof.
Now can finish the proof of Theorem 5.1
Proof of Theorem
5.7
The excess risk is bounded as
ER(2, wT+1)
(10T110())- -0 (11 (xx)) 27
Bawp
2
1
10T+1
uUT+1
Ø*)
2
- 1
-Wi+1
W1
107+1 1
<
A Apr x³)
B2
-
1
(XT+1) uT+1 - 6² (XI+1) 1
112
1
Pat ) (XT+1) wi+1 + Pa(X)=1)2+t) 2r+1| /|
2
72
1
(1 x0 (TT4))T++
+ Po(Xmri) 1
xT+1
712
24
1
p1
d(xrar) df (T++)
2 +
( + log !)
(using x2 tail bound)
n2
n12
Taking expectation over 4T ~ U, we get
E Ew;_, ~y ER(Ø, wr++))
o²(k: + log 1)
p
0" (XT+1)
BBow |Bonn[Ww www] T]l
12 ((XT+1)
112
1
2
0² + (lk+log
P 8" (XI+1)
kmz
F
n2
1 o² (()=x( log
))
d² (k + log !
(Claim B.3
(W))
n2
0² (g)Fx(D))2 +og
o² + log 1
2A
(ox(W) F
n
112
finishing the proof.
22

---

Published as a conference paper at ICLR 2021
C PROOF OF THEOREM 6.1
C.I PROOF SKETCH OF THEOREM 6.1
Let R = || Recall B and W are derived from Eqn. that the constraint set {1/W|| s R/T, | I R} ensures WWW
and let é = BW. We first note S R and || S R at global minimum. On the other hand, our constraint for W, B is also expressive enough to attain any Ô that satisfies |6| I R. See reference e.g. Srebro and Shraibman (0055). Therefore at global minimum || - v R. | F S v and ||ô]|. S R.
12
For the ease of proof, we introduce the following auxiliary functions and parameters. Write
LWW) - 01/20" 1'2BW
L((W) =L)(W) + 1
W + arg min (
[2(w) - =1 |1/207+1 _1//2 Bw
[2 w arg min L2 (w) + w/2(
L.WW) 1 |x((-* - -Bw)|l
2m
(\(W) =L,( + >
W arg (W),
W
(2(w) 2nz || Xr+10 07+1 Xr+1 Bw
82 + arg min L2 (w)).
w<r
We define terms 6,c,1 and 6a,2 that will be used to bound intrinsic dimension concentration error in the input signal. Namely with high probability. || v 1/n, Σn ||20011 S G,,,1 Ge.11/|||= and similarly || Bull - / 1 na || S 6G.,2|| u||2- Additionally we use Eee, E {1,2] to bound
the estimation error (for fixed design) incurred when using noisy label yr-1 and Y.
The choice of Gee,s and Esc, are respectively justified Lemma C.5
Claim C.4
Lemma C.10 and
Claim C.II. along with some more detailed descriptions.
Proof of Theorem 6.1
Eg -u ER(B, (B, iTT+1)
Eg -u L2(1rT+1)
$ Eg 12((04+1) 20
(Claim C.I1
Eo -v iz (w02)
Eee 20 + 22
(Lemma C.4
$ Eg L2 (ww) + 20e + 2 20,27²
(Definition of (2
Eg L2(w3) + 20, 20 2 20,222
(Claim C.11
T (W7)) + 2 2, + 201
(Claim C.3
AR
+ 2 + 2
22
(Lemma
T
2 R + 2 R²
Ge,
2 E T + 21
(Choices of X)
T
Each step is with high probability 1 1 6/10 over the randomness of X' or XY41. Therefore overall
by union bound, with probability 1 1 6, by plugging in the values of Gic,i and Cee, we have:
oR Ō VT
Tr(E)
VIEI
R2 p
TH
Egray Nv ER(B wT+1) S
VTmi
V12
T
72
n22
Notice term ||]l/ is absorbed by ||||/nz n2 since assume n2-
23

---

Published as a conference paper at ICLR 2021
Claim C.1 (guarantee with source regularization).
| 6)1 + + S 3 ||+ S SAR,
T1
and || - 3R. [[ - for any A I (Z)l22
Here X the adjoint operator of such that x (Z) Ei=1 X,T Z
Proof.
With the optimality of Ô we have:
| -7) 21 + 111011 S 22
2 + X||
2m1
Let A = θ - -¹ Therefore
1 |
2n1
<X(10-||- - 1(]1.)) + _ (A,
m
=A||O || + - ||00|- |. || (2)11 + _ (2)I - A|
~|||0'||- + A/2 + 1/2/011. - -|/611-
2 n11
(Let >
=1xx
2 ~110011 ||+ - - ~.
3
1
Therefore 1 | + 1| & "110"'|,, and clearly both terms satisfy 1 || <
2n1
3A||e'||. and |+|| - e
Lemma C.2 (source task concentration), For fixed 5 > 0, let X = Eee,1 + + R. we have
L\(W>) SAR || SVR.
with probability 1 - 5/10.
Proof of Lemma C.2
|W
(((?))
2 12i))
(Definition of W/A)
2 1
(00 +)11 A
2 117
1
2 2
-|2((0' -1]1rr + O 1R) + A
2 1
1
2
Vm
2
|2 -BW + 1 11 + 0 R²)
2 [6AR + 16
(from Claim C.1
O(RR)
-(R)
Thus both results have been shown.
24

---

Published as a conference paper at ICLR 2021
Claim C.3 (Source and Target Connections).
Bg Lz(w2) -W)(
Proof of Claim C.3
3 (B LBTE EB + BB 10 =: -10
where Sx = BB EB
BB
Eer~v l22(unz)
Eg-ne 1 (5x-5x)00mm -x)0
1
T (Ix)Sx)0T+
T (WW
Lemma C.4 (Estimation Error for Target Task).
La ( L2(1)) R o (log 1/6)8/2 log(nz) =: 2
VTna
Proof of Lemma C.4
With the definition of vi we write the basic inequality:
Sr+1(Bit 0*) =T+I 13 S
11T+I+++ 0¹) - -2++1l12.
2m²
2nz
Therefore by rearranging get:
1
1
ST41B((t - w)ll <
-
(ro
w, B X X #T+1)
2n2
112
RR/T
|| X X 2r+1
112
R
oo
2/3 (1/8) log(n2)
(Claim C.6
VTna
= 0
C.2 TECHNICAL LEMMAS
This section includes the technical details for several parts: bounding the noise term from basic inequality; and intrinsic dimension concentration for both source and target tasks.
Lemma C.5 (Regularizer Estimation). For X Baad drawn from distribution p with covariance matrix E, and noise Z ~ NN0, o² In), with high probability 1 ô, we have
1 3/2
e6,1 =
x n
2 -
Vn"
log 3
log(T + +n) VT + Tr(E.).
We use matrix Bernstein with intrinsic dimension to bound À (See Theorem 7.3.1 Tropp et al. 2015)).
Proof.
Write
A = L LXTZ
== = DT X Z.eT =: ET S..
vB
T
Ex,[AAA = EEx
Σ
1
x
Ez
Ez|z12T|x
t=1
-T2
25

---

Published as a conference paper at ICLR 2021
T Σ
2x,2 [1T A] =
-e
xx [zg Xx 2,e,
n
t=1
R Ex,z 12 XX 2
TY)
Therefore the matrix variance statistic of the sum v(A) satisfies: v(A) o² max T+{)) Denote V = diag( Ir( and its intrinsic dimension dy = tr (V) Tr(V) o² n)Tr(E), and | 2 2 TrE).. Therefore dy T n.
Finally from Hanson- Wright inequality, the upper bound on each term is || < |X2, < T²Tr(E)) + - log + + V log with probability - 8. Thus using | S Tr(E),
Hanson-Wright
|| S so (1+ V log TTT(E)) + | log 8 =: L.
Then from intrinsic matrix bernstein (Theorem 7.3.1 in Tropp al. (2015)), with probability 1 have, || S Ol y /log for log(ds:) log $ I ())))))) which gives
1
||||| 2 / log g
T|| log(T + n) + log Tr(E)) log(T + +n) + log j I. log(T + n)
log 5
3/2
S
log(T + n) / Tr
Claim C.6 (target noise concentration). For fixed with probability 1 8/10, Eee
1 Vng
B X 7 < ( (1/8) log(na) TT( EB) s
Proof. The first inequality directly follows from Lemma C.5
Meanwhile (T(TTA)
(E., BBT) S [||||]] BB S || R. This finishes the proof.
Definition C.7. The sub- sabb-aassian norm of some vector y defined as:
ll == sup =68
1 x 1l
(34)
where S denotes the unit Euclidean sphere in R
Definition C.8. Let T C Ra be bounded set, and be standard normal random vector in IR., i.e., g ~ (0,, Then Then the quantities
(T)) = E sup x), and (TT) = E sup kg x))
(35)
wET
#eT
are called the Gaussian width Tf and the Gaussian complexity Tf respectively.
Theorem C.9 (Restated Matrix deviation inequality from Vershynin (017 Let be an m matrix whose rows a, are independent, isotropic and sub- gaussias random vectors in IR., Let C R be fixed bounded set. Then
Ssup TET
|||Ax||2- /m|lalal S CP²>(T),
(36)
where K max; || is the maximal sub- nub-gaussian norm of the rows of A. A high-probability
version states as follows. With probability 1 d.
sup || Vm||=llal= = Cp?h(1) + (log(2/0))(1T),
(37)
TeT
where the radius r(T) = suPxeT ||=|||-
26

---

Published as a conference paper at ICLR 2021
Lemma C.10 (intrinsic dimension concentration). Let X, Xt, E [T] be n d matrix whose rows are independent, isotropic and sub- gaussian random vectors in IR that satisfy Assumption 4.1 and the whitening distribution is with sub- gaussian norm Cip. where E[æ]] 0 and E|xx E. For fixed 6 > O, and any E IRd,, we have
2012 - A/
1x01|12 +
Cp² (VIX(E) - vlog(2/8)/=ii) |/0|22 Vn
vn
For any θ E RdxT, we further have
10
1
Σ
1x0.lă eic,1 1ie1,111l,,
(38)
Vni
where 6ie,1 ==
20p² (vTr(E) + v log (2 with probability 1 - 5.
vi
Proof. We use Theorem C.9
Let T = (o 1/22/22/22 S 1}. Let x E1/22, X Z3 Then
((T) v (T()),r(1))
|
We note with probability 1 6,
1
sup
|xel2
/|51/22/11 m012
||||
vn
1
sup
ZZolz 22 ||ا||
e
Vn
Cp2
(1(T) + vlog(2/8)((T)
Vn
Cp²
(VT+(E) + (lo((2/0)1()
Vn
Therefore vn |
Cp" v
(VTrE) + v /og /lo((2/)\12T]
V|[o|| = 1. Then by
homogeneity of v, for arbitrary u, we have
Cp² (vrr(E) v log 2/0) Σ
Xullz / S |111|2
Notice when n > (Tp'(TT(E) + | log1/)) 1/6), term I I 0.1VA. Therefore |||5//2011 Ko 0.1v/
Write θ = UD where D = diag(o 02, 02....,000 (T)
1
Cp² Vn
(vrr(z) Tog(2/0)111) | )
Σ
of
||51/2u,11
||
||ue||2
1=1
Cp²
0
|1,11/2
un
vn
(TT((E) + Tog(2/0)11E1)
2Cp²
=||5\/2011?
(
(T+(E)) + llg(2/0)) |ا||
Σ 0r(or1153//2u111))
Vā
2Cp²
2111//211/
(vr(E) (0
Σ
oe (max oz (maxor 22
vn
2Cp²
2|22//2012
(VTr(z) + Vlog(2/0)131)
/
Vā
27

---

Published as a conference paper at ICLR 2021
2Cp² vn
Therefore | - v V E xx,0 +
(Vrr(E) + log(2/8) ||||
term 11
Claim C.11. Let X be 122 x d matrix whose rows a are independent, isotropic and sub- sub-gaussian random vectors in R that satisfy Assumption 4.1 where E[x] 0 and E|xx E. Let Σg
B EB for some matrix B that satisfies |BB T. S R. Then for a fixed 8 > 0, and any v E Rd Co'
we have: || vll S x| 2ic2llul], where eic universal constant.
/ | (og)) and C is v
Proof.
This result directly uses Lemma C.10 when replacing X by X B. Notice now the subgaussian
norm for the whitening distribution for B remains the same as Cip. Therefore |> 121/2Bulla 1| s
X Bu l2 + S||lll2 s /oll2 < ymz X Sl Here S Cp² (12(V Tr(En)
vnz
log (2/6) EBll S C'p²/v R log Czc
D PROOF OF THEOREM 7.1
First, we describe a standard lifting of neural networks to infinite dimension linear regression Wei et al. (2019) Rosset et (2007); Bengio al. (2006). Define the infinite feature vector with coordinates ( = (b x)+ for every E S Let ag be signed measure on Sdo-1, The inner product notation denotes integration: a ((x) Jg4p ((x))d((b)) The tth output of the infinitewwidth neural network is far (x) = (ac, d(x)). Consider the least-squares problem
min pew.ne//spplllllee.. 2al2, SR
Σ (whe at ((x))) 1,8
(39)
2n
where ax(u) = [a1 .... ar (t)), and ||a||2.1 = Sgan-1 ||a(b) (ebbll2dd l2d(b). group regularizer on the vector measure a.
The regularizer corresponds
Proposition D.I. Let va be the value of Equation the value of Equation (39). Then
17
when the network has neurons and v be
ai = 22-
(40)
Proof. Let B, W be solutions Equation
17 Let B BD51 and Dạ be a diagonal matrix whose
entries are B5 = [ ejl12. The network fa.w (x) TDTDD(( x)4 and it satisfies
||0|| = ||
We first show that ?/ S 7d- Define ar( |6,
Wg We verify that
at ((x))= Σ (((b))(()) = Σ W1) = (B x)+++++ = SB... (x).
5=1
Due to the regularizer, and using the AM-GM inequality, at optimality 85 -|Weell2. Next, we verify that the two regularizer values are the same. Let w, be the j-th row vector of W. We have
||0||,,1 Σ
3
<
Σ
/2 + 12/2
28

---

Published as a conference paper at ICLR 2021
- |13 2 -
1 || - R.
Thus the network given by a, ((x) has the same network outputs and regularizer values. Thus Y" S Ta.
Finally, we show that na S rå- Let by for j E [d] be the support of the optimal measure (39
Define 3j = Vla(b,))l.. B BDs where B is matrix whose rows are by. and W such that
W5 (b,))) / [bbb))
We verify that the network values agree
e, fa,( e, W D3( x)4 (D(BBx)++
xb) =a Φ(x))
Finally by our construction By = ||Weyll. so the regularizer values agree. Thus Ydd = -/-
Finally, we note that the regularizer can be expressed in variational form a
min ||0||2,1 b.
| + [[]]]
where || = [ d()) and |
f wm (m.(b) (()). With these in place, note that with B constrained to be diagonal operator and
Equation (39) can be expressed as Equation Ta the lifted features (xxx)
Proof of Theorem 7.1
The global minimizer of Equation 39 with d = may have infinite support,
so the corresponding value may not be achieved by minimizing [77. However, Theorem 6.1 only
requires that the obtain learner network with regularized loss less than the regularized loss of the teacher network. Since the teacher network has d neurons, this value attainable by (17). Thus the finite-size network does not need to attain the global minimum of (39) for Claim C.1 apply.
Since Theorem 6.1 has no dependence (even in the logarithmic terms) on the input dimension of the data, it can be applied when the input features the dihinte-dimensionall feature vector d(æ). The only part of the proof of Theorem 6. speecficc to the nuclear norm is that the dual norm is the operator norm. In Lemma
C.5 we had an upper bound on ||| Z112- Since we use the || 11.1,,,1 norm, we must
upper bound +||
Z 2.00 the dual of the (2, norom. Note that || < ||A so the upper
bound in Lemma
C.5 still applies. Thus, Theorem 7.1 follows from Theorem 6.1
Proof of 21 The test error (20) is given by
EIER(JB, S 2
E
[X)) =||o0]
(41)
via the basic inequality (c.f. proof of Claim C.2 and
C.4
By the matrix Bernstein inequality (c.f.
Lemma C.5 or Wei et al. (2019)) E
(X)
21loo] S Vtr(E). When Bī+1; w/
22 P.
sampled from the same distribution as the source tasks, then [ 2| + | -11)1) 2 Thus we conclude
R
VT
tr(E)
(f S
122
'Informally a E PxT with potentially infinite, ||a||2,1 min din - 1|bb11
[
29


Reviews:
[{"review_id": "zEnHH1Csaqy", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This paper presents some new theoretical insights into a two-layer (linear or non-linear) network based meta-learning framework for dimension reduction and few-shot linear regression. In the considered problem setting, the hidden layer for feature extraction is assumed to be shared across the training and test tasks, and the output layer is optimized in a task-specific way with quadratic loss. For well-specified low-dimensional linear representation learning models, statistical analysis shows that when the tasks are sufficiently divergent, the excess risk of the target task estimator has a near-optimal rate of convergence, up to a near-optimal statistical error of meta-training. The corresponding results for well-specified high-dimensional linear representation and neural networks have also been derived under additional regularization conditions.\n\nStrong points:\n\n-S1. Theoretical understanding of meta-learning for feature extraction and few-shot linear regression is an interesting and timely topic in representation learning.\n\n-S2. The excess risk bounds look correct and can reasonable justify the benefit of multi-task feature extraction in terms of sample efficiency. \n\n-S3. The paper is well organized and neatly presented  \n\nWeak points:\n\n-W1. The entire analysis was made under a fundamental assumption that each training task should be globally minimized. From the perspective of optimization, such an assumption is fairly unrealistic in the sense that the linear/non-linear representation learning in the meta-training phase is non-convex and highly non-trivial for optimization. It is thus debatable whether excess risk, which is usually studied in convex learning theory,  should be used as a measurement of generalization performance for the considered representation learning problem. \n\n-W2. In Section 4, it is not very clear how to handle the identifiability issue in model (6), namely, $\\hat B$ and $\\hat W$ can be properly re-scaled and rotated without changing their product. The same concern can be raised for the underlying true model of data generalization in Equation (4) with linear feature map. The excess risk bounds in Theorem 4.1 and Theorem 5.1 seem to be invariant to such a scaling issue. However, the Assumptions 4.3 and 4.4 are clearly sensitive the scale of model. Is there any way to justify this kind of gap between assumption and result?\n\n-W3. Assumption 4.3 essentially requires that $T\\ge k$ because otherwise the smallest singular value will be zero. What will happen if $T<k$? I encourage the authors to provide some discussions/clarifications on this point. \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "JfLx28XK-RG", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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 \n\nThe paper describes excess risk bounds for ERM in the few-shot learning setting where one has access to $n_1$ samples from each of the $T$ source tasks and $n_2$ samples from the target class. Under the assumption that there exists a ground-truth representation map, shared across all tasks, and a ground-truth task-specific linear map, that maps from the representation space to output space, the authors derive bounds that make use of all $n_1T$ data samples from the source tasks to bound the excess risk of the ERM.  \n\nThe bounds that are derived are for the following three settings: 1) low dimensional linear representation, 2) general linear map with $\\ell$-2 norm-based capacity control for the representation, and 3) linear map with a Relu non-linearity based representation. The key innovation is the structure imparted onto the input distribution of the source and target tasks where the assumption is that the input distribution of *all* the tasks covers the target task. The assumptions get progressively stricter for each of the three cases where for the low dimensional linear case, the assumption is that covariance of the target tsk is dominated by the covariance of all the source tasks, for the high dimensional case, the mean covariance is shared across tasks and finally for the neural network cases where the tasks share the same input distribution. These assumptions allow the improvement of the bound in Maurer et al. 2016. \n\n\n## Strengths: \n\n1. Overall the paper is well written and motivated. The implication of the results are well discussed and makes for a good read. \n2. Under the assumptions on input distribution, results are an improvement over the iid task case and provides theoretical motivation for few-shot learning. \n3. Generalizes the Excess risk bound for the ERM in [1] for the low dimensional linear and the high dimensional linear setting. Extends the result to the ERM of 2 layer Relu network. \n\n## Weaknesses\n\n1. The bound is valid when one has access to oracle ERM. This is not the case for most non-convex optimization. Especially in the case of the neural network extension.\n2. As pointed out by the authors, many results are very similar to concurrent work of [1]\n3. The paper lacks discussion with some prior work  [2] where the authors obtained results for task averaged excess risk. The result in this work is not for new task but since the authors make strong assumptions on input data distribution and task model the result seems like a natural extension of the results in [1].\n\n## Discussion and concerns\n\nBoth Theorem 5.1 and 6.1 make the coherence assumption on the target task model. I understand that it allows us to get a bound in terms of $\\| \\Theta^*\\|$ but the implications of this assumption is not well discussed in the paper. This looks like assumption 4.3 for Theorem 4.1. Any understanding of how the results would change if we don’t make the assumption 4.3 and the coherence assumptions?\n\n\n__EDIT: Added references__\n[1] Nilesh Tripuraneni, Chi Jin, and Michael I Jordan. Provable meta-learning of linear representations. arXiv preprint arXiv:2002.11684, 2020\n[2] Pontil, M., & Maurer, A. (2013, June). Excess risk bounds for multitask learning with trace norm regularization. In Conference on Learning Theory (pp. 55-76).", "extra_scores": {}, "extra_text": {}}, {"review_id": "7LVY8j3_7g", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "#######################################################################\n\nSummary:\nThis paper studies the benefit of few-shot learning for sample complexity, when all the tasks (both source and target task) share the same underline representation. Under some assumptions on the data and tasks, this paper improves the previous result based on the iid task assumption and shows that they can utilize all source data. The considered models include linear model (both low dimensional and high dimensional representation) and two-layer neural network.\n\n#######################################################################\n\nPros:\n- Understanding when and why few-shot learning is useful is an important and interesting problem. This work provides some insights into this problem and proves that in some setting few-shot learning is indeed helpful for the sample complexity.\n- By introducing some new assumptions on data and tasks which is different from previous the iid assumption on the tasks, the paper shows that one can use all source data.\n- Several models are considered in the paper, including linear model and two-layer neural network model. \n- The results are mainly focused on the statistical analysis, that is the property of minimizer. The algorithms to achieve such minimizer are also discussed, though for neural net, it may need exponential width.\n- The paper is easy to follow and clearly discusses the meaning of assumptions.\n\n##################################################################\n\nCons/Questions:\n- I was wondering if author(s) could discuss [1] in the related work, which seems to focus on the similar problem.\n- In Section 4 (low dimensional linear representation), a deterministic target risk is discussed in Remark 4.1. That is, the risk for any fixed target task instead of the average of all target task. I was wondering if such result could also hold in the setting of later sections, i.e., high-dimensional linear representation and two-layer neural network.\n\n[1] On the theory of transfer learning: The importance of task diversity. arXiv preprint arXiv:2006.11650\n\n####################################################################\n\nMinor:\n- In Theorem 4.1, \\kappa is defined, but does not seem to be used in the theorem statement.\n\n#####################################################################\n\nThanks for the  response from authors! I will keep my score.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "1j4d6sGOGb", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper aims at justifying the success of few shot learning methods that work based on finding a shared representation among a number of tasks. A serious theoretical challenge is that, even if we assume such a representation exists (and belongs to a predefined class of functions with controlled capacity), we would still need to assume something that connects the source tasks with the target task. Previous work has considered \"i.i.d. tasks\", however, the obtained bounds were not natural in the sense that we don't have the usual decrease in the error as we increase the size of the training set of the source tasks. Under a different set of assumptions, the authors show that, in a sense, one can \"fully\" exploit the training data from the source tasks. \n\nMultiple settings are considered, including linear least squares with a low dimensional shared representation, generalization to non-linear representation, high-dimensional (low norm) representation, and neural networks. The obtained results are interesting, and some intuitions are provided about the assumptions and the results. These discussions are sometimes short/dense, making it hard for the reader to follow the details. This is perhaps due to the page-limit.\n\nPerhaps a basic intuition for the first result (linear case with a low dimensional shared representation) is that if the source tasks are somewhat \"uniform\" in the low dimensional representation and the number of tasks is large enough, then in a sense they will \"cover\" the low dimensional space, and the learned representation will be in a sense accurate in all directions; so if the target tasks is also selected somewhat uniformly, then the learned representation will work well. Is this correct? In any case, I suggest that the authors add more of these intuitions to the paper, especially for the other problems including the neural net and the high-dimensional linear representation.\n\nIt will be interesting to do some experiments on a real world data set and see the extent to which the assumptions are realistic. It will help to see the actual value of the upper bounds on a synthetic data set that adheres the assumptions. \n\n\n  ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of learning a new task with few examples by using related tasks which can exploit shared representations for which more data is available. The paper proves a number of interesting (primarily theoretical) results.
Decision: Accept (Poster)