論文の概要: Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning

• arxiv url: http://arxiv.org/abs/2411.09552v1
• Date: Thu, 14 Nov 2024 16:06:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-15 15:23:15.036914
• Title: Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning
• Title（参考訳）: より高速にプライベートなTop-k$選択:プルーニングを伴う共同指数メカニズム
• Authors: Hao WU, Hanwen Zhang,
• Abstract要約: 差分的にプライベートな$k$選択問題について検討し、$d$アイテムから最も高いスコアを持つ$k$アイテムの列を特定することを目的とした。 Gillenwaterらによる最近の研究(ICML '22)は、$d,Theta(k)$ possible length-$k$ sequencesの膨大なコレクションから直接サンプリングアプローチを採用している。 時間と空間の複雑さを持つアルゴリズムを改良し、$O(d + k2 / epsilon cdot ln d)$で、$epsilon$はプライバシーを表す。
• 参考スコア（独自算出の注目度）: 2.2083091880368855
• License:
• Abstract: We study the differentially private top-$k$ selection problem, aiming to identify a sequence of $k$ items with approximately the highest scores from $d$ items. Recent work by Gillenwater et al. (ICML '22) employs a direct sampling approach from the vast collection of $d^{\,\Theta(k)}$ possible length-$k$ sequences, showing superior empirical accuracy compared to previous pure or approximate differentially private methods. Their algorithm has a time and space complexity of $\tilde{O}(dk)$. In this paper, we present an improved algorithm with time and space complexity $O(d + k^2 / \epsilon \cdot \ln d)$, where $\epsilon$ denotes the privacy parameter. Experimental results show that our algorithm runs orders of magnitude faster than their approach, while achieving similar empirical accuracy.
• Abstract（参考訳）: 差分的にプライベートな$k$選択問題について検討し、$d$アイテムから最も高いスコアを持つ$k$アイテムの列を特定することを目的とした。 Gillenwater et al (ICML '22) による最近の研究は、$d^{\,\Theta(k)}$ $ possible length-$k$Sequences の膨大なコレクションからの直接サンプリングアプローチを採用しており、従来の純粋あるいは近似微分プライベートな手法と比較して、経験的精度が優れている。 彼らのアルゴリズムは時間と空間の複雑さが$\tilde{O}(dk)$である。 本稿では,時間と空間の複雑さが向上したアルゴリズムをO(d + k^2 / \epsilon \cdot \ln d)$で提示する。 実験結果から,本アルゴリズムはアプローチよりも桁違いに高速に動作し,実験精度も同等であることがわかった。

関連論文リスト

• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Efficiently Computing Similarities to Private Datasets [19.99000806126529]
  微分プライベートモデルトレーニングの多くの方法は、クエリポイント(公開データや合成データなど)とプライベートデータとの類似性を計算することに依存している。 類似関数$f$と大きな高次元プライベートデータセット$XサブセットmathbbRd$を与えられた場合、任意のクエリ$y$に対して、X f(x,y)$のsum_xを近似した差分プライベート(DP)データ構造を出力する。
  論文  参考訳（メタデータ） (2024-03-13T19:19:19Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• Run Time Bounds for Integer-Valued OneMax Functions [0.9012198585960443]
  探索空間 $mathbbZn$ を多値決定変数 $0,ldots,r-1n$ の観点から考える。 ステップサイズ適応のRSSが$Theta(n cdot log(|a|_1))$の最適化時間を達成することを示す。 本稿では,これらのアルゴリズムを離散探索空間に対するCMA-ESの変種と比較し,実験的な解析を行った。
  論文  参考訳（メタデータ） (2023-07-21T18:49:06Z)
• 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)
• Faster Differentially Private Samplers via R\'enyi Divergence Analysis of Discretized Langevin MCMC [35.050135428062795]
  ランゲヴィン力学に基づくアルゴリズムは、統計距離のようなある程度の距離測度の下で、はるかに高速な代替手段を提供する。 我々の手法は単純で汎用的で、アンダーダムドランゲヴィン力学に適用できる。
  論文  参考訳（メタデータ） (2020-10-27T22:52:45Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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