On the Computability of Multiclass PAC Learning

• URL: http://arxiv.org/abs/2502.06089v1
• Date: Mon, 10 Feb 2025 01:07:23 GMT
• Title: On the Computability of Multiclass PAC Learning
• Authors: Pascale Gourdeau, Tosca Lechner, Ruth Urner,
• Abstract summary: In the recently introduced computable PAC (CPAC) learning framework, both learners and the functions they output are required to be computable. We show that the corresponding computable dimensions for distinguishers characterize CPAC learning.
• Score: 9.507869508188266
• License:
• Abstract: We study the problem of computable multiclass learnability within the Probably Approximately Correct (PAC) learning framework of Valiant (1984). In the recently introduced computable PAC (CPAC) learning framework of Agarwal et al. (2020), both learners and the functions they output are required to be computable. We focus on the case of finite label space and start by proposing a computable version of the Natarajan dimension and showing that it characterizes CPAC learnability in this setting. We further generalize this result by establishing a meta-characterization of CPAC learnability for a certain family of dimensions: computable distinguishers. Distinguishers were defined by Ben-David et al. (1992) as a certain family of embeddings of the label space, with each embedding giving rise to a dimension. It was shown that the finiteness of each such dimension characterizes multiclass PAC learnability for finite label space in the non-computable setting. We show that the corresponding computable dimensions for distinguishers characterize CPAC learning. We conclude our analysis by proving that the DS dimension, which characterizes PAC learnability for infinite label space, cannot be expressed as a distinguisher (even in the case of finite label space).

Related papers

• When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
  A new complexity measure, called the emphspanning capacity, depends solely on the set $Pi$ and is independent of the MDP dynamics. We show there exists a policy class $Pi$ with a bounded spanning capacity that requires a superpolynomial number of samples to learn. This reveals a surprising separation for learnability between generative access and online access models.
  arXiv  Detail & Related papers  (2023-10-09T19:40:54Z)
• Computing the Vapnik Chervonenkis Dimension for Non-Discrete Settings [0.0]
  We develop a method to approximately compute the VC dimension without constraints on the concept classes or their domain set. Our approach is based on our finding that the Empirical Risk Minimization (ERM) learning paradigm can be used as a new tool to characterize the shattering property of a concept class.
  arXiv  Detail & Related papers  (2023-08-19T14:57:24Z)
• A Geometric Notion of Causal Probing [91.14470073637236]
  In a language model's representation space, all information about a concept such as verbal number is encoded in a linear subspace. We give a set of intrinsic criteria which characterize an ideal linear concept subspace. We find that LEACE returns a one-dimensional subspace containing roughly half of total concept information.
  arXiv  Detail & Related papers  (2023-07-27T17:57:57Z)
• Optimal Learners for Realizable Regression: PAC Learning and Online Learning [52.37726841759983]
  We aim to characterize the statistical complexity of realizable regression both in the PAC learning setting and the online learning setting. We first introduce a minimax instance optimal learner for realizable regression and propose a novel dimension that both qualitatively and quantitatively characterizes which classes of real-valued predictors are learnable. In the context of online learning we provide a dimension that characterizes the minimax optimal instance optimal cumulative loss up to a constant factor and design an optimal online learner for realizable regression.
  arXiv  Detail & Related papers  (2023-07-07T21:39:25Z)
• Find a witness or shatter: the landscape of computable PAC learning [63.26015736148707]
  This paper contributes to the study of CPAC learnability by solving three open questions from recent papers. Firstly, we prove that every CPAC learnable class is contained in a class which is properly CPAC learnable with a sample complexity. Secondly, we show that there exists a decidable class of hypothesis which is properly learnable, but only with uncomputably fast growing sample complexity.
  arXiv  Detail & Related papers  (2023-02-06T02:52:36Z)
• A Characterization of Multiclass Learnability [18.38631912121182]
  We characterize multiclass PAC learnability through the DS dimension, a dimension defined by Daniely and Shalev-Shwartz 2014. In the list learning setting, instead of predicting a single outcome for a given unseen input, the goal is to provide a short menu of predictions. Our second main result concerns the Natarajan dimension, which has been a central candidate for characterizing multiclass learnability.
  arXiv  Detail & Related papers  (2022-03-03T07:41:54Z)
• On characterizations of learnability with computable learners [0.0]
  We study computable PAC (CPAC) learning as introduced by Agarwal et al. We give a characterization of a closely related notion of strong CPAC learning. We consider undecidability of (computable) PAC learnability.
  arXiv  Detail & Related papers  (2022-02-10T13:57:20Z)
• On computable learning of continuous features [2.278415626131568]
  We introduce definitions of computable PAC learning for binary classification over computable metric spaces. We also give a presentation of a hypothesis class that does not admit any proper computable PAC learner with computable sample function.
  arXiv  Detail & Related papers  (2021-11-24T02:28:21Z)
• EigenGAN: Layer-Wise Eigen-Learning for GANs [84.33920839885619]
  EigenGAN is able to unsupervisedly mine interpretable and controllable dimensions from different generator layers. By traversing the coefficient of a specific eigen-dimension, the generator can produce samples with continuous changes corresponding to a specific semantic attribute.
  arXiv  Detail & Related papers  (2021-04-26T11:14:37Z)
• Sample-efficient proper PAC learning with approximate differential privacy [51.09425023771246]
  We prove that the sample complexity of properly learning a class of Littlestone dimension $d$ with approximate differential privacy is $tilde O(d6)$, ignoring privacy and accuracy parameters. This result answers a question of Bun et al. (FOCS 2020) by improving upon their upper bound of $2O(d)$ on the sample complexity.
  arXiv  Detail & Related papers  (2020-12-07T18:17:46Z)
• Towards a combinatorial characterization of bounded memory learning [21.031088723668486]
  We develop dimensions that characterize bounded memory learning. We prove both upper and lower bounds for our candidate solution. We conjecture that our characterization holds in a much wider regime of parameters.
  arXiv  Detail & Related papers  (2020-02-08T09:04:21Z)

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.