論文の概要: 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$ の近傍関係に対して普遍的な準最適性をもたらすことを示す。

関連論文リスト

• Differential Privacy with Multiple Selections [52.5653572324012]
  感性のある機能を持つユーザがサーバから異なるプライベートな方法でレコメンデーションを得るような設定について検討する。 本稿では,サーバが複数のレコメンデーションを送信可能なマルチセレクションアーキテクチャを提案する。
  論文  参考訳（メタデータ） (2024-07-19T19:34:51Z)
• Bounded and Unbiased Composite Differential Privacy [25.427802467876248]
  差分プライバシ(DP)の目的は、隣接する2つのデータベース間で区別できない出力分布を生成することにより、プライバシを保護することである。 既存のソリューションでは、後処理やトランケーション技術を使ってこの問題に対処しようとしている。 本稿では,合成確率密度関数を用いて有界および非偏りの出力を生成する新しい微分プライベート機構を提案する。
  論文  参考訳（メタデータ） (2023-11-04T04:43:47Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。 純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。 本稿では,総和,数,投票の単純な統計量について両問題を解く。
  論文  参考訳（メタデータ） (2023-09-27T17:09:36Z)
• Differential Privacy via Distributionally Robust Optimization [8.409434654561789]
  非漸近的かつ無条件の最適性を保証するメカニズムのクラスを開発する。 上界 (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)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。 また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
  論文  参考訳（メタデータ） (2022-05-05T06:43:46Z)
• 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)

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

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