Provable Lifelong Learning of Representations

• URL: http://arxiv.org/abs/2110.14098v1
• Date: Wed, 27 Oct 2021 00:41:23 GMT
• Title: Provable Lifelong Learning of Representations
• Authors: Xinyuan Cao, Weiyang Liu, Santosh S. Vempala
• Abstract summary: We propose a provable 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.
• Score: 21.440845049501778
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In lifelong learning, the 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 provable 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 $\epsilon$ is $\tilde{O}(dk^{1.5}/\epsilon+km/\epsilon)$. We also prove a matching lower bound for any lifelong learning algorithm that uses a single task learner as a black box. Finally, we complement our analysis with an empirical study.

Related papers

• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networks [69.38572074372392]
  We present the first results proving that feature learning occurs during training with a nonlinear model on multiple tasks. Our key insight is that multi-task pretraining induces a pseudo-contrastive loss that favors representations that align points that typically have the same label across tasks.
  arXiv  Detail & Related papers  (2023-07-13T16:39:08Z)
• Active Representation Learning for General Task Space with Applications in Robotics [44.36398212117328]
  We propose an algorithmic framework for textitactive representation learning, where the learner optimally chooses which source tasks to sample from. We provide several instantiations under this framework, from bilinear and feature-based nonlinear to general nonlinear cases. Our algorithms outperform baselines by $20%-70%$ on average.
  arXiv  Detail & Related papers  (2023-06-15T08:27:50Z)
• On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure [77.60508571062958]
  We investigate the sample complexity of learning the optimal arm for multi-task bandit problems. Arms consist of two components: one that is shared across tasks (that we call representation) and one that is task-specific (that we call predictor) We devise an algorithm OSRL-SC whose sample complexity approaches the lower bound, and scales at most as $H(Glog(delta_G)+ Xlog(delta_H))$, with $X,G,H$ being, respectively, the number of tasks, representations and predictors.
  arXiv  Detail & Related papers  (2022-11-28T08:40:12Z)
• Provably Efficient Lifelong Reinforcement Learning with Linear Function Approximation [41.460894569204065]
  We study lifelong reinforcement learning (RL) in a regret setting of linear contextual Markov decision process (MDP) We propose an algorithm, called UCB Lifelong Value Distillation (UCBlvd), that provably achieves sublinear regret for any sequence of tasks.
  arXiv  Detail & Related papers  (2022-06-01T06:53:28Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm. Our algorithm drives exploration by simply perturbing the training data with judiciously chosen i.i.d. scalar noises. We complement the theory with an empirical evaluation across known difficult exploration tasks.
  arXiv  Detail & Related papers  (2021-06-15T02:23:07Z)
• Sample Efficient Linear Meta-Learning by Alternating Minimization [74.40553081646995]
  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.
  arXiv  Detail & Related papers  (2021-05-18T06:46:48Z)
• Learning Halfspaces With Membership Queries [0.0]
  In some cases, active learning can yield an exponential gain in the number of samples the algorithm needs to see. We show that the algorithm works well in practice, and significantly outperforms uncertainty sampling.
  arXiv  Detail & Related papers  (2020-12-20T18:02:47Z)
• Predicting What You Already Know Helps: Provable Self-Supervised Learning [60.27658820909876]
  Self-supervised representation learning solves auxiliary prediction tasks (known as pretext tasks) without requiring labeled data. We show a mechanism exploiting the statistical connections between certain em reconstruction-based pretext tasks that guarantee to learn a good representation. We prove the linear layer yields small approximation error even for complex ground truth function class.
  arXiv  Detail & Related papers  (2020-08-03T17:56:13Z)

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.