論文の概要: Approximate Secular Equations for the Cubic Regularization Subproblem

• arxiv url: http://arxiv.org/abs/2209.13268v1
• Date: Tue, 27 Sep 2022 09:22:44 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-28 16:44:13.954337
• Title: Approximate Secular Equations for the Cubic Regularization Subproblem
• Title（参考訳）: 立方体正則化サブプロブレムに対する近似系方程式
• Authors: Yihang Gao, Man-Chung Yue, Michael K. Ng
• Abstract要約: 立方正則化サブプロブレム(CRS)の新しい解法を提案する。 提案手法は2つの最先端手法より優れている。
• 参考スコア（独自算出の注目度）: 20.396963952753435
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The cubic regularization method (CR) is a popular algorithm for unconstrained non-convex optimization. At each iteration, CR solves a cubically regularized quadratic problem, called the cubic regularization subproblem (CRS). One way to solve the CRS relies on solving the secular equation, whose computational bottleneck lies in the computation of all eigenvalues of the Hessian matrix. In this paper, we propose and analyze a novel CRS solver based on an approximate secular equation, which requires only some of the Hessian eigenvalues and is therefore much more efficient. Two approximate secular equations (ASEs) are developed. For both ASEs, we first study the existence and uniqueness of their roots and then establish an upper bound on the gap between the root and that of the standard secular equation. Such an upper bound can in turn be used to bound the distance from the approximate CRS solution based ASEs to the true CRS solution, thus offering a theoretical guarantee for our CRS solver. A desirable feature of our CRS solver is that it requires only matrix-vector multiplication but not matrix inversion, which makes it particularly suitable for high-dimensional applications of unconstrained non-convex optimization, such as low-rank recovery and deep learning. Numerical experiments with synthetic and real data-sets are conducted to investigate the practical performance of the proposed CRS solver. Experimental results show that the proposed solver outperforms two state-of-the-art methods.
• Abstract（参考訳）: 立方正則化法(CR)は、制約のない非凸最適化のための一般的なアルゴリズムである。 各反復において、CRは立方正則化部分プロブレム(CRS)と呼ばれる立方正則化二次問題を解く。 CRSの解法の一つは、計算のボトルネックがヘッセン行列のすべての固有値の計算にある世俗方程式の解法に依存する。 本稿では, ヘッセン固有値のいくつかしか必要とせず, より効率的であるような, 近似的世俗方程式に基づく新しいCRS解法を提案し, 解析する。 2つの近似世俗方程式(ASE)が開発されている。 両 ases について,まず根の存在と一意性を研究し,次に標準世俗方程式の根と根の間のギャップの上界を確立する。 このような上限は、近似CRS解に基づくASEから真のCRS解への距離を束縛するために用いられるので、我々のCRS解法に理論的保証を与える。 CRSソルバの望ましい特徴は,行列ベクトル乗算のみを必要とするが,行列逆転は必要とせず,低ランクリカバリやディープラーニングといった非凸最適化の高次元的応用に特に適している点である。 合成および実データを用いた数値実験を行い,提案したCRSソルバの性能について検討した。 実験の結果,提案手法は2つの最先端手法より優れていた。

関連論文リスト

• Optimization without Retraction on the Random Generalized Stiefel Manifold [9.301728976515255]
  本稿では,B$のランダムな推定値にのみアクセスしながら,最適化問題を解く,安価な反復法を提案する。 我々の方法はすべての反復において制約を強制するのではなく、予想で定義される一般化されたスティーフェル多様体上の臨界点に収束する反復を生成する。
  論文  参考訳（メタデータ） (2024-05-02T19:55:30Z)
• A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization [107.07093621337084]
  正規化カット(N-Cut)は、スペクトルクラスタリングの有名なモデルである。 1)正規化ラプラシア行列の連続スペクトル埋め込みを計算する; 2)$K$-meansまたはスペクトル回転による離散化。 有名な座標降下法に基づく新しいN-Cut解法を提案する。
  論文  参考訳（メタデータ） (2023-11-26T07:11:58Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。 本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。 3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
  論文  参考訳（メタデータ） (2022-09-27T09:06:37Z)
• Optimal Diagonal Preconditioning: Theory and Practice [23.79536881427839]
  本稿では,列数や列数の最大化を同時に達成するために,最適対角前処理の問題を提案する。 実装が容易なベースライン分岐アルゴリズムを提案する。 次に, 片側最適対角前条件問題に特化し, 標準双対SDP問題として定式化できることを実証する。
  論文  参考訳（メタデータ） (2022-09-02T04:21:28Z)
• A Novel Fast Exact Subproblem Solver for Stochastic Quasi-Newton Cubic Regularized Optimization [0.38233569758620045]
  本稿では,大規模非制約最適化のための3乗法 (ARC) を用いた適応正規化について述べる。 我々の新しいアプローチであるARCLQNは、最小限のチューニングを伴うモダンと比較される。
  論文  参考訳（メタデータ） (2022-04-19T20:25:29Z)
• Low-Rank Updates of Matrix Square Roots [7.832944895330117]
  行列平方根と逆平方根演算を考える。 行列に対する低階摂動が与えられたとき、(逆)平方根に対する低階近似補正が存在すると論じる。 次に、その方程式に対する低ランク解をどのように計算するかについて議論する。
  論文  参考訳（メタデータ） (2022-01-31T12:05:33Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  我々は弱い教師付き回帰問題を解く。 weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。 数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
  論文  参考訳（メタデータ） (2021-04-13T23:21:01Z)
• Square Root Bundle Adjustment for Large-Scale Reconstruction [56.44094187152862]
  QR分解によるランドマーク変数のnullspace marginalizationに依存するバンドル調整問題の新たな定式化を提案する。 平方根束調整と呼ばれる私たちのアプローチは、一般的に使用されるSchur補完トリックと代数的に等価です。 BALデータセットを用いた実世界での実験では、提案されたソルバが単一の精度でも平均的等しく正確なソリューションで達成できることを示す。
  論文  参考訳（メタデータ） (2021-03-02T16:26:20Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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