論文の概要: Sharpened Lazy Incremental Quasi-Newton Method
- arxiv url: http://arxiv.org/abs/2305.17283v2
- Date: Tue, 12 Mar 2024 05:54:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-13 17:17:13.237161
- Title: Sharpened Lazy Incremental Quasi-Newton Method
- Title（参考訳）: シャープ化ラジインクリメンタル準ニュートン法
- Authors: Aakash Lahoti, Spandan Senapati, Ketan Rajawat, Alec Koppel
- Abstract要約: SLIQN法(シャープエントラジインクリメンタル準ニュートン法)について紹介する。
明示的な超線型収束率と優れた経験的性能を、定価$O(d2)$コストで達成する。
実験では,他の準ニュートン変種よりもSLIQNの方が優れていることを示した。
- 参考スコア（独自算出の注目度）: 15.632456816019944
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The problem of minimizing the sum of $n$ functions in $d$ dimensions is
ubiquitous in machine learning and statistics. In many applications where the
number of observations $n$ is large, it is necessary to use incremental or
stochastic methods, as their per-iteration cost is independent of $n$. Of
these, Quasi-Newton (QN) methods strike a balance between the per-iteration
cost and the convergence rate. Specifically, they exhibit a superlinear rate
with $O(d^2)$ cost in contrast to the linear rate of first-order methods with
$O(d)$ cost and the quadratic rate of second-order methods with $O(d^3)$ cost.
However, existing incremental methods have notable shortcomings: Incremental
Quasi-Newton (IQN) only exhibits asymptotic superlinear convergence. In
contrast, Incremental Greedy BFGS (IGS) offers explicit superlinear convergence
but suffers from poor empirical performance and has a per-iteration cost of
$O(d^3)$. To address these issues, we introduce the Sharpened Lazy Incremental
Quasi-Newton Method (SLIQN) that achieves the best of both worlds: an explicit
superlinear convergence rate, and superior empirical performance at a
per-iteration $O(d^2)$ cost. SLIQN features two key changes: first, it
incorporates a hybrid strategy of using both classic and greedy BFGS updates,
allowing it to empirically outperform both IQN and IGS. Second, it employs a
clever constant multiplicative factor along with a lazy propagation strategy,
which enables it to have a cost of $O(d^2)$. Additionally, our experiments
demonstrate the superiority of SLIQN over other incremental and stochastic
Quasi-Newton variants and establish its competitiveness with second-order
incremental methods.
- Abstract（参考訳）: n$関数の和を$d$次元で最小化する問題は、機械学習と統計学においてユビキタスである。
観察回数が大きい多くのアプリケーションでは、単文あたりのコストが$n$から独立しているため、インクリメンタルまたは確率的な方法を使う必要がある。
これらのうち、準ニュートン法(qn)は、単文あたりのコストと収束率のバランスをとる。
具体的には、o(d^2)$コストの1次メソッドの線形レートやo(d^3)$コストの2次メソッドの二次レートとは対照的に、o(d^2)$コストの2次レートを示す。
しかし、既存の増分法には顕著な欠点がある: インクリメンタル準ニュートン(IQN)は漸近的超線型収束のみを示す。
対照的に、Incrmental Greedy BFGS (IGS) は明示的な超線形収束を提供するが、経験的性能に乏しく、定価$O(d^3)である。
これらの問題に対処するために, 明示的な超線形収束率と, 定価$O(d^2)の経験的性能という両世界の長所を達成する Sharpened Lazy Incremental Quasi-Newton Method (SLIQN) を導入する。
SLIQNには2つの重要な変更がある。まず、古典的および欲張りのあるBFGS更新の両方を使用するハイブリッド戦略を取り入れ、IQNとIGSの両方を経験的に上回るようにしている。
第二に、巧妙な定数乗算係数と遅延伝播戦略を採用しており、コストは$o(d^2)$である。
さらに, SLIQNが他の漸進的および確率的準ニュートン変種よりも優れていることを実証し, 2次インクリメンタル手法との競合性を実証した。
関連論文リスト
- Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence [20.766358513158206]
双対性ギャップの観点から、大域収束率を$O(min1/k,sqrtd/k1.25)$とする。
これらの結果は、外勾配法よりも準ニュートン法の証明可能な利点を示す最初の大域収束結果である。
論文 参考訳（メタデータ） (2024-10-03T16:08:16Z) - Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
そこで本研究では,Nesterovの高速前方反射法と分散還元法を新たに提案し,根絶問題の解法を提案する。
我々のアルゴリズムは単ループであり、ルートフィリング問題に特化して設計された非バイアス分散還元推定器の新たなファミリーを利用する。
論文 参考訳（メタデータ） (2024-06-04T15:23:29Z) - Stochastic Newton Proximal Extragradient Method [18.47705532817026]
そこで本稿では,これらの境界を改良するNewton Extragradient法を提案する。
我々はHybrid Proximal Extragradient(HPE)フレームワークを拡張してこれを実現する。
論文 参考訳（メタデータ） (2024-06-03T16:06:23Z) - Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth
Convex Optimization [26.328847475942894]
我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。
我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
論文 参考訳（メタデータ） (2023-06-03T23:31:27Z) - Extra-Newton: A First Approach to Noise-Adaptive Accelerated
Second-Order Methods [57.050204432302195]
本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。
我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
論文 参考訳（メタデータ） (2022-11-03T14:12:51Z) - Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient [90.14768299744792]
我々はPolyak-Ruppert 平均 Q-leaning (平均 Q-leaning) を用いた同期 Q-learning を$gamma$-discounted MDP で検討した。
繰り返し平均$barboldsymbolQ_T$に対して正規性を確立する。
要するに、我々の理論分析は、Q-Leaningの平均は統計的に効率的であることを示している。
論文 参考訳（メタデータ） (2021-12-29T14:47:56Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳（メタデータ） (2020-09-29T18:48:21Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z) - Stochastic Subspace Cubic Newton Method [14.624340432672172]
本稿では,高次元凸関数$f$を最小化するランダム化二階最適化アルゴリズムを提案する。
ミニバッチサイズが変化するにつれて、SSCNのグローバル収束速度は座標降下速度(CD)と立方正規化ニュートン速度とを補間することを示した。
注目すべきことに、SSCN の局所収束速度は、次数関数 $frac12 (x-x*)top nabla2f(x*)(x-x*)$ の最小化問題に適用される部分空間降下率と一致する。
論文 参考訳（メタデータ） (2020-02-21T19:42:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。