The VC-Dimension of K -Vertex D -Polytopes
- PDF / 322,291 Bytes
- 6 Pages / 442.205 x 665.008 pts Page_size
- 101 Downloads / 159 Views
Bolyai Society – Springer-Verlag
Combinatorica 6pp. DOI: 10.1007/s00493-020-4475-4
THE VC-DIMENSION OF K-VERTEX D-POLYTOPES ANDREY KUPAVSKII∗ Received May 14, 2020 Revised August 25, 2020 In this short note, we show that the VC-dimension of the class of k-vertex polytopes in Rd is at most 8d2 k log2 k, answering an old question of Long and Warmuth. We also show that it is at least 13 kd.
Let 2X stand for the power set of X. Let F ⊂ 2X be a collection of subsets of a set X. In computational geometry, a pair (X, F) is called a range space. In learning theory, the sets from R are called concepts and R is called a concept class. We say that a set Y ⊂ X is shattered by F if for any Y 0 ⊂ Y there is F 0 ∈ F such that F 0 ∩ Y = F 0 . The VC-dimension of a collection of sets is the size of the largest shattered subset Y of X. It was defined in a seminal paper of Vapnik and Chervonenkis [8]. The VC-dimension is one of the fundamental complexity characteristics of a collection of sets and has numerous applications across different branches of mathematics, such as combinatorics, graph theory, computational geometry, learning theory, model theory etc. It is typical to consider set systems, induced on a set X of all points in some space by all objects from a certain geometrically defined class. We shall omit X from the notation when it is clear from the context. One crucial example is the class of all half-spaces in Rd . The VC-dimension of this class is d+1, a statement that is essentially equivalent to the classical theorem of Radon in convex geometry (see [4]). To extend this to polytopes, we need one general result of Blumer, Ehrenfeucht, Haussler and Warmuth [1]. Mathematics Subject Classification (2010): 52B05; 52B55 The author acknowledges the financial support from the Ministry of Education and Science of the Russian Federation in the framework of MegaGrant no 075-15-2019-1926. ∗
2
ANDREY KUPAVSKII
Theorem 1 ([1]). Let R ⊂ 2X be a collection of sets of VC-dimension t. Let R∩k be the collection of all sets that can be obtained as intersections of at most k sets from R. Then the VC-dimension of R∩k is O(tk log k). Using this theorem and Radon’s theorem, we conclude that the VCdimension of the class of all polytopes in Rd with at most k faces is O(dk log k). In the paper [2], Csik´ os, Mustafa and the author showed that this bound is tight up to a constant factor for any d ≥ 4. We refer to [2] for more background on the topic. Surprisingly, very little is known about the dual (in the geometric sense) class of polytopes in Rd with at most k vertices. The famous Upper Bound Theorem (see [4]) implies that a polytope with k vertices can have at most O(k bd/2c ) faces, which gives an upper bound of roughly d2 k d/2 on the VCdimension of this class. Long and Warmuth [3] asked 30 years ago whether the VC-dimension of this class is polynomial in d. In this note, we answer this question in the positive. Theorem 2. The VC-dimension of the class of polytopes with at most k vertices in Rd is at most 8d2 k log2 k. Proof. Assume
Data Loading...
