Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > VC DIMENSION:
Reports tagged with VC Dimension:
TR94-024 | 12th December 1994
Marek Karpinski, Angus Macintyre

Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks

We introduce a new method for proving explicit upper bounds on the VC
Dimension of general functional basis networks, and prove as an
application, for the first time, the VC Dimension of analog neural
networks with the sigmoid activation function $\sigma(y)=1/1+e^{-y}$
to ... more >>>


TR95-051 | 16th October 1995
Pascal Koiran

VC Dimension in Circuit Complexity

The main result of this paper is a Omega(n^{1/4}) lower bound
on the size of a sigmoidal circuit computing a specific AC^0_2 function.
This is the first lower bound for the computation model of sigmoidal
circuits with unbounded weights. We also give upper and lower bounds for
the ... more >>>


TR95-055 | 24th November 1995
Marek Karpinski, Angus Macintyre

VC Dimension of Sigmoidal and General Pfaffian Networks

We introduce a new method for proving explicit upper bounds
on the VC Dimension of general functional basis networks,
and prove as an application, for the first time, that the
VC Dimension of analog neural networks with the sigmoidal
activation function $\sigma(y)=1/1+e^{-y}$ ... more >>>


TR14-135 | 23rd October 2014
Noga Alon, Shay Moran, Amir Yehudayoff

Sign rank, VC dimension and spectral gaps

Revisions: 2

We study the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is $3$. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. Similar (slightly less accurate) statements hold for $d>2$ as well. We discuss the tightness of our methods, and describe ... more >>>


TR15-025 | 22nd February 2015
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff

Teaching and compressing for low VC-dimension

In this work we study the quantitative relation between VC-dimension and two other basic parameters related to learning and teaching. We present relatively efficient constructions of {\em sample compression schemes} and
for classes of low VC-dimension. Let $C$ be a finite boolean concept class of VC-dimension $d$. Set $k ... more >>>


TR15-040 | 24th March 2015
Shay Moran, Amir Yehudayoff

Proper PAC learning is compressing

Revisions: 1

We prove that proper PAC learnability implies compression. Namely, if a concept $C \subseteq \Sigma^X$ is properly PAC learnable with $d$ samples, then $C$ has a sample compression scheme of size $2^{O(d)}$.
In particular, every boolean concept class with constant VC dimension has a sample compression scheme of constant size. ... more >>>


TR15-189 | 25th November 2015
Shay Moran, Cyrus Rashtchian

Shattered Sets and the Hilbert Function

Revisions: 1

We study complexity measures on subsets of the boolean hypercube and exhibit connections between algebra (the Hilbert function) and combinatorics (VC theory). These connections yield results in both directions. Our main complexity-theoretic result proves that most linear program feasibility problems cannot be computed by polynomial-sized constant-depth circuits. Moreover, our result ... more >>>




ISSN 1433-8092 | Imprint