Memory Bounds for Continual Learning
By Xi Chen, Christos Papadimitriou, Binghui Peng. 2022
26 citations recorded by the source corpus.
Continual learning, or lifelong learning, is a formidable current challenge to machine learning. It requires the learner to solve a sequence of k different learning tasks, one after the other, while retaining its aptitude for earlier tasks; the continual learner should scale better than the obvious solution of developing and maintaining a separate learner for each of the k tasks. We embark on a complexity-theoretic study of continual learning in the PAC framework. We make novel uses of communication complexity to establish that any continual learner, even an improper one, needs memory that grows linearly with k, strongly suggesting that the problem is intractable. When logarithmically many passes over the learning tasks are allowed, we provide an algorithm based on multiplicative weights update whose memory requirement scales well; we also establish that improper learning is necessary for such performance. We conjecture that these results may lead to new promising approaches to continual learning.
Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Computer Vision and Pattern Recognition
- René Vidal
- Paris V. Giampouras
- Liangzu Peng
- Ehsan Elhamifar
- Paolo Favaro
- Shuicheng Yan
- Zhouchen Lin
- Jitendra Malik
Citations in the corpus
- The Ideal Continual Learner: An Agent That Never Forgets (2023, background): “(2020) and Chen et al. (2022), which suggest that continual learning without forgetting would require memory to grow linearly with the number T of tasks.”