論文の概要: Sample complexity bounds for categorical Markov random fields via Discrete Diffusions

• arxiv url: http://arxiv.org/abs/2610.02128v1
• Date: Thu, 01 Oct 2026 17:40:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:24.339266
• Title: Sample complexity bounds for categorical Markov random fields via Discrete Diffusions
• Title（参考訳）: 離散拡散によるカテゴリーマルコフ確率場に対するサンプル複雑性境界
• Abstract要約: 我々は、離散拡散のためのエンドツーエンドのサンプル複雑性境界を持つ学習方法を開発した。 私たちの主要な技術的洞察は、離散的なスコアを分解する新しいエンピンジングです。 両立型ニューラルスコア学習器を提案し,それを$$-leapingと組み合わせて,エンドツーエンドのサンプリング手順を得る。
• 参考スコア（独自算出の注目度）: 2.0339465062586566
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many applications in statistics, economics, and physics require sampling from high-dimensional categorical distributions with local dependence structures. Examples include finite memory language models, Ising and Potts systems in statistical physics and protein folding, etc. In modern machine learning, discrete diffusions have emerged as a flexible approach for sampling such data, with strong empirical performance. Motivated by this, we develop learning methods with end-to-end sample complexity bounds for discrete diffusion with uniform noising under local dependence, which we model through low order Markov random fields (MRFs). Our main technical insight is a new \emph{pinning decomposition} of the discrete score. It shows that unlike in continuous diffusions, the score decomposes into components where the dependence on time separates multiplicatively from the dependence on the target. Building on this decomposition, we propose a \emph{weight-sharing neural score learner} and combine it with $τ$-leaping to obtain an end-to-end sampling procedure. Rather than treating score-learning error as a black-box input, as is common in existing sampling analyses, we study the score learning error from finite data and derive optimal sampling guarantees with explicit dependence on the vocabulary size, the interaction order of the MRF, and the sample size. Moreover, our strategy trains a single score network across uniform noise levels while leaving the sampling discretization to be chosen at inference-time. This allows the same trained model to trade accuracy for computational cost as inference-time budgets vary. Numerical experiments on Potts, Ising, and tree-structured models show that weight-sharing score networks outperform fully connected ones for sampling long sequences.
• Abstract（参考訳）: 統計学、経済学、物理学における多くの応用は、局所的な依存構造を持つ高次元カテゴリー分布からのサンプリングを必要とする。 例えば、有限メモリ言語モデル、統計物理学におけるIsingとPottsシステム、タンパク質の折り畳みなどがある。 現代の機械学習では、離散拡散はそのようなデータを強力な経験的性能でサンプリングするための柔軟なアプローチとして現れている。 そこで我々は,局所的依存下で一様雑音を呈し,低次マルコフ確率場 (MRFs) をモデル化した離散拡散のための終端から終端までのサンプル複雑性境界を持つ学習法を開発した。 我々の主要な技術的洞察は、離散スコアの新しい 'emph{pinning decomposition} である。 連続拡散とは異なり、スコアは時間依存が対象への依存から乗法的に分離するコンポーネントに分解される。 この分解に基づいて,emph{weight-sharing neural score learner} を提案し,それを$τ$-leaping と組み合わせて,エンドツーエンドのサンプリング手順を得る。 既存のサンプリング分析では、スコア学習誤差をブラックボックス入力として扱うのではなく、有限データからスコア学習誤差を抽出し、語彙サイズ、MRFの相互作用順序、サンプルサイズに明示的に依存した最適なサンプリング保証を導出する。 さらに,本手法では,一様雑音レベルにまたがる単一スコアネットワークをトレーニングし,サンプリング離散化を推論時に選択する。 これにより、推論時間の予算が異なるため、同じ訓練されたモデルで計算コストの正確さを交換することができる。 Potts、Ising、および木構造モデルに関する数値実験により、重み付けスコアネットワークは長いシーケンスをサンプリングするために完全に接続されたものよりも優れていることが示された。

関連論文リスト

• Fixed-point neural samplers on discrete spaces [23.04205410817134]
  離散非正規分布からサンプリングする固定点ニューラルサンプリング法を提案する。 我々のフレームワークは、マスク付き拡散の上に構築され、また、対の分布間の輸送にも拡張されている。 得られた手法が高次元システムに効果的にスケールできることを実証する。
  論文  参考訳（メタデータ） (2026-10-01T14:11:02Z)
• Counterfactual Generation via Flow Matching: Coupling-Sensitive End-to-End Rates [11.51425194152931]
  本研究では,サンプル分割された2つの頑健なトレーニング目標と,観測結果と適合条件付き結果モデルから抽出した目標結果との学習的結合を組み合わせたフローパラメトリック手法を開発した。 我々の理論的な主な貢献は、定数ステップの離散化のための結合感受性KL結合である。 合成および半合成画像ベンチマークの実験は、結合依存理論をサポートし、有限の離散化予算において、サンプルが対応するODEサンプリング器より優れていることを示す。
  論文  参考訳（メタデータ） (2026-10-01T07:05:31Z)
• Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees [9.180350432640912]
  連続時間マルコフ連鎖(CTMC)の定式化によるスコアベース離散拡散モデルのサンプリング効率について検討した。 一様離散拡散に対して、$$-leapingアルゴリズムは位数$tilde O(d/varepsilon)$の複雑さを達成することを示す。 離散拡散をマスキングするために,本質的な情報理論量によって収束率を制御した$$-leapingサンプルラを導入する。
  論文  参考訳（メタデータ） (2026-02-16T18:48:17Z)
• Generative Modeling with Continuous Flows: Sample Complexity of Flow Matching [60.37045080890305]
  本稿では,フローマッチングに基づく生成モデルにおいて,サンプルの複雑さを初めて解析する。 速度場推定誤差をニューラルネットワーク近似誤差、有限標本サイズによる統計的誤差、速度場推定のための有限個の最適化ステップによる最適化誤差に分解する。
  論文  参考訳（メタデータ） (2025-12-01T05:14:25Z)
• Sampling by averaging: A multiscale approach to score estimation [4.003851730099099]
  複雑で正規化されていないターゲット分布から,マルチスケールのダイナミックスを活用することで,効率的なサンプリングを行うための新しいフレームワークを提案する。 MultALMCとMultCDiffの2つのアルゴリズムが開発された。 このフレームワークは、学生のtベースのノイズモデルと調整された高速プロセスダイナミクスを用いて、重次元のターゲット分布を扱うように拡張されている。
  論文  参考訳（メタデータ） (2025-08-20T21:09:34Z)
• Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
  連続時間マルコフ連鎖(CTMC)に基づくスコアベース離散拡散モデルの理論的側面について検討する。 本稿では,事前定義された時間点におけるスコア推定値を利用する離散時間サンプリングアルゴリズムを一般状態空間$[S]d$に導入する。 我々の収束解析はジルサノフ法を用いて離散スコア関数の重要な性質を確立する。
  論文  参考訳（メタデータ） (2024-10-03T09:07:13Z)
• Noisy Correspondence Learning with Self-Reinforcing Errors Mitigation [63.180725016463974]
  クロスモーダル検索は、実際は精力的な、十分に整合した大規模データセットに依存している。 我々は、新しい雑音対応学習フレームワーク、textbfSelf-textbfReinforcing textbfErrors textbfMitigation(SREM)を導入する。
  論文  参考訳（メタデータ） (2023-12-27T09:03:43Z)
• Score-based Continuous-time Discrete Diffusion Models [102.65769839899315]
  連続時間マルコフ連鎖を介して逆過程が認知されるマルコフジャンププロセスを導入することにより、拡散モデルを離散変数に拡張する。 条件境界分布の単純なマッチングにより、偏りのない推定器が得られることを示す。 提案手法の有効性を,合成および実世界の音楽と画像のベンチマークで示す。
  論文  参考訳（メタデータ） (2022-11-30T05:33:29Z)
• Unrolling Particles: Unsupervised Learning of Sampling Distributions [102.72972137287728]
  粒子フィルタリングは複素系の優れた非線形推定を計算するために用いられる。 粒子フィルタは様々なシナリオにおいて良好な推定値が得られることを示す。
  論文  参考訳（メタデータ） (2021-10-06T16:58:34Z)

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

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