Relating Data Compression and Learnability

By Nick Littlestone, Manfred K. Warmuth. 2003

319 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/0df167e42f204cd6effcc6a7b423e7435f407290

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Empirical Bernstein Bounds and Sample-Variance Penalization (2009, methodology): “The idea of sample compression schemes [6] is to train the algorithm on subsamples of the training data and to use the remaining data points for testing.”
The Set Covering Machine (2003, background): “The analysis, however, can be made by extending an older result due to Littlestone and Warmuth (1986).”
An Overview of Machine Teaching (2018, background): “One reason why this question is of interest to a wider audience within the computational learning theory community is that it appears to be related to the sample compression conjecture, which has been open for 30 years and which states that every concept class C has a “sample compression scheme” in ”
PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification (2003, unknown): “18), which is based on the results in (Littlestone and Warmuth, 1986).”
The Decision List Machine (2002, methodology): “To investigate if it is worthwhile to consider larger classes of functions than just the conjunctions and disjunctions that are used in the SCM, we focus here on the class of decision lists introduced by Rivest (1987) because this class strictly includes both conjunctions and disjunctions and is str”
Chaining Mutual Information and Tightening Generalization Bounds (2018, background): “Generalization bounds have evolved throughout the years, starting from the basic union bound over the hypothesis set, the refined union bound, Rademacher complexity, chaining and VC-dimension [3], [4]; and algorithm-dependent bounds such as PAC-Bayesian bounds [5], uniform stability [6], compression”
Kernel Matching Pursuit (2002, background): “This implies that current theoretical results on generalization bounds that are derived for sparse SVM or Perceptron solutions (Vapnik, 1995; Vapnik, 1998; Littlestone and Warmuth, 1986; Floyd and Warmuth, 1995; Graepel et al., 2000) cannot be readily applied to KMP.”
Adaptive Learning with Robust Generalization Guarantees (2016, methodology): “Note that this definition of variable-length compression scheme (where the number of examples output by the compression algorithm depends on the input sample size) is more general than the one defined in Littlestone and Warmuth (1986).”
Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes (2018, background): “In binary classification, the combinatorial notion of Littlestone-Warmuth compression has been shown to be sufficient [15] and necessary [18] for learning.”
Recursive teaching dimension, VC-dimension and sample compression (2014, methodology): “This way sample bounds for PAC-learning of a class C can be obtained from the size of a smallest sample compression scheme for C (Littlestone and Warmuth, 1996; Floyd and Warmuth, 1995).”
Learning on the border: active learning in imbalanced data classification (2007, background): “This can be achieved by keeping the number of support vectors as low as possible (Littlestone and Warmuth, 1986) or by searching decision boundaries that separate the examples with the largest margin (Vapnik and Lerner, 1963; Vapnik, 1998).”
Fast Kernel Classifiers with Online and Active Learning (2005, background): “This can be achieved by keeping the number of support vectors as low as possible (Littlestone and Warmuth, 1986) or by searching decision boundaries that separate the examples with the largest margin (Vapnik and Lerner, 1963; Vapnik, 1998).”
Bayesian Gaussian process models : PAC-Bayesian generalisation error bounds and sparse approximations (2003, background): “18 in [72] which in turn is based on results in [103].”