論文の概要: 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つの異なる入力が与えられたメカニズムの条件出力分布間のクルバック・リーバーのばらつきを最小限にするものである。
ノイズのコスト制約を考慮したこの分岐を最小化するための最適化問題を定式化する。
まず、加法機構が最適であることを示す。
最適化問題は無限次元であるため、直接解くことはできない。しかしながら、その形状から「カクタス機構」と呼ばれる近似光学的加法機構を導出するために問題を定量化する。
我々は、量子化アプローチが最適なメカニズムに任意に近づくことができることを示す。
驚くべきことに、二次コストの場合、ガウスのメカニズムは、このカクタスのメカニズムと比較して厳密には最適である。
最後に,有限個の組成に対してカクタス機構がガウス機構を上回ることを示す数値的な結果を与える。
関連論文リスト
- Refined Mechanism Design for Approximately Structured Priors via Active
Regression [50.71772232237571]
我々は、大量の商品を戦略的入札者に販売する収益を最大化する販売業者の問題を考える。
この設定の最適かつほぼ最適のメカニズムは、特徴付けや計算が難しいことで有名である。
論文 参考訳(メタデータ) (2023-10-11T20:34:17Z) - Pure Differential Privacy for Functional Summaries via a Laplace-like
Process [8.557392136621894]
この研究は、機能的な要約に差分プライバシーの新たなメカニズムを導入する。
独立成分置換プロセス(ICLP)機構は、関心の要約を真に無限次元のオブジェクトとして扱う。
合成および実データセットに関する数値実験により,提案手法の有効性が示された。
論文 参考訳(メタデータ) (2023-08-31T20:24:51Z) - 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) - Learning Numeric Optimal Differentially Private Truncated Additive
Mechanisms [5.079561894598125]
実効性境界が強い付加的なメカニズムに対して,トランクテッドノイズを学習するためのツールを提案する。
平均単調な単調な音から, 対称性やその新しい音を考慮すれば十分であることを示す。
感度境界機構については, 平均単調な単調なノイズから, 対称性とその新しさを考えるのに十分であることを示す。
論文 参考訳(メタデータ) (2021-07-27T17:22:57Z) - Improved Matrix Gaussian Mechanism for Differential Privacy [29.865497421453917]
差分プライバシー(DP)メカニズムは、従来のスカラー値ではなく、行列のような構造データのために開発されている。
本研究は,行列値DPのための改良行列ガウス機構 (IMGM) を提案し,その必要十分条件を$(varepsilon,delta) $-differential privacy とした。
行列値DPの正規ノイズ分布のうち、最適ノイズ分布はi.i.dであることが判明した。
さまざまなモデルとデータセットに関する実験も、IMGMが同じプライバシー保証で最先端のメカニズムよりもはるかに高い有用性をもたらすことを検証しています。
論文 参考訳(メタデータ) (2021-04-30T07:44:53Z) - From Checking to Inference: Actual Causality Computations as
Optimization Problems [79.87179017975235]
本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。
8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
論文 参考訳(メタデータ) (2020-06-05T10:56:52Z) - Near Instance-Optimality in Differential Privacy [38.8726789833284]
古典統計理論に着想を得た差分プライバシーにおけるインスタンス最適性の概念を考案する。
また、大規模な推定値に対してインスタンス最適(もしくはほぼインスタンス最適)な逆感度機構も開発する。
論文 参考訳(メタデータ) (2020-05-16T04:53:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。