# VC dimension of a class H that assigns 1 to at most k points or that assigns 0 to at most k points

Let $$X$$ be a finite domain and $$k$$ a number such that $$k\le|X|$$. Consider the hypothesis class

$$H:=\{h:|\{x\in X:h(x)=1\}|\le k\text{ or }|\{x\in X:h(x)=0\}|\le k\}.$$

Find the VC dimension of $$H$$.

• Is this a binary classification problem, where you're proposing some Boolean hypothesis over $x$ ? Would you like to describe the VC dimension of a simpler $h'$ which assigns 1 to at most $k$ points, and hence 0 to at least $|X| - k$ points? Perhaps an even simpler $h''$ which assigns 1 to exactly $k$ points?
– J_H
Commented Mar 25 at 18:12
• What have you tried? (Do you have any sets that are shattered, hence a lower bound on the dimension; or an argument for an upper bound, by saying that no set of a large size is shattered?) Commented Apr 14 at 16:34
• See related questions datascience.stackexchange.com/q/114918/55122 and datascience.stackexchange.com/q/117796/55122 Commented Apr 14 at 16:34