論文の概要: 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 16:54:31.76817
• 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: http://creativecommons.org/publicdomain/zero/1.0/
• 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})を指数関数的に改善する固定次元の複雑さを回復する。

関連論文リスト

• Sampling from multi-modal distributions on Riemannian manifolds with training-free stochastic interpolants [17.07401986649233]
  本研究では,非平衡決定論的力学のシミュレーションに基づくサンプリングアルゴリズムを提案する。 機械学習に依存する関連する生成的モデリング手法とは対照的に,本手法は完全にトレーニング不要である。
  論文  参考訳（メタデータ） (2026-01-31T10:17:44Z)
• An Elementary Approach to Scheduling in Generative Diffusion Models [55.171367482496755]
  生成拡散モデルにおけるノイズスケジューリングと時間離散化の影響を特徴付けるための基礎的手法を開発した。 異なるデータセットと事前訓練されたモデルにわたる実験により、我々のアプローチによって選択された時間離散化戦略が、ベースラインとサーチベースの戦略を一貫して上回ることを示した。
  論文  参考訳（メタデータ） (2026-01-20T05:06:26Z)
• Improved sampling algorithms and Poincaré inequalities for non-log-concave distributions [1.9753732769115382]
  これは$d$と$frac1epsilon$である。 $L=mathcalO(1)$と$M=mathrmpoly(d)$である。
  論文  参考訳（メタデータ） (2025-07-15T12:06:11Z)
• Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributions [8.366536762687492]
  模擬テンパリングと任意の局所連鎖モンテカルロサンプリング器を組み合わせることを考える。 混合分布からサンプリングするために,メトロポリスのスペクトルギャップの制限値に下限を与える新しい分解定理を提案する。
  論文  参考訳（メタデータ） (2025-05-21T03:28:55Z)
• Diffusion-based supervised learning of generative models for efficient sampling of multimodal distributions [16.155593250605254]
  ベイズ推定のための高次元多モード確率分布の効率的なサンプリングのためのハイブリッド生成モデルを提案する。 提案手法は,最大100次元のモード形状の異なるマルチモーダル分布を効果的に扱えることを示す。
  論文  参考訳（メタデータ） (2025-04-20T21:06:02Z)
• 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)
• Efficiently learning and sampling multimodal distributions with data-based initialization [20.575122468674536]
  静止測度から少数のサンプルを与えられたマルコフ連鎖を用いて多重モーダル分布をサンプリングする問題を考察する。 マルコフ連鎖が$k$dのスペクトルギャップを持つ場合、静止分布からのサンプルは、静止測度からテレビ距離において$varepsilon$-closeの条件法則を持つサンプルを効率よく生成する。
  論文  参考訳（メタデータ） (2024-11-14T01:37:02Z)
• Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel [10.840582511203024]
  我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでのみ実行できるように並列化可能であることを示す。 また、我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでしか実行できないことを示す。
  論文  参考訳（メタデータ） (2024-06-03T01:34:34Z)
• 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)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。 我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。 シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
  論文  参考訳（メタデータ） (2024-01-29T02:08:40Z)
• Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo [30.4930148381328]
  拡散に基づくモンテカルロ (DMC) は、等尺条件を超えた一般目標分布から試料を採取する手法である。 DMCは、高い勾配の複雑さに遭遇し、その結果、得られたサンプルのエラー耐性$epsilon$に指数関数的に依存する。 本稿では,新しい再帰に基づくスコア推定法に基づくRS-DMCを提案する。 私たちのアルゴリズムは、人気のあるLangevinベースのアルゴリズムよりもはるかに高速です。
  論文  参考訳（メタデータ） (2024-01-12T02:33:57Z)
• Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithms [15.718514510878896]
  マルチモーダル性により低次元でもしばしば困難となるガウス混合などの非対数圏分布からの近似サンプリング問題について検討する。 我々はマルコフ連鎖モンテカルロ法(MCMC)を用いてこの課題を実行することに集中する。
  論文  参考訳（メタデータ） (2023-05-25T12:28:26Z)
• Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models [91.22420505636006]
  本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。 1/varepsilonは$m2d log (1/varepsilon)$である。 以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
  論文  参考訳（メタデータ） (2023-03-30T02:50:49Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• 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)
• Wasserstein distance estimates for the distributions of numerical approximations to ergodic stochastic differential equations [0.3553493344868413]
  エルゴード微分方程式のイン分布と強い対数凸の場合の分布との間のワッサースタイン距離について検討した。 これにより、過減衰および過減衰ランジュバン力学の文献で提案されている多くの異なる近似を統一的に研究することができる。
  論文  参考訳（メタデータ） (2021-04-26T07:50:04Z)
• 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)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)
• 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)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURFは分布を断片的に近似するアルゴリズムである。 実験では最先端のアルゴリズムよりも優れています。
  論文  参考訳（メタデータ） (2020-02-22T01:03:33Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)
• Efficiently Sampling Functions from Gaussian Process Posteriors [76.94808614373609]
  高速後部サンプリングのための簡易かつ汎用的なアプローチを提案する。 分離されたサンプルパスがガウス過程の後部を通常のコストのごく一部で正確に表現する方法を実証する。
  論文  参考訳（メタデータ） (2020-02-21T14:03:16Z)

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

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