Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes

• URL: http://arxiv.org/abs/2210.02297v2
• Date: Fri, 7 Oct 2022 14:01:01 GMT
• Title: Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes
• Authors: Alkis Kalavasis, Grigoris Velegkas, Amin Karbasi
• Abstract summary: 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.
• Score: 31.2676304636432
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper 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. First, we consider the universal learning setting (Bousquet, Hanneke, Moran, van Handel and Yehudayoff, STOC '21), for which we provide a complete characterization of the achievable learning rates that holds for every fixed distribution. In particular, we show the following trichotomy: for any concept class, the optimal learning rate is either exponential, linear or arbitrarily slow. Additionally, we provide complexity measures of the underlying hypothesis class that characterize when these rates occur. Second, we consider the problem of multiclass classification with structured data (such as data lying on a low dimensional manifold or satisfying margin conditions), a setting which is captured by partial concept classes (Alon, Hanneke, Holzman and Moran, FOCS '21). Partial concepts are functions that can be undefined in certain parts of the input space. We extend the traditional PAC learnability of total concept classes to partial concept classes in the multiclass setting and investigate differences between partial and total concepts.

Related papers

• Composing Novel Classes: A Concept-Driven Approach to Generalized Category Discovery [13.68907640197364]
  We tackle the generalized category discovery problem, which aims to discover novel classes in unlabeled datasets. We introduce a novel concept learning framework for GCD, named ConceptGCD, that categorizes concepts into two types: derivable and underivable. Our framework first extracts known class concepts by a known class pre-trained model and then produces derivable concepts from them.
  arXiv  Detail & Related papers  (2024-10-17T07:30:20Z)
• Neural Collapse Terminus: A Unified Solution for Class Incremental Learning and Its Variants [166.916517335816]
  In this paper, we offer a unified solution to the misalignment dilemma in the three tasks. We propose neural collapse terminus that is a fixed structure with the maximal equiangular inter-class separation for the whole label space. Our method holds the neural collapse optimality in an incremental fashion regardless of data imbalance or data scarcity.
  arXiv  Detail & Related papers  (2023-08-03T13:09:59Z)
• 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)
• Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
  We study two basic statistical tasks in non-interactive local differential privacy (LDP): learning and refutation. Our main result is a complete characterization of the sample complexity of PAC learning for non-interactive LDP protocols.
  arXiv  Detail & Related papers  (2022-10-26T03:19:24Z)
• Learning What Not to Segment: A New Perspective on Few-Shot Segmentation [63.910211095033596]
  Recently few-shot segmentation (FSS) has been extensively developed. This paper proposes a fresh and straightforward insight to alleviate the problem. In light of the unique nature of the proposed approach, we also extend it to a more realistic but challenging setting.
  arXiv  Detail & Related papers  (2022-03-15T03:08:27Z)
• 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)
• 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)
• 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)
• Partial Is Better Than All: Revisiting Fine-tuning Strategy for Few-shot Learning [76.98364915566292]
  A common practice is to train a model on the base set first and then transfer to novel classes through fine-tuning. We propose to transfer partial knowledge by freezing or fine-tuning particular layer(s) in the base model. We conduct extensive experiments on CUB and mini-ImageNet to demonstrate the effectiveness of our proposed method.
  arXiv  Detail & Related papers  (2021-02-08T03:27:05Z)
• CURI: A Benchmark for Productive Concept Learning Under Uncertainty [33.83721664338612]
  We introduce a new few-shot, meta-learning benchmark, Compositional Reasoning Under Uncertainty (CURI) CURI evaluates different aspects of productive and systematic generalization, including abstract understandings of disentangling, productive generalization, learning operations, variable binding, etc. It also defines a model-independent "compositionality gap" to evaluate the difficulty of generalizing out-of-distribution along each of these axes.
  arXiv  Detail & Related papers  (2020-10-06T16:23:17Z)
• Federated Learning with Only Positive Labels [71.63836379169315]
  We propose a generic framework for training with only positive labels, namely Federated Averaging with Spreadout (FedAwS) We show, both theoretically and empirically, that FedAwS can almost match the performance of conventional learning where users have access to negative labels.
  arXiv  Detail & Related papers  (2020-04-21T23:35:02Z)

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.