論文の概要: Scalable Private Partition Selection via Adaptive Weighting

• arxiv url: http://arxiv.org/abs/2502.08878v1
• Date: Thu, 13 Feb 2025 01:27:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-14 13:46:56.986903
• Title: Scalable Private Partition Selection via Adaptive Weighting
• Title（参考訳）: 適応重み付けによるスケーラブルなプライベートパーティション選択
• Authors: Justin Y. Chen, Vincent Cohen-Addad, Alessandro Epasto, Morteza Zadimoghaddam,
• Abstract要約: プライベート・セット・ユニオンでは、ユーザーは非有界宇宙からのアイテムのサブセットを保持する。 目標は、ユーザレベルの差分プライバシーを維持しながら、ユーザセットの統一から可能な限り多くのアイテムを出力することである。 そこで本研究では,プライバシに必要なしきい値よりもはるかに重い項目からより少ない項目へ適応的に重みを還元するアルゴリズムであるMaximumDegree (MAD)を提案する。
• 参考スコア（独自算出の注目度）: 66.09199304818928
• License:
• Abstract: In the differentially private partition selection problem (a.k.a. private set union, private key discovery), users hold subsets of items from an unbounded universe. The goal is to output as many items as possible from the union of the users' sets while maintaining user-level differential privacy. Solutions to this problem are a core building block for many privacy-preserving ML applications including vocabulary extraction in a private corpus, computing statistics over categorical data, and learning embeddings over user-provided items. We propose an algorithm for this problem, MaximumAdaptiveDegree (MAD), which adaptively reroutes weight from items with weight far above the threshold needed for privacy to items with smaller weight, thereby increasing the probability that less frequent items are output. Our algorithm can be efficiently implemented in massively parallel computation systems allowing scalability to very large datasets. We prove that our algorithm stochastically dominates the standard parallel algorithm for this problem. We also develop a two-round version of our algorithm where results of the computation in the first round are used to bias the weighting in the second round to maximize the number of items output. In experiments, our algorithms provide the best results across the board among parallel algorithms and scale to datasets with hundreds of billions of items, up to three orders of magnitude larger than those analyzed by prior sequential algorithms.
• Abstract（参考訳）: 微分的にプライベートなパーティション選択問題(例えば、プライベート・セット・ユニオン、プライベート・キー発見)では、ユーザーは非有界宇宙からのアイテムのサブセットを保持する。 目標は、ユーザレベルの差分プライバシーを維持しながら、ユーザセットの統一から可能な限り多くのアイテムを出力することである。 この問題に対するソリューションは、プライベートコーパスでの語彙抽出、カテゴリデータに関する計算統計、ユーザが提供するアイテムに対する埋め込みの学習など、多くのプライバシ保護MLアプリケーションの中核となるビルディングブロックである。 そこで本研究では,プライバシに必要なしきい値よりもはるかに重い項目からより少ない項目へ適応的に重みを還元し,頻繁でない項目が出力される確率を高めるアルゴリズムであるMaximumAdaptiveDegree (MAD)を提案する。 我々のアルゴリズムは大規模並列計算システムで効率的に実装することができ、非常に大きなデータセットのスケーラビリティを実現することができる。 我々は,本アルゴリズムがこの問題の標準並列アルゴリズムを確率的に支配していることを証明した。 また,第1ラウンドの計算結果を第2ラウンドの重み付けに偏り、出力する項目数を最大化する2ラウンドバージョンのアルゴリズムを開発した。 実験では、我々のアルゴリズムは並列アルゴリズムの中で最高の結果を提供し、数十億の項目からなるデータセットにスケールする。

関連論文リスト

• Privacy-Computation trade-offs in Private Repetition and Metaselection [28.11248357424981]
  プライベート反復アルゴリズムは、一定の成功確率を持つ差分プライベートアルゴリズムを入力として、高い確率で成功するアルゴリズムに後押しする。 これらのタスクの既存のアルゴリズムは、プライバシコストの大きなオーバーヘッドを支払うか、計算コストの大きなオーバーヘッドを支払う。 これは、計算オーバーヘッドで異常確率が指数関数的に低下する非プライベートな設定とは対照的である。
  論文  参考訳（メタデータ） (2024-10-22T18:33:02Z)
• Differentially Private Heavy Hitter Detection using Federated Analytics [33.69819799254375]
  本研究では,プレフィックスツリーに基づくアルゴリズムの性能向上のための実用性について検討する。 我々のモデルは、各ユーザが複数のデータポイントを持っていると仮定し、その目標は、すべてのユーザのデータを集約的および局所的な差分プライバシーで可能な限り多くの最も頻繁なデータポイントを学習することである。
  論文  参考訳（メタデータ） (2023-07-21T17:59:15Z)
• Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
  ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。 プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。 各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
  論文  参考訳（メタデータ） (2023-06-07T14:07:35Z)
• Scalable Batch Acquisition for Deep Bayesian Active Learning [70.68403899432198]
  ディープラーニングでは、各ステップでマークアップする複数の例を選択することが重要です。 BatchBALDのような既存のソリューションでは、多くの例を選択する際に大きな制限がある。 本稿では,より計算効率のよいLarge BatchBALDアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-13T11:45:17Z)
• Efficient and Accurate Top-$K$ Recovery from Choice Data [1.14219428942199]
  レコメンデーションシステムのようないくつかのアプリケーションでは、統計学者は主に大量のアイテムから上位のアイテムの集合を回収することに興味がある。 そこで本稿では,K$-recoveryの高速かつ高精度なランキングアルゴリズムとして,選択に基づくボルダカウントアルゴリズムを提案する。 選択に基づくボルダカウントアルゴリズムは,多種多様なランダム効用モデルの下で,上位$Kの回収に最適なサンプル複雑性を有することを示す。
  論文  参考訳（メタデータ） (2022-06-23T22:05:08Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew [58.21885402826496]
  全ペアセットの類似性は、大規模で高次元のデータセットであっても広く使われているデータマイニングタスクである。 我々は,全対集合の類似性を近似するために,新しい分散アルゴリズム LSF-Join を提案する。 LSF-Joinは、小さな類似度閾値やスキュー入力セットであっても、最も近いペアを効率的に見つける。
  論文  参考訳（メタデータ） (2020-03-06T00:06:20Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。 最小クラスタ回復誤差率のアルゴリズムを考案する。 適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2019-10-14T09:18:26Z)

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

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