TY - GEN
T1 - Optimal Multidimensional Differentially Private Mechanisms in the Large-Composition Regime
AU - Alghamdi, Wael
AU - Asoodeh, Shahab
AU - Calmon, Flavio P.
AU - Felipe Gomez, Juan
AU - Kosut, Oliver
AU - Sankar, Lalitha
N1 - Publisher Copyright:
© 2023 IEEE.
PY - 2023
Y1 - 2023
N2 - We construct vector differentially-private (DP) mechanisms that are asymptotically optimal in the limit of the number of compositions growing without bound. First, we derive via the central limit theorem a reduction from DP to a KL-divergence minimization problem. Second, we formulate the general theory of spherically-symmetric DP mechanisms in the large-composition regime. Specifically, we show that additive, continuous, spherically-symmetric DP mechanisms are optimal if one considers a spherically-symmetric cost (e.g., bounded noise variance) and an l2 sensitivity metric. We then formulate a finite-dimensional problem that produces noise distributions that can get arbitrarily close to optimal among monotone mechanisms. Finally, we demonstrate numerically that our proposed mechanism achieves better DP parameters than the vector Gaussian mechanism for the same variance constraint.
AB - We construct vector differentially-private (DP) mechanisms that are asymptotically optimal in the limit of the number of compositions growing without bound. First, we derive via the central limit theorem a reduction from DP to a KL-divergence minimization problem. Second, we formulate the general theory of spherically-symmetric DP mechanisms in the large-composition regime. Specifically, we show that additive, continuous, spherically-symmetric DP mechanisms are optimal if one considers a spherically-symmetric cost (e.g., bounded noise variance) and an l2 sensitivity metric. We then formulate a finite-dimensional problem that produces noise distributions that can get arbitrarily close to optimal among monotone mechanisms. Finally, we demonstrate numerically that our proposed mechanism achieves better DP parameters than the vector Gaussian mechanism for the same variance constraint.
UR - http://www.scopus.com/inward/record.url?scp=85171442763&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85171442763&partnerID=8YFLogxK
U2 - 10.1109/ISIT54713.2023.10206658
DO - 10.1109/ISIT54713.2023.10206658
M3 - Conference contribution
AN - SCOPUS:85171442763
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 2195
EP - 2200
BT - 2023 IEEE International Symposium on Information Theory, ISIT 2023
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2023 IEEE International Symposium on Information Theory, ISIT 2023
Y2 - 25 June 2023 through 30 June 2023
ER -