論文の概要: Computational bottlenecks for denoising diffusions
- arxiv url: http://arxiv.org/abs/2503.08028v1
- Date: Tue, 11 Mar 2025 04:21:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-12 15:45:50.425875
- Title: Computational bottlenecks for denoising diffusions
- Title（参考訳）: 微分拡散の計算的ボトルネック
- Authors: Andrea Montanari, Viet Vu,
- Abstract要約: 拡散の認知は、プロセス$(hatboldsymbol x_t:tge 0)$ in $mathbb Rd$を構成することによって、確率分布$mu$ in $mathbbRd$からサンプルをサンプリングする一般的な戦略を提供する。
我々は,任意の時間計算可能なドリフトを,スコアマッチングの目的を最小限に変化させる方法で修正できることを示す。
- 参考スコア（独自算出の注目度）: 8.05574597775852
- License:
- Abstract: Denoising diffusions provide a general strategy to sample from a probability distribution $\mu$ in $\mathbb{R}^d$ by constructing a stochastic process $(\hat{\boldsymbol x}_t:t\ge 0)$ in ${\mathbb R}^d$ such that the distribution of $\hat{\boldsymbol x}_T$ at large times $T$ approximates $\mu$. The drift ${\boldsymbol m}:{\mathbb R}^d\times{\mathbb R}\to{\mathbb R}^d$ of this diffusion process is learned from data (samples from $\mu$) by minimizing the so-called score-matching objective. In order for the generating process to be efficient, it must be possible to evaluate (an approximation of) ${\boldsymbol m}({\boldsymbol y},t)$ in polynomial time. Is every probability distribution $\mu$, for which sampling is tractable, also amenable to sampling via diffusions? We provide evidence to the contrary by constructing a probability distribution $\mu$ for which sampling is easy, but the drift of the diffusion process is intractable -- under a popular conjecture on information-computation gaps in statistical estimation. We further show that any polynomial-time computable drift can be modified in a way that changes minimally the score matching objective and yet results in incorrect sampling.
- Abstract（参考訳）: 拡散のデノイングは確率分布 $\mu$ in $\mathbb{R}^d$ を確率過程 $(\hat{\boldsymbol x}_t:t\ge 0)$ in ${\mathbb R}^d$ とすることで、確率分布 $\mu$ in $\mathbb{R}^d$ からサンプリングするための一般的な戦略を提供する。
この拡散過程のドリフト ${\boldsymbol m}:{\mathbb R}^d\times{\mathbb R}\to{\mathbb R}^d$ は、いわゆるスコアマッチングの目的を最小化することによって、データ($\mu$からのサンプル)から学習される。
生成過程を効率的にするためには、多項式時間で${\boldsymbol m}({\boldsymbol y},t)$を評価する必要がある。
すべての確率分布は$\mu$で、サンプリングはトラクタブルであり、拡散によるサンプリングも可能か?
サンプリングが容易な確率分布を$\mu$で構築することで、逆の証拠を与えるが、拡散過程のドリフトは、統計的推定における情報計算のギャップに関する一般的な予想の下では、難解である。
さらに、多項式時間計算可能なドリフトは、スコアマッチングの目的を最小限に変化させることができ、誤ったサンプリング結果が得られることを示す。
関連論文リスト
- Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination [35.67742880001828]
平均シフト汚染を用いた高次元ロバスト平均推定のための計算効率のよい最初のアルゴリズムを提案する。
提案アルゴリズムは, ほぼ最適サンプルの複雑性を持ち, サンプル・ポリノミカル時間で動作し, ターゲット平均を任意の精度で近似する。
論文 参考訳（メタデータ） (2025-02-20T17:53:13Z) - Outsourced diffusion sampling: Efficient posterior inference in latent spaces of generative models [65.71506381302815]
本稿では、$p(mathbfxmidmathbfy) propto p_theta(mathbfx)$ という形式の後続分布からサンプリングするコストを償却する。
多くのモデルと関心の制約に対して、ノイズ空間の後方はデータ空間の後方よりも滑らかであり、そのような償却推論に対してより快適である。
論文 参考訳（メタデータ） (2025-02-10T19:49:54Z) - A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Models [45.60426164657739]
拡散型サンプリング器の非漸近収束理論を開発する。
我々は、$d/varepsilon$がターゲット分布を$varepsilon$トータル偏差距離に近似するのに十分であることを証明した。
我々の結果は、$ell$のスコア推定誤差がデータ生成プロセスの品質にどのように影響するかも特徴付ける。
論文 参考訳（メタデータ） (2024-08-05T09:02:24Z) - Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions [11.222970035173372]
カーネルベースのスコア推定器は$widetildeOleft(n-1 t-fracd+22(tfracd2 vee 1)rightの最適平均二乗誤差を達成する
核を用いたスコア推定器は,拡散モデルで生成した試料の分布の総変動誤差に対して,極小ガウスの下での最大平均2乗誤差を$widetildeOleft(n-1/2 t-fracd4right)$上界で達成することを示す。
論文 参考訳（メタデータ） (2024-02-23T20:51:31Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳（メタデータ） (2023-02-20T23:29:43Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - An MCMC Method to Sample from Lattice Distributions [4.4044968357361745]
我々はMarkov Chain Monte Carloアルゴリズムを導入し、$d$-dimensional lattice $Lambdaでサポートされている確率分布からサンプルを生成する。
提案する分布として$pi$を使用し、適切な目標分布に対するメトロポリス・ハスティングの受け入れ比率を算出する。
論文 参考訳（メタデータ） (2021-01-16T15:01:53Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。