論文の概要: Single-seed generation of Brownian paths and integrals for adaptive and high order SDE solvers
- arxiv url: http://arxiv.org/abs/2405.06464v3
- Date: Sat, 25 May 2024 10:46:46 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-29 05:27:58.089883
- Title: Single-seed generation of Brownian paths and integrals for adaptive and high order SDE solvers
- Title（参考訳）: 適応および高次SDEソルバのためのブラウンパスと積分の単列生成
- Authors: Andraž Jelinčič, James Foster, Patrick Kidger,
- Abstract要約: 適応型高次解法を新しいVBTアルゴリズムで実現した2つの応用について述べる。
適応解法を用いて高揮発性CIRモデルをシミュレートし、定常ステップの収束順序を2倍以上に向上する。
MCMC問題に対して, 適応的第三次ランゲヴィン解法を応用し, 関数評価の10分の1しか用いない。
- 参考スコア（独自算出の注目度）: 9.879281328700577
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Despite the success of adaptive time-stepping in ODE simulation, it has so far seen few applications for Stochastic Differential Equations (SDEs). To simulate SDEs adaptively, methods such as the Virtual Brownian Tree (VBT) have been developed, which can generate Brownian motion (BM) non-chronologically. However, in most applications, knowing only the values of Brownian motion is not enough to achieve a high order of convergence; for that, we must compute time-integrals of BM such as $\int_s^t W_r \, dr$. With the aim of using high order SDE solvers adaptively, we extend the VBT to generate these integrals of BM in addition to the Brownian increments. A JAX-based implementation of our construction is included in the popular Diffrax library (https://github.com/patrick-kidger/diffrax). Since the entire Brownian path produced by VBT is uniquely determined by a single PRNG seed, previously generated samples need not be stored, which results in a constant memory footprint and enables experiment repeatability and strong error estimation. Based on binary search, the VBT's time complexity is logarithmic in the tolerance parameter $\varepsilon$. Unlike the original VBT algorithm, which was only precise at some dyadic times, we prove that our construction exactly matches the joint distribution of the Brownian motion and its time integrals at any query times, provided they are at least $\varepsilon$ apart. We present two applications of adaptive high order solvers enabled by our new VBT. Using adaptive solvers to simulate a high-volatility CIR model, we achieve more than twice the convergence order of constant stepping. We apply an adaptive third order underdamped or kinetic Langevin solver to an MCMC problem, where our approach outperforms the No U-Turn Sampler, while using only a tenth of its function evaluations.
- Abstract（参考訳）: ODEシミュレーションにおける適応型タイムステッピングの成功にもかかわらず、SDE(Stochastic Differential Equations)の応用例はこれまでにない。
適応的にSDEをシミュレートするために、VBT(Virtual Brownian Tree)のような手法が開発され、非時間的にブラウン運動(BM)を生成することができる。
しかし、ほとんどのアプリケーションでは、ブラウン運動の値のみを知って高次収束を達成するには不十分であり、そのため、$\int_s^t W_r \, dr$ のようなBMの時間積分を計算する必要がある。
高次SDEソルバを適応的に使用することを目的として、我々は、ブラウン増分に加えて、これらのBM積分を生成するためにVBTを拡張した。
私たちの構築のJAXベースの実装は、人気のあるDiffraxライブラリ(https://github.com/patrick-kidger/diffrax)に含まれている。
VBTが生成するブラウンパス全体が単一のPRNGシードによって一意に決定されるため、以前に生成されたサンプルを格納する必要がなく、結果としてメモリフットプリントが一定となり、実験の再現性と強いエラー推定が可能になる。
バイナリ検索に基づいて、VBTの時間複雑性は許容パラメータ$\varepsilon$の対数である。
元のVBTアルゴリズムとは違い、我々の構成は、少なくとも$\varepsilon$の差がある場合、ブラウン運動とその時間積分の結合分布と正確に一致することを証明している。
適応型高次解法を新しいVBTで実現した2つの応用について述べる。
適応解法を用いて高揮発性CIRモデルをシミュレートし、定常ステップの収束順序を2倍以上に向上する。
MCMC問題に対して, 適応型第3次ランゲヴィン解法を応用し, 提案手法は機能評価の10分の1しか使用せず, No U-Turn Samplerよりも優れていることを示した。
関連論文リスト
- Provable Accuracy Bounds for Hybrid Dynamical Optimization and Sampling [1.5551894637785635]
本稿では,Langevin Diffusion (BLD) アルゴリズムをブロックすることにより,ハイブリッド LNLS の非漸近収束を保証する。
デバイスの変化が有限であれば、ステップ時間、雑音強度、関数パラメータの2-ワッサーシュタインバイアスに明確な境界を与える。
論文 参考訳（メタデータ） (2024-10-08T22:03:41Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Distributed Extra-gradient with Optimal Complexity and Communication
Guarantees [60.571030754252824]
複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。
モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。
そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
論文 参考訳（メタデータ） (2023-08-17T21:15:04Z) - Generative Modelling of L\'{e}vy Area for High Order SDE Simulation [5.9535699822923]
L'evyGANはブラウン増分に基づくL'evy領域の近似サンプルを生成するディープラーニングモデルである。
L'evyGANは関節分布と辺縁分布の両方を測定するいくつかの指標で最先端のパフォーマンスを示す。
論文 参考訳（メタデータ） (2023-08-04T16:38:37Z) - Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for
Multi-Block Bilevel Optimization [43.74656748515853]
非定常多重ブロック双レベル最適化問題には$mgg 1$低レベル問題があり、機械学習において重要な応用がある。
a)標準BO問題の最先端の複雑さを1ブロックに合わせること,(b)サンプルブロックごとのサンプルをサンプリングして並列高速化すること,(c)高次元ヘッセン行列推定器の逆計算を避けること,の3つの特性を実現することを目的とする。
論文 参考訳（メタデータ） (2023-05-30T04:10:11Z) - 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) - DASHA: Distributed Nonconvex Optimization with Communication
Compression, Optimal Oracle Complexity, and No Client Synchronization [77.34726150561087]
我々は,分散最適化問題に対する新しい手法であるDASHAを開発し,解析する。
MARINAとは異なり、新しいDASHAとDASHA-MVRは圧縮ベクターのみを送信し、ノードを同期しないため、学習をより実用的なものにしている。
論文 参考訳（メタデータ） (2022-02-02T20:10:40Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - Diffusion Schr\"odinger Bridge with Applications to Score-Based
Generative Modeling [24.46142828617484]
Diffusion SB は、Schr"odinger Bridge 問題を解くために、Iterative Proportional Fitting (IPF) 手順のオリジナル近似である。
本稿では,SB問題の解法としてIterative Proportional Fitting (IPF) 法のオリジナル近似であるDiffusion SBを提案する。
論文 参考訳（メタデータ） (2021-06-01T17:34:27Z) - Multi-Objective Matrix Normalization for Fine-grained Visual Recognition [153.49014114484424]
双線形プールは細粒度視覚認識(FGVC)において大きな成功を収める
近年,行列パワー正規化は双線形特徴量において2次情報を安定化させることができることが示されている。
両線形表現を同時に正規化できる効率的な多目的行列正規化法(MOMN)を提案する。
論文 参考訳（メタデータ） (2020-03-30T08:40:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。