論文の概要: 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問題、センサネットワークのローカライゼーションなど、様々な計算実験によって示されている。

関連論文リスト

• A Historical Trajectory Assisted Optimization Method for Zeroth-Order Federated Learning [24.111048817721592]
  フェデレートラーニングは分散勾配降下技術に大きく依存している。 勾配情報が得られない状況では、勾配をゼロ次情報から推定する必要がある。 勾配推定法を改善するための非等方的サンプリング法を提案する。
  論文  参考訳（メタデータ） (2024-09-24T10:36:40Z)
• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
  ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。 複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。 本稿では,ZPDVR法とZPDVR法を提案する。
  論文  参考訳（メタデータ） (2024-05-28T02:27:53Z)
• 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)
• 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 [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning [13.908826484332282]
  最適化問題の解法として,新しい2段階勾配法を提案する。 最初の貢献は、提案した2時間スケール勾配アルゴリズムの有限時間複雑性を特徴づけることである。 我々は、強化学習における勾配に基づく政策評価アルゴリズムに適用する。
  論文  参考訳（メタデータ） (2021-09-29T23:15:23Z)
• 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)

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

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