Optimal Continual Learning has Perfect Memory and is NP-hard
  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.
