論文の概要: Sharpened Lazy Incremental Quasi-Newton Method
- arxiv url: http://arxiv.org/abs/2305.17283v1
- Date: Fri, 26 May 2023 22:06:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-30 20:42:52.261284
- Title: Sharpened Lazy Incremental Quasi-Newton Method
- Title（参考訳）: シャープ化ラジインクリメンタル準ニュートン法
- Authors: Aakash Lahoti, Spandan Senapati, Ketan Rajawat, Alec Koppel
- Abstract要約: この研究は、両方の世界の長所を達成するシャープニング・ラジー・インクリメンタル・クアシ・ニュートン(SLIQN)法(英語版)(Sharpened Lazy Incremental Quasi-Newton, SLIQN)を提唱している。
提案されたインクリメンタルなバージョンには、古典的なBFGSアップデートとエレディなBFGSアップデートの両方を取り入れたハイブリッドなアップデート戦略が組み込まれている。
- 参考スコア（独自算出の注目度）: 11.654568410166082
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the finite sum minimization of $n$ strongly convex and smooth
functions with Lipschitz continuous Hessians in $d$ dimensions. In many
applications where such problems arise, including maximum likelihood
estimation, empirical risk minimization, and unsupervised learning, the number
of observations $n$ is large, and it becomes necessary to use incremental or
stochastic algorithms whose per-iteration complexity is independent of $n$. Of
these, the incremental/stochastic variants of the Newton method exhibit
superlinear convergence, but incur a per-iteration complexity of $O(d^3)$,
which may be prohibitive in large-scale settings. On the other hand, the
incremental Quasi-Newton method incurs a per-iteration complexity of $O(d^2)$
but its superlinear convergence rate has only been characterized
asymptotically. This work puts forth the Sharpened Lazy Incremental
Quasi-Newton (SLIQN) method that achieves the best of both worlds: an explicit
superlinear convergence rate with a per-iteration complexity of $O(d^2)$.
Building upon the recently proposed Sharpened Quasi-Newton method, the proposed
incremental variant incorporates a hybrid update strategy incorporating both
classic and greedy BFGS updates. The proposed lazy update rule distributes the
computational complexity between the iterations, so as to enable a
per-iteration complexity of $O(d^2)$. Numerical tests demonstrate the
superiority of SLIQN over all other incremental and stochastic Quasi-Newton
variants.
- Abstract（参考訳）: 我々は、d$次元のリプシッツ連続ヘッシアンを持つn$強凸および滑らかな関数の有限和最小化を考える。
最大推定、経験的リスク最小化、教師なし学習など、そのような問題が生じる多くのアプリケーションにおいて、n$の観測数は膨大であり、各項目毎の複雑性が$n$とは独立な漸進的あるいは確率的アルゴリズムを使用する必要がある。
これらのうち、ニュートン法の漸進的/確率的変種は超線型収束を示すが、大規模設定では禁じられるであろう$O(d^3)$の点当たりの複雑さを生じさせる。
一方、インクリメンタルな準ニュートン法は、o(d^2)$ のイテレーション毎の複雑性をもたらすが、その超線形収束率は漸近的に特徴づけられるのみである。
この研究は、2つの世界のベストを達成するシャープな遅延漸進的準ニュートン(sliqn)法(英語版)(sliqn)を導出する: 文毎の複雑性が$o(d^2)$である明示的な超線形収束率。
最近提案されたSharpened Quasi-Newton法に基づいて、提案されたインクリメンタルなバージョンには、古典的および欲求的なBFGS更新の両方を取り入れたハイブリッドな更新戦略が組み込まれている。
提案した遅延更新規則は、繰り返し間の計算複雑性を分散し、$O(d^2)$のイテレーション当たりの複雑性を実現する。
数値実験は、SLIQNが他の増分的および確率的準ニュートン変種よりも優れていることを示す。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。