A Characterization of Multiclass Learnability

• URL: http://arxiv.org/abs/2203.01550v1
• Date: Thu, 3 Mar 2022 07:41:54 GMT
• Title: A Characterization of Multiclass Learnability
• Authors: Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran and Amir Yehudayoff
• Abstract summary: 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.
• Score: 18.38631912121182
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A seminal result in learning theory characterizes the PAC learnability of binary classes through the Vapnik-Chervonenkis dimension. Extending this characterization to the general multiclass setting has been open since the pioneering works on multiclass PAC learning in the late 1980s. This work resolves this problem: we characterize multiclass PAC learnability through the DS dimension, a combinatorial dimension defined by Daniely and Shalev-Shwartz (2014). The classical characterization of the binary case boils down to empirical risk minimization. In contrast, our characterization of the multiclass case involves a variety of algorithmic ideas; these include a natural setting we call list PAC learning. 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. This dimension was introduced by Natarajan (1988) as a barrier for PAC learning. Whether the Natarajan dimension characterizes PAC learnability in general has been posed as an open question in several papers since. This work provides a negative answer: we construct a non-learnable class with Natarajan dimension one. For the construction, we identify a fundamental connection between concept classes and topology (i.e., colorful simplicial complexes). We crucially rely on a deep and involved construction of hyperbolic pseudo-manifolds by Januszkiewicz and Swiatkowski. It is interesting that hyperbolicity is directly related to learning problems that are difficult to solve although no obvious barriers exist. This is another demonstration of the fruitful links machine learning has with different areas in mathematics.

Related papers

• Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem [26.292576184028924]
  This work continues to investigate the link between differentially private (DP) and online learning. We show that for general classification tasks, DP learnability implies online learnability.
  arXiv  Detail & Related papers  (2024-07-10T15:43:30Z)
• Beyond Prototypes: Semantic Anchor Regularization for Better Representation Learning [82.29761875805369]
  One of the ultimate goals of representation learning is to achieve compactness within a class and well-separability between classes. We propose a novel perspective to use pre-defined class anchors serving as feature centroid to unidirectionally guide feature learning. The proposed Semantic Anchor Regularization (SAR) can be used in a plug-and-play manner in the existing models.
  arXiv  Detail & Related papers  (2023-12-19T05:52:38Z)
• 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)
• 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)
• 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 List Learnability [15.368858716555888]
  We consider list PAC learning where the goal is to output a list of $k$ predictions. Generalizing the recent characterization of multiclass learnability, we show that a hypothesis class is $k$-list learnable if and only if the $k$-DS dimension is finite.
  arXiv  Detail & Related papers  (2022-11-07T21:28:05Z)
• Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes [31.2676304636432]
  We study the problem of multiclass classification with a bounded number of different labels $k$, in the realizable setting. We extend the traditional PAC model to a) distribution-dependent learning rates, and b) learning rates under data-dependent assumptions.
  arXiv  Detail & Related papers  (2022-10-05T14:36:27Z)
• Few-Shot Object Detection via Association and DIscrimination [83.8472428718097]
  Few-shot object detection via Association and DIscrimination builds up a discriminative feature space for each novel class with two integral steps. Experiments on Pascal VOC and MS-COCO datasets demonstrate FADI achieves new SOTA performance, significantly improving the baseline in any shot/split by +18.7.
  arXiv  Detail & Related papers  (2021-11-23T05:04:06Z)
• Multiclass versus Binary Differentially Private PAC Learning [32.22526322514124]
  We show a generic reduction from multiclass differentially private PAC learning to binary private PAC learning. Our proof extends the notion of $Psi$-dimension defined in work of Ben-David et al. [JCSS '95] to the online setting and explores its general properties.
  arXiv  Detail & Related papers  (2021-07-22T18:06:39Z)
• A Theory of PAC Learnability of Partial Concept Classes [30.772106555607458]
  We extend the theory of PAC learning in a way which allows to model a rich variety of learning tasks. We characterize PAC learnability of partial concept classes and reveal an algorithmic landscape which is fundamentally different from the classical one.
  arXiv  Detail & Related papers  (2021-07-18T13:29:26Z)
• 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)

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.