論文の概要: On the Fine-Grained Hardness of Inverting Generative Models
- arxiv url: http://arxiv.org/abs/2309.05795v1
- Date: Mon, 11 Sep 2023 20:03:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-13 15:19:14.501593
- Title: On the Fine-Grained Hardness of Inverting Generative Models
- Title(参考訳): 逆生成モデルの細粒度硬さについて
- Authors: Feyza Duman Keles and Chinmay Hegde
- Abstract要約: 生成モデル反転は、コンピュータビジョンとNLPを含む多くの現代のアプリケーションにおいて、コア計算プリミティブである。
本稿では,この問題に対する計算硬さの景観を詳細に把握することを目的としている。
強い指数時間仮説 (SETH) の下では、正確な逆転の計算複雑性が$Omega (2n)$で制限されることを示した。
近似反転のより実践的な問題として、モデル範囲の点が与えられた目標に近いかどうかを決定することが目的である。
- 参考スコア(独自算出の注目度): 21.566795159091747
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The objective of generative model inversion is to identify a size-$n$ latent
vector that produces a generative model output that closely matches a given
target. This operation is a core computational primitive in numerous modern
applications involving computer vision and NLP. However, the problem is known
to be computationally challenging and NP-hard in the worst case. This paper
aims to provide a fine-grained view of the landscape of computational hardness
for this problem. We establish several new hardness lower bounds for both exact
and approximate model inversion. In exact inversion, the goal is to determine
whether a target is contained within the range of a given generative model.
Under the strong exponential time hypothesis (SETH), we demonstrate that the
computational complexity of exact inversion is lower bounded by $\Omega(2^n)$
via a reduction from $k$-SAT; this is a strengthening of known results. For the
more practically relevant problem of approximate inversion, the goal is to
determine whether a point in the model range is close to a given target with
respect to the $\ell_p$-norm. When $p$ is a positive odd integer, under SETH,
we provide an $\Omega(2^n)$ complexity lower bound via a reduction from the
closest vectors problem (CVP). Finally, when $p$ is even, under the exponential
time hypothesis (ETH), we provide a lower bound of $2^{\Omega (n)}$ via a
reduction from Half-Clique and Vertex-Cover.
- Abstract(参考訳): 生成モデル逆転の目的は、与えられたターゲットと密に一致する生成モデル出力を生成するサイズ=n$潜在ベクトルを特定することである。
この操作は、コンピュータビジョンとnlpを含む多くの現代的な応用におけるコア計算プリミティブである。
しかし、この問題は計算的に困難であり、最悪の場合NPハードであることが知られている。
本稿では,この問題に対する計算硬度の景観を詳細に把握することを目的とする。
厳密なモデル反転と近似モデル反転の両方に対して,いくつかの新しい硬度下界を定式化する。
正確には、目標が与えられた生成モデルの範囲内に含まれるかどうかを決定することである。
強い指数時間仮説 (SETH) の下では、正確な逆転の計算複雑性が$\Omega(2^n)$で$k$-SATから還元されることが示され、これは既知の結果の強化である。
近似逆変換のより実践的な問題に対して、モデル範囲の点が与えられた目標に近づくかどうかを$\ell_p$-norm に対して決定することが目的である。
p$ が正の奇数であるとき、SETH の下では、最も近いベクトル問題 (CVP) から還元して、$\Omega(2^n)$ の複雑性を下界とする。
最後に、$p$ が偶数であるとき、指数時間仮説 (ETH) の下では、ハーフ・クライドとバーテックス・コーバーの還元により 2^{\Omega (n)}$ の低い境界を与える。
関連論文リスト
- Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネル空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
我々は、$epsilon$-covering up $mathcalO(epsilon-frac2dd+2)$に対する計量エントロピーの改善結果を得る。
論文 参考訳(メタデータ) (2024-04-29T15:04:07Z) - Convergence Analysis of Probability Flow ODE for Score-based Generative Models [5.939858158928473]
確率フローODEに基づく決定論的サンプリング器の収束特性を理論的・数値的両面から検討する。
我々は、目標と生成されたデータ分布の総変動を、連続時間レベルで$mathcalO(dsqrtdelta)$で表すことができることを証明した。
ステップサイズ$h$を持つ$p$-thオーダーのRunge-Kuttaインテグレータを使った実用的な実装では、離散レベルで$mathcalO(dsqrtdelta + (dh)p)$のエラー境界を確立する。
論文 参考訳(メタデータ) (2024-04-15T12:29:28Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳(メタデータ) (2024-03-08T18:50:19Z) - Restricted Strong Convexity of Deep Learning Models with Smooth
Activations [31.003601717265006]
本研究では,スムーズなアクティベーション機能を持つディープラーニングモデルの最適化問題について検討する。
Restricted Strong Convexity (RSC) に基づく最適化の新しい解析手法を提案する。
深層学習モデルのためのRCCに基づくGDの幾何収束性を確立するための最初の結果である。
論文 参考訳(メタデータ) (2022-09-29T21:24:26Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-08-26T16:21:31Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳(メタデータ) (2021-10-09T21:13:48Z) - Estimating Stochastic Linear Combination of Non-linear Regressions
Efficiently and Scalably [23.372021234032363]
サブサンプルサイズが大きくなると、推定誤差が過度に犠牲になることを示す。
私たちの知る限りでは、線形テキスト+確率モデルが保証される最初の研究です。
論文 参考訳(メタデータ) (2020-10-19T07:15:38Z) - Estimation in Tensor Ising Models [5.161531917413708]
N$ノード上の分布から1つのサンプルを与えられた$p$-tensor Isingモデルの自然パラメータを推定する問題を考える。
特に、$sqrt N$-consistency of the MPL estimate in the $p$-spin Sherrington-Kirkpatrick (SK) model。
我々は、$p$-tensor Curie-Weiss モデルの特別な場合における MPL 推定の正確なゆらぎを導出する。
論文 参考訳(メタデータ) (2020-08-29T00:06:58Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。