# Interpolation-Based Optimization for Enforcing lp-Norm Metric Differential Privacy in Continuous and Fine-Grained Domains

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 42 references that are in the map.
- First posted on arXiv 15 Jan 2026.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Privacy- and Utility-Preserving Textual Analysis via Calibrated Multivariate Perturbations](https://mlsanity.com/paper/1910.08902/) (2019)
- [Leveraging Hierarchical Representations for Preserving Privacy and Utility in Text](https://mlsanity.com/paper/1910.08917/) (2019)
- [TEM: High Utility Metric Differential Privacy on Text](https://mlsanity.com/paper/2107.07928/) (2021)
- [Perceptual Indistinguishability-Net (PI-Net): Facial Image Obfuscation with Manipulable Semantics](https://mlsanity.com/paper/2104.01753/) (2021)
- [Protecting Locations with Differential Privacy under Temporal Correlations](https://mlsanity.com/paper/1410.5919/) (2014)
- [Optimality of the Laplace Mechanism in Differential Privacy](https://mlsanity.com/paper/1504.00065/) (2015)
- [Voice-Indistinguishability: Protecting Voiceprint in Privacy-Preserving Speech Data Release](https://mlsanity.com/paper/2004.07442/) (2020)
- [Optimal Geo-Indistinguishable Mechanisms for Location Privacy](https://mlsanity.com/paper/1402.5029/) (2014)
- [Constructing elastic distinguishability metrics for location privacy](https://mlsanity.com/paper/1503.00756/) (2015)
- [Group privacy for personalized federated learning](https://mlsanity.com/paper/2206.03396/) (2022)
- [Author Obfuscation Using Generalised Differential Privacy](https://mlsanity.com/paper/1805.08866/) (2018)
- [User Customizable and Robust Geo-Indistinguishability for Location Privacy](https://mlsanity.com/paper/2206.08396/) (2022)
- [Is Geo-Indistinguishability What You Are Looking for?](https://mlsanity.com/paper/1709.06318/) (2017)
- [Enhancing Scalability of Metric Differential Privacy via Secret Dataset Partitioning and Benders Decomposition](https://mlsanity.com/paper/2405.04344/) (2024)

## Abstract (arXiv)

Metric Differential Privacy (mDP) generalizes Local Differential Privacy (LDP) by adapting privacy guarantees based on pairwise distances, enabling context-aware protection and improved utility. While existing optimization-based methods reduce utility loss effectively in coarse-grained domains, optimizing mDP in fine-grained or continuous settings remains challenging due to the computational cost of constructing dense perterubation matrices and satisfying pointwise constraints. In this paper, we propose an interpolation-based framework for optimizing lp-norm mDP in such domains. Our approach optimizes perturbation distributions at a sparse set of anchor points and interpolates distributions at non-anchor locations via log-convex combinations, which provably preserve mDP. To address privacy violations caused by naive interpolation in high-dimensional spaces, we decompose the interpolation process into a sequence of one-dimensional steps and derive a corrected formulation that enforces lp-norm mDP by design. We further explore joint optimization over perturbation distributions and privacy budget allocation across dimensions. Experiments on real-world location datasets demonstrate that our method offers rigorous privacy guarantees and competitive utility in fine-grained domains, outperforming baseline mechanisms. in high-dimensional spaces, we decompose the interpolation process into a sequence of one-dimensional steps and derive a corrected formulation that enforces lp-norm mDP by design. We further explore joint optimization over perturbation distributions and privacy budget allocation across dimensions. Experiments on real-world location datasets demonstrate that our method offers rigorous privacy guarantees and competitive utility in fine-grained domains, outperforming baseline mechanisms.