論文の概要: Private Frequency Estimation via Projective Geometry

• arxiv url: http://arxiv.org/abs/2203.00194v1
• Date: Tue, 1 Mar 2022 02:49:55 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-02 15:34:42.716493
• Title: Private Frequency Estimation via Projective Geometry
• Title（参考訳）: 射影幾何学によるプライベート周波数推定
• Authors: Vitaly Feldman, Jelani Nelson, Huy L\^e Nguyen, Kunal Talwar
• Abstract要約: そこで本研究では,局所微分型(LDP)周波数推定のための新しいアルゴリズムであるProjectiveGeometryResponse (PGR)を提案する。 私たちの$varepsilon$-LDPアルゴリズムは、プライベートコイン設定で$lceillogkrceilビット、パブリックコイン設定で$varepsilonlog e + O(1)$の通信コストを持っています。 実際に使用される多くのパラメータ設定では、これは最近のPIによって達成されるO(n+k2)$Optimalコストよりも大幅に改善されている。
• 参考スコア（独自算出の注目度）: 47.112770141205864
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we propose a new algorithm ProjectiveGeometryResponse (PGR) for locally differentially private (LDP) frequency estimation. For a universe size of $k$ and with $n$ users, our $\varepsilon$-LDP algorithm has communication cost $\lceil\log_2k\rceil$ bits in the private coin setting and $\varepsilon\log_2 e + O(1)$ in the public coin setting, and has computation cost $O(n + k\exp(\varepsilon) \log k)$ for the server to approximately reconstruct the frequency histogram, while achieving the state-of-the-art privacy-utility tradeoff. In many parameter settings used in practice this is a significant improvement over the $ O(n+k^2)$ computation cost that is achieved by the recent PI-RAPPOR algorithm (Feldman and Talwar; 2021). Our empirical evaluation shows a speedup of over 50x over PI-RAPPOR while using approximately 75x less memory for practically relevant parameter settings. In addition, the running time of our algorithm is within an order of magnitude of HadamardResponse (Acharya, Sun, and Zhang; 2019) and RecursiveHadamardResponse (Chen, Kairouz, and Ozgur; 2020) which have significantly worse reconstruction error. The error of our algorithm essentially matches that of the communication- and time-inefficient but utility-optimal SubsetSelection (SS) algorithm (Ye and Barg; 2017). Our new algorithm is based on using Projective Planes over a finite field to define a small collection of sets that are close to being pairwise independent and a dynamic programming algorithm for approximate histogram reconstruction on the server side. We also give an extension of PGR, which we call HybridProjectiveGeometryResponse, that allows trading off computation time with utility smoothly.
• Abstract（参考訳）: そこで本研究では,局所微分型(LDP)周波数推定のための新しいアルゴリズムであるProjectiveGeometry Response (PGR)を提案する。 k$の宇宙サイズと$n$のユーザに対して、我々の$\varepsilon$-LDPアルゴリズムは、プライベートコインセッティングにおける$\lceil\log_2k\rceil$ビットとパブリックコインセッティングにおける$\varepsilon\log_2e + O(1)$の通信コストを持ち、計算コスト$O(n + k\exp(\varepsilon) \log k)$は、サーバが周波数ヒストグラムをほぼ再構築し、最先端のプライバシユーティリティトレードオフを達成します。 実際には多くのパラメータ設定において、これは最近のpi-rapporアルゴリズム(feldman and talwar; 2021)によって達成された$ o(n+k^2)$計算コストを大幅に改善する。 実験により,PI-RAPPORを50倍以上高速化し,約75倍少ないメモリでパラメータ設定を行った。 さらに、我々のアルゴリズムの実行時間はハダマール応答 (Acharya, Sun, and Zhang; 2019) と再帰ハダマール応答 (Chen, Kairouz, and Ozgur; 2020) のオーダーの範囲内であり、再構成エラーが著しく悪化している。 我々のアルゴリズムの誤差は、本質的に通信効率と時間効率が良いが、ssアルゴリズム(ye and barg; 2017)と一致している。 我々の新しいアルゴリズムは、有限フィールド上の射影平面を用いて、対独立に近い集合の小さな集合と、サーバ側のヒストグラム再構成を近似する動的プログラミングアルゴリズムを定義することに基づいている。 また,我々はhybridprojectivegeometryresponseと呼ぶpgrの拡張も提供している。

関連論文リスト

• Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
  本研究では,平均推定,PCA,線形回帰に着目したハマー汚染モデルにおけるスパース推定タスクについて検討する。 それぞれのタスクに対して、最適なエラー保証を備えた最初のサンプルと計算効率の良い頑健な推定器を与える。 技術レベルでは、スパース方式における新しい多次元フィルタリング法を開発し、他の応用を見出すことができる。
  論文  参考訳（メタデータ） (2024-03-15T15:51:27Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
  純微分プライバシー(DP)モデルと近似微分プライバシー(DP)モデルの両方において、ガウス分布をプライベートに推定する効率的なアルゴリズムを提供する。 純粋なDP設定では、未知の$d$次元ガウス分布を任意の全変分誤差まで推定する効率的なアルゴリズムを与える。 平均推定の特別な場合、我々のアルゴリズムは$widetilde O(d1.5)$の最適なサンプル複雑性を達成し、以前の作業から$widetilde O(d1.5)$のバウンドを改善する。
  論文  参考訳（メタデータ） (2022-12-15T18:27:39Z)
• Confident Approximate Policy Iteration for Efficient Local Planning in $q^\pi$-realizable MDPs [2.5652904661855076]
  我々は、$gamma$-discounted Markov決定過程における近似動的プログラミングについて考察する。 私たちの最初のコントリビューションは、CAPI(Confident Approximate Policy Iteration)と呼ばれる、新しいバージョンの近似ポリシーイテレーション(API)です。 CAPIは、最適エラーバウンドスケーリングによる決定論的定常ポリシーを、有効地平線$H$と最悪の近似誤差$epsilon$の積と線形に計算する。
  論文  参考訳（メタデータ） (2022-10-27T20:19:31Z)
• 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)
• 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)
• A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
  最適な輸送を計算するための厳密なアルゴリズムは遅くなる。 我々は、OT距離の$varepsilon$approximationを求めるための、新しい非常に単純なアプローチを導入する。 我々のアルゴリズムは、OT距離を計算するために、O(n2/varepsilon2)$のほぼ最適実行時間を達成する。
  論文  参考訳（メタデータ） (2022-03-07T21:40:14Z)
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost [53.968049198926444]
  スイッチングコストの低い線形MDPのための最初のアルゴリズムを提案する。 このアルゴリズムは$widetildeoleft(sqrtd3h4kright)$ regretをほぼ最適の$oleft(d hlog kright)$グローバルスイッチングコストで達成する。
  論文  参考訳（メタデータ） (2021-01-02T18:41:27Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation [44.374427255708135]
  線形関数近似を用いた無限水平平均逆設定でマルコフ決定過程を学習するための新しいアルゴリズムを開発した。 まず,最適$widetildeO(sqrtT)$ regretの計算非効率アルゴリズムを提案する。 次に,逆線形包帯から着想を得て,$widetildeO(sqrtT)$ regretのアルゴリズムを新たに開発した。
  論文  参考訳（メタデータ） (2020-07-23T08:23:44Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。