# Tag Info

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 ...
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 ...
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 ...

### 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 ...

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 ...
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-...
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 ...
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 ...
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 ...
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://...

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