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

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


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


8

Here is an easy argument: Assume there is a set $U$ of 5 points that can be shattered by balls. So for any set $S \subseteq U$, there exists a ball $B$ s.t. $B \cap U = S$ and a ball $B'$ s.t. $B' \cap U = U \setminus S$. Therefore, $B \cap B'$ contains no points of $U$. If $B \cap B' = \emptyset$, $B$ and $B'$ can be separated by a ...


8

My solution is incorrect. See other answer...


7

I believe you would enjoy Theory of Classification: A Survey of Recent Advances by Boucheron, Bousquet, and Lugosi. In particular, it starts by building up basic generalization theory via Rademacher complexities, introduces some useful tools (like the contraction principle, whose proof you can track down in Shai&Shai's notes referenced in the answer by ...


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

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


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


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


5

This was a recently taught course. http://www.cs.huji.ac.il/~shais/Handouts.pdf. I haven't carefully read through it, but chapter 7 has material on Rademacher Complexities. Hope it helps.


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.


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

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

The book by Cesa-Bianchi and Lugosi has much of the modern aspects of generalization bounds and learning theory.


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

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


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

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

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


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


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


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