論文の概要: Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes

• arxiv url: http://arxiv.org/abs/2307.07604v4
• Date: Wed, 3 Jul 2024 19:22:10 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-09 01:11:44.799804
• Title: Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes
• Title（参考訳）: パディング・アンド・パーフォーミングフィンガープリント符号による個人差分アルゴリズムの滑らかな下界
• Authors: Naty Peter, Eliad Tsfadia, Jonathan Ullman,
• Abstract要約: 微分プライベートアルゴリズムのサンプル複雑性に基づいて,スムーズな下界を生成するための新しいフレームワークとツールを提案する。 我々の主な技術は、指紋コードにパディング・アンド・パーミュート変換を適用することである。 我々はDwork et al. (FOCS 2015) と Bun et al. (SODA 2017) より強い新しい指紋認証補題を開発する。
• 参考スコア（独自算出の注目度）: 4.553891255178496
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Fingerprinting arguments, first introduced by Bun, Ullman, and Vadhan (STOC 2014), are the most widely used method for establishing lower bounds on the sample complexity or error of approximately differentially private (DP) algorithms. Still, there are many problems in differential privacy for which we don't know suitable lower bounds, and even for problems that we do, the lower bounds are not smooth, and usually become vacuous when the error is larger than some threshold. We present a new framework and tools to generate smooth lower bounds on the sample complexity of differentially private algorithms satisfying very weak accuracy. We illustrate the applicability of our method by providing new lower bounds in various settings: 1. A tight lower bound for DP averaging in the low-accuracy regime, which in particular implies a lower bound for the private 1-cluster problem introduced by Nissim, Stemmer, and Vadhan (PODS 2016). 2. A lower bound on the additive error of DP algorithms for approximate k-means clustering and general (k,z)-clustering, as a function of the multiplicative error, which is tight for a constant multiplication error. 3. A lower bound for estimating the top singular vector of a matrix under DP in low-accuracy regimes, which is a special case of DP subspace estimation studied by Singhal and Steinke (NeurIPS 2021). Our main technique is to apply a padding-and-permuting transformation to a fingerprinting code. However, rather than proving our results using a black-box access to an existing fingerprinting code (e.g., Tardos' code), we develop a new fingerprinting lemma that is stronger than those of Dwork et al. (FOCS 2015) and Bun et al. (SODA 2017), and prove our lower bounds directly from the lemma. Our lemma, in particular, gives a simpler fingerprinting code construction with optimal rate (up to polylogarithmic factors) that is of independent interest.
• Abstract（参考訳）: Bun, Ullman, Vadhan (STOC 2014) が最初に導入したフィンガープリンティング引数は、サンプルの複雑さや約微分プライベート(DP)アルゴリズムの誤差を下げるための最も広く使われている手法である。 しかし、差分プライバシーには、適切な下位境界が分かっていない問題が多く、私たちがしている問題においても、下位境界は滑らかではなく、エラーがしきい値より大きい場合は通常空白になる。 非常に弱い精度を満足する微分プライベートアルゴリズムのサンプル複雑性に対して,スムーズな下界を生成するための新しいフレームワークとツールを提案する。 1)低精度政権におけるDP平均化の厳密な下限は,特にNissim, Stemmer, Vadhan (PODS 2016) が導入したプライベート1クラスタ問題に対する下限を意味する。 2) 近似k平均クラスタリングと一般(k,z)クラスタリングのためのDPアルゴリズムの加算誤差に対する下限を乗算誤差の関数として用いた。 3) 低精度な状態における行列の頂点特異ベクトルをDPの下で推定する下界は、シンガルとシュタインケ(NeurIPS 2021)によって研究されたDP部分空間推定の特別な場合である。 我々の主な技術は、指紋コードにパディング・アンド・パーミュート変換を適用することである。 しかし、既存の指紋認証コード(例えば、Tardosのコード)へのブラックボックスアクセスを使って結果を証明する代わりに、Dwork et al (FOCS 2015) や Bun et al (SODA 2017) よりも強い新しい指紋認証補題を開発し、この補題から直接下位境界を証明します。 私たちの補題は、特に、独立した関心を持つ最適な速度(多言語的要因まで)で、より単純なフィンガープリントコードの構築を提供します。

関連論文リスト

• The Cost of Shuffling in Private Gradient Based Optimization [40.31928071333575]
  その結果, DP-ShuffleGはDP-SGDと比較して, データのシャッフル処理により過大なリスクが生じることがわかった。 我々は、プライベートな最適化に公開データサンプルを統合するハイブリッドアプローチである textitInterleaved-ShuffleG を提案する。
  論文  参考訳（メタデータ） (2025-02-05T22:30:00Z)
• User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
  サンプルスカース方式では,各ユーザが少数のサンプルしか持たないため,以下の結果が得られる。 近似DPについては,任意の項目レベルDPアルゴリズムをユーザレベルDPアルゴリズムに汎用変換する。 ユーザレベル設定に指数的機構(McSherry, Talwar FOCS 2007)を適用するための簡単な手法を提案する。
  論文  参考訳（メタデータ） (2023-09-21T21:51:55Z)
• Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints [8.261182037130407]
  局所差分プライバシー (LDP) と通信制約の両面から, 単純な二分仮説テストについて検討する。 我々はその結果をミニマックス最適かインスタンス最適かのどちらかとみなす。
  論文  参考訳（メタデータ） (2023-01-09T18:36:49Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。 DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
  論文  参考訳（メタデータ） (2022-06-27T03:45:02Z)
• Differentially Private Learning Needs Hidden State (Or Much Faster Convergence) [9.429448411561541]
  差分的にプライベートな学習は、厳密な拘束力を持って、隠れた状態のプライバシ分析や、高速な収束を必要とすることを示す。 私たちの収束するプライバシー分析は、差異のあるプライベートな学習が、厳密な拘束力を持って、隠れた状態のプライバシ分析や、高速な収束を必要とすることを示している。
  論文  参考訳（メタデータ） (2022-03-10T13:31:08Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)
• Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative Drift [9.853329403413701]
  乗法的ドリフトシナリオに対する単純な負のドリフト定理は既存の解析を単純化できることを示す。 我々は、非エリート変異に基づく進化アルゴリズムのランタイムにおける下位境界を証明するための最も一般的なツールの1つである集団法において、Lehre's emph negative drift in populations法(PPSN 2010)についてより詳細に論じる。
  論文  参考訳（メタデータ） (2020-05-02T15:10:09Z)

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

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