Few-Shot Learning via Learning the Representation, Provably

This paper studies few-shot learning via representation learning, where one uses T 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 n2 (ll n1) 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 of a sample size reduction is possible. First, we study the setting where this common representation is low-dimensional and provide a fast rate of Oleft(fracCleft(Phiright)n1T + frackn2right); here, Phi is the representation function class, Cleft(Phiright) is its complexity measure, and k is the dimension of the representation. When specialized to linear representation functions, this rate becomes Oleft(fracdkn1T + frackn2right) where d (gg k) is the ambient input dimension, which is a substantial improvement over the rate without using representation learning, i.e. over the rate of Oleft(fracdn2right). This result bypasses the Omega(frac1T) barrier under the i.i.d. task assumption, and can capture the desired property that all n1T samples from source tasks can be pooled together for representation learning. 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 network learning. Our results demonstrate representation learning can fully utilize all n1T samples from source tasks.