# Optimal Continual Learning has Perfect Memory and is NP-hard

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

## Key facts

- Cited by 87 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2020.

## Built on by (most cited first, 30 of 87)

- [A Comprehensive Survey of Continual Learning: Theory, Method and Application](https://mlsanity.com/paper/2302.00487/) (2023)
- [Towards Open World Object Detection](https://mlsanity.com/paper/2103.02603/) (2021)
- [S-Prompts Learning with Pre-trained Transformers: An Occam's Razor for Domain Incremental Learning](https://mlsanity.com/paper/2207.12819/) (2022)
- [Online Continual Learning in Image Classification: An Empirical Survey](https://mlsanity.com/paper/2101.10423/) (2021)
- [DeepCore: A Comprehensive Library for Coreset Selection in Deep Learning](https://mlsanity.com/paper/2204.08499/) (2022)
- [How catastrophic can catastrophic forgetting be in linear regression?](https://mlsanity.com/paper/2205.09588/) (2022)
- [SSUL: Semantic Segmentation with Unknown Label for Exemplar-based Class-Incremental Learning](https://mlsanity.com/paper/2106.11562/) (2021)
- [Continual Learning: Applications and the Road Forward](https://mlsanity.com/paper/2311.11908/) (2023)
- [M3D: Dataset Condensation by Minimizing Maximum Mean Discrepancy](https://mlsanity.com/paper/2312.15927/) (2023)
- [Understanding Catastrophic Forgetting and Remembering in Continual Learning with Optimal Relevance Mapping](https://mlsanity.com/paper/2102.11343/) (2021)
- [Isolation and Impartial Aggregation: A Paradigm of Incremental Learning without Interference](https://mlsanity.com/paper/2211.15969/) (2022)
- [Incorporating Neuro-Inspired Adaptability for Continual Learning in Artificial Intelligence](https://mlsanity.com/paper/2308.14991/) (2023)
- [Understanding Continual Learning Settings with Data Distribution Drift Analysis](https://mlsanity.com/paper/2104.01678/) (2021)
- [The Ideal Continual Learner: An Agent That Never Forgets](https://mlsanity.com/paper/2305.00316/) (2023)
- [Analysis of Catastrophic Forgetting for Random Orthogonal Transformation Tasks in the Overparameterized Regime](https://mlsanity.com/paper/2207.06475/) (2022)
- [Hierarchical Prototype Networks for Continual Graph Representation Learning](https://mlsanity.com/paper/2111.15422/) (2021)
- [How to Reuse and Compose Knowledge for a Lifetime of Tasks: A Survey on Continual Learning and Functional Composition](https://mlsanity.com/paper/2207.07730/) (2022)
- [Emptying the Ocean with a Spoon: Should We Edit Models?](https://mlsanity.com/paper/2310.11958/) (2023)
- [An Investigation of Replay-based Approaches for Continual Learning](https://mlsanity.com/paper/2108.06758/) (2021)
- [Formalizing the Generalization-Forgetting Trade-off in Continual Learning](https://mlsanity.com/paper/2109.14035/) (2021)
- [Random Boxes Are Open-world Object Detectors](https://mlsanity.com/paper/2307.08249/) (2023)
- [Catastrophic Forgetting in Deep Learning: A Comprehensive Taxonomy](https://mlsanity.com/paper/2312.10549/) (2023)
- [Task-Free Continual Learning via Online Discrepancy Distance Learning](https://mlsanity.com/paper/2210.06579/) (2022)
- [Continual Learning in Sensor-based Human Activity Recognition: an Empirical Benchmark Analysis](https://mlsanity.com/paper/2104.09396/) (2021)
- [MIM4DD: Mutual Information Maximization for Dataset Distillation](https://mlsanity.com/paper/2312.16627/) (2023)
- [HiDe-PET: Continual Learning via Hierarchical Decomposition of Parameter-Efficient Tuning](https://mlsanity.com/paper/2407.05229/) (2024)
- [How do Quadratic Regularizers Prevent Catastrophic Forgetting: The Role of Interpolation](https://mlsanity.com/paper/2102.02805/) (2021)
- [Memory Bounds for Continual Learning](https://mlsanity.com/paper/2204.10830/) (2022)
- [Disentangling and Mitigating the Impact of Task Similarity for Continual Learning](https://mlsanity.com/paper/2405.20236/) (2024)
- [Towards Robust Graph Incremental Learning on Evolving Graphs](https://mlsanity.com/paper/2402.12987/) (2024)

## Abstract (arXiv)

Continual Learning (CL) algorithms incrementally learn a predictor or representation across multiple sequentially observed tasks. Designing CL algorithms that perform reliably and avoid so-called catastrophic forgetting has proven a persistent challenge. The current paper develops a theoretical approach that explains why. In particular, we derive the computational properties which CL algorithms would have to possess in order to avoid catastrophic forgetting. Our main finding is that such optimal CL algorithms generally solve an NP-hard problem and will require perfect memory to do so. The findings are of theoretical interest, but also explain the excellent performance of CL algorithms using experience replay, episodic memory and core sets relative to regularization-based approaches.