論文の概要: Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies

• arxiv url: http://arxiv.org/abs/2404.10995v2
• Date: Thu, 30 Jan 2025 15:32:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-31 15:12:09.396446
• Title: Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
• Title（参考訳）: 変形予測のためのクリッピングSGDアルゴリズム:バイアスと治療をクリッピングするためのタイトバウンド
• Authors: Qiang Li, Michal Yemini, Hoi-To Wai,
• Abstract要約: 本稿では,決定依存型データ分布を用いたクリッピング勾配降下法(SGD)アルゴリズムの収束性について検討する。 我々は,SGDGDが安定解に達するのを防ぐクリッピング演算子によって生じるクリッピングバイアス(PCSGD)を特徴付ける。 また,本解析は,後者のアルゴリズムが性能設定におけるクリッピングバイアスを含まないことを示すために拡張された。
• 参考スコア（独自算出の注目度）: 28.699424769503764
• License:
• Abstract: This paper studies the convergence of clipped stochastic gradient descent (SGD) algorithms with decision-dependent data distribution. Our setting is motivated by privacy preserving optimization algorithms that interact with performative data where the prediction models can influence future outcomes. This challenging setting involves the non-smooth clipping operator and non-gradient dynamics due to distribution shifts. We make two contributions in pursuit for a performative stable solution using clipped SGD algorithms. First, we characterize the clipping bias with projected clipped SGD (PCSGD) algorithm which is caused by the clipping operator that prevents PCSGD from reaching a stable solution. When the loss function is strongly convex, we quantify the lower and upper bounds for this clipping bias and demonstrate a bias amplification phenomenon with the sensitivity of data distribution. When the loss function is non-convex, we bound the magnitude of stationarity bias. Second, we propose remedies to mitigate the bias either by utilizing an optimal step size design for PCSGD, or to apply the recent DiceSGD algorithm [Zhang et al., 2024]. Our analysis is also extended to show that the latter algorithm is free from clipping bias in the performative setting. Numerical experiments verify our findings.
• Abstract（参考訳）: 本稿では,クリッピング確率勾配勾配(SGD)アルゴリズムと決定依存データ分布の収束性について検討する。 我々の設定は、予測モデルが将来の結果に影響を与える可能性のあるパフォーマンスデータと相互作用するプライバシー保護最適化アルゴリズムによって動機付けられている。 この挑戦的な設定には、非滑らかなクリッピング演算子と、分散シフトによる非段階的なダイナミクスが含まれる。 クリップされたSGDアルゴリズムを用いて,性能安定解の探索に2つの貢献をする。 まず,PCSGDが安定解に達するのを防ぐクリッピング演算子によって生じるクリッピングバイアスを,投影されたクリッピングSGD (PCSGD) アルゴリズムで特徴づける。 損失関数が強く凸している場合、このクリッピングバイアスの上下境界を定量化し、データ分布の感度でバイアス増幅現象を示す。 損失関数が非凸であるとき、定常バイアスの大きさを束縛する。 次に、PCSGDの最適ステップサイズ設計を利用するか、最新のDiceSGDアルゴリズム[Zhang et al , 2024]を適用することでバイアスを軽減する方法を提案する。 また,本解析は,後者のアルゴリズムが性能設定におけるクリッピングバイアスを含まないことを示すために拡張された。 数値実験は我々の発見を検証した。

関連論文リスト

• Privacy of the last iterate in cyclically-sampled DP-SGD on nonconvex composite losses [2.532202013576547]
  微分プライベート勾配(DP-SGD)は、微分プライベートモデルパラメータの列を生成するために反復する反復機械学習アルゴリズムのファミリーである。 最終段階の会計は困難であり、既存の作業はほとんどの実装で満たされていない強い仮定を必要とする。 損失関数の小さなステップサイズとリプシッツ滑らかさの現実的な仮定の下で、最後のイテレーションに対して新しいRenyi差分プライバシー(R)上限を提供する。
  論文  参考訳（メタデータ） (2024-07-07T02:35:55Z)
• Differentially Private SGD Without Clipping Bias: An Error-Feedback Approach [62.000948039914135]
  Differentially Private Gradient Descent with Gradient Clipping (DPSGD-GC) を使用して、差分プライバシ(DP)がモデルパフォーマンス劣化の犠牲となることを保証する。 DPSGD-GCに代わる新しいエラーフィードバック(EF)DPアルゴリズムを提案する。 提案アルゴリズムに対するアルゴリズム固有のDP解析を確立し,R'enyi DPに基づくプライバシ保証を提供する。
  論文  参考訳（メタデータ） (2023-11-24T17:56:44Z)
• 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)
• Efficient Private SCO for Heavy-Tailed Data via Averaged Clipping [40.69950711262191]
  我々は、差分プライベート(DP)を保証する重み付きデータに対する差分プライベート凸最適化について検討する。 我々は,制約付きおよび制約なし凸問題に対するAClipped-dpSGDというアルゴリズムに対して,新たな収束結果を確立し,複雑性境界を改善した。
  論文  参考訳（メタデータ） (2022-06-27T01:39:15Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  勾配降下(SGD)により最適化された高次元におけるランダム特徴(RF)回帰特性について検討する。 本研究では, RF回帰の高精度な非漸近誤差境界を, 定常および適応的なステップサイズSGD設定の下で導出する。 理論的にも経験的にも二重降下現象を観察する。
  論文  参考訳（メタデータ） (2021-10-13T17:47: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)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。 我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
  論文  参考訳（メタデータ） (2020-06-12T02:45:21Z)

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

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