0
$\begingroup$

There are of course $n \choose k$ monotone disjunctions which bounds the VC dimension at $\log_2 {n \choose k}$. I'm wondering if this is bound at $k \log_2 n$? (Possibly follows from combinatorial identities).

More generally I'm looking at the claim in An algorithmic theory of learning: Robust concepts and random projection: "Further, it is NP-hard to learn a disjunction of $k$ variables as a disjunction of few than $k \log n$ variable." The author states this without proof; I'm assuming it's well-known or obvious but am trying to figure out why or where it is proved.

$\endgroup$
1
  • $\begingroup$ You mention $n \log k$ and $k \log n$ - was one of them a typo? $\endgroup$
    – G. Bach
    Dec 17, 2015 at 13:39

1 Answer 1

1
$\begingroup$

Yes. This bound follows by a little bit of straightforward manipulation:

$${n \choose k} = {n \times (n-1) \times \dots \times (n-k+1) \over k!} \le {n \times n \times \dots \times n \over 1} = n^k.$$

Now taking the logarithm of both sides, we see that

$$ \lg {n \choose k} \le \lg(n^k) = k \lg n.$$

The bound can also be derived from bounds listed in Wikipedia: it follows from the fact that ${n \choose k} \le n^k/k!$. Check out Wikipedia in the future -- it's often helpful!

$\endgroup$
3
  • $\begingroup$ Thanks, yeah it was easy. I don't see the full claim following like I thought it would; so posted question on the full claim here. $\endgroup$
    – djechlin
    Dec 17, 2015 at 20:24
  • $\begingroup$ I see why I was confused... this gives an upper bound, I needed lower ... :/ $\endgroup$
    – djechlin
    Dec 17, 2015 at 20:26
  • $\begingroup$ @djechlin, You can obtain an asymptotic lower bound from inequalities listed on that same Wikipedia page. $\endgroup$
    – D.W.
    Dec 17, 2015 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.