論文の概要: The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models

• arxiv url: http://arxiv.org/abs/2506.05500v1
• Date: Thu, 05 Jun 2025 18:34:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-09 17:28:43.194854
• Title: The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models
• Title（参考訳）: Generative Leap: ガウスのマルチインデックスモデルを効率的に学習するためのシャープサンプル複雑さ
• Authors: Alex Damian, Jason D. Lee, Joan Bruna,
• Abstract要約: この研究において、ラベルは(ガウス)$d$-次元入力にのみ依存し、低次元$r = O_d(1)$部分空間への射影を通して得られる。 生成的跳躍指数 $kstar$, [Damian et al.'24] から生成的指数の自然拡張をマルチインデックス設定に導入する。
• 参考スコア（独自算出の注目度）: 71.5283441529015
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work we consider generic Gaussian Multi-index models, in which the labels only depend on the (Gaussian) $d$-dimensional inputs through their projection onto a low-dimensional $r = O_d(1)$ subspace, and we study efficient agnostic estimation procedures for this hidden subspace. We introduce the \emph{generative leap} exponent $k^\star$, a natural extension of the generative exponent from [Damian et al.'24] to the multi-index setting. We first show that a sample complexity of $n=\Theta(d^{1 \vee \k/2})$ is necessary in the class of algorithms captured by the Low-Degree-Polynomial framework. We then establish that this sample complexity is also sufficient, by giving an agnostic sequential estimation procedure (that is, requiring no prior knowledge of the multi-index model) based on a spectral U-statistic over appropriate Hermite tensors. We further compute the generative leap exponent for several examples including piecewise linear functions (deep ReLU networks with bias), and general deep neural networks (with $r$-dimensional first hidden layer).
• Abstract（参考訳）: 本研究では,低次元$r = O_d(1)$部分空間への射影による(ガウス)$d$-次元入力にのみ依存する一般ガウス多次元モデルについて考察する。 Damian et al '24] から生成指数の自然拡張である \emph{generative leap} exponent $k^\star$ を導入する。 まず、Low-Degree-Polynomialフレームワークによってキャプチャされたアルゴリズムのクラスにおいて、$n=\Theta(d^{1 \vee \k/2})$のサンプル複雑性が必要とされることを示す。 そして、適切なエルミートテンソル上のスペクトルU-統計に基づいて、このサンプルの複雑さも十分であることを示す。 さらに, 分割線形関数(バイアスの深いReLUネットワーク)や, 一般的なディープニューラルネットワーク($r$次元の第1隠蔽層)など, 数例で生成的跳躍指数を計算する。

関連論文リスト

• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Model-adapted Fourier sampling for generative compressed sensing [7.130302992490975]
  測定行列が一意行列からランダムにサブサンプリングされたとき, 生成的圧縮センシングについて検討した。 我々は,textitO(kd| boldsymbolalpha|_22)$の測定精度を改良したモデル適応サンプリング戦略を構築した。
  論文  参考訳（メタデータ） (2023-10-08T03:13:16Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。 遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
  論文  参考訳（メタデータ） (2022-10-30T22:58:22Z)
• 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)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。 我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-30T19:10:32Z)
• Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing [22.337756118270217]
  基本統計量に対する2つの方法を開発した:$epsilon$-corrupted set of $n$ sample from a $d$-linear sub-Gaussian distribution。 最初のロバストなアルゴリズムは反復フィルタリングを時間内に実行し、近似固有ベクトルを返し、単純なフィルタリングアプローチに基づいている。 私たちの2つめは、わずかに悪い近似係数を達成し、軽度のスペクトルギャップ仮定の下でほぼ自明な時間とイテレーションで実行します。
  論文  参考訳（メタデータ） (2020-06-12T07:45:38Z)

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

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