Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.23561 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908930039349248 |
|---|---|
| author | Liu, Jiahua Li, Benchong |
| author_facet | Liu, Jiahua Li, Benchong |
| contents | In the realm of machine learning theory, to prevent unnatural coding schemes between teacher and learner, No-Clash Teaching Dimension was introduced as provably optimal complexity measure for collusion-free teaching. However, whether No-Clash Teaching Dimension is upper-bounded by Vapnik-Chervonenkis dimension remains unknown. In this paper, for any finite concept class, we construct fragments of size equals to its Vapnik-Chervonenkis dimension which identify concepts through an ordered compression scheme. Naturally, these fragments are used as teaching sets, one can easily see that they satisfy the non-clashing condition, i.e., this open question is resolved for finite concept classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_23561 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The No-Clash Teaching Dimension is Bounded by VC Dimension Liu, Jiahua Li, Benchong Information Theory Machine Learning In the realm of machine learning theory, to prevent unnatural coding schemes between teacher and learner, No-Clash Teaching Dimension was introduced as provably optimal complexity measure for collusion-free teaching. However, whether No-Clash Teaching Dimension is upper-bounded by Vapnik-Chervonenkis dimension remains unknown. In this paper, for any finite concept class, we construct fragments of size equals to its Vapnik-Chervonenkis dimension which identify concepts through an ordered compression scheme. Naturally, these fragments are used as teaching sets, one can easily see that they satisfy the non-clashing condition, i.e., this open question is resolved for finite concept classes. |
| title | The No-Clash Teaching Dimension is Bounded by VC Dimension |
| topic | Information Theory Machine Learning |
| url | https://arxiv.org/abs/2603.23561 |