Few-Shot Learning via Learning the Representation, Provably

Introduction

A popular scheme for few-shot learning, i.e., learning in a data-scarce environment, is representation learning, where one first learns a feature extractor, or representation, e.g., the last layer of a convolutional neural network, from different but related source tasks, and then uses a simple predictor (usually a linear function) on top of this representation in the target task. The hope is that the learned representation captures the common structure across tasks, which makes a linear predictor sufficient for the target task. If the learned representation is good enough, it is possible that a few samples are sufficient for learning the target task, which can be much smaller than the number of samples required to learn the target task from scratch.

Unfortunately, as pointed out by Maurer et al. (2016), there exists an example that satisfies the i.i.d. task assumption for which $\Omega(\frac{1}{\sqrt{T}})$ is unavoidable (or $\Omega(\frac{1}{T})$ 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, a 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_{1}T$ data from source tasks. We replace the i.i.d. assumption over tasks with natural structural conditions on the input 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 to the desirable guarantees.

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 a good representation. Our result on high-dimensional representations and overparametrized neural networks shows that the capacity control for representation learning does not have to be through explicit low dimensionality.

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. We next present our analysis in four different settings:

Section 4 presents the results for low-dimensional linear representation learning.

Section 5 presents the results for low-dimensional nonlinear representation classes, including neural networks.

Section 6 presents the results for high-dimensional linear representation learning.

Section 7 presents the results for representation learning in overparametrized neural networks.

Finally, we conclude in Section 8 and leave most of the proofs to appendices.

Related Work

The idea of multitask representation learning at least dates back to Caruana (1997), Thrun and Pratt (1998), Baxter (2000). Empirically, representation learning has shown its great power in various domains; see Bengio et al. (2013) for a survey. In particular, representation learning is widely adopted for few-shot learning tasks (Sun et al., 2017, Goyal et 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 a useful representation. The scheme we analyze in this paper is closely related to Lee et al. (2019), Bertinetto et al. (2018) for meta-learning.

The concurrent work of Tripuraneni et al. (2020a) 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 a special case of our result. Furthermore, we also provide results for high-dimensional linear representations, general non-linear representations, and overparametrized neural networks. Tripuraneni et al. (2020a) also give a computationally efficient algorithm for standard Gaussian inputs and a lower bound for subspace recovery in the low-dimensional linear setting. Subsequent work of Tripuraneni et al. (2020b) generalizes this work from linear task-specific layers $w_{t}$ to nonlinear task specific layers and bounded loss functions via proposing a new diversity assumption.

Another recent line of theoretical work analyzed gradient-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 et al., 2016, Denevi et al., 2018).

Notation and Setup

We use the standard $O(\cdot)$, $\Omega(\cdot)$ and $\Theta(\cdot)$ notation to hide universal constant factors. We also use $a\lesssim b$ or $b\gtrsim a$ to indicate $a=O(b)$, and use $a\gg b$ or $b\ll a$ to mean that $a\geq C\cdot b$ for a sufficiently large universal constant $C>0$.

Let $\hat{{\bm{w}}}_{T+1}$ be the returned solution. We are interested in whether our learned predictor ${\bm{x}}\mapsto\langle\hat{{\bm{w}}}_{T+1},{\hat{\phi}}({\bm{x}})\rangle$ works well on average for the target task, i.e., we want the population loss

to be small. In particular, we are interested in the few-shot learning setting, where the number of samples $n_{2}$ from the target task is small – much smaller than the number of samples required for learning the target task from scratch.

where ${\bm{x}}$ and $z$ are independent. Our goal is to bound the excess risk of our learned model on the target task, i.e., how much our learned model $({\hat{\phi}},\hat{{\bm{w}}}_{T+1})$ performs worse than the optimal model $(\phi^{*},{\bm{w}}_{T+1}^{*})$ on the target task:

Low-Dimensional Linear Representations

With this notation, (6) can be rewritten as

With the learned representation $\hat{B}$ from (7), for the target task, we further find a linear function on top of the representation:

There exists $c>0$ such that $\Sigma_{t}\succeq c\cdot\Sigma_{T+1}$ for all $t\in[T]$.Note that Assumption 4.2 is a significant generalization of the identically distributed isotropic assumption used in concurrent work Tripuraneni et al. (2020a): they require $\Sigma_{1}=\Sigma_{2}=\cdots=\Sigma_{T+1}=I$.

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 or boundedness conditions if we adopt different tail bounds in the analysis.

Assumption 4.2 says that every direction spanned by $\Sigma_{T+1}$ should also be spanned by $\Sigma_{t}$ ($t\in[T]$), and the parameter $c$ quantifies how “easy” it is for $\Sigma_{t}$ to cover $\Sigma_{T+1}$. Intuitively, the larger $c$ is, the easier it is to cover the target domain using source domains, and we will indeed see that the risk will be proportional to $\frac{1}{c}$. We remark that we do not necessarily need $\Sigma_{t}\succeq c\cdot\Sigma_{T+1}$ for all $t\in[T]$; as long as this holds for a constant fraction of $t$’s, our result is valid.

We also make the following assumption that characterizes the diversity of the source tasks.

Finally, we make the following assumption on the distribution of the target task.

Assumption 4.4 can be removed at the cost of a slightly worse risk bound. See Remark 4.2. Our main result in this section is the following theorem.

Fix a failure probability $\delta\in(0,1)$. Under Assumptions 4.1, 4.2, 4.3 and 4.4, we further assume $2k\leq\min\{d,T\}$ and that the sample sizes in source and target tasks satisfy $n_{1}\gg\rho^{4}(d+\log\frac{T}{\delta})$, $n_{2}\gg\rho^{4}(k+\log\frac{1}{\delta})$, and $cn_{1}\geq n_{2}$. Define $\kappa=\frac{\max_{t\in[T]}\lambda_{\max}(\Sigma_{t})}{\min_{t\in[T]}\lambda_{\min}(\Sigma_{t})}$. Then with probability at least $1-\delta$ over the samples, the expected excess risk of the learned predictor ${\bm{x}}\mapsto\hat{{\bm{w}}}_{T+1}^{\top}\hat{B}{\bm{x}}$ on the target task satisfies

The proof of Theorem 4.1 is in Appendix A. Theorem 4.1 shows that it is possible to learn the target task using only $O(k)$ samples via learning a good representation from the source tasks, which is better than the baseline $O(d)$ sample complexity for linear regression, thus demonstrating the benefit of representation learning. It also shows that all $n_{1}T$ samples from source tasks can be pooled together, bypassing the $\Omega(\frac{1}{T})$ barrier under the i.i.d. tasks assumption.

We note that all our results apply to multi-class problems by removing $T$, with similar class-diversity assumption. Specifically, when source and target have $n_{1}$ and $n_{2}$ multi-class labeled samples (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 $\sigma^{2}O\left(\frac{kd\log(\kappa n_{1})}{cn_{1}}+\frac{k+\log 1/\delta}{n_{2}}\right)$ (see e.g. Lee et al. (2020)). Notice the result is independent of the number of classes.

We can drop Assumption 4.4 and easily obtain the following excess risk bound for any deterministic ${\bm{w}}_{T+1}^{*}$ by slightly modifying the proof of Theorem 4.1:

which is only at most $k$ times larger than the bound in (9).

General Low-Dimensional Representations

Now we return to the general case described in Section 3 where we allow a general representation function class $\Phi$. We still assume that the representation is of low dimension $k$. The goal is to obtain a result similar to Theorem 4.1. In this section we assume that inputs from all the tasks follow the same distribution, i.e., $p_{1}=\cdots=p_{T+1}=p$, but each task $t$ still has its own specialization function ${\bm{w}}_{t}^{*}$ (c.f. (4)). We remark that despite this restriction, our result in this section still applies to many interesting and nontrivial scenarios – consider the case where the inputs are all images from ImageNet and each task asks whether the image is from a specific class.

To characterize the complexity of the representation function class $\Phi$, we need the standard definition of Gaussian width.

We will measure the complexity of $\Phi$ using the Gaussian width of the following set that depends on the input data $\mathcal{X}$:

It is easy to verify $\Lambda_{q}(\phi,\phi^{\prime})\succeq 0$ for any $\phi,\phi^{\prime}$ and $q$.See the proof of Lemma B.1.

We make the following assumptions on the input distribution $p$, which ensure concentration properties of the representation covariances.

where $\hat{p}$ is the empirical distribution over the $n$ samples.

where $\hat{p}$ is the empirical distribution over the $n$ samples.

Our main theorem in this section is the following:

Theorem 5.1 is very similar to Theorem 4.1 in terms of the result and the assumptions made. In the bound (11), the complexity of $\Phi$ is captured by the Gaussian width of the data-dependent set $\mathcal{F}_{\mathcal{X}}(\Phi)$ defined in (10). 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, we can apply concentration bounds to get rid of the data dependency, such as our result for linear representations (Theorem 4.1).

Our assumptions on the linear specification functions ${\bm{w}}_{t}^{*}$’s are the same as in Theorem 4.1. The probabilistic assumption on ${\bm{w}}_{T+1}^{*}$ can also be removed at the cost of an additional factor of $k$ in the bound – see Remark 4.2.

The proof of Theorem 5.1 is given in Appendix B. Here we prove an important intermediate result on the in-sample risk, which explains how the Gaussian width of $\mathcal{F}_{\mathcal{X}}(\Phi)$ arises.

Let $\hat{\phi}$ and $\hat{{\bm{w}}}_{1},\ldots,\hat{{\bm{w}}}_{T}$ be the optimal solution to (2). Then with probability at least $1-\delta$ we have

By the optimality of $\hat{\phi}$ and $\hat{{\bm{w}}}_{1},\ldots,\hat{{\bm{w}}}_{T}$ for (2), we know

Plugging in ${\bm{y}}_{t}=\phi^{*}(X_{t}){\bm{w}}^{*}_{t}+{\bm{z}}_{t}$ (${\bm{z}}_{t}\sim\mathcal{N}(0,I)$ is independent of $X_{t}$), we get

Then the proof is completed using (12). ∎

High-Dimensional Linear Representations

In this section, we consider the case where the representation is a general linear map without an 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 in many applications the representation dimension is not restricted.

In this section we additionally assume that all tasks have the same input covariance:

The input distributions in all tasks satisfy $\Sigma_{1}=\cdots=\Sigma_{T+1}=\Sigma$.

Note that each task $t$ still has its own specialization function ${\bm{w}}_{t}^{*}$ (c.f. (4)). We remark that there are many interesting and nontrivial scenarios under Assumption 6.1 – for example, consider the case where the inputs in each task are all images from ImageNet and each task asks whether the image is from a specific class.

Since we do not have a dimensionality constraint, we modify (7) by adding norm constraints:

For the target task, we also modify (8) by adding a norm constraint:

We will specify the choices of regularization, i.e., $\lambda$ and $r$ in Theorem 6.1.

Fix a failure probability $\delta\in(0,1)$. Under Assumptions 4.1 and 6.1, we further assume $n_{1}\geq n_{2}$, $R=\|\Theta\|_{*}.$ Let $r=2\sqrt{R/T}$, $\bar{R}=R/\sqrt{T}$ and proper $\lambda$ specified in Lemma C.2. Let the target task model ${\bm{\theta}}_{T+1}^{*}$ be coherent with the source task models $\Theta^{*}$ in the sense that ${\bm{\theta}}_{T+1}^{*}\sim\nu=\mathcal{N}(\bm{0},\Theta^{*}(\Theta^{*})^{\top}/T)$. Then with probability at least $1-\delta$ over the samples, the expected excess risk of the learned predictor ${\bm{x}}\mapsto\hat{{\bm{w}}}_{T+1}^{\top}\hat{B}^{\top}{\bm{x}}$ on the target task satisfies:

The proof of Theorem 6.1 is given in Appendix C. Note that $\|\Theta^{*}\|_{F}=\sqrt{T}$ when each ${\bm{\theta}}^{\ast}_{t}$ is of unit norm. Thus $\bar{R}=\left\|\Theta^{*}\right\|_{*}/\sqrt{T}$ should generally be regarded as $O(1)$ for a well-behaved $\Theta^{*}$ that is nearly low-dimensional. In this regime, Theorem 6.1 indicates that we are able to exploit all $n_{1}T$ samples from the source tasks, similar to 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 to the target task data:

Although the optimization problem (13) is non-convex, its structure allows us 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 (13) (Ge et al., 2015, Lee et al., 2016, Jin et al., 2017).

Neural Networks

In this section, we show that we can provably learn good representations in a neural network.

On the target task, we simply re-train the output layer while fixing the hidden layer weights:

Fix a failure probability $\delta\in(0,1)$. Under Assumptions 4.1, 7.1 and 7.2, let $n_{1}\geq n_{2}$, $\bar{R}=(\frac{1}{2}\|B^{*}\|_{F}^{2}+\frac{1}{2}\|W^{*}\|_{F}^{2})/\sqrt{T}$. Let the target task model $f_{\alpha_{T+1}}=\langle\alpha_{T+1},\phi({\bm{x}})\rangle$ be coherent with the source task models in the sense that $\alpha_{T+1}^{*}\sim\nu$. Set $r^{2}=(\|B^{*}\|_{F}^{2}+\|W^{*}\|_{F}^{2})/T$.Then with probability at least $1-\delta$ over the samples, the expected excess risk of the learned predictor ${\bm{x}}\mapsto\hat{{\bm{w}}}_{T+1}^{\top}(\hat{B}^{\top}{\bm{x}})_{+}$ on the target task satisfies:

To highlight the advantage of representation learning, we compare to training a neural network with weight decay directly on the target task:

The error of the baseline method in fixed-design is

We see that Equation (20) is always smaller than Equation (22) since $n_{1}T\geq n_{2}$. See Appendix D for the proof of Theorem 7.1 and the calculation of (22).

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 is not necessary, and norm-based capacity control also forces the classifier to learn good representations. Further questions include whether this is a general phenomenon in all deep learning models, whether other capacity control can be applied, and how to optimize to attain good representations.

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 W911NF-11-1-0303, the Sloan Research Fellowship, and NSF CCF 2002272. WH is supported by NSF, 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 QL were participants.

References

Appendix A Proof of Theorem 4.1

We first prove several claims and then combine them to finish the proof of Theorem 4.1. We will use technical lemmas proved in Section A.1.

Suppose $n_{1}\gg\rho^{4}(d+\log(T/\delta))$ for $\delta\in(0,1)$. Then with probability at least $1-\frac{\delta}{10}$ over the inputs $X_{1},\ldots,X_{T}$ in the source tasks, we have

The proof is finished by taking a union bound over all $t\in[T]$. ∎

Since $\frac{1}{n_{2}}VDU^{\top}\bar{X}_{T+1}^{\top}\bar{X}_{T+1}UDV^{\top}=\frac{1}{n_{2}}B^{\top}\Sigma_{T+1}^{1/2}\bar{X}_{T+1}^{\top}\bar{X}_{T+1}\Sigma_{T+1}^{1/2}B=\frac{1}{n_{2}}B^{\top}X_{T+1}^{\top}X_{T+1}B$ and $VDDV^{\top}=VDU^{\top}UDV^{\top}=B^{\top}\Sigma_{T+1}B$, the above inequality becomes

Under the setting of Theorem 4.1, with probability at least $1-\frac{\delta}{5}$ we have

We assume that (23) is true, which happens with probability at least $1-\frac{\delta}{10}$ according to Claim A.1.

Let $\hat{\Theta}=\hat{B}\hat{W}$ and $\Theta^{*}=B^{*}W^{*}$. From the optimality of $\hat{B}$ and $\hat{W}$ for (7) we have $\|Y-\mathcal{X}(\hat{\Theta})\|_{F}^{2}\leq\|Y-\mathcal{X}(\Theta^{*})\|_{F}^{2}$. Plugging in $Y=\mathcal{X}(\Theta^{*})+Z$, this becomes

Next we give a high-probability upper bound on $\sum_{t=1}^{T}\left\|U_{t}^{\top}{\bm{z}}_{t}\right\|^{2}$ using the randomness in $Z$. Since $U_{t}$’s depend on $V$ which depends on $Z$, we will need an $\epsilon$-net argument to cover all possible $V\in\mathcal{O}_{d,2k}$. First, for any fixed $\bar{V}\in\mathcal{O}_{d,2k}$, we let $X_{t}\bar{V}=\bar{U}_{t}\bar{Q}_{t}$ where $\bar{U}_{t}\in\mathcal{O}_{n,2k}$. The $\bar{U}_{t}$’s defined in this way are independent of $Z$. Since $Z$ has i.i.d. $\mathcal{N}(0,\sigma^{2})$ entries, we know that $\sigma^{-2}\sum_{t=1}^{T}\left\|\bar{U}_{t}^{\top}{\bm{z}}_{t}\right\|^{2}$ is distributed as $\chi^{2}(2kT)$. Using the standard tail bound for $\chi^{2}$ random variables, we know that with probability at least $1-\delta^{\prime}$ over $Z$,

Therefore, using the same argument in (A) we know that with probability at least $1-\delta^{\prime}$,

Now, from Lemma A.5 we know that there exists an $\epsilon$-net $\mathcal{N}$ of $\mathcal{O}_{d,2k}$ in Frobenius norm such that $\mathcal{N}\subset\mathcal{O}_{d,2k}$ and $|\mathcal{N}|\leq(\frac{6\sqrt{2k}}{\epsilon})^{2kd}$. Applying a union bound over $\mathcal{N}$, we know that with probability at least $1-\delta^{\prime}|\mathcal{N}|$,

Choosing $\delta^{\prime}=\frac{\delta}{20(\frac{6\sqrt{2k}}{\epsilon})^{2kd}}$, we know that (28) holds with probability at least $1-\frac{\delta}{20}$.

We will use (23), (26) and (28) to complete the proof of the claim. This is done in the following steps:

Since $\sigma^{-2}\left\|Z\right\|_{F}^{2}\sim\chi^{2}(n_{1}T)$, we know that with probability at least $1-\frac{\delta}{20}$,

Upper bounding $\left\|\Delta\right\|_{F}$.

From (26) we have $\left\|\mathcal{X}(\Delta)\right\|_{F}^{2}\leq 2\left\|Z\right\|_{F}\left\|\mathcal{X}(\Delta)\right\|_{F}$, which implies $\left\|\mathcal{X}(\Delta)\right\|_{F}\leq 2\left\|Z\right\|_{F}\lesssim\sigma\sqrt{n_{1}T+\log(1/\delta)}$. On the other hand, letting the $t$-th column of $\Delta$ be ${\bm{\delta}}_{t}$, we have

where ${\underline{\lambda}}=\min_{t\in[T]}\lambda_{\min}(\Sigma_{t})$. Hence we obtain

Applying the $\epsilon$-net $\mathcal{N}$.

Let $\bar{V}\in\mathcal{N}$ such that $\left\|V-\bar{V}\right\|_{F}\leq\epsilon$. Then we have

We have the following chain of inequalities:

Finally, we let $\epsilon=\frac{k}{\sqrt{\kappa}n_{1}}$, and recall $\delta^{\prime}=\frac{\delta}{20(\frac{6\sqrt{2k}}{\epsilon})^{2kd}}$. Then the above inequality implies

The high-probability events we have used in the proof are (23), (28) and (29). By a union bound, the failure probability is at most $\frac{\delta}{10}+\frac{\delta}{20}+\frac{\delta}{20}=\frac{\delta}{5}$. Therefore the proof is completed. ∎

Under the setting of Theorem 4.1, with probability at least $1-\frac{2\delta}{5}$, we have

From the optimality of $\hat{B}$ and $\hat{W}$ in (6) we know $X_{t}\hat{B}\hat{{\bm{w}}}_{t}=P_{X_{t}\hat{B}}{\bm{y}}_{t}=P_{X_{t}\hat{B}}(X_{t}B^{*}{\bm{w}}_{t}^{*}+{\bm{z}}_{t})$ for each $t\in[T]$. Then we have

Next, we write $\hat{B}=[\hat{B},B^{*}]\begin{bmatrix}I\\ 0\end{bmatrix}=:BA$ and $B^{*}=[\hat{B},B^{*}]\begin{bmatrix}0\\ I\end{bmatrix}=:BC$. Recall that we have $\frac{1}{n_{2}}B^{\top}X_{T+1}^{\top}X_{T+1}B\preceq 1.1B^{\top}\Sigma_{T+1}B$ from Claim A.2. Then using Lemma A.7 we can obtain

For the target task, the excess risk of our learned linear predictor ${\bm{x}}\mapsto(\hat{B}\hat{{\bm{w}}}_{T+1})^{\top}{\bm{x}}$ is

Applying Claim A.2 with $B=[\hat{B},B^{*}]$, we have

which implies $0.9{\bm{v}}^{\top}B^{\top}\Sigma_{T+1}B{\bm{v}}\leq\frac{1}{n_{2}}{\bm{v}}B^{\top}X_{T+1}^{\top}X_{T+1}B{\bm{v}}$ for ${\bm{v}}=\begin{bmatrix}\hat{{\bm{w}}}_{T+1}\\ {\bm{w}}_{T+1}^{*}\end{bmatrix}$. This becomes

From the optimality of $\hat{{\bm{w}}}_{T+1}$ in (8) we know $X_{T+1}\hat{B}\hat{{\bm{w}}}_{T+1}=P_{X_{T+1}\hat{B}}{\bm{y}}_{T+1}=P_{X_{T+1}\hat{B}}(X_{T+1}B^{*}{\bm{w}}_{T+1}^{*}+{\bm{z}}_{T+1})$. It follows that

For the second term above, notice that $\frac{1}{\sigma^{2}}\left\|P_{X_{T+1}\hat{B}}{\bm{z}}_{T+1}\right\|_{F}^{2}\sim\chi^{2}(k)$, and thus with probability at least $1-\frac{\delta}{5}$ we have $\frac{1}{\sigma^{2}}\left\|P_{X_{T+1}\hat{B}}{\bm{z}}_{T+1}\right\|_{F}^{2}\lesssim k+\log\frac{1}{\delta}$. Therefore we obtain the final bound

where the last inequality is due to $cn_{1}\geq n_{2}$. ∎

Finally, we need to transform $\mathcal{N}^{\prime}$ into an $\epsilon$-net $\mathcal{N}$ that is a subset of $\mathcal{O}_{d_{1},d_{2}}$. This can be done by projecting each point in $\mathcal{N}^{\prime}$ onto $\mathcal{O}_{d_{1},d_{2}}$. Namely, for each $\bar{V}\in\mathcal{N}^{\prime}$, let $\mathcal{P}(\bar{V})$ be its closest point in $\mathcal{O}_{d_{1},d_{2}}$ (in Frobenium norm); then define $\mathcal{N}=\{\mathcal{P}(\bar{V})\mid\bar{V}\in\mathcal{N}^{\prime}\}$. Then we have $|\mathcal{N}|\leq|\mathcal{N}^{\prime}|\leq(\frac{6\sqrt{d_{2}}}{\epsilon})^{d_{1}d_{2}}$ and $\mathcal{N}$ is an $\epsilon$-net of $\mathcal{O}_{d_{1},d_{2}}$, because for any $V\in\mathcal{O}_{d_{1},d_{2}}$, there exists $\bar{V}\in\mathcal{N}^{\prime}$ such that $\left\|V-\bar{V}\right\|_{F}\leq\frac{\epsilon}{2}$, which implies $\mathcal{P}(\bar{V})\in\mathcal{N}$ and $\left\|V-\mathcal{P}(\bar{V})\right\|_{F}\leq\left\|V-\bar{V}\right\|_{F}+\left\|\bar{V}-\mathcal{P}(\bar{V})\right\|_{F}\leq\left\|V-\bar{V}\right\|_{F}+\left\|\bar{V}-V\right\|_{F}=2\left\|V-\bar{V}\right\|_{F}\leq\epsilon$. ∎

Let $A=\frac{1}{n}\sum_{i=1}^{n}{\bm{a}}_{i}{\bm{a}}_{i}^{\top}-I$. Then it suffices to show $\left\|A\right\|\leq 0.1$ with probability at least $1-\delta$.

Next, take a $\frac{1}{5}$-net $\mathcal{N}\subset\mathcal{S}^{d-1}$ of $\mathcal{S}^{d-1}$ with size $|\mathcal{N}|\leq e^{O(d)}$. By a union bound over all ${\bm{v}}\in\mathcal{N}$, we have

Plugging in $\epsilon=\frac{1}{20}$ and noticing $\rho>1$, the above inequality becomes

where the last inequality is due to $n\gg\rho^{4}\left(d+\log(1/\delta)\right)$.

Therefore, with probability at least $1-\delta$ we have $\max_{{\bm{v}}\in\mathcal{N}}|{\bm{v}}^{\top}A{\bm{v}}|\leq\frac{1}{20}$. Suppose this indeed happens. Next, for any ${\bm{u}}\in\mathcal{S}^{d-1}$, there exists ${\bm{u}}^{\prime}\in\mathcal{N}$ such that $\left\|{\bm{u}}-{\bm{u}}^{\prime}\right\|\leq\frac{1}{5}$. Then we have

Taking a supreme over $u\in\mathcal{S}^{d-1}$, we obtain $\left\|A\right\|\leq\frac{1}{20}+\frac{1}{2}\left\|A\right\|$, i.e., $\left\|A\right\|\leq\frac{1}{10}$. ∎

If two matrices $A_{1}$ and $A_{2}$ (with the same number of columns) satisfy $A_{1}^{\top}A_{1}\succeq A_{2}^{\top}A_{2}$, then for any matrix $B$ (of compatible dimensions), we have

As a consequence, for any matrices $B$ and $B^{\prime}$ (of compatible dimensions), we have

For the first part of the lemma, it suffices to show the following for any vector ${\bm{v}}$:

Let ${\bm{w}}^{*}\in\operatorname*{arg\,min}_{{\bm{w}}}\|A_{1}B{\bm{w}}-A_{1}{\bm{v}}\|_{2}^{2}$. Then we have

For the second part, from $A_{1}^{\top}P^{\perp}_{A_{1}B}A_{1}\succeq A_{2}^{\top}P^{\perp}_{A_{2}B}A_{2}$ we know

Appendix B Proof of Theorem 5.1

The proof is conditioned on several high-probability events, each happening with probability at least $1-\Omega(\delta)$. By a union bound at the end, the final success probability is also at least $1-\Omega(\delta)$. We can always rescale $\delta$ by a constant factor such that the final probability is at least $1-\delta$. Therefore, we will not carefully track the constants before $\delta$ in the proof. All the $\delta$’s should be understood as $\Omega(\delta)$.

We use the following notion of representation divergence.

It is easy to verify $D_{q}(\phi,\phi^{\prime})\succeq 0$, $D_{q}(\phi,\phi)=0$ for any $\phi,\phi^{\prime}$ and $q$. See Lemma B.1’s proof.

The next lemma shows a relation between (symmetric) covariance and divergence.

Similarly, letting $g({\bm{w}})=[{\bm{w}}^{\top},-{\bm{v}}^{\top}]\Lambda_{q^{\prime}}(\phi,\phi^{\prime})\begin{bmatrix}{\bm{w}}\\ -{\bm{v}}\end{bmatrix}$, we have

Under the setting of Theorem 5.1, with probability at least $1-\delta$ we have

We continue to use the notation from Claim 5.3 and its proof.

Let $\hat{p}_{t}$ be the empirical distribution over the samples in $X_{t}$ ($t\in[T+1]$). According to Assumptions 5.1 and 5.2 as well as the setting in Theorem 5.1, we know that the followings are satisfied with probability at least $1-\delta$:

By the optimality of $\hat{\phi}$ and $\hat{{\bm{w}}}_{1},\ldots,\hat{{\bm{w}}}_{T}$ for (2), we know $\hat{\phi}(X_{t})\hat{{\bm{w}}}_{t}=P_{\hat{\phi}(X_{t})}{\bm{y}}_{t}=P_{\hat{\phi}(X_{t})}(\phi^{*}(X_{t}){\bm{w}}^{*}_{t}+{\bm{z}}_{t})$. Then we have the following chain of inequalities:

Now we can finish the proof of Theorem 5.1.

Taking expectation over ${\bm{w}}_{T+1}^{*}\sim\nu$, we get

Appendix C Proof of Theorem 6.1

Let $R=\|\Theta^{*}\|_{*}$. Recall $\hat{B}$ and $\hat{W}$ are derived from Eqn. (13) and let $\hat{\Theta}:=\hat{B}\hat{W}$. We first note that the constraint set $\{\|{\bm{w}}\|_{i}^{2}\leq R/T,\|B\|_{F}^{2}\leq R\}$ ensures $\|W\|_{F}^{2}\leq R$ and $\|WB\|_{*}\leq R$ at global minimum. On the other hand, our constraint for $W,B$ is also expressive enough to attain any $\hat{\Theta}$ that satisfies $\|\hat{\Theta}\|_{*}\leq R$. See reference e.g. Srebro and Shraibman (2005). Therefore at global minimum $\|\hat{W}\|_{F}\leq\sqrt{R},\|\hat{B}\|_{F}\leq\sqrt{R}$ and $\|\hat{\Theta}\|_{*}\leq R$.

For the ease of proof, we introduce the following auxiliary functions and parameters. Write

We define terms $\epsilon_{ic,1}$ and $\epsilon_{ic,2}$ that will be used to bound intrinsic dimension concentration error in the input signal. Namely with high probability, $\|\Sigma^{1/2}\Theta\|-\sqrt{1/n_{1}\sum_{t=1}^{T}\|X_{t}\theta_{t}\|^{2}}\leq\epsilon_{ic,1}\|\Theta\|_{*}$, and similarly $\|\Sigma^{1/2}\hat{B}{\bm{v}}\|-\sqrt{\frac{1}{n_{2}}\|X\hat{B}{\bm{v}}\|^{2}}\leq\epsilon_{ic,2}\|v\|_{2}$. Additionally we use $\epsilon_{ee,i},i\in\{1,2\}$ to bound the estimation error (for fixed design) incurred when using noisy label ${\bm{y}}_{T+1}$ and $Y$.

The choice of $\epsilon_{ee,i}$, and $\epsilon_{ic,i}$ are respectively justified in Lemma C.5, Claim C.4, Lemma C.10 and Claim C.11, along with some more detailed descriptions.

Each step is with high probability $1-\delta/10$ over the randomness of $\mathcal{X}$ or $X_{T+1}$. Therefore overall by union bound, with probability $1-\delta$, by plugging in the values of $\epsilon_{ic,i}$ and $\epsilon_{ee,i}$ we have:

Notice a term $\|\Sigma\|/n_{1}$ is absorbed by $\|\Sigma\|/n_{2}$ since we assume $n_{1}\geq n_{2}$. ∎

and $\|\hat{B}\|_{F}^{2}\leq 3R$, $\|\hat{W}\|_{F}^{2}\leq 3R$ for any $\lambda\geq\frac{2}{n}\|\mathcal{X}^{*}(Z)\|_{2}$.

Here $\mathcal{X}^{*}$ is the adjoint operator of $\mathcal{X}$ such that $\mathcal{X}^{*}(Z)=\sum_{i=1}^{T}X_{t}^{\top}{\bm{z}}_{t}{\bm{e}}_{t}^{\top}$.

With the optimality of $\hat{\Theta}$ we have:

Let $\Delta=\hat{\Theta}-\Theta^{*}$. Therefore

Therefore $\frac{1}{2n_{1}}\|\mathcal{X}(\Delta)\|_{F}^{2}+\frac{\lambda}{2}\|\hat{\Theta}\|_{*}\leq\frac{3}{2}\lambda\|\Theta^{*}\|_{*}$, and clearly both terms satisfy $\frac{1}{n_{1}}\|\mathcal{X}(\Delta)\|_{F}^{2}\leq 3\lambda\|\Theta^{*}\|_{*}$ and $\|\hat{\Theta}\|_{*}\leq 3\|\Theta^{*}\|_{*}$.

For a fixed $\delta>0$, let $\lambda=\epsilon_{ee,1}^{2}+\epsilon_{ic,1}^{2}R$, we have

where $S_{\lambda}:=(\hat{B}^{\top}\Sigma\hat{B}+\lambda I)^{-1}\hat{B}^{\top}\Sigma$.

With the definition of $\hat{{\bm{w}}}$ we write the basic inequality:

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.

We use matrix Bernstein with intrinsic dimension to bound $\lambda$ (See Theorem 7.3.1 in Tropp et al. (2015)).

Write $A=\frac{1}{\sqrt{n}}X^{\top}Z=\frac{1}{\sqrt{n}}\sum_{t=1}^{T}X^{\top}{\bm{z}}_{t}{\bm{e}}_{t}^{\top}=:\sum_{t=1}^{T}S_{t}$.

Then from intrinsic matrix bernstein (Theorem 7.3.1 in Tropp et al. (2015)), with probability $1-\delta$ we have, $\|A\|\leq{\cal{O}}(\sigma\sqrt{\log\frac{1}{\delta}v\log(d_{\Sigma})}+\sigma\log\frac{1}{\delta}L\log(d_{\Sigma}))$, which gives

The sub-gaussian norm of some vector ${\bm{y}}$ is defined as:

are called the Gaussian width of $T$ and the Gaussian complexity of $T$, respectively.

where $K=\max_{i}\|A_{i}\|_{\psi_{2}}$ is the maximal sub-gaussian norm of the rows of $A$. A high-probability version states as follows. With probability $1-\delta$,

where the radius $r(T):=\sup_{{\bm{x}}\in T}\|{\bm{x}}\|_{2}$.

Appendix D Proof of Theorem 7.1

Let $\gamma_{d}$ be the value of Equation (18) when the network has $d$ neurons and $\gamma^{\star}_{d}$ be the value of Equation (39). Then

Let $B,W$ be solutions to Equation (18). Let $\bar{B}=BD_{\beta}^{-1}$ and $D_{\beta}$ be a diagonal matrix whose entries are $\beta_{j}=\|B^{\top}{\bm{e}}_{j}\|_{2}$. The network $f_{B,W}({\bm{x}})=W^{\top}D_{\beta}(\bar{B}^{\top}{\bm{x}})_{+}$ and it satisfies

We first show that $\gamma^{\star}_{d}\leq\gamma_{d}$. Define $\alpha_{t}(\frac{\bm{b}_{j}}{\|\bm{b}_{j}\|})=W_{tj}\beta_{j}$. We verify that

Due to the regularizer, and using the AM-GM inequality, at optimality $\beta_{j}=\|W{\bm{e}}_{j}\|_{2}$. Next, we verify that the two regularizer values are the same. Let $\bar{\bm{w}}_{j}$ be the $j$-th row vector of $W$. We have

Thus the network given by $\alpha_{t}^{\top}\phi({\bm{x}})$ has the same network outputs and regularizer values. Thus $\gamma^{\star}\leq\gamma_{d}$.

Finally, we show that $\gamma_{d}\leq\gamma^{\star}_{d}$. Let $\bar{\bm{b}}_{j}$ for $j\in[d]$ be the support of the optimal measure of (39). Define $\beta_{j}=\sqrt{\|\bm{\alpha}(\bar{\bm{b}}_{j})\|_{2}}$, $B=\bar{B}D_{\beta}$ where $\bar{B}$ is a matrix whose rows are $\bar{\bm{b}}_{j}$, and $W$ such that $W_{jt}=\alpha_{t}(\bar{\bm{b}}_{j})/\sqrt{\|\bm{\alpha}(\bar{\bm{b}}_{j})\|}$.

Finally by our construction $\beta_{j}=\|W{\bm{e}}_{j}\|$, so the regularizer values agree. Thus $\gamma_{d}=\gamma^{\star}_{d}$.

where $\|\beta\|_{2}^{2}=\int\beta(\bar{\bm{b}})^{2}d(\bar{\bm{b}})$ and $\|W\|_{F}^{2}=\sum_{t}\int{\bm{w}}_{t}(\bar{\bm{b}})^{2}d(\bar{\bm{b}})$. With these in place, we note that Equation (39) can be expressed as Equation (13) with $B$ constrained to be a diagonal operator and $x_{it}$ as the lifted features $\phi(x_{it})$.

The global minimizer of Equation (39) with $d=\infty$ may have infinite support, so the corresponding value may not be achieved by minimizing (18). However, Theorem 6.1 only requires that the we obtain a learner network with regularized loss less than the regularized loss of the teacher network. Since the teacher network has $d$ neurons, this value is attainable by (18). Thus the finite-size network does not need to attain the global minimum of (39) for Claim C.1 to 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 infinite-dimensional feature vector $\phi({\bm{x}})$. The only part of the proof of Theorem 6.1 specific to the nuclear norm is that the dual norm is the operator norm. In Lemma C.5 we had an upper bound on $\frac{1}{n}\|X^{\top}Z\|_{2}$. Since we use the $\|\cdot\|_{2,1}$ norm, we must upper bound $\frac{1}{n}\|X^{\top}Z\|_{2,\infty}$ , the dual of the $(2,1)$-norm. Note that $\|A\|_{2,\infty}\leq\|A\|_{2}$, so the upper bound in Lemma C.5 still applies. Thus, Theorem 7.1 follows from Theorem 6.1. ∎