Facility Location Problem under Local Differential Privacy without Super-set Assumption

• URL: http://arxiv.org/abs/2506.15224v1
• Date: Wed, 18 Jun 2025 08:08:12 GMT
• Title: Facility Location Problem under Local Differential Privacy without Super-set Assumption
• Authors: Kevin Pfisterer, Quentin Hillebrand, Vorapong Suppakitpaisarn,
• Abstract summary: We introduce an adaptation of the facility location problem and analyze it within the framework of local differential privacy (LDP)<n>Under this model, we ensure the privacy of client presence at specific locations.<n>We provide experimental results demonstrating that our algorithm outperforms the straightforward approach on both synthetically generated and real-world datasets.
• Score: 1.9749268648715583
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we introduce an adaptation of the facility location problem and analyze it within the framework of local differential privacy (LDP). Under this model, we ensure the privacy of client presence at specific locations. When n is the number of points, Gupta et al. established a lower bound of $\Omega(\sqrt{n})$ on the approximation ratio for any differentially private algorithm applied to the original facility location problem. As a result, subsequent works have adopted the super-set assumption, which may, however, compromise user privacy. We show that this lower bound does not apply to our adaptation by presenting an LDP algorithm that achieves a constant approximation ratio with a relatively small additive factor. Additionally, we provide experimental results demonstrating that our algorithm outperforms the straightforward approach on both synthetically generated and real-world datasets.

Related papers

• Instance-Optimality for Private KL Distribution Estimation [41.35506763248454]
  We study the fundamental problem of estimating an unknown discrete distribution $p$ over $d$ symbols, given $n$ i.i.d. samples from the distribution.<n>We propose algorithms that achieve instance-optimality up to constant factors, with and without a differential privacy constraint.
  arXiv  Detail & Related papers  (2025-05-29T16:27:57Z)
• Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimization [30.45012237666837]
  We consider the problem of differentially private convex optimization (DP-SCO) in a distributed setting with $M$ clients.<n>The objective is to design an algorithm to minimize a convex population loss using a collaborative effort across $M$ clients.<n>We establish matching converse and achievability results using a novel lower bound and a new algorithm for distributed DP-SCO.
  arXiv  Detail & Related papers  (2025-01-06T18:57:05Z)
• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  We introduce a new adaptive $k$-nearest neighbours ($kK$-NN) algorithm that explores the local curvature at a sample to adaptively defining the neighborhood size. Results on many real-world datasets indicate that the new $kK$-NN algorithm yields superior balanced accuracy compared to the established $k$-NN method.
  arXiv  Detail & Related papers  (2024-09-08T13:08:45Z)
• Dynamic Privacy Allocation for Locally Differentially Private Federated Learning with Composite Objectives [10.528569272279999]
  This paper proposes a differentially private federated learning algorithm for strongly convex but possibly nonsmooth problems. The proposed algorithm adds artificial noise to the shared information to ensure privacy and dynamically allocates the time-varying noise variance to minimize an upper bound of the optimization error. Numerical results show the superiority of the proposed algorithm over state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-08-02T13:30:33Z)
• Instance-Optimal Differentially Private Estimation [2.320417845168326]
  We study local minimax convergence estimation rates subject to $epsilon$-differential privacy. We show that optimal algorithms for simple hypothesis testing, namely the recent optimal private testers of Canonne et al., directly inform the design of locally minimax estimation algorithms.
  arXiv  Detail & Related papers  (2022-10-28T01:08:01Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  Modern machine learning algorithms aim to extract fine-grained information from data to provide accurate predictions, which often conflicts with the goal of privacy protection. This paper addresses the practical and theoretical importance of developing privacy-preserving machine learning algorithms that ensure good performance while preserving privacy.
  arXiv  Detail & Related papers  (2022-09-09T08:54:13Z)
• Private Domain Adaptation from a Public Source [48.83724068578305]
  We design differentially private discrepancy-based algorithms for adaptation from a source domain with public labeled data to a target domain with unlabeled private data. Our solutions are based on private variants of Frank-Wolfe and Mirror-Descent algorithms.
  arXiv  Detail & Related papers  (2022-08-12T06:52:55Z)
• Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging [20.39986955578245]
  We introduce pairwise network differential privacy, a relaxation of Local Differential Privacy (LDP) We derive a differentially private decentralized optimization algorithm that alternates between local gradient descent steps and gossip averaging. Our results show that our algorithms amplify privacy guarantees as a function of the distance between nodes in the graph.
  arXiv  Detail & Related papers  (2022-06-10T13:32:35Z)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  We show that PrivUnit achieves the optimal variance among a large family of locally private randomizers. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees.
  arXiv  Detail & Related papers  (2022-05-05T06:43:46Z)
• 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)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  We show that random shuffling amplifies differential privacy guarantees of locally randomized data. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees.
  arXiv  Detail & Related papers  (2020-12-23T17:07:26Z)

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.