License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.59
URN: urn:nbn:de:0030-drops-188849
URL: https://drops.dagstuhl.de/opus/volltexte/2023/18884/
Go to the corresponding LIPIcs Volume Portal


Blocki, Jeremiah ; Grigorescu, Elena ; Mukherjee, Tamalika ; Zhou, Samson

How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity

pdf-format:
LIPIcs-APPROX59.pdf (0.8 MB)


Abstract

We develop a framework for efficiently transforming certain approximation algorithms into differentially-private variants, in a black-box manner. Specifically, our results focus on algorithms A that output an approximation to a function f of the form (1-α)f(x)-κ ≤ A(x) ≤ (1+α)f(x)+κ, where κ ∈ ℝ_{≥ 0} denotes additive error and α ∈ [0,1) denotes multiplicative error can be"tuned" to small-enough values while incurring only a polynomial blowup in the running time/space. We show that such algorithms can be made differentially private without sacrificing accuracy, as long as the function f has small "global sensitivity". We achieve these results by applying the "smooth sensitivity" framework developed by Nissim, Raskhodnikova, and Smith (STOC 2007).
Our framework naturally applies to transform non-private FPRAS and FPTAS algorithms into ε-differentially private approximation algorithms where the former case requires an additional postprocessing step. We apply our framework in the context of sublinear-time and sublinear-space algorithms, while preserving the nature of the algorithm in meaningful ranges of the parameters. Our results include the first (to the best of our knowledge) ε-edge differentially-private sublinear-time algorithm for estimating the number of triangles, the number of connected components, and the weight of a minimum spanning tree of a graph whose accuracy holds with high probability. In the area of streaming algorithms, our results include ε-DP algorithms for estimating L_p-norms, distinct elements, and weighted minimum spanning tree for both insertion-only and turnstile streams. Our transformation also provides a private version of the smooth histogram framework, which is commonly used for converting streaming algorithms into sliding window variants, and achieves a multiplicative approximation to many problems, such as estimating L_p-norms, distinct elements, and the length of the longest increasing subsequence.

BibTeX - Entry

@InProceedings{blocki_et_al:LIPIcs.APPROX/RANDOM.2023.59,
  author =	{Blocki, Jeremiah and Grigorescu, Elena and Mukherjee, Tamalika and Zhou, Samson},
  title =	{{How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{59:1--59:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18884},
  URN =		{urn:nbn:de:0030-drops-188849},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.59},
  annote =	{Keywords: Differential privacy, approximation algorithms}
}

Keywords: Differential privacy, approximation algorithms
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Issue Date: 2023
Date of publication: 04.09.2023


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI