Optimal Continual Learning has Perfect Memory and is NP-hard
Authors: Jeremias Knoblauch, Hisham Husain, Tom Diethe
ICML 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main finding is that such optimal CL algorithms generally solve an NP-HARD problem and will require perfect memory to do so. The current paper develops a theoretical approach that explains why. We show that without any further assumptions, the optimality of CL algorithms can be studied with the tools of set theory (Lemma 1), which drastically simplifies the subsequent analysis. We show that optimal CL algorithms can solve a version of the set intersection decision problem (Lemma 2). Crucially, this decision problem will generally be NP-COMPLETE, meaning that the optimal CL algorithm itself is NP-HARD (Theorem 1; Corollary 1). optimal CL algorithms are NP-HARD and (2) optimal CL algorithms require perfect memory. |
| Researcher Affiliation | Collaboration | Jeremias Knoblauch 1 Hisham Husain 2 Tom Diethe 3 1Department of Statistics, Warwick University & The Alan Turing Institute, London 2Australian National University, Canberra & Data61, Sydney 3Amazon. |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper mentions 'A video summary of these contributions is available at https://www.youtube.com/watch?v=Ma-H37QtkM8', which is a video link, not a link to source code. No other statements about code availability are made. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments on specific datasets. While examples use 'empirical measures', these are for theoretical illustration, not actual data training with public access information. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments, therefore no dataset splits for training, validation, or testing are mentioned or relevant. |
| Hardware Specification | No | The paper is theoretical and does not conduct experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not conduct experiments, therefore no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and does not describe or conduct experiments, therefore no experimental setup details such as hyperparameters or training configurations are provided. |