Optimality of Staircase Mechanisms for Vector Queries under Differential Privacy
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Optimality of Matrix Mechanism on $\ell_p^p$-metric
In this paper, we introduce the $\ell_p^p$-error metric (for $p \geq 2$) when answering linear queries under the constraint of differential privacy. We characterize such an error under $(\epsilon,\delta)$-differential pr…
Projective view at Optimization Problem for Multiband Filter
The best uniform rational approximation of the \emph{sign} function on two intervals separated by zero was explicitly solved by E.I. Zolotar\"ev in 1877. This optimization problem is the initial step in the staircase of …
Electrical EngineeringAccurate and Scalable Matrix Mechanisms via Divide and Conquer
Matrix mechanisms are often used to provide unbiased differentially private query answers when publishing statistics or creating synthetic data. Recent work has developed matrix mechanisms, such as ResidualPlanner and We…
Staircase Attention for Recurrent Processing of Sequences
Attention mechanisms have become a standard tool for sequence modeling tasks, in particular by stacking self-attention layers over the entire input sequence as in the Transformer architecture. In this work we introduce a…
Language ModelingLanguage ModellingOn the Privacy of Selection Mechanisms with Gaussian Noise
Report Noisy Max and Above Threshold are two classical differentially private (DP) selection mechanisms. Their output is obtained by adding noise to a sequence of low-sensitivity queries and reporting the identity of the…