  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.
