DROPS

Document

DOI: 10.4230/LIPIcs.FORC.2025.2

Smooth Sensitivity Revisited: Towards Optimality

Authors: Richard Hladík and Jakub Tětek

Published in: LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025)

Abstract

Smooth sensitivity is one of the most commonly used techniques for designing practical differentially private mechanisms. In this approach, one computes the smooth sensitivity of a given query q on the given input D and releases q(D) with noise added proportional to this smooth sensitivity. One question remains: what distribution should we pick the noise from? In this paper, we give a new class of distributions suitable for the use with smooth sensitivity, which we name the PolyPlace distribution. This distribution improves upon the state-of-the-art Student’s T distribution in terms of standard deviation by arbitrarily large factors, depending on a "smoothness parameter" γ, which one has to set in the smooth sensitivity framework. Moreover, our distribution is defined for a wider range of parameter γ, which can lead to significantly better performance. Furthermore, we prove that the PolyPlace distribution converges for γ → 0 to the Laplace distribution and so does its variance. This means that the Laplace mechanism is a limit special case of the PolyPlace mechanism. This implies that our mechanism is in a certain sense optimal for γ → 0.

Cite as

Richard Hladík and Jakub Tětek. Smooth Sensitivity Revisited: Towards Optimality. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hladik_et_al:LIPIcs.FORC.2025.2,
  author =	{Hlad{\'\i}k, Richard and T\v{e}tek, Jakub},
  title =	{{Smooth Sensitivity Revisited: Towards Optimality}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{2:1--2:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-367-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{329},
  editor =	{Bun, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.2},
  URN =		{urn:nbn:de:0030-drops-231292},
  doi =		{10.4230/LIPIcs.FORC.2025.2},
  annote =	{Keywords: differential privacy, smooth sensitivity}
}

Document

DOI: 10.4230/LIPIcs.FORC.2025.6

Near-Universally-Optimal Differentially Private Minimum Spanning Trees

Authors: Richard Hladík and Jakub Tětek

Published in: LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025)

Abstract

Devising mechanisms with good beyond-worst-case input-dependent performance has been an important focus of differential privacy, with techniques such as smooth sensitivity, propose-test-release, or inverse sensitivity mechanism being developed to achieve this goal. This makes it very natural to use the notion of universal optimality in differential privacy. Universal optimality is a strong instance-specific optimality guarantee for problems on weighted graphs, which roughly states that for any fixed underlying (unweighted) graph, the algorithm is optimal in the worst-case sense, with respect to the possible setting of the edge weights. In this paper, we give the first such result in differential privacy. Namely, we prove that a simple differentially private mechanism for approximately releasing the minimum spanning tree is near-optimal in the sense of universal optimality for the 𝓁₁ neighbor relation. Previously, it was only known that this mechanism is nearly optimal in the worst case. We then focus on the 𝓁_∞ neighbor relation, for which the described mechanism is not optimal. We show that one may implement the exponential mechanism for MST in polynomial time, and that this results in universal near-optimality for both the 𝓁₁ and the 𝓁_∞ neighbor relations.

Cite as

Richard Hladík and Jakub Tětek. Near-Universally-Optimal Differentially Private Minimum Spanning Trees. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hladik_et_al:LIPIcs.FORC.2025.6,
  author =	{Hlad{\'\i}k, Richard and T\v{e}tek, Jakub},
  title =	{{Near-Universally-Optimal Differentially Private Minimum Spanning Trees}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-367-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{329},
  editor =	{Bun, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.6},
  URN =		{urn:nbn:de:0030-drops-231337},
  doi =		{10.4230/LIPIcs.FORC.2025.6},
  annote =	{Keywords: differential privacy, universal optimality, minimum spanning trees}
}

Search Results

Documents authored by Hladík, Richard

Smooth Sensitivity Revisited: Towards Optimality

Abstract

Cite as

Near-Universally-Optimal Differentially Private Minimum Spanning Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message