Optimality of Staircase Mechanisms for Vector Queries under Differential Privacy
This provides a foundational result for differential privacy, offering a general optimality proof that benefits researchers and practitioners in privacy-preserving data analysis.
The paper tackles the problem of designing optimal additive mechanisms for vector-valued queries under differential privacy, proving that staircase mechanisms minimize expected utility loss for any dimension, norm, and norm-monotone cost function, thereby resolving a prior conjecture.
We study the optimal design of additive mechanisms for vector-valued queries under $ε$-differential privacy (DP). Given only the sensitivity of a query and a norm-monotone cost function measuring utility loss, we ask which noise distribution minimizes expected cost among all additive $ε$-DP mechanisms. Using convex rearrangement theory, we show that this infinite-dimensional optimization problem admits a reduction to a one-dimensional compact and convex family of radially symmetric distributions whose extreme points are the staircase distributions. As a consequence, we prove that for any dimension, any norm, and any norm-monotone cost function, there exists an $ε$-DP staircase mechanism that is optimal among all additive mechanisms. This result resolves a conjecture of Geng, Kairouz, Oh, and Viswanath, and provides a geometric explanation for the emergence of staircase mechanisms as extremal solutions in differential privacy.