論文の概要: Fast Optimal Locally Private Mean Estimation via Random Projections
- arxiv url: http://arxiv.org/abs/2306.04444v1
- Date: Wed, 7 Jun 2023 14:07:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-08 14:12:13.866851
- Title: Fast Optimal Locally Private Mean Estimation via Random Projections
- Title（参考訳）: ランダム射影による高速最適局所的平均推定
- Authors: Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar
- Abstract要約: ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
- 参考スコア（独自算出の注目度）: 58.603579803010796
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of locally private mean estimation of high-dimensional
vectors in the Euclidean ball. Existing algorithms for this problem either
incur sub-optimal error or have high communication and/or run-time complexity.
We propose a new algorithmic framework, ProjUnit, for private mean estimation
that yields algorithms that are computationally efficient, have low
communication complexity, and incur optimal error up to a $1+o(1)$-factor. Our
framework is deceptively simple: each randomizer projects its input to a random
low-dimensional subspace, normalizes the result, and then runs an optimal
algorithm such as PrivUnitG in the lower-dimensional space. In addition, we
show that, by appropriately correlating the random projection matrices across
devices, we can achieve fast server run-time. We mathematically analyze the
error of the algorithm in terms of properties of the random projections, and
study two instantiations. Lastly, our experiments for private mean estimation
and private federated learning demonstrate that our algorithms empirically
obtain nearly the same utility as optimal ones while having significantly lower
communication and computational cost.
- Abstract（参考訳）: ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
この問題に対する既存のアルゴリズムは、サブオプティマイズエラーを引き起こすか、通信や実行時の複雑さが高い。
本稿では,計算効率が高く,通信の複雑度が低く,最大1+o(1)$-factorの誤差が生じるアルゴリズムをプライベート平均推定のために提案するアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、低次元空間においてPrivUnitGのような最適なアルゴリズムを実行する。
また,デバイス間でランダムな投影行列を適切に関連付けることで,高速なサーバ実行を実現することができることを示す。
ランダム射影の性質の観点からアルゴリズムの誤差を数学的に解析し、2つのインスタンス化の研究を行った。
最後に,私的平均推定および私的フェデレート学習実験により,我々のアルゴリズムは,通信コストと計算コストを大幅に低減しつつ,最適値とほぼ同一の効用を実証的に得ることを示した。
関連論文リスト
- Efficient distributed representations with linear-time attention scores normalization [3.8673630752805437]
本研究では,有界ノルムを持つ埋め込みベクトルに対するアテンションスコア正規化定数の線形時間近似を提案する。
推定公式の精度は、競合するカーネルメソッドを桁違いに上回る。
提案アルゴリズムは高度に解釈可能であり,任意の埋め込み問題に容易に適応できる。
論文 参考訳（メタデータ） (2023-03-30T15:48:26Z) - Subset-Based Instance Optimality in Private Estimation [23.173651165908282]
我々は、幅広いデータセット特性を推定する際に、インスタンス最適性の概念を実現するプライベートアルゴリズムを構築する方法を示す。
提案アルゴリズムは,分布的な仮定の下で,既存のアルゴリズムの性能を同時に一致または超過する。
論文 参考訳（メタデータ） (2023-03-01T18:49:10Z) - 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) - Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。
また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
論文 参考訳（メタデータ） (2022-05-05T06:43:46Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。