I have the following theorem in my textbook:

As the number of samples goes to infinity the error rate of 1-NN is no more than twice the Bayes error rate.

Proof sketch:

Abbreviate notation $P(c|x) := P(Y=c|x)$

The expected (Bayes) error of the Bayes classifier (at x) is $$1-\text{ max }_{c\in\{1,...,C\}}P(c|x)$$

and the expected rate of $1-NN$ (at x) is


observe that as the number of samples goes to infinity, $m\to \infty$,

$$P(c|x)\approx P(c|x_{nn})$$

thus the expected rate of 1-NN (at x) is $$\sum^C_{c=1}P(c|x)[1-P(c|x)]$$

We need to show $$\sum^C_{c=1}P(c|x)[1-P(c|x)]\leq 2[1-\text{ max }_{c\in\{1,...,C\}}P(c|x)]$$:

Let $c^*=\text{ argmax }_{c\in\{1,...,C\}}P(c|x)$ and $p^*=P(c^*|x)$. Observe that $$\sum^C_{c=1}P(c|x)[1-P(c|x)]=\sum^C_{c\neq c^*}P(c|x)[1-P(c|x)]+p^*(1-p^*)\\ \leq (C-1)\frac{1-p^*}{C-1}[1-\frac{1-p^*}{C-1}]+p^*(1-p^*)\\ = (1-p^*)[1-\frac{1-p^*}{C-1}+p^*]$$

Where the second line follows since the sum is maximised when all "$P(c|x)$" have the same value. And since $p^*<1$ we are done.

I don't completely understand how the second line follows. Could someone show me please?

  • $\begingroup$ Are you sure your expression for $c^* = \arg \max \dots$ is correct? $\endgroup$
    – jbowman
    Oct 4, 2021 at 18:19

2 Answers 2


Let's define $y_c:=P(c|x)$, $\forall{c} \in \{1,2,\ldots, C\}$, then we have $y_{c^{*}}=p^{*}$

Also, let $f\left(y_1,y_2,\ldots,y_{c^{*}-1},y_{c^{*}+1},\ldots,y_C\right)=\sum\limits_{c\neq c^{*}}y_c(1-y_c)$, this is the function we want to maximize (note the absence of $c^{*}$ in the variables).

Also, we have a constraint that $\sum\limits_{c=1}^{C}y_c=1$, since the posterior probabilities must sum to $1$.

Let's define the constraint function $g\left(y_1,y_2,\ldots,y_{c^{*}-1},y_{c^{*}+1},\ldots,y_C\right)=\sum\limits_{c\neq c^{*}}y_c + p^{*}-1=0$,

s.t. we have to maximize $f$ w.r.t. the constraint $g$.

It means we must have $\nabla f = \lambda \nabla g$ for some $\lambda$, when $f$ is an extremum (using the Lagrange multiplier).

$\implies \begin{align} \begin{bmatrix} 1-2y_1 \\ 1-2y_2 \\ \vdots \\ 1-2y_{c^{*}-1} \\ 1-2y_{c^{*}+1} \\ \vdots \\ 1-2y_{C} \end{bmatrix} \end{align}$ $=\lambda \begin{align} \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix} \end{align}$ $\implies y_c = \dfrac{\lambda-1}{2}$, $\forall{c} \neq c^{*}$

Also, we must have the constraint satisfied, i.e.,

$\sum\limits_{c\neq c^{*}}y_c + p^{*}-1=\sum\limits_{c\neq c^{*}}\dfrac{\lambda-1}{2}+p^{*}-1= 0$

$\implies (C-1)\dfrac{\lambda-1}{2}+p^{*}-1= 0$

$\implies y_c=\dfrac{\lambda-1}{2}=\dfrac{1-p^{*}}{C-1}$, $\forall{c} \neq c^{*}$

Hence, at maximum, we have,

$f_{max}\left(y_1,y_2,\ldots,y_{c^{*}-1},y_{c^{*}+1},\ldots,y_C\right)=\sum\limits_{c\neq c^{*}}y_c(1-y_c)=\sum\limits_{c\neq c^{*}}\dfrac{1-p^{*}}{C-1}\left(1-\dfrac{1-p^{*}}{C-1}\right)$


Now, since we have $f \leq f_{max}$,

$\implies \sum\limits^C_{c\neq c^*}P(c|x)[1-P(c|x)] \leq (C-1)\frac{1-p^*}{C-1}[1-\frac{1-p^*}{C-1}]$

$\implies \sum\limits^C_{c\neq c^*}P(c|x)[1-P(c|x)]+p^*(1-p^*) \leq (C-1)\frac{1-p^*}{C-1}[1-\frac{1-p^*}{C-1}]+p^*(1-p^*)$

  • $\begingroup$ thanks for the elaborate answer! $\endgroup$
    – Slim Shady
    Oct 5, 2021 at 8:59

Sorry, quick answer since I'm on my way out the door: you need to think about maximizing the curve

$$ \sum_{c\neq c^*} x_c(1-x_c)\,,\hspace{3em} \text{with } x_c\geq0\,,\hspace{3em}\text{and}\,\, \sum_{c\neq c*} = 1-x_{c^*}\,. $$

A bit of straightforward calculus (or noticing that $x(1-x)<x$ in the domain) will show you that this is maximized when $x_1=x_2=\ldots=x_{C}$, here when $x_c = (1-x_{c^*})/(C-1)$. So

$$ \sum_{c-c^*} P(c|x)[1-P(c|x)] \leq \sum_{c-c^*} P(c^*|x)[1-P(c^*|x)] = (C-1)P(c^*|x)[1-P(c^*|x)] = (C-1)\left(\frac{1-p^*}{C-1}\right)\left[1-\frac{1-p^*}{C-1}\right]\,. $$

The result follows.

  • $\begingroup$ How exactly did you know that it's maximized when $x_1=x_2=...=x_C$? Also, why exactly is $P(c^*|x)=\frac{1-p^*}{C-1}$? Isn't $P(c^*|x)=p^*$? Also, don't understand why $x_c=1(1-x_{c^*})/(C-1)$. Could you please elaborate on your answer? $\endgroup$
    – Slim Shady
    Oct 4, 2021 at 17:59
  • $\begingroup$ 1. The straight forward calculus is Lagrange Multiplies: to maximize $f(x)$ subject to $g(x)=c$, find the joint solution to $\nabla f(x) = \lambda \nabla g(x)$ and $g(x) = c$. This is pretty straight forward in this case if you know calculus, but if you don't writing out the computation isn't going to be fairly useful. I would give it a try yourself and ask if you have questions. 2. $P(c^*|x) \neq (1-p*)/(C-1)$, instead we're trying to find the maximum that the left hand side of my expression could possibly be to bound it. By (1), that maximum occurs when the probabilities are equal. $\endgroup$
    – Nate
    Oct 4, 2021 at 18:27
  • $\begingroup$ 3. If all $x_c$ are equal for $c\neq c^*$ then $1-p^* = \sum_{c\neq c^*} x_c = (1-C)x_c$, so $x_c = (1-p^*)/(1-C)$. $\endgroup$
    – Nate
    Oct 4, 2021 at 18:37

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.