Sign rank versus VC dimension

Noga Alon, Shay Moran, Amir Yehudayoff

Research output: Contribution to journalConference articlepeer-review

22 Scopus citations


This work studies the maximum possible sign rank of N × N sign matrices with a given VC 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. Our lower bounds improve over previous ones by Ben-David et al. and can be interpreted as exhibiting a weakness of kernel-based classifiers. Our upper bounds, on the other hand, can be interpreted as exhibiting the universality of kernel-based classifiers. 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 VC dimension, and the number of maximum classes of a given VC dimension - answering a question of Frankl from'89, and (ii) design an efficient algorithm that provides an O(N/log(N)) multiplicative approximation for the sign rank (computing the sign rank is equivalent to the existential theory of the reals). We also observe a general connection between sign rank and spectral gaps which is based on Forster's argument. Consider the N × N adjacency 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 VC dimension 2 and sign rank Θ(- N1/2). This answers a question of Ben-David et al. regarding the sign rank of large VC 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.

Original languageEnglish (US)
Pages (from-to)47-80
Number of pages34
JournalJournal of Machine Learning Research
Issue numberJune
StatePublished - Jun 6 2016
Externally publishedYes
Event29th Conference on Learning Theory, COLT 2016 - New York, United States
Duration: Jun 23 2016Jun 26 2016

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence


  • Communication complexity
  • Dimension complexity
  • Kernel machines
  • Maximum classes
  • Sign rank
  • Spectral gap
  • VC dimension


Dive into the research topics of 'Sign rank versus VC dimension'. Together they form a unique fingerprint.

Cite this