論文の概要: First and zeroth-order implementations of the regularized Newton method
with lazy approximated Hessians
- arxiv url: http://arxiv.org/abs/2309.02412v1
- Date: Tue, 5 Sep 2023 17:40:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-06 13:43:44.753398
- Title: First and zeroth-order implementations of the regularized Newton method
with lazy approximated Hessians
- Title（参考訳）: 遅延近似ヘッシアンを用いた正則化ニュートン法の一階およびゼロ階実装
- Authors: Nikita Doikov, Geovani Nunes Grapiglia
- Abstract要約: 我々は一般の非自由$ノルムフリー問題のリップオーダー(ヘシアン-O)とゼロオーダー(微分自由)の実装を開発する。
また、アルゴリズムに遅延バウンダリ更新を加えて、これまで計算されたヘッセン近似行列を数回繰り返し再利用する。
- 参考スコア（独自算出の注目度）: 4.62316736194615
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we develop first-order (Hessian-free) and zero-order
(derivative-free) implementations of the Cubically regularized Newton method
for solving general non-convex optimization problems. For that, we employ
finite difference approximations of the derivatives. We use a special adaptive
search procedure in our algorithms, which simultaneously fits both the
regularization constant and the parameters of the finite difference
approximations. It makes our schemes free from the need to know the actual
Lipschitz constants. Additionally, we equip our algorithms with the lazy
Hessian update that reuse a previously computed Hessian approximation matrix
for several iterations. Specifically, we prove the global complexity bound of
$\mathcal{O}( n^{1/2} \epsilon^{-3/2})$ function and gradient evaluations for
our new Hessian-free method, and a bound of $\mathcal{O}( n^{3/2}
\epsilon^{-3/2} )$ function evaluations for the derivative-free method, where
$n$ is the dimension of the problem and $\epsilon$ is the desired accuracy for
the gradient norm. These complexity bounds significantly improve the previously
known ones in terms of the joint dependence on $n$ and $\epsilon$, for the
first-order and zeroth-order non-convex optimization.
- Abstract（参考訳）: 本研究では,一般の非凸最適化問題を解くために,立方正則ニュートン法の1次(ヘッセンフリー)および0次(微分フリー)実装を開発する。
そのため、微分の有限差分近似を用いる。
アルゴリズムでは、正規化定数と有限差分近似のパラメータの両方に同時に適合する特別な適応探索手順を用いる。
これは我々のスキームを実際のリプシッツ定数を知る必要性から解放する。
さらに、いくつかのイテレーションで計算済みのヘッセン近似行列を再利用する遅延ヘッセン更新をアルゴリズムに装備する。
具体的には、新しい Hessian-free 法に対する関数および勾配評価の $\mathcal{O}(n^{1/2} \epsilon^{-3/2})$ と微分自由法に対する $\mathcal{O}(n^{3/2} \epsilon^{-3/2} )$ の関数評価の $n$ は問題の次元であり、$\epsilon$ は勾配ノルムの所望の精度であることを示す。
これらの複雑性は、一階およびゼロ階の非凸最適化に対する$n$と$\epsilon$の合同依存の観点から、これまで知られていたものを大幅に改善する。
関連論文リスト
- Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - 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) - A Newton-CG based barrier method for finding a second-order stationary
point of nonconvex conic optimization with complexity guarantees [0.5922488908114022]
2つの微分可能な関数の交叉を最小限に抑える2階定常点(SOSP)の発見を検討する。
我々の方法は反復であるだけでなく、最もよく知られた複雑性にマッチする$mincal O(epsilon/2)を達成する。
論文 参考訳（メタデータ） (2022-07-12T17:21:45Z) - A Projection-free Algorithm for Constrained Stochastic Multi-level
Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。
提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文 参考訳（メタデータ） (2022-02-09T06:05:38Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。