Differential privacy via distributionally robust optimization
File(s)
Accepted version
Author(s)
Selvi, Aras
Liu, Huikang
Wiesemann, Wolfram
Type
Journal Article
Abstract
In recent years, differential privacy has emerged as the de facto standard for sharing statistics of data sets while limiting the disclosure of private information about the involved individuals. This is achieved by randomly perturbing the statistics to be published, which in turn, leads to a privacy-accuracy trade-off; larger perturbations provide stronger privacy guarantees, but they result in less accurate statistics that offer lower utility to the recipients. Of particular interest are, therefore, optimal mechanisms that provide the highest accuracy for a preselected level of privacy. To date, work in this area has focused on specifying families of perturbations a priori and subsequently proving their asymptotic and/or best-in-class optimality. In this paper, we develop a class of mechanisms that enjoy nonasymptotic and unconditional optimality guarantees. To this end, we formulate the mechanism design problem as an infinite-dimensional distributionally robust optimization problem. We show that the problem affords a strong dual, and we exploit this duality to develop converging hierarchies of finite-dimensional upper- and lower-bounding problems. Our upper (primal) bounds correspond to implementable perturbations whose suboptimality can be bounded by our lower (dual) bounds. Both bounding problems can be solved within seconds via cutting-plane techniques that exploit the inherent problem structure. Our numerical experiments demonstrate that our perturbations can outperform the previously best results from the literature on artificial as well as standard benchmark problems.
Date Issued
2026-01-01
Date Acceptance
2025-01-14
Citation
Operations Research, 2026, 74 (1), pp.356-376
ISSN
0030-364X
Publisher
Institute for Operations Research and Management Sciences
Start Page
356
End Page
376
Journal / Book Title
Operations Research
Volume
74
Issue
1
Copyright Statement
© 2025, INFORMS. This is the author’s accepted manuscript made available under a CC-BY licence in accordance with Imperial’s Research Publications Open Access policy (www.imperial.ac.uk/oa-policy)
License URL
Subjects
0102 Applied Mathematics
0802 Computation Theory and Mathematics
1503 Business and Management
Operations Research
Publication Status
Published
Date Publish Online
2025-03-10