論文の概要: Diffusion Posterior Sampling is Computationally Intractable
- arxiv url: http://arxiv.org/abs/2402.12727v1
- Date: Tue, 20 Feb 2024 05:28:13 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-21 16:59:37.947084
- Title: Diffusion Posterior Sampling is Computationally Intractable
- Title（参考訳）: 拡散後サンプリングは計算可能
- Authors: Shivam Gupta, Ajil Jalal, Aditya Parulekar, Eric Price, Zhiyang Xun
- Abstract要約: 後方サンプリングは、塗装、超解像、MRI再構成などのタスクに有用である。
暗号における最も基本的な仮定では、一方通行関数が存在する。
また,指数時間回帰サンプリングは,指数時間で逆転する一方向関数が存在するという強い仮定の下で,本質的に最適であることを示す。
- 参考スコア（独自算出の注目度）: 9.483130965295324
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Diffusion models are a remarkably effective way of learning and sampling from
a distribution $p(x)$. In posterior sampling, one is also given a measurement
model $p(y \mid x)$ and a measurement $y$, and would like to sample from $p(x
\mid y)$. Posterior sampling is useful for tasks such as inpainting,
super-resolution, and MRI reconstruction, so a number of recent works have
given algorithms to heuristically approximate it; but none are known to
converge to the correct distribution in polynomial time.
In this paper we show that posterior sampling is \emph{computationally
intractable}: under the most basic assumption in cryptography -- that one-way
functions exist -- there are instances for which \emph{every} algorithm takes
superpolynomial time, even though \emph{unconditional} sampling is provably
fast. We also show that the exponential-time rejection sampling algorithm is
essentially optimal under the stronger plausible assumption that there are
one-way functions that take exponential time to invert.
- Abstract（参考訳）: 拡散モデルは分布$pからの学習とサンプリングの極めて効果的な方法である
(x)$。
後方サンプリングでは、測定モデル $p(y \mid) も与えられる。
x)$と測定値$y$で、$p(x \mid)からサンプリングしたい
y) である。
後部サンプリングは、塗装、超解像、MRI再構成などのタスクに有用であるため、近年の多くの研究でそれをヒューリスティックに近似するアルゴリズムが提供されているが、多項式時間で正しい分布に収束することは知られていない。
本稿では, 後続サンプリングが, 暗号の最も基本的な前提として, 片方向関数が存在すること, あるいは, \emph{unconditional} サンプリングが確実に高速であるにもかかわらず, スーパーポリノミカル時間を要する事例が存在すること, を述べる。
また,指数時間回帰サンプリングアルゴリズムは,指数時間で逆転する一方向関数が存在するという強い仮定の下で,本質的に最適であることを示す。
関連論文リスト
- 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) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Consistency Model is an Effective Posterior Sample Approximation for Diffusion Inverse Solvers [28.678613691787096]
過去の近似は後続の手段に依存しており、画像分布の支持には当てはまらない可能性がある。
本稿では,画像分布支援において有効なサンプルを生成することを保証する,後部近似のための新しい手法を提案する。
論文 参考訳（メタデータ） (2024-02-09T02:23:47Z) - Optimal sampling of tensor networks targeting wave function's fast
decaying tails [0.0]
等尺テンソルネットワーク状態に対する局所測定文字列の量子結果のサンプリングに最適戦略を導入する。
このアルゴリズムはサンプルの繰り返しを回避し、指数関数的に減衰する尾を持つサンプリング分布を効率的に行う。
論文 参考訳（メタデータ） (2024-01-18T19:00:05Z) - Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。
提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
論文 参考訳（メタデータ） (2022-06-22T17:58:23Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - 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) - Faster Differentially Private Samplers via R\'enyi Divergence Analysis
of Discretized Langevin MCMC [35.050135428062795]
ランゲヴィン力学に基づくアルゴリズムは、統計距離のようなある程度の距離測度の下で、はるかに高速な代替手段を提供する。
我々の手法は単純で汎用的で、アンダーダムドランゲヴィン力学に適用できる。
論文 参考訳（メタデータ） (2020-10-27T22:52:45Z) - Efficient sampling from the Bingham distribution [38.50073658077009]
我々は、Bingham分布の$p(x)propto exp(xtop A x)$と、$operatornamepoly(d, lambda_max(A)-lambda_min(A))$の期待ランタイムを持つ球面$mathcal Sd-1$の正確なサンプリングアルゴリズムを与える。
直接応用として、ランク1行列推論問題の後方分布を時間内にサンプリングする。
論文 参考訳（メタデータ） (2020-09-30T22:48:03Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。