General-distribution nearest-neighbor optimality conjecture

About 2 years old · traced to 2024

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.

References

Primary source

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

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A posted counterexample claims the rule can perform worse than chance and fail to be best, but this has not been independently verified.

Kevin Bleakley posed the conjecture in 2024: with arbitrary one-dimensional distributions, classifying a mixture observation by whichever of one sample from each distribution is nearer should beat chance and be optimal among distribution-free rules.

Known results

Bleakley (2024): the above-chance guarantee is proved for Gaussian distributions, including unknown unequal variances.
Bleakley (2024): optimality is explicitly left open, even in the Gaussian settings.
Bleakley (2024): the general case is reduced to an integral inequality, for which the manuscript reports no proof or disproof.

Posted attempt

A posted construction using compactly supported densities claims success probability $255/512<1/2$ , with a reversed rule achieving $257/512$ ; it therefore claims a complete counterexample to both conjectures. The calculation has not been independently verified.

Current status (as of August 2026): The Gaussian above-chance result is recorded, but the general claim and optimality remain unverified; a posted counterexample would refute both if correct.

Sources

arxiv.org

CounterexampleThis solution needs a summarySee full solutionHide full solution

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.