# Tag Info

## Hot answers tagged vc-dimension

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
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,765
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 ...
• 12k

### 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
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,471

• 10.6k
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.6k
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.6k
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,656
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.6k
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.6k
1 vote

### VC dimension in data mining

A range space is just a pair $(X,\mathcal{R})$ where $X$ is a finite or infinite set and a $\mathcal{R}$ is a finite or infinite collection of subsets of $X$ (the elements of $\mathcal{R}$ are called ...
• 569

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