論文の概要: Newton-CG methods for nonconvex unconstrained optimization with H\"older
continuous Hessian
- arxiv url: http://arxiv.org/abs/2311.13094v1
- Date: Wed, 22 Nov 2023 01:50:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-23 16:31:52.146961
- Title: Newton-CG methods for nonconvex unconstrained optimization with H\"older
continuous Hessian
- Title(参考訳): H\"older continuous Hessian を用いた非凸非拘束最適化のためのNewton-CG法
- Authors: Chuan He and Zhaosong Lu
- Abstract要約: 我々は、H"古いヘッセンによる2つの微分可能な目的関数を最小化する非制約非制約最適化問題を考える。
パラメータの事前知識を必要とせず,パラメータフリーなNewtonCG法を開発した。
本稿では,よく知られた正規化ニュートン法よりも優れた実用性能を示すために,予備的な数値計算結果を提案する。
- 参考スコア(独自算出の注目度): 5.161026048499362
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we consider a nonconvex unconstrained optimization problem
minimizing a twice differentiable objective function with H\"older continuous
Hessian. Specifically, we first propose a Newton-conjugate gradient (Newton-CG)
method for finding an approximate first-order stationary point (FOSP) of this
problem, assuming the associated the H\"older parameters are explicitly known.
Then we develop a parameter-free Newton-CG method without requiring any prior
knowledge of these parameters. To the best of our knowledge, this method is the
first parameter-free second-order method achieving the best-known iteration and
operation complexity for finding an approximate FOSP of this problem.
Furthermore, we propose a Newton-CG method for finding an approximate
second-order stationary point (SOSP) of the considered problem with high
probability and establish its iteration and operation complexity. Finally, we
present preliminary numerical results to demonstrate the superior practical
performance of our parameter-free Newton-CG method over a well-known
regularized Newton method.
- Abstract(参考訳): 本稿では, h\"older continuous hessian の 2 倍微分可能な対象関数を最小化する非凸非拘束最適化問題を考える。
具体的には,h\"olderパラメータが明示的に知られていることを仮定して,この問題の近似一階定常点(fosp)を求めるニュートン共役勾配(newton-cg)法を提案する。
そこで,パラメータの事前知識を必要とせずにパラメータフリーのニュートンcg法を開発した。
我々の知る限りでは、この手法は最もよく知られた反復と操作の複雑さを達成する最初のパラメータフリーな二階法である。
さらに,高確率で考慮された問題の2次定常点(sosp)を近似的に求めるニュートンcg法を提案し,その反復と演算の複雑さを確立する。
最後に,よく知られた正規化ニュートン法よりもパラメータフリーニュートンcg法が優れていることを示すために,予備的な数値計算結果を示す。
関連論文リスト
- Incremental Quasi-Newton Methods with Faster Superlinear Convergence
Rates [50.36933471975506]
各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。
最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。
本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
論文 参考訳(メタデータ) (2024-02-04T05:54:51Z) - Provably Efficient Gauss-Newton Temporal Difference Learning Method with
Function Approximation [9.661245904728618]
関数近似を用いたQ値推定問題の解法としてガウスニュートン時間差分法(GNTD)を提案する。
本研究では, 線形, ニューラルネットワーク, 一般スムーズ関数近似の下でのGNTDの有限サンプル非漸近収束を導出した。
論文 参考訳(メタデータ) (2023-02-25T14:14:01Z) - A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization [77.8485863487028]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳(メタデータ) (2023-01-10T20:43:29Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳(メタデータ) (2023-01-10T12:18:47Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (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) - STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。
我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
論文 参考訳(メタデータ) (2021-11-01T15:43:36Z) - Newton-LESS: Sparsification without Trade-offs for the Sketched Newton
Update [88.73437209862891]
2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。
本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。
ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
論文 参考訳(メタデータ) (2021-07-15T17:33:05Z) - Distributed Second Order Methods with Fast Rates and Compressed
Communication [6.069611493148631]
分散最適化のための通信効率の高い第2次手法を複数開発する。
我々は大域的な部分線型および線形収束率と高速超線形速度を証明した。
結果は実データセットでの実験結果と共にサポートされます。
論文 参考訳(メタデータ) (2021-02-14T14:06:45Z) - A Unified Analysis of First-Order Methods for Smooth Games via Integral
Quadratic Constraints [10.578409461429626]
本研究では、滑らかで強可変なゲームやイテレーションのための一階法に積分二次的制約理論を適用する。
我々は、負の運動量法(NM)に対して、既知の下界と一致する複雑性$mathcalO(kappa1.5)$で、初めて大域収束率を与える。
一段階のメモリを持つアルゴリズムでは,バッチ毎に1回だけ勾配を問合せすれば,高速化は不可能であることを示す。
論文 参考訳(メタデータ) (2020-09-23T20:02:00Z) - On Newton Screening [14.040371216692645]
我々はNewton Screening (NS) と呼ばれる新しいスクリーニング手法を開発した。
NSは、一段階局所収束を達成するという意味で、最適収束特性を有することを示す。
論文 参考訳(メタデータ) (2020-01-27T11:25:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。