論文の概要: Parallel Sampling via Autospeculation
- arxiv url: http://arxiv.org/abs/2511.07869v1
- Date: Wed, 12 Nov 2025 01:25:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-12 20:17:03.51333
- Title: Parallel Sampling via Autospeculation
- Title（参考訳）: 自己特定による並列サンプリング
- Authors: Nima Anari, Carlo Baronio, CJ Chen, Alireza Haqi, Frederic Koehler, Anqi Li, Thuy-Duong Vuong,
- Abstract要約: 我々は,任意の順序の自己回帰モデルと拡散モデルという2つの設定において,サンプリングを高速化するアルゴリズムを提案する。
オラクルコールを並列に発行することで、期待されるサンプリング時間を$widetildeO(n1/2)$に削減できることを示す。
我々は投機的拒絶サンプリングという新しい手法を導入する。
- 参考スコア（独自算出の注目度）: 13.643401888306398
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present parallel algorithms to accelerate sampling via counting in two settings: any-order autoregressive models and denoising diffusion models. An any-order autoregressive model accesses a target distribution $μ$ on $[q]^n$ through an oracle that provides conditional marginals, while a denoising diffusion model accesses a target distribution $μ$ on $\mathbb{R}^n$ through an oracle that provides conditional means under Gaussian noise. Standard sequential sampling algorithms require $\widetilde{O}(n)$ time to produce a sample from $μ$ in either setting. We show that, by issuing oracle calls in parallel, the expected sampling time can be reduced to $\widetilde{O}(n^{1/2})$. This improves the previous $\widetilde{O}(n^{2/3})$ bound for any-order autoregressive models and yields the first parallel speedup for diffusion models in the high-accuracy regime, under the relatively mild assumption that the support of $μ$ is bounded. We introduce a novel technique to obtain our results: speculative rejection sampling. This technique leverages an auxiliary ``speculative'' distribution~$ν$ that approximates~$μ$ to accelerate sampling. Our technique is inspired by the well-studied ``speculative decoding'' techniques popular in large language models, but differs in key ways. Firstly, we use ``autospeculation,'' namely we build the speculation $ν$ out of the same oracle that defines~$μ$. In contrast, speculative decoding typically requires a separate, faster, but potentially less accurate ``draft'' model $ν$. Secondly, the key differentiating factor in our technique is that we make and accept speculations at a ``sequence'' level rather than at the level of single (or a few) steps. This last fact is key to unlocking our parallel runtime of $\widetilde{O}(n^{1/2})$.
- Abstract（参考訳）: 我々は,任意の順序自己回帰モデルと拡散モデルという2つの設定において,サンプリングを高速化する並列アルゴリズムを提案する。
任意の順序自己回帰モデルは、条件境界を提供するオラクルを通して、ターゲット分布に$μ$ on $[q]^n$をアクセスし、一方、デノナイズ拡散モデルは、ガウス雑音の下で条件平均を提供するオラクルを介して、ターゲット分布に$μ$ on $\mathbb{R}^n$をアクセスする。
標準的なシーケンシャルサンプリングアルゴリズムは、どちらも$μ$からサンプルを生成するのに$\widetilde{O}(n)$時間を必要とする。
オラクルコールを並列に発行することで、期待されるサンプリング時間を$\widetilde{O}(n^{1/2})$に削減できることを示す。
これにより、任意の階自己回帰モデルに対する以前の$\widetilde{O}(n^{2/3})$boundが改善され、$μ$のサポートが有界であるという比較的穏やかな仮定の下で、高精度な状態における拡散モデルに対する最初の並列スピードアップが得られる。
我々は投機的拒絶サンプリングという新しい手法を導入する。
この手法は補助的な `speculative'' 分布~$ν$ を利用してサンプリングを加速する。
提案手法は, 大規模言語モデルで広く普及している「投機的復号化」技術に着想を得たものであるが, キーとなる方法が異なる。
まず、'`autospeculation,' を使い、—$μ$ を定義する同じオラクルから$ν$ という憶測を構築します。
対照的に、投機的復号法は通常、分離され、高速だが、より正確でない ``draft'' モデル $ν$ を必要とする。
第2に,我々の技術における重要な差別化要因は,単一(あるいは少数の)ステップではなく,‘シーケンス’レベルでの推測と受け入れを行うことです。
この最後の事実は、$\widetilde{O}(n^{1/2})$の並列ランタイムをアンロックする鍵となります。
関連論文リスト
- Constrained and Composite Sampling via Proximal Sampler [2.087898608419977]
本研究では,制約サンプリングと複合サンプリングの2つの対数凹型サンプリング問題について検討する。
主な課題は、ミキシングを劣化させることなくフィージビリティを強制することである。
複合サンプリングでは、ターゲットは$exp(-f(x)-h(x))$に比例する。
論文 参考訳（メタデータ） (2026-02-16T05:36:36Z) - Posterior Sampling by Combining Diffusion Models with Annealed Langevin Dynamics [6.987640034932562]
後方サンプリングは、塗装、脱臭、MRI再構成などのタスクのための正確で公正なフレームワークを提供する。
我々は、拡散モデルとランゲヴィン力学の変種を組み合わせることで、スコア誤差の$L4$バウンドだけで条件付きサンプリングを実現することを証明した。
論文 参考訳（メタデータ） (2025-10-30T10:17:27Z) - DISCO: Diversifying Sample Condensation for Efficient Model Evaluation [59.01400190971061]
コスト評価は傾向を低下させ、イノベーションのサイクルを遅くし、環境への影響を悪化させる。
モデル応答の多様性を最大化するサンプルを選択することが重要となる。
我々のメソッドである$textbfDiversifying Sample Condensation (DISCO)$は、最も大きなモデル不一致を持つトップkサンプルを選択します。
論文 参考訳（メタデータ） (2025-10-09T08:53:59Z) - Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [72.69498649272347]
条件分布は機械学習の中心的な問題です
ペアデータとペアデータの両方を統合する新しいパラダイムを提案する。
提案手法は任意の誤差で理論上真の条件分布を復元可能であることを示す。
論文 参考訳（メタデータ） (2024-10-03T16:12:59Z) - Parallel Sampling via Counting [3.6854430278041264]
任意の分布からのサンプリングを高速化するために並列化を用いる方法を示す。
我々のアルゴリズムは、$O(n2/3cdot operatornamepolylog(n,q))$ parallel timeである。
この結果は自己回帰モデルにおけるサンプリングに影響を及ぼす。
論文 参考訳（メタデータ） (2024-08-18T11:42:54Z) - 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) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - Optimal Sublinear Sampling of Spanning Trees and Determinantal Point
Processes via Average-Case Entropic Independence [3.9586758145580014]
強いレイリー分布から繰り返しサンプリングする高速アルゴリズムを設計する。
グラフ $G=(V, E)$ に対して、$G$ in $widetildeO(lvert Vrvert)$ time per sample から一様にランダムに散らばる木を概算する方法を示す。
$n$要素の基底集合の$k$のサブセット上の決定的点プロセスに対して、$widetildeO(komega)$ time の最初の $widetildeO(nk) の後に、$widetildeO(komega)$ time のサンプルを概算する方法を示す。
論文 参考訳（メタデータ） (2022-04-06T04:11:26Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳（メタデータ） (2020-07-15T03:25:24Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。