論文の概要: Optimal Algorithms for Mean Estimation under Local Differential Privacy

• arxiv url: http://arxiv.org/abs/2205.02466v1
• Date: Thu, 5 May 2022 06:43:46 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-06 15:31:44.278409
• Title: Optimal Algorithms for Mean Estimation under Local Differential Privacy
• Title（参考訳）: 局所微分プライバシー下における平均推定の最適アルゴリズム
• Authors: Hilal Asi, Vitaly Feldman, Kunal Talwar
• Abstract要約: そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。 また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
• 参考スコア（独自算出の注目度）: 55.32262879188817
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of mean estimation of $\ell_2$-bounded vectors under the constraint of local differential privacy. While the literature has a variety of algorithms that achieve the asymptotically optimal rates for this problem, the performance of these algorithms in practice can vary significantly due to varying (and often large) hidden constants. In this work, we investigate the question of designing the protocol with the smallest variance. We show that PrivUnit (Bhowmick et al. 2018) with optimized parameters achieves the optimal variance among a large family of locally private randomizers. To prove this result, we establish some properties of local randomizers, and use symmetrization arguments that allow us to write the optimal randomizer as the optimizer of a certain linear program. These structural results, which should extend to other problems, then allow us to show that the optimal randomizer belongs to the PrivUnit family. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees. This allows us to establish several useful properties on the exact constants of the optimal error as well as to numerically estimate these constants.
• Abstract（参考訳）: 局所微分プライバシーの制約下での$\ell_2$-boundedベクトルの平均推定問題について検討する。 文献には、この問題の漸近的最適速度を達成する様々なアルゴリズムがあるが、実際にはこれらのアルゴリズムの性能は、様々な(しばしば大きな)隠れ定数によって大きく異なる。 本研究では,最小の分散でプロトコルを設計する問題について検討する。 最適化されたパラメータを持つprivunit (bhowmick et al. 2018) は、局所的ランダム化器の大きなファミリー間の最適な分散を実現する。 この結果を証明するため、局所ランダム化器の特性を定式化し、最適なランダム化器をある線形プログラムの最適化器として書けるように対称性の引数を用いる。 これらの構造結果は、他の問題にまで拡張され、最適確率化器がPrivUnitファミリーに属することを示す。 また,ガウス分布に基づくPrivUnitの新しい変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。 これにより、最適誤差の厳密な定数にいくつかの有用な性質を定め、これらの定数を数値的に推定することができる。

関連論文リスト

• Differential Privacy with Multiple Selections [52.5653572324012]
  感性のある機能を持つユーザがサーバから異なるプライベートな方法でレコメンデーションを得るような設定について検討する。 本稿では,サーバが複数のレコメンデーションを送信可能なマルチセレクションアーキテクチャを提案する。
  論文  参考訳（メタデータ） (2024-07-19T19:34:51Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。 純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。 本稿では,総和,数,投票の単純な統計量について両問題を解く。
  論文  参考訳（メタデータ） (2023-09-27T17:09:36Z)
• Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
  ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。 プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。 各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
  論文  参考訳（メタデータ） (2023-06-07T14:07:35Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。 すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
  論文  参考訳（メタデータ） (2023-01-31T18:47:42Z)
• Optimal Compression of Locally Differentially Private Mechanisms [21.200464908282594]
  共有ランダムネスを用いてデータを共同で圧縮・民営化する手法の利点を実証する。 我々の理論的および実証的な結果は、我々のアプローチがPivUnit (Bhowmick et al., Coding and Subset Selection (Ye et al., the most known LDP algorithm for mean and frequency Estimation, to the order of communication, while Preserving their privacy and accuracy guarantees to the order of communication, to the order of epsilon-bits to the order of communication, to the order of epsilon-bits to the order of communication, to the order of the Epsilon-bits to the order of communication。
  論文  参考訳（メタデータ） (2021-10-29T21:36:34Z)
• No-Regret Algorithms for Private Gaussian Process Bandit Optimization [13.660643701487002]
  プライバシー保護統計のレンズによるガウス過程(GP)帯域最適化の至るところでの問題点を考察する。 均一なカーネル近似器とランダムな摂動を組み合わせた差分プライベートGPバンディット最適化のためのソリューションを提案する。 我々のアルゴリズムは最適化手順を通して微分プライバシを保持し、予測のためのサンプルパスに明示的に依存しない。
  論文  参考訳（メタデータ） (2021-02-24T18:52:24Z)
• Projection-Free Bandit Optimization with Privacy Guarantees [18.95253453749389]
  プロジェクションフリー設定におけるバンディット凸最適化問題に対する微分プライベートアルゴリズムの設計を行う。 この設定は、決定集合が複素幾何学を持つときに重要であり、それへのアクセスは線型最適化オラクルを通してのみ効率的に行われる。 これはプロジェクションフリーなバンディット最適化のための最初の微分プライベートアルゴリズムであり、実際、$widetildeO(T3/4)$は最もよく知られた非プライベートなプロジェクションフリーアルゴリズムと一致する。
  論文  参考訳（メタデータ） (2020-12-22T16:19:29Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)
• Private Stochastic Convex Optimization: Efficient Algorithms for Non-smooth Objectives [28.99826590351627]
  本稿では,プライバシパラメータがサンプル数に比例する場合に,一階降下を実現する雑音ミラーに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-22T03:03:43Z)

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

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