論文の概要: SPAN: A Stochastic Projected Approximate Newton Method
- arxiv url: http://arxiv.org/abs/2002.03687v2
- Date: Tue, 3 Mar 2020 02:01:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 09:37:47.264349
- Title: SPAN: A Stochastic Projected Approximate Newton Method
- Title(参考訳): SPAN: 確率的予測型近似ニュートン法
- Authors: Xunpeng Huang, Xianfeng Liang, Zhengyang Liu, Yitan Li, Linyun Yu, Yue
Yu, Lei Li
- Abstract要約: ヘッセン行列の逆数を計算するために,新しい近似的かつ高速なニュートン法であるSPANを提案する。
SPANは、コンバージェンスウォールクロック時間の観点から、既存の1次および2次最適化手法より優れている。
- 参考スコア(独自算出の注目度): 17.94221425332409
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Second-order optimization methods have desirable convergence properties.
However, the exact Newton method requires expensive computation for the Hessian
and its inverse. In this paper, we propose SPAN, a novel approximate and fast
Newton method. SPAN computes the inverse of the Hessian matrix via low-rank
approximation and stochastic Hessian-vector products. Our experiments on
multiple benchmark datasets demonstrate that SPAN outperforms existing
first-order and second-order optimization methods in terms of the convergence
wall-clock time. Furthermore, we provide a theoretical analysis of the
per-iteration complexity, the approximation error, and the convergence rate.
Both the theoretical analysis and experimental results show that our proposed
method achieves a better trade-off between the convergence rate and the
per-iteration efficiency.
- Abstract(参考訳): 二階最適化は望ましい収束特性を持つ。
しかし、正確なニュートン法はヘッセンとその逆数に対する高価な計算を必要とする。
本稿では,新しい近似的かつ高速なニュートン法であるSPANを提案する。
SPANはローランク近似と確率的ヘッセンベクトル積を通じてヘッセン行列の逆を計算する。
複数のベンチマークデータセットを用いた実験により,spanは壁時間収束の観点から,既存の一階および二階最適化手法よりも優れていることが示された。
さらに, 点数毎の複雑性, 近似誤差, 収束率に関する理論的解析を行った。
理論解析と実験の結果から,提案手法はコンバージェンス率とイテレーション効率のトレードオフが良好であることが判明した。
関連論文リスト
- Incremental Quasi-Newton Methods with Faster Superlinear Convergence
Rates [50.36933471975506]
各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。
最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。
本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
論文 参考訳(メタデータ) (2024-02-04T05:54:51Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - Robust empirical risk minimization via Newton's method [9.797319790710711]
実験的リスク最小化のためのニュートン法の新しい変種について検討した。
目的関数の勾配と Hessian は、ロバストな推定器に置き換えられる。
また,共役勾配法に基づくニュートン方向のロバストな解を求めるアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-30T18:54:54Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - A Unified Convergence Theorem for Stochastic Optimization Methods [4.94128206910124]
一連の統一最適化手法に対する収束結果の導出に使用される基本的な統一収束定理を提供する。
直接応用として、一般的な設定下での収束結果をほぼ確実に回復する。
論文 参考訳(メタデータ) (2022-06-08T14:01:42Z) - Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization
with Large Batches [22.925108493465363]
本稿では,二階法の利点をすべて享受する有限サム最小化アルゴリズムを提案する。
本稿では,SVRNが最小二乗解法(Subsampled Newtonなど)や反復最小二乗解法を高速化できることを示す。
論文 参考訳(メタデータ) (2022-06-06T16:00:18Z) - A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。
提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
論文 参考訳(メタデータ) (2021-10-07T17:51:10Z) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
論文 参考訳(メタデータ) (2021-04-30T08:50:24Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳(メタデータ) (2020-10-15T18:09:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。