# On public and private binary classification with metric space valued predictors

arXiv: https://arxiv.org/abs/2605.31184 · HTML: https://mlsanity.com/paper/2605.31184/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 23 references that are in the map.
- First posted on arXiv 29 May 2026.

## Builds on (most cited first, 8 of 8)

- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces](https://mlsanity.com/paper/2010.00636/) (2020)
- [Achieving the time of 1-NN, but the accuracy of k-NN](https://mlsanity.com/paper/1712.02369/) (2017)
- [Classification under local differential privacy](https://mlsanity.com/paper/1912.04629/) (2019)
- [Strongly universally consistent nonparametric regression and classification with privatised data](https://mlsanity.com/paper/2011.00216/) (2020)
- [An adaptive multiclass nearest neighbor classifier](https://mlsanity.com/paper/1804.02756/) (2018)
- [Multivariate density estimation from privatised data: universal consistency and minimax rates](https://mlsanity.com/paper/2107.12649/) (2021)
- [On Rate-Optimal Partitioning Classification from Observable and from Privatised Data](https://mlsanity.com/paper/2312.14889/) (2023)

## Abstract (arXiv)

We consider the problem of binary classification in a framework where the predictor X takes values in an arbitrary separable metric space mathcal X and the label Y values in  ± 1 . In the first part of this work, we assume that one has direct access to an i.i.d. sample (X1,Y1),ldots,(Xn,Yn) from the unknown distribution of the pair (X,Y). We derive a convergence rate for the Proto-NN classifier which was recently introduced as a classifier in the presence of metric space-valued predictors. In the second part of the paper, we reconsider the same problem under an additional privacy constraint. More precisely, we work in the framework of local differential privacy where one assumes that the data (X1,Y1),ldots,(Xn,Yn) cannot be directly observed but only a privatised surrogate obtained through a suitable mechanism satisfying the privacy constraint is available. The statistician should select an optimal privacy mechanism from the class of all mechanism that guarantee local differential privacy. Our method of choice is to add Laplace distributed noise to both a set of in Proto-NN classifier using the privatised data only is universally consistent. Finally, a rate of convergence for the privatised Proto-NN classifier is derived.