Fugu-MT 論文翻訳(概要): Tight Convergence Rate Bounds for Optimization Under Power Law Spectral Conditions

論文の概要: Tight Convergence Rate Bounds for Optimization Under Power Law Spectral Conditions

arxiv url: http://arxiv.org/abs/2202.00992v3
Date: Mon, 25 Mar 2024 13:31:05 GMT
ステータス: 処理完了
システム内更新日: 2024-03-28 02:19:20.774265
Title: Tight Convergence Rate Bounds for Optimization Under Power Law Spectral Conditions
Title（参考訳）: 電力法スペクトル条件下での最適化のためのタイト収束速度境界
Authors: Maksim Velikanov, Dmitry Yarotsky,
Abstract要約: スペクトルの所定の形状に対して、最適に加速された方法、そのスケジュール、収束上限が統一的に得られるかを示す。実験により、得られた収束境界と加速度戦略は、正確に2次最適化問題に関係しているだけでなく、ニューラルネットワークのトレーニングに適用した場合にもかなり正確であることがわかった。
参考スコア（独自算出の注目度）: 15.25021403154845
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Performance of optimization on quadratic problems sensitively depends on the low-lying part of the spectrum. For large (effectively infinite-dimensional) problems, this part of the spectrum can often be naturally represented or approximated by power law distributions, resulting in power law convergence rates for iterative solutions of these problems by gradient-based algorithms. In this paper, we propose a new spectral condition providing tighter upper bounds for problems with power law optimization trajectories. We use this condition to build a complete picture of upper and lower bounds for a wide range of optimization algorithms -- Gradient Descent, Steepest Descent, Heavy Ball, and Conjugate Gradients -- with an emphasis on the underlying schedules of learning rate and momentum. In particular, we demonstrate how an optimally accelerated method, its schedule, and convergence upper bound can be obtained in a unified manner for a given shape of the spectrum. Also, we provide first proofs of tight lower bounds for convergence rates of Steepest Descent and Conjugate Gradients under spectral power laws with general exponents. Our experiments show that the obtained convergence bounds and acceleration strategies are not only relevant for exactly quadratic optimization problems, but also fairly accurate when applied to the training of neural networks.
Abstract（参考訳）: 二次問題に対する最適化の性能は、スペクトルの低い部分に依存する。大きな(事実上無限次元の)問題に対して、スペクトルのこの部分は自然に電力法則分布によって表されるか近似されることが多く、結果として勾配に基づくアルゴリズムによってこれらの問題の反復解に対する電力法収束率が得られる。本稿では,電力法最適化トラジェクトリの問題に対して,より厳密な上限を与える新しいスペクトル条件を提案する。我々はこの条件を用いて、学習率と運動量の基礎となるスケジュールに重点を置いて、幅広い最適化アルゴリズム(グラディエント・ディフレッシュ、ステペスト・ディフレッシュ、ヘビーボール、コンジュゲート・グラディエント)の上下境界の全体像を構築する。特に、スペクトルの所定の形状に対して、最適に加速された方法、そのスケジュール、収束上限が統一的に得られるかを示す。また、一般指数を持つスペクトルパワー法則の下で、ステプストDescent と Conjugate Gradients の収束率の厳密な下界の第一の証明を与える。実験により、得られた収束境界と加速度戦略は、正確に2次最適化問題に関係しているだけでなく、ニューラルネットワークのトレーニングに適用した場合にもかなり正確であることがわかった。

関連論文リスト

The inexact power augmented Lagrangian method for constrained nonconvex optimization [44.516958213972885]
この研究は、強大な拡張ラグランジアン用語を導入し、拡大項はユークリッドのノルムを権力へと引き上げる。その結果, 長期化に低消費電力を用いると, 残余の減少が遅くなるにもかかわらず, より高速な成長が期待できることがわかった。以上の結果より, 持続時間の短縮には低消費電力が有効であるが, 残留率が低下する傾向が示唆された。
論文参考訳（メタデータ） (2024-10-26T11:31:56Z)
Proximal Subgradient Norm Minimization of ISTA and FISTA [8.261388753972234]
反復収縮保持アルゴリズムのクラスに対する2乗近位次数ノルムは逆2乗率で収束することを示す。また、高速反復収縮保持アルゴリズム (FISTA) のクラスに対する2乗次次数次ノルムが、逆立方レートで収束するように加速されることも示している。
論文参考訳（メタデータ） (2022-11-03T06:50:19Z)
Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文参考訳（メタデータ） (2021-08-18T09:26:17Z)
Transient growth of accelerated first-order methods for strongly convex optimization problems [1.6114012813668934]
本稿では,高速化第一次最適化アルゴリズムの過渡挙動について検討する。二次最適化問題に対しては、線形系理論のツールを用いて、非正規ダイナミクスの存在から過渡的成長が生じることを示す。強凸滑らかな最適化問題に対して, 積分二次制約の理論を応用し, ネステロフ加速法の過渡応答の大きさの上限を定式化する。
論文参考訳（メタデータ） (2021-03-14T20:01:14Z)
The Role of Momentum Parameters in the Optimal Convergence of Adaptive Polyak's Heavy-ball Methods [12.93796690939018]
適応型Polyak's Heavy-ball (HB) 法は最適な個人収束率を$O(frac1sqrtt)$とする。新しい解析では,hb運動量とその時間的変動が凸最適化の高速化にどのように役立つかを示す。
論文参考訳（メタデータ） (2021-02-15T02:57:14Z)
Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文参考訳（メタデータ） (2020-12-21T17:29:58Z)
An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文参考訳（メタデータ） (2020-10-23T09:12:47Z)
Direct Optimal Control Approach to Laser-Driven Quantum Particle Dynamics [77.34726150561087]
間接制御理論に対する頑健で柔軟な代替手段として, 直接最適制御を提案する。この方法は、バイスタブルポテンシャルにおけるレーザー駆動のウェーブパレットダイナミクスの場合に説明される。
論文参考訳（メタデータ） (2020-10-08T07:59:29Z)
A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints [10.578409461429626]
本研究では、滑らかで強可変なゲームやイテレーションのための一階法に積分二次的制約理論を適用する。我々は、負の運動量法(NM)に対して、既知の下界と一致する複雑性$mathcalO(kappa1.5)$で、初めて大域収束率を与える。一段階のメモリを持つアルゴリズムでは,バッチ毎に1回だけ勾配を問合せすれば,高速化は不可能であることを示す。
論文参考訳（メタデータ） (2020-09-23T20:02:00Z)
IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
論文参考訳（メタデータ） (2020-06-11T18:49:06Z)
Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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