論文の概要: Cactus Mechanisms: Optimal Differential Privacy Mechanisms in the
Large-Composition Regime
- arxiv url: http://arxiv.org/abs/2207.00420v1
- Date: Sat, 25 Jun 2022 20:05:50 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-10 14:09:38.626776
- Title: Cactus Mechanisms: Optimal Differential Privacy Mechanisms in the
Large-Composition Regime
- Title（参考訳）: cactus機構:大規模コンポジション体制における最適微分プライバシー機構
- Authors: Wael Alghamdi, Shahab Asoodeh, Flavio P. Calmon, Oliver Kosut, Lalitha
Sankar, Fei Wei
- Abstract要約: 本研究では,多数の構成の限界における最適微分プライバシー機構の設計について検討する。
この体制では、最高のプライバシーメカニズムは、Kullback-Leiblerの発散を最小限にするものである。
我々は、量子化アプローチが最適なメカニズムに任意に近づくことができることを示す。
- 参考スコア（独自算出の注目度）: 12.420941209631742
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Most differential privacy mechanisms are applied (i.e., composed) numerous
times on sensitive data. We study the design of optimal differential privacy
mechanisms in the limit of a large number of compositions. As a consequence of
the law of large numbers, in this regime the best privacy mechanism is the one
that minimizes the Kullback-Leibler divergence between the conditional output
distributions of the mechanism given two different inputs. We formulate an
optimization problem to minimize this divergence subject to a cost constraint
on the noise. We first prove that additive mechanisms are optimal. Since the
optimization problem is infinite dimensional, it cannot be solved directly;
nevertheless, we quantize the problem to derive near-optimal additive
mechanisms that we call "cactus mechanisms" due to their shape. We show that
our quantization approach can be arbitrarily close to an optimal mechanism.
Surprisingly, for quadratic cost, the Gaussian mechanism is strictly
sub-optimal compared to this cactus mechanism. Finally, we provide numerical
results which indicate that cactus mechanism outperforms the Gaussian mechanism
for a finite number of compositions.
- Abstract（参考訳）: ほとんどの差分プライバシメカニズムは、機密データに何度も適用される(すなわち、構成される)。
本稿では,多数の構成の限界における最適微分プライバシー機構の設計について検討する。
多数の法則の結果として、この体制では、最高のプライバシメカニズムは、2つの異なる入力が与えられたメカニズムの条件出力分布間のクルバック・リーバーのばらつきを最小限にするものである。
ノイズのコスト制約を考慮したこの分岐を最小化するための最適化問題を定式化する。
まず、加法機構が最適であることを示す。
最適化問題は無限次元であるため、直接解くことはできない。しかしながら、その形状から「カクタス機構」と呼ばれる近似光学的加法機構を導出するために問題を定量化する。
我々は、量子化アプローチが最適なメカニズムに任意に近づくことができることを示す。
驚くべきことに、二次コストの場合、ガウスのメカニズムは、このカクタスのメカニズムと比較して厳密には最適である。
最後に,有限個の組成に対してカクタス機構がガウス機構を上回ることを示す数値的な結果を与える。
関連論文リスト
- Privacy-Aware Randomized Quantization via Linear Programming [13.002534825666219]
偏りがなく、偏りのない量子化機構のファミリーを提案する。
提案するメカニズムは,ベースラインと比較して,より優れたプライバシ・正確性トレードオフを実現することができる。
論文 参考訳（メタデータ） (2024-06-01T18:40:08Z) - Near-Universally-Optimal Differentially Private Minimum Spanning Trees [0.0]
我々は、最小スパンニングツリーを概解する単純な微分プライベートなメカニズムが、$ell_infty$ 近傍関係に対する普遍的最適性という意味では、ほぼ最適であることを示す。
我々は MST の指数的機構を時間内に実装し、これは $ell_infty$ と $ell_infty$ の近傍関係の両方に対して普遍的な準最適性をもたらすことを示した。
論文 参考訳（メタデータ） (2024-04-23T13:39:25Z) - Refined Mechanism Design for Approximately Structured Priors via Active
Regression [50.71772232237571]
我々は、大量の商品を戦略的入札者に販売する収益を最大化する販売業者の問題を考える。
この設定の最適かつほぼ最適のメカニズムは、特徴付けや計算が難しいことで有名である。
論文 参考訳（メタデータ） (2023-10-11T20:34:17Z) - Truncated Laplace and Gaussian mechanisms of RDP [28.227024132603123]
ラプラス機構とガウス機構は、微分プライバシーの主要なメカニズムである。
無限範囲の確率変数によって、ラプラスとガウスのメカニズムは、負数のような意味的に不可能な値を返すことができる。
論文 参考訳（メタデータ） (2023-09-22T06:37:45Z) - Less is More: Revisiting the Gaussian Mechanism for Differential Privacy [8.89234867625102]
出力摂動による差分プライバシーは、機密データに対してクエリや計算結果をリリースするためのデファクトスタンダードとなっている。
既存のガウスのメカニズムはすべて、フルランクの共分散行列の呪いに苦しむ。
論文 参考訳（メタデータ） (2023-06-04T04:14:38Z) - On User-Level Private Convex Optimization [59.75368670035683]
ユーザレベルの差分プライバシー保証を伴う凸最適化(SCO)のための新しいメカニズムを提案する。
我々のメカニズムは損失に対する滑らかさの仮定を必要としない。
私たちの限界は、ユーザレベルのプライバシーに必要な最小限のユーザが、その次元に依存しない、最初のものです。
論文 参考訳（メタデータ） (2023-05-08T17:47:28Z) - Pessimism meets VCG: Learning Dynamic Mechanism Design via Offline
Reinforcement Learning [114.36124979578896]
オフライン強化学習アルゴリズムを用いて動的メカニズムを設計する。
我々のアルゴリズムは悲観主義の原理に基づいており、オフラインデータセットのカバレッジについて軽度な仮定しか必要としない。
論文 参考訳（メタデータ） (2022-05-05T05:44:26Z) - On Scheduling Mechanisms Beyond the Worst Case [17.281501828240877]
機構Kは各入力における機構Pよりも社会的コストが小さいことが分かる。
また、メカニズムPの平均ケース近似比は、同じ定数に収束する。
論文 参考訳（メタデータ） (2022-04-14T20:57:50Z) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳（メタデータ） (2022-03-11T17:19:26Z) - Understanding Interlocking Dynamics of Cooperative Rationalization [90.6863969334526]
選択的合理化(Selective rationalization)は、ニューラルネットワークの出力を予測するのに十分な入力の小さなサブセットを見つけることによって、複雑なニューラルネットワークの予測を説明する。
このような合理化パラダイムでは,モデルインターロックという大きな問題が浮かび上がっている。
A2Rと呼ばれる新しい合理化フレームワークを提案し、アーキテクチャに第3のコンポーネントを導入し、選択とは対照的にソフトアテンションによって駆動される予測器を提案する。
論文 参考訳（メタデータ） (2021-10-26T17:39:18Z) - From Checking to Inference: Actual Causality Computations as
Optimization Problems [79.87179017975235]
本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。
8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
論文 参考訳（メタデータ） (2020-06-05T10:56:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。