論文の概要: 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-近似を含む形で提供する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。