論文の概要: Differentially Private Partial Set Cover with Applications to Facility
Location
- arxiv url: http://arxiv.org/abs/2207.10240v2
- Date: Mon, 21 Aug 2023 14:22:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-23 02:54:26.003140
- Title: Differentially Private Partial Set Cover with Applications to Facility
Location
- Title（参考訳）: 差動的にプライベートな部分集合被覆と施設配置への応用
- Authors: George Z. Li and Dung Nguyen and Anil Vullikanti
- Abstract要約: また、2009guptadifferentiallyでは、Set Cover問題には差分プライバシー下での強い不可視性結果があることが観察された。
我々の研究では、これらの硬さは部分集合被覆問題に目を向けると解消され、そこでは、約$rhoin(0,1)$に対して、宇宙の要素の$rho$fractionをカバーしなければならない。
入力集合系のゆるい条件下では、非自明な近似保証付き明示的集合被覆を出力する差分プライベートなアルゴリズムを与える。
- 参考スコア（独自算出の注目度）: 16.810982345283687
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: It was observed in \citet{gupta2009differentially} that the Set Cover problem
has strong impossibility results under differential privacy. In our work, we
observe that these hardness results dissolve when we turn to the Partial Set
Cover problem, where we only need to cover a $\rho$-fraction of the elements in
the universe, for some $\rho\in(0,1)$. We show that this relaxation enables us
to avoid the impossibility results: under loose conditions on the input set
system, we give differentially private algorithms which output an explicit set
cover with non-trivial approximation guarantees. In particular, this is the
first differentially private algorithm which outputs an explicit set cover.
Using our algorithm for Partial Set Cover as a subroutine, we give a
differentially private (bicriteria) approximation algorithm for a facility
location problem which generalizes $k$-center/$k$-supplier with outliers. Like
with the Set Cover problem, no algorithm has been able to give non-trivial
guarantees for $k$-center/$k$-supplier-type facility location problems due to
the high sensitivity and impossibility results. Our algorithm shows that
relaxing the covering requirement to serving only a $\rho$-fraction of the
population, for $\rho\in(0,1)$, enables us to circumvent the inherent hardness.
Overall, our work is an important step in tackling and understanding
impossibility results in private combinatorial optimization.
- Abstract（参考訳）: \citet{gupta2009differentially} において、集合被覆問題は微分プライバシー下で強い不可能性を持つことが観測された。
我々の研究では、これらの硬度結果は部分集合被覆問題に目を向けると解消され、そこでは、ある$\rho\in(0,1)$に対して、宇宙の要素の$\rho$-fractionをカバーしなければならない。
入力集合系上のゆるい条件下では、非自明な近似保証を持つ明示的な集合被覆を出力する微分プライベートアルゴリズムを与える。
特に、これは明示的な集合被覆を出力する最初の微分プライベートアルゴリズムである。
部分集合被覆のアルゴリズムをサブルーチンとして使用し,施設位置問題に対して微分プライベート(bicriteria)近似アルゴリズムを与え,異常値付き$k$-center/$k$-supplierを一般化する。
セットカバー問題と同様に、高い感度と不合理性の結果により、$k$-center/$k$-supplier型施設配置問題に対して非自明な保証を与えるアルゴリズムは存在しない。
我々のアルゴリズムは、人口の$\rho$-fractionを$$\rho\in(0,1)$とすることで、カバー要件を緩和することで、固有の硬さを回避することができることを示している。
全体として、我々の研究は、プライベートな組合せ最適化の結果を扱い、理解するための重要なステップである。
関連論文リスト
- Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More [5.893651469750359]
マルチウェイカットと最小$k$cutのためのエッジ微分プライベートアルゴリズムを導入する。
最小$k$-cut問題に対して、指数的メカニズムと近似$k$-cutの数の有界性を組み合わせた別のアプローチを用いる。
論文 参考訳（メタデータ） (2024-07-09T14:46:33Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Fine-Grained Privacy Guarantees for Coverage Problems [3.2135945554116905]
差分プライバシの下で、Max CoverやSet Coverなどのカバレッジ問題に対して、近隣データベースの新たな概念を導入する。
グラフのノードプライバシに類似した、これらの問題の標準的なプライバシー概念とは対照的に、私たちの新しい定義はよりきめ細かいプライバシー保証を提供します。
論文 参考訳（メタデータ） (2024-03-05T21:40:10Z) - Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。
誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
論文 参考訳（メタデータ） (2024-01-17T09:23:25Z) - Differentially Private Online Item Pricing [1.7404865362620803]
本稿では,商品選択と入札という,購入者の入力ペアに対する差分プライバシを提供する小説を紹介する。
当社のアルゴリズムは、プライバシ保証付きサブリニアの$O(sqrtTlogT)を初めて提供する。
論文 参考訳（メタデータ） (2023-05-19T00:50:50Z) - Non-Euclidean Differentially Private Stochastic Convex Optimization [15.302167005107135]
雑音勾配降下法(SGD)アルゴリズムは低次元状態において最適過大なリスクを達成できることを示す。
私たちの作品は、規則性、均一凸性、均一な平滑性の概念など、規範空間の幾何学から概念を導き出します。
論文 参考訳（メタデータ） (2021-03-01T19:48:44Z) - 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) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。