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

• arxiv url: http://arxiv.org/abs/2202.00992v1
• Date: Wed, 2 Feb 2022 12:24:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-03 15:17:54.765263
• Title: Tight Convergence Rate Bounds for Optimization Under Power Law Spectral Conditions
• Title（参考訳）: 電力法スペクトル条件下での最適化のためのタイト収束速度境界
• Authors: Maksim Velikanov and Dmitry Yarotsky
• Abstract要約: 適応型,非適応型,定数型,非コンスタントな学習率を有する古典的一段階および多段階一階最適化アルゴリズムについて検討する。 スペクトル推定法は、スペクトル指数の特定の倍数で与えられる収束率指数とともに、アルゴリズムの収束率に対するパワー則を必要とすることを証明する。
• 参考スコア（独自算出の注目度）: 17.55171891411791
• 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. In this paper we perform a systematic study of a range of classical single-step and multi-step first order optimization algorithms, with adaptive and non-adaptive, constant and non-constant learning rates: vanilla Gradient Descent, Steepest Descent, Heavy Ball, and Conjugate Gradients. For each of these, we prove that a power law spectral assumption entails a power law for convergence rate of the algorithm, with the convergence rate exponent given by a specific multiple of the spectral exponent. We establish both upper and lower bounds, showing that the results are tight. Finally, we demonstrate applications of these results to kernel learning and training of neural networks in the NTK regime.
• Abstract（参考訳）: 二次問題に対する最適化の性能はスペクトルの低い部分に依存する。 大きな(事実上無限次元の)問題に対して、スペクトルのこの部分は、しばしば自然に電力法則分布によって表されるか近似される。 本稿では,適応型,非適応型,定数型,非コンスタントな学習率であるバニラグラディエントDescent,Steepest Descent,Heavy Ball,Conjugate Gradientsを用いて,古典的な一段階および多段階の1次最適化アルゴリズムを体系的に研究する。 これらのそれぞれに対して、パワー法スペクトル仮定は、スペクトル指数の特定の倍数で与えられる収束率指数とともに、アルゴリズムの収束率に対するパワー則を必要とすることを証明する。 上界と下界の両方を定め、結果は厳密であることを示す。 最後に、NTK体制におけるニューラルネットワークのカーネル学習とトレーニングにこれらの結果の応用を実証する。

関連論文リスト

• 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)

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

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