論文の概要: Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation
- arxiv url: http://arxiv.org/abs/2412.10130v1
- Date: Fri, 13 Dec 2024 13:22:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-16 15:03:08.330345
- Title: Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation
- Title（参考訳）: 入力摂動によるプライベート・ミニマル・スパンニングツリーの最適境界
- Authors: Rasmus Pagh, Lukas Retschmeier, Hao Wu, Hanwen Zhang,
- Abstract要約: 近似最小スパンニングツリー(MST)のプライベートリリース問題について検討する。
既存のプライベートMSTアルゴリズムはトレードオフに直面し、計算効率または精度を犠牲にする。
重みベクトルをプライベートにするのに十分でない入力のランダムな摂動により、結果は非公開となり、最先端のエラー保証が達成される。
- 参考スコア（独自算出の注目度）: 11.345141417475956
- License:
- Abstract: We study the problem of privately releasing an approximate minimum spanning tree (MST). Given a graph $G = (V, E, \vec{W})$ where $V$ is a set of $n$ vertices, $E$ is a set of $m$ undirected edges, and $ \vec{W} \in \mathbb{R}^{|E|} $ is an edge-weight vector, our goal is to publish an approximate MST under edge-weight differential privacy, as introduced by Sealfon in PODS 2016, where $V$ and $E$ are considered public and the weight vector is private. Our neighboring relation is $\ell_\infty$-distance on weights: for a sensitivity parameter $\Delta_\infty$, graphs $ G = (V, E, \vec{W}) $ and $ G' = (V, E, \vec{W}') $ are neighboring if $\|\vec{W}-\vec{W}'\|_\infty \leq \Delta_\infty$. Existing private MST algorithms face a trade-off, sacrificing either computational efficiency or accuracy. We show that it is possible to get the best of both worlds: With a suitable random perturbation of the input that does not suffice to make the weight vector private, the result of any non-private MST algorithm will be private and achieves a state-of-the-art error guarantee. Furthermore, by establishing a connection to Private Top-k Selection [Steinke and Ullman, FOCS '17], we give the first privacy-utility trade-off lower bound for MST under approximate differential privacy, demonstrating that the error magnitude, $\tilde{O}(n^{3/2})$, is optimal up to logarithmic factors. That is, our approach matches the time complexity of any non-private MST algorithm and at the same time achieves optimal error. We complement our theoretical treatment with experiments that confirm the practicality of our approach.
- Abstract（参考訳）: 約最小スパンニングツリー(MST)をプライベートにリリースする問題について検討する。
グラフ $G = (V, E, \vec{W})$ where $V$ is a set of $n$ vertices, $E$ is a set of $m$ undirected edges, $ \vec{W} \in \mathbb{R}^{|E|} $ is a edge-weight vector, 我々のゴールは、エッジ-weight differential privacyの下で近似MSTを公開することである。
我々の隣り合う関係はウェイト上の$\ell_\infty$-distanceである: 感度パラメータ $\Delta_\infty$, graphs $ G = (V, E, \vec{W}) $ and $ G' = (V, E, \vec{W}') $ is neighboring if $\|\vec{W}-\vec{W}'\|_\infty \leq \Delta_\infty$.
既存のプライベートMSTアルゴリズムはトレードオフに直面し、計算効率または精度を犠牲にする。
重みベクトルをプライベートにするのに十分でない入力のランダムな摂動により、任意のプライベートなMSTアルゴリズムの結果はプライベートとなり、最先端のエラー保証が達成される。
さらに、プライベートトップk選択(Steinke and Ullman, FOCS '17]への接続を確立することにより、近似差分プライバシーの下でのMSTに対する最初のプライバシー利用トレードオフを低く設定し、エラーサイズ$\tilde{O}(n^{3/2})$が対数因子に最適であることを実証する。
すなわち、我々の手法は、任意の非プライベートMSTアルゴリズムの時間的複雑さと一致し、同時に最適な誤差を達成する。
我々は,我々のアプローチの実用性を確認する実験で理論的処理を補完する。
関連論文リスト
- Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
本稿では,データ依存型ランダム化応答行列(DaRRM)アルゴリズムを提案する。
DaRRMはデータ依存ノイズ関数$gamma$でパラメータ化され、全てのプライベートアルゴリズムのクラスに対して効率的なユーティリティ最適化を可能にする。
本稿では,DARRMが共通ベースラインよりも2倍のプライバシゲインを,固定ユーティリティで確実に享受していることを示す。
論文 参考訳（メタデータ） (2024-11-27T00:48:48Z) - Faster Private Minimum Spanning Trees [11.72102598708538]
本稿では,時間内で動作中の既存手法の実用性に適合する新しい差分プライベートMSTアルゴリズムを提案する。
我々は,少なくとも$O(n2)$カットエッジを$O(sqrtn log n)$ timeでサンプリングすることのできるデータ構造を示す。
論文 参考訳（メタデータ） (2024-08-13T16:00:30Z) - Private Zeroth-Order Nonsmooth Nonconvex Optimization [41.05664717242051]
非平滑な目的と非平滑な目的に対するプライベート最適化のための新しいゼロ階アルゴリズムを提案する。
データセットサイズが$M$であれば、アルゴリズムはプライバシの差分を見つける。
目的はスムーズではないが、プライバシーがある。
無料の$tdepsilon$
論文 参考訳（メタデータ） (2024-06-27T23:57:01Z) - 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) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment [7.4288915613206505]
本研究では,バンディットとフルインフォメーションの両方のフィードバックの下で,オンライン学習環境における個人差分問題について検討する。
差分的な私的盗賊に対しては、UTBとトンプソンサンプリングに基づくアルゴリズムを同時に提案し、最適な$O左(sum_j: Delta_j>0 fracln(T)min leftDelta_j, epsilon right)$ minimax lower boundとする。
同じ差分プライベートなフル情報設定に対しては、$epsilon$-differentially も提示する。
論文 参考訳（メタデータ） (2021-02-16T02:48:16Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - A bounded-noise mechanism for differential privacy [3.9596068699962323]
ベクトル $vecx(i) の平均 $frac1nsum_i=1n vecx(i)$ を [0,1]k$ で出力し、任意の $vecx(i)$ に対してプライバシーを保持します。
我々は、ほとんどの値$delta$に対して最適な$ell_infty$エラーを持つ$(epsilon,delta)$-privateメカニズムを示す。
論文 参考訳（メタデータ） (2020-12-07T16:03:21Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。