論文の概要: Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problems
- arxiv url: http://arxiv.org/abs/2603.20589v1
- Date: Sat, 21 Mar 2026 01:16:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-24 19:11:38.987222
- Title: Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problems
- Title（参考訳）: 拡散を用いた離散分布の生成:ランダム制約満足問題からの考察
- Authors: Alankrita Bhatt, Mukur Gupta, Germain Kolossov, Andrea Montanari,
- Abstract要約: いくつかのグループは最近、新しい生成技法の合成ベンチマークとして、ランダムな$k$-satisfiability(k$-SAT)を使用している。
ランダム制約満足度問題の理論からの基本的な知見は、そのようなベンチマーク上での生成技術の挙動に観測可能な意味を持つことを示す。
- 参考スコア（独自算出の注目度）: 14.051523781282674
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Generating data from discrete distributions is important for a number of application domains including text, tabular data, and genomic data. Several groups have recently used random $k$-satisfiability ($k$-SAT) as a synthetic benchmark for new generative techniques. In this paper, we show that fundamental insights from the theory of random constraint satisfaction problems have observable implications (sometime contradicting intuition) on the behavior of generative techniques on such benchmarks. More precisely, we study the problem of generating a uniformly random solution of a given (random) $k$-SAT or $k$-XORSAT formula. Among other findings, we observe that: $(i)$~Continuous diffusions outperform masked discrete diffusions; $(ii)$~Learned diffusions can match the theoretical `ideal' accuracy; $(iii)$~Smart ordering of the variables can significantly improve accuracy, although not following popular heuristics.
- Abstract（参考訳）: 離散分布からデータを生成することは、テキスト、表データ、ゲノムデータを含む多くのアプリケーション領域にとって重要である。
いくつかのグループは最近、新しい生成技法の合成ベンチマークとして、ランダムな$k$-satisfiability(k$-SAT)を使用している。
本稿では,ランダム制約満足度問題の理論から得られる基本的な知見が,このようなベンチマークにおける生成手法の挙動に,観測可能な意味(直観と矛盾することもある)を持つことを示す。
より正確には、与えられた(ランダムな)$k$-SATあるいは$k$-XORSATの均一にランダムな解を生成する問題を研究する。
その他の発見の中で、我々は次のように観察している。
(i)$~連続拡散はマスク付き離散拡散より優れ、$
(ii)$~earnedfusions は理論上の 'ideal' の精度と一致する。
(iii)$~ Smart ordering of the variables can significantly improve accuracy, but not not follow popular heuristics。
関連論文リスト
- Gaussian Universality for Diffusion Models [13.722991812691054]
一般化線形モデルである $f(mathbfW)$ のテスト誤差は、拡散データ上の分類タスクのために訓練された検定誤差がガウス混合法で訓練された $f(mathbfW)$ のテスト誤差と一致することを示す。
また、任意の$$$-lipschitz scalar function $phi$, $phi(mathbfx)$ が $mathbbE phi(mathbfx)$ に近く、条件拡散モデルからサンプリングされた $mathbfx$ の確率が高いことも示している。
論文 参考訳（メタデータ） (2025-01-13T23:13:01Z) - SymmetricDiffusers: Learning Discrete Diffusion on Finite Symmetric Groups [14.925722398371498]
本稿では,S_n$以上の複雑な分布を学習するタスクを単純化する離散拡散モデルを提案する。
有限群上のランダムウォークの理論に基づいて拡散長を選択するための経験的ガイドラインを提供する。
本モデルでは,4桁画像のソート,ジグソーパズル,旅行セールスマン問題などの課題に対して,最先端ないし同等のパフォーマンスを実現する。
論文 参考訳（メタデータ） (2024-10-03T19:37:40Z) - 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) - Non-asymptotic bounds for forward processes in denoising diffusions: Ornstein-Uhlenbeck is hard to beat [49.1574468325115]
本稿では,全変動(TV)における前方拡散誤差の非漸近的境界について述べる。
我々は、R$からFarthestモードまでの距離でマルチモーダルデータ分布をパラメライズし、加法的および乗法的雑音による前方拡散を考察する。
論文 参考訳（メタデータ） (2024-08-25T10:28:31Z) - Doubly Robust Conditional Independence Testing with Generative Neural Networks [8.323172773256449]
本稿では、第3の確率ベクトル$Z$を与えられた2つのジェネリックランダムベクトル$X$と$Y$の条件独立性をテストする問題に対処する。
条件分布を明示的に推定しない新しい非パラメトリック試験法を提案する。
論文 参考訳（メタデータ） (2024-07-25T01:28:59Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Squared $\ell_2$ Norm as Consistency Loss for Leveraging Augmented Data
to Learn Robust and Invariant Representations [76.85274970052762]
元のサンプルと拡張されたサンプルの埋め込み/表現の距離を規則化することは、ニューラルネットワークの堅牢性を改善するための一般的なテクニックである。
本稿では、これらの様々な正規化選択について検討し、埋め込みの正規化方法の理解を深める。
私たちが特定したジェネリックアプローチ(squared $ell$ regularized augmentation)は、それぞれ1つのタスクのために特別に設計されたいくつかの手法より優れていることを示す。
論文 参考訳（メタデータ） (2020-11-25T22:40:09Z) - Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。
一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-14T16:09:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。