論文の概要: Armijo Line-search Makes (Stochastic) Gradient Descent Go Fast

• arxiv url: http://arxiv.org/abs/2503.00229v1
• Date: Fri, 28 Feb 2025 22:26:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:22:02.470703
• Title: Armijo Line-search Makes (Stochastic) Gradient Descent Go Fast
• Title（参考訳）: Armijoのライン検索は、(確率的に)グラディエントな輝きを速くする
• Authors: Sharan Vaswani, Reza Babanezhad,
• Abstract要約: アルミホ線探索凸(Armijo-LS)は勾配降下(GD)のステップサイズを設定する標準的な方法である 一定の非一様条件の場合、GD-LS は GD よりも安定に収束し、ステップサイズは 1/L である。
• 参考スコア（独自算出の注目度）: 7.974134340935598
• License:
• Abstract: Armijo line-search (Armijo-LS) is a standard method to set the step-size for gradient descent (GD). For smooth functions, Armijo-LS alleviates the need to know the global smoothness constant $L$ and adapts to the local smoothness, enabling GD to converge faster. However, existing theoretical analyses of GD with Armijo-LS (GD-LS) do not characterize this fast convergence. We show that if the objective function satisfies a certain non-uniform smoothness condition, GD-LS converges provably faster than GD with a constant $1/L$ step-size (denoted as GD(1/L)). Our results imply that for convex losses corresponding to logistic regression and multi-class classification, GD-LS can converge to the optimum at a linear rate and, hence, improve over the sublinear convergence of GD(1/L). Furthermore, for non-convex losses satisfying gradient domination (for example, those corresponding to the softmax policy gradient in RL or generalized linear models with a logistic link function), GD-LS can match the fast convergence of algorithms tailored for these specific settings. Finally, we prove that under the interpolation assumption, for convex losses, stochastic GD with a stochastic line-search can match the fast convergence of GD-LS.
• Abstract（参考訳）: アルミホ線探索(アルミホ線探索、Armijo line-search)は、勾配降下(GD)のステップサイズを設定する標準的な方法である。 滑らかな函数に対して、Armijo-LS は大域的滑らかさ定数 $L$ を知る必要性を緩和し、局所滑らかさに適応し、GD をより早く収束させることができる。 しかし、既存のArmijo-LS (GD-LS) によるGDの理論解析では、この高速収束は特徴づけられていない。 目的関数がある非一様滑らか性条件を満たす場合、GD-LS は GD よりも確率的に速く収束し、ステップサイズが定数 1/L$(GD(1/L) と記述される)。 その結果, 対数回帰と多クラス分類に対応する凸損失に対して, GD-LS は線形速度で最適値に収束し, GD(1/L) のサブ線形収束性を改善することができることがわかった。 さらに、勾配支配を満たす非凸損失(例えば、RLのソフトマックスポリシー勾配に対応するものや、ロジスティックリンク関数を持つ一般化線形モデルに対応するもの)に対しては、GD-LSはこれらの特定の設定に適したアルゴリズムの高速収束と一致する。 最後に、補間仮定の下で、凸損失に対して、確率的直線探索を伴う確率的GDがGD-LSの高速収束と一致することを証明した。

関連論文リスト

• Langevin Dynamics: A Unified Perspective on Optimization via Lyapunov Potentials [15.718093624695552]
  我々は、リアプノフポテンシャルと最適化に基づいて、グラディエント・ランゲヴィン・ダイナミクス(SGLD)のグローバル・ミニマへの収束を分析する。 2) SGLD に対する最初の有限勾配複雑性、3) 連続時間ランゲヴィンダイナミクスが最適化に成功するなら、次に離散時間 SGLD が穏やかな正則性仮定の下で成功することを証明する。
  論文  参考訳（メタデータ） (2024-07-05T05:34:10Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descent [50.4531316289086]
  SGD(Gradient Descent)は、大規模非ルートモデルの学習方法である。 集団損失のGFが収束すると仮定して、総合的な条件 SGD が収束する。 我々は、凸損失のような古典的な設定だけでなく、Retrieval Matrix sq-rootのようなより複雑な問題に対してもGD/SGDを統一的に解析する。
  論文  参考訳（メタデータ） (2022-10-13T03:55:04Z)
• SGDA with shuffling: faster convergence for nonconvex-P{\L} minimax optimization [18.668531108219415]
  逐次降下勾配(SGDA)を用いた最小最適化問題に対する理論的アプローチを提案する。 我々は,ポリアック・ロジャシエヴィチ(PL)幾何を用いて,非凹凸対象に対するSGDA-LLの同時的および交互的目的を解析した。 我々のレートはミニバッチGDARRにも拡張され、完全な勾配勾配降下勾配 (GDA) の既知率はほとんど回復しない。 最後に, 2 時間スケール GDA の包括的下限について述べる。
  論文  参考訳（メタデータ） (2022-10-12T08:05:41Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。 ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。 我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
  論文  参考訳（メタデータ） (2021-10-20T02:25:25Z)
• Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
  目的関数の非一様洗練は、emphNon-uniform Smoothness(NS)とemphNon-uniform Lojasiewicz inequality(NL)につながる 新しい定義は、古典的な$Omega (1/t2)$下界よりも早く大域的最適性に収束する新しい幾何学的一階法を刺激する。
  論文  参考訳（メタデータ） (2021-05-13T04:23:07Z)
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms [65.09383385484007]
  2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。 本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
  論文  参考訳（メタデータ） (2020-11-10T11:36:30Z)
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
  我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。 我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
  論文  参考訳（メタデータ） (2020-10-19T15:23:18Z)
• An improved convergence analysis for decentralized online stochastic non-convex optimization [17.386715847732468]
  本稿では,GT-Loakjasiewics(GT-Loakjasiewics)と呼ばれる手法が,GT-Loakjasiewics(GT-Loakjasiewics)が現在の収束率を満たすことを示す。 結果はすぐに適用できるだけでなく、現在知られている最高の収束率にも適用できる。
  論文  参考訳（メタデータ） (2020-08-10T15:29:13Z)
• Replica Exchange for Non-Convex Optimization [4.421561004829125]
  勾配降下(GD)は凸目的関数に対して急速に収束することが知られているが、局所的なミニマに閉じ込められることがある。 ランゲヴィン力学(LD)は状態空間を探索し、大域的な最小値を見つけることができるが、正確な推定を得るためには、LDは小さな離散化ステップサイズで実行し、弱い力を検証する必要がある。 本稿では,これら2つのアルゴリズムとその非スワッピング変種が,単純な交換機構によって協調可能であることを示す。
  論文  参考訳（メタデータ） (2020-01-23T03:13:19Z)
• Dual Stochastic Natural Gradient Descent and convergence of interior half-space gradient approximations [0.0]
  多項ロジスティック回帰(MLR)は統計学や機械学習で広く使われている。 勾配降下(SGD)は、ビッグデータシナリオにおけるMLRモデルのパラメータを決定する最も一般的な手法である。
  論文  参考訳（メタデータ） (2020-01-19T00:53:49Z)

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

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