Sign rank versus Vapnik-Chervonenkis dimension

N. Alon, S. Moran, A. Yehudayoff

Research output: Contribution to journalArticle

Abstract

This work studies the maximum possible sign rank of sign (N × N)-matrices with a given Vapnik-Chervonenkis dimension d. For d = 1, this maximum is three. For d = 2, this maximum is ⊖ (N1/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 Forsters argument. Consider the adjacency (N×N)- matrix of a δ-regular graph with a second eigenvalue of absolute value λ and δ ≤ N/2. We show that the sign rank of the signed version of this matrix is at least δ/λ. We use this connection to prove the existence of a maximum class C ⊆ {±1}N with Vapnik-Chervonenkis dimension 2 and sign rank ⊖ (N1/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.

Original languageEnglish (US)
Pages (from-to)1724-1757
Number of pages34
JournalSbornik Mathematics
Volume208
Issue number12
DOIs
StatePublished - Jan 1 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory

Keywords

  • VC dimension
  • halfspaces
  • hyperplane arrangement
  • linear classifiers
  • sign rank
  • unbounded-error communication complexity

Fingerprint Dive into the research topics of 'Sign rank versus Vapnik-Chervonenkis dimension'. Together they form a unique fingerprint.

Cite this