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 ...
user avatar
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 ...
user avatar
  • 6,635
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 ...
user avatar
  • 11.8k
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 ...
user avatar
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 ...
user avatar
  • 4,341
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}{\...
user avatar
  • 10.1k
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 ...
user avatar
  • 10.1k
5 votes

Resource listing models with known VC dimension

Rather than computing the VC dimension of a particular function class, it's usually more interesting to understand how generic properties of a function class relate to its VC dimension. For example, ...
user avatar
  • 10.1k
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 ...
user avatar
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 ...
user avatar
  • 4,341
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,...
user avatar
  • 10.1k
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 ...
user avatar
  • 10.1k
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)
user avatar
3 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 ...
user avatar
  • 2,743
3 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 ...
user avatar
  • 10.1k
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$ ...
user avatar
  • 10.1k
3 votes
Accepted

Are there closed-form expressions providing the VC-dimension for the multi-class case for different classifiers?

VC-dimension has multiple multiclass extensions: pseudo dimension, Natarajan dimension, graph dimension. See here for example: http://math.huji.ac.il/~amitd/multiclass.pdf http://jmlr.org/papers/...
user avatar
  • 10.1k
3 votes
Accepted

How to deal with concept classes with exponential value of VC dimension

One approach would be to stratify your concept class by VC-complexity. For example, suppose that $C$ is the set of all functions $f:\{0,1\}^n\to\{0,1\}$; its VC-dim is $2^n$. However, you can ...
user avatar
  • 10.1k
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$ ...
user avatar
  • 10.1k
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 ...
user avatar
  • 10.1k
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 ...
user avatar
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 ...
user avatar
  • 10.1k
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,...
user avatar
  • 10.1k
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-...
user avatar
  • 10.1k
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 ...
user avatar
  • 13.5k
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 ...
user avatar
  • 10.1k
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....
user avatar
  • 10.1k
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)>\...
user avatar
  • 10.1k
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 ...
user avatar
  • 5,261
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 ...
user avatar
  • 10.1k

Only top scored, non community-wiki answers of a minimum length are eligible