General-distribution nearest-neighbor optimality conjecture

From papers

Let $X$ and $Z$ be independent draws from arbitrary unknown probability distributions with densities $f_X$ and $f_Z$ , satisfying

\int_{\mathbb{R}} |f_X(w)-f_Z(w)|\,dw>0.

Let $Y$ be drawn from the mixture distribution

Y\sim \frac{1}{2}f_X+\frac{1}{2}f_Z.

The decision rule classifies $Y=y$ as coming from $f_X$ when $|x-y|<|z-y|$ , and from $f_Z$ otherwise. Nearest-neighbor optimality conjecture. This rule is correct more than half the time and minimizes classification error among all decision rules. The paper establishes the result for Gaussian densities, while the general-distribution claim and optimality remain open.

Progress summary

Open

The general claim remains unproved: only Gaussian cases are established, and no verified counterexample or solution was found.

The conjecture says that, for distinct one-dimensional distributions with densities, classifying a mixture observation by whichever sample is nearer should beat chance and minimize classification error. The available manuscript records this as a conjecture for arbitrary distributions and gives no general proof.

Known results

Gaussian distributions with equal variance: nearest-neighbor classification is correct more than half the time.
Gaussian distributions with different variances: the same above-chance guarantee holds.
Optimality among all decision rules remains open even in the Gaussian settings described.
The arbitrary-density section gives calculations and conjectures, explicitly without proof.

Current status (as of August 2026): The general-distribution conjecture and the claimed optimality remain open; the verified record contains only Gaussian above-chance results, not a proof, counterexample, or corroborated solution.

Sources

arxiv.org

Sources & referencesView supporting material

Primary source

Kevin Bleakley, “Extreme change-point detection”, arXiv:2403.19237 (2024).

1 week ago

The nearest-neighbor rule can perform strictly worse than a coin flip, even when both distributions have probability densities.

For $c\in\mathbb R$ , let

u_c(t)=5\mathbf1_{\{|t-c|<1/10\}},

and take the distinct probability densities

f_X=\frac14u_2+\frac34u_5, \qquad f_Z=\frac18u_0+\frac18u_3+\frac34u_5.

At centers $(0,2,3,5)$ , their component masses are

p=(0,1/4,0,3/4), \qquad q=(1/8,0,1/8,3/4).

Write $D=F_X-F_Z$ . Conditional on labeled observations $X=x<z=Z$ , the nearest-neighbor classifier has success probability

\frac12+\frac12D\left(\frac{x+z}{2}\right).

For $x>z$ , the sign of the second term reverses. Therefore its unconditional success probability is

\frac12+ \frac12\int_{x<z} D\left(\frac{x+z}{2}\right) \bigl(f_X(x)f_Z(z)-f_X(z)f_Z(x)\bigr)\,dx\,dz.

For component centers $c_i<c_j$ , all midpoints lie inside a common gap between supports, so $D$ is constant on that block. The complete block data are

\begin{array}{c|c|c} (c_i,c_j)&D((c_i+c_j)/2)&p_iq_j-p_jq_i\\ \hline (0,2)&-1/8&-1/32\\ (0,3)&-1/8&0\\ (0,5)&1/8&-3/32\\ (2,3)&1/8&1/32\\ (2,5)&0&3/16\\ (3,5)&0&-3/32 \end{array}

Hence the excess success probability equals

\frac1{512}-\frac3{512}+\frac1{512} =-\frac1{512},

and consequently

\Pr(\text{nearest-neighbor prediction correct}) =\frac{255}{512}<\frac12.

The reverse nearest-neighbor rule instead succeeds with probability $257/512$ . Thus the nearest-neighbor rule neither necessarily beats chance nor minimizes classification error.

Replacing every $u_c$ by a translate of the same normalized smooth bump supported in $(-1/10,1/10)$ leaves all block calculations unchanged, so the counterexample also holds for smooth densities.

0 endorsements

Shivam Patel · 22 hours ago