Memory Bounds for Continual Learning
Memory Bounds for Continual Learning
复制标题
DOI：
10.1109/focs54457.2022.00056
复制
发表时间：
2022-04
期刊：
影响因子：
--
通讯作者：
Xi Chen;Christos Papadimitriou;Binghui Peng
中科院分区：
文献类型：
--
作者：
Xi Chen;Christos Papadimitriou;Binghui Peng
持续学习，或终身学习，是当前机器学习面临的一项艰巨挑战。它要求学习者依次解决一系列k个不同的学习任务，同时保留其对早期任务的能力；持续学习者应该比为k个任务中的每一个开发和维护一个单独的学习者这种显而易见的解决方案扩展性更好。我们在PAC框架下对持续学习进行了复杂性理论研究。我们创新性地利用通信复杂性来证明，任何持续学习者，即使是不恰当的学习者，都需要随k线性增长的内存，这有力地表明该问题是棘手的。当允许对学习任务进行对数多次遍历的时候，我们提供了一种基于乘法权重更新的算法，其内存需求扩展性良好；我们还证明了这种性能需要不恰当学习。我们推测这些结果可能会为持续学习带来新的有前景的方法。
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.