論文の概要: Privacy-Computation trade-offs in Private Repetition and Metaselection

• arxiv url: http://arxiv.org/abs/2410.19012v1
• Date: Tue, 22 Oct 2024 18:33:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-28 13:36:52.284700
• Title: Privacy-Computation trade-offs in Private Repetition and Metaselection
• Title（参考訳）: プライベートリピートとメタセレクションにおけるプライバシ計算のトレードオフ
• Authors: Kunal Talwar,
• Abstract要約: プライベート反復アルゴリズムは、一定の成功確率を持つ差分プライベートアルゴリズムを入力として、高い確率で成功するアルゴリズムに後押しする。 これらのタスクの既存のアルゴリズムは、プライバシコストの大きなオーバーヘッドを支払うか、計算コストの大きなオーバーヘッドを支払う。 これは、計算オーバーヘッドで異常確率が指数関数的に低下する非プライベートな設定とは対照的である。
• 参考スコア（独自算出の注目度）: 28.11248357424981
• License:
• Abstract: A Private Repetition algorithm takes as input a differentially private algorithm with constant success probability and boosts it to one that succeeds with high probability. These algorithms are closely related to private metaselection algorithms that compete with the best of many private algorithms, and private hyperparameter tuning algorithms that compete with the best hyperparameter settings for a private learning algorithm. Existing algorithms for these tasks pay either a large overhead in privacy cost, or a large overhead in computational cost. In this work, we show strong lower bounds for problems of this kind, showing in particular that for any algorithm that preserves the privacy cost up to a constant factor, the failure probability can only fall polynomially in the computational overhead. This is in stark contrast with the non-private setting, where the failure probability falls exponentially in the computational overhead. By carefully combining existing algorithms for metaselection, we prove computation-privacy tradeoffs that nearly match our lower bounds.
• Abstract（参考訳）: プライベート反復アルゴリズムは、一定の成功確率を持つ差分プライベートアルゴリズムを入力として、高い確率で成功するアルゴリズムに後押しする。 これらのアルゴリズムは、多くのプライベートアルゴリズムのベストと競合するプライベートメタ選択アルゴリズムと、プライベート学習アルゴリズムの最高のハイパーパラメータ設定と競合するプライベートハイパーパラメータチューニングアルゴリズムと密接に関連している。 これらのタスクの既存のアルゴリズムは、プライバシコストの大きなオーバーヘッドを支払うか、計算コストの大きなオーバーヘッドを支払う。 本研究では, プライバシのコストを一定に抑えるアルゴリズムの場合, 故障確率は計算オーバーヘッドにおいて多項式的にしか低下しないことを示す。 これは、計算オーバーヘッドで異常確率が指数関数的に低下する非プライベートな設定とは対照的である。 メタ選択のための既存のアルゴリズムを慎重に組み合わせることで、下限にほぼ一致する計算プライバシトレードオフを証明できる。

関連論文リスト

• Differentially Private Multiway and $k$-Cut [5.893651469750359]
  我々は,最小$k$カットおよびマルチウェイカット問題に対して,ほぼ最適な性能を実現する,エッジ微分プライベートアルゴリズムを導入する。 最小$k$-cut問題に対して、我々のアルゴリズムは、近似$k$-cutの個数に対する既知のバウンダリを活用し、固定プライバシーパラメータに対して最適な加算誤差$O(klog n)$のプライベートアルゴリズムを実現する。
  論文  参考訳（メタデータ） (2024-07-09T14:46:33Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Dynamic Privacy Allocation for Locally Differentially Private Federated Learning with Composite Objectives [10.528569272279999]
  本稿では,強い凸性を持つが非滑らかな問題に対する差分プライベートなフェデレーション学習アルゴリズムを提案する。 提案アルゴリズムは、共有情報に人工ノイズを加えてプライバシーを確保するとともに、時間変化のノイズ分散を動的に割り当て、最適化誤差の上限を最小化する。 解析結果から,提案手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2023-08-02T13:30:33Z)
• Private Networked Federated Learning for Nonsmooth Objectives [7.278228169713637]
  本稿では,非平滑な目的関数を解くためのネットワーク型フェデレーション学習アルゴリズムを提案する。 参加者の秘密性を保証するため、ゼロ集中型微分プライバシー概念(zCDP)を用いる。 プライバシ保証とアルゴリズムの正確な解への収束の完全な理論的証明を提供する。
  論文  参考訳（メタデータ） (2023-06-24T16:13:28Z)
• Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
  ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。 プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。 各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
  論文  参考訳（メタデータ） (2023-06-07T14:07:35Z)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。 また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
  論文  参考訳（メタデータ） (2022-05-05T06:43:46Z)
• Numerical Composition of Differential Privacy [22.523399777002926]
  我々は、任意の精度で微分プライベート(DP)アルゴリズムのプライバシー保証を最適に構成する高速アルゴリズムを提供する。 本手法は、DPアルゴリズムのプライバシー損失を定量化するために、プライバシー損失ランダム変数の概念に基づいている。
  論文  参考訳（メタデータ） (2021-06-05T09:20:15Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• No-Regret Algorithms for Private Gaussian Process Bandit Optimization [13.660643701487002]
  プライバシー保護統計のレンズによるガウス過程(GP)帯域最適化の至るところでの問題点を考察する。 均一なカーネル近似器とランダムな摂動を組み合わせた差分プライベートGPバンディット最適化のためのソリューションを提案する。 我々のアルゴリズムは最適化手順を通して微分プライバシを保持し、予測のためのサンプルパスに明示的に依存しない。
  論文  参考訳（メタデータ） (2021-02-24T18:52:24Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms [95.73230376153872]
  本稿では,反復学習アルゴリズムにおける一般化とプライバシ保護の関係を2つのステップで検討する。 我々は、$(varepsilon, delta)$-differential privacyは、マルチデータベース学習アルゴリズムに縛られる平均的な一般化を意味することを証明している。 次に,ほとんどの学習アルゴリズムが共有する反復的な性質が,プライバシーの保護とさらなる一般化にどのように影響するかを検討する。
  論文  参考訳（メタデータ） (2020-07-18T09:12:03Z)

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

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