論文の概要: Communication-Efficient Publication of Sparse Vectors under Differential Privacy

• arxiv url: http://arxiv.org/abs/2506.20234v1
• Date: Wed, 25 Jun 2025 08:25:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-26 21:00:42.658263
• Title: Communication-Efficient Publication of Sparse Vectors under Differential Privacy
• Title（参考訳）: 差分プライバシー下におけるスパースベクトルの通信効率の向上
• Authors: Quentin Hillebrand, Vorapong Suppakitpaisarn, Tetsuo Shibuya,
• Abstract要約: スパースベクトルから集約された行列をパブリッシュするための微分プライベートアルゴリズムを提案する。 我々のアルゴリズムは、このコストを$O(varepsilon m)$に大幅に削減し、$varepsilon$はプライバシー予算である。 理論的には,本手法がランダム化応答と同一の結果をもたらすことを証明している。
• 参考スコア（独自算出の注目度）: 2.9123921488295768
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we propose a differentially private algorithm for publishing matrices aggregated from sparse vectors. These matrices include social network adjacency matrices, user-item interaction matrices in recommendation systems, and single nucleotide polymorphisms (SNPs) in DNA data. Traditionally, differential privacy in vector collection relies on randomized response, but this approach incurs high communication costs. Specifically, for a matrix with $N$ users, $n$ columns, and $m$ nonzero elements, conventional methods require $\Omega(n \times N)$ communication, making them impractical for large-scale data. Our algorithm significantly reduces this cost to $O(\varepsilon m)$, where $\varepsilon$ is the privacy budget. Notably, this is even lower than the non-private case, which requires $\Omega(m \log n)$ communication. Moreover, as the privacy budget decreases, communication cost further reduces, enabling better privacy with improved efficiency. We theoretically prove that our method yields results identical to those of randomized response, and experimental evaluations confirm its effectiveness in terms of accuracy, communication efficiency, and computational complexity.
• Abstract（参考訳）: 本研究では,スパースベクトルから集約された行列をパブリッシュするための微分プライベートアルゴリズムを提案する。 これらの行列には、ソーシャルネットワークの隣接行列、レコメンデーションシステムにおけるユーザ-item相互作用行列、DNAデータの単一ヌクレオチド多型(SNP)が含まれる。 伝統的に、ベクトル収集における差分プライバシーはランダムな応答に依存するが、このアプローチは通信コストが高い。 具体的には、$N$ユーザ、$n$列、$m$非ゼロ要素を持つ行列の場合、従来の手法では$\Omega(n \times N)$通信が必要であるため、大規模データには実用的ではない。 我々のアルゴリズムはこのコストを$O(\varepsilon)に大幅に削減する m)$, where $\varepsilon$はプライバシー予算です。 特に、これは、$\Omega(m \log)を必要とする非私的ケースよりもさらに低い。 n)$コミュニケーション。 さらに、プライバシ予算が減少するにつれて、通信コストはさらに削減され、効率が向上し、より優れたプライバシが実現される。 理論的には,提案手法がランダム化応答の結果と同一であることが証明され,実験により精度,通信効率,計算複雑性の点で有効性が確認された。

関連論文リスト

• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  本稿では,データ依存型ランダム化応答行列(DaRRM)アルゴリズムを提案する。 DaRRMはデータ依存ノイズ関数$gamma$でパラメータ化され、全てのプライベートアルゴリズムのクラスに対して効率的なユーティリティ最適化を可能にする。 本稿では,DARRMが共通ベースラインよりも2倍のプライバシゲインを,固定ユーティリティで確実に享受していることを示す。
  論文  参考訳（メタデータ） (2024-11-27T00:48:48Z)
• Communication Cost Reduction for Subgraph Counting under Local Differential Privacy via Hash Functions [3.1815791977708834]
  エッジローカル差分プライバシーの下でのサブグラフのカウントにおいて,ハッシュ関数を用いて通信コストを削減することを提案する。 サンプリングレートが$s$であれば,通信コストを$s2$に削減できる。
  論文  参考訳（メタデータ） (2023-12-12T08:12:18Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。 純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。 本稿では,総和,数,投票の単純な統計量について両問題を解く。
  論文  参考訳（メタデータ） (2023-09-27T17:09:36Z)
• Unbounded Differentially Private Quantile and Maximum Estimation [2.855485723554975]
  単純な$textttAboveThreshold$の呼び出しは、最高の量子化に対してより正確でロバストな見積もりを提供する。 我々は、textttAboveThreshold$を改良することで、広く使われているスパースベクトルテクニックのプライバシー保証を改善することができることを示す。
  論文  参考訳（メタデータ） (2023-05-02T03:23:07Z)
• Smooth Anonymity for Sparse Graphs [69.1048938123063]
  しかし、スパースデータセットを共有するという点では、差分プライバシーがプライバシのゴールドスタンダードとして浮上している。 本研究では、スムーズな$k$匿名性(スムーズな$k$匿名性)と、スムーズな$k$匿名性(スムーズな$k$匿名性)を提供する単純な大規模アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2022-07-13T17:09:25Z)
• 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)
• Computationally Efficient Approximations for Matrix-based Renyi's Entropy [33.72108955447222]
  最近開発された行列ベースのRenyiのエントロピーは、データ内の情報の計測を可能にする。 そのような量の計算には、PSD行列の$G$上のトレース演算子を$alpha$(つまり$tr(Galpha)$)の電力とする。 我々は、この新しいエントロピー汎函数に対する計算学的に効率的な近似を示し、その複雑性を$O(n2)$よりもはるかに小さくすることができる。
  論文  参考訳（メタデータ） (2021-12-27T14:59:52Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)

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

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