論文の概要: Nys-Curve: Nystr\"om-Approximated Curvature for Stochastic Optimization
- arxiv url: http://arxiv.org/abs/2110.08577v1
- Date: Sat, 16 Oct 2021 14:04:51 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-21 12:15:19.935256
- Title: Nys-Curve: Nystr\"om-Approximated Curvature for Stochastic Optimization
- Title(参考訳): 確率最適化のためのNys-Curve: Nystr\
- Authors: Hardik Tankaria, Dinesh Singh, Makoto Yamada
- Abstract要約: 準ニュートン法は, セカント方程式を用いてヘッセンを近似することにより曲率情報を提供する。
線形収束率を持つ凸関数の大規模な経験的リスクに対するニュートンステップに基づくDP最適化アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 20.189732632410024
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The quasi-Newton methods generally provide curvature information by
approximating the Hessian using the secant equation. However, the secant
equation becomes insipid in approximating the Newton step owing to its use of
the first-order derivatives. In this study, we propose an approximate Newton
step-based stochastic optimization algorithm for large-scale empirical risk
minimization of convex functions with linear convergence rates. Specifically,
we compute a partial column Hessian of size ($d\times k$) with $k\ll d$
randomly selected variables, then use the \textit{Nystr\"om method} to better
approximate the full Hessian matrix. To further reduce the computational
complexity per iteration, we directly compute the update step
($\Delta\boldsymbol{w}$) without computing and storing the full Hessian or its
inverse. Furthermore, to address large-scale scenarios in which even computing
a partial Hessian may require significant time, we used distribution-preserving
(DP) sub-sampling to compute a partial Hessian. The DP sub-sampling generates
$p$ sub-samples with similar first and second-order distribution statistics and
selects a single sub-sample at each epoch in a round-robin manner to compute
the partial Hessian. We integrate our approximated Hessian with stochastic
gradient descent and stochastic variance-reduced gradients to solve the
logistic regression problem. The numerical experiments show that the proposed
approach was able to obtain a better approximation of Newton\textquotesingle s
method with performance competitive with the state-of-the-art first-order and
the stochastic quasi-Newton methods.
- Abstract(参考訳): 準ニュートン法は一般に正則方程式を用いてヘッセンを近似することで曲率情報を提供する。
しかし、セカント方程式は一階微分(英語版)を用いることでニュートン段階に近いものとなる。
本研究では,線形収束率を持つ凸関数の大規模リスク最小化のための,ニュートンステップに基づく近似確率最適化アルゴリズムを提案する。
具体的には、$k\ll d$ の変数をランダムに選択した部分列 Hessian ($d\times k$) を計算し、次に \textit{Nystr\"om method} を使って、完全な Hessian 行列をよりよく近似する。
繰り返し毎の計算複雑性をさらに軽減するため、Hessianあるいはその逆を計算したり保存したりすることなく、更新ステップ(\Delta\boldsymbol{w}$)を直接計算する。
さらに,部分ヘシアンを計算してもかなりの時間を要するような大規模シナリオに対処するために,分布保存(DP)サブサンプリングを用いて部分ヘシアンを計算した。
DPサブサンプリングは、同様の1次および2次分布統計を持つ$p$サブサンプルを生成し、各エポックにおける1つのサブサンプルをラウンドロビン方式で選択し、部分ヘッセンを計算する。
近似ヘシアンと確率勾配勾配と確率分散還元勾配を統合し,ロジスティック回帰問題を解く。
数値実験により,提案手法は,最先端の1次法や確率的準ニュートン法と競合する性能を持つNewton\textquotesle s法の近似値を得ることができた。
関連論文リスト
- Unbiased Kinetic Langevin Monte Carlo with Inexact Gradients [0.9558392439655016]
動力学的ランゲヴィンダイナミクスに基づく後進手段の非バイアス化手法を提案する。
提案した推定器は偏りがなく、有限分散となり、中心極限定理を満たす。
実験により, 有効試料当たりの勾配評価の数は, 不正確な勾配を用いた場合においても, 寸法に依存しないことが示唆された。
論文 参考訳(メタデータ) (2023-11-08T21:19:52Z) - Robust empirical risk minimization via Newton's method [9.797319790710711]
実験的リスク最小化のためのニュートン法の新しい変種について検討した。
目的関数の勾配と Hessian は、ロバストな推定器に置き換えられる。
また,共役勾配法に基づくニュートン方向のロバストな解を求めるアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-30T18:54:54Z) - Statistical Inference of Constrained Stochastic Optimization via
Sketched Sequential Quadratic Programming [59.36379287247961]
この問題を解決するために,完全オンライン逐次2次プログラミング(StoSQP)手法を開発した。
最近の数値二階法の設計により、StoSQPは任意のランダムなステップサイズを適応的に選択できる。
また,2次法の計算コストを大幅に削減するため,StoSQPはランダム化反復解法を用いて2次プログラムを不正確に解けるようにした。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z) - Hessian Averaging in Stochastic Newton Methods Achieves Superlinear
Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。
最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文 参考訳(メタデータ) (2022-04-20T07:14:21Z) - Convergence of First-Order Methods for Constrained Nonconvex
Optimization with Dependent Data [7.513100214864646]
収束$tildeO(t-1/4)$とMoreautildeO(vareps-4)$がスムーズな非最適化のために最悪の場合の複雑性を示す。
適応的なステップサイズと最適収束度を持つ投影勾配法に基づく従属データに対する最初のオンライン非負行列分解アルゴリズムを得る。
論文 参考訳(メタデータ) (2022-03-29T17:59:10Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳(メタデータ) (2022-02-26T19:10:48Z) - Newton-LESS: Sparsification without Trade-offs for the Sketched Newton
Update [88.73437209862891]
2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。
本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。
ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
論文 参考訳(メタデータ) (2021-07-15T17:33:05Z) - 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) - Carath\'eodory Sampling for Stochastic Gradient Descent [79.55586575988292]
本稿では,Tchakaloff と Carath'eodory の古典的な結果から着想を得た手法を提案する。
我々は、測定値の低減を行う降下ステップを適応的に選択する。
これをBlock Coordinate Descentと組み合わせることで、測定の削減を極めて安価に行えるようにします。
論文 参考訳(メタデータ) (2020-06-02T17:52:59Z) - Stochastic Subspace Cubic Newton Method [14.624340432672172]
本稿では,高次元凸関数$f$を最小化するランダム化二階最適化アルゴリズムを提案する。
ミニバッチサイズが変化するにつれて、SSCNのグローバル収束速度は座標降下速度(CD)と立方正規化ニュートン速度とを補間することを示した。
注目すべきことに、SSCN の局所収束速度は、次数関数 $frac12 (x-x*)top nabla2f(x*)(x-x*)$ の最小化問題に適用される部分空間降下率と一致する。
論文 参考訳(メタデータ) (2020-02-21T19:42:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。