論文の概要: Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel

• arxiv url: http://arxiv.org/abs/2406.00924v2
• Date: Thu, 17 Oct 2024 03:54:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-18 13:16:45.539026
• Title: Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel
• Title（参考訳）: ランダム化中間点を用いた高速拡散サンプリング:シークエンシャルと並列
• Authors: Shivam Gupta, Linda Cai, Sitan Chen,
• Abstract要約: 我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでのみ実行できるように並列化可能であることを示す。 また、我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでしか実行できないことを示す。
• 参考スコア（独自算出の注目度）: 10.840582511203024
• License:
• Abstract: Sampling algorithms play an important role in controlling the quality and runtime of diffusion model inference. In recent years, a number of works~\cite{chen2023sampling,chen2023ode,benton2023error,lee2022convergence} have proposed schemes for diffusion sampling with provable guarantees; these works show that for essentially any data distribution, one can approximately sample in polynomial time given a sufficiently accurate estimate of its score functions at different noise levels. In this work, we propose a new scheme inspired by Shen and Lee's randomized midpoint method for log-concave sampling~\cite{ShenL19}. We prove that this approach achieves the best known dimension dependence for sampling from arbitrary smooth distributions in total variation distance ($\widetilde O(d^{5/12})$ compared to $\widetilde O(\sqrt{d})$ from prior work). We also show that our algorithm can be parallelized to run in only $\widetilde O(\log^2 d)$ parallel rounds, constituting the first provable guarantees for parallel sampling with diffusion models. As a byproduct of our methods, for the well-studied problem of log-concave sampling in total variation distance, we give an algorithm and simple analysis achieving dimension dependence $\widetilde O(d^{5/12})$ compared to $\widetilde O(\sqrt{d})$ from prior work.
• Abstract（参考訳）: サンプリングアルゴリズムは拡散モデル推論の品質と実行時間を制御する上で重要な役割を果たす。 近年、多くの研究―\cite{chen2023sampling,chen2023ode,benton2023error,lee2022convergence} が証明可能な保証付き拡散サンプリングのスキームを提案している。 本研究では,ShenとLeeのランダム化中間点法に着想を得た新しい手法を提案する。 このアプローチは、全変動距離 (\widetilde O(d^{5/12})$) における任意の滑らかな分布からサンプリングする際の最もよく知られた次元依存性を、以前の作業から$\widetilde O(\sqrt{d})$と比較する。 また,我々のアルゴリズムは,拡散モデルによる並列サンプリングの証明可能な最初の保証として,$\widetilde O(\log^2 d)$並列ラウンドでのみ並列化可能であることを示す。 提案手法の副産物として,全変動距離におけるログコンケーブサンプリングのよく研究された問題に対して,従来の作業から得られる次元依存性を$\widetilde O(d^{5/12})$と$\widetilde O(\sqrt{d})$と比較するアルゴリズムと簡単な解析を行う。

関連論文リスト

• Efficiently learning and sampling multimodal distributions with data-based initialization [20.575122468674536]
  静止測度から少数のサンプルを与えられたマルコフ連鎖を用いて多重モーダル分布をサンプリングする問題を考察する。 マルコフ連鎖が$k$dのスペクトルギャップを持つ場合、静止分布からのサンプルは、静止測度からテレビ距離において$varepsilon$-closeの条件法則を持つサンプルを効率よく生成する。
  論文  参考訳（メタデータ） (2024-11-14T01:37:02Z)
• Faster Sampling via Stochastic Gradient Proximal Sampler [28.422547264326468]
  非log-concave分布からのサンプリングのための近位サンプリング器 (SPS) について検討した。 対象分布への収束性は,アルゴリズムの軌道が有界である限り保証可能であることを示す。 我々は、Langevin dynamics(SGLD)とLangevin-MALAの2つの実装可能な変種を提供し、SPS-SGLDとSPS-MALAを生み出した。
  論文  参考訳（メタデータ） (2024-05-27T00:53:18Z)
• Fast parallel sampling under isoperimetry [10.619901778151336]
  ログソボレフの不等式を満たすディストリビューション$pi$ over $mathbb Rd$から並列にサンプリングする方法を示す。 提案アルゴリズムは分布$hatpi$からKullback-Leibler分散の$pi$に近いサンプルを出力する。
  論文  参考訳（メタデータ） (2024-01-17T07:24:18Z)
• Improved Active Learning via Dependent Leverage Score Sampling [8.400581768343804]
  本研究では,非依存的(逆方向雑音)環境下での能動学習手法の改善方法について述べる。 エンフェボタルサンプリングアルゴリズムに基づく簡単な実装法を提案する。 独立サンプリングと比較して,本手法は,所定の目標精度に到達するために必要なサンプル数を最大50%削減する。
  論文  参考訳（メタデータ） (2023-10-08T01:51:30Z)
• 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)
• Perfect Sampling from Pairwise Comparisons [26.396901523831534]
  分散分布$mathcalD$の与えられたアクセスから最適なサンプルを効率よく取得する方法を,サポート対象の要素のペア比較に限定して検討する。 固定分布が$mathcalD$と一致するマルコフ連鎖を設計し、過去からの結合技術を用いて正確なサンプルを得るアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-11-23T11:20:30Z)
• Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
  我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。 我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
  論文  参考訳（メタデータ） (2022-07-16T03:09:30Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  高確率状態に着目して離散分布を試験する問題について検討する。 一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-14T16:09:17Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)
• 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)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)

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

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