Applications of Littlestone dimension to query learning and to compression

Hunter Chase, James Freitag, Lev Reyzin
10/7/2023
cs.LGmath.LO

No confident code implementation found for this paper.

Abstract

In this paper we give several applications of Littlestone dimension. The first is to the model of \cite{angluin2017power}, where we extend their results for learning by equivalence queries with random counterexamples. Second, we extend that model to infinite concept classes with an additional source of randomness. Third, we give improved results on the relationship of Littlestone dimension to classes with extended $d$-compression schemes, proving a strong version of a conjecture of \cite{floyd1995sample} for Littlestone dimension.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Effective Littlestone Dimension

83% match2024

Sample Compression Scheme Reductions

78% match2024

Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem

78% match2024

On Reductions and Representations of Learning Problems in Euclidean Spaces

77% match2024

Bottleneck Structure in Learned Features: Low-Dimension vs Regularity Tradeoff

76% match2023

Improved Hardness Results for Learning Intersections of Halfspaces

76% match2024

Cite this paper

@article{chase2023applications,
  title  = {Applications of Littlestone dimension to query learning and to compression},
  author = {Hunter Chase and James Freitag and Lev Reyzin},
  year   = {2023},
  eprint = {2310.04812},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2310.04812v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2310.04812.svg)](https://codeofpaper.com/paper/2310.04812)

Discussion