Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?

• URL: http://arxiv.org/abs/2406.11667v2
• Date: Tue, 18 Jun 2024 04:18:17 GMT
• Title: Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?
• Authors: Constantinos Daskalakis, Noah Golowich,
• Abstract summary: We investigate whether the ability to perform ERM, which computes a hypothesis minimizing empirical risk on a given dataset, is necessary for efficient learning. We show that in real setting of PAC for binary classification, a concept class can be learned using an oracle which only returns a single bit. Our results extend to the learning setting with a slight strengthening of the oracle, as well as to the partial concept, multiclass and real-valued learning settings.
• Score: 26.334900941196082
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The empirical risk minimization (ERM) principle has been highly impactful in machine learning, leading both to near-optimal theoretical guarantees for ERM-based learning algorithms as well as driving many of the recent empirical successes in deep learning. In this paper, we investigate the question of whether the ability to perform ERM, which computes a hypothesis minimizing empirical risk on a given dataset, is necessary for efficient learning: in particular, is there a weaker oracle than ERM which can nevertheless enable learnability? We answer this question affirmatively, showing that in the realizable setting of PAC learning for binary classification, a concept class can be learned using an oracle which only returns a single bit indicating whether a given dataset is realizable by some concept in the class. The sample complexity and oracle complexity of our algorithm depend polynomially on the VC dimension of the hypothesis class, thus showing that there is only a polynomial price to pay for use of our weaker oracle. Our results extend to the agnostic learning setting with a slight strengthening of the oracle, as well as to the partial concept, multiclass and real-valued learning settings. In the setting of partial concept classes, prior to our work no oracle-efficient algorithms were known, even with a standard ERM oracle. Thus, our results address a question of Alon et al. (2021) who asked whether there are algorithmic principles which enable efficient learnability in this setting.

Related papers

• A Unified Framework for Neural Computation and Learning Over Time [56.44910327178975]
  Hamiltonian Learning is a novel unified framework for learning with neural networks "over time" It is based on differential equations that: (i) can be integrated without the need of external software solvers; (ii) generalize the well-established notion of gradient-based learning in feed-forward and recurrent networks; (iii) open to novel perspectives.
  arXiv  Detail & Related papers  (2024-09-18T14:57:13Z)
• LLMs as Probabilistic Minimally Adequate Teachers for DFA Learning [11.037017229299607]
  The emergence of intelligence in large language models (LLMs) has inspired investigations into their integration into automata learning. This paper introduces the probabilistic Minimally Adequate Teacher (pMAT) formulation. We develop techniques to improve answer accuracy and ensure the correctness of the learned automata.
  arXiv  Detail & Related papers  (2024-08-06T07:12:09Z)
• 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)
• Multiclass Boosting: Simple and Intuitive Weak Learning Criteria [72.71096438538254]
  We give a simple and efficient boosting algorithm, that does not require realizability assumptions. We present a new result on boosting for list learners, as well as provide a novel proof for the characterization of multiclass PAC learning.
  arXiv  Detail & Related papers  (2023-07-02T19:26:58Z)
• Impossibility of Collective Intelligence [10.107996426462604]
  We show that it is theoretically impossible to design a rational learning algorithm that has the ability to learn across heterogeneous environments. The only feasible algorithm compatible with all of the axioms is the standard empirical risk minimization. Our impossibility result reveals informational incomparability between environments as one of the foremost obstacles for researchers.
  arXiv  Detail & Related papers  (2022-06-05T07:58:39Z)
• 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)
• On the Statistical Benefits of Curriculum Learning [33.94130046391917]
  We study the benefits of Curriculum learning (CL) in the multitask linear regression problem under both structured and unstructured settings. Our results reveal that adaptive learning can be fundamentally harder than the oracle learning in the unstructured setting.
  arXiv  Detail & Related papers  (2021-11-13T14:51:07Z)
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
  We show how iteration under a more standard notion of low inherent Bellman error, typically employed in least-square value-style algorithms, can provide strong PAC guarantees on learning a near optimal value function. We present a computationally tractable algorithm for the reward-free setting and show how it can be used to learn a near optimal policy for any (linear) reward function.
  arXiv  Detail & Related papers  (2020-08-18T04:34:21Z)
• Discovering Reinforcement Learning Algorithms [53.72358280495428]
  Reinforcement learning algorithms update an agent's parameters according to one of several possible rules. This paper introduces a new meta-learning approach that discovers an entire update rule. It includes both 'what to predict' (e.g. value functions) and 'how to learn from it' by interacting with a set of environments.
  arXiv  Detail & Related papers  (2020-07-17T07:38:39Z)
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning [96.78504087416654]
  Motivated by the prevailing paradigm of using unsupervised learning for efficient exploration in reinforcement learning (RL) problems, we investigate when this paradigm is provably efficient. We present a general algorithmic framework that is built upon two components: an unsupervised learning algorithm and a noregret tabular RL algorithm.
  arXiv  Detail & Related papers  (2020-03-15T19:23:59Z)

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.