論文の概要: A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees

• arxiv url: http://arxiv.org/abs/2502.04799v2
• Date: Fri, 14 Feb 2025 16:53:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-17 18:05:10.787867
• Title: A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees
• Title（参考訳）: 大域的・局所的複雑度保証を用いた非凸最適化のための正規化ニュートン法
• Authors: Yuhao Zhou, Jintao Xu, Chenglong Bao, Chao Ding, Jun Zhu,
• Abstract要約: 2階局所呼び出しに関して、$epsilon-frac32) + tilde O$と、Hessian-vectorvectorsに対して$tilde O(epsilon-frac74)$という大域的な複雑さを見出す。 予備的な数値計算の結果は、我々のアルゴリズムを示している。
• 参考スコア（独自算出の注目度）: 31.772894924814395
• License:
• Abstract: We consider the problem of finding an $\epsilon$-stationary point of a nonconvex function with a Lipschitz continuous Hessian and propose a quadratic regularized Newton method incorporating a new class of regularizers constructed from the current and previous gradients. The method leverages a recently developed linear conjugate gradient approach with a negative curvature monitor to solve the regularized Newton equation. Notably, our algorithm is adaptive, requiring no prior knowledge of the Lipschitz constant of the Hessian, and achieves a global complexity of $O(\epsilon^{-\frac{3}{2}}) + \tilde O(1)$ in terms of the second-order oracle calls, and $\tilde O(\epsilon^{-\frac{7}{4}})$ for Hessian-vector products, respectively. Moreover, when the iterates converge to a point where the Hessian is positive definite, the method exhibits quadratic local convergence. Preliminary numerical results illustrate the competitiveness of our algorithm.
• Abstract（参考訳）: 我々は、リプシッツ連続ヘシアンを持つ非凸関数の$\epsilon$-定常点を求める問題を考察し、現在の勾配とそれ以前の勾配から構築された新しい正則化のクラスを組み込んだ二次正則化ニュートン法を提案する。 この方法は、正則化ニュートン方程式を解くために、負曲率モニターを用いた最近開発された線形共役勾配法を利用する。 特に、我々のアルゴリズムは適応的であり、ヘシアンのリプシッツ定数の事前知識は必要とせず、ヘシアンベクトル積に対してそれぞれ$O(\epsilon^{-\frac{3}{2}}) + \tilde O(1)$、$\tilde O(\epsilon^{-\frac{7}{4}})$という大域的な複雑さを達成する。 さらに、反復が正定値である点に収束すると、この方法は二次局所収束を示す。 予備的な数値計算の結果は,アルゴリズムの競争力を示している。

関連論文リスト

• Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence [20.766358513158206]
  双対性ギャップの観点から、大域収束率を$O(min1/k,sqrtd/k1.25)$とする。 これらの結果は、外勾配法よりも準ニュートン法の証明可能な利点を示す最初の大域収束結果である。
  論文  参考訳（メタデータ） (2024-10-03T16:08:16Z)
• Reduced-Space Iteratively Reweighted Second-Order Methods for Nonconvex Sparse Regularization [11.56128809794923]
  本稿では,局所的なプロパティ収束の反復を$ell_p-$で行うような非スパース性プロモート正規化問題について検討する。
  論文  参考訳（メタデータ） (2024-07-24T12:15:59Z)
• Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
  1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。 本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。 本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
  論文  参考訳（メタデータ） (2024-06-18T20:14:52Z)
• First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessians [4.62316736194615]
  我々は一般の非自由$ノルムフリー問題のリップオーダー(ヘシアン-O)とゼロオーダー(微分自由)の実装を開発する。 また、アルゴリズムに遅延バウンダリ更新を加えて、これまで計算されたヘッセン近似行列を数回繰り返し再利用する。
  論文  参考訳（メタデータ） (2023-09-05T17:40:54Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• Second-order optimization with lazy Hessians [55.51077907483634]
  一般の非線形最適化問題を解くためにニュートンの遅延ヘッセン更新を解析する。 我々は、メソッドの各ステップで新しい勾配を計算しながら、これまで見られたヘッセン反復を再利用する。
  論文  参考訳（メタデータ） (2022-12-01T18:58:26Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。 ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
  論文  参考訳（メタデータ） (2021-07-15T17:33:05Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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