論文の概要: 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$に対しても, 効率的なプライベートアルゴリズムを提供する。
関連論文リスト
- Privacy-Computation trade-offs in Private Repetition and Metaselection [28.11248357424981]
プライベート反復アルゴリズムは、一定の成功確率を持つ差分プライベートアルゴリズムを入力として、高い確率で成功するアルゴリズムに後押しする。
これらのタスクの既存のアルゴリズムは、プライバシコストの大きなオーバーヘッドを支払うか、計算コストの大きなオーバーヘッドを支払う。
これは、計算オーバーヘッドで異常確率が指数関数的に低下する非プライベートな設定とは対照的である。
論文 参考訳（メタデータ） (2024-10-22T18:33:02Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Near-Optimal Differentially Private k-Core Decomposition [2.859324824091086]
我々は、$k$-core分解のための$eps$-edge差分秘密アルゴリズムが乗算誤差なしでコア数を出力し、$O(textlog(n)/eps)$加法誤差を示す。
これは乗法誤差における2の因子による以前の作業を改善すると同時に、ほぼ最適加法誤差を与える。
論文 参考訳（メタデータ） (2023-12-12T20:09:07Z) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳（メタデータ） (2023-06-07T14:07:35Z) - 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) - 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) - Numerical Composition of Differential Privacy [22.523399777002926]
我々は、任意の精度で微分プライベート(DP)アルゴリズムのプライバシー保証を最適に構成する高速アルゴリズムを提供する。
本手法は、DPアルゴリズムのプライバシー損失を定量化するために、プライバシー損失ランダム変数の概念に基づいている。
論文 参考訳（メタデータ） (2021-06-05T09:20:15Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。