論文の概要: Lossless Compression of Efficient Private Local Randomizers
- arxiv url: http://arxiv.org/abs/2102.12099v1
- Date: Wed, 24 Feb 2021 07:04:30 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-25 13:21:14.416890
- Title: Lossless Compression of Efficient Private Local Randomizers
- Title（参考訳）: 高効率プライベートローカルランダム化器のロスレス圧縮
- Authors: Vitaly Feldman and Kunal Talwar
- Abstract要約: Locally Differentially Private (LDP) Reportsは、フェデレーション設定における統計と機械学習の収集に一般的に使用されます。
多くの場合、最もよく知られたldpアルゴリズムは、クライアントデバイスからサーバに強制的に大きなメッセージを送信する必要がある。
これにより、LDPアルゴリズムの通信コストの削減に大きく貢献しています。
- 参考スコア（独自算出の注目度）: 55.657133416044104
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Locally Differentially Private (LDP) Reports are commonly used for collection
of statistics and machine learning in the federated setting. In many cases the
best known LDP algorithms require sending prohibitively large messages from the
client device to the server (such as when constructing histograms over large
domain or learning a high-dimensional model). This has led to significant
efforts on reducing the communication cost of LDP algorithms.
At the same time LDP reports are known to have relatively little information
about the user's data due to randomization. Several schemes are known that
exploit this fact to design low-communication versions of LDP algorithm but all
of them do so at the expense of a significant loss in utility. Here we
demonstrate a general approach that, under standard cryptographic assumptions,
compresses every efficient LDP algorithm with negligible loss in privacy and
utility guarantees. The practical implication of our result is that in typical
applications the message can be compressed to the size of the server's
pseudo-random generator seed. More generally, we relate the properties of an
LDP randomizer to the power of a pseudo-random generator that suffices for
compressing the LDP randomizer. From this general approach we derive
low-communication algorithms for the problems of frequency estimation and
high-dimensional mean estimation. Our algorithms are simpler and more accurate
than existing low-communication LDP algorithms for these well-studied problems.
- Abstract（参考訳）: Locally Differentially Private (LDP) Reportsは、フェデレーション設定における統計と機械学習の収集に一般的に使用されます。
多くの場合、最もよく知られたldpアルゴリズムは、クライアントデバイスからサーバへ(大きなドメイン上でヒストグラムを構築する場合や高次元モデルを学ぶ場合など)、非常に大きなメッセージを送らなければなりません。
これにより、LDPアルゴリズムの通信コストの削減に大きく貢献しています。
同時に、ldpレポートはランダム化によってユーザーのデータに関する情報が比較的少ないことが知られている。
いくつかのスキームは、この事実を利用してLDPアルゴリズムの低コミュニケーションバージョンを設計することが知られているが、これら全てはユーティリティーの大幅な損失を犠牲にしている。
ここでは,標準的な暗号仮定の下で,プライバシとユーティリティの保証を損なうことなく,すべての効率的なldpアルゴリズムを圧縮する一般的なアプローチを示す。
この結果の実際的な意味は、典型的なアプリケーションでは、メッセージはサーバの疑似randomジェネレータシードのサイズに圧縮できるということです。
より一般に、LDPランダム化器の特性と、LDPランダム化器を圧縮するのに十分である擬似ランダム生成器のパワーを関連付ける。
本稿では,周波数推定問題と高次元平均推定問題に対する低コミュニケーションアルゴリズムを導出する。
当社のアルゴリズムは、これらのよく研究された問題に対する既存の低通信LDPアルゴリズムよりもシンプルで正確です。
関連論文リスト
- Sketches-based join size estimation under local differential privacy [3.0945730947183203]
機密データの結合サイズ推定は、プライバシー漏洩のリスクをもたらす。
ローカルディファレンシャルプライバシ(LDP)は、機密データを収集しながらプライバシを保存するソリューションである。
スケッチベースジョインサイズ推定のための LDPJoinSketch という新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-19T01:21:54Z) - Noise Variance Optimization in Differential Privacy: A Game-Theoretic Approach Through Per-Instance Differential Privacy [7.264378254137811]
差分プライバシー(DP)は、個人をターゲットデータセットに含めることによる分布の変化を観察することにより、プライバシー損失を測定することができる。
DPは、AppleやGoogleのような業界巨人の機械学習におけるデータセットの保護において際立っている。
本稿では,PDPを制約として提案し,各データインスタンスのプライバシ損失を測定し,個々のインスタンスに適したノイズを最適化する。
論文 参考訳（メタデータ） (2024-04-24T06:51:16Z) - Semidefinite programs simulate approximate message passing robustly [3.1528188401664137]
近似メッセージパッシング(AMP)は、電力を一般化する反復アルゴリズムの一群である。
AMPアルゴリズムは、多くの平均ケース最適化問題を最適に解くことが知られている。
論文 参考訳（メタデータ） (2023-11-15T15:00:48Z) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳（メタデータ） (2023-06-07T14:07:35Z) - Private and Communication-Efficient Algorithms for Entropy Estimation [21.195965074919602]
分布のエントロピーの一般的な測度を推定するために、改良された私的および通信効率のアルゴリズムを提供する。
全てのアルゴリズムは通信コストが一定であり、局所的な差分プライバシーを満たす。
論文 参考訳（メタデータ） (2023-05-12T20:35:10Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - RL for Latent MDPs: Regret Guarantees and a Lower Bound [74.41782017817808]
後期マルコフ決定過程(LMDP)における強化学習における後悔問題の検討
LMDPにおいて、M$可能なMDPのセットからMDPをランダムに描画するが、選択したMDPの同一性はエージェントに明らかにしない。
鍵となるリンクは、MDPシステムの力学の分離の概念であることを示す。
論文 参考訳（メタデータ） (2021-02-09T16:49:58Z) - A One-Pass Private Sketch for Most Machine Learning Tasks [48.17461258268463]
差別化プライバシ(DP)は、正式な証明可能な保証を通じて、プライバシとユーティリティのトレードオフを説明する魅力的なプライバシ定義である。
本稿では,回帰,分類,密度推定など,多数の機械学習タスクをサポートするプライベートスケッチを提案する。
このスケッチは,局所性に敏感なハッシュをインデックス化して,効率的なワンパスアルゴリズムで構築したランダムな一致テーブルで構成されている。
論文 参考訳（メタデータ） (2020-06-16T17:47:48Z) - User-Level Privacy-Preserving Federated Learning: Analysis and
Performance Optimization [77.43075255745389]
フェデレートラーニング(FL)は、データを有用なモデルにトレーニングしながら、モバイル端末(MT)からプライベートデータを保存することができる。
情報理論の観点からは、MTがアップロードした共有モデルから、好奇心の強いサーバがプライベートな情報を推測することが可能である。
サーバにアップロードする前に、共有モデルに人工ノイズを加えることで、ユーザレベルの差分プライバシー(UDP)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-29T10:13:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。