Efficient Representations for Lifelong Learning and Autoencoding

By Maria-Florina Balcan, Avrim Blum, Santosh Srinivas Vempala. 2014

75 citations recorded by the source corpus.

It has been a long-standing goal in machine learning, as well as in AI more generally, to develop life-long learning systems that learn many different tasks over time, and reuse insights from tasks learned, “learning to learn” as they do so. In this work we pose and provide efficient algorithms for several natural theoretical formulations of this goal. Specifically, we consider the problem of learning many different target functions over time, that share certain commonalities that are initially unknown to the learning algorithm. Our aim is to learn new internal representations as the algorithm learns new target functions, that capture this commonality and allow subsequent learning tasks to be solved more efficiently and from less data. We develop efficient algorithms for two very different kinds of commonalities that target functions might share: one based on learning common lowdimensional and unions of low-dimensional subspaces and one based on learning nonlinear Boolean combinations of features. Our algorithms for learning Boolean feature combinations additionally have a dual interpretation, and can be viewed as giving an efficient procedure for constructing near-optimal sparse Boolean autoencoders under a natural “anchor-set” assumption.

Subfields: Representation & Self-Supervised Learning, Meta & Continual Learning

How researchers see this paper

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

In Representation & Self-Supervised Learning

In Meta & Continual Learning

Citations in the corpus

Adaptive Gradient-Based Meta-Learning Methods (2019, background): “However, much effort has also been devoted to the online setting, often through the framework of lifelong learning [45, 5, 2].”
Gradient Episodic Memory for Continual Learning (2017, background): “This learning setting led to implementations [Carlson et al., 2010, Ruvolo and Eaton, 2013, Ring, 1997], and theoretical investigations [Baxter, 2000, Balcan et al., 2015, Pentina and Urner, 2016], although the latter ones have been restricted to linear models.”
The Ideal Continual Learner: An Agent That Never Forgets (2023, background): “Yet another task relationship is that every objective Lt is the composition of two functions ft ◦ g, where the function g : Rn → Rs is referred to as the shared representation; see, e.g., Maurer et al. (2016); Balcan et al. (2015); Tripuraneni et al. (2021); Du et al. (2021).”
Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructions (2022, background): “The works [33, 25, 1, 4] provide theoretical guarantees on lifelong learning.”
Lifelong Learning with Weighted Majority Votes (2016, methodology): “Note that the concepts below are closely related to the ones used in [3] for the case of linear predictors and linear combinations over these.”
An Online Learning Approach to Interpolation and Extrapolation in Domain Generalization (2021, background): “, 2015; Hazan, 2016), for which there already exist provable regret bounds and efficiency guarantees (Balcan et al., 2015; Alquier et al., 2017).”
Generalize Across Tasks: Efficient Algorithms for Linear Representation Learning (2019, background): “Learning a linear representation has been studied by Balcan et al. (2015).”
A Sample Complexity Separation between Non-Convex and Convex Meta-Learning (2020, methodology): “Inspired by their popularity, several recent learning-theoretic analyses of meta-learning have followed suit, eschewing customization to specific hypothesis classes such as halfspaces (Maurer & Pontil, 2013; Balcan et al., 2015) and instead favoring the convex-case study of gradient-based algorithms”
Incremental Learning-to-Learn with Statistical Guarantees (2018, background): “The papers (Balcan et al., 2015; Herbster et al., 2016) present results in an online framework which applies to a finite number of tasks using different performance measures.”
Learning-to-Learn Stochastic Gradient Descent with Biased Regularization (2019, background): “, 2018; Ravi & Larochelle, 2017) and the theoretical challenge of statistically principled and efficient solutions (Alquier et al., 2017; Balcan et al., 2015; Maurer et al., 2016; Pentina & Lampert, 2014; Denevi et al., 2018a;b; Gupta & Roughgarden, 2017).”
On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithms (2019, background): “A closely related problem to this setting is the lifelong learning framework (Balcan et al., 2015; Alquier et al., 2017).”
Provable Guarantees for Gradient-Based Meta-Learning (2019, background): “Here there are many theoretical results for learning useful data representations (Ruvolo & Eaton, 2013; Pentina & Lampert, 2014; Balcan et al., 2015; Alquier et al., 2017); the PACBayesian result of Pentina & Lampert (2014) can also be used for regularization-based parameter transfer, which we also ”
A Continual Learning Survey: Defying Forgetting in Classification Tasks (2019, background): “The inﬂuence of dropout [43] and different activation functions on forgetting have been studied empirically for two sequential tasks [31] , and several works studied task incremental learning from a theoretical perspective [44], [45], [46], [47].”
Lifelong Learning with Non-i.i.d. Tasks (2015, background): “To our knowledge, only the recent [10] has studied lifelong learning without an i.”
Provable Lifelong Learning of Representations (2021, methodology): “For linear features, if a new target function does not have a good representation as a combination of the features learned so far, the new target is itself a new feature since everything is linear (Algorithm 1, [Balcan et al., 2015]), so k0 above is 1.”
Regret Bounds for Lifelong Learning (2016, background): “, 2016, and references therein), we are aware of only few papers which address the statistical analysis of lifelong learning (Balcan et al., 2015; Herbster et al., 2016; Pentina and Urner, 2016).”