Sign rank versus Vapnik-Chervonenkis dimension

N. Alon ; Sh. Moran ; A. Yehudayoff

Sbornik. Mathematics, Tome 208 (2017) no. 12, pp. 1724-1757

Résumé

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.

Détail

Keywords: hyperplane arrangement, sign rank, half-spaces, linear classifiers, unbounded-error communication complexity.
Mots-clés : VC dimension