Statistically and Computationally Efficient Linear Meta-representation Learning

In typical few-shot learning, each task is not equipped with enough data to be learned in isolation. To cope with such data scarcity, meta-representation learning methods train across many related tasks to find a shared (lower-dimensional) representation of the data where all tasks can be solved accurately. It is hypothesized that any new arriving tasks can be rapidly trained on this low-dimensional representation using only a few samples. Despite the practical successes of this approach, its statistical and computational properties are less understood. Recent theoretical studies either provide a highly suboptimal statistical error, or require many samples for every task, which is infeasible in the few-shot learning setting. Moreover, the prescribed algorithms in these studies have little resemblance to those used in practice or they are computationally intractable. To understand and explain the success of popular meta-representation learning approaches such as ANIL [43] , MetaOptNet [36], R2D2 [9], and OML [33], we study a alternating gradient-descent minimization (AltMinGD) method (and its variant alternating minimization (AltMin) in the Appendix) which underlies the aforementioned methods. For a simple but canonical setting of shared linear representations, we show that AltMinGD achieves nearly-optimal estimation error, requiring only Ω(polylog d) samples per task. This agrees with the observed efficacy of this algorithm in the practical few-shot learning scenarios.