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