論文の概要: On the Parallel Complexity of Multilevel Monte Carlo in Stochastic Gradient Descent

• arxiv url: http://arxiv.org/abs/2310.02402v2
• Date: Tue, 10 Oct 2023 10:00:53 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-13 01:59:40.228599
• Title: On the Parallel Complexity of Multilevel Monte Carlo in Stochastic Gradient Descent
• Title（参考訳）: 多レベルモンテカルロの確率勾配明度における並列複素性について
• Authors: Kei Ishikawa
• Abstract要約: ニューラル微分方程式において、マルチレベルカルロ法(MLMC法)は、単純モンテカルロ法よりも理論的に複雑であることが知られている。 本稿では,以前に計算した部品によるシーケンシャルCリサイクルの並列化を劇的に低減する遅延勾配推定器を提案する。 提案した推定器は, 摂食収束率をわずかに低下させるコストで, 勾配当たりの平均並列複雑性を確実に低減する。
• 参考スコア（独自算出の注目度）: 0.8158530638728501
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the stochastic gradient descent (SGD) for sequential simulations such as the neural stochastic differential equations, the Multilevel Monte Carlo (MLMC) method is known to offer better theoretical computational complexity compared to the naive Monte Carlo approach. However, in practice, MLMC scales poorly on massively parallel computing platforms such as modern GPUs, because of its large parallel complexity which is equivalent to that of the naive Monte Carlo method. To cope with this issue, we propose the delayed MLMC gradient estimator that drastically reduces the parallel complexity of MLMC by recycling previously computed gradient components from earlier steps of SGD. The proposed estimator provably reduces the average parallel complexity per iteration at the cost of a slightly worse per-iteration convergence rate. In our numerical experiments, we use an example of deep hedging to demonstrate the superior parallel complexity of our method compared to the standard MLMC in SGD.
• Abstract（参考訳）: 神経確率微分方程式のような逐次シミュレーションのための確率勾配勾配(SGD)では、マルチレベルモンテカルロ法(MLMC)は、単純モンテカルロ法よりも理論的に複雑であることが知られている。 しかし、実際にはmlmcは、ナイーブモンテカルロ法と同等の大きな並列複雑性のため、現代のgpuのような超並列コンピューティングプラットフォームではスケールが貧弱である。 この問題に対処するため,計算済み勾配成分をSGDの初期段階から再利用することにより,MLMCの並列複雑性を大幅に低減する遅延MLMC勾配推定器を提案する。 提案する推定器は, シナリオ毎の収束率をやや下回るコストで, イテレーション毎の平均並列複雑性を低減できる。 数値実験では,SGD の標準 MLMC と比較して,本手法の並列複雑性が優れていることを示すために,ディープヘッジの例を用いる。

関連論文リスト

• Convergence Acceleration of Markov Chain Monte Carlo-based Gradient Descent by Deep Unfolding [5.584060970507506]
  本研究では,深部展開法(deep unfolding)と呼ばれる深部学習手法を用いて,最適化問題(COP)のトレーニング可能なサンプリングベース解法を提案する。 提案手法は,マルコフ鎖モンテカルロ(MCMC)と勾配勾配を結合したオオゼキ法に基づいている。 数個のCOPの数値計算結果から,提案した解法はオリジナルの大関法と比較して収束速度を著しく向上させた。
  論文  参考訳（メタデータ） (2024-02-21T08:21:48Z)
• Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo [30.4930148381328]
  拡散に基づくモンテカルロ (DMC) は、等尺条件を超えた一般目標分布から試料を採取する手法である。 DMCは、高い勾配の複雑さに遭遇し、その結果、得られたサンプルのエラー耐性$epsilon$に指数関数的に依存する。 本稿では,新しい再帰に基づくスコア推定法に基づくRS-DMCを提案する。 私たちのアルゴリズムは、人気のあるLangevinベースのアルゴリズムよりもはるかに高速です。
  論文  参考訳（メタデータ） (2024-01-12T02:33:57Z)
• Online Variational Sequential Monte Carlo [49.97673761305336]
  我々は,計算効率が高く正確なモデルパラメータ推定とベイジアン潜在状態推定を提供する変分連続モンテカルロ法(VSMC)を構築した。 オンラインVSMCは、パラメータ推定と粒子提案適応の両方を効率よく、完全にオンザフライで実行することができる。
  論文  参考訳（メタデータ） (2023-12-19T21:45:38Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Aiming towards the minimizers: fast convergence of SGD for overparametrized problems [25.077446336619378]
  本稿では,勾配法と同一のケース複雑性を有する勾配法を提案する。 既存の保証は全て勾配法で小さなステップを踏む必要があり、結果として収束速度ははるかに遅くなる。 我々は,線形出力層を用いた十分に広いフィードフォワードニューラルネットワークのトレーニングにおいて,この条件が成り立つことを実証した。
  論文  参考訳（メタデータ） (2023-06-05T05:21:01Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  共分散行列の明示的な構成を避ける新しい推論手法を提案する。 本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。 いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
  論文  参考訳（メタデータ） (2022-02-25T16:35:26Z)
• An adaptive Hessian approximated stochastic gradient MCMC method [12.93317525451798]
  後方からのサンプリング中に局所的幾何情報を組み込む適応型ヘッセン近似勾配MCMC法を提案する。 我々は,ネットワークの空間性を高めるために,等級に基づく重み付け法を採用する。
  論文  参考訳（メタデータ） (2020-10-03T16:22:15Z)
• Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters [152.03852111442114]
  モデルに依存しないメタラーニング(MAML)は非常に成功したアルゴリズムメタラーニングの実践であるが、高い計算複雑性を持つ。 本稿では,その複雑さがANILの全体的な収束性能に大きく影響することを示す。
  論文  参考訳（メタデータ） (2020-06-16T19:57:48Z)

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

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