論文の概要: Polynomial time sampling from log-smooth distributions in fixed dimension under semi-log-concavity of the forward diffusion with application to strongly dissipative distributions

• arxiv url: http://arxiv.org/abs/2501.00565v1
• Date: Tue, 31 Dec 2024 17:51:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-05 17:11:50.354318
• Title: Polynomial time sampling from log-smooth distributions in fixed dimension under semi-log-concavity of the forward diffusion with application to strongly dissipative distributions
• Title（参考訳）: 前方拡散の半対数共振の下での固定次元における対数平滑分布からの多項式時間サンプリングと強い散逸分布への応用
• Authors: Adrien Vacher, Omar Chehab, Anna Korba,
• Abstract要約: 固定次元の複雑なサンプリングアルゴリズムを提案する。 提案アルゴリズムは,$O(d7Ld+2epsilon-2(d+3) (L+beta)2d2(d+1))$ timeにおいて,$textKL$発散で期待される$epsilon$エラーを実現する。
• 参考スコア（独自算出の注目度）: 9.48556659249574
• License:
• Abstract: In this article we provide a stochastic sampling algorithm with polynomial complexity in fixed dimension that leverages the recent advances on diffusion models where it is shown that under mild conditions, sampling can be achieved via an accurate estimation of intermediate scores across the marginals $(p_t)_{t\ge 0}$ of the standard Ornstein-Uhlenbeck process started at the density we wish to sample from. The heart of our method consists into approaching these scores via a computationally cheap estimator and relating the variance of this estimator to the smoothness properties of the forward process. Under the assumption that the density to sample from is $L$-log-smooth and that the forward process is semi-log-concave: $-\nabla^2 \log(p_t) \succeq -\beta I_d$ for some $\beta \geq 0$, we prove that our algorithm achieves an expected $\epsilon$ error in $\text{KL}$ divergence in $O(d^7L^{d+2}\epsilon^{-2(d+3)} (L+\beta)^2d^{2(d+1)})$ time. In particular, our result allows to fully transfer the problem of sampling from a log-smooth distribution into a regularity estimate problem. As an application, we derive an exponential complexity improvement for the problem of sampling from a $L$-log-smooth distribution that is $\alpha$-strongly log-concave distribution outside some ball of radius $R$: after proving that such distributions verify the semi-log-concavity assumption, a result which might be of independent interest, we recover a $poly(R,L,\alpha^{-1}, \epsilon^{-1})$ complexity in fixed dimension which exponentially improves upon the previously known $poly(e^{RL^2}, L,\alpha^{-1}, \log(\epsilon^{-1}))$ complexity in the low precision regime.
• Abstract（参考訳）: 本稿では, 固定次元における多項式複雑性を持つ確率的サンプリングアルゴリズムを提案する。このアルゴリズムは拡散モデルの最近の進歩を生かし, 穏やかな条件下では, サンプリングを, サンプリングしたい密度で開始する標準オルンシュタイン-ウレンベック過程の中間点$(p_t)_{t\ge 0}$の精度で推定することにより, サンプリングを行うことができる。 提案手法の心臓部は,計算的に安価な推定器を用いてこれらのスコアに近づき,この推定器のばらつきを前処理の滑らかさ特性に関連付ける。 サンプルの密度が$L$-log-smooth であり、前処理が半log-concave であるという仮定の下で、$-\nabla^2 \log(p_t) \sucta I_d$ for some $\beta \geq 0$ で、我々のアルゴリズムが期待される $\epsilon$ error in $\text{KL}$ divergence in $O(d^7L^{d+2}\epsilon^{-2(d+3)} (L+\beta)^2d^{2(d+1)})$ time を達成することを証明している。 特に,本研究の結果は,対数平滑分布から正則性推定問題へのサンプリング問題の完全移行を可能にする。 応用として、そのような分布が半log-concavityの仮定を検証することを証明すると、独立の利害関係にあるかもしれない結果、$poly(R,L,\alpha^{-1}, \epsilon^{-1})を回復し、既知の$poly(e^{RL^2}, L,\alpha^{-1}, \log(\epsilon^{-1})を指数関数的に改善する固定次元の複雑さを回復する。

関連論文リスト

• On the query complexity of sampling from non-log-concave distributions [2.4253233571593547]
  密度$p(x)propto e-f(x)$を持つ$d$次元分布からサンプリングする問題を、必ずしも良好な等尺条件を満たすとは限らない。 広い範囲のパラメータに対して、サンプリングは$d$の超指数係数による最適化よりも厳密に容易であることを示す。
  論文  参考訳（メタデータ） (2025-02-10T06:54:16Z)
• On the sampling complexity of coherent superpositions [0.4972323953932129]
  重ね合わせにPOVMを適用する際に測定結果の分布からサンプリングする問題を考察する。 我々は、$-$$$$O(chi |c|2 log1/delta)$そのようなサンプルを与えられたアルゴリズムを与え、確率密度関数を評価するためにオラクルを呼び出す。
  論文  参考訳（メタデータ） (2025-01-28T16:56:49Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models [91.22420505636006]
  本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。 1/varepsilonは$m2d log (1/varepsilon)$である。 以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
  論文  参考訳（メタデータ） (2023-03-30T02:50:49Z)
• 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)
• Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence [3.9586758145580014]
  強いレイリー分布から繰り返しサンプリングする高速アルゴリズムを設計する。 グラフ $G=(V, E)$ に対して、$G$ in $widetildeO(lvert Vrvert)$ time per sample から一様にランダムに散らばる木を概算する方法を示す。 $n$要素の基底集合の$k$のサブセット上の決定的点プロセスに対して、$widetildeO(komega)$ time の最初の $widetildeO(nk) の後に、$widetildeO(komega)$ time のサンプルを概算する方法を示す。
  論文  参考訳（メタデータ） (2022-04-06T04:11:26Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。 十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。 ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
  論文  参考訳（メタデータ） (2021-11-29T19:26:28Z)
• Complexity of zigzag sampling algorithm for strongly log-concave distributions [6.336005544376984]
  強いログ凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討する。 ジグザグサンプリングアルゴリズムは, 計算コストが$obiglに匹敵するchi-squareの発散において, $varepsilon$ 誤差を達成することを証明した。
  論文  参考訳（メタデータ） (2020-12-21T03:10:21Z)
• 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)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)

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

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