論文の概要: Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More

• arxiv url: http://arxiv.org/abs/2407.06911v4
• Date: Fri, 08 Nov 2024 02:03:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-11 14:51:49.673423
• Title: Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More
• Title（参考訳）: グラフカットのための微分プライベートアルゴリズム:シフト機構アプローチなど
• Authors: Rishi Chandra, Michael Dinitz, Chenglin Fan, Zongrui Zou,
• Abstract要約: マルチウェイカットと最小$k$cutのためのエッジ微分プライベートアルゴリズムを導入する。 最小$k$-cut問題に対して、指数的メカニズムと近似$k$-cutの数の有界性を組み合わせた別のアプローチを用いる。
• 参考スコア（独自算出の注目度）: 5.893651469750359
• License:
• Abstract: In this paper, we address the challenge of differential privacy in the context of graph cuts, specifically focusing on the multiway cut and the minimum $k$-cut. We introduce edge-differentially private algorithms that achieve nearly optimal performance for these problems. Motivated by multiway cut, we propose the shifting mechanism, a general framework for private combinatorial optimization problems. This framework allows us to develop an efficient private algorithm with a multiplicative approximation ratio that matches the state-of-the-art non-private algorithm, improving over previous private algorithms that have provably worse multiplicative loss. We then provide a tight information-theoretic lower bound on the additive error, demonstrating that for constant $k$, our algorithm is optimal in terms of the privacy cost. The shifting mechanism also allows us to design private algorithm for the multicut and max-cut problems, with runtimes determined by the best non-private algorithms for these tasks. For the minimum $k$-cut problem we use a different approach, combining the exponential mechanism with bounds on the number of approximate $k$-cuts to get the first private algorithm with optimal additive error of $O(k\log n)$ (for a fixed privacy parameter). We also establish an information-theoretic lower bound that matches this additive error. Furthermore, we provide an efficient private algorithm even for non-constant $k$, including a polynomial-time 2-approximation with an additive error of $\tilde{O}(k^{1.5})$.
• Abstract（参考訳）: 本稿では,グラフカットの文脈における差分プライバシの課題について,特にマルチウェイカットと最低$k$カットに着目して論じる。 これらの問題に対して、ほぼ最適な性能を実現するために、エッジ微分プライベートアルゴリズムを導入する。 マルチウェイカットによってモチベーションを得た,プライベートな組合せ最適化問題に対する一般的なフレームワークであるシフト機構を提案する。 このフレームワークにより,従来の非プライベートアルゴリズムに適合する乗算近似比を持つ効率的なプライベートアルゴリズムの開発が可能となる。 次に、加算誤差の厳密な情報理論の下限を提供し、一定の$k$の場合、我々のアルゴリズムはプライバシーコストの観点から最適であることを示す。 また、このシフト機構により、これらのタスクに最適な非プライベートアルゴリズムによって決定されるランタイムを用いて、マルチカットおよび最大カット問題のプライベートアルゴリズムを設計できる。 最小の$k$-cut問題に対しては、指数的なメカニズムと近似的な$k$-cutの値のバウンダリを組み合わせて、最初のプライベートアルゴリズムに最適な加算誤差を$O(k\log n)$(固定されたプライバシパラメータの場合)を得る。 また、この加算誤差と一致する情報理論の下限も確立する。 さらに, 多項式時間2-近似を$\tilde{O}(k^{1.5})$の加算誤差で含む非定数$k$に対しても, 効率的なプライベートアルゴリズムを提供する。

関連論文リスト

• 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)

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

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