The Power of Input Perturbation: Differentially Private Learning from Pairwise Distances

Differential privacy (DP) has been extensively studied for metric learning problems within specific geometric contexts, such as Euclidean space. However, in many applications, the input metric is available only as a matrix of pairwise distances. This paper systematically investigates the power of *input perturbation* for pairwise distances in general metric spaces under the $\rho$-distance-based DP model. The approach is remarkably simple: we add independent Gaussian noise to the pairwise distance entries, optionally repair the matrix to the nearest metric, and release the matrix for downstream tasks. This mechanism offers significant practical utility, as a single privatized distance matrix can be reused across various downstream applications. Despite this simplicity, we prove that this method achieves a nearly tight $\tilde{O}(\rho \sqrt{n\log (1/\delta )}/\epsilon )$ additive error for $(\epsilon ,\delta )$-DP metric release. We further apply this approach to a host of metric learning tasks, including minimum spanning trees (MST), $k$-clustering, hierarchical clustering (HC), and coresets, leading to bounds that are either tight or match the state-of-the-art. Experiments on 12 datasets demonstrate the advantages of this approach in terms of utility and time complexity compared to existing benchmarks. The experiments also reveal error-efficiency trade-offs via different metric repair strategies for practical private metric release.