論文の概要: Fine-Grained Privacy Guarantees for Coverage Problems

• arxiv url: http://arxiv.org/abs/2403.03337v1
• Date: Tue, 5 Mar 2024 21:40:10 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-17 17:01:02.760735
• Title: Fine-Grained Privacy Guarantees for Coverage Problems
• Title（参考訳）: カバー問題に対する微粒化プライバシ保証
• Authors: Laxman Dhulipala, George Z. Li,
• Abstract要約: 差分プライバシの下で、Max CoverやSet Coverなどのカバレッジ問題に対して、近隣データベースの新たな概念を導入する。 グラフのノードプライバシに類似した、これらの問題の標準的なプライバシー概念とは対照的に、私たちの新しい定義はよりきめ細かいプライバシー保証を提供します。
• 参考スコア（独自算出の注目度）: 3.2135945554116905
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a new notion of neighboring databases for coverage problems such as Max Cover and Set Cover under differential privacy. In contrast to the standard privacy notion for these problems, which is analogous to node-privacy in graphs, our new definition gives a more fine-grained privacy guarantee, which is analogous to edge-privacy. We illustrate several scenarios of Set Cover and Max Cover where our privacy notion is desired one for the application. Our main result is an $\epsilon$-edge differentially private algorithm for Max Cover which obtains an $(1-1/e-\eta,\tilde{O}(k/\epsilon))$-approximation with high probability. Furthermore, we show that this result is nearly tight: we give a lower bound show that an additive error of $\Omega(k/\epsilon)$ is necessary under edge-differential privacy. Via group privacy properties, this implies a new algorithm for $\epsilon$-node differentially private Max Cover which obtains an $(1-1/e-\eta,\tilde{O}(fk/\epsilon))$-approximation, where $f$ is the maximum degree of an element in the set system. When $f\ll k$, this improves over the best known algorithm for Max Cover under pure (node) differential privacy, which obtains an $(1-1/e,\tilde{O}(k^2/\epsilon))$-approximation.
• Abstract（参考訳）: 差分プライバシの下で、Max CoverやSet Coverなどのカバレッジ問題に対して、近隣データベースの新たな概念を導入する。 グラフのノードプライバシに類似した、これらの問題の標準的なプライバシー概念とは対照的に、私たちの新しい定義は、エッジプライバシに類似した、よりきめ細かいプライバシー保証を提供します。 アプリケーションのプライバシの概念が望まれるSet CoverとMax Coverのシナリオをいくつか説明します。 我々の主な結果は、Max Coverに対する$\epsilon$-edge差分プライベートアルゴリズムであり、高い確率で$(1-1/e-\eta,\tilde{O}(k/\epsilon)$-approximationを得る。 エッジ差分プライバシーの下では$\Omega(k/\epsilon)$の加算誤差が必要であることを示す。 グループプライバシー特性により、$\epsilon$-nodely differentially private Max Cover は$(1-1/e-\eta,\tilde{O}(fk/\epsilon))$-approximation を得る。 1-1/e,\tilde{O}(k^2/\epsilon))$-approximationが得られる。

関連論文リスト

• A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility [4.7712438974100255]
  パーソナライズされたプライバシパラメータで$(epsilon_i,delta_i)$-PLDP設定をシャッフルする方法を示す。 shuffled $(epsilon_i,delta_i)$-PLDP process approximately saves $mu$-Gaussian Differential Privacy with mu = sqrtfrac2sum_i=1n frac1-delta_i1+eepsilon_i-max_ifrac1-delta_i1+e
  論文  参考訳（メタデータ） (2023-12-22T02:31:46Z)
• Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
  専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。 本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
  論文  参考訳（メタデータ） (2022-10-24T18:40:19Z)
• Differentially Private Partial Set Cover with Applications to Facility Location [16.810982345283687]
  また、2009guptadifferentiallyでは、Set Cover問題には差分プライバシー下での強い不可視性結果があることが観察された。 我々の研究では、これらの硬さは部分集合被覆問題に目を向けると解消され、そこでは、約$rhoin(0,1)$に対して、宇宙の要素の$rho$fractionをカバーしなければならない。 入力集合系のゆるい条件下では、非自明な近似保証付き明示的集合被覆を出力する差分プライベートなアルゴリズムを与える。
  論文  参考訳（メタデータ） (2022-07-21T00:43:14Z)
• Smooth Anonymity for Sparse Graphs [69.1048938123063]
  しかし、スパースデータセットを共有するという点では、差分プライバシーがプライバシのゴールドスタンダードとして浮上している。 本研究では、スムーズな$k$匿名性(スムーズな$k$匿名性)と、スムーズな$k$匿名性(スムーズな$k$匿名性)を提供する単純な大規模アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2022-07-13T17:09:25Z)
• Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
  DP-SGDで訓練されたモデルをリリースする際の個々の事例に対するプライバシー保証を特徴付ける。 ほとんどの例では、最悪のケースよりも強力なプライバシー保証を享受しています。 これは、モデルユーティリティの観点からは守られないグループが同時に、より弱いプライバシー保証を経験することを意味する。
  論文  参考訳（メタデータ） (2022-06-06T13:49:37Z)
• Differential Privacy in Personalized Pricing with Nonparametric Demand Models [15.036147440342338]
  本稿では,データプライバシ保護下でのテキスト非パラメトリック需要モデルを用いた動的パーソナライズ価格問題について検討する。 データプライバシの2つの概念が実践に広く適用されている。 提案手法は,CDP と LDP をそれぞれ満たし,価格決定と未知の要求を即時に学習するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-09-10T01:56:55Z)
• 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)
• Differentially Private Online Submodular Maximization [16.422215672356167]
  差分プライバシフィード(DP)を用いた基準制約下でのオンラインサブモジュラー関数の問題点について考察する。 共通有限基底集合上の$T$サブモジュラー関数のストリームがオンラインに届き、各時点において、決定者は関数を観察する前に$U$のほとんどの$k$要素を選択する必要がある。 意思決定者は、選択された集合で評価された関数に等しい報酬を得るとともに、期待の低い後悔を実現する一連の集合を学習することを目的とする。
  論文  参考訳（メタデータ） (2020-10-24T07:23:30Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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