Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructions

Binghui Peng, Andrej Risteski

Continual Learning (CL) remains one of the most persistent challenges in machine learning. As models encounter sequential tasks or environments, they often suffer from "catastrophic forgetting"—the tendency to completely erase knowledge of past tasks while learning new ones. While empirical workarounds and heuristics abound, rigorous theoretical foundations defining what a guarantee against forgetting actually looks like have been scarce.

This paper formalizes CL through the lens of feature extraction, offering both a provably efficient algorithm for linear features and a fundamental impossibility theorem for non-linear features.

Formalizing Continual Learning

In standard machine learning, data is assumed to be independent and identically distributed (i.i.d.). Continual learning breaks this assumption by exposing the model to a sequence of distinct environments.

The authors frame this challenge as a feature extraction problem, aligning their theory with how large-scale models (like BERT or CLIP) operate in practice. The framework relies on three core pillars:

  1. Shared Features: The model learns a shared representation function, $R(x)$.
  2. Fixed Classifiers: For each task $i$, the model learns a task-specific linear classifier, $v_i$.
  3. Efficiency Constraints: To satisfy memory and privacy constraints, once task $i$ is completed, its training data is discarded and its classifier $v_i$ is permanently frozen.

The central mathematical challenge is updating the shared representation $R(x)$ for a new task without breaking its compatibility with the frozen classifiers of all previous tasks.

The Linear Solution: DPGrad

For linear feature mappings, the authors introduce Doubly Projected Gradient Descent (DPGrad).

Standard approaches, such as Orthogonal Gradient Descent (OGD), attempt to prevent forgetting by ensuring gradient updates do not interfere with the outputs of previous tasks. However, the authors identify a critical insight: preserving the output is insufficient; the underlying feature subspace must also be preserved.

DPGrad achieves this by projecting updates so they are orthogonal to both the column span and the row span of the previous feature matrix. This "double projection" allows the model to adapt to new tasks while maintaining perfect compatibility with older, frozen classifiers.

Empirically, DPGrad's performance is striking. On synthetic high-dimensional linear regression tasks across 500 sequential environments, DPGrad maintained a near-zero average error of 0.001. In stark contrast, vanilla SGD yielded an error of 5.16, and OGD struggled significantly with an error of 83.59. The authors further validated these findings on standard CL benchmarks, including Rotated and Permuted MNIST.

The Non-Linear Barrier: A "Commitment Trap"

The paper's "bad news" comes in the form of a barrier theorem for non-linear features. Using a hard instance construction, the authors prove that even for a simple two-layer neural network, no algorithm can guarantee low error across all tasks in this strict online setting.

This obstruction arises from a "commitment trap." An online learner must commit to a representation for an early task without knowing future data distributions. This early commitment can make it mathematically impossible to find a valid representation for subsequent tasks without altering the frozen classifiers. The authors rigorously establish that for any "proper" learner in this non-linear setting, there exists a sequence of environments where the error must be at least 1/1000, regardless of the algorithm used.

Limitations and Future Directions

While this work provides a robust theoretical foundation for CL, it operates under certain constraints that pave the way for future research:

  • Known Task Identities: The framework assumes that the "environment identity" (which task is being performed) is known at test time. Real-world applications often require the model to infer the task dynamically.
  • Proper vs. Improper Learning: The impossibility result applies specifically to "proper" learners—those restricted to a specific function class. The authors hypothesize that "improper" learning, where the model can dynamically expand its hypothesis space, might offer a pathway around the non-linear barrier.
  • Heuristics for Deep Networks: While a perfect algorithm for non-linear features is mathematically impossible under these constraints, the principles underlying DPGrad (such as preserving row and column spaces) could inspire more robust heuristics for deep neural networks.

Ultimately, this paper delivers a crucial reality check for the continual learning community: while we can achieve perfect sequential learning in linear settings, true non-linear continual learning requires fundamentally rethinking our constraints.

Summary updated

Abstract

Continual learning is an emerging paradigm in machine learning, wherein a model is exposed in an online fashion to data from multiple different distributions (i.e. environments), and is expected to adapt to the distribution change. Precisely, the goal is to perform well in the new environment, while simultaneously retaining the performance on the previous environments (i.e. avoid ``catastrophic forgetting''). While this setup has enjoyed a lot of attention in the applied community, there hasn't be theoretical work that even formalizes the desired guarantees. In this paper, we propose a framework for continual learning through the framework of feature extraction---namely, one in which features, as well as a classifier, are being trained with each environment. When the features are linear, we design an efficient gradient-based algorithm $\mathsf{DPGrad}$, that is guaranteed to perform well on the current environment, as well as avoid catastrophic forgetting. In the general case, when the features are non-linear, we show such an algorithm cannot exist, whether efficient or not.
BibTeX
@inproceedings{peng2022continual,
  author = {Binghui Peng and Andrej Risteski},
  title = {{Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=z9cpLkoSNNh},
}
Figure