# Memory Bounds for Continual Learning

arXiv: https://arxiv.org/abs/2204.10830 · HTML: https://mlsanity.com/paper/2204.10830/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 59 references that are in the map.
- First posted on arXiv 22 Apr 2022.

## Builds on (most cited first, 27 of 27)

- [Overcoming catastrophic forgetting in neural networks](https://mlsanity.com/paper/1612.00796/) (2016)
- [Gradient Episodic Memory for Continual Learning](https://mlsanity.com/paper/1706.08840/) (2017)
- [Progressive Neural Networks](https://mlsanity.com/paper/1606.04671/) (2016)
- [Continual Lifelong Learning with Neural Networks: A Review](https://mlsanity.com/paper/1802.07569/) (2018)
- [Continual Learning with Deep Generative Replay](https://mlsanity.com/paper/1705.08690/) (2017)
- [Experience Replay for Continual Learning](https://mlsanity.com/paper/1811.11682/) (2018)
- [Efficient Lifelong Learning with A-GEM](https://mlsanity.com/paper/1812.00420/) (2018)
- [An Empirical Investigation of Catastrophic Forgetting in Gradient-Based Neural Networks](https://mlsanity.com/paper/1312.6211/) (2013)
- [Does Learning Require Memorization? A Short Tale about a Long Tail](https://mlsanity.com/paper/1906.05271/) (2019)
- [Orthogonal Gradient Descent for Continual Learning](https://mlsanity.com/paper/1910.07104/) (2019)
- [When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?](https://mlsanity.com/paper/2012.06421/) (2020)
- [Continual Learning in Low-rank Orthogonal Subspaces](https://mlsanity.com/paper/2010.11635/) (2020)
- [Optimal Continual Learning has Perfect Memory and is NP-hard](https://mlsanity.com/paper/2006.05188/) (2020)
- [Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning](https://mlsanity.com/paper/1602.05161/) (2016)
- [Sample Complexity Bounds on Differentially Private Learning via Communication Complexity](https://mlsanity.com/paper/1402.6278/) (2014)
- [Efficient Representations for Life-Long Learning and Autoencoding](https://mlsanity.com/paper/1411.1490/) (2014)
- [Memory-Sample Tradeoffs for Linear Regression with Small Error](https://mlsanity.com/paper/1904.08544/) (2019)
- [Improved Algorithms for Collaborative PAC Learning](https://mlsanity.com/paper/1805.08356/) (2018)
- [Memory Bounds for the Experts Problem](https://mlsanity.com/paper/2204.09837/) (2022)
- [Extractor-Based Time-Space Lower Bounds for Learning](https://mlsanity.com/paper/1708.02639/) (2017)
- [Tight Bounds for Collaborative PAC Learning via Multiplicative Weights](https://mlsanity.com/paper/1805.09217/) (2018)
- [Provable Lifelong Learning of Representations](https://mlsanity.com/paper/2110.14098/) (2021)
- [Space lower bounds for linear prediction in the streaming model](https://mlsanity.com/paper/1902.03498/) (2019)
- [Efficient Convex Optimization Requires Superlinear Memory](https://mlsanity.com/paper/2203.15260/) (2022)
- [On Communication Complexity of Classification Problems](https://mlsanity.com/paper/1711.05893/) (2017)
- [Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructions](https://mlsanity.com/paper/2203.14383/) (2022)
- [The Communication Complexity of Optimization](https://mlsanity.com/paper/1906.05832/) (2019)

## Built on by (most cited first, 19 of 19)

- [Theory on Forgetting and Generalization of Continual Learning](https://mlsanity.com/paper/2302.05836/) (2023)
- [On Limitations of the Transformer Architecture](https://mlsanity.com/paper/2402.08164/) (2024)
- [The Ideal Continual Learner: An Agent That Never Forgets](https://mlsanity.com/paper/2305.00316/) (2023)
- [A Statistical Theory of Regularization-Based Continual Learning](https://mlsanity.com/paper/2406.06213/) (2024)
- [Fixed Design Analysis of Regularization-Based Continual Learning](https://mlsanity.com/paper/2303.10263/) (2023)
- [Disentangling and Mitigating the Impact of Task Similarity for Continual Learning](https://mlsanity.com/paper/2405.20236/) (2024)
- [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022)
- [Near Optimal Memory-Regret Tradeoff for Online Learning](https://mlsanity.com/paper/2303.01673/) (2023)
- [The sample complexity of multi-distribution learning](https://mlsanity.com/paper/2312.04027/) (2023)
- [Theoretical Insights into Overparameterized Models in Multi-Task and Replay-Based Continual Learning](https://mlsanity.com/paper/2408.16939/) (2024)
- [Last Iterate Convergence of Incremental Methods and Applications in Continual Learning](https://mlsanity.com/paper/2403.06873/) (2024)
- [The complexity of non-stationary reinforcement learning](https://mlsanity.com/paper/2307.06877/) (2023)
- [The I/O Complexity of Attention, or How Optimal is Flash Attention?](https://mlsanity.com/paper/2402.07443/) (2024)
- [Measuring Representational Shifts in Continual Learning: A Linear Transformation Perspective](https://mlsanity.com/paper/2505.20970/) (2025)
- [Replay Can Provably Increase Forgetting](https://mlsanity.com/paper/2506.04377/) (2025)
- [Memory-Query Tradeoffs for Randomized Convex Optimization](https://mlsanity.com/paper/2306.12534/) (2023)
- [Sample-Adaptivity Tradeoff in On-Demand Sampling](https://mlsanity.com/paper/2511.15507/) (2025)
- [What is the role of memorization in Continual Learning?](https://mlsanity.com/paper/2505.17664/) (2025)
- [Self-Evolving Agent Harness](https://mlsanity.com/paper/2610.18813/) (2026)

## Abstract (arXiv)

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.