論文の概要: Higher-Order Newton Methods with Polynomial Work per Iteration
- arxiv url: http://arxiv.org/abs/2311.06374v1
- Date: Fri, 10 Nov 2023 20:02:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-14 18:59:38.984708
- Title: Higher-Order Newton Methods with Polynomial Work per Iteration
- Title（参考訳）: イテレーション当たりの多項式処理による高次ニュートン法
- Authors: Amir Ali Ahmadi, Abraar Chaudhry, Jeffrey Zhang
- Abstract要約: 任意の$d$の微分を包含するオラクル法を一般化するが、その反復次元における盆地への依存は維持する。
数値的な例では、$d$ の局所的なアトラクションは、追加の仮定がなされると局所的に大きくなる。
- 参考スコア（独自算出の注目度）: 0.8506177495717225
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present generalizations of Newton's method that incorporate derivatives of
an arbitrary order $d$ but maintain a polynomial dependence on dimension in
their cost per iteration. At each step, our $d^{\text{th}}$-order method uses
semidefinite programming to construct and minimize a sum of squares-convex
approximation to the $d^{\text{th}}$-order Taylor expansion of the function we
wish to minimize. We prove that our $d^{\text{th}}$-order method has local
convergence of order $d$. This results in lower oracle complexity compared to
the classical Newton method. We show on numerical examples that basins of
attraction around local minima can get larger as $d$ increases. Under
additional assumptions, we present a modified algorithm, again with polynomial
cost per iteration, which is globally convergent and has local convergence of
order $d$.
- Abstract（参考訳）: 任意の次数 $d$ の微分を組み込んだニュートン法を一般化するが、反復あたりのコストの次元に対する多項式依存性は維持する。
それぞれのステップにおいて、我々の$d^{\text{th}}$-orderメソッドは半定値プログラミングを用いて、最小化したい関数の$d^{\text{th}}$-order taylor展開に対する平方凸近似の和を構成および最小化する。
我々は、$d^{\text{th}}$-orderメソッドが$d$の局所収束を持つことを証明します。
この結果、古典的なニュートン法に比べてオラクルの複雑さは低い。
数値的な例では、ローカルミニマ周辺のアトラクションの盆地は$d$の増加とともに大きくなる。
追加の仮定の下で、修正されたアルゴリズムを再び1イテレーションあたりの多項式コストで示し、これはグローバルに収束し、順序 $d$ の局所収束を持つ。
関連論文リスト
- A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
我々は、$f(hat x)$ ができるだけ小さいような点 $hat xin barmathcal X$ を返すアルゴリズムを構築している。
この方法は、$f(hat x) - min_xin barmathcal X f(x)$ が、多対数項まで$d2/sqrtn$ より小さい順序であることを証明する。
論文 参考訳（メタデータ） (2024-06-26T18:19:10Z) - Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
そこで本研究では,Nesterovの高速前方反射法と分散還元法を新たに提案し,根絶問題の解法を提案する。
我々のアルゴリズムは単ループであり、ルートフィリング問題に特化して設計された非バイアス分散還元推定器の新たなファミリーを利用する。
論文 参考訳（メタデータ） (2024-06-04T15:23:29Z) - 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) - 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) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Regularized Newton Method with Global $O(1/k^2)$ Convergence [10.685862129925729]
目的が強く凸している場合,本手法は超直線的に収束することを示す。
我々の手法はニュートン法の最初の変種であり、安価な反復と証明可能な高速な大域収束の両方を持つ。
論文 参考訳（メタデータ） (2021-12-03T18:55:50Z) - Computing the Newton-step faster than Hessian accumulation [8.147652597876862]
関数の計算グラフを考えると、この境界は$O(mtau3)$に縮めることができ、$tau, m$はグラフのツリー分解の幅と大きさである。
提案アルゴリズムは,LQRに基づく非線形最適制御法を一般化し,ヘシアンが高密度である場合においても,反復複雑度において非自明なゲインを提供する。
論文 参考訳（メタデータ） (2021-08-02T11:22:08Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59: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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。