論文の概要: Smooth Lower Bounds for Differentially Private Algorithms via
Padding-and-Permuting Fingerprinting Codes
- arxiv url: http://arxiv.org/abs/2307.07604v1
- Date: Fri, 14 Jul 2023 19:58:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-18 19:07:41.792424
- Title: Smooth Lower Bounds for Differentially Private Algorithms via
Padding-and-Permuting Fingerprinting Codes
- Title（参考訳）: padding-and-permuting fingerprinting codesによる微分プライベートアルゴリズムの滑らかな下限
- Authors: Naty Peter, Eliad Tsfadia, Jonathan Ullman
- Abstract要約: 本稿では,フィンガープリントコードにパディング・アンド・パータスク変換を適用し,ハードインスタンスを生成する手法を提案する。
本手法の適用性について,様々な設定で新しい下界を提供することにより述べる。
- 参考スコア（独自算出の注目度）: 4.801975818473341
- 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.
In this work, we present a simple method to generate hard instances by
applying a padding-and-permuting transformation to a fingerprinting code. We
illustrate the applicability of this 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 new 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, 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平均クラスタリングのためのDPアルゴリズムの加算誤差に対する下限は, 一定の乗算誤差に対して厳密な乗算誤差の関数である。
3) 低精度な状態における行列の上特異ベクトルをDPの下で推定する下界は、シンガルとシュタインケ(NeurIPS 2021)によって研究されたDP部分空間推定の特別な場合である。
我々の主な技術は、指紋コードにパディング・アンド・パーミュート変換を適用することである。
しかし、既存の指紋認証コード(例えばTardosのコード)へのブラックボックスアクセスを使って結果を証明する代わりに、Dwork et al. (FOCS 2015) や Bun et al. (SODA 2017) よりも強い新しい指紋認証補題を開発し、その下位境界を補題から直接証明する。
特に我々の補題は、独立した関心を持つ最適な率(多対数因子まで)で、より単純なフィンガープリントコード構成を与えます。
関連論文リスト
- 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) - Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
データフィッティングと正規化のための大域的スムーズなロバスト推定器に基づくロバストな非剛性登録のための定式化を提案する。
本稿では,L-BFGS を用いた最小二乗問題の解法に,各繰り返しを減らし,最大化最小化アルゴリズムを適用した。
論文 参考訳（メタデータ） (2020-04-09T01:45:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。