11
votes
Accepted
Proper PAC learning VC dimension bounds
My thanks to Aryeh for bringing this question to my attention.
As others have mentioned, the answer to (1) is Yes, and the
simple method of Empirical Risk Minimization in $\mathcal{C}$ achieves
the ...
- 126
9
votes
Accepted
VC dimension of polynomials over tropical semirings?
I've realized that the answer to my question is - yes: the VC dimension of degree $\leq d$ polynomials on $n$ variables over any tropical semiring is at most a constant times $n^2\log(n+d)$. This can ...
- 6,685
7
votes
Accepted
How can we compute the VC dimension of a finite class of sets?
In 1996 Papadimitriou and Yannakakis noted that there exists an $n^{O(\log n)}$ brute-force algorithm (where $n$ is the size of the input) for computing VC-dimension of a 0-1 matrix by checking all ...
- 11.9k
7
votes
What is the VC Dimension of the $k-$Junta class
For the very limited situation in which $k=1$ and we're only interested in functions whose domain is $\{0,1\}^n$, the VC dimension is $\lfloor \log_2(n+1) + 1 \rfloor$.
The upper bound follows ...
- 1,429
6
votes
Proper PAC learning VC dimension bounds
Your questions (1) and (2) are related. First, let's talk about proper PAC learning. It is known that there are proper PAC learners that achieve zero sample error, and yet require $\Omega(\frac{d}{\...
- 10.3k
6
votes
Accepted
Tight VC bound for agnostic learning
This was proven in
M. Talagrand. Sharper bounds for Gaussian and empirical processes. The Annals of Probability, pages 28–76, 1994.
This is mentioned in e.g. this paper (Section 1.1.2), which does ...
- 4,451
5
votes
Accepted
Is there an equivalent to VC-dimension for density estimation as opposed to classification?
For distributions with finite support of size $d$, when the error metric is the $\ell_1$ distance, the analogue of VC dimension is exactly $d$. (In fact, it's pretty much the VC dimension -- since to ...
- 10.3k
5
votes
Proper PAC learning VC dimension bounds
To add to the currently accepted answer:
Yes. The $$O\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$$
sample complexity upper bound holds for proper PAC learning as well (although it is ...
- 4,451
5
votes
Parameterized complexity of Hitting Set in finite VC-dimension
We address this question in a new preprint:
http://arxiv.org/abs/1512.00481
Hitting Set in hypergraphs of low VC-dimension (Karl Bringmann, László Kozma, Shay Moran, N.S. Narayanaswamy).
It turns ...
- 1,306
4
votes
Is uniform convergence faster for low-entropy distributions?
This is very much a partial answer to my question. I'm hoping for a much better bound (or a counterexample). I managed to show a very weak bound. It is not very useful, but it does at least show that ...
- 2,803
4
votes
Is uniform convergence faster for low-entropy distributions?
First, let's use McDiarmid's inequality to conclude that
$$\mathbb{P}\left[|| \bar X - \mu ||_\infty \ge
\mathbb{E}|| \bar X - \mu ||_\infty
+
\varepsilon \right] \le e^{-2n\varepsilon^2},$$
so it ...
- 10.3k
4
votes
Accepted
PAC-learning bound with epsilon-cover of hypothesis class
This follows from Massart's finite class lemma. Let $F$ is a binary function class restricted to some set $\{X_1,\ldots,X_n\}$, and let $P_n$ be the empirical (i.e., uniform) measure on this set. Then,...
- 10.3k
4
votes
Accepted
What is tightest known (VC-style) sample complexity bound for uniform convergence of empirical means?
I'm not sure if claims about optimal constants are meaningful when trying to optimize all 3; often it is the case that one can be made better at the expense of another. One way to simplify the issue ...
- 10.3k
3
votes
VC dimension of the class of all polygons with k vertices
Assuming that the $k$-gon is simple (i.e., does not intersect itself and has no holes) and $k>3$, the two-ears theorem,
https://en.wikipedia.org/wiki/Two_ears_theorem
implies that it can be ...
- 10.3k
3
votes
Accepted
Rademacher complexity for piecewise-linear convex function
Since we're talking about real-valued functions, rather than VC-dimension, you probably want the fat-shattering one. The $\gamma$-fat-shattering of linear functions with $\ell_2$ norm bounded by $B$ ...
- 10.3k
3
votes
Accepted
VC generalization bound extended to other types of target functions
Pseudo dimension and fat shattering dimension are (some of the) analogue of VC dimension in the regression setting. See https://ttic.uchicago.edu/~tewari/lectures/lecture15.pdf (section 3)
3
votes
VC dimension of intersection of half-spaces
It has been recently shown by Csikos, Kupavskii, Mustafa
in "Optimal Bounds on the VC-dimension" that the VC dimension of $k$-fold unions (or intersections or XORs) of half-spaces in $R^d$ ...
- 10.3k
3
votes
Accepted
How to find the size of an ϵ-net of a vector space?
Note that $\mathcal{W}_{\epsilon}$ is an epsilon-net in the parametrization space, which is just $p$-dimensional Euclidean space. (So there is no need to think about covering numbers in e.g. spaces of ...
- 146
2
votes
Accepted
Other Uniform Bound
There's some confusion in the question which I'll try to clear up. First, let's dispense with "better sample complexity than bounds such as Chernoff bound and Hoeffding bound". These concentration ...
- 10.3k
2
votes
Accepted
What is the VC dimension of Turing machines with specified maximum size?
The exact VC bounds will depend on the alphabet size and the exact specification of the transition function (must it always move left or right, or can it stay put, etc). For fixed alphabet size, say 2,...
- 10.3k
2
votes
How can AIC converge in the limit when even 2 parameter models can have infinite VC dimension?
I tried to find a simple and accessible analysis of AIC. A definitive work seems to be Barron, Birgé, Massart, "Risk bounds for model selection via penalization"
https://link.springer.com/article/10....
- 10.3k
2
votes
Accepted
VC dimension for balanced binary decision trees
It is shown here (slide 10) that if $H_{d,k}$ is the number of depth-$k$ decision trees over $d$ input bits, then
$$v:=\log_2(H_{d,k})=
(2^k-1)(1+\log_2(d))+1
.
$$
So $v$ is an upper bound on the VC-...
- 10.3k
2
votes
Accepted
How to generalize VC dimension?
If the $VC$-dimension is $d$, then the number of sets that can be cut out from $m$ points by your family is $(em/d)^d$. (This is called the shatter function.)
Every set that you can cut out, can be ...
- 13.9k
2
votes
Accepted
Upper bound for VCdim of $H$ in terms of subgraph$(F)$, where $H := \{S(f) | f \in F\}$, with $S(f) := \{(x,y) \in X \times \{\pm 1\} | yf(x) \le 1\}$
Let us suppose that $H$ shatters some $k$ points $(x_i,y_i)$, $i\in[k]$.
That means that for all $b\in\{0,1\}^k$, there is an $f=f_b\in F$ such that $y_if(x_i)\le\gamma$ if $b_i=1$ and
$y_if(x_i)>\...
- 10.3k
2
votes
Accepted
Tighter Probability Bounds
This is almost a duplicate (see my comment above) but I'll give a quick answer before it (likely) gets closed. The first inequality in the OP has a superfluous $\log(n/d)$, which may be removed via ...
- 10.3k
1
vote
Accepted
VC-dimension of the infinite intersection of two spheres
Once the OP has clarified that the question is about the VC-dimension of the 2-fold intersection of spheres in $\mathbb{R}^d$ (in fact, $d=2$ was specified), a simple upper bound can be stated. The VC-...
- 10.3k
1
vote
VC generalization bound extended to other types of target functions
Daniely et al had some works on the subject back in 2012--2015.
In particular, it is referred to (there) as "multiclass learning".
Here are two works on this:
Multiclass learnability and the ...
- 5,531
1
vote
VC-dimension of infinite set of triangle wave
First of all, presumably you want the VC-dimension of your class of composed with the sign function, which yields a class of Boolean functions (otherwise, VC-dim is not defined). With that out of the ...
- 10.3k
1
vote
Is uniform convergence faster for low-entropy distributions?
We have largely resolved the question for product measures. I'm going to change the notation from the OP to be in line with our paper,
https://arxiv.org/abs/2209.04054
I'll be writing $\mu$ rather ...
- 10.3k
1
vote
How can AIC converge in the limit when even 2 parameter models can have infinite VC dimension?
AIC is used for model selection (i.e., density estimation, unsupervised learning) while VC theory is for supervised classification. "AIC is not a consistent model selection method":
https://...
- 10.3k
Only top scored, non community-wiki answers of a minimum length are eligible