Provable Lifelong Learning of Representations

Abstract

In lifelong learning, tasks (or classes) to be learned arrive sequentially over time in arbitrary order. During training, knowledge from previous tasks can be captured and transferred to subsequent ones to improve sample efficiency. We consider the setting where all target tasks can be represented in the span of a small number of unknown linear or nonlinear features of the input data. We propose a lifelong learning algorithm that maintains and refines the internal feature representation. We prove that for any desired accuracy on all tasks, the dimension of the representation remains close to that of the underlying representation. The resulting sample complexity improves significantly on existing bounds. In the setting of linear features, our algorithm is provably efficient and the sample complexity for input dimension $d$, $m$ tasks with $k$ features up to error $\epsilon$ is $\tilde{O}(d{k}^{1.5}/\epsilon +km/\epsilon )$. We also prove a matching lower bound for any lifelong learning algorithm that uses a single task learner as a black box. We complement our analysis with an empirical study, including a heuristic lifelong learning algorithm for deep neural networks. Our method performs favorably on challenging realistic image datasets compared to state-of-the-art continual learning methods.

arXiv commentAccepted to AISTATS 2022

References in corpus (13)

• Distilling the Knowledge in a Neural Network
• Overcoming catastrophic forgetting in neural networks
• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Exploring Simple Siamese Representation Learning
• Reinforced Continual Learning
• Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
• Few-Shot Learning via Learning the Representation, Provably
• Provable Meta-Learning of Linear Representations
• Optimization and Generalization of Regularization-Based Continual Learning: a Loss Approximation Viewpoint
• Neural Similarity Learning
• Generalisation Guarantees for Continual Learning with Orthogonal Gradient Descent
• Conditional Meta-Learning of Linear Representations