Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes

• URL: http://arxiv.org/abs/2210.05455v1
• Date: Tue, 11 Oct 2022 13:54:41 GMT
• Title: Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes
• Abstract summary: 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$.
• Score: 16.684376456880642
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The sample compressibility of concept classes plays an important role in learning theory, as a sufficient condition for PAC learnability, and more recently as an avenue for robust generalisation in adaptive data analysis. Whether compression schemes of size $O(d)$ must necessarily exist for all classes of VC dimension $d$ is unknown, but conjectured to be true by Warmuth. Recently Chalopin, Chepoi, Moran, and Warmuth (2018) gave a beautiful unlabelled sample compression scheme of size VC dimension for all maximum classes: classes that meet the Sauer-Shelah-Perles Lemma with equality. They also offered a counterexample to compression schemes based on a promising approach known as corner peeling. In this paper we simplify and extend their proof technique to deal with so-called extremal classes of VC dimension $d$ which contain maximum classes of VC dimension $d-1$. A criterion is given which would imply that all extremal classes admit unlabelled compression schemes of size $d$. We also prove that all intersection-closed classes with VC dimension $d$ admit unlabelled compression schemes of size at most $11d$.

Related papers

• PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting [46.089126569274676]
  We study the problem of multiclass PAC learning with bandit feedback in the realizable setting.<n>In this framework, there is an unknown data distribution over an instance space $mathcalX$ and a label space $mathcalY$.<n>We provide a general characterization of the optimal sample of this problem, sharp for every concept class up to complexity.
  arXiv  Detail & Related papers  (2026-05-25T10:35:16Z)
• Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale [54.65053906803857]
  We study the optimal scale at which real-valued function classes exhibit uniform convergence and learnability.<n>Our main result establishes a scale-sensitive generalization of the fundamental theorem of PAC learning.<n>We also highlight several open questions on quantitative sample complexity and evaluability.
  arXiv  Detail & Related papers  (2026-05-13T15:41:30Z)
• An Optimal Sauer Lemma Over $k$-ary Alphabets [46.089126569274676]
  We show that the Sauer-Shelah-Perles Lemma bounds are suboptimal for alphabet sizes $k>2$.<n>Our bound is tight for every size $k$, list size $ell$, and dimension value, replacing the exponential dependence on $ell$ in the Natarajan-based bound.<n>In contrast to the classical case, we are not aware of any purely proof in the DS setting.
  arXiv  Detail & Related papers  (2026-04-14T16:50:38Z)
• 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)
• Sample Compression Scheme Reductions [17.389446817000945]
  We present novel reductions from sample compression schemes in multiclass classification, regression, and adversarially robust learning settings. We establish similar results for adversarially robust learning and also provide an example of a concept class that is robustly learnable but has no bounded-size compression scheme.
  arXiv  Detail & Related papers  (2024-10-16T20:14:02Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• A Theory of Interpretable Approximations [61.90216959710842]
  We study the idea of approximating a target concept $c$ by a small aggregation of concepts from some base class $mathcalH$. For any given pair of $mathcalH$ and $c$, exactly one of these cases holds: (i) $c$ cannot be approximated by $mathcalH$ with arbitrary accuracy. We show that, in the case of interpretable approximations, even a slightly nontrivial a-priori guarantee on the complexity of approximations implies approximations with constant (distribution-free and accuracy-
  arXiv  Detail & Related papers  (2024-06-15T06:43:45Z)
• 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)
• The Real Price of Bandit Information in Multiclass Classification [73.17969992976501]
  We revisit the classical problem of multiclass classification with bandit feedback. We present a new bandit classification algorithm that guarantees regret $smashwidetildeO(|H|+sqrtT)$.
  arXiv  Detail & Related papers  (2024-05-16T12:11:09Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Multiclass Learnability Does Not Imply Sample Compression [5.257719744958368]
  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.
  arXiv  Detail & Related papers  (2023-08-12T00:26:08Z)
• Improving Zero-Shot Generalization for CLIP with Synthesized Prompts [135.4317555866831]
  Most existing methods require labeled data for all classes, which may not hold in real-world applications. We propose a plug-and-play generative approach called textbfSynttextbfHestextbfIzed textbfPrompts(textbfSHIP) to improve existing fine-tuning methods.
  arXiv  Detail & Related papers  (2023-07-14T15:15:45Z)
• Uniform-PAC Guarantees for Model-Based RL with Bounded Eluder Dimension [86.3584476711976]
  We propose algorithms for both nonlinear bandits and model-based episodic RL using the general function class with a bounded eluder. The achieved uniform-PAC sample complexity is tight in the sense that it matches the state-of-the-art regret bounds or sample complexity guarantees when reduced to the linear case.
  arXiv  Detail & Related papers  (2023-05-15T05:07:45Z)
• 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)
• Optimally compressing VC classes [0.0]
  Resolving a conjecture of Littlestone and Warmuth, we show that any concept class of VC-dimension $d$ has a sample compression scheme of size $d$.
  arXiv  Detail & Related papers  (2022-01-11T18:56:08Z)
• Eluder Dimension and Generalized Rank [48.27338656415236]
  We show that eluder dimension can be exponentially larger than $sigma$-rank. When $sigma$ is the $mathrmrelu$ activation, we show that eluder dimension can be exponentially larger than $sigma$-rank.
  arXiv  Detail & Related papers  (2021-04-14T16:53:13Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)

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.