論文の概要: Differentially Private Multiway and $k$-Cut

• arxiv url: http://arxiv.org/abs/2407.06911v1
• Date: Tue, 9 Jul 2024 14:46:33 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-10 17:47:35.240107
• Title: Differentially Private Multiway and $k$-Cut
• Title（参考訳）: Differentially Private Multiway と $k$-Cut
• Authors: Rishi Chandra, Michael Dinitz, Chenglin Fan, Zongrui Zou,
• Abstract要約: 我々は,最小$k$カットおよびマルチウェイカット問題に対して,ほぼ最適な性能を実現する,エッジ微分プライベートアルゴリズムを導入する。 最小$k$-cut問題に対して、我々のアルゴリズムは、近似$k$-cutの個数に対する既知のバウンダリを活用し、固定プライバシーパラメータに対して最適な加算誤差$O(klog n)$のプライベートアルゴリズムを実現する。
• 参考スコア（独自算出の注目度）: 5.893651469750359
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we address the challenge of differential privacy in the context of graph cuts, specifically focusing on the minimum $k$-cut and multiway cut problems. We introduce edge-differentially private algorithms that achieve nearly optimal performance for these problems. For the multiway cut problem, we first provide a private algorithm with a multiplicative approximation ratio that matches the state-of-the-art non-private algorithm. We then present a tight information-theoretic lower bound on the additive error, demonstrating that our algorithm on weighted graphs is near-optimal for constant $k$. For the minimum $k$-cut problem, our algorithms leverage a known bound on the number of approximate $k$-cuts, resulting in a private algorithm with optimal additive error $O(k\log n)$ for fixed privacy parameter. We also establish a information-theoretic lower bound that matches this additive error. Additionally, we give an efficient private algorithm for $k$-cut even for non-constant $k$, including a polynomial-time 2-approximation with an additive error of $\widetilde{O}(k^{1.5})$.
• Abstract（参考訳）: 本稿では,グラフカットの文脈における差分プライバシの課題,特に$k$カットとマルチウェイカットの問題に焦点をあてる。 これらの問題に対して、ほぼ最適な性能を実現するために、エッジ微分プライベートアルゴリズムを導入する。 マルチウェイカット問題に対して、我々はまず、最先端の非プライベートアルゴリズムと一致する乗法近似比のプライベートアルゴリズムを提供する。 次に、重み付きグラフ上のアルゴリズムが定数$k$に対してほぼ最適であることを証明し、加法誤差の厳密な情報理論の下界を示す。 最小$k$-cut問題に対して、我々のアルゴリズムは、近似$k$-cutの個数に対する既知のバウンダリを活用し、固定プライバシーパラメータに対して最適な加算誤差$O(k\log n)$のプライベートアルゴリズムを実現する。 また、この加算誤差と一致する情報理論の下限も確立する。 さらに、非コンスタントな$k$に対しても、$k$カットの効率的なプライベートアルゴリズムを、$\widetilde{O}(k^{1.5})$の加算誤差を持つ多項式時間2-近似を含む形で提供する。

関連論文リスト

• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• DP-Dueling: Learning from Preference Feedback without Compromising User Privacy [32.58099924135157]
  ユーザ好みでアクティブな学習を行うための,最初の微分プライベートなダリング帯域幅アルゴリズムを提案する。 我々のアルゴリズムは、ほぼ最適性能で計算効率が良い。 我々は結果を任意の一般的な決定空間に拡張し、潜在的に無限の腕を持つ$d$次元を持つ。
  論文  参考訳（メタデータ） (2024-03-22T09:02:12Z)
• Near-Optimal Differentially Private k-Core Decomposition [2.859324824091086]
  我々は、$k$-core分解のための$eps$-edge差分秘密アルゴリズムが乗算誤差なしでコア数を出力し、$O(textlog(n)/eps)$加法誤差を示す。 これは乗法誤差における2の因子による以前の作業を改善すると同時に、ほぼ最適加法誤差を与える。
  論文  参考訳（メタデータ） (2023-12-12T20:09:07Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
  専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。 本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
  論文  参考訳（メタデータ） (2022-10-24T18:40:19Z)
• 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)
• Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism [16.996435043565594]
  純微分プライバシーを受ける独立サンプルの共分散で$d$正確率分布の平均を推定するアルゴリズムを初めて与える。 我々の主な手法は、強力なSum of Squares法(SoS)を用いて微分プライベートアルゴリズムを設計する新しいアプローチである。
  論文  参考訳（メタデータ） (2021-11-25T09:31:15Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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