論文の概要: On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis
- arxiv url: http://arxiv.org/abs/2501.04377v2
- Date: Sun, 02 Feb 2025 23:48:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-04 16:07:59.277954
- Title: On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis
- Title（参考訳）: 視覚自己回帰モデルにおける計算限界と潜在的に効率的な基準について:細粒度複雑度解析
- Authors: Yekun Ke, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song,
- Abstract要約: 我々は,Visual Autoregressive(mathsf/$)モデルの計算限界と効率基準を分析する。
より詳細な複雑性理論からStrong Exponential Time hypothesis(mathsfSETH$)を仮定すると、$mathsf/$モデルに対する準量子時間アルゴリズムは不可能である。
私たちの技術は、$mathsf/$フレームワークでスケーラブルで効率的な画像生成を推し進めることに重点を置いています。
- 参考スコア（独自算出の注目度）: 22.641550077885686
- License:
- Abstract: Recently, Visual Autoregressive ($\mathsf{VAR}$) Models introduced a groundbreaking advancement in the field of image generation, offering a scalable approach through a coarse-to-fine ``next-scale prediction'' paradigm. Suppose that $n$ represents the height and width of the last VQ code map generated by $\mathsf{VAR}$ models, the state-of-the-art algorithm in [Tian, Jiang, Yuan, Peng and Wang, NeurIPS 2024] takes $O(n^{4+o(1)})$ time, which is computationally inefficient. In this work, we analyze the computational limits and efficiency criteria of $\mathsf{VAR}$ Models through a fine-grained complexity lens. Our key contribution is identifying the conditions under which $\mathsf{VAR}$ computations can achieve sub-quadratic time complexity. We have proved that assuming the Strong Exponential Time Hypothesis ($\mathsf{SETH}$) from fine-grained complexity theory, a sub-quartic time algorithm for $\mathsf{VAR}$ models is impossible. To substantiate our theoretical findings, we present efficient constructions leveraging low-rank approximations that align with the derived criteria. This work initiates the study of the computational efficiency of the $\mathsf{VAR}$ model from a theoretical perspective. Our technique will shed light on advancing scalable and efficient image generation in $\mathsf{VAR}$ frameworks.
- Abstract（参考訳）: 最近、Visual Autoregressive$\mathsf{VAR}$) Modelsは、画像生成の分野における画期的な進歩を導入し、粗い‘next-scale prediction’パラダイムを通じてスケーラブルなアプローチを提供した。
n$は、$\mathsf{VAR}$モデルによって生成される最後のVQ符号マップの高さと幅を表すと仮定すると、[Tian, Jiang, Yuan, Peng and Wang, NeurIPS 2024] における最先端のアルゴリズムは、計算的に非効率な$O(n^{4+o(1)})$時間を取る。
本研究では,より微細な複雑性レンズを用いて,$\mathsf{VAR}$ Modelsの計算限界と効率の基準を解析する。
我々の重要な貢献は、$\mathsf{VAR}$計算が準二次時間複雑性を実現する条件を特定することである。
より詳細な複雑性理論からStrong Exponential Time hypothesis(\mathsf{SETH}$)を仮定すると、$\mathsf{VAR}$モデルの準量子時間アルゴリズムは不可能であることが証明された。
理論的な知見を裏付けるために, 導出基準に適合する低ランク近似を利用した効率的な構成法を提案する。
この研究は理論的な観点から$\mathsf{VAR}$モデルの計算効率の研究を始める。
我々の技術は、$\mathsf{VAR}$フレームワークにおけるスケーラブルで効率的な画像生成の進歩に光を当てます。
関連論文リスト
- Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39:42Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Learning the hypotheses space from data through a U-curve algorithm: a
statistically consistent complexity regularizer for Model Selection [0.0]
本稿では, モデル選択に対するデータ駆動型, 一貫性, 非排他的アプローチを提案する。
我々の主な貢献は、$mathbbL(mathcalH)$上で正規化モデル選択を行うデータ駆動の一般学習アルゴリズムである。
このアプローチの顕著な結果は、$mathbbL(mathcalH)$の非排他的探索が最適解を返すことができる条件である。
論文 参考訳（メタデータ） (2021-09-08T18:28:56Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - Estimating Stochastic Linear Combination of Non-linear Regressions
Efficiently and Scalably [23.372021234032363]
サブサンプルサイズが大きくなると、推定誤差が過度に犠牲になることを示す。
私たちの知る限りでは、線形テキスト+確率モデルが保証される最初の研究です。
論文 参考訳（メタデータ） (2020-10-19T07:15:38Z) - Subgradient Regularized Multivariate Convex Regression at Scale [21.55988846648753]
次数正規化凸回帰関数を$d$次元で$n$のサンプルに適合させる新しい大規模アルゴリズムを提案する。
本研究のフレームワークは,n=105$と$d=10$で,段階的な正規化凸回帰問題のインスタンスを数分で解くことができることを示す。
論文 参考訳（メタデータ） (2020-05-23T19:08:39Z) - Reinforcement Learning with General Value Function Approximation:
Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
一般値関数近似を用いた効率の良い強化学習アルゴリズムを確立する。
我々のアルゴリズムは、$d$が複雑性測度である場合、$widetildeO(mathrmpoly(dH)sqrtT)$の後悔の限界を達成することを示す。
我々の理論は線形値関数近似によるRLの最近の進歩を一般化し、環境モデルに対する明示的な仮定をしない。
論文 参考訳（メタデータ） (2020-05-21T17:36:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。