Multiclass Learnability Does Not Imply Sample Compression

• URL: http://arxiv.org/abs/2308.06424v2
• Date: Wed, 20 Sep 2023 20:51:51 GMT
• Title: Multiclass Learnability Does Not Imply Sample Compression
• Abstract summary: A hypothesis class admits a sample compression scheme, if for every sample labeled by a hypothesis from the class, it is possible to retain only a small subsample. We show that the analogous statement pertaining to sample compression is not true for multiclass hypothesis classes.
• Score: 5.257719744958368
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A hypothesis class admits a sample compression scheme, if for every sample labeled by a hypothesis from the class, it is possible to retain only a small subsample, using which the labels on the entire sample can be inferred. The size of the compression scheme is an upper bound on the size of the subsample produced. Every learnable binary hypothesis class (which must necessarily have finite VC dimension) admits a sample compression scheme of size only a finite function of its VC dimension, independent of the sample size. For multiclass hypothesis classes, the analog of VC dimension is the DS dimension. We show that the analogous statement pertaining to sample compression is not true for multiclass hypothesis classes: every learnable multiclass hypothesis class, which must necessarily have finite DS dimension, does not admit a sample compression scheme of size only a finite function of its DS dimension.

Related papers

• Strategic PAC Learnability via Geometric Definability [69.34283267701421]
  Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision.<n>A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations.<n>We introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over $mathbbR_mathttexp$.<n>We prove that learnability is preserved, with sample complexity controlled by the complexity
  arXiv  Detail & Related papers  (2026-05-13T12:21:56Z)
• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
  We show that multiclass PAC sample complexity is governed by two distinct dimensions.<n>Unlike binary or online classification, multiclass learning inherently involves two structural parameters.<n>A key ingredient is a novel online procedure based on a self-adaptive multiplicative-weights algorithm performing a label-space reduction.
  arXiv  Detail & Related papers  (2025-11-16T15:47:47Z)
• Dual VC Dimension Obstructs Sample Compression by Embeddings [25.63430474763066]
  This work studies embedding of arbitrary VC classes in well-behaved VC classes, focusing particularly on extremal classes. We prove that for every $d$ there is a class with VC dimension $d$ that cannot be embedded in any extremal class of VC dimension smaller than exponential in $d$. This result has an important implication in learning theory, as it reveals a fundamental limitation of one of the most extensively studied approaches to tackling the long-standing sample compression conjecture.
  arXiv  Detail & Related papers  (2024-05-27T12:38:25Z)
• 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)
• A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimension [6.522952386973185]
  This paper presents a construction of a proper and stable labelled sample compression scheme of size $O(VCD2)$ for any finite concept class.
  arXiv  Detail & Related papers  (2022-12-24T01:56:02Z)
• Differentially-Private Bayes Consistency [70.92545332158217]
  We construct a Bayes consistent learning rule that satisfies differential privacy (DP) We prove that any VC class can be privately learned in a semi-supervised setting with a near-optimal sample complexity.
  arXiv  Detail & Related papers  (2022-12-08T11:57:30Z)
• Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes [5.194264506657145]
  We introduce comparative learning as a combination of the realizable and agnostic settings in PAC learning. Even when both $S$ and $B$ have infinite VC dimensions, comparative learning can still have a small sample complexity. We show that the sample complexity of comparative learning is characterized by the mutual VC dimension $mathsfVC(S,B)$.
  arXiv  Detail & Related papers  (2022-11-16T18:38:24Z)
• Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes [16.684376456880642]
  We show that all classes of VC dimension $d$ admit unlabelled compression schemes of size $O(d)$. We also prove that all intersection-closed classes with VC dimension $d$ admit unlabelled compression schemes of size at most $11d$.
  arXiv  Detail & Related papers  (2022-10-11T13:54:41Z)
• Intrinsic Dimension Estimation [92.87600241234344]
  We introduce a new estimator of the intrinsic dimension and provide finite sample, non-asymptotic guarantees. We then apply our techniques to get new sample complexity bounds for Generative Adversarial Networks (GANs) depending on the intrinsic dimension of the data.
  arXiv  Detail & Related papers  (2021-06-08T00:05:39Z)
• 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)
• Rethinking preventing class-collapsing in metric learning with margin-based losses [81.22825616879936]
  Metric learning seeks embeddings where visually similar instances are close and dissimilar instances are apart. margin-based losses tend to project all samples of a class onto a single point in the embedding space. We propose a simple modification to the embedding losses such that each sample selects its nearest same-class counterpart in a batch.
  arXiv  Detail & Related papers  (2020-06-09T09:59:25Z)
• Compressing Large Sample Data for Discriminant Analysis [78.12073412066698]
  We consider the computational issues due to large sample size within the discriminant analysis framework. We propose a new compression approach for reducing the number of training samples for linear and quadratic discriminant analysis.
  arXiv  Detail & Related papers  (2020-05-08T05:09:08Z)
• Agnostic Sample Compression Schemes for Regression [30.539063844697772]
  We show that for every other $ell_p$ loss, $pin (1,infty)$, there does not exist an exact compression scheme of bounded size. For $ell$ loss, does every function class admit an approximate compression scheme of size in the fat-shattering dimension?
  arXiv  Detail & Related papers  (2018-10-03T11:46: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.