論文の概要: 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)}$ の低い境界を与える。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39:42Z) - 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) - Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth [1.9643748953805935]
コンベックス関数を$gamma-$Holderian成長下で最小化するために、完全かつ不正確なPPAの漸近複雑性を導出する。
数値実験では, 既存の再起動バージョンよりも改善が見られた。
論文 参考訳（メタデータ） (2021-08-10T07:15:07Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。