論文の概要: SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics

• arxiv url: http://arxiv.org/abs/2302.11055v2
• Date: Thu, 31 Aug 2023 21:09:03 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-04 17:11:50.722456
• Title: SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics
• Title（参考訳）: ニューラルネットワークにおけるsgd学習--跳躍複雑性とサドル・トゥ・サドルダイナミクス
• Authors: Emmanuel Abbe, Enric Boix-Adsera, Theodor Misiakiewicz
• Abstract要約: 等方性データを用いた完全連結ニューラルネットワークにおけるSGD学習の時間的複雑さについて検討する。 我々は、"階層的"なターゲット関数がどのようにあるかを測定する複雑さの尺度(跳躍)を提唱した。 トレーニングは,サドル・トゥ・サドル・ダイナミックで関数サポートを逐次学習することを示す。
• 参考スコア（独自算出の注目度）: 22.365592070563764
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the time complexity of SGD learning on fully-connected neural networks with isotropic data. We put forward a complexity measure -- the leap -- which measures how "hierarchical" target functions are. For $d$-dimensional uniform Boolean or isotropic Gaussian data, our main conjecture states that the time complexity to learn a function $f$ with low-dimensional support is $\tilde\Theta (d^{\max(\mathrm{Leap}(f),2)})$. We prove a version of this conjecture for a class of functions on Gaussian isotropic data and 2-layer neural networks, under additional technical assumptions on how SGD is run. We show that the training sequentially learns the function support with a saddle-to-saddle dynamic. Our result departs from [Abbe et al. 2022] by going beyond leap 1 (merged-staircase functions), and by going beyond the mean-field and gradient flow approximations that prohibit the full complexity control obtained here. Finally, we note that this gives an SGD complexity for the full training trajectory that matches that of Correlational Statistical Query (CSQ) lower-bounds.
• Abstract（参考訳）: 等方性データを用いた完全連結ニューラルネットワークにおけるSGD学習の時間的複雑さについて検討する。 目標関数がいかに"階層的"であるかを測定する、複雑性尺度 -- the leap -- を提案しました。 d$-dimensional uniform boolean あるいは isotropic gaussian data に対し、我々の主予想では、低次元サポートを持つ関数を学習する時間複雑性は $\tilde\theta (d^{\max(\mathrm{leap}(f),2)} である。 ガウス等方性データと2層ニューラルネットワーク上の関数のクラスに対するこの予想を、SGDの動作に関する追加の技術的仮定の下で証明する。 トレーニングでは,サドル・トゥ・サドル・ダイナミックで関数サポートを逐次学習する。 以上の結果から,[Abbe et al. 2022] は跳躍 1 (メルジ階段関数) を超越し,また,ここで得られる複雑性の完全な制御を禁止した平均場および勾配流近似を超越した。 最後に、これは相関統計クエリ(CSQ)の下位バウンドと一致する完全なトレーニングトラジェクトリに対して、SGDの複雑さをもたらすことに留意する。

関連論文リスト

• Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics [21.55547541297847]
  平均場ランゲヴィンアルゴリズムを用いて学習した2層ニューラルネットワークを用いて,高次元のマルチインデックスモデルを学習する問題について検討する。 軽度の分布仮定の下では、サンプルと計算の複雑さの両方を制御する実効次元 $d_mathrmeff$ を特徴づける。
  論文  参考訳（メタデータ） (2024-08-14T02:13:35Z)
• Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
  勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。 次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
  論文  参考訳（メタデータ） (2024-04-18T17:57:53Z)
• Sliding down the stairs: how correlated latent variables accelerate learning with neural networks [8.107431208836426]
  入力累積に符号化された方向に沿った潜伏変数間の相関が高次相関から学習を高速化することを示す。 この結果は2層ニューラルネットワークのシミュレーションで確認された。
  論文  参考訳（メタデータ） (2024-04-12T17:01:25Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem [1.3597551064547502]
  本研究では,2層ニューラルネットワーク上でのミニバッチ降下勾配(SGD)の最適化過程について考察する。 二次 XOR' 関数 $y = -x_ix_j$ でラベル付けされた $d$-dimensional Boolean hypercube から得られるデータから、人口誤差 $o(1)$ と $d :textpolylog(d)$ のサンプルをトレーニングすることが可能であることを証明した。
  論文  参考訳（メタデータ） (2023-09-26T17:57:44Z)
• The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks [19.899987851661354]
  我々は,SGD-Lrnability with $O(d)$ sample complexity in a large ambient dimension。 本研究の主な成果は, 階層的特性である「マージ階段特性」を特徴付けるものである。 鍵となるツールは、潜在低次元部分空間上で定義される函数に適用される新しい「次元自由」力学近似である。
  論文  参考訳（メタデータ） (2022-02-17T13:43:06Z)
• Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning [59.71676469100807]
  この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。 計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
  論文  参考訳（メタデータ） (2021-02-12T14:22:05Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Measuring Model Complexity of Neural Networks with Curve Activation Functions [100.98319505253797]
  本稿では,線形近似ニューラルネットワーク(LANN)を提案する。 ニューラルネットワークのトレーニングプロセスを実験的に検討し、オーバーフィッティングを検出する。 我々は、$L1$と$L2$正規化がモデルの複雑さの増加を抑制することを発見した。
  論文  参考訳（メタデータ） (2020-06-16T07:38:06Z)
• Convolutional Tensor-Train LSTM for Spatio-temporal Learning [116.24172387469994]
  本稿では,ビデオシーケンスの長期相関を効率的に学習できる高次LSTMモデルを提案する。 これは、時間をかけて畳み込み特徴を組み合わせることによって予測を行う、新しいテンソルトレインモジュールによって達成される。 この結果は,幅広いアプリケーションやデータセットにおいて,最先端のパフォーマンス向上を実現している。
  論文  参考訳（メタデータ） (2020-02-21T05:00:01Z)

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

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