Sample Efficient Linear Meta-Learning by Alternating Minimization

• URL: http://arxiv.org/abs/2105.08306v1
• Date: Tue, 18 May 2021 06:46:48 GMT
• Title: Sample Efficient Linear Meta-Learning by Alternating Minimization
• Authors: Kiran Koshy Thekumparampil, Prateek Jain, Praneeth Netrapalli, Sewoong Oh
• Abstract summary: We study a simple alternating minimization method (MLLAM) which alternately learns the low-dimensional subspace and the regressors. We show that for a constant subspace dimension MLLAM obtains nearly-optimal estimation error, despite requiring only $Omega(log d)$ samples per task. We propose a novel task subset selection scheme that ensures the same strong statistical guarantee as MLLAM.
• Score: 74.40553081646995
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Meta-learning synthesizes and leverages the knowledge from a given set of tasks to rapidly learn new tasks using very little data. Meta-learning of linear regression tasks, where the regressors lie in a low-dimensional subspace, is an extensively-studied fundamental problem in this domain. However, existing results either guarantee highly suboptimal estimation errors, or require $\Omega(d)$ samples per task (where $d$ is the data dimensionality) thus providing little gain over separately learning each task. In this work, we study a simple alternating minimization method (MLLAM), which alternately learns the low-dimensional subspace and the regressors. We show that, for a constant subspace dimension MLLAM obtains nearly-optimal estimation error, despite requiring only $\Omega(\log d)$ samples per task. However, the number of samples required per task grows logarithmically with the number of tasks. To remedy this in the low-noise regime, we propose a novel task subset selection scheme that ensures the same strong statistical guarantee as MLLAM, even with bounded number of samples per task for arbitrarily large number of tasks.

Related papers

• Meta Learning for High-dimensional Ising Model Selection Using $\ell_1$-regularized Logistic Regression [28.776950569604026]
  We consider the meta learning problem for estimating the graphs associated with high-dimensional Ising models. Our goal is to use the information learned from the auxiliary tasks in the learning of the novel task to reduce its sufficient sample complexity.
  arXiv  Detail & Related papers  (2022-08-19T20:28:39Z)
• New Tight Relaxations of Rank Minimization for Multi-Task Learning [161.23314844751556]
  We propose two novel multi-task learning formulations based on two regularization terms. We show that our methods can correctly recover the low-rank structure shared across tasks, and outperform related multi-task learning methods.
  arXiv  Detail & Related papers  (2021-12-09T07:29:57Z)
• Instance-Level Task Parameters: A Robust Multi-task Weighting Framework [17.639472693362926]
  Recent works have shown that deep neural networks benefit from multi-task learning by learning a shared representation across several related tasks. We let the training process dictate the optimal weighting of tasks for every instance in the dataset. We conduct extensive experiments on SURREAL and CityScapes datasets, for human shape and pose estimation, depth estimation and semantic segmentation tasks.
  arXiv  Detail & Related papers  (2021-06-11T02:35:42Z)
• Memory-Based Optimization Methods for Model-Agnostic Meta-Learning and Personalized Federated Learning [56.17603785248675]
  Model-agnostic meta-learning (MAML) has become a popular research area. Existing MAML algorithms rely on the episode' idea by sampling a few tasks and data points to update the meta-model at each iteration. This paper proposes memory-based algorithms for MAML that converge with vanishing error.
  arXiv  Detail & Related papers  (2021-06-09T08:47:58Z)
• Adaptive Task Sampling for Meta-Learning [79.61146834134459]
  Key idea of meta-learning for few-shot classification is to mimic the few-shot situations faced at test time. We propose an adaptive task sampling method to improve the generalization performance.
  arXiv  Detail & Related papers  (2020-07-17T03:15:53Z)
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning [123.69175280309226]
  One of the challenges in online reinforcement learning (RL) is that the agent needs to trade off the exploration of the environment and the exploitation of the samples to optimize its behavior. We propose to tackle the exploration-exploitation problem following a decoupled approach composed of: 1) An "objective-specific" algorithm that prescribes how many samples to collect at which states, as if it has access to a generative model (i.e., sparse simulator of the environment); 2) An "objective-agnostic" sample collection responsible for generating the prescribed samples as fast as possible.
  arXiv  Detail & Related papers  (2020-07-13T15:17:35Z)
• Robust Meta-learning for Mixed Linear Regression with Small Batches [34.94138630547603]
  We study a fundamental question: can abundant small-data tasks compensate for the lack of big-data tasks? Existing approaches show that such a trade-off is efficiently achievable, with the help of medium-sized tasks with $Omega(k1/2)$ examples each. We introduce a spectral approach that is simultaneously robust under both scenarios.
  arXiv  Detail & Related papers  (2020-06-17T07:59:05Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator) We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$. We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
  arXiv  Detail & Related papers  (2020-05-26T17:53:18Z)
• Meta-learning for mixed linear regression [44.27602704497616]
  In modern supervised learning, there are a large number of tasks, but many of them are associated with only a small amount of labeled data. We study a fundamental question of interest: When can abundant tasks with small data compensate for lack of tasks with big data? We show that we can efficiently utilize small data tasks with the help of $tildeOmega(k3/2)$ medium data tasks each with $tildeOmega(k1/2)$ examples.
  arXiv  Detail & Related papers  (2020-02-20T18:34:28Z)
• Task-Robust Model-Agnostic Meta-Learning [42.27488241647739]
  We introduce the notion of "task-robustness" by reformulating the popular ModelAgnostic Meta-Learning (AML) objective. The solution to this novel formulation is taskrobust in the sense that it places equal importance on even the most difficult/or rare tasks.
  arXiv  Detail & Related papers  (2020-02-12T02:20:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.