# Provable Lifelong Learning of Representations

arXiv: https://arxiv.org/abs/2110.14098 · HTML: https://mlsanity.com/paper/2110.14098/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 50 references that are in the map.
- First posted on arXiv 27 Oct 2021.

## Builds on (most cited first, 30 of 32)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Overcoming catastrophic forgetting in neural networks](https://mlsanity.com/paper/1612.00796/) (2016)
- [Exploring Simple Siamese Representation Learning](https://mlsanity.com/paper/2011.10566/) (2020)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Learning without Forgetting](https://mlsanity.com/paper/1606.09282/) (2016)
- [iCaRL: Incremental Classifier and Representation Learning](https://mlsanity.com/paper/1611.07725/) (2016)
- [Progressive Neural Networks](https://mlsanity.com/paper/1606.04671/) (2016)
- [Continual Lifelong Learning with Neural Networks: A Review](https://mlsanity.com/paper/1802.07569/) (2018)
- [Lifelong Learning with Dynamically Expandable Networks](https://mlsanity.com/paper/1708.01547/) (2017)
- [End-to-End Incremental Learning](https://mlsanity.com/paper/1807.09536/) (2018)
- [Class-incremental learning: survey and performance evaluation on image classification](https://mlsanity.com/paper/2010.15277/) (2020)
- [Orthogonal Gradient Descent for Continual Learning](https://mlsanity.com/paper/1910.07104/) (2019)
- [DER: Dynamically Expandable Representation for Class Incremental Learning](https://mlsanity.com/paper/2103.16788/) (2021)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Maintaining Discrimination and Fairness in Class Incremental Learning](https://mlsanity.com/paper/1911.07053/) (2019)
- [Few-Shot Learning via Learning the Representation, Provably](https://mlsanity.com/paper/2002.09434/) (2020)
- [Reinforced Continual Learning](https://mlsanity.com/paper/1805.12369/) (2018)
- [Adaptive Gradient-Based Meta-Learning Methods](https://mlsanity.com/paper/1906.02717/) (2019)
- [Provable Meta-Learning of Linear Representations](https://mlsanity.com/paper/2002.11684/) (2020)
- [A Theoretical Analysis of Catastrophic Forgetting through the NTK Overlap Matrix](https://mlsanity.com/paper/2010.04003/) (2020)
- [Generalisation Guarantees for Continual Learning with Orthogonal Gradient Descent](https://mlsanity.com/paper/2006.11942/) (2020)
- [Provable Guarantees for Gradient-Based Meta-Learning](https://mlsanity.com/paper/1902.10644/) (2019)
- [Orthogonal Over-Parameterized Training](https://mlsanity.com/paper/2004.04690/) (2020)
- [How Fine-Tuning Allows for Effective Meta-Learning](https://mlsanity.com/paper/2105.02221/) (2021)
- [The Advantage of Conditional Meta-Learning for Biased Regularization and Fine-Tuning](https://mlsanity.com/paper/2008.10857/) (2020)
- [Efficient Representations for Life-Long Learning and Autoencoding](https://mlsanity.com/paper/1411.1490/) (2014)
- [Heated-Up Softmax Embedding](https://mlsanity.com/paper/1809.04157/) (2018)
- [Neural Similarity Learning](https://mlsanity.com/paper/1910.13003/) (2019)

## Built on by (most cited first, 15 of 15)

- [Theory on Forgetting and Generalization of Continual Learning](https://mlsanity.com/paper/2302.05836/) (2023)
- [The Ideal Continual Learner: An Agent That Never Forgets](https://mlsanity.com/paper/2305.00316/) (2023)
- [A Statistical Theory of Regularization-Based Continual Learning](https://mlsanity.com/paper/2406.06213/) (2024)
- [Memory Bounds for Continual Learning](https://mlsanity.com/paper/2204.10830/) (2022)
- [Nearly Minimax Algorithms for Linear Bandits with Shared Representation](https://mlsanity.com/paper/2203.15664/) (2022)
- [Continual Learning by Modeling Intra-Class Variation](https://mlsanity.com/paper/2210.05398/) (2022)
- [Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructions](https://mlsanity.com/paper/2203.14383/) (2022)
- [Last Iterate Convergence of Incremental Methods and Applications in Continual Learning](https://mlsanity.com/paper/2403.06873/) (2024)
- [Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective](https://mlsanity.com/paper/2506.00205/) (2025)
- [Measuring Representational Shifts in Continual Learning: A Linear Transformation Perspective](https://mlsanity.com/paper/2505.20970/) (2025)
- [Action Flow Matching for Continual Robot Learning](https://mlsanity.com/paper/2504.18471/) (2025)
- [On the Theory of Continual Learning with Gradient Descent for Neural Networks](https://mlsanity.com/paper/2510.05573/) (2025)
- [Sample Compression for Self Certified Continual Learning](https://mlsanity.com/paper/2503.10503/) (2025)
- [Provable Effects of Data Replay in Continual Learning: A Feature Learning Perspective](https://mlsanity.com/paper/2602.02767/) (2026)
- [Bridging Lifelong and Multi-Task Representation Learning via Algorithm and Complexity Measure](https://mlsanity.com/paper/2511.01847/) (2025)

## Abstract (arXiv)

In lifelong learning, tasks (or classes) to be learned arrive sequentially over time in arbitrary order. During training, knowledge from previous tasks can be captured and transferred to subsequent ones to improve sample efficiency. We consider the setting where all target tasks can be represented in the span of a small number of unknown linear or nonlinear features of the input data. We propose a lifelong learning algorithm that maintains and refines the internal feature representation. We prove that for any desired accuracy on all tasks, the dimension of the representation remains close to that of the underlying representation. The resulting sample complexity improves significantly on existing bounds. In the setting of linear features, our algorithm is provably efficient and the sample complexity for input dimension d, m tasks with k features up to error ε is tildeO(dk1.5/ε+km/ε). We also prove a matching lower bound for any lifelong learning algorithm that uses a single task learner as a black box. We complement our analysis with an empirical study, including a heuristic lifelong learning algorithm for deep neural networks. Our method performs favorably on challenging realistic image datasets compared to state-of-the-art continual learning methods.