I wish to show that a function whose output doesn't vary much cannot be a good classifier (machine learning). For this i need to estimate the "complexity" of such a class of functions.

So let $\mathcal X$ be an abstract set (we may assume has metric structure, e.g $\mathbb R^d$). Given $\alpha \ge 0$, define

$$ \mathcal H_\alpha := \{h: \mathcal X \rightarrow [0, 1]\text{ s.t } | \exists a_h \in \mathbb R \text{ veryfing } |h(x) - a_h| \le \alpha\;\forall x \in \mathcal X\}. $$

Question:

(A) What is the VC (pseudo-)dimension of $\mathcal H_\alpha$ ?

(B) I'd also be interested in (tight bounds for) metric complexity measures of $\mathcal H_\alpha$ (covering number, metric entropy, etc.).

(C) Given a probability distribution $P$ on $\mathcal X \times \{0,1\}$ and a point $(x, y)$ sampled from $P$, consider the ernoulli random variable $$ Z_h := 1_{\{h(x) \ne y\}}= \begin{cases}1,&\mbox{ if }h(x) \ne y,\\ 0 ,&\mbox{ if }h(x)=y.\end{cases}, $$ with expected value $p_h := \mathbb E_{(x,y) \sim P}[Z_h] = P(h(x) \ne y)$.

• What is a good (bigger is better) lower bound on the best generalization error $\inf_{h \in \mathcal H_\alpha} p_h $ ?

• Same question for $\sup_{P \in \mathcal P(X \times \{0,1\})} \inf_{h \in \mathcal H_\alpha} p_h$ and $\inf_{h \in \mathcal H_\alpha}\sup_{P \in \mathcal P(X \times \{0,1\})}p_h$.