論文の概要: New Q-Newton's method meets Backtracking line search: good convergence
guarantee, saddle points avoidance, quadratic rate of convergence, and easy
implementation
- arxiv url: http://arxiv.org/abs/2108.10249v1
- Date: Mon, 23 Aug 2021 15:39:00 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-24 15:52:32.569563
- Title: New Q-Newton's method meets Backtracking line search: good convergence
guarantee, saddle points avoidance, quadratic rate of convergence, and easy
implementation
- Title（参考訳）: 新しいq-newton法はバックトラックライン探索を満たす:良好な収束保証、鞍点回避、二次収束率、簡単な実装
- Authors: Tuyen Trung Truong
- Abstract要約: ニュートン法 (Newton's method) は「ニュー・Q・ニュートン法 (New Q-Newton's method)」と名付けられ、サドル点を回避でき、2次収束率を持つ。
小さなスケールでの実験では、この手法は他のニュートンの方法のよく知られた修正と非常に競争的に機能することを示した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In a recent joint work, the author has developed a modification of Newton's
method, named New Q-Newton's method, which can avoid saddle points and has
quadratic rate of convergence. While good theoretical convergence guarantee has
not been established for this method, experiments on small scale problems show
that the method works very competitively against other well known modifications
of Newton's method such as Adaptive Cubic Regularization and BFGS, as well as
first order methods such as Unbounded Two-way Backtracking Gradient Descent.
In this paper, we resolve the convergence guarantee issue by proposing a
modification of New Q-Newton's method, named New Q-Newton's method
Backtracking, which incorporates a more sophisticated use of hyperparameters
and a Backtracking line search. This new method has very good theoretical
guarantees, which for a {\bf Morse function} yields the following (which is
unknown for New Q-Newton's method):
{\bf Theorem.} Let $f:\mathbb{R}^m\rightarrow \mathbb{R}$ be a Morse
function, that is all its critical points have invertible Hessian. Then for a
sequence $\{x_n\}$ constructed by New Q-Newton's method Backtracking from a
random initial point $x_0$, we have the following two alternatives:
i) $\lim _{n\rightarrow\infty}||x_n||=\infty$,
or
ii) $\{x_n\}$ converges to a point $x_{\infty}$ which is a {\bf local
minimum} of $f$, and the rate of convergence is {\bf quadratic}.
Moreover, if $f$ has compact sublevels, then only case ii) happens.
As far as we know, for Morse functions, this is the best theoretical
guarantee for iterative optimization algorithms so far in the literature. We
have tested in experiments on small scale, with some further simplified
versions of New Q-Newton's method Backtracking, and found that the new method
significantly improve New Q-Newton's method.
- Abstract（参考訳）: 最近の共同研究において、著者は、サドル点を回避し、2次収束率を持つNew Q-Newton法と呼ばれるニュートン法を修正した。
この方法の理論的収束保証は確立されていないが、小規模問題に対する実験により、適応立方正則化やBFGSといったニュートン法や、非有界二方向追跡勾配法のような一階法など、他のよく知られた修正法と非常に競合することを示した。
本稿では、より洗練されたハイパーパラメータとバックトラックライン探索を組み込んだ、New Q-Newton法(New Q-Newton法)の修正を提案し、収束保証問題を解消する。
この方法は非常に優れた理論的保証を持ち、これはある {\bf Morse 関数に対して以下の結果が得られる(新Q-ニュートン法では未知である)。
f:\mathbb{R}^m\rightarrow \mathbb{R}$ をモース函数とする。
このとき、New Q-Newton のメソッドで構築されたシーケンス $\{x_n\}$ に対して、ランダムな初期点 $x_0$ からバックトラックすると、次の2つの選択肢がある: i) $\lim _{n\rightarrow\infty}|||x_n||=\infty$, or i) $\{x_n\}$ は、$f$ の a {\bf局所最小値である点 $x_{\infty}$ に収束する。
さらに、$f$ がコンパクトな部分レベルを持つ場合、ケース ii) が発生する。
私たちの知る限り、モース関数は、これまでの文献において反復最適化アルゴリズムの最良の理論的保証である。
我々は,より簡易な新Q-Newton法Backtrackingを用いて,小規模で実験を行い,新Q-Newton法を大幅に改善することを発見した。
関連論文リスト
- Symmetric Rank-One Quasi-Newton Methods for Deep Learning Using Cubic Regularization [0.5120567378386615]
アダムやアダグラッドのような一階降下や他の一階変種は、ディープラーニングの分野で一般的に使われている。
しかし、これらの手法は曲率情報を活用しない。
準ニュートン法は、以前計算された低ヘッセン近似を再利用する。
論文 参考訳（メタデータ） (2025-02-17T20:20:11Z) - 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) - Incremental Quasi-Newton Methods with Faster Superlinear Convergence
Rates [50.36933471975506]
各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。
最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。
本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
論文 参考訳（メタデータ） (2024-02-04T05:54:51Z) - Krylov Cubic Regularized Newton: A Subspace Second-Order Method with
Dimension-Free Convergence Rate [83.3933097134767]
次元に依存しない大域収束率を$Oleft(frac1mk+frac1k2right)$とする,新しい部分空間正規化ニュートン法を導入する。
提案手法は,特に高次元問題に対して,既存のランダム部分空間法よりも高速に収束する。
論文 参考訳（メタデータ） (2024-01-05T20:24:18Z) - Newton-CG methods for nonconvex unconstrained optimization with Hölder continuous Hessian [53.044526424637866]
我々は、H"古いヘッセンによる2つの微分可能な目的関数を最小化する非制約非制約最適化問題を考える。
まずニュートン共役法(Newton-conjugate, Newton-CG)を提案する。
本稿では,パラメータフリーなNewtonCG法において,優れた実用性能を示すための予備的な数値計算結果を提案する。
論文 参考訳（メタデータ） (2023-11-22T01:50:43Z) - Sketch-and-Project Meets Newton Method: Global $\mathcal O(k^{-2})$ Convergence with Low-Rank Updates [1.592855981846993]
高速な$mathcal O(k-2)$大域収束率を持つスケッチ・アンド・プロジェクトニュートン法を提案する。
SGNは、スケッチ・アンド・プロジェクト方式の安価なイテレーションコスト、最先端の$mathcal O(k-2)$フルランクニュートン方式のグローバル収束率、減衰ニュートン方式のアルゴリズム単純さの3つを継承している。
論文 参考訳（メタデータ） (2023-05-22T14:51:40Z) - Regularized Newton Method with Global $O(1/k^2)$ Convergence [10.685862129925729]
目的が強く凸している場合,本手法は超直線的に収束することを示す。
我々の手法はニュートン法の最初の変種であり、安価な反復と証明可能な高速な大域収束の両方を持つ。
論文 参考訳（メタデータ） (2021-12-03T18:55:50Z) - Newton-LESS: Sparsification without Trade-offs for the Sketched Newton
Update [88.73437209862891]
2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。
本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。
ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
論文 参考訳（メタデータ） (2021-07-15T17:33:05Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳（メタデータ） (2020-09-29T18:48:21Z) - Unconstrained optimisation on Riemannian manifolds [0.0]
本稿では, (Local-) Backtracking Gradient Descent と New Q-Newton の手法について記述する。
また、対称正方行列の最小固有値を計算するための明示的な計算を行う。
論文 参考訳（メタデータ） (2020-08-25T15:10:21Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。