論文の概要: Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees

• arxiv url: http://arxiv.org/abs/2602.15008v1
• Date: Mon, 16 Feb 2026 18:48:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-17 16:22:50.633903
• Title: Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees
• Title（参考訳）: 離散拡散モデルによる効率的なサンプリング:シャープと適応的保証
• Authors: Daniil Dmitriev, Zhihan Huang, Yuting Wei,
• Abstract要約: 連続時間マルコフ連鎖(CTMC)の定式化によるスコアベース離散拡散モデルのサンプリング効率について検討した。 一様離散拡散に対して、$$-leapingアルゴリズムは位数$tilde O(d/varepsilon)$の複雑さを達成することを示す。 離散拡散をマスキングするために,本質的な情報理論量によって収束率を制御した$$-leapingサンプルラを導入する。
• 参考スコア（独自算出の注目度）: 9.180350432640912
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Diffusion models over discrete spaces have recently shown striking empirical success, yet their theoretical foundations remain incomplete. In this paper, we study the sampling efficiency of score-based discrete diffusion models under a continuous-time Markov chain (CTMC) formulation, with a focus on $τ$-leaping-based samplers. We establish sharp convergence guarantees for attaining $\varepsilon$ accuracy in Kullback-Leibler (KL) divergence for both uniform and masking noising processes. For uniform discrete diffusion, we show that the $τ$-leaping algorithm achieves an iteration complexity of order $\tilde O(d/\varepsilon)$, with $d$ the ambient dimension of the target distribution, eliminating linear dependence on the vocabulary size $S$ and improving existing bounds by a factor of $d$; moreover, we establish a matching algorithmic lower bound showing that linear dependence on the ambient dimension is unavoidable in general. For masking discrete diffusion, we introduce a modified $τ$-leaping sampler whose convergence rate is governed by an intrinsic information-theoretic quantity, termed the effective total correlation, which is bounded by $d \log S$ but can be sublinear or even constant for structured data. As a consequence, the sampler provably adapts to low-dimensional structure without prior knowledge or algorithmic modification, yielding sublinear convergence rates for various practical examples (such as hidden Markov models, image data, and random graphs). Our analysis requires no boundedness or smoothness assumptions on the score estimator beyond control of the score entropy loss.
• Abstract（参考訳）: 離散空間上の拡散モデルは、最近顕著な実験的な成功を示しているが、理論的な基礎はいまだ不完全である。 本稿では,連続時間マルコフ連鎖 (CTMC) の定式化によるスコアベース離散拡散モデルのサンプリング効率について検討し,$τ$-leaping-based samplers に着目した。 クルバック・リブラー(KL)の均一およびマスキングノイズ発生過程における精度を$\varepsilon$で達成するための鋭い収束保証を確立する。 一様離散拡散に対して、$τ$-leapingアルゴリズムは次数$\tilde O(d/\varepsilon)$, with $d$ the ambient dimension of the target distribution, away the linear dependency on the vocabulary size $S$ and improve existing bounds by a factor of $d$; さらに、周辺次元への線形依存が一般に避けられないことを示すアルゴリズム的下界を確立する。 離散拡散をマスキングするために,内在的な情報理論量によって収束率が支配される改良された$τ$-leapingサンプルを導入し,実効的な総相関を$d \log S$で有界だが,構造データに対してはサブ線形あるいは定数でもよいとした。 その結果、サンプルは事前の知識やアルゴリズムの修正なしに低次元構造に順応し、様々な実例(隠れマルコフモデル、画像データ、ランダムグラフなど)のサブ線形収束率を得る。 我々の分析では、スコアエントロピー損失の制御以外のスコア推定器に境界性や滑らかさの仮定は必要としない。

関連論文リスト

• Entropy-Based Dimension-Free Convergence and Loss-Adaptive Schedules for Diffusion Models [3.2091923314854416]
  学習スコア(またはデノイザー)によって駆動される逆時間ダイナミクスを離散化することで拡散生成モデルがサンプルを合成する 我々は、幾何学的仮定を避けるために、次元自由収束に対する情報理論的アプローチを開発する。 また、逆SDEの効率的な離散化のための損失適応スケジュール(LAS)を提案し、これは軽量であり、訓練損失のみに依存している。
  論文  参考訳（メタデータ） (2026-01-29T16:28:21Z)
• Inference-Time Scaling of Diffusion Language Models with Particle Gibbs Sampling [70.8832906871441]
  我々は、モデルを再訓練することなく、所望の報酬に向けて世代を操る方法を研究する。 従来の手法では、通常は1つの認知軌道内でサンプリングやフィルタを行い、軌道レベルの改善なしに報酬をステップバイステップで最適化する。 本稿では,拡散言語モデル(PG-DLM)の粒子ギブスサンプリングについて紹介する。
  論文  参考訳（メタデータ） (2025-07-11T08:00:47Z)
• Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
  連続時間マルコフ連鎖(CTMC)に基づくスコアベース離散拡散モデルの理論的側面について検討する。 本稿では,事前定義された時間点におけるスコア推定値を利用する離散時間サンプリングアルゴリズムを一般状態空間$[S]d$に導入する。 我々の収束解析はジルサノフ法を用いて離散スコア関数の重要な性質を確立する。
  論文  参考訳（メタデータ） (2024-10-03T09:07:13Z)
• O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions [6.76974373198208]
  最小の仮定の下で,拡散確率モデル(DDPM)の高速収束理論を確立する。 収束率は$O(k/T)$に改善され、$k$は対象データ分布の内在次元であることを示す。 これはDDPMが未知の低次元構造に自動的に適応する能力を強調している。
  論文  参考訳（メタデータ） (2024-09-27T17:59:10Z)
• Informed Correctors for Discrete Diffusion Models [27.295990499157814]
  離散拡散モデルに対する予測・相関型サンプリング手法を提案する。 情報補正器は,誤差が少なく,FIDスコアが向上した優れたサンプルを連続的に生成することを示す。 本結果は,離散拡散を用いた高速かつ高忠実な生成のための情報補正器の可能性を明らかにするものである。
  論文  参考訳（メタデータ） (2024-07-30T23:29:29Z)
• Closed-form Filtering for Non-linear Systems [83.91296397912218]
  我々は密度近似と計算効率の面でいくつかの利点を提供するガウスPSDモデルに基づく新しいフィルタのクラスを提案する。 本研究では,遷移や観測がガウスPSDモデルである場合,フィルタリングを効率的にクローズド形式で行うことができることを示す。 提案する推定器は, 近似の精度に依存し, 遷移確率の正則性に適応する推定誤差を伴って, 高い理論的保証を享受する。
  論文  参考訳（メタデータ） (2024-02-15T08:51:49Z)
• Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization [17.535229185525353]
  連続マルコフ連鎖の均一化を利用したアルゴリズムを導入し、ランダムな時間点の遷移を実装した。 我々の結果は、$mathbbRd$における拡散モデルの最先端の成果と一致し、さらに$mathbbRd$設定と比較して離散拡散モデルの利点を浮き彫りにする。
  論文  参考訳（メタデータ） (2024-02-12T22:26:52Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Smpling (AIS)は、抽出可能な分布から重み付けされたサンプルを合成する。 本稿では,alpha$-divergencesに対する定数レートAISアルゴリズムとその効率的な実装を提案する。
  論文  参考訳（メタデータ） (2023-06-27T08:15:28Z)
• Score-based Continuous-time Discrete Diffusion Models [102.65769839899315]
  連続時間マルコフ連鎖を介して逆過程が認知されるマルコフジャンププロセスを導入することにより、拡散モデルを離散変数に拡張する。 条件境界分布の単純なマッチングにより、偏りのない推定器が得られることを示す。 提案手法の有効性を,合成および実世界の音楽と画像のベンチマークで示す。
  論文  参考訳（メタデータ） (2022-11-30T05:33:29Z)

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

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