# VC dimension, fat-shattering dimension, and other complexity measures, of a class BV functions

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 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]$.

• Since the range is $[0,1]$ rather than $\{0,1\}$, do you want pseudo-dimension instead of VC-dimension? – usul Jul 30 '18 at 18:47
• Please don't simultaneously cross-post -- ask on one site and wait for answers before trying the other. cstheory.stackexchange.com/questions/41291/… – usul Jul 30 '18 at 18:49
• @usul They're are slightly different. Here I'm asking for measures of complexity. On the CSTheory post, I'm asking for bounds on an integral (generalization error). But I agree both questions are related, and an answer to one would shed light on the other. I'll include a ref to the CSTheory post. – dohmatob Jul 30 '18 at 18:56
• Well the answer should have really been a comment instead, since it was pointing to a bug in one of the defined quantities. I've fixed the bug and up-voted his / her answer. Also I thought I left a comment (apparently not). I don't know of any other reasonable way to handle this. – dohmatob Jul 31 '18 at 13:23
• Wrt my answer: I assumed $C_\alpha$ was the main interest, and thought my answer would actually end the need for the question (otherwise I would have make it a comment). – Benoît Kloeckner Aug 1 '18 at 10:04

Since the OP mentions functions of bounded variation in the title, let's take that literal definition. A function $f:[0,1]\to\mathbb{R}$ is said to have variation $V(f)$ defined by $$V(f) = \sup_{0=x_0<x_1<\ldots<x_n=1}\sum_{i=1}^n|f(x_i)-f(x_{i-1})|.$$ For functions with integrable derivative, $V(f)=\int_0^1|f'(x)|dx$. Let $F_v$ be the collection of all $f:[0,1]\to\mathbb{R}$ with $V(f)\le v$. It is known (Anthony and Bartlett, Neural Network Learning (1999), Theorem 11.12) that the fat-shattering dimension of $F_v$ at scale $\gamma$ is $$1+\left\lfloor \frac{v}{2\gamma} \right\rfloor.$$

(The notion of fat-shattering -- the one most appropriate for learnability of continuous function classes, is given ibid. in Definition 11.11.)

Of course, covering numbers and fat-shattering are intimately related. For example, Theorem 12.7 ibid. shows how to bound the $L_\infty$ covering numbers in terms of the fat-shattering dimension (read the whole chapter!).

Finally, I take issue with "a function whose output doesn't vary much cannot be a good classifier". Linear classifiers/regressors are as smooth as can be and yet have an excellent track record. Conversely, functions that vary too rapidly are prone to overfitting.

• Thanks for the response. I came across that result, but didn't stare at it for too long because it only holds for functions of a single real variable. My naive guess is that it will then scale like $(1 + \frac{v}{2\gamma})^{\operatorname{dim}(\mathcal X)}$ , for some appropriate definition of $\operatorname{dim}(\mathcal X)$. Any thoughts ? – dohmatob Jul 31 '18 at 12:42
• Also my remark about "a function whose outputs don't vary too much" was badly phrased. I've corrected the phrasing to more clearly reflect what I hard in mind: essential constant functions. BTW, your paper on "concentration under weak dependence" is really cool :) – dohmatob Jul 31 '18 at 12:43
• If I can supplement your answer, Theorem 2 of this 1997 paper by Partlett citeseerx.ist.psu.edu/viewdoc/… shows that there exists absolute constants $c_1,c_2$ such that $\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$ for any $\mathcal H \subseteq [0,1]^{\mathcal X}$, so if we can estimate $\operatorname{fat}_{\mathcal H}(\gamma)$ (for higher dimensional $\mathcal X$), then we're done! – dohmatob Jul 31 '18 at 12:54
• I have tried (again and again) in vain to come up with a reasonable higher-dimensional analogue of BV, which would behave well with regard to fat-shattering -- along the lines of what you suggested. It seems to be a VERY difficult problem. See some failed attempts here: mathoverflow.net/questions/234251/… – Aryeh Kontorovich Jul 31 '18 at 14:08
• (1) I see you've edited the question so that some of my "Finally" comment no longer applies. (2) Feel free to accept if you feel the question has been adequately answered. – Aryeh Kontorovich Aug 1 '18 at 11:18

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 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 functions, when $\mathcal{X}$ is a metric space (the particular case of Lipschitz function is the most common),

• As mentioned by Aryeh Kontorovich, BV 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 $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.

• Thanks for the generous response (upvoted). (A) What if we impose $\alpha \ll 1$ and $|\bar{h} - 1/2| \gg \alpha$ for all $h$ (see the of definition of $\mathcal H_\alpha$) ? This will sure diminish the richness of $\mathcal H_\alpha$, right ? Can anything be salvaged from the wreckage ? (B) What minimal conditions could be imposed on the $\bar{h}$'s so as to have something +ve to say about the claim ? – dohmatob Aug 1 '18 at 11:03
• @dohmatob: no, your patch would not fix anything. $1/2$ has no particular role, it could be replaced by any value. You do need to use the geometry of $\mathcal{X}$ in some way: any condition that is invariant by bijective map will give you the same complexity for $[0,1]$ or $[0,1]^{124643234}$ - hence either trivial or infinite. – Benoît Kloeckner Aug 1 '18 at 11:18
• Thanks, I see the big picture. One last take: In the limit $\alpha \rightarrow 0^+$, $\mathcal H_\alpha$ "approaches" the set of constant functions from $\mathcal X$ to $[0,1]$ (as all the functions in it are then essentially constants). Thus in this limit, one would then expect the covering number of $\mathcal H_\alpha$ to be essentially that of the interval $[0,1]$ (independent of the geometry of $\mathcal X$), namely $1/\epsilon$. No ? – dohmatob Aug 1 '18 at 11:56
• @dohmatob: yes if $\varepsilon$ is fixed and $\alpha\to 0$, but then it amounts to looking only at constant functions, and more importantly it says nothing if $\varepsilon$ goes to $0$ as well (and the limits cannot be exchanged here). – Benoît Kloeckner Aug 1 '18 at 12:19