論文の概要: Glocal Smoothness: Line Search can really help!

• arxiv url: http://arxiv.org/abs/2506.12648v1
• Date: Sat, 14 Jun 2025 22:18:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-17 17:28:46.604183
• Title: Glocal Smoothness: Line Search can really help!
• Title（参考訳）: Glocal Smoothness: ライン検索は本当に役に立ちます!
• Authors: Curtis Fox, Aaron Mishkin, Sharan Vaswani, Mark Schmidt,
• Abstract要約: 一階最適化アルゴリズムの反復複雑性は、一般に勾配の大域リプシッツ定数の項で記述される。 実際に発生する多くの客観的関数は、より大きなステップサイズを使うことができる小さなリプシッツ定数を持つ領域を持つ。 局所的な滑らかさはPolyakとAdGDのステップサイズの改善に繋がることを示した。
• 参考スコア（独自算出の注目度）: 13.442002218246037
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Iteration complexities for first-order optimization algorithms are typically stated in terms of a global Lipschitz constant of the gradient, and near-optimal results are achieved using fixed step sizes. But many objective functions that arise in practice have regions with small Lipschitz constants where larger step sizes can be used. Many local Lipschitz assumptions have been proposed, which have lead to results showing that adaptive step sizes and/or line searches yield improved convergence rates over fixed step sizes. However, these faster rates tend to depend on the iterates of the algorithm, which makes it difficult to compare the iteration complexities of different methods. We consider a simple characterization of global and local ("glocal") smoothness that only depends on properties of the function. This allows upper bounds on iteration complexities in terms of iterate-independent constants and enables us to compare iteration complexities between algorithms. Under this assumption it is straightforward to show the advantages of line searches over fixed step sizes, and that in some settings, gradient descent with line search has a better iteration complexity than accelerated methods with fixed step sizes. We further show that glocal smoothness can lead to improved complexities for the Polyak and AdGD step sizes, as well other algorithms including coordinate optimization, stochastic gradient methods, accelerated gradient methods, and non-linear conjugate gradient methods.
• Abstract（参考訳）: 一階最適化アルゴリズムの反復複雑性は、一般に勾配のグローバルリプシッツ定数の項で記述され、固定ステップサイズを用いてほぼ最適結果が得られる。 しかし、実際には多くの目的関数が小さなリプシッツ定数を持つ領域を持ち、より大きなステップサイズを使うことができる。 多くの局所的なリプシッツ仮定が提案され、これは適応的なステップサイズと/またはライン探索が固定されたステップサイズよりも収束率を向上させることを示す結果となった。 しかし、これらの高速な速度はアルゴリズムの繰り返しに依存する傾向にあり、異なる手法の反復複雑さを比較することは困難である。 関数の性質にのみ依存する大域的および局所的(局所的な)滑らかさの簡易な特徴づけを考える。 これにより、反復複雑性のイテレート非依存定数の上限が得られ、アルゴリズム間で反復複雑性を比較することができる。 この仮定の下では、固定ステップサイズよりもライン探索の利点を示すことは簡単であり、いくつかの設定では、ライン探索による勾配勾配は、固定ステップサイズを持つアクセラレーションされたメソッドよりも、イテレーションの複雑さが優れている。 さらに、局所的な滑らかさは、PolyakとAdGDのステップサイズ、および座標最適化、確率勾配法、加速度勾配法、非線形共役勾配法を含む他のアルゴリズムの複雑さの向上につながることを示した。

関連論文リスト

• Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective [17.5796206457693]
  局所的な局所次変分の下での非滑らかな最適化問題について検討する。 得られた目的のクラスは、定義されたクラスに基づいて目的のクラスをカプセル化する。
  論文  参考訳（メタデータ） (2024-03-24T22:42:40Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothness [0.0]
  非常に多くのスムーズで可能な非サイズの関数の平均を考慮し、この問題に対処するために2つの広く最小限のフレームワークを使用します。 IG/RRスキームの簡易制御による修正を定義する。 我々は、完全なバッチ勾配(L-BFGS)とIG/RR手法の実装の両方で実装を証明し、アルゴリズムが同様の計算作業を必要とすることを証明した。
  論文  参考訳（メタデータ） (2022-12-04T15:26:36Z)
• Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales [45.994415581007054]
  関数 $f : mathbbRd rightarrow mathbbR$ の最小化は、未知の非相互作用な滑らかで凸な函数の和として暗黙的に分解可能である。 そこで我々は,多種多様な条件の最適化問題を効率的に解くために,勾配に基づく新しい手法を提案する。
  論文  参考訳（メタデータ） (2021-11-04T20:09:12Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Functions with average smoothness: structure, algorithms, and learning [12.362670630646804]
  各点における局所勾配を定義し、これらの値の平均として関数複雑性を測る。 平均は最大よりも劇的に小さくなるので、この複雑性測度はよりシャープな一般化境界が得られる。 私たちは定義した関数クラスにおいて驚くほどリッチで解析的な構造を発見します。
  論文  参考訳（メタデータ） (2020-07-13T10:06:58Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)

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

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