Variants of VC dimension and their applications to dynamics
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912306051416064 |
|---|---|
| author | Gao, Guorong Ma, Jie Rong, Mingyuan Tran, Tuan |
| author_facet | Gao, Guorong Ma, Jie Rong, Mingyuan Tran, Tuan |
| contents | Since its introduction by Vapnik and Chervonenkis in the 1960s, the VC dimension and its variants have played a central role in numerous fields. In this paper, we investigate several variants of the VC dimension and their applications to dynamical systems. First, we prove a new bound for a recently introduced generalization of VC dimension, which unifies and extends various extremal results on the VC, Natarajan, and Steele dimensions. This new bound allows us to strengthen one of the main theorems of Huang and Ye [Adv. Math., 2009] in dynamical systems. Second, we refine a key lemma of Huang and Ye related to a variant of VC dimension by providing a more concise and conceptual proof. We also highlight a surprising connection among this result, combinatorics, dynamical systems, and recent advances in communication complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_05353 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Variants of VC dimension and their applications to dynamics Gao, Guorong Ma, Jie Rong, Mingyuan Tran, Tuan Combinatorics Computational Complexity Dynamical Systems Since its introduction by Vapnik and Chervonenkis in the 1960s, the VC dimension and its variants have played a central role in numerous fields. In this paper, we investigate several variants of the VC dimension and their applications to dynamical systems. First, we prove a new bound for a recently introduced generalization of VC dimension, which unifies and extends various extremal results on the VC, Natarajan, and Steele dimensions. This new bound allows us to strengthen one of the main theorems of Huang and Ye [Adv. Math., 2009] in dynamical systems. Second, we refine a key lemma of Huang and Ye related to a variant of VC dimension by providing a more concise and conceptual proof. We also highlight a surprising connection among this result, combinatorics, dynamical systems, and recent advances in communication complexity. |
| title | Variants of VC dimension and their applications to dynamics |
| topic | Combinatorics Computational Complexity Dynamical Systems |
| url | https://arxiv.org/abs/2310.05353 |