論文の概要: Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo
- arxiv url: http://arxiv.org/abs/2401.06325v1
- Date: Fri, 12 Jan 2024 02:33:57 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-15 20:30:09.607667
- Title: Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo
- Title（参考訳）: 拡散型モンテカルロによるイソペリメトリーのない高速サンプリング
- Authors: Xunpeng Huang and Difan Zou and Hanze Dong and Yian Ma and Tong Zhang
- Abstract要約: 拡散に基づくモンテカルロ (DMC) は、等尺条件を超えた一般目標分布から試料を採取する手法である。
DMCは、高い勾配の複雑さに遭遇し、その結果、得られたサンプルのエラー耐性$epsilon$に指数関数的に依存する。
本稿では,新しい再帰に基づくスコア推定法に基づくRS-DMCを提案する。
私たちのアルゴリズムは、人気のあるLangevinベースのアルゴリズムよりもはるかに高速です。
- 参考スコア（独自算出の注目度）: 30.4930148381328
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: To sample from a general target distribution $p_*\propto e^{-f_*}$ beyond the
isoperimetric condition, Huang et al. (2023) proposed to perform sampling
through reverse diffusion, giving rise to Diffusion-based Monte Carlo (DMC).
Specifically, DMC follows the reverse SDE of a diffusion process that
transforms the target distribution to the standard Gaussian, utilizing a
non-parametric score estimation. However, the original DMC algorithm
encountered high gradient complexity, resulting in an exponential dependency on
the error tolerance $\epsilon$ of the obtained samples. In this paper, we
demonstrate that the high complexity of DMC originates from its redundant
design of score estimation, and proposed a more efficient algorithm, called
RS-DMC, based on a novel recursive score estimation method. In particular, we
first divide the entire diffusion process into multiple segments and then
formulate the score estimation step (at any time step) as a series of
interconnected mean estimation and sampling subproblems accordingly, which are
correlated in a recursive manner. Importantly, we show that with a proper
design of the segment decomposition, all sampling subproblems will only need to
tackle a strongly log-concave distribution, which can be very efficient to
solve using the Langevin-based samplers with a provably rapid convergence rate.
As a result, we prove that the gradient complexity of RS-DMC only has a
quasi-polynomial dependency on $\epsilon$, which significantly improves
exponential gradient complexity in Huang et al. (2023). Furthermore, under
commonly used dissipative conditions, our algorithm is provably much faster
than the popular Langevin-based algorithms. Our algorithm design and
theoretical framework illuminate a novel direction for addressing sampling
problems, which could be of broader applicability in the community.
- Abstract（参考訳）: 一般目標分布$p_*\propto e^{-f_*}$を等尺条件を超えてサンプリングするために、Huang et al. (2023) は逆拡散によるサンプリングを行うことを提案し、拡散に基づくモンテカルロ (DMC) を生み出した。
具体的には、DMCは非パラメトリックスコア推定を用いて、ターゲット分布を標準ガウスに変換する拡散過程の逆SDEに従う。
しかし、元のDMCアルゴリズムは高い勾配の複雑さに遭遇し、その結果、得られたサンプルの誤差耐性$\epsilon$に指数関数的に依存する結果となった。
本稿では,dmcの複雑性が高いのはスコア推定の冗長な設計に起因することを実証し,新しい再帰的スコア推定法に基づいて,rs-dmcと呼ばれるより効率的なアルゴリズムを提案する。
特に、まず拡散過程全体を複数のセグメントに分割し、次に、再帰的に相関した一連の相互平均推定とサンプリングサブプロブレムとしてスコア推定ステップ(任意の時間ステップで)を定式化する。
重要となるのは,セグメント分解を適切に設計すれば,すべてのサンプリングサブプロブレムが強いログコンケーブ分布に取り組むだけでよいことであり,ランジュバンベースのサンプリング器を高速収束率で解くのは非常に効率的であることを示すことである。
その結果、RS-DMCの勾配複雑性は、Huang et al. (2023) の指数勾配複雑性を著しく改善する$\epsilon$に準多項式依存性しか持たないことが証明された。
さらに、一般的な散逸条件下では、我々のアルゴリズムは一般的なランゲヴィンベースのアルゴリズムよりもはるかに高速である。
当社のアルゴリズム設計と理論的枠組みは,サンプリング問題に対処するための新たな方向性を照らしている。
関連論文リスト
- Faster Sampling via Stochastic Gradient Proximal Sampler [28.422547264326468]
非log-concave分布からのサンプリングのための近位サンプリング器 (SPS) について検討した。
対象分布への収束性は,アルゴリズムの軌道が有界である限り保証可能であることを示す。
我々は、Langevin dynamics(SGLD)とLangevin-MALAの2つの実装可能な変種を提供し、SPS-SGLDとSPS-MALAを生み出した。
論文 参考訳（メタデータ） (2024-05-27T00:53:18Z) - Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion [13.832359344815043]
本稿では,非正規化密度の問合せに基づく非ログコンケーブ分布からのサンプリング問題について考察する。
最初に、モンテカルロ推定器によって近似された点数を持つ偏微分拡散過程のシミュレーションに基づいて、DDMC(Denoising Diffusion Monte Carlo)というフレームワークを記述した。
DDMCを真のアルゴリズムであるZOD-MC(Zeroth-Order Diffusion Monte Carlo)に変換する。
論文 参考訳（メタデータ） (2024-02-27T21:00:00Z) - Distributed Markov Chain Monte Carlo Sampling based on the Alternating
Direction Method of Multipliers [143.6249073384419]
本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。
我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。
シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
論文 参考訳（メタデータ） (2024-01-29T02:08:40Z) - Langevin Quasi-Monte Carlo [6.146093081175471]
ランゲヴィン・モンテカルロ(LMC)とその勾配バージョンは複雑な高次元分布からサンプリングする強力なアルゴリズムである。
準ランダムサンプルを用いてLCCの推定誤差を低減できることを示す。
論文 参考訳（メタデータ） (2023-09-22T07:15:18Z) - Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling [8.655526882770742]
1990年代、ネスターとネミロフスキーは自己調和障壁に基づく凸最適化のための内部点法(IPM)を開発した。
2012年、カナンとナラヤナンはポリトープを一様にサンプリングするダイキンウォークを提案した。
本稿では、多時間サンプリングアルゴリズムのためのダイキンウォークと共にIPM機械を開発し、適応させることにより、このアプローチを一般化する。
論文 参考訳（メタデータ） (2023-07-24T17:15:38Z) - Decomposed Diffusion Sampler for Accelerating Large-Scale Inverse
Problems [64.29491112653905]
本稿では, 拡散サンプリング法とクリロフ部分空間法を相乗的に組み合わせた, 新規で効率的な拡散サンプリング手法を提案する。
具体的には、ツイーディの公式による分母化標本における接空間がクリロフ部分空間を成すならば、その分母化データによるCGは、接空間におけるデータの整合性更新を確実に維持する。
提案手法は,従来の最先端手法よりも80倍以上高速な推論時間を実現する。
論文 参考訳（メタデータ） (2023-03-10T07:42:49Z) - Asymptotically Unbiased Instance-wise Regularized Partial AUC
Optimization: Theory and Algorithm [101.44676036551537]
One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。
既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。
本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
論文 参考訳（メタデータ） (2022-10-08T08:26:22Z) - Reconstructing the Universe with Variational self-Boosted Sampling [7.922637707393503]
ハミルトニアン・モンテカルロ (HMC) のような伝統的なアルゴリズムは、相関サンプルを生成するために計算的に非効率である。
本稿では,両アルゴリズムの欠点を軽減するために,変分自己ブーストサンプリング(VBS)と呼ばれるハイブリッド方式を開発する。
VBSは、単純なVIアプローチよりも優れた品質のサンプルを生成し、HMCのみを用いてサンプリングフェーズの相関長を10～50倍に削減する。
論文 参考訳（メタデータ） (2022-06-28T21:30:32Z) - Improving Diffusion Models for Inverse Problems using Manifold Constraints [55.91148172752894]
我々は,現在の解法がデータ多様体からサンプルパスを逸脱し,エラーが蓄積することを示す。
この問題に対処するため、多様体の制約に着想を得た追加の補正項を提案する。
本手法は理論上も経験上も従来の方法よりも優れていることを示す。
論文 参考訳（メタデータ） (2022-06-02T09:06:10Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳（メタデータ） (2021-07-06T21:59:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。