Optimal Continual Learning has Perfect Memory and is NP-hard

By Jeremias Knoblauch, Hisham Husain, Tom Diethe. 2020

117 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Meta & Continual Learning, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Meta & Continual Learning

In Statistical Learning Theory

Citations in the corpus

A Comprehensive Survey of Continual Learning: Theory, Method and Application (2023, background): “Such a classical continual learning problem has proven to be NP-hard in general [62], because the feasible parameter space tends to be narrow and irregular as more tasks are introduced, thus difﬁcult to identify (see Fig.”
Incorporating neuro-inspired adaptability for continual learning in artificial intelligence (2023, background): “16 To minimize EDt(θ) and ED1:t−1(θ) without the use of old training samples D1:t−1 := {Dk} k=1, a continual learning model can only minimize an empirical risk over the current training samples Dt in a parameter space Θ applicable to old tasks [47, 70], denoted as minθ∈Θ ÊDt(θ) where ÊDt(θ) = 1 Nt ∑”
The Ideal Continual Learner: An Agent That Never Forgets (2023, background): “This seems to contradict the results of Knoblauch et al. (2020) and Chen et al. (2022), which suggest that continual learning without forgetting would require memory to grow linearly with the number T of tasks.”
Task-Free Continual Learning via Online Discrepancy Distance Learning (2022, neutral): “Recent attempts have provided the theoretical analysis for CL from different perspectives including the risk bound [46, 51], NP-hard problem [17], Teacher-Student framework [23, 58] and game theory [37].”
S-Prompts Learning with Pre-trained Transformers: An Occam's Razor for Domain Incremental Learning (2022, background): “The sharing-driven network tuning inevitably results in a non-trivial trade-off (or so-called tug-of-war) between old task learning and new task learning [56, 33].”
Continual Learning with Guarantees via Weight Interval Constraints (2022, methodology): “Even simple linear models together with an intuitively appealing upper bound on the prediction error as optimality criterion are NP-HARD (see (Knoblauch et al., 2020)[Example 1]).”
SSUL: Semantic Segmentation with Unknown Label for Exemplar-based Class-Incremental Learning (2021, methodology): “Using exemplar-memory to store a small portion of past training data for CIL is backed with a theoretical ﬁnding [19] as well as strong empirical results [27, 30, 2, 1, 4] for classiﬁcation.”
Towards Open World Object Detection (2021, background): “[26] develops a theoretical justification for the unwarranted power of replay methods.”
Online Continual Learning in Image Classification: An Empirical Survey (2021, positive): “This also confirms the results of three recent studies, where [111] shows the shortcomings of regularization-based approaches in the class incremental setting, [112] theoretically explains why regularization-based methods underperform memory-based methods and [113] empirically demonstrates that KD i”
Generalisation Guarantees for Continual Learning with Orthogonal Gradient Descent (2020, background): “l Learning. Alquier et al. (2017) deﬁne a compound regret for lifelong learning, as the regret with respect to the oracle who would have known the best common representation for all tasks in advance. Knoblauch et al. (2020) show that optimal Continual Learning algorithms generally solve an NP-HARD p”
The Effectiveness of Memory Replay in Large Scale Continual Learning (2020, neutral): “It has been observed that replay based algorithms usually outperform regularization based methods (Nguyen et al., 2017; van de Ven & Tolias, 2019), and some explanation have been made by Knoblauch et al. (2020).”
Regularization Shortcomings for Continual Learning (2019, neutral): “Our conclusions on regularization shortcomings are similar to [12] ones but we used a different approach.”
How to Reuse and Compose Knowledge for a Lifetime of Tasks: A Survey on Continual Learning and Functional Composition (2022, background): “One potential theoretical explanation for this discrepancy is that optimally solving the continual learning problem requires storing and reusing all past data (Knoblauch et al., 2020).”
Continual Variational Autoencoder Learning via Online Cooperative Memorization (2022, background): “In recent years, some studies have provided the theoretical analysis for continual learning from different perspectives including the NP-hard problem [27], risk bound [58,64], Teacher-Student framework [34,57] and game theory [43].”
An Investigation of Replay-based Approaches for Continual Learning (2021, background): “The authors of [46] considered the complexity of CL for the”
Formalizing the Generalization-Forgetting Trade-off in Continual Learning (2021, background): “In [28], it was shown theoretically that memory-based approaches typically do better than regularization-driven approaches, as is empirically observed in this paper, too.”
Continual Learning of Semantic Segmentation using Complementary 2D-3D Data Representations (2021, methodology): “Among the different strategies proposed to address this issue, experience replay has proven to be particularly effective [14], [5], [15], [16], often outperforming approaches based on more complex designs [17], [18].”
CGLB: Benchmark Tasks for Continual Graph Learning (2022, methodology): “Memory-replay based methods select a set of representative data from previous tasks, which are used to retrain the model with the new task data to prevent forgetting [32, 42, 4, 6, 9, 26].”
Saliency Guided Experience Packing for Replay in Continual Learning (2021, background): “The authors in [22] argued that for an optimal performance one needs to store all the past examples in the memory.”