論文の概要: Oneshot Differentially Private Top-k Selection
- arxiv url: http://arxiv.org/abs/2105.08233v1
- Date: Tue, 18 May 2021 02:18:01 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-19 14:09:00.847314
- Title: Oneshot Differentially Private Top-k Selection
- Title（参考訳）: oneshot differentially top-k selection
- Authors: Gang Qiao, Weijie J. Su, Li Zhang
- Abstract要約: 我々は、トップ$k$問題の高速、低歪み、および微分プライベートプリミティブを紹介します。
文献の既存手法と比較して、我々のアルゴリズムはカウントにLaplaceノイズを加え、上位の$k$ノイズ数とその推定値を一括してリリースする。
- 参考スコア（独自算出の注目度）: 23.88111547236874
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Being able to efficiently and accurately select the top-$k$ elements without
privacy leakage is an integral component of various data analysis tasks and has
gained significant attention. In this paper, we introduce the \textit{oneshot
mechanism}, a fast, low-distortion, and differentially private primitive for
the top-$k$ problem. Compared with existing approaches in the literature, our
algorithm adds Laplace noise to the counts and releases the top-$k$ noisy
counts and their estimates in a oneshot fashion, thereby substantially reducing
the computational cost while maintaining satisfying utility. Our proof of
privacy for this mechanism relies on a novel coupling technique that is of
independent theoretical interest. Finally, we apply the oneshot mechanism to
multiple hypothesis testing and ranking from pairwise comparisons and thus
obtain their differentially private counterparts.
- Abstract（参考訳）: プライバシリークのないトップ$1の要素を効率的かつ正確に選択できることは、さまざまなデータ分析タスクの不可欠なコンポーネントであり、大きな注目を集めている。
本稿では,上位k$問題に対する高速かつ低歪みかつ微分プライベートなプリミティブである「textit{oneshot mechanism}」を紹介する。
文献の既存手法と比較すると,本アルゴリズムは数にLaplaceノイズを付加し,高額なノイズ数とその推定値を一括してリリースすることにより,有効性を保ちながら計算コストを大幅に削減する。
このメカニズムのプライバシーの証明は、独立した理論的関心を持つ新しい結合技術に依存している。
最後に,複数仮説検定とペア比較によるランク付けにワンショット機構を適用し,その差分プライベートな結果を得る。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Breaking the Communication-Privacy-Accuracy Tradeoff with
$f$-Differential Privacy [51.11280118806893]
サーバが複数のユーザの協調的なデータ分析を,プライバシの懸念と限られた通信能力で調整する,フェデレートされたデータ分析問題を考える。
有限出力空間を有する離散値機構の局所的差分プライバシー保証を$f$-differential privacy (DP) レンズを用いて検討する。
より具体的には、様々な離散的評価機構の厳密な$f$-DP保証を導出することにより、既存の文献を前進させる。
論文 参考訳（メタデータ） (2023-02-19T16:58:53Z) - Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean
Estimation [8.9598796481325]
本稿では, アルゴリズムと計算複雑性の両面において, 異なる統計問題に対する観測結果について検討する。
プライベートスパース平均推定のための情報計算ギャップを確立する。
また、プライバシーによって引き起こされる情報計算のギャップを、いくつかの統計や学習問題に対して証明する。
論文 参考訳（メタデータ） (2022-11-01T20:03:41Z) - Smooth Anonymity for Sparse Graphs [69.1048938123063]
しかし、スパースデータセットを共有するという点では、差分プライバシーがプライバシのゴールドスタンダードとして浮上している。
本研究では、スムーズな$k$匿名性(スムーズな$k$匿名性)と、スムーズな$k$匿名性(スムーズな$k$匿名性)を提供する単純な大規模アルゴリズムを設計する。
論文 参考訳（メタデータ） (2022-07-13T17:09:25Z) - Learning Numeric Optimal Differentially Private Truncated Additive
Mechanisms [5.079561894598125]
実効性境界が強い付加的なメカニズムに対して,トランクテッドノイズを学習するためのツールを提案する。
平均単調な単調な音から, 対称性やその新しい音を考慮すれば十分であることを示す。
感度境界機構については, 平均単調な単調なノイズから, 対称性とその新しさを考えるのに十分であることを示す。
論文 参考訳（メタデータ） (2021-07-27T17:22:57Z) - On a Utilitarian Approach to Privacy Preserving Text Generation [5.123298347655088]
本研究では, 従来機構の近傍選択基準をパラメータ化する微分的プライベート機構のクラスを提案する。
Vickreyオークションは、第2位の価格のみを公表し、最も高い価格を非公開にしておくことで、第1位と第2位の隣人の選択のバランスをとる。
実際のテキスト分類データセットの実験では、同じ実証的なプライバシー保証を持つ既存の最先端技術と比較して、ユーティリティが最大50%改善されている。
論文 参考訳（メタデータ） (2021-04-23T23:13:43Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z) - Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy
Amplification by Shuffling [49.43288037509783]
ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。
私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
論文 参考訳（メタデータ） (2020-12-23T17:07:26Z) - Differential Privacy of Hierarchical Census Data: An Optimization
Approach [53.29035917495491]
国勢調査局(Census Bureaus)は、個人に関する機密情報を明らかにすることなく、大人口に関する社会経済的データをまとめて公開することに興味を持っている。
最近の出来事では、これらの組織が直面しているプライバシー上の課題がいくつか特定されている。
本稿では,階層的な個人数を解放する新たな差分プライバシ機構を提案する。
論文 参考訳（メタデータ） (2020-06-28T18:19:55Z) - Tight Differential Privacy for Discrete-Valued Mechanisms and for the
Subsampled Gaussian Mechanism Using FFT [6.929834518749884]
離散的な1次元の出力を持つアルゴリズムに対して,厳密な$(varepsilon,delta)$-privacy損失を評価するための数値会計法を提案する。
本稿では,従来の文献と同等のプライバシーで,ノイズ分散を最大75%低減できることを示す。
論文 参考訳（メタデータ） (2020-06-12T12:46:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。