I wish to show that a function which is "essentially constant" (defined shortly) can't 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 $0 < \alpha \ll 1$, define


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


Questions
=========


**(A)** What is the VC dimension or fat-shattering dimension of $\mathcal H\_\alpha$ ? Good lower and upper bounds thereof would be just as important.


**(B)** I'd also be interested in metric complexity measures for $\mathcal H\_\alpha$ (covering number, metric entropy, etc.).
Good lower and upper bounds thereof would be just as important. 


Observations
============


Theorem 2 of [this 1997 paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.266&rep=rep1&type=pdf) shows that there exists absolute constants $c\_1,c\_2$ such that for any $\mathcal H \subseteq [0,1]^{\mathcal X}$, the following bounds metric entropy and fat-shattering dimension holds


$$
\operatorname{fat}\_{\mathcal {H}}(4\epsilon)/32 \le \max\_{P}\log\_2(\mathcal N(\epsilon,\mathcal H,\mathcal L\_1(dP))) \le c\_1 \operatorname{fat}\_{\mathcal H}(c\_2 \epsilon)(\log\_2(1/\epsilon))^2.
$$
So if we can estimate $\operatorname{fat}\_{\mathcal H\_\alpha}(\gamma)$, then we're done!


**Answer to one-dimensional case.**
A user has given an explicit computation of $\operatorname{fat}\_{\mathcal H\_\alpha}(\gamma)$ in the simple one-dimensional case $\mathcal X = [0, 1]$.



VC dimension, fat-shattering dimension, and other complexity measures, of a class BV functions
I think the family $\mathcal{H}\_\alpha$ is ill-suited for your purposes, because it is too rich.


For example in the case $\mathcal{X} = [0,1]$ (or anything atomless probability measure space) one can find arbitrarily many $h\_\tau\in\mathcal{H}\_\alpha$ such that any two of them are at distance $\alpha/2$. This means that $\mathcal{N}(\varepsilon,\mathcal{H}\_\alpha,L^1([0,1])) = \infty$ as soon as $\varepsilon\le \alpha/2$.


To prove this explicitely, one can use [Hadamard matrices](https://en.wikipedia.org/wiki/Hadamard_matrix) of size $N$ (this is certainly a conceptual overkill and could be replaced by a random choice, or a classical non-compactness argument in functional analysis, but it seems the simplest way to proceed). Divide $[0,1]$ into $N$ equal intervals, and for each sequence $\tau=(\tau\_i)\_{1\le i\le N} \in \{-1,1\}^N$ define $h\_\tau$ to be $\frac{1+\tau\_i\alpha}2$ on the $i$-th interval. If $\tau,\tau'$ are two lines of a Hadamard matrix, they differ on exactly half their entries, so that $\lVert h\_\tau-h\_{\tau'}\rVert\_{L^1([0,1])}=\frac\alpha2$. There exist arbitrarily large Hadamard matrices and we are done.


Note that if you stay at the level of precision $\varepsilon\simeq \alpha$, then your family is essentially reduced to a point (any two $h\in\mathcal{H}\_\alpha$ are indistinguishable at this scale).


In order not to stay on a negative claim, let me suggest that you use instead another definition of ``essentially constant'', through a more refined measures of variations of a function. The problem with your condition is that it does not see any of the geometry of $\mathcal{X}$ (the class $\mathcal{H}\_\alpha$ essentially only depend on the cardinal of $\mathcal{X}$), and you cannot expect anything (unless possibly you capture some geometry with the chosen metric on the considered space of functions - $L^1$ would not do, as the $[0,1]^{n}$ are all isomorphic when endowed with their Lebesgue measures).


There are many natural choices:


* [H"older](https://en.wikipedia.org/wiki/H%C3%B6lder_condition) functions, when $\mathcal{X}$ is a metric space (the particular case of Lipschitz function is the most common),
* As mentioned by Aryeh Kontorovich, [BV](https://en.wikipedia.org/wiki/Bounded_variation) functions (this notion is quite simple in dimension $1$, but significantly more intricate in higher dimension), and for a rougher notion $p$-BV (in dimension $1$, one replaces the $\lvert f(x\_{i+1})-f(x\_i)\rvert$ by $\lvert f(x\_{i+1})-f(x\_i)\rvert^p$, where $1/p<1$ plays the same role as the H"older exponent,
* smooth ($\mathcal{C}^k$) functions when $\mathcal{X}$ is a domain in $\mathbb{R}^n$ or a manifold, and the many available variations: Sobolev, Besov, etc.


