論文の概要: DRSOM: A Dimension Reduced Second-Order Method
- arxiv url: http://arxiv.org/abs/2208.00208v3
- Date: Sun, 2 Jul 2023 16:11:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-04 15:58:45.803423
- Title: DRSOM: A Dimension Reduced Second-Order Method
- Title(参考訳): DRSOM:次元還元2次法
- Authors: Chuwen Zhang, Dongdong Ge, Chang He, Bo Jiang, Yuntian Jiang, Yinyu Ye
- Abstract要約: 信頼的な枠組みの下では,2次法の収束を保ちながら,数方向の情報のみを用いる。
理論的には,この手法は局所収束率と大域収束率が$O(epsilon-3/2)$であり,第1次条件と第2次条件を満たすことを示す。
- 参考スコア(独自算出の注目度): 13.778619250890406
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: In this paper, we propose a Dimension-Reduced Second-Order Method (DRSOM) for
convex and nonconvex (unconstrained) optimization. Under a trust-region-like
framework, our method preserves the convergence of the second-order method
while using only curvature information in a few directions. Consequently, the
computational overhead of our method remains comparable to the first-order such
as the gradient descent method. Theoretically, we show that the method has a
local quadratic convergence and a global convergence rate of
$O(\epsilon^{-3/2})$ to satisfy the first-order and second-order conditions if
the subspace satisfies a commonly adopted approximated Hessian assumption. We
further show that this assumption can be removed if we perform a corrector step
using a Krylov-like method periodically at the end stage of the algorithm. The
applicability and performance of DRSOM are exhibited by various computational
experiments, including $L_2 - L_p$ minimization, CUTEst problems, and sensor
network localization.
- Abstract(参考訳): 本稿では,凸および非凸(非拘束)最適化のための次元縮小二階法(drsom)を提案する。
信頼領域的な枠組みの下では, 曲率情報のみを数方向で使用しながら, 第二次手法の収束を保っている。
その結果, 本手法の計算オーバーヘッドは勾配降下法のような一階法に匹敵することがわかった。
理論的には、この方法では局所二次収束と大域収束率を o(\epsilon^{-3/2})$ とすることで、部分空間が一般に採用されている近似ヘッセンの仮定を満たすならば、一階および二階の条件を満たすことができる。
さらに,アルゴリズムの終了段階において,krylovのような手法を周期的に使用して修正ステップを行えば,この仮定を除去できることを示す。
DRSOMの適用性と性能は、$L_2 - L_p$最小化、CUTEst問題、センサネットワークのローカライゼーションなど、様々な計算実験によって示されている。
関連論文リスト
- Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - Stochastic Dimension-reduced Second-order Methods for Policy
Optimization [11.19708535159457]
各イテレーションにおいて勾配とヘシアンベクトル積のみを必要とするポリシー最適化のための新しい2次アルゴリズムを提案する。
具体的には、投影された2次元信頼領域のサブプロブレムを繰り返す次元還元二階法(DR-SOPO)を提案する。
DR-SOPOはおよそ1次定常状態に到達するために$mathcalO(epsilon-3.5)$の複雑さが得られることを示す。
さらに,拡張アルゴリズム (DVR-SOPO) を提案する。
論文 参考訳(メタデータ) (2023-01-28T12:09:58Z) - A Fully First-Order Method for Stochastic Bilevel Optimization [8.663726907303303]
一階勾配オラクルのみが利用できる場合、制約のない二段階最適化問題を考える。
完全一階近似法(F2SA)を提案し,その非漸近収束特性について検討する。
MNISTデータハイパクリーニング実験において,既存の2次手法よりも提案手法の実用性能が優れていることを示す。
論文 参考訳(メタデータ) (2023-01-26T05:34:21Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳(メタデータ) (2023-01-10T12:18:47Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Accelerated first-order methods for convex optimization with locally
Lipschitz continuous gradient [0.0]
まず,Lipschitz連続勾配 (LLCG) を用いた非拘束凸最適化について検討し,それを解決するための加速近位勾配 (APG) 法を提案する。
提案手法は検証可能な終端基準を備えており、演算複雑性は$cal O(varepsilon-1/2log varepsilon-1)$である。
提案手法の性能を実証するために,予備的な数値計算結果を示す。
論文 参考訳(メタデータ) (2022-06-02T10:34:26Z) - Nesterov Accelerated Shuffling Gradient Method for Convex Optimization [15.908060383231371]
このアルゴリズムは,統一シャッフル方式を用いて,$mathcalO (1/T)$の改善率を示す。
我々の収束解析は有界領域や有界勾配条件に関する仮定を必要としない。
数値シミュレーションはアルゴリズムの効率を実証する。
論文 参考訳(メタデータ) (2022-02-07T21:23:17Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳(メタデータ) (2021-10-28T14:19:30Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳(メタデータ) (2020-06-10T15:00:09Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳(メタデータ) (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。