論文の概要: Clipped SGD Algorithms for Privacy Preserving Performative Prediction: Bias Amplification and Remedies
- arxiv url: http://arxiv.org/abs/2404.10995v1
- Date: Wed, 17 Apr 2024 02:17:05 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-18 15:34:07.514471
- Title: Clipped SGD Algorithms for Privacy Preserving Performative Prediction: Bias Amplification and Remedies
- Title(参考訳): 変形予測のためのプライバシ保護のためのクリッピングSGDアルゴリズム:バイアス増幅と改善
- Authors: Qiang Li, Michal Yemini, Hoi-To Wai,
- Abstract要約: クラッピング勾配降下(SGD)アルゴリズムは、プライバシー保護最適化の最も一般的なアルゴリズムの一つである。
本稿では,これらのアルゴリズムの収束特性を実演予測設定で検討する。
- 参考スコア(独自算出の注目度): 28.699424769503764
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Clipped stochastic gradient descent (SGD) algorithms are among the most popular algorithms for privacy preserving optimization that reduces the leakage of users' identity in model training. This paper studies the convergence properties of these algorithms in a performative prediction setting, where the data distribution may shift due to the deployed prediction model. For example, the latter is caused by strategical users during the training of loan policy for banks. Our contributions are two-fold. First, we show that the straightforward implementation of a projected clipped SGD (PCSGD) algorithm may converge to a biased solution compared to the performative stable solution. We quantify the lower and upper bound for the magnitude of the bias and demonstrate a bias amplification phenomenon where the bias grows with the sensitivity of the data distribution. Second, we suggest two remedies to the bias amplification effect. The first one utilizes an optimal step size design for PCSGD that takes the privacy guarantee into account. The second one uses the recently proposed DiceSGD algorithm [Zhang et al., 2024]. We show that the latter can successfully remove the bias and converge to the performative stable solution. Numerical experiments verify our analysis.
- Abstract(参考訳): クラッピング確率勾配勾配(SGD)アルゴリズムは、モデルトレーニングにおけるユーザのアイデンティティの漏洩を低減するために、プライバシ保護最適化のための最も一般的なアルゴリズムの一つである。
本稿では,これらのアルゴリズムの収束特性を,配置した予測モデルによりデータ分布がシフトする性能予測設定で検討する。
例えば、後者は、銀行の融資政策の訓練中に戦略的利用者によって引き起こされる。
私たちの貢献は2倍です。
まず,PCSGD(PCSGD)アルゴリズムの直接的実装は,実演安定解と比較して偏りのある解に収束することを示した。
偏差の大きさについて下界と上界を定量化し、偏差がデータ分布の感度で増大する偏差増幅現象を示す。
次に,バイアス増幅効果に対する2つの対策を提案する。
第一に、プライバシーの保証を考慮に入れたPCSGDの最適なステップサイズ設計を利用する。
2つ目は、最近提案されたDiceSGDアルゴリズム [Zhang et al , 2024] である。
後者は, バイアスを除去し, 安定解に収束することを示す。
数値解析実験は我々の分析を検証した。
関連論文リスト
- CURATE: Scaling-up Differentially Private Causal Graph Discovery [8.471466670802817]
因果グラフ発見(CGD)におけるユーザのプライバシを確保するために、差分プライバシー(DP)が採用されている。
CURATEは、適応的なプライバシー予算を持つDP-CGDフレームワークである。
CURATEは従来のDP-CGDアルゴリズムに比べてプライバシー保護の少ない高効率を実現していることを示す。
論文 参考訳(メタデータ) (2024-09-27T18:00:38Z) - Bias-Aware Minimisation: Understanding and Mitigating Estimator Bias in
Private SGD [56.01810892677744]
DP-SGDにおいて,サンプルごとの勾配ノルムとプライベート勾配オラクルの推定バイアスの関連性を示す。
BAM(Bias-Aware Minimisation)を提案する。
論文 参考訳(メタデータ) (2023-08-23T09:20:41Z) - 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) - On Private Online Convex Optimization: Optimal Algorithms in
$\ell_p$-Geometry and High Dimensional Contextual Bandits [9.798304879986604]
本研究では,分散分布からサンプリングしたストリーミングデータを用いてDPの凸最適化問題について検討し,逐次到着する。
また、プライベート情報に関連するパラメータを更新し、新しいデータ(しばしばオンラインアルゴリズム)に基づいてリリースする連続リリースモデルについても検討する。
提案アルゴリズムは,1pleq 2$のときの最適余剰リスクと,2pleqinfty$のときの非プライベートな場合の最先端の余剰リスクを線形時間で達成する。
論文 参考訳(メタデータ) (2022-06-16T12:09:47Z) - Bayes DistNet -- A Robust Neural Network for Algorithm Runtime
Distribution Predictions [1.8275108630751844]
ランダム化アルゴリズムは制約満足度問題 (CSP) やブール満足度問題 (SAT) の多くの最先端の解法で用いられている。
従来の最先端の手法は、入力インスタンスが従う固定パラメトリック分布を直接予測しようとする。
この新モデルは,低観測環境下での堅牢な予測性能と,検閲された観測処理を実現する。
論文 参考訳(メタデータ) (2020-12-14T01:15:39Z) - Direction Matters: On the Implicit Bias of Stochastic Gradient Descent
with Moderate Learning Rate [105.62979485062756]
本稿では,中等度学習におけるSGDの特定の正規化効果を特徴付けることを試みる。
SGDはデータ行列の大きな固有値方向に沿って収束し、GDは小さな固有値方向に沿って収束することを示す。
論文 参考訳(メタデータ) (2020-11-04T21:07:52Z) - Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。
MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
論文 参考訳(メタデータ) (2020-10-12T17:41:44Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳(メタデータ) (2020-06-24T06:01:24Z) - When Does Preconditioning Help or Hurt Generalization? [74.25170084614098]
本稿では,第1次および第2次手法のテキスト単純バイアスが一般化特性の比較にどのように影響するかを示す。
本稿では、バイアス分散トレードオフを管理するためのいくつかのアプローチと、GDとNGDを補間する可能性について論じる。
論文 参考訳(メタデータ) (2020-06-18T17:57:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。