A nearest-neighbor rule can have unit deletion instability and zero training loss

Let $\mathsf{X}=\mathbb{R}$ with its Borel sigma-algebra and distance $d(x,x^{\mathrm{\prime }})=\mathrm{\mid }x-x^{\mathrm{\prime }}\mathrm{\mid }$, and let $\mathsf{Y}=\mathsf{A}=\{0,1\}$ with the discrete sigma-algebra. Let $P$ be any probability measure on $(\mathsf{X}\times \mathsf{Y},\mathcal{B}(\mathbb{R})\otimes 2^{\{0,1\}})$, let $\mathcal{F}$ be the class of all Borel-measurable predictors $h:\mathsf{X}\to \mathsf{A}$, and use the zero-one loss $\mathrm{\ell }(a,y)=\mathbf{1}\{a\mathrm{\ne }y\}$, so $L(h,(x,y))=\mathrm{\ell }(h(x),y)$. Define a deterministic one-nearest-neighbor rule that predicts the majority label among all sample points at minimum distance from $x$, resolving a tie by predicting $0$; on the empty sample it predicts $1$ everywhere. For a fixed finite sample, each nearest-index region is specified by finitely many distance comparisons and is Borel, so the resulting predictor belongs to $\mathcal{F}$. This rule is permutation-invariant. For any $m\ge 2$, let $S$ contain one observation $(0,0)$ and $m-1$ copies of $(10,1)$. Its empirical risk is zero. At the test point $(1,1)$ the full rule predicts $0$ and incurs loss $1$, while the rule after deleting $(0,0)$ predicts $1$ and incurs loss $0$. Since the loss is bounded by $1$, the uniform deletion-stability coefficient at size $m$ is exactly $1$.

Uniform deletion stability is defined by Uniform algorithmic stability under deletion.

The supervised sample and loss setting is specified by Supervised prediction problems.

Empirical risk is the finite sample average by Population and empirical risk.