Sbornik: Mathematics
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Sb.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Sbornik: Mathematics, 2017, Volume 208, Issue 12, Pages 1724–1757
DOI: https://doi.org/10.1070/SM8780
(Mi sm8780)
 

This article is cited in 2 scientific papers (total in 2 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
References:
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.
Funding agency Grant number
United States - Israel Binational Science Foundation (BSF)
Israel Science Foundation
The Israeli Centers for Research Excellence (I-CORE)
Oswald Veblen Fund
Taube Foundation for Jewish Life & Culture
N. Alon's research was carried out with the partial support of the United States-Israel Binational Science Foundation (BSF), the Israel Science Foundation (ISF), Israeli Centers for Research Excellence (I-CORE) and the Oswald Veblen Fund. A. Yehudayoff's research was carried out with the support of the Taube Foundation of Jewish Life & Culture (Hover fellow), the Israel Science Foundation (ISF) and the United States-Israel Binational Science Foundation (BSF).
Received: 06.07.2016 and 14.10.2016
Russian version:
Matematicheskii Sbornik, 2017, Volume 208, Number 12, Pages 4–41
DOI: https://doi.org/10.4213/sm8780
Bibliographic databases:
Document Type: Article
UDC: 512.643.8+519.142
MSC: Primary 03D15, 05A05, 15A60, 68T05; Secondary 68Q32
Language: English
Original paper language: Russian
Citation: N. Alon, Sh. Moran, A. Yehudayoff, “Sign rank versus Vapnik-Chervonenkis dimension”, Mat. Sb., 208:12 (2017), 4–41; Sb. Math., 208:12 (2017), 1724–1757
Citation in format AMSBIB
\Bibitem{AloMorYeh17}
\by N.~Alon, Sh.~Moran, A.~Yehudayoff
\paper Sign rank versus Vapnik-Chervonenkis dimension
\jour Mat. Sb.
\yr 2017
\vol 208
\issue 12
\pages 4--41
\mathnet{http://mi.mathnet.ru/sm8780}
\crossref{https://doi.org/10.4213/sm8780}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3659577}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2017SbMat.208.1724A}
\elib{https://elibrary.ru/item.asp?id=30738005}
\transl
\jour Sb. Math.
\yr 2017
\vol 208
\issue 12
\pages 1724--1757
\crossref{https://doi.org/10.1070/SM8780}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000425457000001}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85042653765}
Linking options:
  • https://www.mathnet.ru/eng/sm8780
  • https://doi.org/10.1070/SM8780
  • https://www.mathnet.ru/eng/sm/v208/i12/p4
  • This publication is cited in the following 2 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математический сборник Sbornik: Mathematics
    Statistics & downloads:
    Abstract page:417
    Russian version PDF:329
    English version PDF:14
    References:39
    First page:19
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024