Optimality of Staircase Mechanisms for Vector Queries under Differential Privacy

• URL: http://arxiv.org/abs/2601.14597v1
• Date: Wed, 21 Jan 2026 02:35:33 GMT
• Title: Optimality of Staircase Mechanisms for Vector Queries under Differential Privacy
• Authors: James Melbourne, Mario Diaz, Shahab Asoodeh,
• Abstract summary: We show 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.<n>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.
• Score: 3.7942266369982955
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.

Related papers

• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy [13.264499801590583]
  We introduce new high-probability spectral-norm perturbation bounds for symmetric matrix $A in mathbbRn times n$ and an arbitrary symmetric perturbationE$.<n>Under mild eigengap and norm conditions, our bounds yield sharp estimates for $|(A + E)_p - A_p|$, with improvements of up to a factor of $sqrtn$.<n>As an application, we derive improved utility guarantees for differentially private PCA, resolving an open problem in the literature.
  arXiv  Detail & Related papers  (2025-10-29T16:36:00Z)
• N-output Mechanism: Estimating Statistical Information from Numerical Data under Local Differential Privacy [0.0]
  Local Differential Privacy (LDP) addresses significant privacy concerns in sensitive data collection.<n>Existing LDP mechanisms are optimized for either a very small ($|Omega| in 2, 3$) or infinite output spaces.<n>We propose the textbfN-output mechanism, a generalized framework that maps numerical data to one of $N$ discrete outputs.
  arXiv  Detail & Related papers  (2025-10-13T08:06:59Z)
• Beyond Laplace and Gaussian: Exploring the Generalized Gaussian Mechanism for Private Machine Learning [49.66162382667325]
  We investigate the Generalized Gaussian mechanism, which samples the additive noise term $x$ with probability proportional to $e-frac| x |sigmabeta $ for some $beta geq 1$.<n>We show that privacy accounting for the GG Mechanism and its variants is independent, which substantially improves computational costs of privacy accounting.
  arXiv  Detail & Related papers  (2025-06-14T15:49:25Z)
• Transformers as Support Vector Machines [54.642793677472724]
  We establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem. We characterize the implicit bias of 1-layer transformers optimized with gradient descent. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.
  arXiv  Detail & Related papers  (2023-08-31T17:57:50Z)
• Less is More: Revisiting the Gaussian Mechanism for Differential Privacy [8.89234867625102]
  Differential privacy via output perturbation has been a de facto standard for releasing query or computation results on sensitive data. We identify that all existing Gaussian mechanisms suffer from the curse of full-rank covariance matrices.
  arXiv  Detail & Related papers  (2023-06-04T04:14:38Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  A classical approach to private mean estimation is to compute the true mean and add unbiased, but possibly correlated, Gaussian noise to it. We show that for every input dataset, an unbiased mean estimator satisfying concentrated differential privacy introduces approximately at least as much error.
  arXiv  Detail & Related papers  (2023-01-31T18:47:42Z)
• Cactus Mechanisms: Optimal Differential Privacy Mechanisms in the Large-Composition Regime [12.420941209631742]
  We study the design of optimal differential privacy mechanisms in the limit of a large number of compositions. In this regime the best privacy mechanism is the one that minimizes the Kullback-Leibler divergence. We show that our quantization approach can be arbitrarily close to an optimal mechanism.
  arXiv  Detail & Related papers  (2022-06-25T20:05:50Z)
• On Scheduling Mechanisms Beyond the Worst Case [17.281501828240877]
  We find that mechanism K achieves a smaller social cost than mechanism P on every input. We also find that the average-case approximation ratio of mechanism P converges to the same constant.
  arXiv  Detail & Related papers  (2022-04-14T20:57:50Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.