論文の概要: Synthesizing Tight Privacy and Accuracy Bounds via Weighted Model Counting

• arxiv url: http://arxiv.org/abs/2402.16982v2
• Date: Thu, 29 Feb 2024 16:19:16 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-18 07:09:00.276609
• Title: Synthesizing Tight Privacy and Accuracy Bounds via Weighted Model Counting
• Title（参考訳）: 重み付きモデル計数によるタイトプライバシと精度境界の合成
• Authors: Lisa Oakley, Steven Holtzen, Alina Oprea,
• Abstract要約: 2つの中核的な課題は、DPアルゴリズムの分布の表現的でコンパクトで効率的な符号化を見つけることである。 プライバシーと正確性に縛られた合成法を開発することで、最初の課題に対処する。 DPアルゴリズムに固有の対称性を活用するためのフレームワークを開発する。
• 参考スコア（独自算出の注目度）: 5.552645730505715
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Programmatically generating tight differential privacy (DP) bounds is a hard problem. Two core challenges are (1) finding expressive, compact, and efficient encodings of the distributions of DP algorithms, and (2) state space explosion stemming from the multiple quantifiers and relational properties of the DP definition. We address the first challenge by developing a method for tight privacy and accuracy bound synthesis using weighted model counting on binary decision diagrams, a state of the art technique from the artificial intelligence and automated reasoning communities for exactly computing probability distributions. We address the second challenge by developing a framework for leveraging inherent symmetries in DP algorithms. Our solution benefits from ongoing research in probabilistic programming languages, allowing us to succinctly and expressively represent different DP algorithms with approachable language syntax that can be used by non-experts. We provide a detailed case study of our solution on the binary randomized response algorithm. We also evaluate an implementation of our solution using the Dice probabilistic programming language for the randomized response and truncated geometric above threshold algorithms. We compare to prior work on exact DP verification using Markov chain probabilistic model checking. Very few existing works consider mechanized analysis of accuracy guarantees for DP algorithms. We additionally provide a detailed analysis using our technique for finding tight accuracy bounds for DP algorithms.
• Abstract（参考訳）: プログラムによって厳密な差分プライバシー(DP)境界を生成することは難しい問題である。 2つの主要な課題は、(1)DPアルゴリズムの分布の表現的、コンパクトで効率的な符号化を見つけること、(2)DP定義の多重量子化器と関係性から生じる状態空間の爆発である。 本稿では,二項決定図に基づく重み付きモデルカウントを用いた厳密なプライバシと精度境界合成法,人工知能による最先端技術,確率分布を正確に計算するための自動推論コミュニティを開発することで,最初の課題に対処する。 DPアルゴリズムに固有の対称性を活用するためのフレームワークを開発することで,この2つの課題に対処する。 我々のソリューションは、確率的プログラミング言語の研究の恩恵を受けており、非専門家が利用できる親しみやすい言語構文を用いて、様々なDPアルゴリズムを簡潔かつ表現的に表現することができる。 本稿では,バイナリランダム化応答アルゴリズムにおける解の詳細なケーススタディを提案する。 また,Dice確率型プログラミング言語を用いて,乱数化応答と乱数化した幾何学的しきい値アルゴリズムの実装も検討した。 マルコフ連鎖確率モデル検査を用いたDPの正確な検証に関する先行研究との比較を行った。 DPアルゴリズムの精度保証を機械化して解析する研究はほとんどない。 また,DPアルゴリズムの厳密な精度境界を求めるために,本手法を用いた詳細な解析を行った。

関連論文リスト

• Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
  本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。 我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-05-28T19:02:30Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation [8.9598796481325]
  本稿では, アルゴリズムと計算複雑性の両面において, 異なる統計問題に対する観測結果について検討する。 プライベートスパース平均推定のための情報計算ギャップを確立する。 また、プライバシーによって引き起こされる情報計算のギャップを、いくつかの統計や学習問題に対して証明する。
  論文  参考訳（メタデータ） (2022-11-01T20:03:41Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。 DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
  論文  参考訳（メタデータ） (2022-06-27T03:45:02Z)
• Differentially Private Federated Learning via Inexact ADMM with Multiple Local Updates [0.0]
  我々は,複数の局所的な更新を施した乗算器アルゴリズムのDP不正確な交互方向法を開発した。 当社のアルゴリズムでは,各イテレーション毎に$barepsilon$-DPを提供しており,$barepsilon$はユーザが管理するプライバシ予算である。 提案アルゴリズムは,既存のDPアルゴリズムと比較してテストエラーを少なくとも31%削減すると同時に,データプライバシのレベルが同じであることを実証する。
  論文  参考訳（メタデータ） (2022-02-18T19:58:47Z)
• Dynamic programming by polymorphic semiring algebraic shortcut fusion [1.9405875431318445]
  動的プログラミング(動的プログラミング、英: Dynamic Programming、DP)は、難解問題の効率的かつ正確な解法のためのアルゴリズム設計パラダイムである。 本稿では,セミリングに基づくDPアルゴリズムを体系的に導出するための厳密な代数形式について述べる。
  論文  参考訳（メタデータ） (2021-07-05T00:51:02Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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