論文の概要: Differentially Private Top-k Selection via Canonical Lipschitz Mechanism

• arxiv url: http://arxiv.org/abs/2201.13376v1
• Date: Mon, 31 Jan 2022 17:39:04 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-01 18:20:55.509187
• Title: Differentially Private Top-k Selection via Canonical Lipschitz Mechanism
• Title（参考訳）: カノニカルリプシッツ機構による個人別トップk選択
• Authors: Michael Shekelyan and Grigorios Loukides
• Abstract要約: リプシッツ機構は、ノイズ分布に対する強制リプシッツ特性を介して単一のDP耐性を持つ付加的なノイズ機構である。 Canyon loss関数はサブセットを、サブセットがトップ$k$になるために変更しなければならないユーザ数によって評価する。 構成自由な部分選択アプローチは、$Omega(log k)$ factorによってユーティリティ保証を改善する。
• 参考スコア（独自算出の注目度）: 5.270592093299472
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Selecting the top-$k$ highest scoring items under differential privacy (DP) is a fundamental task with many applications. This work presents three new results. First, the exponential mechanism, permute-and-flip and report-noisy-max, as well as their oneshot variants, are unified into the Lipschitz mechanism, an additive noise mechanism with a single DP-proof via a mandated Lipschitz property for the noise distribution. Second, this new generalized mechanism is paired with a canonical loss function to obtain the canonical Lipschitz mechanism, which can directly select k-subsets out of $d$ items in $O(dk+d \log d)$ time. The canonical loss function assesses subsets by how many users must change for the subset to become top-$k$. Third, this composition-free approach to subset selection improves utility guarantees by an $\Omega(\log k)$ factor compared to one-by-one selection via sequential composition, and our experiments on synthetic and real-world data indicate substantial utility improvements.
• Abstract（参考訳）: ディファレンシャルプライバシ(dp)の下で上位$k$の得点項目を選択することは、多くのアプリケーションで基本的なタスクである。 この研究は3つの新しい結果をもたらす。 第一に、指数的なメカニズムであるpermute-and-flip と report-noisy-max と、その一発の変種は、ノイズ分布に対する強制リプシッツ特性を介して単一のDP耐性を持つ付加的なノイズ機構であるlipschitz のメカニズムに統合される。 第二に、この新しい一般化されたメカニズムは正準損失関数と組み合わせて正準リプシッツ機構を得ることができ、これは$O(dk+d \log d)$時間で$d$アイテムからk-サブセットを直接選択できる。 canonical loss関数は、サブセットを最大$k$になるように変更しなければならないユーザ数によって、サブセットを評価する。 第3に,サブセット選択に対するこの構成自由アプローチは,逐次合成による1対1の選択と比較して,$\Omega(\log k)$因子による実用性保証を改善する。

関連論文リスト

• Differential Privacy with Multiple Selections [52.5653572324012]
  感性のある機能を持つユーザがサーバから異なるプライベートな方法でレコメンデーションを得るような設定について検討する。 本稿では,サーバが複数のレコメンデーションを送信可能なマルチセレクションアーキテクチャを提案する。
  論文  参考訳（メタデータ） (2024-07-19T19:34:51Z)
• Fair Submodular Cover [18.37610521373708]
  フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。 まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。 次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
  論文  参考訳（メタデータ） (2024-07-05T18:37:09Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Novel Quadratic Constraints for Extending LipSDP beyond Slope-Restricted Activations [52.031701581294804]
  ニューラルネットワークのリプシッツ境界は、高い時間保存保証で計算できる。 このギャップを埋めて,リプシッツを傾斜制限活性化関数を超えて拡張する。 提案した解析は一般であり、$ell$ および $ell_infty$ Lipschitz 境界を推定するための統一的なアプローチを提供する。
  論文  参考訳（メタデータ） (2024-01-25T09:23:31Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。 すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
  論文  参考訳（メタデータ） (2023-01-31T18:47:42Z)
• Adaptive Private-K-Selection with Adaptive K and Application to Multi-label PATE [19.344510696808282]
  我々は、差分的にプライベートなトップ$k$選択のためのエンドツーエンドのRenyi DPベースのフレームワークを提供する。 提案手法は,従来のトップ$選択アルゴリズムと比較して,プライバシとユーティリティのトレードオフを改善していることを示す。
  論文  参考訳（メタデータ） (2022-03-30T07:11:01Z)
• Oneshot Differentially Private Top-k Selection [23.88111547236874]
  我々は、トップ$k$問題の高速、低歪み、および微分プライベートプリミティブを紹介します。 文献の既存手法と比較して、我々のアルゴリズムはカウントにLaplaceノイズを加え、上位の$k$ノイズ数とその推定値を一括してリリースする。
  論文  参考訳（メタデータ） (2021-05-18T02:18:01Z)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。 我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
  論文  参考訳（メタデータ） (2021-04-06T20:25:57Z)
• Universal guarantees for decision tree induction via a higher-order splitting criterion [16.832966312395126]
  本アルゴリズムは,全対象関数に対して,一様分布に対して, -1,1n から -1,1$ の証明可能な保証を実現する。 我々の拡張の要点は、その属性の$f$と小さなサブセットの相関を考慮に入れた、新しい分割基準である。 我々のアルゴリズムは以下の保証を満たす: すべての対象関数 $f : -1,1n to -1,1$, sizes $sin mathbbN$, error parameters $epsilon$ に対して、決定を構成する。
  論文  参考訳（メタデータ） (2020-10-16T21:20:45Z)
• Regularized Submodular Maximization at Scale [45.914693923126826]
  亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。 正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
  論文  参考訳（メタデータ） (2020-02-10T02:37:18Z)

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

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