Statistical curriculum learning: An elimination algorithm achieving an oracle risk

• URL: http://arxiv.org/abs/2402.13366v1
• Date: Tue, 20 Feb 2024 20:44:40 GMT
• Title: Statistical curriculum learning: An elimination algorithm achieving an oracle risk
• Authors: Omer Cohen, Ron Meir, Nir Weinberger
• Abstract summary: We consider a statistical version of curriculum learning (CL) in a parametric prediction setting. We consider three types of learners, depending on the level of side-information they receive.
• Score: 31.997825444285457
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a statistical version of curriculum learning (CL) in a parametric prediction setting. The learner is required to estimate a target parameter vector, and can adaptively collect samples from either the target model, or other source models that are similar to the target model, but less noisy. We consider three types of learners, depending on the level of side-information they receive. The first two, referred to as strong/weak-oracle learners, receive high/low degrees of information about the models, and use these to learn. The third, a fully adaptive learner, estimates the target parameter vector without any prior information. In the single source case, we propose an elimination learning method, whose risk matches that of a strong-oracle learner. In the multiple source case, we advocate that the risk of the weak-oracle learner is a realistic benchmark for the risk of adaptive learners. We develop an adaptive multiple elimination-rounds CL algorithm, and characterize instance-dependent conditions for its risk to match that of the weak-oracle learner. We consider instance-dependent minimax lower bounds, and discuss the challenges associated with defining the class of instances for the bound. We derive two minimax lower bounds, and determine the conditions under which the performance weak-oracle learner is minimax optimal.

Related papers

• Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning [28.184175745050474]
  We study the impact of the choice of supervised learning oracle on the computational complexity of reinforcement learning algorithms. First, we identify two-context regression as a minimal oracle in the standard episodic access model. Second, we identify one-context regression as a near-minimal oracle in the stronger reset access model. Third, we broaden our focus to Low-Rank MDPs, where we give cryptographic evidence that the analogous oracle from the Block MDP setting is insufficient.
  arXiv  Detail & Related papers  (2025-02-12T18:47:13Z)
• Probably Approximately Precision and Recall Learning [62.912015491907994]
  Precision and Recall are foundational metrics in machine learning. One-sided feedback--where only positive examples are observed during training--is inherent in many practical problems. We introduce a PAC learning framework where each hypothesis is represented by a graph, with edges indicating positive interactions.
  arXiv  Detail & Related papers  (2024-11-20T04:21:07Z)
• LoRA Unlearns More and Retains More (Student Abstract) [0.0]
  PruneLoRA reduces the need for large-scale parameter updates by applying low-rank updates to the model. We leverage LoRA to selectively modify a subset of the pruned model's parameters, thereby reducing the computational cost, memory requirements and improving the model's ability to retain performance on the remaining classes.
  arXiv  Detail & Related papers  (2024-11-16T16:47:57Z)
• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  We study a variant of Collaborative PAC Learning, in which we aim to learn an accurate classifier for each of the $n$ data distributions. We show that, when the data distributions satisfy a weaker realizability assumption, sample-efficient learning is still feasible.
  arXiv  Detail & Related papers  (2024-02-16T04:32:22Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions. We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Minimax Excess Risk of First-Order Methods for Statistical Learning with Data-Dependent Oracles [25.557803548119466]
  We provide sharp upper and lower bounds for the minimax excess risk of strongly convex and smooth statistical learning. This novel class of oracles can query the gradient with any given data distribution.
  arXiv  Detail & Related papers  (2023-07-10T16:29:05Z)
• Oracle Inequalities for Model Selection in Offline Reinforcement Learning [105.74139523696284]
  We study the problem of model selection in offline RL with value function approximation. We propose the first model selection algorithm for offline RL that achieves minimax rate-optimal inequalities up to logarithmic factors. We conclude with several numerical simulations showing it is capable of reliably selecting a good model class.
  arXiv  Detail & Related papers  (2022-11-03T17:32:34Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  We provide the first oracle-efficient, no-regret algorithms in this setting. We show that if a function class is learnable in the classical setting, then there is an oracle-efficient, no-regret algorithm for contextual bandits.
  arXiv  Detail & Related papers  (2022-02-09T19:22:34Z)
• Knowledge-driven Active Learning [70.37119719069499]
  Active learning strategies aim at minimizing the amount of labelled data required to train a Deep Learning model. Most active strategies are based on uncertain sample selection, and even often restricted to samples lying close to the decision boundary. Here we propose to take into consideration common domain-knowledge and enable non-expert users to train a model with fewer samples.
  arXiv  Detail & Related papers  (2021-10-15T06:11:53Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  Empirical risk minimization (ERM) is the workhorse of machine learning, but its model-agnostic guarantees can fail when we use adaptively collected data. We study a generic importance sampling weighted ERM algorithm for using adaptively collected data to minimize the average of a loss function over a hypothesis class. For policy learning, we provide rate-optimal regret guarantees that close an open gap in the existing literature whenever exploration decays to zero.
  arXiv  Detail & Related papers  (2021-06-03T09:50: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.