Back to Search Start Over

Littlestone and VC-dimension of families of zero sets

Authors :
Guingona, Vincent
Kolesnikov, Alexei
Nierwinski, Julie
Soucy, Richard
Publication Year :
2021

Abstract

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$.<br />Comment: 18 pages

Subjects

Subjects :
Mathematics - Logic

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2109.04805
Document Type :
Working Paper