Few-Shot Learning via Learning the Representation, Provably

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 \emph{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 $O\left(\frac{\mathcal{C}\left(\Phi \right)}{n_{1}T}+\frac{k}{n_2}\right)$; here, $\Phi$ is the representation function class, $\mathcal{C}\left(\Phi \right)$ is its complexity measure, and $k$ is the dimension of the representation. When specialized to linear representation functions, this rate becomes $O\left(\frac{dk}{n_{1}T}+\frac{k}{n_2}\right)$ 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 $O\left(\frac{d}{n_2}\right)$. 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_{1}T$ samples from source tasks can be \emph{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 $n_{1}T$ samples from source tasks.

arXiv commentICLR2021

References in corpus (9)

• A Theoretical Analysis of Contrastive Unsupervised Representation Learning
• The Benefit of Multitask Representation Learning
• Online Meta-Learning
• Random design analysis of ridge regression
• On the Theory of Transfer Learning: The Importance of Task Diversity
• Provable Meta-Learning of Linear Representations
• Predicting What You Already Know Helps: Provable Self-Supervised Learning
• Learning-to-Learn Stochastic Gradient Descent with Biased Regularization
• Incremental Learning-to-Learn with Statistical Guarantees

Cited by in corpus (35)

• On the Opportunities and Risks of Foundation Models
• Exploiting Shared Representations for Personalized Federated Learning
• On the Theory of Transfer Learning: The Importance of Task Diversity
• Provable Meta-Learning of Linear Representations
• Predicting What You Already Know Helps: Provable Self-Supervised Learning
• What Makes Multi-modal Learning Better than Single (Provably)
• Generalization Bounds for Sparse Random Feature Expansions
• Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning
• Probing transfer learning with a model of synthetic correlated datasets
• Meta-Adaptive Nonlinear Control: Theory and Algorithms
• How Important is the Train-Validation Split in Meta-Learning?
• Minimax Estimation for Personalized Federated Learning: An Alternative between FedAvg and Local Training?
• In-N-Out: Pre-Training and Self-Training using Auxiliary Information for Out-of-Distribution Robustness
• Robust Meta-learning for Mixed Linear Regression with Small Batches
• Near-optimal Representation Learning for Linear Bandits and Linear RL
• On the Power of Multitask Representation Learning in Linear MDP
• How Fine-Tuning Allows for Effective Meta-Learning
• A Scaling Law for Synthetic-to-Real Transfer: How Much Is Your Pre-training Effective?
• The Power of Contrast for Feature Learning: A Theoretical Analysis
• Impact of Representation Learning in Linear Bandits
• Bilevel Optimization for Machine Learning: Algorithm Design and Convergence Analysis
• How Does the Task Landscape Affect MAML Performance?
• Optimal Multitask Linear Regression and Contextual Bandits under Sparse Heterogeneity
• On the Statistical Benefits of Curriculum Learning
• Representation Learning Beyond Linear Prediction Functions
• Provable Adaptation across Multiway Domains via Representation Learning
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
• Theoretical bounds on estimation error for meta-learning
• Functional Regularization for Representation Learning: A Unified Theoretical Perspective
• Invariant Feature Learning for Sensor-based Human Activity Recognition
• For Manifold Learning, Deep Neural Networks can be Locality Sensitive Hash Functions
• Two Sides of Meta-Learning Evaluation: In vs. Out of Distribution
• Provable Hierarchy-Based Meta-Reinforcement Learning
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation
• Provable Lifelong Learning of Representations