論文の概要: Regularized Newton Method with Global $O(1/k^2)$ Convergence

• arxiv url: http://arxiv.org/abs/2112.02089v1
• Date: Fri, 3 Dec 2021 18:55:50 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-06 16:46:14.358121
• Title: Regularized Newton Method with Global $O(1/k^2)$ Convergence
• Title（参考訳）: グローバル$O(1/k^2)$収束を用いた正規化ニュートン法
• Authors: Konstantin Mishchenko
• Abstract要約: 目的が強く凸している場合,本手法は超直線的に収束することを示す。 我々の手法はニュートン法の最初の変種であり、安価な反復と証明可能な高速な大域収束の両方を持つ。
• 参考スコア（独自算出の注目度）: 10.685862129925729
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a Newton-type method that converges fast from any initialization and for arbitrary convex objectives with Lipschitz Hessians. We achieve this by merging the ideas of cubic regularization with a certain adaptive Levenberg--Marquardt penalty. In particular, we show that the iterates given by $x^{k+1}=x^k - \bigl(\nabla^2 f(x^k) + \sqrt{H\|\nabla f(x^k)\|} \mathbf{I}\bigr)^{-1}\nabla f(x^k)$, where $H>0$ is a constant, converge globally with a $\mathcal{O}(\frac{1}{k^2})$ rate. Our method is the first variant of Newton's method that has both cheap iterations and provably fast global convergence. Moreover, we prove that locally our method converges superlinearly when the objective is strongly convex. To boost the method's performance, we present a line search procedure that does not need hyperparameters and is provably efficient.
• Abstract（参考訳）: 任意の初期化や任意の凸対象に対してリプシッツ・ヘッシアンと高速に収束するニュートン型手法を提案する。 我々は、立方正則化のアイデアとある種の適応レベンベルグ=マルカルトペナルティを融合することによりこれを達成する。 特に、$x^{k+1}=x^k - \bigl(\nabla^2 f(x^k)) + \sqrt{H\|\nabla f(x^k)\|} \mathbf{I}\bigr)^{-1}\nabla f(x^k)$, ここで$H>0$は定数であり、$\mathcal{O}(\frac{1}{k^2})$ rateと全世界的に収束する。 提案手法は,ニュートン法の最初の変種であり,安価な反復と高速なグローバル収束を両立させる。 さらに, 対象が強凸である場合, 局所的に本手法が超線形に収束することを示す。 提案手法の性能を向上させるため,ハイパーパラメータを必要とせず,かつ有効な行探索手法を提案する。

関連論文リスト

• On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
  本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。 我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。 収束率は$frac1Tsum_k=1Tと類似していると考えられる。
  論文  参考訳（メタデータ） (2024-02-01T07:21:32Z)
• Higher-Order Newton Methods with Polynomial Work per Iteration [0.7568448369029973]
  任意の$d$の微分を包含するオラクル法を一般化するが、その反復次元における盆地への依存は維持する。 数値的な例では、$d$ の局所的なアトラクションは、追加の仮定がなされると局所的に大きくなる。
  論文  参考訳（メタデータ） (2023-11-10T20:02:58Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimization [26.328847475942894]
  我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。 我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
  論文  参考訳（メタデータ） (2023-06-03T23:31:27Z)
• Convergence of a Normal Map-based Prox-SGD Method under the KL Inequality [0.0]
  我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
  論文  参考訳（メタデータ） (2023-05-10T01:12:11Z)
• Perseus: A Simple and Optimal High-Order Method for Variational Inequalities [81.32967242727152]
  VI は、$langle F(x), x - xstarrangle geq 0$ for all $x in MathcalX$ であるように、mathcalX$ で $xstar を見つける。 そこで本稿では,テキストitが行探索を必要とせず,$O(epsilon-2/(p+1))$で弱解に確実に収束する$pth$-order法を提案する。
  論文  参考訳（メタデータ） (2022-05-06T13:29:14Z)
• Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization [47.27237492375659]
  双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。 Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
  論文  参考訳（メタデータ） (2022-01-19T05:56:19Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• A fast and simple modification of Newton's method helping to avoid saddle points [0.0]
  この論文は、$f$が$C3$でシーケンス$x_n$であれば、極限点は臨界点であり、サドル点ではなく、収束速度はニュートンの方法と同じである。
  論文  参考訳（メタデータ） (2020-06-02T10:38:00Z)
• A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
  我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。 Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
  論文  参考訳（メタデータ） (2020-03-05T01:56:17Z)

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

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