論文の概要: Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models

• arxiv url: http://arxiv.org/abs/2303.17109v2
• Date: Wed, 24 May 2023 04:27:04 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-26 01:33:16.023169
• Title: Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models
• Title（参考訳）: 正の半定値モデルによる確率微分方程式の効率的なサンプリング
• Authors: Anant Raj, Umut \c{S}im\c{s}ekli and Alessandro Rudi
• Abstract要約: 本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。 1/varepsilonは$m2d log (1/varepsilon)$である。 以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
• 参考スコア（独自算出の注目度）: 91.22420505636006
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: This paper deals with the problem of efficient sampling from a stochastic differential equation, given the drift function and the diffusion matrix. The proposed approach leverages a recent model for probabilities \cite{rudi2021psd} (the positive semi-definite -- PSD model) from which it is possible to obtain independent and identically distributed (i.i.d.) samples at precision $\varepsilon$ with a cost that is $m^2 d \log(1/\varepsilon)$ where $m$ is the dimension of the model, $d$ the dimension of the space. The proposed approach consists in: first, computing the PSD model that satisfies the Fokker-Planck equation (or its fractional variant) associated with the SDE, up to error $\varepsilon$, and then sampling from the resulting PSD model. Assuming some regularity of the Fokker-Planck solution (i.e. $\beta$-times differentiability plus some geometric condition on its zeros) We obtain an algorithm that: (a) in the preparatory phase obtains a PSD model with L2 distance $\varepsilon$ from the solution of the equation, with a model of dimension $m = \varepsilon^{-(d+1)/(\beta-2s)} (\log(1/\varepsilon))^{d+1}$ where $1/2\leq s\leq1$ is the fractional power to the Laplacian, and total computational complexity of $O(m^{3.5} \log(1/\varepsilon))$ and then (b) for Fokker-Planck equation, it is able to produce i.i.d.\ samples with error $\varepsilon$ in Wasserstein-1 distance, with a cost that is $O(d \varepsilon^{-2(d+1)/\beta-2} \log(1/\varepsilon)^{2d+3})$ per sample. This means that, if the probability associated with the SDE is somewhat regular, i.e. $\beta \geq 4d+2$, then the algorithm requires $O(\varepsilon^{-0.88} \log(1/\varepsilon)^{4.5d})$ in the preparatory phase, and $O(\varepsilon^{-1/2}\log(1/\varepsilon)^{2d+2})$ for each sample. Our results suggest that as the true solution gets smoother, we can circumvent the curse of dimensionality without requiring any sort of convexity.
• Abstract（参考訳）: 本稿では,ドリフト関数と拡散行列を与えられた確率微分方程式からの効率的なサンプリングの問題を扱う。 提案手法は近年の確率モデル cite{rudi2021psd} (正の半定値-PSDモデル) を利用しており、これは独立で同一に分布したサンプルを精度$\varepsilon$で得ることができ、コストは$m^2 d \log(1/\varepsilon)$$m$はモデルの次元、$d$は空間の次元である。 まず、SDEに関連するフォッカー・プランク方程式(またはその分数変量)を満足するPSDモデルを計算し、エラー$\varepsilon$まで計算し、その結果のPSDモデルからサンプリングする。 Fokker-Planck 解の正則性 (例えば $\beta$-times differentiability と 0 上の幾何条件) を仮定すると、以下のアルゴリズムが得られる。 (a) 予備相において、方程式の解から L2 距離 $\varepsilon$ の PSD モデルを得るが、次元 $m = \varepsilon^{-(d+1)/(\beta-2s)} (\log(1/\varepsilon))^{d+1}$ ここで、1/2\leq s\leq1$ はラプラシアンの分数乗であり、合計計算複雑性は$O(m^{3.5} \log(1/\varepsilon)$ となる。 (b)fokker-planck方程式では、サンプル毎に$o(d \varepsilon^{-2(d+1)/\beta-2} \log(1/\varepsilon)^{2d+3})$というコストで、waserstein-1距離の誤差$\varepsilon$のi.i.d.\サンプルを生成することができる。 これは、sde に付随する確率が幾分正則であれば、すなわち $\beta \geq 4d+2$ であるなら、各サンプルに対して $o(\varepsilon^{-0.88} \log(1/\varepsilon)^{4.5d})$ と $o(\varepsilon^{-1/2}\log(1/\varepsilon)^{2d+2}) が必要であることを意味する。 以上より, 真の解がより滑らかになるにつれて, 次元の呪いを回避できる可能性が示唆された。

関連論文リスト

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
  閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。 線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
  論文  参考訳（メタデータ） (2024-09-05T16:59:56Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model [3.749193647980305]
  本稿では,一連の状態対応機能を有するマルコフ決定プロセス(MDP)について考察する。 モデルに基づくアプローチ(resp.$Q-learning)が、高い確率で$varepsilon$-Optimalポリシーを確実に学習することを示す。
  論文  参考訳（メタデータ） (2021-05-28T17:49:39Z)
• Learning elliptic partial differential equations with randomized linear algebra [2.538209532048867]
  ほぼ確実に収束する$G$への近似を構築することができることを示す。 0Gamma_epsilonleq 1$はトレーニングデータセットの品質を特徴付ける。
  論文  参考訳（メタデータ） (2021-01-31T16:57:59Z)
• SDP Achieves Exact Minimax Optimality in Phase Synchronization [19.909352968029584]
  我々は、ノイズ測定$Y=z*z*+sigma WinmathbbCntimes ntimes nで位相同期問題を研究する。 SDPが誤差境界$ (1+o)fracnp22np$を2乗の$ell$損失で達成することを証明する。
  論文  参考訳（メタデータ） (2021-01-07T03:14:05Z)
• Denoising modulo samples: k-NN regression and tightness of SDP relaxation [5.025654873456756]
  サンプルの値が$f(x_i)$で一様誤差率$O(fraclog nn)frac1d+2)$を高い確率で保持する2段階のアルゴリズムを導出する。 サンプル $f(x_i)$ の見積もりは、その後、関数 $f$ の見積もりを構築するために使われる。
  論文  参考訳（メタデータ） (2020-09-10T13:32:46Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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