10

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 $O((d/\varepsilon)\log(1/\varepsilon))$ sample complexity (see Vapnik and Chervonenkis, 1974; Blumer, Ehrenfeucht, Haussler, and Warmuth, 1989). As for (2), ...


9

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 be shown using Theorem 1 above. See here for details. So, BPP $\subseteq$ P/poly holds also for tropical circuits and, hence, also for "pure" dynamic ...


7

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 essentially from Sasho's argument: there are $2+2n$ 1-juntas on $n$ variables, and if there were more than $\log_2$ of that many inputs, we could find a function that ...


6

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}{\epsilon}\log\frac1\epsilon)$ examples. For a simple proof of the $\epsilon$ dependence, consider the concept class of intervals $[a,b]\subseteq[0,1]$ under the ...


6

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 a pretty good job (in my opinion) of summarizing the landscape.


5

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 estimate a distribution over $d$ in $\ell_1$ is equivalent to agnostically PAC-learning the concept class $2^{[d]}$). For discrete distributions with infinite ...


5

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, function spaces with linear dimension $d$ have VC-dim at most $d$. You can also bound the VC-dim of a function class realized by circuits with bounded depth/...


5

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 out that Hitting Set is W[1]-hard already when the VC-dimension is equal to 2.


5

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 important to note that it may not lead to a computationally efficient learning algorithm. Which is normal, since unless $\mathsf{NP}=\mathsf{RP}$ is it known ...


4

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, for any $\epsilon>0$, the empirical Rademacher complexity of $F$ is bounded by $$ R_n(F;X) \le \epsilon + \sqrt{\frac{2\log N_F(\epsilon)}{n}},$$ where $...


4

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 is to look at the expectation, so you only have to deal with one constant. This is the approach taken by Devroye-Lugosi (the book suggested by Clément). The ...


3

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

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 uniform convergence can be bounded using entropy. As Aryeh observes, it suffices to bound $\mathbb{E}[\|\overline X - \mu\|_\infty]$. First, use the duality ...


3

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 remains to bound $\mathbb{E}|| \bar X - \mu ||_\infty$. Using Jensen's inequality, $$ (\mathbb{E}|| \bar X - \mu ||_\infty)^2\le \mathbb{E}|| \bar X - \mu ||_\...


3

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$ is of order $(B/\gamma)^2$. For a $k$-fold maximum of such functions, the bound grows as $O((B/\gamma)^2k\log k)$, as shown here: https://www.cs.bgu.ac.il/~...


3

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$ behaves as $$ \Theta(dk\log k).$$ Additionally, in a recent tour de force, Kupavskii has given a polynomial bound on the VC-dimension of $k$-vertex polytopes: ...


2

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 decompose $C$ in any number of ways. Say, $C_k$ is the collection of all functions whose (minimal) binary tree has depth $k$ or less. Or, $C_k$ is the set of all ...


2

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/volume8/guermeur07a/guermeur07a.pdf There are also extensions to continuous-valued functions (fat-shattering dimension): http://users.cecs.anu.edu.au/~williams/...


2

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 results are invoked, implicitly or explicitly, in the VC and Rademacher bounds as well and are essentially unimprovable (unless you want to take into account ...


2

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, I think you can apply the DFA-VCdim analysis of Ishigami and Tani, VC-dimensions of finite automata and commutative finite automata with $k$ letters and $n$...


2

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-dimension of your class. I don't know how tight it is, since you have the additional constraint of the trees being balanced.


2

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 changed at most $\sum_{i=0}^{tm} \binom mi$ ways to contribute to the $t$-shattering. So if you want to $t$-shatter a set of size $m$, then you need $2^m\le (em/d)...


2

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 chaining, as discussed here: Tight VC bound for agnostic learning Once that log-factor is removed from the VC bound, it becomes optimal up to constants (i.e., ...


2

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.1007/s004400050210 though I can't vouch for accessibility. Instead, let's analyze your sinusoids example. Suppose I have a parametric class of densities over $[...


1

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 ERM principle Multiclass Learning Approaches: A Theoretical Comparison with Implications Unfortunately, my knowledge of this is limited to knowing the authors ...


1

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 way, the answer is: It's infinite. That will be the answer for any periodic function class that contains all possible frequencies and crosses the x-axis. For a ...


1

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://robjhyndman.com/hyndsight/aic/ Various theoretical analyses of AIC are available; see here for example: http://www.math.tau.ac.il/~felix/PAPERS/ieee2016.pdf


1

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 "ranges"). Note that a range space is not used to "represent" the VC-dimension (whatever meaning of "represent" you are using). Rather, the VC-dimension is a ...


1

Converting the comment to an answer: See the notes here: cs.cornell.edu/~sridharan/dudley.pdf with the dependence on $\sup_f \hat E[f^2]$


1

See Hanneke's disagreement coefficient, http://projecteuclid.org/euclid.aos/1291388378


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