Optimal Continual Learning has Perfect Memory and is NP-hard
arXiv:2006.05188
Abstract
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.
Accepted for publication at ICML (International Conference on Machine Learning) 2020; 13 pages, 8 Figures
Cited by in corpus (11)
- Continual Learning in Sensor-based Human Activity Recognition: an Empirical Benchmark Analysis
- An Investigation of Replay-based Approaches for Continual Learning
- Regularization Shortcomings for Continual Learning
- The Effectiveness of Memory Replay in Large Scale Continual Learning
- Meta-Learning with Sparse Experience Replay for Lifelong Language Learning
- On Sequential Bayesian Inference for Continual Learning
- Understanding Continual Learning Settings with Data Distribution Drift Analysis
- A Study of Continual Learning Methods for Q-Learning
- Formalizing the Generalization-Forgetting Trade-off in Continual Learning
- Towards Open World Object Detection
- Continual Learning of Multi-modal Dynamics with External Memory