論文の概要: Optimality of Staircase Mechanisms for Vector Queries under Differential Privacy

• arxiv url: http://arxiv.org/abs/2601.14597v1
• Date: Wed, 21 Jan 2026 02:35:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-22 21:27:50.211454
• Title: Optimality of Staircase Mechanisms for Vector Queries under Differential Privacy
• Title（参考訳）: 差分プライバシ下におけるベクトルキューのステアケース機構の最適性
• Authors: James Melbourne, Mario Diaz, Shahab Asoodeh,
• Abstract要約: 任意の次元,任意のノルム,任意のノルム単調コスト関数に対して,任意の加法機構の中で最適となる$-DP階段機構が存在することを示す。 この結果は、Geng, Kairouz, Oh, Viswanath の予想を解き、微分プライバシーにおける極端解としての階段機構の出現に関する幾何学的な説明を提供する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 本稿では,ε$-differential privacy (DP) に基づくベクトル値クエリに対する加算機構の最適設計について検討する。 提案手法は,クエリの感度と効用損失を測定するノルム単調なコスト関数のみを考慮し,任意の付加的な$ε$-DP機構において,ノイズ分布が期待コストを最小化するかを問う。 凸再配置理論を用いて、この無限次元最適化問題は、極点が階段分布である放射対称分布の一次元コンパクトで凸な族に還元されることを示す。 その結果、任意の次元、ノルム、ノルム単調なコスト関数に対して、すべての加法機構の中で最適となる$ε$-DP階段機構が存在することが証明された。 この結果は、Geng, Kairouz, Oh, Viswanath の予想を解き、微分プライバシーにおける極端解としての階段機構の出現に関する幾何学的な説明を提供する。

関連論文リスト

• Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy [13.264499801590583]
  mathbbRn 倍 n$ の対称行列 $A と任意の対称摂動 E$ に対して、新しい高確率スペクトル-ノルム摂動境界を導入する。 穏やかな固有ギャップとノルム条件の下では、我々の境界は$|(A + E)_p - A_p|$に対して鋭い推定値を得るが、最大で$sqrtn$となる。 応用として,PCAの実用性保証の改善を導出し,文献の未解決問題を解消する。
  論文  参考訳（メタデータ） (2025-10-29T16:36:00Z)
• N-output Mechanism: Estimating Statistical Information from Numerical Data under Local Differential Privacy [0.0]
  ローカル微分プライバシー(LDP)は、機密データ収集において重要なプライバシー上の懸念に対処する。 既存の LDP 機構は、非常に小さな (|Omega| in 2, 3$) か無限出力空間に最適化される。 数値データを$N$の離散出力にマッピングする一般化されたフレームワークである textbfN-output 機構を提案する。
  論文  参考訳（メタデータ） (2025-10-13T08:06:59Z)
• Beyond Laplace and Gaussian: Exploring the Generalized Gaussian Mechanism for Private Machine Learning [49.66162382667325]
  一般化ガウス機構(英語版)を考察し、ある$beta geq 1$に対して$e-frac| x |sigmabeta $ に比例した付加雑音項 $x$ をサンプリングする。 GGメカニズムとその変種に対するプライバシ会計は独立であり、プライバシ会計の計算コストを大幅に向上させることを示す。
  論文  参考訳（メタデータ） (2025-06-14T15:49:25Z)
• Transformers as Support Vector Machines [54.642793677472724]
  自己アテンションの最適化幾何と厳密なSVM問題との間には,形式的等価性を確立する。 勾配降下に最適化された1層変圧器の暗黙バイアスを特徴付ける。 これらの発見は、最適なトークンを分離し選択するSVMの階層としてのトランスフォーマーの解釈を刺激していると信じている。
  論文  参考訳（メタデータ） (2023-08-31T17:57:50Z)
• Less is More: Revisiting the Gaussian Mechanism for Differential Privacy [8.89234867625102]
  出力摂動による差分プライバシーは、機密データに対してクエリや計算結果をリリースするためのデファクトスタンダードとなっている。 既存のガウスのメカニズムはすべて、フルランクの共分散行列の呪いに苦しむ。
  論文  参考訳（メタデータ） (2023-06-04T04:14:38Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。 すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
  論文  参考訳（メタデータ） (2023-01-31T18:47:42Z)
• Cactus Mechanisms: Optimal Differential Privacy Mechanisms in the Large-Composition Regime [12.420941209631742]
  本研究では,多数の構成の限界における最適微分プライバシー機構の設計について検討する。 この体制では、最高のプライバシーメカニズムは、Kullback-Leiblerの発散を最小限にするものである。 我々は、量子化アプローチが最適なメカニズムに任意に近づくことができることを示す。
  論文  参考訳（メタデータ） (2022-06-25T20:05:50Z)
• On Scheduling Mechanisms Beyond the Worst Case [17.281501828240877]
  機構Kは各入力における機構Pよりも社会的コストが小さいことが分かる。 また、メカニズムPの平均ケース近似比は、同じ定数に収束する。
  論文  参考訳（メタデータ） (2022-04-14T20:57:50Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。 暗黙正則化現象の理論的保証を提供する。
  論文  参考訳（メタデータ） (2020-07-16T13:27:47Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。