論文の概要: Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean
Estimation
- arxiv url: http://arxiv.org/abs/2211.00724v1
- Date: Tue, 1 Nov 2022 20:03:41 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-03 12:53:21.839129
- Title: Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean
Estimation
- Title（参考訳）: プライバシーはロバスト性をもたらす:情報計算ギャップとスパース平均推定
- Authors: Kristian Georgiev, Samuel B. Hopkins
- Abstract要約: 本稿では, アルゴリズムと計算複雑性の両面において, 異なる統計問題に対する観測結果について検討する。
プライベートスパース平均推定のための情報計算ギャップを確立する。
また、プライバシーによって引き起こされる情報計算のギャップを、いくつかの統計や学習問題に対して証明する。
- 参考スコア（独自算出の注目度）: 8.9598796481325
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We establish a simple connection between robust and differentially-private
algorithms: private mechanisms which perform well with very high probability
are automatically robust in the sense that they retain accuracy even if a
constant fraction of the samples they receive are adversarially corrupted.
Since optimal mechanisms typically achieve these high success probabilities,
our results imply that optimal private mechanisms for many basic statistics
problems are robust.
We investigate the consequences of this observation for both algorithms and
computational complexity across different statistical problems. Assuming the
Brennan-Bresler secret-leakage planted clique conjecture, we demonstrate a
fundamental tradeoff between computational efficiency, privacy leakage, and
success probability for sparse mean estimation. Private algorithms which match
this tradeoff are not yet known -- we achieve that (up to polylogarithmic
factors) in a polynomially-large range of parameters via the Sum-of-Squares
method.
To establish an information-computation gap for private sparse mean
estimation, we also design new (exponential-time) mechanisms using fewer
samples than efficient algorithms must use. Finally, we give evidence for
privacy-induced information-computation gaps for several other statistics and
learning problems, including PAC learning parity functions and estimation of
the mean of a multivariate Gaussian.
- Abstract（参考訳）: 非常に高い確率でうまく機能するプライベートメカニズムは、たとえ受信したサンプルの一定割合が敵対的に破損したとしても、精度を維持するという意味で自動的に堅牢である。
最適メカニズムは一般にこれらの高い成功確率を達成するため、多くの基礎統計問題に対する最適プライベートメカニズムは堅牢であることを示す。
本稿では, アルゴリズムと計算複雑性の両面において, 異なる統計問題に対する観測結果について検討する。
ブレナン・ブレスラーの秘密推論による斜流予想を仮定すると、計算効率、プライバシーリーク、およびスパース平均推定の成功確率の基本的なトレードオフを示す。
このトレードオフにマッチするプライベートアルゴリズムはまだ分かっていないが、 Sum-of-Squares 法により多項式的に広いパラメータで(多対数因子まで)達成できる。
プライベートスパース平均推定のための情報計算ギャップを確立するために,効率的なアルゴリズムよりも少ないサンプルを用いた新しい(指数時間)機構を設計する。
最後に、PAC学習パリティ関数や多変量ガウス平均の推定など、いくつかの統計および学習問題に対するプライバシーによる情報計算ギャップの証拠を示す。
関連論文リスト
- Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Differentially Private Linear Regression with Linked Data [3.9325957466009203]
コンピュータ科学の数学的概念である差分プライバシーは、堅牢なプライバシー保証を提供する上昇するツールである。
最近の研究は、個々の統計および機械学習タスクの微分プライベートバージョンの開発に焦点を当てている。
相関データを用いた線形回帰のための2つの微分プライベートアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-08-01T21:00:19Z) - Stability is Stable: Connections between Replicability, Privacy, and
Adaptive Generalization [26.4468964378511]
複製可能なアルゴリズムは、そのランダム性が固定されたときに高い確率で同じ出力を与える。
データ解析にレプリカブルアルゴリズムを使用することで、公開結果の検証が容易になる。
我々は、複製性とアルゴリズム安定性の標準概念との新たな接続と分離を確立する。
論文 参考訳（メタデータ） (2023-03-22T21:35:50Z) - On the Privacy-Robustness-Utility Trilemma in Distributed Learning [7.778461949427662]
本稿では,少数の対向マシンに対してロバスト性を保証するアルゴリズムによって得られた誤差を,まず厳密に解析する。
私たちの分析は、プライバシ、堅牢性、ユーティリティの基本的なトレードオフを示しています。
論文 参考訳（メタデータ） (2023-02-09T17:24:18Z) - Robustness Implies Privacy in Statistical Estimation [16.061651295129302]
本研究では,高次元統計学における敵のプライバシーと差分プライバシーの関係について検討する。
プライバシーから堅牢性への最初のブラックボックスの削減は、最適なトレードオフを伴うプライベートな推定器を生み出すことができる。
また, アルゴリズムは, ほぼ最適に崩壊したサンプルに対して頑健である。
論文 参考訳（メタデータ） (2022-12-09T18:07:30Z) - Learning to Bound Counterfactual Inference in Structural Causal Models
from Observational and Randomised Data [64.96984404868411]
我々は、従来のEMベースのアルゴリズムを拡張するための全体的なデータの特徴付けを導出する。
新しいアルゴリズムは、そのような混合データソースからモデルパラメータの(不特定性)領域を近似することを学ぶ。
反実的な結果に間隔近似を与え、それが特定可能な場合の点に崩壊する。
論文 参考訳（メタデータ） (2022-12-06T12:42:11Z) - Decentralized Stochastic Optimization with Inherent Privacy Protection [103.62463469366557]
分散最適化は、現代の協調機械学習、分散推定と制御、大規模センシングの基本的な構成要素である。
データが関与して以降、分散最適化アルゴリズムの実装において、プライバシ保護がますます重要になっている。
論文 参考訳（メタデータ） (2022-05-08T14:38:23Z) - Robust and Differentially Private Mean Estimation [40.323756738056616]
異なるプライバシーは、米国国勢調査から商用デバイスで収集されたデータまで、さまざまなアプリケーションで標準要件として浮上しています。
このようなデータベースの数は、複数のソースからのデータからなり、それらすべてが信頼できるわけではない。
これにより、既存のプライベート分析は、腐敗したデータを注入する敵による攻撃に弱い。
論文 参考訳（メタデータ） (2021-02-18T05:02:49Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z) - New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
微分プライベートな合成データを構築するための3つの新しいアルゴリズムを提案する。
アルゴリズムは最悪の場合でも差分プライバシーを満たす。
現状の手法である高次元行列機構 citeMcKennaMHM18 と比較すると,我々のアルゴリズムは大規模作業負荷の精度が向上する。
論文 参考訳（メタデータ） (2020-07-10T15:46:05Z) - Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。
本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
論文 参考訳（メタデータ） (2020-05-22T22:30:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。