On Facility Location Problem in the Local Differential Privacy Model

Vincent Cohen-Addad, Yunus Esencayi, Chenglin Fan, Marco Gaboardi, Shi Li, Di WangAISTATS 2022 · OpenReview

Authors: Vincent Cohen-Addad, Yunus Esencayi, Chenglin Fan, Marco Gaboradi, Shi Li, Di Wang

Abstract: We study the facility location problem under the constraints imposed by local differential privacy (LDP). Recently, Gupta et al. (2010) and Esencayi et al. (2019) proposed lower and upper bounds for the problem on the central differential privacy (DP) model where a trusted curator first collects all data and processes it. In this paper, we focus on the LDP model, where we protect a client’s participation in the facility location instance. Under the HST metric, we show that there is a non-interactive $\epsilon$-LDP algorithm achieving $O(n^{1/4}/\epsilon^2)$-approximation ratio, where $n$ is the size of the metric. On the negative side, we show a lower bound of $\Omega(n^{1/4}/\sqrt{\epsilon})$ on the approximation ratio for any non-interactive $\epsilon$-LDP algorithm. Thus, our results are tight up to a polynomial factor of $\epsilon$. Moreover, unlike previous results, our results generalize to non-uniform facility costs.

Introduction

The Facility Location Problem (FL) is a fundamental challenge in combinatorial optimization. Given a set of potential facility locations and clients, the goal is to minimize the sum of facility opening costs and the distances clients must travel to reach their nearest open facility. In the era of big data, client locations are often sensitive, requiring privacy-preserving mechanisms.

While previous research has explored the Central Differential Privacy (DP) model—where a trusted server aggregates raw data before anonymization—this paper investigates the more stringent Local Differential Privacy (LDP) setting. In LDP, users do not trust the server; they apply noise to their own data locally before transmission. This setting is particularly challenging for FL because the problem is highly sensitive to noise in client distribution.

Problem Setting and Challenges

The authors address the "super-set output setting." In standard FL, an algorithm outputs a specific set of facilities to open. However, under privacy constraints, this can lead to massive errors. Instead, the algorithm provides a list of candidate facilities, and clients connect to the best available one. The fundamental question addressed is: What is the fundamental limit of accuracy for FL when every client provides only a locally privatized bit of information?

Methodology: The LDP-FL Framework

The authors develop a non-interactive protocol using several sophisticated theoretical tools:

1. HST Metrics and Tree Embedding

To handle complex geographic distances, the problem is embedded into Hierarchically Well-Separated Trees (HSTs). This standard technique allows the problem to be solved on a tree structure, where distances are defined by the height of the lowest common ancestor. This simplifies the optimization while maintaining a logarithmic approximation factor relative to general metrics.

2. Local Privacy via Randomized Response

To satisfy $\epsilon$-LDP, each client employs a randomized response mechanism. When queried about their presence at a location, they report a noisy bit. This ensures that the server cannot determine with certainty whether any specific individual participated in the dataset.

3. Noisy Tree Estimation and the Marking Strategy

The server aggregates these noisy bits to construct unbiased estimators for the number of clients in any given subtree. The core algorithm, LDP-FL-tree, utilizes a "marking" strategy. It decides whether to mark a facility as potentially open based on whether the estimated client count in its vicinity justifies the facility's opening cost. Calibration is critical: the algorithm must set thresholds that balance the risk of opening too many facilities against opening too few.

Theoretical Results and Insights

The paper provides the first comprehensive analysis of the approximation ratios possible under LDP for this problem.

The $n^{1/4}$ Barrier

The most significant finding is the jump in error between models. In Central DP, approximation ratios can be independent of the number of clients ($n$). However, the authors prove that in the LDP model, a penalty of $n^{1/4}$ is unavoidable. Specifically:

  • Upper Bound: $O(n^{1/4}/\epsilon^2)$ approximation for HST metrics.
  • Lower Bound: $\Omega(n^{1/4}/\sqrt{\epsilon})$ for any non-interactive LDP algorithm.

Generalization to Non-Uniform Costs

Unlike much of the existing literature which assumes uniform facility costs, this work generalizes to non-uniform costs. This demonstrates that the privacy-utility tradeoff is robust even when facility costs vary significantly across locations.

Correcting the Central DP Record

The authors identified a flaw in a prominent 2019 study regarding Central DP bounds. They provide a corrected algorithm for the central model that achieves an $O(1/\sqrt{\epsilon})$ ratio, matching known lower bounds and resolving a discrepancy in the field.

Conclusion and Future Directions

This research establishes the fundamental limits of the Facility Location Problem in the LDP setting. While the $n^{1/4}$ factor indicates a significant utility cost for local privacy, the results are nearly tight. Future work remains in exploring interactive LDP protocols to see if multiple rounds of communication could break the $n^{1/4}$ barrier, and closing the polynomial gap in the privacy parameter $\epsilon$.

Summary updated

Abstract

We study the facility location problem under the constraints imposed by local differential privacy (LDP). Recently, Gupta et al. (2010) and Esencayi et al. (2019) proposed lower and upper bounds for the problem on the central differential privacy (DP) model where a trusted curator first collects all data and processes it. In this paper, we focus on the LDP model, where we protect a client’s participation in the facility location instance. Under the HST metric, we show that there is a non-interactive $\epsilon$-LDP algorithm achieving $O(n^{1/4}/\epsilon^2)$-approximation ratio, where $n$ is the size of the metric. On the negative side, we show a lower bound of $\Omega(n^{1/4}/\sqrt{\epsilon})$ on the approximation ratio for any non-interactive $\epsilon$-LDP algorithm. Thus, our results are tight up to a polynomial factor of $\epsilon$. Moreover, unlike previous results, our results generalize to non-uniform facility costs.
BibTeX
@inproceedings{cohenaddad2022facility,
  author = {Vincent Cohen-Addad and Yunus Esencayi and Chenglin Fan and Marco Gaboardi and Shi Li and Di Wang},
  title = {{On Facility Location Problem in the Local Differential Privacy Model}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=T3bGxDBX28},
}
Figure