論文の概要: Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism

• arxiv url: http://arxiv.org/abs/2111.12981v1
• Date: Thu, 25 Nov 2021 09:31:15 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-29 18:19:51.171769
• Title: Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism
• Title（参考訳）: 正方形指数機構による純粋微分プライバシーを用いた効率的な平均推定
• Authors: Samuel B. Hopkins, Gautam Kamath, Mahbod Majid
• Abstract要約: 純微分プライバシーを受ける独立サンプルの共分散で$d$正確率分布の平均を推定するアルゴリズムを初めて与える。 我々の主な手法は、強力なSum of Squares法(SoS)を用いて微分プライベートアルゴリズムを設計する新しいアプローチである。
• 参考スコア（独自算出の注目度）: 16.996435043565594
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give the first polynomial-time algorithm to estimate the mean of a $d$-variate probability distribution with bounded covariance from $\tilde{O}(d)$ independent samples subject to pure differential privacy. Prior algorithms for this problem either incur exponential running time, require $\Omega(d^{1.5})$ samples, or satisfy only the weaker concentrated or approximate differential privacy conditions. In particular, all prior polynomial-time algorithms require $d^{1+\Omega(1)}$ samples to guarantee small privacy loss with "cryptographically" high probability, $1-2^{-d^{\Omega(1)}}$, while our algorithm retains $\tilde{O}(d)$ sample complexity even in this stringent setting. Our main technique is a new approach to use the powerful Sum of Squares method (SoS) to design differentially private algorithms. SoS proofs to algorithms is a key theme in numerous recent works in high-dimensional algorithmic statistics -- estimators which apparently require exponential running time but whose analysis can be captured by low-degree Sum of Squares proofs can be automatically turned into polynomial-time algorithms with the same provable guarantees. We demonstrate a similar proofs to private algorithms phenomenon: instances of the workhorse exponential mechanism which apparently require exponential time but which can be analyzed with low-degree SoS proofs can be automatically turned into polynomial-time differentially private algorithms. We prove a meta-theorem capturing this phenomenon, which we expect to be of broad use in private algorithm design. Our techniques also draw new connections between differentially private and robust statistics in high dimensions. In particular, viewed through our proofs-to-private-algorithms lens, several well-studied SoS proofs from recent works in algorithmic robust statistics directly yield key components of our differentially private mean estimation algorithm.
• Abstract（参考訳）: 純粋微分プライバシーの対象となる$\tilde{o}(d)$独立サンプルから有界共分散を持つ$d$-変量確率分布の平均を推定する最初の多項式時間アルゴリズムを与える。 この問題の以前のアルゴリズムは指数関数的な実行時間、$\Omega(d^{1.5})$サンプルを必要とするか、より弱い集中あるいは近似的な差分プライバシー条件のみを満たす。 特に、全ての事前多項式時間アルゴリズムは「暗号的に」高い確率で小さなプライバシー損失を保証するために$d^{1+\Omega(1)}$サンプルを必要とするが、我々のアルゴリズムは、この厳密な設定でも$\tilde{O}(d)$サンプル複雑性を保持する。 我々の主な手法は、強力なSum of Squares法(SoS)を用いて微分プライベートアルゴリズムを設計する新しいアプローチである。 アルゴリズムに対するsosの証明は、最近の多くの高次元アルゴリズム統計学における重要なテーマである -- 指数関数的な実行時間を必要とするように見えるが、正方形証明の低次和によって解析されるような推定器は、同じ証明可能な保証で自動的に多項式時間アルゴリズムに変換できる。 指数関数時間を必要とするが、低次sos証明で解析できるワークホース指数関数機構の例を多項式時間微分プライベートアルゴリズムに自動的に変換することができる。 この現象を捉えたメタ理論を証明し、プライベートなアルゴリズム設計において広く使われることを期待する。 我々の手法は、高次元における微分プライベート統計学とロバスト統計学の新たな関係も引き起こす。 特に,アルゴリズムロバスト統計学における最近の研究から得られたいくつかのsos証明は,我々の微分的平均推定アルゴリズムの重要なコンポーネントを直接生み出すものである。

関連論文リスト

• Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More [5.893651469750359]
  マルチウェイカットと最小$k$cutのためのエッジ微分プライベートアルゴリズムを導入する。 最小$k$-cut問題に対して、指数的メカニズムと近似$k$-cutの数の有界性を組み合わせた別のアプローチを用いる。
  論文  参考訳（メタデータ） (2024-07-09T14:46:33Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
  本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。 我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
  論文  参考訳（メタデータ） (2022-06-07T16:49:54Z)
• Faster Differentially Private Samplers via R\'enyi Divergence Analysis of Discretized Langevin MCMC [35.050135428062795]
  ランゲヴィン力学に基づくアルゴリズムは、統計距離のようなある程度の距離測度の下で、はるかに高速な代替手段を提供する。 我々の手法は単純で汎用的で、アンダーダムドランゲヴィン力学に適用できる。
  論文  参考訳（メタデータ） (2020-10-27T22:52:45Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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