論文の概要: Fundamental limits of weak learnability in high-dimensional multi-index models
- arxiv url: http://arxiv.org/abs/2405.15480v1
- Date: Fri, 24 May 2024 11:59:02 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-27 14:32:33.213963
- Title: Fundamental 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次反復アルゴリズムを用いて低次元構造を弱めに復元するために必要な最小サンプル複雑性に着目した。
- 参考スコア（独自算出の注目度）: 30.501140910531017
- License: http://creativecommons.org/licenses/by/4.0/
- 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 networks. This paper examines the theoretical boundaries of learnability in this hypothesis class, focusing particularly 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 is $n=\alpha d$ is proportional to the covariate dimension $d$. Our findings unfold in three parts: (i) first, we identify under which conditions a \textit{trivial subspace} can be learned with a single step of a first-order algorithm for any $\alpha\!>\!0$; (ii) second, in the case where the trivial subspace is empty, we provide necessary and sufficient conditions for the existence of an {\it easy subspace} consisting of directions that can be learned only above a certain sample complexity $\alpha\!>\!\alpha_c$. The critical threshold $\alpha_{c}$ marks the presence of a computational phase transition, in the sense that no efficient iterative algorithm can succeed for $\alpha\!<\!\alpha_c$. In a limited but interesting set of really hard directions -- akin to the parity problem -- $\alpha_c$ is found to diverge. Finally, (iii) we demonstrate that interactions between different directions can result in an intricate hierarchical learning phenomenon, where some directions can be learned sequentially when coupled to easier ones. Our analytical approach is built on the optimality of approximate message-passing algorithms among first-order iterative methods, delineating the fundamental learnability limit across a broad spectrum of algorithms, including neural networks trained with gradient descent.
- Abstract（参考訳）: マルチインデックスモデル -- サブスペース上のプロジェクションの非線形変換による共変量のみに依存する関数 -- は、ニューラルネットワークによる特徴学習を研究する上で有用なベンチマークである。
本稿では,1次反復アルゴリズムを用いて低次元構造を弱復元するのに必要となる最小限のサンプル複雑性に着目し,この仮説クラスにおける学習可能性の理論的境界について検討する。
私たちの発見は3つの部分に分かれています。
(i)まず、任意の$\alpha\!に対して一階アルゴリズムの単一ステップで \textit{trivial subspace} を学習できる条件を識別する。
>\!
0$。
第二に、自明な部分空間が空である場合には、あるサンプル複雑性$\alpha\!
>\!
alpha_c$。
臨界しきい値$\alpha_{c}$は、効率的な反復アルゴリズムが$\alpha\!
<\!
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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。