論文の概要: Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential

• arxiv url: http://arxiv.org/abs/2510.02735v1
• Date: Fri, 03 Oct 2025 05:35:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-06 16:35:52.279288
• Title: Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential
• Title（参考訳）: Goldstein subdifferential を用いた非凸損失に対する投射確率勾配の定量的収束解析
• Authors: Yuping Zheng, Andrew Lamperski,
• Abstract要約: 本稿では,非同相収束測度に対する予測分散低減法の解析について述べる。 収束は、制約によるSGDゴールドスタイン部分微分勾配への勾配である。
• 参考スコア（独自算出の注目度）: 2.179637644332717
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stochastic gradient descent (SGD) is the main algorithm behind a large body of work in machine learning. In many cases, constraints are enforced via projections, leading to projected stochastic gradient algorithms. In recent years, a large body of work has examined the convergence properties of projected SGD for non-convex losses in asymptotic and non-asymptotic settings. Strong quantitative guarantees are available for convergence measured via Moreau envelopes. However, these results cannot be compared directly with work on unconstrained SGD, since the Moreau envelope construction changes the gradient. Other common measures based on gradient mappings have the limitation that convergence can only be guaranteed if variance reduction methods, such as mini-batching, are employed. This paper presents an analysis of projected SGD for non-convex losses over compact convex sets. Convergence is measured via the distance of the gradient to the Goldstein subdifferential generated by the constraints. Our proposed convergence criterion directly reduces to commonly used criteria in the unconstrained case, and we obtain convergence without requiring variance reduction. We obtain results for data that are independent, identically distributed (IID) or satisfy mixing conditions ($L$-mixing). In these cases, we derive asymptotic convergence and $O(N^{-1/3})$ non-asymptotic bounds in expectation, where $N$ is the number of steps. In the case of IID sub-Gaussian data, we obtain almost-sure asymptotic convergence and high-probability non-asymptotic $O(N^{-1/5})$ bounds. In particular, these are the first non-asymptotic high-probability bounds for projected SGD with non-convex losses.
• Abstract（参考訳）: 確率勾配降下(SGD)は、機械学習における大きな仕事の背後にある主要なアルゴリズムである。 多くの場合、制約は射影を通して強制され、射影確率勾配アルゴリズムが導かれる。 近年,漸近的および非漸近的セッティングにおける非凸損失に対する投影されたSGDの収束特性について研究が進められている。 モローエンベロープを通じて測定される収束には、強い量的保証が利用できる。 しかし、モロー包絡構造が勾配を変化させるため、これらの結果は非拘束なSGDの研究と直接比較することはできない。 勾配写像に基づく他の一般的な測度は、ミニバッチのような分散還元法が用いられる場合にのみ収束が保証されるという制限がある。 本稿では,コンパクト凸集合上の非凸損失に対する投影されたSGDの解析を行う。 収束度は、制約によって生成されたゴールドスタイン部分微分への勾配距離を介して測定される。 提案した収束基準は, 制約のない場合で一般的に使用される基準に直接還元し, ばらつきを伴わずに収束を得る。 独立で、同一分散(IID)または混合条件を満たすデータ(L$-mixing)について結果を得る。 これらの場合、漸近収束と$O(N^{-1/3})$非漸近境界を期待して導き、$N$はステップの数である。 IIDサブガウスデータの場合、ほぼ確実に漸近収束と高確率非漸近$O(N^{-1/5})$境界を得る。 特に、これらは非凸損失を持つ射影SGDに対する最初の非漸近的高確率境界である。

関連論文リスト

• Stochastic Gradient Descent in Non-Convex Problems: Asymptotic Convergence with Relaxed Step-Size via Stopping Time Methods [13.677904140815386]
  Gradient Descent (SGD) は機械学習の研究で広く使われている。 本稿では,より緩やかなステップサイズ条件下でのSGDの収束解析法を提案する。
  論文  参考訳（メタデータ） (2025-04-17T02:56:20Z)
• Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
  グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。 有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
  論文  参考訳（メタデータ） (2023-12-13T21:41:06Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。 解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
  論文  参考訳（メタデータ） (2023-10-28T18:53:41Z)
• Demystifying the Myths and Legends of Nonconvex Convergence of SGD [17.445810977264067]
  勾配勾配勾配(SGD)とその変種は、大規模最適化問題の解法の主要な仕事場である。 分析として,勾配の非収束に関連する神話や伝説について考察した。
  論文  参考訳（メタデータ） (2023-10-19T17:58:59Z)
• A High-dimensional Convergence Theorem for U-statistics with Applications to Kernel-based Testing [3.469038201881982]
  次数2のU-統計量に対して収束定理を証明し、データ次元$d$はサンプルサイズ$n$でスケールすることができる。 我々はこの理論を、高次元性能の研究が困難である2つのカーネルベースの分散テスト MMD と KSD に適用した。
  論文  参考訳（メタデータ） (2023-02-11T12:49:46Z)
• On the Convergence of mSGD and AdaGrad for Stochastic Optimization [0.696125353550498]
  凸降下(SGD)は、過去10年間に機械学習に大きく開発され、広く応用されてきた。 モーメントベースのSGD(mSGD)や適応的勾配最適化(AdaGrad)など、多くの競合や応用においてSGDよりも優れている修正SGD型アルゴリズムもある。 我々は,機械学習における任意の滑らかな(不可能かもしれない)損失関数に対するmSGDとAdaGradの収束解析に着目する。
  論文  参考訳（メタデータ） (2022-01-26T22:02:21Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)

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

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