The VC-dimension of K-vertex D-polytopes

DOI10.1007/S00493-020-4475-4MaRDI QIDQ2663418zbMATH OpenOpenAlexFDO

Authors Andrey B. Kupavskii

Publication date 16 April 2021

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.04841

zbMATH Keywords

old question of Long and WarmuthpolytopesRadon's theoremsign patternVC-dimension

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computational aspects related to convexity (52B55)

Abstract: In this short note, we show that the VC-dimension of the class of $k$-vertex polytopes in $mathbb{R}^d$ is at most $8d^{2}klo{g}_{2}k$, answering an old question of Long and Warmuth.

Review text

A range space \((X,\mathcal{F})\) is a pair of a set \(X\) and a collection of subsets \(\mathcal{F}\) of \(X\). A set \(Y\subset X\) is shattered by \(\mathcal{F}\) if for any \(Z\subset Y\) there is \(F'\in \mathcal{F}\) such that \(F'\cap Z = F'\). The \(VC\)-dimension of a collection of sets is the size of the largest shattered subset \(Y\) of \(X\). \par The author proves that the VC-dimension of the class of \(k\)-vertex polytopes in \(\mathbb{R}^d\) is \par (1) at most \(8d^2 k \log_2 k\), and \par (2) at least \(\frac{1}{3} kd\). \par Statement (1) answers an old question of \textit{P. M. Long} and \textit{M. K. Warmuth} [Inf. Comput. 113, No. 2, 230--252 (1994; Zbl 0821.68102)].

Recommendations

• VC dimension and a union theorem for set systems
• Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
• The VC-dimension of Sperner systems
• The VC dimension of k‐uniform random hypergraphs
• The Vapnik-Chervonenkis dimension of a random graph

Cites work

• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 3053541 (Why is no real title available?)
• Learnability and the Vapnik-Chervonenkis dimension
• On the Betti Numbers of Real Varieties
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Tight lower bounds on the VC-dimension of geometric set systems

Cited in

(6)

• Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
• Active-learning a convex body in low dimensions
• The VC-dimension of axis-parallel boxes on the torus
• On the VC-dimension of half-spaces with respect to convex sets
• The VC dimension of k‐uniform random hypergraphs
• Online geometric hitting set using points in \(\mathbb{Z}^d\)

This page was built for publication: The VC-dimension of K-vertex D-polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2663418)