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


8

The basic method works like this: Assume your inequalities are of the form $$ \sum_{i \le d} a_i x^i \le 0$$ Then you construct a lifting map to a space of higher dimension in which each monomial corresponds to one dimension. Now the polynomial can be expressed as a linear combination of the new dimensions and you can invoke the usual result for half ...


7

I discovered after this publication that there is older work by Dvoretzky-Kiefer-Wolfowitz in 1956 that looks specifically at this one-dimensional case for sampling. There is also follow up by just Kiefer and Wolfowitz a year or two later that handles the (anchored) rectangle case. For these specific settings, there has been some much more refined work ...


7

First, and more obviously, an $\epsilon$-sample is an $\epsilon$-net. Of course, the above observation gives usually very loose bounds for $\epsilon$-nets. The bound you mention at the end of our post relies not just on small discrepancy but also on VC-dimension itself, so the relationship is not so clear. Let me elaborate. Let $s(\epsilon)$ be the size ...


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

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.


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


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


5

No, you cannot. See Thm 2.1 of http://link.springer.com/article/10.1007%2FBF02187833 (it says that a random family gives an example, with appropriately chosen parameters).


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

The following is based on Jiri Matousek's Geometric Discrepancy book. Define a range space in $\mathbb{R}^d$ parametrized by $a_1, \ldots, a_p$ as follows. Let $f$ be a degree $D$ polynomial in $d + p$ variables. For each $a \in \mathbb{R}^p$, the set $S(a)$ is defined as $S(a) = \{x \in \mathbb{R}^d: f(x, a) \leq 0\}$. For example, circles are defined as $(...


4

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.


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


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


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

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


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

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

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

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

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


1

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


1

This doesn't answer the question, but it might be helpful. Mossel and Umans have made a detailed study of the complexity of approximating VC-dimension, when the set system is succinctly presented: On the Complexity of Approximating the VC Dimension http://users.cms.caltech.edu/~umans/papers/MU01-final.ps


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