PAnDA: Rethinking Metric Differential Privacy Optimization at Scale with Anchor-Based Approximation

• URL: http://arxiv.org/abs/2509.08720v1
• Date: Wed, 10 Sep 2025 16:14:08 GMT
• Title: PAnDA: Rethinking Metric Differential Privacy Optimization at Scale with Anchor-Based Approximation
• Authors: Ruiyao Liu, Chenxi Qiu,
• Abstract summary: We propose Perturbation via Anchor-based Distributed Approximation (PAnDA) as a scalable framework for metric differential privacy (mDP)<n>Experiments on real-world geo-location datasets demonstrate that PAnDA scales to secret domains with up to 5,000 records, two times larger than prior LP-based methods.
• Score: 7.889420673572309
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Metric Differential Privacy (mDP) extends the local differential privacy (LDP) framework to metric spaces, enabling more nuanced privacy protection for data such as geo-locations. However, existing mDP optimization methods, particularly those based on linear programming (LP), face scalability challenges due to the quadratic growth in decision variables. In this paper, we propose Perturbation via Anchor-based Distributed Approximation (PAnDA), a scalable two-phase framework for optimizing metric differential privacy (mDP). To reduce computational overhead, PAnDA allows each user to select a small set of anchor records, enabling the server to solve a compact linear program over a reduced domain. We introduce three anchor selection strategies, exponential decay (PAnDA-e), power-law decay (PAnDA-p), and logistic decay (PAnDA-l), and establish theoretical guarantees under a relaxed privacy notion called probabilistic mDP (PmDP). Experiments on real-world geo-location datasets demonstrate that PAnDA scales to secret domains with up to 5,000 records, two times larger than prior LP-based methods, while providing theoretical guarantees for both privacy and utility.

Related papers

• Interpolation-Based Optimization for Enforcing lp-Norm Metric Differential Privacy in Continuous and Fine-Grained Domains [9.320305401683438]
  Metric Differential Privacy (mDP) generalizes Local Differential Privacy (LDP) by adapting privacy guarantees based on pairwise distances.<n>Existing optimization-based methods reduce utility loss effectively in coarse-grained domains.<n>We propose an computational-based framework for optimizing lp-norm mDP in such domains.
  arXiv  Detail & Related papers  (2026-01-15T00:12:54Z)
• Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
  User-level differentially private convex optimization (DP-SCO) has garnered significant attention due to the importance of safeguarding user privacy in machine learning applications.<n>Current methods, such as those based on differentially private gradient descent (DP-SGD), often struggle with high noise accumulation and suboptimal utility.<n>We introduce a novel linear-time algorithm that leverages robust statistics, specifically the median and trimmed mean, to overcome these challenges.
  arXiv  Detail & Related papers  (2025-02-13T02:05:45Z)
• Differentially Private Policy Gradient [48.748194765816955]
  We show that it is possible to find the right trade-off between privacy noise and trust-region size to obtain a performant differentially private policy gradient algorithm.<n>Our results and the complexity of the tasks addressed represent a significant improvement over existing DP algorithms in online RL.
  arXiv  Detail & Related papers  (2025-01-31T12:11:13Z)
• Enhancing Scalability of Metric Differential Privacy via Secret Dataset Partitioning and Benders Decomposition [1.283608820493284]
  Metric Differential Privacy (mDP) extends the concept of Differential Privacy (DP) to serve as a new paradigm of data. It is designed to protect secret data represented in general metric space, such as text data encoded as word embeddings or geo-location data on the road network or grid maps.
  arXiv  Detail & Related papers  (2024-05-07T14:19:09Z)
• Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under Streaming Differential Privacy [47.997934291881414]
  Existing mean estimation schemes are usually optimized for $L_infty$ geometry and rely on random rotation or Kashin's representation to adapt to $L$ geometry. We introduce a novel privacy accounting method for the sparsified Gaussian mechanism that incorporates the randomness inherent in sparsification into the DP. Unlike previous approaches, our accounting algorithm directly operates in $L$ geometry, yielding MSEs that fast converge to those of the Gaussian mechanism.
  arXiv  Detail & Related papers  (2024-05-02T03:48:47Z)
• Differentially Private Zeroth-Order Methods for Scalable Large Language Model Finetuning [0.0]
  differentially private (DP) fine-tuning of pretrained LLMs has been widely used to safeguarding the privacy of task-specific datasets.<n>Despite pushing the scalability of DP-SGD to its limit, DP-SGD-based fine-tuning methods are unfortunately limited by the inherent inefficiency of SGD.
  arXiv  Detail & Related papers  (2024-02-12T17:24:15Z)
• Adaptive Differentially Quantized Subspace Perturbation (ADQSP): A Unified Framework for Privacy-Preserving Distributed Average Consensus [6.364764301218972]
  We propose a general approach named adaptive differentially quantized subspace (ADQSP) We show that by varying a single quantization parameter the proposed method can vary between SMPC-type performances and DP-type performances. Our results show the potential of exploiting traditional distributed signal processing tools for providing cryptographic guarantees.
  arXiv  Detail & Related papers  (2023-12-13T07:52:16Z)
• DPZero: Private Fine-Tuning of Language Models without Backpropagation [49.365749361283704]
  We introduce DPZero, a novel private zeroth-order algorithm with nearly dimension-independent rates. The memory efficiency of DPZero is demonstrated in privately fine-tuning RoBERTa and OPT on several downstream tasks.
  arXiv  Detail & Related papers  (2023-10-14T18:42:56Z)
• Theoretically Principled Federated Learning for Balancing Privacy and Utility [61.03993520243198]
  We propose a general learning framework for the protection mechanisms that protects privacy via distorting model parameters. It can achieve personalized utility-privacy trade-off for each model parameter, on each client, at each communication round in federated learning.
  arXiv  Detail & Related papers  (2023-05-24T13:44:02Z)
• FedLAP-DP: Federated Learning by Sharing Differentially Private Loss Approximations [53.268801169075836]
  We propose FedLAP-DP, a novel privacy-preserving approach for federated learning. A formal privacy analysis demonstrates that FedLAP-DP incurs the same privacy costs as typical gradient-sharing schemes. Our approach presents a faster convergence speed compared to typical gradient-sharing methods.
  arXiv  Detail & Related papers  (2023-02-02T12:56:46Z)
• Differentially Private Decentralized Optimization with Relay Communication [1.2695958417031445]
  We introduce a new measure: Privacy Leakage Frequency (PLF), which reveals the relationship between communication and privacy leakage of algorithms.<n>A novel differentially private decentralized primal--dual algorithm named DP-RECAL is proposed to take advantage of operator splitting method and relay communication mechanism to experience less PLF.
  arXiv  Detail & Related papers  (2022-12-21T09:05:36Z)
• Local Differential Privacy for Bayesian Optimization [12.05395706770007]
  We consider a black-box optimization in the nonparametric Gaussian process setting with local differential privacy (LDP) guarantee. Specifically, the rewards from each user are further corrupted to protect privacy and the learner only has access to the corrupted rewards to minimize the regret. We present three almost optimal algorithms based on the GP-UCB framework and Laplace DP mechanism.
  arXiv  Detail & Related papers  (2020-10-13T21:50:09Z)
• User-Level Privacy-Preserving Federated Learning: Analysis and Performance Optimization [77.43075255745389]
  Federated learning (FL) is capable of preserving private data from mobile terminals (MTs) while training the data into useful models. From a viewpoint of information theory, it is still possible for a curious server to infer private information from the shared models uploaded by MTs. We propose a user-level differential privacy (UDP) algorithm by adding artificial noise to the shared models before uploading them to servers.
  arXiv  Detail & Related papers  (2020-02-29T10:13:39Z)

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.