VC dimension of polynomials (in one variable) of degree d

Question

Linear functions in one variable have VC dimension =3 and I remember reading somewhere that the VC for polynomials of degree $d$ is $(d^2 + 3d + 2)/2$.

I am searching for ideas that can prove the above claim (and perhaps generalize to many variables as well, though that seems too much to hope for).

Any approach, even an incomplete one, will be appreciated.

To define the problem properly: Given a plane (2D, x and y coordinates) what is the size of maximum set that can be shattered if you can use classifying functions that are polynomial ($y=p(x)$) of degree at mode $d$, and you are free to choose which side of the curve you want to label positive.

For example, label (x,y) as positive iff $y > x^2 +5x +9$.

Answer 1

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 spaces in the resulting space.

I'm not sure where you get your bound from: the correct expression for the VC dimension of polynomials in d variables of degree D is $\binom{d + D}{d}$, which is the number of monomials of degree at most D formed from d variables.

Answer 2

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 $(x_1 - a_1)^2 + (x_2 - a_2)^2 - 1 \leq 0$.

We can get a bound on a quantity which is more delicate than VC dimension in this model. Define $\pi(m)$ as the maximum number of distinct sets induced by $\{S(a)\}$ on any set of $m$ points, i.e. $$ \pi(m) = \max_{X \subseteq \mathbb{R}^d}{|\{S(a) \cap X\}|}, $$ where the max is taken over sets $X$ of $m$ points. This is the primal shatter function of the range space $\{S(a)\}$. Notice that the VC-dimension of of the range space is that maximum $m$ such that $\pi(m) = 2^m$. Also, if the VC-dimension of a range space is $k$, then its shatter function is bounded by $O(m^k)$.

For $m$ polynomials $f_1(a), \ldots, f_m(a)$, $\sigma = (\sigma_1, \ldots, \sigma_m) \in \{-, +\}^m$ is a sign pattern if there exists some $a$ such that for all $i$ the sign of $f_i(a)$ is $\sigma_i$. A result from algebraic geometry is that the maximum number of distinct sign patterns of $m$ degree $D$ polynomials in $p$ variables is bounded by $2^{O(p)}(Dm/p)^p$.

Let's use this theorem. Define $f_i(a) = f(x^i, a)$. We get that $|\{S(a) \cap X\}|$ is exactly the number of distinct sign patterns of $f_1, \ldots, f_m$. So, in particular, if a range space is given by a family of constant degree polynomials in $p$ parameters, its shatter function is bounded by $O(m^p)$.

Answer 3

I think the paper VC dimension of neural networks answers the question. In Equation (6), the definition of VC dimension of real valued functions is the same as yours (and I saw some different definitions somewhere), and Theorem 1 claims that the VC dimension of polynomials is exactly the number of items in it. By the way, if the function set contains all the polynomials with degree no more than D, the VC dimension would be $C_{D+d}^d$ according to Suresh Venkat's answer.