論文の概要: On Differential Privacy and Adaptive Data Analysis with Bounded Space
- arxiv url: http://arxiv.org/abs/2302.05707v1
- Date: Sat, 11 Feb 2023 14:45:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-14 19:00:21.254375
- Title: On Differential Privacy and Adaptive Data Analysis with Bounded Space
- Title（参考訳）: 境界空間を用いた微分プライバシーと適応データ解析について
- Authors: Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou
- Abstract要約: 差分プライバシーと適応データ分析の2つの関連分野の空間複雑性について検討する。
差分プライバシーで効率的に解くために指数関数的に多くの空間を必要とする問題Pが存在することを示す。
アダプティブデータ分析の研究の行は、アダプティブクエリのシーケンスに応答するのに必要なサンプルの数を理解することに焦点を当てている。
- 参考スコア（独自算出の注目度）: 76.10334958368618
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the space complexity of the two related fields of differential
privacy and adaptive data analysis. Specifically,
(1) Under standard cryptographic assumptions, we show that there exists a
problem P that requires exponentially more space to be solved efficiently with
differential privacy, compared to the space needed without privacy. To the best
of our knowledge, this is the first separation between the space complexity of
private and non-private algorithms.
(2) The line of work on adaptive data analysis focuses on understanding the
number of samples needed for answering a sequence of adaptive queries. We
revisit previous lower bounds at a foundational level, and show that they are a
consequence of a space bottleneck rather than a sampling bottleneck.
To obtain our results, we define and construct an encryption scheme with
multiple keys that is built to withstand a limited amount of key leakage in a
very particular way.
- Abstract（参考訳）: 差分プライバシーと適応データ分析の2つの関連分野の空間複雑性について検討する。
具体的には,(1)標準暗号仮定の下では,プライバシのない空間に比べて,差分プライバシーで効率的に解決できる空間が指数関数的に多く必要となる問題Pが存在することを示す。
私たちの知る限りでは、これはプライベートアルゴリズムと非プライベートアルゴリズムの空間複雑性の最初の分離である。
2)適応データ分析における研究の行は,適応クエリのシーケンスに応答するために必要なサンプル数を理解することに集中している。
従来の下位境界を基礎レベルで再検討し、これらがサンプリングボトルネックではなく、空間ボトルネックの結果であることを示す。
この結果を得るために,我々は,限られた量の鍵漏洩に耐えられるように構築された,複数の鍵を持つ暗号方式を定義し,構築する。
関連論文リスト
- Initialization Matters: Privacy-Utility Analysis of Overparameterized
Neural Networks [72.51255282371805]
我々は、最悪の近傍データセット上でのモデル分布間のKLばらつきのプライバシー境界を証明した。
このKLプライバシー境界は、トレーニング中にモデルパラメータに対して期待される2乗勾配ノルムによって決定される。
論文 参考訳（メタデータ） (2023-10-31T16:13:22Z) - On the Complexity of Differentially Private Best-Arm Identification with
Fixed Confidence [16.295693624977563]
我々は、$epsilon$-global Differential Privacyの下で、信頼度を固定したベストアーム識別の問題について検討する。
われわれの限界は、プライバシー予算によって2つのプライバシー体制が存在することを示唆している。
我々はトップ2アルゴリズムの$epsilon$-global DP変種であるAdaP-TTを提案する。
論文 参考訳（メタデータ） (2023-09-05T13:07:25Z) - Algorithms with More Granular Differential Privacy Guarantees [65.3684804101664]
我々は、属性ごとのプライバシー保証を定量化できる部分微分プライバシー(DP)について検討する。
本研究では,複数の基本データ分析および学習タスクについて検討し,属性ごとのプライバシパラメータが個人全体のプライバシーパラメータよりも小さい設計アルゴリズムについて検討する。
論文 参考訳（メタデータ） (2022-09-08T22:43:50Z) - On Differential Privacy for Federated Learning in Wireless Systems with
Multiple Base Stations [90.53293906751747]
複数の基地局とセル間干渉を持つ無線システムにおける連合学習モデルを考える。
本稿では,学習過程の収束挙動を,その最適性ギャップの上限を導出することによって示す。
提案するスケジューラは,ランダムなスケジューラと比較して予測平均精度を向上する。
論文 参考訳（メタデータ） (2022-08-25T03:37:11Z) - Private Domain Adaptation from a Public Source [48.83724068578305]
我々は、公開ラベル付きデータを持つソースドメインから、未ラベル付きプライベートデータを持つターゲットドメインへの適応のための差分プライベート離散性に基づくアルゴリズムを設計する。
我々の解は、Frank-WolfeとMirror-Descentアルゴリズムのプライベートな変種に基づいている。
論文 参考訳（メタデータ） (2022-08-12T06:52:55Z) - Private Alternating Least Squares: Practical Private Matrix Completion
with Tighter Rates [34.023599653814415]
ユーザレベルのプライバシの下で、差分的プライベート(DP)行列補完の問題について検討する。
本稿では,Alternating-Least-Squares (ALS) 方式の差分型を設計する。
論文 参考訳（メタデータ） (2021-07-20T23:19:11Z) - Robust and Differentially Private Mean Estimation [40.323756738056616]
異なるプライバシーは、米国国勢調査から商用デバイスで収集されたデータまで、さまざまなアプリケーションで標準要件として浮上しています。
このようなデータベースの数は、複数のソースからのデータからなり、それらすべてが信頼できるわけではない。
これにより、既存のプライベート分析は、腐敗したデータを注入する敵による攻撃に弱い。
論文 参考訳（メタデータ） (2021-02-18T05:02:49Z) - Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy
Amplification by Shuffling [49.43288037509783]
ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。
私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
論文 参考訳（メタデータ） (2020-12-23T17:07:26Z) - Privately Learning Markov Random Fields [44.95321417724914]
我々は、差分プライバシーの制約の下でランダムフィールド(イジングモデルを含む)を学習する問題を考察する。
私たちは、さまざまなプライバシー制約の下で、両方の問題に対してアルゴリズムと低いバウンダリを提供します。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。