On public and private binary classification with metric space valued predictors

• URL: http://arxiv.org/abs/2605.31184v1
• Date: Fri, 29 May 2026 11:54:13 GMT
• Title: On public and private binary classification with metric space valued predictors
• Abstract summary: 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 $ pm 1 $.
• Score: 3.925313161884993
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $\{ \pm 1 \}$. In the first part of this work, we assume that one has direct access to an i.i.d. sample $(X_1,Y_1),\ldots,(X_n,Y_n)$ 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 $(X_1,Y_1),\ldots,(X_n,Y_n)$ 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.

Related papers

• Private Model Personalization Revisited [13.4143747448136]
  We study model personalization under user-level differential privacy (DP) in the shared representation framework.<n>Our goal is to privately recover the shared embedding and the local low-dimensional representations with small excess risk.<n>We present an information-theoretic construction to privately learn the shared embedding and derive a margin-based accuracy guarantee.
  arXiv  Detail & Related papers  (2025-06-24T00:57:17Z)
• Beyond Laplace and Gaussian: Exploring the Generalized Gaussian Mechanism for Private Machine Learning [49.66162382667325]
  We investigate the Generalized Gaussian mechanism, which samples the additive noise term $x$ with probability proportional to $e-frac| x |sigmabeta $ for some $beta geq 1$.<n>We show that privacy accounting for the GG Mechanism and its variants is independent, which substantially improves computational costs of privacy accounting.
  arXiv  Detail & Related papers  (2025-06-14T15:49:25Z)
• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  We introduce the Data-dependent Randomized Response Majority (DaRRM) algorithm.<n>DaRRM is parameterized by a data-dependent noise function $gamma$, and enables efficient utility optimization over the class of all private algorithms.<n>We show that DaRRM provably enjoys a privacy gain of a factor of 2 over common baselines, with fixed utility.
  arXiv  Detail & Related papers  (2024-11-27T00:48:48Z)
• On Differentially Private U Statistics [25.683071759227293]
  We propose a new thresholding-based approach using emphlocal H'ajek projections to reweight different subsets of the data. This leads to nearly optimal private error for non-degenerate U-statistics and a strong indication of near-optimality for degenerate U-statistics.
  arXiv  Detail & Related papers  (2024-07-06T03:27:14Z)
• On Rate-Optimal Partitioning Classification from Observable and from Privatised Data [4.2931743492904095]
  We revisit the classical method of partitioning classification and study its convergence rate under relaxed conditions.<n>We consider the problem of classification in a $d$ dimensional Euclidean space.
  arXiv  Detail & Related papers  (2023-12-22T18:07:18Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  A classical approach to private mean estimation is to compute the true mean and add unbiased, but possibly correlated, Gaussian noise to it. We show that for every input dataset, an unbiased mean estimator satisfying concentrated differential privacy introduces approximately at least as much error.
  arXiv  Detail & Related papers  (2023-01-31T18:47:42Z)
• Smooth Anonymity for Sparse Graphs [69.1048938123063]
  differential privacy has emerged as the gold standard of privacy, however, when it comes to sharing sparse datasets. In this work, we consider a variation of $k$-anonymity, which we call smooth-$k$-anonymity, and design simple large-scale algorithms that efficiently provide smooth-$k$-anonymity.
  arXiv  Detail & Related papers  (2022-07-13T17:09:25Z)
• Nonparametric extensions of randomized response for private confidence sets [51.75485869914048]
  This work derives methods for performing nonparametric, nonasymptotic statistical inference for population means under the constraint of local differential privacy (LDP) We present confidence intervals (CI) and time-uniform confidence sequences (CS) for $mustar$ when only given access to the privatized data.
  arXiv  Detail & Related papers  (2022-02-17T16:04:49Z)
• Locally differentially private estimation of nonlinear functionals of discrete distributions [9.028773906859541]
  We study the problem of estimating non-linear functionals of discrete distributions in the context of local differential privacy. Only $alpha$-locally differentially private (LDP) samples are publicly available, where the term 'local' means that each $z_i$ is produced using one individual $x_i$. We describe the behavior of the quadratic risk for estimating the power sum functional $F_gamma = sum_k=1K p_kgamma$, $gamma >0$ as a function of $K,, n
  arXiv  Detail & Related papers  (2021-07-08T16:11:10Z)
• Achieving differential privacy for $k$-nearest neighbors based outlier detection by data partitioning [0.3437656066916039]
  We develop a differentially private ($epsilon$-DP) approach for $k$-NN based outlier detection. We propose a method for $k$-NN based outlier detection by separating the procedure into a fitting step on reference inlier data and then apply the outlier classifier to new data. Our approach yields nearly optimal performance on real-world data with varying dimensions when compared to the non-private versions of $k$-NN.
  arXiv  Detail & Related papers  (2021-04-16T07:35:26Z)
• Learning with User-Level Privacy [61.62978104304273]
  We analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints. Rather than guaranteeing only the privacy of individual samples, user-level DP protects a user's entire contribution. We derive an algorithm that privately answers a sequence of $K$ adaptively chosen queries with privacy cost proportional to $tau$, and apply it to solve the learning tasks we consider.
  arXiv  Detail & Related papers  (2021-02-23T18:25:13Z)
• Strongly universally consistent nonparametric regression and classification with privatised data [2.879036956042183]
  We revisit the classical problem of nonparametric regression, but impose local differential privacy constraints. We design a novel estimator of the regression function, which can be viewed as a privatised version of the well-studied partitioning regression estimator.
  arXiv  Detail & Related papers  (2020-10-31T09:00:43Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.