We build a theoretical framework for understanding practical meta-learning methods that enables the integration of sophisticated formalizations of task-similarity with the extensive literature on online convex optimization and sequential prediction algorithms in order to provide within-task performance guarantees. Our approach improves upon recent analyses of parameter-transfer by enabling the task-similarity to be learned adaptively and by improving transfer-risk bounds in the setting of statistical learning-to-learn. It also leads to straightforward derivations of average-case regret bounds for efficient algorithms in settings where the task-environment changes dynamically or the tasks share a certain geometric structure. Meta-learning, or learning-to-learn (LTL) BID26 , has recently re-emerged as an important direction for developing algorithms capable of performing well in multitask learning, changing environments, and federated settings. By using the data of numerous training tasks, meta-learning algorithms seek to perform well on new, potentially related test tasks without using many samples from them. Successful modern approaches have also focused on exploiting the capacity of deep neural networks, whether by learning multi-task data representations passed to simple classifiers BID25 or by neural control of the optimization algorithms themselves BID23 .Because of its simplicity and flexibility, a common approach is that of parameter-transfer, in which all tasks use the same class of Θ-parameterized functions f θ : X → Y; usually a shared global model φ ∈ Θ is learned that can then be used to train task-specific parameters. In gradient-based meta-learning (GBML) BID11 , φ is a metainitialization such that a few stochastic gradient steps on a Preliminary work. Under review by the International Conference on Machine Learning (ICML). Do not distribute. few samples from a new task suffice to learn a good taskspecific model. GBML is now used in a variety of LTL domains such as vision BID18 BID21 BID17 , federated learning BID7 , and robotics BID0 . However, its simplicity also raises many practical and theoretical questions concerning what task-relationships it is able to exploit and in which settings it may be expected to succeed.While theoretical LTL has a long history BID4 BID19 BID22 , there has recently been an effort to understand GBML in particular. This has naturally lead to online convex optimization (OCO) (Zinkevich, 2003) , either directly BID12 BID16 or via online-to-batch conversion to statistical LTL BID16 BID9 . These efforts all consider learning a shared initialization of a descent method; BID12 then prove learnability of a metalearning algorithm while BID16 and BID9 give meta-test-time performance guarantees.However, this line of work has so far considered at most a very restricted, if natural, notion of task-similarity -closeness to a single fixed point in the parameter space. We introduce a new theoretical framework, Averaged-Regret Upper-Bound Analysis (ARUBA), that enables the derivation of meta-learning algorithms that can provably take advantage of much more sophisticated task-structure. Expanding significantly upon the work of BID16 , ARUBA treats meta-learning as the online learning of a sequence of losses that each upper bound the regret on a single task. These bounds frequently have convenient functional forms that are (a) nice enough for us to easily draw on the existing OCO literature and (b) strongly dependent on both the task-data and the meta-initialization, thus encoding task-similarity in a mathematically accessible way. Using ARUBA we provide new or dramatically improved meta-learning algorithms in the following settings:• Adaptive Meta-Learning: A major drawback of previous work is the reliance on knowing the task-similarity beforehand to set the learning rate BID12 or regularization BID9 , or the use of a suboptimal guess-and-tune approach based on the doubling trick BID16 . ARUBA yields a simple and efficient gradient-based algorithm that eliminates the need to guess the task-similarity by learning it on-the-fly.• Statistical LTL: ARUBA allows us to leverage powerful results in online-to-batch conversion BID27 BID15 to derive new upper-bounds on the transfer risk when using GBML for statistical LTL BID4 , including fast rates in the number of tasks when the task-similarity is known and fully highprobability guarantees for a class of losses that includes linear regression. These results improve directly upon the guarantees of BID16 and BID9 for similar or identical GBML algorithms.• LTL in Dynamic Environments: Many practical applications of GBML include settings where the optimal initialization may change over time due to a changing taskenvironment BID0 . However, current theoretical work on GBML has only considered learning a fixed initialization BID12 BID9 . ARUBA reduces the problem of meta-learning in changing environments to a dynamic regret-minimization problem, for which there exists a vast array of online algorithms with provable guarantees.• Meta-Learning the Task Geometry: A recurring theme in parameter-transfer LTL is the idea that certain model weights, such as those encoding a shared representation, are common to all tasks, whereas others, such as those performing a task-specific classification, need to be updated on each one. However, by simply using a fixed initialization we are forced to re-learn this structure on every task. Using ARUBA we provide an algorithm that can learn and take advantage of such structure by adaptively determining which directions in parameter-space need to be updated. We further provide a fully adaptive, per-coordinate variant that may be viewed as an analog for Reptile BID21 of the Meta-SGD modification of MAML BID11 BID18 , which learns a per-coordinate learning rate; in addition to its provable guarantees, our version is more efficient and can be applied to a variety of GBML methods.In the current paper we provide in Section 2 an introduction to ARUBA and use it to show guarantees for adaptive and statistical LTL. We defer our theory for meta-learning in dynamic environments and of different task-geometries, as well as our empirical results, to the full version of the paper.
Practical adaptive algorithms for gradient-based meta-learning with provable guarantees.
{"src": "scitldr-AIC_train", "paper_id": "S1lSNcrs2N"}