論文の概要: The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimization

• arxiv url: http://arxiv.org/abs/2409.09745v1
• Date: Sun, 15 Sep 2024 14:20:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-17 17:40:52.687114
• Title: The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimization
• Title（参考訳）: 高次元二次最適化のための(加速)SGDの最適性
• Authors: Haihan Zhang, Yuanshi Liu, Qianwen Chen, Cong Fang,
• Abstract要約: 勾配降下(SGD)は機械学習、特にニューラルネットワークトレーニングにおいて広く使われているアルゴリズムである。 正準2次最適化や線形回帰のSGDに関する最近の研究は、適切な高次元設定で十分に一般化できることを示している。 本稿では,ステップサイズスケジュールと運動量指数の2つの基本成分を持つSGDについて検討する。
• 参考スコア（独自算出の注目度）: 4.7256945641654164
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic gradient descent (SGD) is a widely used algorithm in machine learning, particularly for neural network training. Recent studies on SGD for canonical quadratic optimization or linear regression show it attains well generalization under suitable high-dimensional settings. However, a fundamental question -- for what kinds of high-dimensional learning problems SGD and its accelerated variants can achieve optimality has yet to be well studied. This paper investigates SGD with two essential components in practice: exponentially decaying step size schedule and momentum. We establish the convergence upper bound for momentum accelerated SGD (ASGD) and propose concrete classes of learning problems under which SGD or ASGD achieves min-max optimal convergence rates. The characterization of the target function is based on standard power-law decays in (functional) linear regression. Our results unveil new insights for understanding the learning bias of SGD: (i) SGD is efficient in learning ``dense'' features where the corresponding weights are subject to an infinity norm constraint; (ii) SGD is efficient for easy problem without suffering from the saturation effect; (iii) momentum can accelerate the convergence rate by order when the learning problem is relatively hard. To our knowledge, this is the first work to clearly identify the optimal boundary of SGD versus ASGD for the problem under mild settings.
• Abstract（参考訳）: 確率勾配降下(SGD)は機械学習、特にニューラルネットワークトレーニングにおいて広く使われているアルゴリズムである。 正準2次最適化や線形回帰のSGDに関する最近の研究は、適切な高次元設定で十分に一般化できることを示している。 しかし、高次元学習問題SGDとその加速変種が最適性を達成できるかどうかという根本的な疑問は、まだ十分に研究されていない。 本稿では,ステップサイズスケジュールと運動量指数の2つの基本成分を持つSGDについて検討する。 我々は、運動量加速SGD(ASGD)の収束上限を確立し、SGDまたはASGDがmin-max最適収束率を達成する学習問題の具体的なクラスを提案する。 対象関数のキャラクタリゼーションは、(機能的)線形回帰における標準的なパワーロー崩壊に基づいている。 SGDの学習バイアスを理解するための新たな知見が得られた。 (i)SGDは、対応する重みが無限ノルム制約を受ける「dense」の特徴を学ぶのに効率的である。 (II)SGDは、飽和効果に悩まされることなく、容易な問題に有効である。 三 学習問題が比較的困難である場合には、順に収束率を加速することができる。 我々の知る限り、軽度条件下での問題に対して、SGDとASGDの最適境界を明確に特定する最初の研究である。

関連論文リスト

• Non-convergence to global minimizers in data driven supervised deep learning: Adam and stochastic gradient descent optimization provably fail to converge to global minimizers in the training of deep neural networks with ReLU activation [3.6185342807265415]
  厳密な理論用語でSGD法の成功と限界を説明することは、研究のオープンな問題である。 本研究では,最適化問題の大域的最小化に収束しない確率の高いSGD手法の大規模なクラスについて検証する。 この研究の一般的な非収束結果は、通常のバニラ標準SGD法だけでなく、多くの加速および適応SGD法にも適用される。
  論文  参考訳（メタデータ） (2024-10-14T14:11:37Z)
• A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning [74.80956524812714]
  我々は,現代のディープラーニングにおいて広く普及している一般的なメタ学習問題に対処する。 これらの問題は、しばしばBi-Level Optimizations (BLO)として定式化される。 我々は,与えられたBLO問題を,内部損失関数が滑らかな分布となり,外損失が内部分布に対する期待損失となるようなii最適化に変換することにより,新たな視点を導入する。
  論文  参考訳（メタデータ） (2024-10-14T12:10:06Z)
• Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks [59.142826407441106]
  本稿では,アルゴリズム安定性の概念を活用して,浅層ニューラルネットワーク(SNN)の一般化挙動について検討する。 我々は、SNNを訓練するために勾配降下(GD)と勾配降下(SGD)を考慮する。
  論文  参考訳（メタデータ） (2022-09-19T18:48:00Z)
• Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensions [26.782342518986503]
  勾配降下(SGD)は現代の機械学習の柱であり、様々な問題に対するゴート最適化アルゴリズムとして機能している。 HSGD形式をストリーミングSGDに適合させる方法を示し、ストリーミングSGDと比較してマルチパスSGDの過大なリスクを正確に予測できることを示す。
  論文  参考訳（メタデータ） (2022-06-15T02:32:26Z)
• Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
  本研究では,適切な学習データを得ることで,一般化性能を実現する「従来型」学習ルールとして,勾配降下度(SGD)がどの程度理解されるかを検討する。 類似現象が起こらない近縁な交換SGDを解析し、その集団リスクが実際に最適な速度で収束することを証明する。
  論文  参考訳（メタデータ） (2022-02-27T13:25:01Z)
• Stabilizing Spiking Neuron Training [3.335932527835653]
  スパイキングニューロモルフィックコンピューティングは、人工知能のエネルギー効率を改善するためにバイナリアクティビティを使用する。 与えられたタスクとネットワークに対して最適なSGを決定する方法はまだ不明である。 我々は、SGの減衰、鋭さ、尾の太さを網羅的に調査する必要性を減らすために、どのように使用できるかを示す。
  論文  参考訳（メタデータ） (2022-02-01T09:10:57Z)
• The Benefits of Implicit Regularization from SGD in Least Squares Problems [116.85246178212616]
  勾配降下(SGD)はアルゴリズム正則化効果が強い。 我々は、(正規化されていない)平均SGDで得られる暗黙の正則化とリッジ回帰の明示的な正則化の比較を行う。
  論文  参考訳（メタデータ） (2021-08-10T09:56:47Z)
• Understanding Long Range Memory Effects in Deep Neural Networks [10.616643031188248]
  深層学習において,SGD(textitstochastic gradient descent)が重要である。 本研究では, SGN はガウス的でも安定でもないと主張する。 そこで本研究では,SGDをFBM(textitfractional Brownian Motion)によって駆動されるSDEの離散化と見なすことができる。
  論文  参考訳（メタデータ） (2021-05-05T13:54:26Z)
• Direction Matters: On the Implicit Bias of Stochastic Gradient Descent with Moderate Learning Rate [105.62979485062756]
  本稿では,中等度学習におけるSGDの特定の正規化効果を特徴付けることを試みる。 SGDはデータ行列の大きな固有値方向に沿って収束し、GDは小さな固有値方向に沿って収束することを示す。
  論文  参考訳（メタデータ） (2020-11-04T21:07:52Z)
• Detached Error Feedback for Distributed SGD with Random Sparsification [98.98236187442258]
  コミュニケーションのボトルネックは、大規模なディープラーニングにおいて重要な問題である。 非効率な分散問題に対する誤りフィードバックよりも優れた収束性を示す分散誤差フィードバック(DEF)アルゴリズムを提案する。 また、DEFよりも優れた境界を示すDEFの一般化を加速するDEFAを提案する。
  論文  参考訳（メタデータ） (2020-04-11T03:50:59Z)

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

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