Lower bound on misclassification rate of Lipschitz functions in terms of Lipschitz constant

Question

Important note

@MateuszKwaśnicki in the comment section has raised a fundamental issue with the current statement of the problem. I'm trying to bugfix it.

Setup

I wish to show that a Lipschitz function with a "very small" Lipschitz constant can't be a "very good" classifier (machine learning), as the uncertainty margin must be huge. Indeed, intuitively, if the Lipschitz constant is too small, then the classifier defines an essentially constant / clueless function, which is totally inconsiderate of the data.

Formally, let $X=(X, d)$ be a metric space (assumed to be totally bounded, for convenience), $Y = \{0,1\}$, and let $P$ be a fixed probability distribution on $X \times Y$. Finally, given $L > 0$, let $\mathcal H$ be the space of $L$-Lipschitz functions $X \rightarrow [0, 1]$, and for $h \in \mathcal H$, define $c_h: X \rightarrow \{0,1\}$ by $c_h(x) = \mathbb 1_{h(x) \ge 1/2}$.

Question 1

As a function of $P$ and $L$, what is a lower bound on the misclassification rate of the champion in $\mathcal H$ ? More formally, whats a good lower bound for

$$ \operatorname{err}_{\mathcal H} := \inf_{h \in \mathcal H} P(c_h(x) \ne y) ? $$

Question 2

For $\epsilon \ge 0$, define a robustified version of $\operatorname{err}_{\mathcal H}$ as

$$\operatorname{err}_{H,\epsilon} := \inf_{h \in \mathcal H} P(\exists x' \in \operatorname{Ball}_X(x,\epsilon) | c_h(x') \ne y). $$ Note that $\operatorname{err}_{\mathcal H,\epsilon} \ge \operatorname{err}_{\mathcal H}$ with equality if $\epsilon = 0$. Question: What's a good lower bound for $\operatorname{err}_{\mathcal H,\epsilon}$ as a function of $P$, $L$, and $\epsilon$?

Observation

• Of course the answer will depend on the unknown distribution $P$; It will suffice to show that $\operatorname{err}_{\mathcal H}$ is "much bigger" than than the misclassification rate of the Bayes optimal classifier defined by $x \mapsto \mathbb 1_{\mathbb E_P[y|x]\ge 1/2}$.

• I know of bounds on the metric entropy of such a space (e.g see Theorem 11 of this paper), but I'm not sure how to apply them to the above problem. In the literature, I've seen metric entropy, etc. being used to obtain upper bounds on generalization error, but don't know of works which use this measure of complexity to establish lower bounds on the error rate of a family of classifiers. Thanks in advance.

Related questions

The question is related to this one.

Answer 1

If we let $P$ put probability $\frac{1}{2}$ each on $Y \in \{\pm 1\}$ independent of $X$, then for every classifier (from any class!) $$P(\text{sign}(h(x)) \neq y) = \frac{1}{2}$$ so $\text{err}_{\mathcal{H}} = \frac{1}{2}$ of course.

On the other hand, most reasonable classes $\mathcal{H}$ can guarantee $\text{err}_{\mathcal{H}} \geq \frac{1}{2}$ on all distributions. For instance suppose $\mathcal{H}$ contains a pair $h,h'$ with $h(x) = -h'(x)$ for all $x$. Then for any $P$, one of these hypotheses has error rate at least $\frac{1}{2}$.

So there is a trivial answer not at all related to the structure of your hypothesis class, and the problem is with your question's setup. This is why we use notions of regret and excess risk: They compare the difference in performance of a finite-sample algorithm to the best hypothesis in $\mathcal{H}$ for $P$, and bound this difference over all $P$. (The question asks to bound absolute performance over all $P$). Bounding the difference in performance is where VC-dimension, etc. come in.

So to make your point about this family of classifiers being a bad one, you have to ask a different question. For instance you could consider a broader family of hypotheses and show that $\mathcal{H}$ performs really badly relative to that family on some examples.

Answer 2

You can express the $\gamma$ fat-shattering dimension of the set of $L$-Lipschitz functions $F_L$ in terms of the packing numbers of your metric space: $$ \mathrm{fat}_\gamma(F_L)\le M(L/\gamma), $$ (disregarding universal constants; see exact statement in Corollary 1 here: https://www.cs.bgu.ac.il/~karyeh/metric-classification-ieee-arxiv.pdf , where it's stated as an upper bound, but a matching lower bound clearly holds). Since fat-shattering characterizes uniform convergence (see, e.g., http://homes.dsi.unimi.it/~cesabian/Pubblicazioni/jacm-97b.pdf), you can get a precise relationship between the Lipschitz constant and the generalization error.