mlsanityData to 7 Oct 2026

Optimal Continual Learning has Perfect Memory and is NP-hard

arXiv 2006.05188 ↗First posted 9 Jun 2020cs.LG cs.AI stat.MLcited by 86

Not on the map. Why?

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.

Key facts. Cited by 86 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 15; 2022: 21; 2023: 21; 2024: 11; 2025: 10; 2026: 8.

86 papers.

Sort:

  1. 2023A Comprehensive Survey of Continual Learning: Theory, Method and Applicationcited by 860
  2. 2021Towards Open World Object Detectioncited by 297
  3. 2022S-Prompts Learning with Pre-trained Transformers: An Occam's Razor for Domain Incremental Learningcited by 246
  4. 2021Online Continual Learning in Image Classification: An Empirical Surveycited by 242
  5. 2022DeepCore: A Comprehensive Library for Coreset Selection in Deep Learningcited by 146
  6. 2022How catastrophic can catastrophic forgetting be in linear regression?cited by 80
  7. 2021SSUL: Semantic Segmentation with Unknown Label for Exemplar-based Class-Incremental Learningcited by 71
  8. 2023Continual Learning: Applications and the Road Forwardcited by 59
  9. 2023M3D: Dataset Condensation by Minimizing Maximum Mean Discrepancycited by 49
  10. 2021Understanding Catastrophic Forgetting and Remembering in Continual Learning with Optimal Relevance Mappingcited by 47
  11. 2022Isolation and Impartial Aggregation: A Paradigm of Incremental Learning without Interferencecited by 44
  12. 2023Incorporating Neuro-Inspired Adaptability for Continual Learning in Artificial Intelligencecited by 43
38 more
  1. 2021Understanding Continual Learning Settings with Data Distribution Drift Analysiscited by 38
  2. 2023The Ideal Continual Learner: An Agent That Never Forgetscited by 34
  3. 2021Hierarchical Prototype Networks for Continual Graph Representation Learningcited by 28
  4. 2022Analysis of Catastrophic Forgetting for Random Orthogonal Transformation Tasks in the Overparameterized Regimecited by 28
  5. 2022How to Reuse and Compose Knowledge for a Lifetime of Tasks: A Survey on Continual Learning and Functional Compositioncited by 27
  6. 2023Emptying the Ocean with a Spoon: Should We Edit Models?cited by 27
  7. 2021An Investigation of Replay-based Approaches for Continual Learningcited by 26
  8. 2021Formalizing the Generalization-Forgetting Trade-off in Continual Learningcited by 24
  9. 2023Random Boxes Are Open-world Object Detectorscited by 24
  10. 2023Catastrophic Forgetting in Deep Learning: A Comprehensive Taxonomycited by 24
  11. 2022Task-Free Continual Learning via Online Discrepancy Distance Learningcited by 22
  12. 2021Continual Learning in Sensor-based Human Activity Recognition: an Empirical Benchmark Analysiscited by 21
  13. 2023MIM4DD: Mutual Information Maximization for Dataset Distillationcited by 21
  14. 2024HiDe-PET: Continual Learning via Hierarchical Decomposition of Parameter-Efficient Tuningcited by 20
  15. 2021How do Quadratic Regularizers Prevent Catastrophic Forgetting: The Role of Interpolationcited by 19
  16. 2024Disentangling and Mitigating the Impact of Task Similarity for Continual Learningcited by 19
  17. 2022Memory Bounds for Continual Learningcited by 18
  18. 2024Towards Robust Graph Incremental Learning on Evolving Graphscited by 18
  19. 2021Continual Learning in Deep Networks: an Analysis of the Last Layercited by 17
  20. 2022A Theory for Knowledge Transfer in Continual Learningcited by 16
  21. 2021Saliency Guided Experience Packing for Replay in Continual Learningcited by 14
  22. 2023GRASP: A Rehearsal Policy for Efficient Online Continual Learningcited by 13
  23. 2022Continual Variational Autoencoder Learning via Online Cooperative Memorizationcited by 12
  24. 2024On the Diminishing Returns of Width for Continual Learningcited by 12
  25. 2024Continual Learning on Graphs: A Surveycited by 11
  26. 2022Continual Learning with Guarantees via Weight Interval Constraintscited by 10
  27. 2022A Benchmark and Empirical Analysis for Replay Strategies in Continual Learningcited by 8
  28. 2024Learning to Continually Learn with the Bayesian Principlecited by 8
  29. 2025On-device edge learning for IoT data streams: a surveycited by 8
  30. 2023On the Limitation and Experience Replay for GNNs in Continual Learningcited by 7
  31. 2023DOCTOR: A Multi-Disease Detection Continual Learning Framework Based on Wearable Medical Sensorscited by 7
  32. 2023Continual Learning with Strong Experience Replaycited by 7
  33. 2024On the Convergence of Continual Learning with Adaptive Methodscited by 7
  34. 2023On Sequential Bayesian Inference for Continual Learningcited by 6
  35. 2023Replay-enhanced Continual Reinforcement Learningcited by 6
  36. 2025Bridging Streaming Continual Learning via In-Context Large Tabular Modelscited by 6
  37. 2022Re-examining Distillation For Continual Object Detectioncited by 5
  38. 2025Sequence Transferability and Task Order Selection in Continual Learningcited by 5

50 most cited of 86 All 86 (JSON)