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

• arxiv url: http://arxiv.org/abs/2610.09166v1
• Date: Tue, 06 Oct 2026 22:09:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 21:58:22.631769
• Title: Lower Bounds for Parallel Diffusion Sampling
• Title（参考訳）: 並列拡散サンプリングのための下界
• Abstract要約: 並列サンプリング手法は、より少ないシーケンシャルラウンドに対する追加評価を取引することで、生成を加速しようとする。 近似スコアを用いた拡散サンプリングのための第1並列ラウンド下界を確立する。 私たちの構築では、隠れた情報へのシーケンシャルなアクセスを強制する、固定された近似スコアオラクルを使用します。
• 参考スコア（独自算出の注目度）: 9.996405509085692
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Standard diffusion samplers generate samples through repeated evaluations of a learned score function. Parallel sampling methods seek to accelerate generation by trading additional evaluations for fewer sequential rounds. This raises the question of how much sequential dependence is unavoidable, even when many score queries can be made simultaneously. We establish the first polynomial parallel-round lower bounds for diffusion sampling with approximate scores. Specifically, we prove (1) a $\widetildeΩ(d^{1/3})$-round lower bound for sampling smooth, near-isotropic Gaussian mixtures in $R^d$, and (2) an $Ω(d)$-round lower bound for uniform sampling from anisotropic axis-aligned boxes contained in the unit ball. Both bounds hold for arbitrary randomized algorithms making polynomially many queries per round at arbitrary locations and noise levels, with inverse-polynomial score error and constant total variation accuracy. The linear bound is tight for our box family. Our constructions use fixed approximate score oracles that enforce sequential access to hidden information while satisfying the accuracy guarantee at every noise level.
• Abstract（参考訳）: 標準拡散サンプリング器は、学習したスコア関数の繰り返し評価によりサンプルを生成する。 並列サンプリング手法は、より少ないシーケンシャルラウンドに対する追加評価を取引することで、生成を加速しようとする。 これにより、同時に多くのスコアクエリを作成できる場合でも、シーケンシャルな依存がどの程度避けられないのかという疑問が持ち上がる。 近似スコアを用いた拡散サンプリングのための第1多項式並列ラウンド下界を確立する。 具体的には、(1)R^d$における滑らかでほぼ等方的なガウス混合をサンプリングするための$\widetildeΩ(d^{1/3})$ラウンド下界、(2)単位球に含まれる異方軸整列箱からの一様サンプリングのための$Ω(d)$ラウンド下界を証明する。 どちらの境界も任意のランダム化アルゴリズムを保ち、任意の位置とノイズレベルで1ラウンド当たりのクエリを多項式的に多数生成する。 線形境界は我々のボックスファミリーにとってきつい。 提案手法では,各ノイズレベルにおける精度保証を満足しつつ,隠れ情報への逐次アクセスを強制する,固定された近似スコアオラクルを用いている。

関連論文リスト

• Two-Sample Testing via Generative Processes [60.42943145582429]
  生成輸送は、2つのサンプルが同じ分布から来るかどうかを決定する新しい方法を提供する。 2つのサンプルの間に直接補間体を構築し、対称スケジュールでは、その法則が時間反射の下で不変であることを観察する。 したがって、t と 1-t の辺辺が、Jensen-Shannon の発散を計算することで一致するかどうかをテストする。
  論文  参考訳（メタデータ） (2026-10-06T12:48:27Z)
• A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization [66.48718943929202]
  非強凸二値問題の場合、既存の一階法はネストループに依存するのが一般的である。 2つの相補成分を組み合わせたSingle-loop Constant-1次ペナルティ法(ICOS)を提案する。
  論文  参考訳（メタデータ） (2026-10-05T19:26:20Z)
• Correcting CondOT: Exact Finite-Step Sampling in Gaussian Flow Matching [20.840789905678488]
  フローマッチングは、徐々にノイズをデータに変換することでサンプルを生成する。 実際には、有限個のサンプリングステップを使用すると、選択したスケジュールに依存する数値誤差が発生する。 本稿では,標準条件付き最適輸送(CondOT)スケジュールが先行中点誤差をキャンセルし,一般収束境界を改善することを示す。
  論文  参考訳（メタデータ） (2026-09-30T10:50:36Z)
• Query Lower Bounds for Diffusion Sampling [5.541583428822629]
  我々は、$d$次元の分布に精度でスコア推定へのアクセスを与えられる場合、サンプリングには$widetilde(sqrtd)$スコアクエリが必要であることを証明した。 我々の証明は、どのサンプルも$widetilde(sqrtd)$の異なるノイズレベルを探索しなければならないことを示し、実際なぜマルチスケールノイズスケジュールが必要なのかを正式な説明を提供する。
  論文  参考訳（メタデータ） (2026-04-12T23:47:46Z)
• Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel [10.840582511203024]
  我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでのみ実行できるように並列化可能であることを示す。 また、我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでしか実行できないことを示す。
  論文  参考訳（メタデータ） (2024-06-03T01:34:34Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。 十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。 ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
  論文  参考訳（メタデータ） (2021-11-29T19:26:28Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。 ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。 我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
  論文  参考訳（メタデータ） (2021-10-20T02:25:25Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)

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

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