Memory Bounds for Continual Learning

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.

Authors

• Xi Chen 0001
• Christos H. Papadimitriou
• Binghui Peng

Keywords

• Computer science
• Memory management
• Machine learning
• Picture archiving and communication systems
• Complexity theory
• Task analysis
• Incremental Learning
• Learning Task
• Complex Communication
• Multiplicative Update
• Data Distribution
• Lower Bound
• Generative Adversarial Networks
• Convex Optimization
• Communication Problems
• Sequential Task
• Original Distribution
• Complex Learning
• Distribution Of Sequences
• Information Bits
• Multiple Passages
• Direct Sum
• Finite Field
• Rejection Sampling
• One-way Communication
• Catastrophic Forgetting
• Reed-Solomon Codes
• Total Communication
• Communication Rounds
• Small Positive Constant
• Forward Error Correction
• Boolean Function
• Learning Requirements
• Deep Neural Network
• Neural Network
• Continual learning
• lifelong learning
• foundation of machine learning