A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimension

• URL: http://arxiv.org/abs/2212.12631v2
• Date: Wed, 28 Dec 2022 02:25:41 GMT
• Title: A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimension
• Abstract summary: This paper presents a construction of a proper and stable labelled sample compression scheme of size $O(VCD2)$ for any finite concept class.
• Score: 6.522952386973185
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper presents a construction of a proper and stable labelled sample compression scheme of size $O(\VCD^2)$ for any finite concept class, where $\VCD$ denotes the Vapnik-Chervonenkis Dimension. The construction is based on a well-known model of machine teaching, referred to as recursive teaching dimension. This substantially improves on the currently best known bound on the size of sample compression schemes (due to Moran and Yehudayoff), which is exponential in $\VCD$. The long-standing open question whether the smallest size of a sample compression scheme is in $O(\VCD)$ remains unresolved, but our results show that research on machine teaching is a promising avenue for the study of this open problem. As further evidence of the strong connections between machine teaching and sample compression, we prove that the model of no-clash teaching, introduced by Kirkpatrick et al., can be used to define a non-trivial lower bound on the size of stable sample compression schemes.

Related papers

• 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)
• Activations and Gradients Compression for Model-Parallel Training [85.99744701008802]
  We study how simultaneous compression of activations and gradients in model-parallel distributed training setup affects convergence. We find that gradients require milder compression rates than activations. Experiments also show that models trained with TopK perform well only when compression is also applied during inference.
  arXiv  Detail & Related papers  (2024-01-15T15:54:54Z)
• 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)
• 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)
• Unrolled Compressed Blind-Deconvolution [77.88847247301682]
  sparse multichannel blind deconvolution (S-MBD) arises frequently in many engineering applications such as radar/sonar/ultrasound imaging. We propose a compression method that enables blind recovery from much fewer measurements with respect to the full received signal in time.
  arXiv  Detail & Related papers  (2022-09-28T15:16:58Z)
• L$_0$onie: Compressing COINs with L$_0$-constraints [0.4568777157687961]
  Implicit Neural Representations (INR) have motivated research on domain-agnostic compression techniques. We propose a sparsity-constrained extension of the COIN compression method.
  arXiv  Detail & Related papers  (2022-07-08T22:24:56Z)
• Estimating the Resize Parameter in End-to-end Learned Image Compression [50.20567320015102]
  We describe a search-free resizing framework that can further improve the rate-distortion tradeoff of recent learned image compression models. Our results show that our new resizing parameter estimation framework can provide Bjontegaard-Delta rate (BD-rate) improvement of about 10% against leading perceptual quality engines.
  arXiv  Detail & Related papers  (2022-04-26T01:35:02Z)
• Labeled sample compression schemes for complexes of oriented matroids [0.04297070083645048]
  We show that the topes of a complex of oriented matroids (abbreviated COM) of VC-dimension $d$ admit a proper labeled sample compression scheme of size $d$. This is a step towards the sample compression conjecture -- one of the oldest open problems in computational learning theory.
  arXiv  Detail & Related papers  (2021-10-28T14:42:55Z)
• 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)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator) We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$. We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
  arXiv  Detail & Related papers  (2020-05-26T17:53:18Z)
• 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)
• On Biased Compression for Distributed Learning [55.89300593805943]
  We show for the first time that biased compressors can lead to linear convergence rates both in the single node and distributed settings. We propose several new biased compressors with promising theoretical guarantees and practical performance.
  arXiv  Detail & Related papers  (2020-02-27T19:52:24Z)

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.