論文の概要: Near-Universally-Optimal Differentially Private Minimum Spanning Trees
- arxiv url: http://arxiv.org/abs/2404.15035v1
- Date: Tue, 23 Apr 2024 13:39:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-24 13:51:55.424577
- Title: Near-Universally-Optimal Differentially Private Minimum Spanning Trees
- Title(参考訳): ほぼ普遍的に最適な微分プライベートな最小スパンニング木
- Authors: Richard Hladík, Jakub Tětek,
- Abstract要約: 我々は、最小スパンニングツリーを概解する単純な微分プライベートなメカニズムが、$ell_infty$ 近傍関係に対する普遍的最適性という意味では、ほぼ最適であることを示す。
我々は MST の指数的機構を時間内に実装し、これは $ell_infty$ と $ell_infty$ の近傍関係の両方に対して普遍的な準最適性をもたらすことを示した。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Devising mechanisms with good beyond-worst-case input-dependent performance has been an important focus of differential privacy, with techniques such as smooth sensitivity, propose-test-release, or inverse sensitivity mechanism being developed to achieve this goal. This makes it very natural to use the notion of universal optimality in differential privacy. Universal optimality is a strong instance-specific optimality guarantee for problems on weighted graphs, which roughly states that for any fixed underlying (unweighted) graph, the algorithm is optimal in the worst-case sense, with respect to the possible setting of the edge weights. In this paper, we give the first such result in differential privacy. Namely, we prove that a simple differentially private mechanism for approximately releasing the minimum spanning tree is near-optimal in the sense of universal optimality for the $\ell_1$ neighbor relation. Previously, it was only known that this mechanism is nearly optimal in the worst case. We then focus on the $\ell_\infty$ neighbor relation, for which the described mechanism is not optimal. We show that one may implement the exponential mechanism for MST in polynomial time, and that this results in universal near-optimality for both the $\ell_1$ and the $\ell_\infty$ neighbor relations.
- Abstract(参考訳): この目標を達成するために、スムーズな感度、提案-テスト-リリース、逆感度メカニズムなどの技術が開発されている。
これにより、微分プライバシーにおける普遍的最適性の概念を非常に自然に利用することができる。
普遍的最適性(Universal optimality)は、重み付きグラフ上の問題に対して強いインスタンス固有の最適性を保証するものである。
本稿では,差分プライバシーに関する最初の結果を与える。
すなわち、最小スパンニングツリーをおよそ解放する単純な微分プライベートなメカニズムが、$\ell_1$ 近傍関係に対する普遍的最適性という意味では、ほぼ最適であることを示す。
以前は、このメカニズムが最悪の場合、ほぼ最適であるとしか分かっていなかった。
次に、記述されたメカニズムが最適でない$\ell_\infty$近傍関係に焦点を当てる。
多項式時間で MST の指数的機構を実装することができ、これは$\ell_1$ と $\ell_\infty$ の近傍関係に対して普遍的な準最適性をもたらすことを示す。
関連論文リスト
- On User-Level Private Convex Optimization [59.75368670035683]
ユーザレベルの差分プライバシー保証を伴う凸最適化(SCO)のための新しいメカニズムを提案する。
我々のメカニズムは損失に対する滑らかさの仮定を必要としない。
私たちの限界は、ユーザレベルのプライバシーに必要な最小限のユーザが、その次元に依存しない、最初のものです。
論文 参考訳(メタデータ) (2023-05-08T17:47:28Z) - Differential Privacy via Distributionally Robust Optimization [6.080354168357744]
非漸近的かつ無条件の最適性を保証するメカニズムのクラスを開発する。
上界 (primal) は実装可能な摂動に対応しており、その準最適性は下界 (dual) で有界である。
数値実験により、我々の摂動は、人工的および標準ベンチマーク問題に関する文献から得られた最も優れた結果よりも優れていることが示された。
論文 参考訳(メタデータ) (2023-04-25T09:31:47Z) - General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean
Estimation [58.03500081540042]
プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。
すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
論文 参考訳(メタデータ) (2023-01-31T18:47:42Z) - Cactus Mechanisms: Optimal Differential Privacy Mechanisms in the
Large-Composition Regime [12.420941209631742]
本研究では,多数の構成の限界における最適微分プライバシー機構の設計について検討する。
この体制では、最高のプライバシーメカニズムは、Kullback-Leiblerの発散を最小限にするものである。
我々は、量子化アプローチが最適なメカニズムに任意に近づくことができることを示す。
論文 参考訳(メタデータ) (2022-06-25T20:05:50Z) - Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。
また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
論文 参考訳(メタデータ) (2022-05-05T06:43:46Z) - Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。
次に,政策最適化におけるコミット率の概念を紹介する。
第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
論文 参考訳(メタデータ) (2021-10-29T06:35:44Z) - Non-Euclidean Differentially Private Stochastic Convex Optimization [15.302167005107135]
雑音勾配降下法(SGD)アルゴリズムは低次元状態において最適過大なリスクを達成できることを示す。
私たちの作品は、規則性、均一凸性、均一な平滑性の概念など、規範空間の幾何学から概念を導き出します。
論文 参考訳(メタデータ) (2021-03-01T19:48:44Z) - Optimal Approximation -- Smoothness Tradeoffs for Soft-Max Functions [73.33961743410876]
ソフトマックス関数は近似と滑らかさの2つの主要な効率尺度を持つ。
近似と滑らか性の異なる尺度に対する最適近似-滑らか性トレードオフを同定する。
これにより、新しいソフトマックス関数が生まれ、それぞれ異なる用途に最適である。
論文 参考訳(メタデータ) (2020-10-22T05:19:58Z) - Bilevel Optimization for Differentially Private Optimization in Energy
Systems [53.806512366696275]
本稿では,入力に敏感な制約付き最適化問題に対して,差分プライバシーを適用する方法について検討する。
本稿は, 自然仮定の下では, 大規模非線形最適化問題に対して, 双レベルモデルを効率的に解けることを示す。
論文 参考訳(メタデータ) (2020-01-26T20:15:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。