論文の概要: On Tight Convergence Rates of Without-replacement SGD

• arxiv url: http://arxiv.org/abs/2004.08657v1
• Date: Sat, 18 Apr 2020 16:14:11 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-12 05:51:11.592678
• Title: On Tight Convergence Rates of Without-replacement SGD
• Title（参考訳）: 無置換SGDのタイト収束速度について
• Authors: Kwangjun Ahn and Suvrit Sra
• Abstract要約: 有限サム最適化問題を解くために、置換サンプリングのないSGDは、SGDより優れていることを実証的に示している。 本研究では, 時代によって異なるステップサイズを解析することによって, これらの制約を克服する。
• 参考スコア（独自算出の注目度）: 52.99237600875452
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: For solving finite-sum optimization problems, SGD without replacement sampling is empirically shown to outperform SGD. Denoting by $n$ the number of components in the cost and $K$ the number of epochs of the algorithm , several recent works have shown convergence rates of without-replacement SGD that have better dependency on $n$ and $K$ than the baseline rate of $O(1/(nK))$ for SGD. However, there are two main limitations shared among those works: the rates have extra poly-logarithmic factors on $nK$, and denoting by $\kappa$ the condition number of the problem, the rates hold after $\kappa^c\log(nK)$ epochs for some $c>0$. In this work, we overcome these limitations by analyzing step sizes that vary across epochs.
• Abstract（参考訳）: 有限サム最適化問題の解法として, 置換サンプリングのないSGDがSGDより優れていることを示す。 コストの成分数$n$とアルゴリズムのエポック数$K$を示す最近のいくつかの研究は、SGDのベースラインレート$O(1/(nK))$よりも$n$と$K$への依存性が優れている無置換SGDの収束率を示している。 しかし、これらの作品には2つの主要な制限がある: レートは$nK$に余分な多変数因子を持ち、問題の条件番号は$\kappa$であり、ある$c>0$に対して$\kappa^c\log(nK)$ epochsである。 本研究では,時代によって異なるステップサイズを分析することで,これらの制限を克服する。

関連論文リスト

• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• Demystifying the Myths and Legends of Nonconvex Convergence of SGD [17.445810977264067]
  勾配勾配勾配(SGD)とその変種は、大規模最適化問題の解法の主要な仕事場である。 分析として,勾配の非収束に関連する神話や伝説について考察した。
  論文  参考訳（メタデータ） (2023-10-19T17:58:59Z)
• Convergence Analysis of Decentralized ASGD [1.8710230264817358]
  本稿では,ノード間の部分同期や制限的ネットワークトポロジを必要としない分散非同期SGD(DASGD)に対する新しい収束速度解析法を提案する。 我々の収束証明は、固定段数と任意の非滑らかで同質でL字型の目的函数を仮定する。
  論文  参考訳（メタデータ） (2023-09-07T14:50:31Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
  論文  参考訳（メタデータ） (2022-06-16T17:10:57Z)
• Faster Convergence of Local SGD for Over-Parameterized Models [1.5504102675587357]
  現代の機械学習アーキテクチャは、しばしば非常に表現力が高い。 不均一なデータ設定における過パラメータ化関数に対する局所SGD(またはFedAvg)の収束を解析する。 一般凸損失関数に対しては、$O(K/T)$の誤差が成立する。 非剰余関数に対しては、どちらの場合も$O(K/T)$の誤差が証明される。 確立された収束率を、合理的に小さなステップサイズで一定の要因に密着した問題インスタンスを提供することで、結果を完成させる。
  論文  参考訳（メタデータ） (2022-01-30T04:05:56Z)
• Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent [7.176107039687231]
  雑音に対して勾配降下(SGD)を適応させるステップサイズスキームを設計する。 我々は、Nesterov反復によるSGDの$T$反復がほぼ最適であることを示す。 他のステップサイズスキームと比較して、新しい指数的なステップサイズスキームの有効性を実証する。
  論文  参考訳（メタデータ） (2021-10-21T19:22:14Z)
• SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs [30.41773138781369]
  本稿では,現実に一般的に用いられているグラディエント・ディファイス(SGD)のマルチエポックな変種について述べる。 最悪の場合、これはシングルパスSGDと同程度であることを示す。 SCOの特定の問題に対して、データセットに複数のパスを取ることは、シングルパスSGDを著しく上回る。
  論文  参考訳（メタデータ） (2021-07-11T15:50:01Z)
• Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems [55.40911408462676]
  その結果,非置換型SGDエンファンドは最悪のケース境界において,非置換型SGDに対して顕著な改善は得られなかった。 機械学習や他の分野の多くの問題は条件が不適切であり、大きなデータセットが関与しているため、非置換が現実的な予算のための非置換サンプリングよりも必ずしも改善しないことを示している。
  論文  参考訳（メタデータ） (2021-06-12T23:07:27Z)
• Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
  無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。 最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
  論文  参考訳（メタデータ） (2021-01-31T16:17:56Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)

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

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