論文の概要: A fast and simple modification of Newton's method helping to avoid
saddle points
- arxiv url: http://arxiv.org/abs/2006.01512v4
- Date: Thu, 9 Sep 2021 14:26:11 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-26 00:20:51.116572
- Title: A fast and simple modification of Newton's method helping to avoid
saddle points
- Title（参考訳）: サドル点の回避を支援するニュートン法の高速かつ簡便な修正
- Authors: Tuyen Trung Truong, Tat Dat To, Tuan Hang Nguyen, Thu Hang Nguyen,
Hoang Phuong Nguyen, Maged Helmy
- Abstract要約: この論文は、$f$が$C3$でシーケンス$x_n$であれば、極限点は臨界点であり、サドル点ではなく、収束速度はニュートンの方法と同じである。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose in this paper New Q-Newton's method. The update rule is very
simple conceptually, for example $x_{n+1}=x_n-w_n$ where
$w_n=pr_{A_n,+}(v_n)-pr_{A_n,-}(v_n)$, with $A_n=\nabla ^2f(x_n)+\delta
_n||\nabla f(x_n)||^2.Id$ and $v_n=A_n^{-1}.\nabla f(x_n)$. Here $\delta _n$ is
an appropriate real number so that $A_n$ is invertible, and $pr_{A_n,\pm}$ are
projections to the vector subspaces generated by eigenvectors of positive
(correspondingly negative) eigenvalues of $A_n$.
The main result of this paper roughly says that if $f$ is $C^3$ (can be
unbounded from below) and a sequence $\{x_n\}$, constructed by the New
Q-Newton's method from a random initial point $x_0$, {\bf converges}, then the
limit point is a critical point and is not a saddle point, and the convergence
rate is the same as that of Newton's method. The first author has recently been
successful incorporating Backtracking line search to New Q-Newton's method,
thus resolving the convergence guarantee issue observed for some (non-smooth)
cost functions. An application to quickly finding zeros of a univariate
meromorphic function will be discussed. Various experiments are performed,
against well known algorithms such as BFGS and Adaptive Cubic Regularization
are presented.
- Abstract（参考訳）: 本稿では,新しいQ-Newton法を提案する。
例えば、$w_n=pr_{a_n,+}(v_n)-pr_{a_n,-}(v_n)$、$a_n=\nabla ^2f(x_n)+\delta _n||\nabla f(x_n)||^2.id$、$v_n=a_n^{-1}である。
f(x_n)$ である。
ここで、$\delta _n$ は、$a_n$ が可逆であるような適切な実数であり、$pr_{a_n,\pm}$ は、正(対応する負)固有値 $a_n$ の固有ベクトル部分空間の射影である。
この論文の主な結果は、もし$f$ が$c^3$(下からアンバウンドできる)で、ランダムな初期点 $x_0$, {\bf converges} から新しい q-ニュートン法によって構築されたシーケンス $\{x_n\}$ であるなら、極限点は臨界点であり、鞍点ではなく、収束率はニュートン法と同じである。
最初の著者は、最近 New Q-Newton の手法に Backtracking line search を組み込むことで、いくつかの(滑らかでない)コスト関数で観測される収束保証問題の解決に成功した。
単変数の準同型関数の零点を素早く見つけるための応用について論じる。
BFGSやAdaptive Cubic Regularizationといったよく知られたアルゴリズムに対して、様々な実験が行われている。
関連論文リスト
- 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) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - Distribution-Independent Regression for Generalized Linear Models with
Oblivious Corruptions [49.69852011882769]
一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。
本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。
これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
論文 参考訳（メタデータ） (2023-09-20T21:41:59Z) - 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) - Regularized Newton Method with Global $O(1/k^2)$ Convergence [10.685862129925729]
目的が強く凸している場合,本手法は超直線的に収束することを示す。
我々の手法はニュートン法の最初の変種であり、安価な反復と証明可能な高速な大域収束の両方を持つ。
論文 参考訳（メタデータ） (2021-12-03T18:55:50Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - Generalisations and improvements of New Q-Newton's method Backtracking [0.0]
本稿では,新しいQ-Newtonの手法のバックトラッキングのための一般的なフレームワークを提案する。
例えば、1$ または $e_m(x)$'s は必ずしも $nabla 2f(x)$ の固有ベクトルではない。
論文 参考訳（メタデータ） (2021-09-23T14:28:15Z) - New Q-Newton's method meets Backtracking line search: good convergence
guarantee, saddle points avoidance, quadratic rate of convergence, and easy
implementation [0.0]
ニュートン法 (Newton's method) は「ニュー・Q・ニュートン法 (New Q-Newton's method)」と名付けられ、サドル点を回避でき、2次収束率を持つ。
小さなスケールでの実験では、この手法は他のニュートンの方法のよく知られた修正と非常に競争的に機能することを示した。
論文 参考訳（メタデータ） (2021-08-23T15:39:00Z) - Statistical Query Lower Bounds for List-Decodable Linear Regression [55.06171096484622]
本稿では,リスト復号化可能な線形回帰問題について考察する。
我々の主な成果は、この問題に対して$dmathrmpoly (1/alpha)$の統計的クエリ(SQ)の低いバウンダリである。
論文 参考訳（メタデータ） (2021-06-17T17:45:21Z) - Unconstrained optimisation on Riemannian manifolds [0.0]
本稿では, (Local-) Backtracking Gradient Descent と New Q-Newton の手法について記述する。
また、対称正方行列の最小固有値を計算するための明示的な計算を行う。
論文 参考訳（メタデータ） (2020-08-25T15:10:21Z) - Backtracking Gradient Descent allowing unbounded learning rates [0.0]
ユークリッド空間上の非制約最適化では、勾配 Descent process (GD) $x_n+1=x_n-delta _n nabla f(x_n)$ の収束を証明するために、通常、学習レート $delta _n$'s が有界であることが要求される。
本稿では,学習率$delta _n$を非有界にする。
この$h$の成長率は、シーケンスの$x_n$の収束を望んでいれば最善であることが示される。
論文 参考訳（メタデータ） (2020-01-07T12:52:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。