論文の概要: Streaming Krylov-Accelerated Stochastic Gradient Descent

• arxiv url: http://arxiv.org/abs/2505.07046v1
• Date: Sun, 11 May 2025 16:36:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-13 20:21:49.180182
• Title: Streaming Krylov-Accelerated Stochastic Gradient Descent
• Title（参考訳）: クリロフ加速確率勾配のストリーミング
• Authors: Stephen Thomas,
• Abstract要約: 本稿では,新しい最適化手法であるSKA-SGD(Streaming Krylov-Accelerated Gradient Descent)を提案する。 低次元クリロフ部分空間に射影することで、不条件問題に対する収束を加速する。 実験結果から,SKA-SGDは標準SGDとAdamの収束率と最終誤差を著しく上回ることがわかった。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present SKA-SGD (Streaming Krylov-Accelerated Stochastic Gradient Descent), a novel optimization approach that accelerates convergence for ill-conditioned problems by projecting stochastic gradients onto a low-dimensional Krylov subspace. Directly inspired by recent advances in s-step Conjugate Gradient methods with streaming Gauss-Seidel Gram solvers \cite{dambra2025sstep}, our method extends these techniques to the stochastic optimization domain. Our approach combines three key innovations: (1) projection coefficients computed via a single streaming Gauss-Seidel iteration, which is mathematically equivalent to Modified Gram-Schmidt orthogonalization; (2) a Chebyshev polynomial basis for constructing the Krylov subspace, providing superior numerical stability; and (3) efficient implementation for AMD GPUs using HIP. We prove that our streaming approach achieves a backward error near machine precision with $O(s^2)$ complexity rather than $O(s^3)$, where $s$ is the Krylov subspace dimension. Experimental results demonstrate that SKA-SGD significantly outperforms standard SGD and Adam in convergence rate and final error, particularly for problems with condition numbers exceeding $10^3$. GPU performance analysis reveals a crossover point where communication-avoiding benefits outweigh computational overhead, typically occurring at moderate scale ($p \approx 64$ processors) for problem sizes $n \geq 10^6$.
• Abstract（参考訳）: SKA-SGD(Streaming Krylov-Accelerated Stochastic Gradient Descent)は,低次元クリロフ部分空間に確率勾配を投影することにより,不条件問題の収束を加速する新しい最適化手法である。 ストリームガウス・シーデル・グラハム・ソルバを用いたSステップ共役勾配法の最近の進歩にインスパイアされた本手法は,これらの手法を確率的最適化領域に拡張する。 提案手法は,(1) 1 つのストリーミングガウス・シーデル反復によって計算される投影係数と,(2) クリロフ部分空間を構築するためのチェビシェフ多項式基底,(3) HIP を用いたAMD GPU の効率的な実装,の3つの重要な革新と組み合わせる。 我々のストリーミング手法は、$O(s^3)$ではなく$O(s^2)$の複雑さでマシン精度に近い後方誤差を達成していることを証明している。 実験結果から,SKA-SGDはコンバージェンスレートと最終誤差において標準SGDとAdamを著しく上回り,特に条件数10^3$を超える問題に対して有意な性能を示した。 GPUパフォーマンス分析は、通信回避の利点が計算オーバーヘッドを上回るというクロスオーバーポイントを明らかにし、通常、問題サイズが$n \geq 10^6$に対して、適度なスケール(p \approx 64$ CPU)で発生する。

関連論文リスト

• Second-order Optimization of Gaussian Splats with Importance Sampling [51.95046424364725]
  3D Gaussian Splatting (3DGS) は、高品質で高速な推論時間のため、新しいビューレンダリングに広く用いられている。 本稿では,Levenberg-Marquardt (LM) と Conjugate Gradient (CG) に基づく新しい2階最適化手法を提案する。 提案手法は標準LMよりも3倍の高速化を実現し,ガウス数が少ない場合のAdamを6倍の6倍の速さで上回る。
  論文  参考訳（メタデータ） (2025-04-17T12:52:08Z)
• Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimization [26.328847475942894]
  我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。 我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
  論文  参考訳（メタデータ） (2023-06-03T23:31:27Z)
• On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
  機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。 本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2023-05-30T17:47:27Z)
• Stochastic Zeroth order Descent with Structured Directions [10.604744518360464]
  我々は, 有限差分法であるStructured Zeroth Order Descent (SSZD)を導入・解析し, 集合 $lleq d 方向の勾配を近似し, $d は周囲空間の次元である。 凸凸に対して、すべての$c1/2$に対して$O( (d/l) k-c1/2$)$ 上の関数の収束はほぼ確実に証明する。
  論文  参考訳（メタデータ） (2022-06-10T14:00:06Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
  論文  参考訳（メタデータ） (2022-03-30T11:39:00Z)
• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization [104.96004056928474]
  本稿では,非コンケーブ最小値問題に対する高速適応勾配降下法を提案する。 我々は,本手法が,ミニバッチサイズが$O(kappa2.5epsilon-3)$のより低いサンプル複雑性に達することを示す。
  論文  参考訳（メタデータ） (2021-06-30T14:47:09Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)

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

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