論文の概要: Private and Communication-Efficient Algorithms for Entropy Estimation
- arxiv url: http://arxiv.org/abs/2305.07751v1
- Date: Fri, 12 May 2023 20:35:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-16 19:56:04.307624
- Title: Private and Communication-Efficient Algorithms for Entropy Estimation
- Title（参考訳）: エントロピー推定のためのプライベートおよび通信効率の良いアルゴリズム
- Authors: Gecia Bravo-Hermsdorff, R\'obert Busa-Fekete, Mohammad Ghavamzadeh,
Andres Mu\~noz Medina, Umar Syed
- Abstract要約: 分布のエントロピーの一般的な測度を推定するために、改良された私的および通信効率のアルゴリズムを提供する。
全てのアルゴリズムは通信コストが一定であり、局所的な差分プライバシーを満たす。
- 参考スコア（独自算出の注目度）: 21.195965074919602
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Modern statistical estimation is often performed in a distributed setting
where each sample belongs to a single user who shares their data with a central
server. Users are typically concerned with preserving the privacy of their
samples, and also with minimizing the amount of data they must transmit to the
server. We give improved private and communication-efficient algorithms for
estimating several popular measures of the entropy of a distribution. All of
our algorithms have constant communication cost and satisfy local differential
privacy. For a joint distribution over many variables whose conditional
independence is given by a tree, we describe algorithms for estimating Shannon
entropy that require a number of samples that is linear in the number of
variables, compared to the quadratic sample complexity of prior work. We also
describe an algorithm for estimating Gini entropy whose sample complexity has
no dependence on the support size of the distribution and can be implemented
using a single round of concurrent communication between the users and the
server. In contrast, the previously best-known algorithm has high communication
cost and requires the server to facilitate interaction between the users.
Finally, we describe an algorithm for estimating collision entropy that
generalizes the best known algorithm to the private and communication-efficient
setting.
- Abstract（参考訳）: 現代の統計的推定はしばしば分散環境で行われ、各サンプルは中央サーバとデータを共有している1人のユーザーに属している。
ユーザは一般的に、サンプルのプライバシーを守り、サーバに送信しなければならないデータの量を最小限に抑えることに関心を持っている。
分布のエントロピーの一般的な測度を推定するために、改良されたプライベートおよび通信効率のアルゴリズムを提供する。
全てのアルゴリズムは通信コストが一定であり、局所的な差分プライバシーを満たす。
条件付き独立性が木によって与えられる多くの変数のジョイント分布について,変数数に線形なサンプル数を必要とするシャノンエントロピーを,事前作業の二次的サンプル複雑性と比較して推定するアルゴリズムについて述べる。
また,Giniエントロピーを推定するアルゴリズムについて述べる。このアルゴリズムは,サンプルの複雑さが分布の支持サイズに依存せず,ユーザとサーバ間の同時通信を単一ラウンドで行うことができる。
対照的に、最もよく知られたアルゴリズムは、高い通信コストを持ち、サーバがユーザ間のインタラクションを容易にする必要がある。
最後に,最もよく知られたアルゴリズムをプライベートかつ通信効率の良い設定に一般化した衝突エントロピー推定アルゴリズムについて述べる。
関連論文リスト
- Scalable Decentralized Algorithms for Online Personalized Mean Estimation [12.002609934938224]
本研究は,各エージェントが実数値分布からサンプルを収集し,その平均値を推定する,オーバーアーキシング問題の簡易版に焦点を当てた。
1つは信念の伝播からインスピレーションを得ており、もう1つはコンセンサスに基づくアプローチを採用している。
論文 参考訳（メタデータ） (2024-02-20T08:30:46Z) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳（メタデータ） (2023-06-07T14:07:35Z) - Balancing Privacy and Performance for Private Federated Learning
Algorithms [4.681076651230371]
Federated Learning(FL)は、複数のクライアントがプライベートデータを公開せずにモデルをトレーニングする分散機械学習フレームワークである。
FLアルゴリズムは、共有前に各クライアントのモデル更新にノイズを導入する差分プライバシーメカニズムを頻繁に採用する。
ローカルステップの数と通信ラウンドの間に最適なバランスがあることを示し、プライバシー予算内での収束性能を最大化する。
論文 参考訳（メタデータ） (2023-04-11T10:42:11Z) - Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean
Estimation [8.9598796481325]
本稿では, アルゴリズムと計算複雑性の両面において, 異なる統計問題に対する観測結果について検討する。
プライベートスパース平均推定のための情報計算ギャップを確立する。
また、プライバシーによって引き起こされる情報計算のギャップを、いくつかの統計や学習問題に対して証明する。
論文 参考訳（メタデータ） (2022-11-01T20:03:41Z) - On Differential Privacy for Federated Learning in Wireless Systems with
Multiple Base Stations [90.53293906751747]
複数の基地局とセル間干渉を持つ無線システムにおける連合学習モデルを考える。
本稿では,学習過程の収束挙動を,その最適性ギャップの上限を導出することによって示す。
提案するスケジューラは,ランダムなスケジューラと比較して予測平均精度を向上する。
論文 参考訳（メタデータ） (2022-08-25T03:37:11Z) - Collaborative Learning of Distributions under Heterogeneity and
Communication Constraints [35.82172666266493]
機械学習では、ユーザはしばしば、データを生成するディストリビューションを学ぶために協力する必要がある。
まず、ユーザはサーバと通信して中央分布を学習し、協調する。
そして、学習した中央分布を微調整して、ユーザの個々の分布を推定する。
論文 参考訳（メタデータ） (2022-06-01T18:43:06Z) - Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。
提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
論文 参考訳（メタデータ） (2021-05-23T19:21:55Z) - Lossless Compression of Efficient Private Local Randomizers [55.657133416044104]
Locally Differentially Private (LDP) Reportsは、フェデレーション設定における統計と機械学習の収集に一般的に使用されます。
多くの場合、最もよく知られたldpアルゴリズムは、クライアントデバイスからサーバに強制的に大きなメッセージを送信する必要がある。
これにより、LDPアルゴリズムの通信コストの削減に大きく貢献しています。
論文 参考訳（メタデータ） (2021-02-24T07:04:30Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。