Incremental Learning-to-Learn with Statistical Guarantees

By Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, Massimiliano Pontil. 2018

48 citations recorded by the source corpus.

In learning-to-learn the goal is to infer a learning algorithm that works well on a class of tasks sampled from an unknown meta distribution. In contrast to previous work on batch learning-to-learn, we consider a scenario where tasks are presented sequentially and the algorithm needs to adapt incrementally to improve its performance on future tasks. Key to this setting is for the algorithm to rapidly incorporate new observations into the model as they arrive, without keeping them in memory. We focus on the case where the underlying algorithm is ridge regression parameterized by a positive semidefinite matrix. We propose to learn this matrix by applying a stochastic strategy to minimize the empirical error incurred by ridge regression on future tasks sampled from the meta distribution. We study the statistical properties of the proposed algorithm and prove non-asymptotic bounds on its excess transfer risk, that is, the generalization performance on new tasks from the same meta distribution. We compare our online learning-to-learn approach with a state of the art batch method, both theoretically and empirically.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

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 Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Adaptive Gradient-Based Meta-Learning Methods (2019, background): “Recently, several works have built upon this theory to understand modern LTL, either from a PAC-Bayesian perspective (Amit & Meir, 2018) or in the ridge regression setting with a learned kernel (Denevi et al., 2018).”
Generalisation Guarantees for Continual Learning with Orthogonal Gradient Descent (2020, background): “…a statistical learning theory perspective, they define and provide regret bounds for lifelong learning (Alquier et al., 2017), or study the sample complexity and convergence of meta-learning algorithms (Denevi et al. 2018a, Du et al. 2020, Ji et al. 2020, Saunshi et al. 2020, Denevi et al. 2018b).”
Few-Shot Learning via Learning the Representation, Provably (2020, background): “Lastly, we remark that there are analyses for other representation learning schemes (Arora et al., 2019, McNamara and Balcan, 2017, Galanti et al., 2016, Alquier et al., 2016, Denevi et al., 2018).”
Bilevel Programming for Hyperparameter Optimization and Meta-Learning (2018, background): “Ideas from (Maurer et al., 2016; Denevi et al., 2018) may be useful in this direction.”
Efficient Meta Learning via Minibatch Proximal Update (2019, background): “Alternative to meta-initialization, the meta-regularization approaches have gained recent interest mostly due to their provable strong guarantees on statistical learning and computation efﬁciency [24, 25, 26, 27, 21].”
Provable Guarantees for Gradient-Based Meta-Learning (2019, methodology): “Closely related to our work are the regularization-based approaches of Denevi et al. (2018a;b), which provide statistical learning guarantees for Ridge regression with a meta-learned kernel or bias.”
Provable Representation Learning for Imitation Learning via Bi-level Optimization (2020, background): “Maurer (2009) analyzed linear representation learning, while Bullins et al. (2019); Denevi et al. (2018) provide efficient algorithms to learn linear representations that can reduce sample complexity of a new task.”
A Sample Complexity Separation between Non-Convex and Convex Meta-Learning (2020, background): “Our focus is on a well-studied setting in which tasks such as halfspace learning share a common low-dimensional subspace, with the goal of obtaining sample complexity depending on this sparse structure rather than on the ambient dimension (Maurer, 2009; Maurer & Pontil, 2013; Balcan et al., 2015; De”
Learning To Learn Around A Common Mean (2018, background): “we do not work on what in literature is called future empirical risk [12, 20]), but we sacrifice a subset of them for testing.”
Learning-to-Learn Stochastic Gradient Descent with Biased Regularization (2019, methodology): “The problem of learning-to-learn (LTL) [4, 30] is receiving increasing attention in recent years, due to its practical importance [11, 26] and the theoretical challenge of statistically principled and efficient solutions [1, 2, 21, 23, 9, 10, 12].”
Multi-Step Model-Agnostic Meta-Learning: Convergence and Improved Algorithms (2020, methodology): “…meta-initialization algorithms such as MAML, meta-regularization approaches aim to learn a good bias for a regularized empirical risk minimization problem for intra-task learning (Alquier et al., 2016; Denevi et al., 2018b,a, 2019; Rajeswaran et al., 2019; Balcan et al., 2019; Zhou et al., 2019).”