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\}. $$


(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.


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

  • $\begingroup$ Since the range is $[0,1]$ rather than $\{0,1\}$, do you want pseudo-dimension instead of VC-dimension? $\endgroup$ – usul Jul 30 '18 at 18:47
  • 1
    $\begingroup$ Please don't simultaneously cross-post -- ask on one site and wait for answers before trying the other. cstheory.stackexchange.com/questions/41291/… $\endgroup$ – usul Jul 30 '18 at 18:49
  • $\begingroup$ @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. $\endgroup$ – dohmatob Jul 30 '18 at 18:56
  • 1
    $\begingroup$ 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. $\endgroup$ – dohmatob Jul 31 '18 at 13:23
  • 1
    $\begingroup$ 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). $\endgroup$ – 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.

  • $\begingroup$ 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 ? $\endgroup$ – dohmatob Jul 31 '18 at 12:42
  • $\begingroup$ 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 :) $\endgroup$ – dohmatob Jul 31 '18 at 12:43
  • $\begingroup$ 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! $\endgroup$ – dohmatob Jul 31 '18 at 12:54
  • $\begingroup$ 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/… $\endgroup$ – Aryeh Kontorovich Jul 31 '18 at 14:08
  • $\begingroup$ (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. $\endgroup$ – 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.

  • $\begingroup$ 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 ? $\endgroup$ – dohmatob Aug 1 '18 at 11:03
  • $\begingroup$ @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. $\endgroup$ – Benoît Kloeckner Aug 1 '18 at 11:18
  • $\begingroup$ 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 ? $\endgroup$ – dohmatob Aug 1 '18 at 11:56
  • $\begingroup$ @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). $\endgroup$ – Benoît Kloeckner Aug 1 '18 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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