論文の概要: Fundamental computational limits of weak learnability in high-dimensional multi-index models

• arxiv url: http://arxiv.org/abs/2405.15480v3
• Date: Thu, 24 Oct 2024 11:58:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-25 12:48:33.251721
• Title: Fundamental computational limits of weak learnability in high-dimensional multi-index models
• Title（参考訳）: 高次元マルチインデックスモデルにおける弱学習可能性の基本計算限界
• Authors: Emanuele Troiani, Yatin Dandi, Leonardo Defilippis, Lenka Zdeborová, Bruno Loureiro, Florent Krzakala,
• Abstract要約: 本稿では, 1次反復アルゴリズムを用いて低次元構造を弱めに復元するために必要な最小サンプル複雑性に着目した。 i) 自明な部分空間が任意の$alpha!>!0$; (ii) 自明な部分空間が空であれば、簡単な部分空間の存在に必要な必要十分条件を提供する。 限定的だが興味深い厳密な方向の集合において、-パリティ問題に似て-$alpha_c$が見つかる
• 参考スコア（独自算出の注目度）: 30.501140910531017
• License:
• Abstract: Multi-index models - functions which only depend on the covariates through a non-linear transformation of their projection on a subspace - are a useful benchmark for investigating feature learning with neural nets. This paper examines the theoretical boundaries of efficient learnability in this hypothesis class, focusing on the minimum sample complexity required for weakly recovering their low-dimensional structure with first-order iterative algorithms, in the high-dimensional regime where the number of samples $n\!=\!\alpha d$ is proportional to the covariate dimension $d$. Our findings unfold in three parts: (i) we identify under which conditions a trivial subspace can be learned with a single step of a first-order algorithm for any $\alpha\!>\!0$; (ii) if the trivial subspace is empty, we provide necessary and sufficient conditions for the existence of an easy subspace where directions that can be learned only above a certain sample complexity $\alpha\!>\!\alpha_c$, where $\alpha_{c}$ marks a computational phase transition. In a limited but interesting set of really hard directions -- akin to the parity problem -- $\alpha_c$ is found to diverge. Finally, (iii) we show that interactions between different directions can result in an intricate hierarchical learning phenomenon, where directions can be learned sequentially when coupled to easier ones. We discuss in detail the grand staircase picture associated to these functions (and contrast it with the original staircase one). Our theory builds on the optimality of approximate message-passing among first-order iterative methods, delineating the fundamental learnability limit across a broad spectrum of algorithms, including neural networks trained with gradient descent, which we discuss in this context.
• Abstract（参考訳）: マルチインデックスモデル — サブスペース上のプロジェクションの非線形変換を通じて共変量のみに依存する関数 — は、ニューラルネットによる特徴学習を研究する上で有用なベンチマークである。 本稿では, 1次反復アルゴリズムを用いて低次元構造を弱めに復元するために必要な最小限のサンプル複雑性を, サンプル数$n\!の高次元状態において, 仮説クラスにおける効率的な学習可能性の理論的境界について検討する。 =\! \alpha d$ は共変次元 $d$ に比例する。 私たちの発見は3つの部分に分かれています。 i) 自明な部分空間が任意の$\alpha\! >\! 0$。 (ii) 自明な部分空間が空であれば、あるサンプル複雑性より上だけに学習できる方向を$\alpha\! >\! \alpha_c$, $\alpha_{c}$は計算相転移を示す。 限定的だが興味深い厳密な方向のセット -- パリティ問題と同様 -- において、$\alpha_c$ は発散する。 最後に 3) 異なる方向の相互作用が複雑な階層的学習現象を引き起こし, より容易な方向と組み合わせることで, 順次学習できることを示す。 これらの機能に関連する大階段図について詳しく論じる(原階段図と対比する)。 我々の理論は、一階反復法における近似メッセージパッシングの最適性に基づいており、勾配降下法で訓練されたニューラルネットワークを含む幅広いアルゴリズムにおいて、基本的な学習可能性限界を記述し、この文脈で論じる。

関連論文リスト

• Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics [21.55547541297847]
  平均場ランゲヴィンアルゴリズムを用いて学習した2層ニューラルネットワークを用いて,高次元のマルチインデックスモデルを学習する問題について検討する。 軽度の分布仮定の下では、サンプルと計算の複雑さの両方を制御する実効次元 $d_mathrmeff$ を特徴づける。
  論文  参考訳（メタデータ） (2024-08-14T02:13:35Z)
• Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension [17.485243410774814]
  教師付き学習の伝統的なモデルでは、学習者の目標は、あるクラスから最も適した概念の競争的($epsilon$以内)な仮説を出力することである。 学習者が最高の無知としか競合しないスムーズな分析フレームワークを導入する。 時間内に$k$-halfspacesの交点を前向きに学習する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-07-01T04:58:36Z)
• Stochastic Nested Compositional Bi-level Optimization for Robust Feature Learning [11.236838268731804]
  ネストされた二段階最適化問題を解くアルゴリズムを開発し,解析する。 提案アルゴリズムは,行列複雑性やミニバッチに依存しない。
  論文  参考訳（メタデータ） (2023-07-11T15:52:04Z)
• Nonsmooth automatic differentiation: a cheap gradient principle and other complexity results [0.0]
  我々は,多種多様な非滑らかなプログラムに対して,アルゴリズム微分の後方モードと前方モードの計算コストを推定するモデルを提供する。 有名な例として、有名なreluと畳み込みニューラルネットワークとその標準損失関数がある。
  論文  参考訳（メタデータ） (2022-06-01T08:43:35Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  単純複体は多方向順序関係を明示的にエンコードするグラフの高次元一般化と見なすことができる。 単体錯体の$k$-homological特徴によってパラメータ化された関数のグラフ畳み込みモデルを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:59:41Z)
• Deep Magnification-Flexible Upsampling over 3D Point Clouds [103.09504572409449]
  本稿では,高密度点雲を生成するためのエンドツーエンド学習ベースのフレームワークを提案する。 まずこの問題を明示的に定式化し、重みと高次近似誤差を判定する。 そこで我々は,高次改良とともに,統一重みとソート重みを適応的に学習する軽量ニューラルネットワークを設計する。
  論文  参考訳（メタデータ） (2020-11-25T14:00:18Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Deep neural networks for inverse problems with pseudodifferential operators: an application to limited-angle tomography [0.4110409960377149]
  線形逆問題において擬微分演算子(Psi$DOs)を学習するための新しい畳み込みニューラルネットワーク(CNN)を提案する。 フォワード演算子のより一般的な仮定の下では、ISTAの展開された反復はCNNの逐次的な層として解釈できることを示す。 特に、LA-CTの場合、アップスケーリング、ダウンスケーリング、畳み込みの操作は、制限角X線変換の畳み込み特性とウェーブレット系を定義する基本特性を組み合わせることで正確に決定できることを示す。
  論文  参考訳（メタデータ） (2020-06-02T14:03:41Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)
• Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learning [66.05472746340142]
  本稿では,SGD による階層的学習 _efficiently_ と _automatically_ を学習目標として,多層ニューラルネットワークがどのように行うかを分析する。 我々は、下位機能のエラーを上位層と共にトレーニングする際に自動的に修正できる"後方特徴補正"と呼ばれる新しい原則を確立する。
  論文  参考訳（メタデータ） (2020-01-13T17:28:29Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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