論文の概要: 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)
• Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving $O(1/k)$ Finite-Sample Complexity [2.5382095320488665]
  本稿では,2つの結合非線形作用素の根を探すために,2時間スケールのモノトン近似の新しい変種を開発することを提案する。 私たちのキーとなるアイデアは、古典的なRuppert-Polyak平均化技術を活用して、それらのサンプルを通して演算子を動的に推定することです。 これらの平均ステップの見積値は、望まれる解を見つけるために、2時間スケールの近似更新で使用される。
  論文  参考訳（メタデータ） (2024-01-23T13:44:15Z)
• 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)
• 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)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。