論文の概要: Second-order optimization with lazy Hessians
- arxiv url: http://arxiv.org/abs/2212.00781v3
- Date: Thu, 15 Jun 2023 12:25:04 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-17 02:54:51.711434
- Title: Second-order optimization with lazy Hessians
- Title（参考訳）: 遅延ヘッシアンによる二階最適化
- Authors: Nikita Doikov, El Mahdi Chayti, Martin Jaggi
- Abstract要約: 一般の非線形最適化問題を解くためにニュートンの遅延ヘッセン更新を解析する。
我々は、メソッドの各ステップで新しい勾配を計算しながら、これまで見られたヘッセン反復を再利用する。
- 参考スコア（独自算出の注目度）: 55.51077907483634
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We analyze Newton's method with lazy Hessian updates for solving general
possibly non-convex optimization problems. We propose to reuse a previously
seen Hessian for several iterations while computing new gradients at each step
of the method. This significantly reduces the overall arithmetical complexity
of second-order optimization schemes. By using the cubic regularization
technique, we establish fast global convergence of our method to a second-order
stationary point, while the Hessian does not need to be updated each iteration.
For convex problems, we justify global and local superlinear rates for lazy
Newton steps with quadratic regularization, which is easier to compute. The
optimal frequency for updating the Hessian is once every $d$ iterations, where
$d$ is the dimension of the problem. This provably improves the total
arithmetical complexity of second-order algorithms by a factor $\sqrt{d}$.
- Abstract（参考訳）: 一般の非凸最適化問題を解くために,遅延ヘッセン更新を用いたニュートン法を解析した。
提案手法では,各ステップで新しい勾配を計算しながら,いくつかのイテレーションで既見のヘッシアンを再利用する。
これは二階最適化スキームの全体的な算術的複雑性を大幅に削減する。
立方正則化法を用いて,本手法の高速な大域収束を2次定常点に確立する一方,ヘッセンは反復ごとに更新される必要はない。
凸問題に対して、計算が容易な2次正規化による遅延ニュートンステップのグローバルおよび局所超線形率を正当化する。
ヘシアンを更新する最適な周波数は、1回$d$の繰り返しであり、$d$は問題の次元である。
これは2階アルゴリズムの算術的複雑性を$\sqrt{d}$で証明的に改善する。
関連論文リスト
- First and zeroth-order implementations of the regularized Newton method
with lazy approximated Hessians [4.62316736194615]
我々は一般の非自由$ノルムフリー問題のリップオーダー(ヘシアン-O)とゼロオーダー(微分自由)の実装を開発する。
また、アルゴリズムに遅延バウンダリ更新を加えて、これまで計算されたヘッセン近似行列を数回繰り返し再利用する。
論文 参考訳（メタデータ） (2023-09-05T17:40:54Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。
私たちの分析は単純だが強力だ。
Goldstein-subdifferential set, これは最近の進歩を可能にする。
非滑らかな非最適化
論文 参考訳（メタデータ） (2023-07-10T11:56:04Z) - Faster Riemannian Newton-type Optimization by Subsampling and Cubic
Regularization [3.867143522757309]
この研究は、制約集合が多様体構造を意味するような制約付き大規模非制約最適化に関するものである。
本稿では,収束性の向上と計算コストの削減を目的とした2階サドル最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-22T00:37:44Z) - 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) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳（メタデータ） (2021-12-09T02:27:52Z) - Newton-LESS: Sparsification without Trade-offs for the Sketched Newton
Update [88.73437209862891]
2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。
本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。
ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
論文 参考訳（メタデータ） (2021-07-15T17:33:05Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。