論文の概要: Computational-Statistical Gaps in Gaussian Single-Index Models

• arxiv url: http://arxiv.org/abs/2403.05529v2
• Date: Tue, 12 Mar 2024 22:27:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-14 10:59:10.097895
• Title: Computational-Statistical Gaps in Gaussian Single-Index Models
• Title（参考訳）: ガウスの単一インデックスモデルにおける計算統計的ギャップ
• Authors: Alex Damian, Loucas Pillaud-Vivien, Jason D. Lee, Joan Bruna
• Abstract要約: 単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
• 参考スコア（独自算出の注目度）: 77.1473134227844
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Single-Index Models are high-dimensional regression problems with planted structure, whereby labels depend on an unknown one-dimensional projection of the input via a generic, non-linear, and potentially non-deterministic transformation. As such, they encompass a broad class of statistical inference tasks, and provide a rich template to study statistical and computational trade-offs in the high-dimensional regime. While the information-theoretic sample complexity to recover the hidden direction is linear in the dimension $d$, we show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $\Omega(d^{k^\star/2})$ samples, where $k^\star$ is a "generative" exponent associated with the model that we explicitly characterize. Moreover, we show that this sample complexity is also sufficient, by establishing matching upper bounds using a partial-trace algorithm. Therefore, our results provide evidence of a sharp computational-to-statistical gap (under both the SQ and LDP class) whenever $k^\star>2$. To complete the study, we provide examples of smooth and Lipschitz deterministic target functions with arbitrarily large generative exponents $k^\star$.
• Abstract（参考訳）: 単一インデックスモデル(Single-Index Models)は、植木構造における高次元回帰問題であり、ラベルは汎用的で非線形で潜在的に非決定論的変換を通じて入力の未知の1次元の射影に依存する。 このように、それらは幅広い統計的推論タスクを包含し、高次元状態における統計的および計算的トレードオフを研究するための豊富なテンプレートを提供する。 隠れた方向を復元する情報理論的なサンプル複雑性は$d$で線形であるが、統計的クエリ (SQ) と低デグレ多項式 (LDP) フレームワークの両方において計算効率のよいアルゴリズムは、必然的に$\Omega(d^{k^\star/2})$サンプルを必要とする。 さらに、このサンプルの複雑さも、部分トレースアルゴリズムを用いて一致した上限を確立することで十分であることを示す。 したがって、この結果は、$k^\star>2$のとき、(SQクラスとLDPクラスの両方で)鋭い計算と統計のギャップの証拠となる。 この研究を完了するために、任意に大きい生成指数を$k^\star$とする滑らかかつリプシッツ決定論的対象関数の例を示す。

関連論文リスト

• Scaling and renormalization in high-dimensional regression [72.59731158970894]
  本稿では,様々な高次元リッジ回帰モデルの訓練および一般化性能の簡潔な導出について述べる。 本稿では,物理と深層学習の背景を持つ読者を対象に,これらのトピックに関する最近の研究成果の紹介とレビューを行う。
  論文  参考訳（メタデータ） (2024-05-01T15:59:00Z)
• Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data [4.971690889257356]
  コリンズとナイアーとヴァスワニによって提案された交互最小化・退化スキームの適応について紹介する。 iidにおいてもバニラ変動最小化降下は破滅的に失敗するが, 軽度に非等方性データは得られない。 我々の分析は、事前の作業を統一し、一般化し、幅広いアプリケーションに柔軟なフレームワークを提供する。
  論文  参考訳（メタデータ） (2023-08-08T17:56:20Z)
• Subspace clustering in high-dimensions: Phase transitions \& Statistical-to-Computational gap [24.073221004661427]
  部分空間クラスタリングを研究するための単純なモデルは、高次元の$k$-ガウス混合モデルである。 広帯域な高次元状態における統計的に最適な再構成誤差を正確に評価する。
  論文  参考訳（メタデータ） (2022-05-26T17:47:35Z)
• Improving Computational Complexity in Statistical Models with Second-Order Information [32.64382185990981]
  パラメトリック統計モデルにおけるパラメータ推定のための正規化勾配降下法(NormGD)について検討する。 我々は、NormGDアルゴリズムが最終的な統計的半径に達するために最適な計算量$mathcalO(n)$を達成することを示した。 この計算複雑性は、固定ステップサイズ勾配勾配アルゴリズムよりも安価である。
  論文  参考訳（メタデータ） (2022-02-09T01:32:50Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably [23.372021234032363]
  サブサンプルサイズが大きくなると、推定誤差が過度に犠牲になることを示す。 私たちの知る限りでは、線形テキスト+確率モデルが保証される最初の研究です。
  論文  参考訳（メタデータ） (2020-10-19T07:15:38Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。 本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
  論文  参考訳（メタデータ） (2020-05-22T22:30:52Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。 アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。 ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
  論文  参考訳（メタデータ） (2020-02-20T10:50:58Z)
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-$\ell_1$-Norm Interpolated Classifiers [3.167685495996986]
  本稿では,分離可能なデータの強化に関する高精度な高次元理論を確立する。 統計モデルのクラスでは、ブースティングの普遍性誤差を正確に解析する。 また, 推力試験誤差と最適ベイズ誤差の関係を明示的に説明する。
  論文  参考訳（メタデータ） (2020-02-05T00:24:53Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。