論文の概要: Unifying Optimization and Dynamics to Parallelize Sequential Computation: A Guide to Parallel Newton Methods for Breaking Sequential Bottlenecks

• arxiv url: http://arxiv.org/abs/2603.16850v1
• Date: Tue, 17 Mar 2026 17:55:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-18 17:42:07.466795
• Title: Unifying Optimization and Dynamics to Parallelize Sequential Computation: A Guide to Parallel Newton Methods for Breaking Sequential Bottlenecks
• Title（参考訳）: 逐次計算の並列化のための最適化とダイナミクスの統一:逐次ボットネックの並列化のためのNewton法
• Authors: Xavier Gonzalez,
• Abstract要約: 準ニュートンおよび信頼領域アプローチに基づくスケーラブルで安定した並列ニュートン法を開発した。 本手法の近似精度と安定性に依存する固定点法に対して線形収束率を確立する。 並列化が動的系を確実に加速し、それができないときに特徴付ける、動的安定性に根ざした正確な条件を与える。
• 参考スコア（独自算出の注目度）: 1.2691047660244335
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Massively parallel hardware (GPUs) and long sequence data have made parallel algorithms essential for machine learning at scale. Yet dynamical systems, like recurrent neural networks and Markov chain Monte Carlo, were thought to suffer from sequential bottlenecks. Recent work showed that dynamical systems can in fact be parallelized across the sequence length by reframing their evaluation as a system of nonlinear equations, which can be solved with Newton's method using a parallel associative scan. However, these parallel Newton methods struggled with limitations, primarily inefficiency, instability, and lack of convergence guarantees. This thesis addresses these limitations with methodological and theoretical contributions, drawing particularly from optimization. Methodologically, we develop scalable and stable parallel Newton methods, based on quasi-Newton and trust-region approaches. The quasi-Newton methods are faster and more memory efficient, while the trust-region approaches are significantly more stable. Theoretically, we unify many fixed-point methods into our parallel Newton framework, including Picard and Jacobi iterations. We establish a linear convergence rate for these techniques that depends on the method's approximation accuracy and stability. Moreover, we give a precise condition, rooted in dynamical stability, that characterizes when parallelization provably accelerates a dynamical system and when it cannot. Specifically, the sign of the Largest Lyapunov Exponent of a dynamical system determines whether or not parallel Newton methods converge quickly. In sum, this thesis unlocks scalable and stable methods for parallelizing sequential computation, and provides a firm theoretical basis for when such techniques will and will not work. This thesis also serves as a guide to parallel Newton methods for researchers who want to write the next chapter in this ongoing story.
• Abstract（参考訳）: 大規模並列ハードウェア(GPU)と長いシーケンスデータにより、大規模な機械学習には並列アルゴリズムが不可欠である。 しかし、リカレントニューラルネットワークやマルコフ連鎖モンテカルロのような力学系は、シーケンシャルなボトルネックに悩まされていると考えられていた。 最近の研究で、力学系は非線形方程式の系としての評価をフレーミングすることで、実際にシーケンス長にわたって並列化できることが示され、これは並列連想スキャンを用いてニュートン法で解ける。 しかし、これらの並列ニュートン法は、主に非効率性、不安定性、収束保証の欠如といった制限に悩まされた。 この論文はこれらの制限に、特に最適化から引き出された方法論的および理論的貢献で対処する。 提案手法は,準ニュートン法と信頼領域法に基づいて,スケーラブルで安定した並列ニュートン法を開発する。 準ニュートン法は高速でメモリ効率が良く、信頼領域法ははるかに安定している。 理論的には、ピカールとヤコビの反復を含む多くの固定点法を並列ニュートンフレームワークに統合する。 近似精度と安定性に依存するこれらの手法に対して線形収束率を確立する。 さらに, 並列化が動的系を確実に加速し, 不可能な場合に特徴付ける, 動的安定性に根ざした正確な条件を与える。 具体的には、力学系の最も大きなリャプノフ指数の符号は、平行ニュートン法が急速に収束するかどうかを決定する。 まとめると、この論文はシーケンシャルな計算を並列化するスケーラブルで安定した手法を解き放ち、そのような手法がいつ有効で、いつうまくいかないかという理論的な根拠を提供する。 この論文は、この進行中の物語の次の章を書きたい研究者のための、ニュートン法と平行する手法のガイドとしても機能する。

関連論文リスト

• PRISM: Parallel Residual Iterative Sequence Model [52.26239951489612]
  我々はこの緊張を解決するためにPRISM(Parallel Residual Iterative Sequence Model)を提案する。 PRISMは、パラレル化可能な形で多段階精製の重要な構造特性を捉える、ソルバに着想を得た帰納バイアスを導入している。 この定式化が Rank-$L$ の蓄積を達成することを証明し、更新多様体を単一ステップの Rank-$1$ ボトルネックを超えて構造的に拡張する。
  論文  参考訳（メタデータ） (2026-02-11T12:39:41Z)
• A Unifying Framework for Parallelizing Sequential Models with Linear Dynamical Systems [41.44667250045256]
  固定点法を用いて逐次過程を並列に評価するためのいくつかの手法が提案されている。 これらの手法は線形力学系に基づく共通フレームワーク内で理解可能であることを示す。 この統一的な見解は、これらのテクニックの背後にある共通原則を強調し、特定の固定ポイントメソッドが最も効果的である可能性を明確にする。
  論文  参考訳（メタデータ） (2025-09-26T00:27:02Z)
• Towards Scalable and Stable Parallelization of Nonlinear RNNs [13.705742451466225]
  そこで我々は, 非線形RNNを並列に評価するDEERという手法を開発した。 準ニュートン近似を適用し、それらをニュートンに可逆収束させ、メモリを少なくし、より高速であることを示す。 これらの革新は、より大規模でより安定な非線形RNNの並列評価を可能にする。
  論文  参考訳（メタデータ） (2024-07-26T22:38:11Z)
• Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates [50.36933471975506]
  各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。 最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。 本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
  論文  参考訳（メタデータ） (2024-02-04T05:54:51Z)
• Guaranteed Conservation of Momentum for Learning Particle-based Fluid Dynamics [96.9177297872723]
  本稿では,学習物理シミュレーションにおける線形運動量を保証する新しい手法を提案する。 我々は、強い制約で運動量の保存を強制し、反対称的な連続的な畳み込み層を通して実現する。 提案手法により,学習シミュレータの物理的精度を大幅に向上させることができる。
  論文  参考訳（メタデータ） (2022-10-12T09:12:59Z)
• Newton methods based convolution neural networks using parallel processing [3.9220281834178463]
  畳み込みニューラルネットワークの訓練は高次元かつ非パラメトリック最適化問題である。 畳み込みニューラルネットワークのニュートン法は、サブサンプルのヘッセンニュートン法を用いてこれを扱う。 ミニバッチ計算ではシリアル処理の代わりに並列処理を用いてきた。
  論文  参考訳（メタデータ） (2021-12-02T16:42:27Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。 ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
  論文  参考訳（メタデータ） (2021-07-15T17:33:05Z)
• Parallelization Techniques for Verifying Neural Networks [52.917845265248744]
  検証問題に基づくアルゴリズムを反復的に導入し、2つの分割戦略を探索する。 また、ニューラルネットワークの検証問題を単純化するために、ニューロンアクティベーションフェーズを利用する、高度に並列化可能な前処理アルゴリズムも導入する。
  論文  参考訳（メタデータ） (2020-04-17T20:21:47Z)
• Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving [106.63673243937492]
  ニューラルネットワークの評価や自己回帰モデルからのサンプリングなどのフィードフォワード計算は、機械学習においてユビキタスである。 本稿では,非線形方程式の解法としてフィードフォワード計算の課題を定式化し,ジャコビ・ガウス・シーデル固定点法とハイブリッド法を用いて解を求める。 提案手法は, 並列化可能な繰り返し回数の削減(あるいは等値化)により, 元のフィードフォワード計算と全く同じ値が与えられることを保証し, 十分な並列化計算能力を付与する。
  論文  参考訳（メタデータ） (2020-02-10T10:11:31Z)

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

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