The VC-Dimension of K-Vertex D-Polytopes
The VC-Dimension of K-Vertex D-Polytopes
复制标题
K 顶点 D 多面体的 VC 维数
DOI：
10.1007/s00493-020-4475-4
复制
发表时间：
2020
期刊：
影响因子：
1.1
通讯作者：
A. Kupavskii
中科院分区：
文献类型：
--
作者：
A. Kupavskii
本文证明了Rd中k-顶点多面体类的VC-维数至多为8d 2klog 2k，回答了Long和Warranty的一个老问题.我们还表明，它至少是1/3 kd。
In this short note, we show that the VC-dimension of the class of k-vertex polytopes in Rd is at most 8d2k log2k, answering an old question of Long and Warmuth. We also show that it is at least 1/3kd.