# Optimality of Staircase Mechanisms for Vector Queries under Differential Privacy

arXiv: https://arxiv.org/abs/2601.14597 · HTML: https://mlsanity.com/paper/2601.14597/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 24 references that are in the map.
- First posted on arXiv 21 Jan 2026.

## Builds on (most cited first, 8 of 8)

- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Guidelines for Implementing and Auditing Differentially Private Systems](https://mlsanity.com/paper/2002.04049/) (2020)
- [Mean estimation in the add-remove model of differential privacy](https://mlsanity.com/paper/2312.06658/) (2023)
- [A Central Limit Theorem for Differentially Private Query Answering](https://mlsanity.com/paper/2103.08721/) (2021)
- [Cactus Mechanisms: Optimal Differential Privacy Mechanisms in the Large-Composition Regime](https://mlsanity.com/paper/2207.00420/) (2022)
- [Grafting Laplace and Gaussian distributions: A new noise mechanism for differential privacy](https://mlsanity.com/paper/2212.09657/) (2022)
- [Offset-Symmetric Gaussians for Differential Privacy](https://mlsanity.com/paper/2110.06412/) (2021)
- [Differential privacy for symmetric log-concave mechanisms](https://mlsanity.com/paper/2202.11393/) (2022)

## Abstract (arXiv)

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.