# Littlestone and VC-dimension of families of zero sets

@inproceedings{Guingona2021LittlestoneAV, title={Littlestone and VC-dimension of families of zero sets}, author={Vincent Guingona and Alexei D. Kolesnikov and Julie Nierwinski and Richard Soucy}, year={2021} }

We prove that, for any d linearly independent functions from some set into a d-dimensional vector space over any field, the family of zero sets of all non-trivial linear combination of these functions has VC-dimension and Littlestone dimension d−1. Additionally, we characterize when such families are maximal of VC-dimension d − 1 and give a sufficient condition for when they are maximal of Littlestone dimension d− 1.

#### References

SHOWING 1-7 OF 7 REFERENCES

Some new maximum VC classes

- Mathematics, Computer Science
- Inf. Process. Lett.
- 2014

It is shown that Floyd's lemma applies to a wider class of linearly parameterized functions than has been formally recognized to date and, modulo some minor technicalities, the sets of positivity for any linear combination of real analytic functions is maximum on points in general position. Expand

THICKET DENSITY

- Computer Science, Mathematics
- The Journal of Symbolic Logic
- 2021

A new type of “shatter function” for set systems that satisfies a Sauer–Shelah type dichotomy, but whose polynomial-growth case is governed by Shelah’s two-rank instead of VC dimension is defined. Expand

MODEL THEORY AND COMBINATORICS OF BANNED SEQUENCES

- Mathematics
- 2018

We set up a general context in which one can prove Sauer-Shelah type lemmas. We apply our general results to answer a question of Bhaskar and give a slight improvement to a result of Malliaris and… Expand

Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition

- Mathematics, Computer Science
- IEEE Trans. Electron. Comput.
- 1965

It is shown that a family of surfaces having d degrees of freedom has a natural separating capacity of 2d pattern vectors, thus extending and unifying results of Winder and others on the pattern-separating capacity of hyperplanes. Expand

Balls in Rk do not cut all subsets of k + 2 points

- Mathematics
- 1979

Abstract For any set E cf k + 2 points in k k, k = 1, 2,…, not all subsets of E are of the form B ∩ E where E is a ball.

Space-bounded learning and the Vapnik-Chervonenkis dimension

- Mathematics, Computer Science
- COLT '89
- 1989

This paper explores algorithms that learn a concept from a concept class of Vapnik-Chervonenkis (VC) dimension d by saving at most d examples at a time. The framework is the model of learning… Expand

MODEL THEORY AND MACHINE LEARNING

- Mathematics, Computer Science
- The Bulletin of Symbolic Logic
- 2019

A new and similar connection between model theory and machine learning is pointed out, this time developing a correspondence between stability and learnability in various settings of online learning. Expand