A Nearest Neighbor Characterization of Lebesgue Points in Metric Measure Spaces
This work addresses a foundational theoretical issue for machine learning practitioners using nearest neighbor methods in general metric spaces, though it is incremental as it builds on existing Lebesgue point theory.
The paper tackles the problem of characterizing Lebesgue points in metric measure spaces to ensure consistency in nearest neighbor classification algorithms, proving convergence of risk for a broad class of such algorithms under conditions where almost every point is a Lebesgue point.
The property of almost every point being a Lebesgue point has proven to be crucial for the consistency of several classification algorithms based on nearest neighbors. We characterize Lebesgue points in terms of a 1-Nearest Neighbor regression algorithm for pointwise estimation, fleshing out the role played by tie-breaking rules in the corresponding convergence problem. We then give an application of our results, proving the convergence of the risk of a large class of 1-Nearest Neighbor classification algorithms in general metric spaces where almost every point is a Lebesgue point.