EUVIMEDEUVIMED entdecken
Crossref

Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries

Christian Janos Lebeda, Aleksandar Nikolov, Haohua Tang

Proceedings of the ACM on Management of Data · 12.05.2026 · 4 (2) · 1-23

DOI: 10.1145/3801919 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2026. Verfasst von Christian Janos Lebeda und 2 weiteren Autor:innen. Die Arbeit nennt 38 Literaturangaben. Gefördert von: NSERC Discovery Grant, Agence Nationale de la Recherche, Canada Research Chairs.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We revisit the task of releasing marginal queries under differential privacy with additive (correlated) Gaussian noise. We first give a construction for answering arbitrary workloads of weighted marginal queries, over arbitrary domains. Our technique is based on releasing queries in the Fourier basis with independent noise with carefully calibrated variances, and reconstructing the marginal query answers using the inverse Fourier transform. We show that our algorithm, which is a factorization mechanism, is exactly optimal among all factorization mechanisms, both for minimizing the sum of weighted noise variances, and for minimizing the maximum noise variance. Unlike algorithms based on optimizing over all factorization mechanisms via semidefinite programming, our mechanism runs in time polynomial in the dataset and the output size. This construction recovers results of Xiao et al. [Neurips 2023] with a simpler algorithm and optimality proof, and a better running time. We then extend our approach to a generalization of marginals which we refer to as product queries. We show that our algorithm is still exactly optimal for this more general class of queries. Finally, we show how to embed extended marginal queries, which allow using a threshold predicate on numerical attributes, into product queries. We show that our mechanism is almost optimal among all factorization mechanisms for extended marginals, in the sense that it achieves the optimal (maximum or average) noise variance up to lower order terms.

Förderung

  • NSERC Discovery Grant
  • Agence Nationale de la Recherche
  • Canada Research Chairs

Zitieren

APA

Lebeda, C. J., Nikolov, A., & Tang, H. (2026). Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries. Proceedings of the ACM on Management of Data, 4(2), 1-23. https://doi.org/10.1145/3801919

Vancouver

Lebeda CJ, Nikolov A, Tang H. Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries. Proceedings of the ACM on Management of Data. 2026;4(2):1-23. doi:10.1145/3801919

BibTeX
@article{Lebeda2026,
  author = {Lebeda, Christian Janos and Nikolov, Aleksandar and Tang, Haohua},
  title = {Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {2},
  pages = {1--23},
  doi = {10.1145/3801919}
}
Kostenlos starten →