論文の概要: 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} サンプリングが確実に高速であるにもかかわらず, スーパーポリノミカル時間を要する事例が存在すること, を述べる。
また,指数時間回帰サンプリングアルゴリズムは,指数時間で逆転する一方向関数が存在するという強い仮定の下で,本質的に最適であることを示す。
関連論文リスト
- Convex Relaxations of ReLU Neural Networks Approximate Global Optima in
Polynomial Time [54.01594785269913]
本稿では, 重み劣化と凸緩和に則った2層ReLUネットワーク間の最適性ギャップについて述べる。
トレーニングデータがランダムである場合、元の問題と緩和の間の相対的な最適性ギャップは、サンプルの勾配によって境界付けられることを示す。
論文 参考訳(メタデータ) (2024-02-06T01:29:35Z) - Optimal sampling of tensor networks targeting wave function's fast
decaying tails [0.0]
等尺テンソルネットワーク状態に対する局所測定文字列の量子結果のサンプリングに最適戦略を導入する。
このアルゴリズムはサンプルの繰り返しを回避し、指数関数的に減衰する尾を持つサンプリング分布を効率的に行う。
論文 参考訳(メタデータ) (2024-01-18T19:00:05Z) - Model-adapted Fourier sampling for generative compressed sensing [7.130302992490975]
測定行列が一意行列からランダムにサブサンプリングされたとき, 生成的圧縮センシングについて検討した。
我々は,textitO(kd| boldsymbolalpha|_22)$の測定精度を改良したモデル適応サンプリング戦略を構築した。
論文 参考訳(メタデータ) (2023-10-08T03:13:16Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳(メタデータ) (2023-02-18T09:24:15Z) - Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。
提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
論文 参考訳(メタデータ) (2022-06-22T17:58:23Z) - Robust Sparse Mean Estimation via Sum of Squares [48.07596965953344]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳(メタデータ) (2022-06-07T16:49:54Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。