論文の概要: Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model

• arxiv url: http://arxiv.org/abs/2606.15219v1
• Date: Sat, 13 Jun 2026 09:34:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-16 16:21:33.061358
• Title: Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model
• Title（参考訳）: ニューラルネットワークは最適計算統計トレードオフを実現することができるか? : 単一インデックスモデルによる解析
• Authors: Siyu Chen, Beining Wu, Miao Lu, Zhuoran Yang, Tianhao Wang,
• Abstract要約: 本稿では,2層ニューラルネットワークを時間内にトレーニングするための勾配に基づくアルゴリズムを提案する。 このアルゴリズムは未知の信号$star$と強く一致したスパース表現を学習することを示す。 私たちは、$star$が$k$-sparse for $k = o(sqrtd)$という設定にアプローチを拡張します。
• 参考スコア（独自算出の注目度）: 53.6316818897326
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we tackle the following question: Can neural networks trained with gradient-based methods achieve the optimal computational-statistical tradeoff in learning Gaussian single-index models? Prior research has shown that any polynomial-time algorithm under the statistical query (SQ) framework requires $Ω(d^{s^\star/2}\lor d)$ samples, where $s^\star$ is the generative exponent representing the intrinsic difficulty of learning the underlying model. However, it remains unknown whether neural networks can achieve this sample complexity. Inspired by prior techniques such as label transformation and landscape smoothing for learning single-index models, we propose a unified gradient-based algorithm for training a two-layer neural network in polynomial time. Our method is adaptable to a variety of loss and activation functions, covering a broad class of existing approaches. We show that our algorithm learns a feature representation that strongly aligns with the unknown signal $θ^\star$, with sample complexity $\widetilde{O} (d^{s^\star/2} \lor d)$, matching the SQ lower bound up to a polylogarithmic factor for all generative exponents $s^\star\geq 1$. Furthermore, we extend our approach to the setting where $θ^\star$ is $k$-sparse for $k = o(\sqrt{d})$ by introducing a novel weight perturbation technique that leverages the sparsity structure. We derive a corresponding SQ lower bound of order $\widetildeΩ(k^{s^\star})$, matched by our method up to a polylogarithmic factor. Our framework, especially the weight perturbation technique, is of independent interest, and suggests potential gradient-based solutions to other problems such as sparse tensor PCA.
• Abstract（参考訳）: 勾配に基づく手法で訓練されたニューラルネットワークは、ガウスの単一インデックスモデルを学ぶ際に最適な計算統計的トレードオフを達成することができるか? 従来の研究では、統計的クエリー(SQ)フレームワークの多項式時間アルゴリズムには$Ω(d^{s^\star/2}\lor d)$サンプルが必要であることが示されている。 しかし、ニューラルネットワークがこのサンプルの複雑さを達成できるかどうかは不明だ。 単一インデックスモデル学習のためのラベル変換やランドスケープスムーシングといった先行技術に着想を得て, 2層ニューラルネットワークを多項式時間でトレーニングするための統一的勾配に基づくアルゴリズムを提案する。 提案手法は,多様な損失・アクティベーション機能に適応し,既存手法の幅広いクラスをカバーする。 我々のアルゴリズムは未知の信号である$θ^\star$と強い整合性を持つ特徴表現を、サンプル複雑性$\widetilde{O} (d^{s^\star/2} \lor d)$で学習し、SQの下限を全ての生成指数$s^\star\geq 1$に対してポリ対数係数に一致することを示す。 さらに、このアプローチを$θ^\star$が$k = o(\sqrt{d})$に対して$k$-sparseとなるような設定にまで拡張し、空間構造を利用する新しい重み摂動手法を導入する。 対応する SQ 下界の次数 $\widetildeΩ(k^{s^\star})$ を導出する。 我々のフレームワーク、特に重み摂動技術は独立して興味を持ち、スパーステンソルPCAのような他の問題に対する潜在的な勾配に基づく解を提案する。

関連論文リスト

• Gradient Descent with Projection Finds Over-Parameterized Neural Networks for Learning Low-Degree Polynomials with Nearly Minimax Optimal Rate [15.975065054204753]
  本稿では、真次を識別し、ほぼ最適な回帰率を達成する新しい適応度選択アルゴリズムを提案する。 我々の結果は、通常のニューラル・タンジェント・カーネル(NTK)限界を超えています。
  論文  参考訳（メタデータ） (2026-03-22T05:06:17Z)
• Neural Networks Learn Generic Multi-Index Models Near Information-Theoretic Limit [66.20349460098275]
  一般ガウス多次元モデル $f(boldsymbolx)=g(boldsymbolUboldsymbolx)$ の勾配降下学習を隠蔽部分空間 $boldsymbolUin mathbbRrtimes d$ で研究する。 リンク関数上の一般的な非退化仮定の下では、層次勾配勾配勾配によって訓練された標準的な2層ニューラルネットワークは、$o_d(1)$テスト誤差でターゲットを不可知的に学習できることを示す。
  論文  参考訳（メタデータ） (2025-11-19T04:46:47Z)
• Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations [40.77319247558742]
  目的関数 $f_*:mathbbRdtomathbbR$ を加法構造で学習する際の計算複雑性について検討する。 2層ニューラルネットワークの勾配学習により,$f_*$の大規模なサブセットを効率的に学習できることを実証した。
  論文  参考訳（メタデータ） (2024-06-17T17:59:17Z)
• Pruning is Optimal for Learning Sparse Features in High-Dimensions [15.967123173054535]
  本研究では,勾配勾配勾配で学習したプルーンドニューラルネットワークを用いて,統計モデルのクラスを最適に学習可能であることを示す。 ニューラルネットワークのプルーニングが$boldsymbolV$のスパーシリティレベルに比例すると、未切断ネットワークと比較してサンプルの複雑さが向上することを示す。
  論文  参考訳（メタデータ） (2024-06-12T21:43:12Z)
• Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
  我々は、2層完全連結ニューラルネットワーク上での符号勾配降下(SGD)による$k$スパースパリティ問題を解く。 このアプローチは、$d$次元ハイパーキューブ上での$k$スパースパリティ問題を効率的に解くことができることを示す。 次に、符号SGDを持つトレーニングニューラルネットワークが、この優れたネットワークを効果的に近似し、小さな統計的誤差で$k$-parity問題を解く方法を示す。
  論文  参考訳（メタデータ） (2024-04-18T17:57:53Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learning [66.05472746340142]
  本稿では,SGD による階層的学習 _efficiently_ と _automatically_ を学習目標として,多層ニューラルネットワークがどのように行うかを分析する。 我々は、下位機能のエラーを上位層と共にトレーニングする際に自動的に修正できる"後方特徴補正"と呼ばれる新しい原則を確立する。
  論文  参考訳（メタデータ） (2020-01-13T17:28:29Z)

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

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