論文の概要: Query Lower Bounds for Diffusion Sampling

• arxiv url: http://arxiv.org/abs/2604.10857v1
• Date: Sun, 12 Apr 2026 23:47:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-14 20:13:16.252793
• Title: Query Lower Bounds for Diffusion Sampling
• Title（参考訳）: 拡散サンプリングのための問合せ下界
• Authors: Zhiyang Xun, Eric Price,
• Abstract要約: 我々は、$d$次元の分布に精度でスコア推定へのアクセスを与えられる場合、サンプリングには$widetilde(sqrtd)$スコアクエリが必要であることを証明した。 我々の証明は、どのサンプルも$widetilde(sqrtd)$の異なるノイズレベルを探索しなければならないことを示し、実際なぜマルチスケールノイズスケジュールが必要なのかを正式な説明を提供する。
• 参考スコア（独自算出の注目度）: 5.541583428822629
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Diffusion models generate samples by iteratively querying learned score estimates. A rapidly growing literature focuses on accelerating sampling by minimizing the number of score evaluations, yet the information-theoretic limits of such acceleration remain unclear. In this work, we establish the first score query lower bounds for diffusion sampling. We prove that for $d$-dimensional distributions, given access to score estimates with polynomial accuracy $\varepsilon=d^{-O(1)}$ (in any $L^p$ sense), any sampling algorithm requires $\widetildeΩ(\sqrt{d})$ adaptive score queries. In particular, our proof shows that any sampler must search over $\widetildeΩ(\sqrt{d})$ distinct noise levels, providing a formal explanation for why multiscale noise schedules are necessary in practice.
• Abstract（参考訳）: 拡散モデルは、学習したスコア推定を反復的にクエリすることでサンプルを生成する。 急速に増大する文献は、スコア評価の最小化によるサンプリングの高速化に焦点が当てられているが、そのようなアクセラレーションの情報理論上の限界はいまだ不明である。 本研究では,拡散サンプリングのための第1スコアクエリの下位境界を確立する。 我々は、$d$次元分布に対して、多項式精度$\varepsilon=d^{-O(1)}$(任意の$L^p$の意味で)のスコア推定へのアクセスが与えられた場合、任意のサンプリングアルゴリズムは$\widetildeΩ(\sqrt{d})$アダプティブスコアクエリを必要とすることを証明した。 特に、我々の証明は、どのサンプルも$\widetildeΩ(\sqrt{d})$別のノイズレベルを探索しなければならないことを示している。

関連論文リスト

• High-accuracy log-concave sampling with stochastic queries [70.90863485771405]
  サブエクスフォデンシャルテールの繰り返し勾配を用いて,ログコンケーブサンプリングの精度保証が達成可能であることを示す。 また、このフレームワークは、0番目の順序(値)クエリの下でも、同様の高精度な保証を提供する。
  論文  参考訳（メタデータ） (2026-02-15T23:19:07Z)
• Faster Diffusion Models via Higher-Order Approximation [28.824924809206255]
  本稿では,d1+2/K varepsilon-1/K $$のスコア関数評価のみを必要とする,原則付き無トレーニングサンプリングアルゴリズムを提案する。 我々の理論はロバストなvis-a-vis不正確なスコア推定であり、スコア推定誤差が増加するにつれて優雅に劣化する。 より広範に、我々は高速サンプリングのための高次手法の有効性を理解するための理論的枠組みを開発した。
  論文  参考訳（メタデータ） (2025-06-30T16:49:03Z)
• Diffusion Tree Sampling: Scalable inference-time alignment of diffusion models [13.312007032203857]
  事前訓練された拡散モデルを推論時に新しい目的に適応させることは、生成的モデリングにおいて未解決の問題である。 そこで本研究では,終末報酬を拡散連鎖を通じて伝播させることにより,報奨目標密度から抽出するツリーベースアプローチを提案する。 以前の世代からの情報を再利用することで、任意のアルゴリズムが追加の計算を着実により良いサンプルに変換する。
  論文  参考訳（メタデータ） (2025-06-25T17:59:10Z)
• Distributional Diffusion Models with Scoring Rules [83.38210785728994]
  拡散モデルは高品質な合成データを生成する。 高品質な出力を生成するには、多くの離散化ステップが必要です。 クリーンデータサンプルの後部エム分布を学習し,サンプル生成を実現することを提案する。
  論文  参考訳（メタデータ） (2025-02-04T16:59:03Z)
• Provable Acceleration for Diffusion Models under Minimal Assumptions [8.15094483029656]
  そこで本研究では,スコアベースサンプルの学習自由化手法を提案する。 最小限の仮定の下で、我々のスキームは$widetildeO(d5/4/sqrtvarepsilon)$で全変量を達成する。
  論文  参考訳（メタデータ） (2024-10-30T17:59:06Z)
• Improved Sample Complexity Bounds for Diffusion Model Training [6.20468094368214]
  オンラインの誤りや深度への依存度は,他の関連するパラメータとともに指数関数的に改善した。 オンラインのエラーや深度に依存し,他のパラメータへの依存性も改善した。
  論文  参考訳（メタデータ） (2023-11-23T00:27:13Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。 この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
  論文  参考訳（メタデータ） (2021-06-29T12:49:54Z)
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning [123.69175280309226]
  オンライン強化学習(RL)における課題の1つは、エージェントがその振る舞いを最適化するために、環境の探索とサンプルの活用をトレードオフする必要があることである。 1) 生成モデル(環境のスパースシミュレータなど)にアクセス可能な状態のサンプル数を規定する「対象別」アルゴリズム,2) 所定のサンプルをできるだけ早く生成する「対象別」サンプル収集。
  論文  参考訳（メタデータ） (2020-07-13T15:17:35Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)

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

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