This article is cited in
4 papers
Sign rank versus Vapnik-Chervonenkis dimension
N. Alonabc,
Sh. Morandbe,
A. Yehudayofff a Sackler School of Mathematics and Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv, Israel
b Microsoft Research, Herzliya, Israel
c School of Mathematics, Institute for Advanced Study, Princeton,
NJ, USA
d Department of Computer Science, Technion – Israel Institute of Technology, Haifa, Israel
e Max Planck Institute for Informatics, Saarbrücken, Germany
f Department of Mathematics, Technion – Israel Institute of Technology, Haifa, Israel
Abstract:
This work studies the maximum possible sign rank of sign
$(N \times N)$-matrices with a given Vapnik-Chervonenkis dimension
$d$. For
$d=1$, this maximum is three. For
$d=2$, this maximum is
$\widetilde{\Theta}(N^{1/2})$. For
$d >2$, similar but slightly less accurate statements hold. The lower bounds improve on previous ones by Ben-David et al., and the upper bounds are novel.
The lower bounds are obtained by probabilistic constructions, using a theorem of Warren in real algebraic topology. The upper bounds are obtained using a result of Welzl about spanning trees with low stabbing number, and using the moment curve.
The upper bound technique is also used to: (i) provide estimates on the number of classes of a given Vapnik-Chervonenkis dimension, and the number of maximum classes of a given Vapnik-Chervonenkis dimension—answering a question of Frankl from 1989, and (ii) design an efficient algorithm that provides an
$O(N/\log(N))$ multiplicative approximation for the sign rank.
We also observe a general connection between sign rank and spectral gaps which is based on Forster's argument. Consider the adjacency
$(N \times N)$-matrix of a
$\Delta$-regular graph with a second eigenvalue of absolute value
$\lambda$ and
$\Delta \leq N/2$. We show that the sign rank of the signed version of this matrix is at least
$\Delta/\lambda$. We use this connection to prove the existence of a maximum class
$C\subseteq\{\pm 1\}^N$ with Vapnik-Chervonenkis dimension
$2$ and sign rank
$\widetilde{\Theta}(N^{1/2})$. This answers a question of Ben-David et al. regarding the sign rank of large Vapnik-Chervonenkis classes. We also describe limitations of this approach, in the spirit of the Alon-Boppana theorem.
We further describe connections to communication complexity, geometry, learning theory, and combinatorics.
Bibliography: 69 titles.
Keywords:
VC dimension, hyperplane arrangement, sign rank, half-spaces, linear classifiers, unbounded-error communication complexity.
UDC:
512.643.8+
519.142
MSC: Primary
03D15,
05A05,
15A60,
68T05; Secondary
68Q32 Received: 06.07.2016 and 14.10.2016
DOI:
10.4213/sm8780
Fulltext:
PDF file (1204 kB)
