論文の概要: Low-complexity subspace-descent over symmetric positive definite manifold

• arxiv url: http://arxiv.org/abs/2305.02041v1
• Date: Wed, 3 May 2023 11:11:46 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-04 15:03:45.391370
• Title: Low-complexity subspace-descent over symmetric positive definite manifold
• Title（参考訳）: 対称正定値多様体上の低複素部分空間線
• Authors: Yogesh Darmwal, Ketan Rajawat
• Abstract要約: 対称正定値多様体(SPD)上の関数の最小化のための低複素性アルゴリズムを開発する。 提案手法は、慎重に選択された部分空間を利用して、更新をイテレートのコレスキー因子とスパース行列の積として記述することができる。
• 参考スコア（独自算出の注目度）: 9.036025934093965
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work puts forth low-complexity Riemannian subspace descent algorithms for the minimization of functions over the symmetric positive definite (SPD) manifold. Different from the existing Riemannian gradient descent variants, the proposed approach utilizes carefully chosen subspaces that allow the update to be written as a product of the Cholesky factor of the iterate and a sparse matrix. The resulting updates avoid the costly matrix operations like matrix exponentiation and dense matrix multiplication, which are generally required in almost all other Riemannian optimization algorithms on SPD manifold. We further identify a broad class of functions, arising in diverse applications, such as kernel matrix learning, covariance estimation of Gaussian distributions, maximum likelihood parameter estimation of elliptically contoured distributions, and parameter estimation in Gaussian mixture model problems, over which the Riemannian gradients can be calculated efficiently. The proposed uni-directional and multi-directional Riemannian subspace descent variants incur per-iteration complexities of $\mathcal{O}(n)$ and $\mathcal{O}(n^2)$ respectively, as compared to the $\mathcal{O}(n^3)$ or higher complexity incurred by all existing Riemannian gradient descent variants. The superior runtime and low per-iteration complexity of the proposed algorithms is also demonstrated via numerical tests on large-scale covariance estimation problems.
• Abstract（参考訳）: この研究は、対称正定値(spd)多様体上の関数の最小化のための低複素リーマン部分空間降下アルゴリズムをもたらす。 既存のリーマン勾配降下変種と異なり、提案手法は慎重に選択された部分空間を利用して、更新をイテレートのコレスキー因子とスパース行列の積として記述することができる。 結果として得られる更新は、spd多様体上のほとんど全てのリーマン最適化アルゴリズムで一般的に必要とされる行列指数や密行列乗法のようなコストのかかる行列演算を避ける。 さらに,多種多様な応用,例えば,カーネル・マトリックス・ラーニング,ガウス分布の共分散推定,楕円曲線分布の最大確率パラメータ推定,およびリーマン勾配を効率的に計算できるガウス混合モデル問題におけるパラメータ推定を同定する。 提案された一方向および多方向のリーマン部分空間降下変種は、既存のリーマン勾配降下変種すべてによって引き起こされる$\mathcal{o}(n)$ と$\mathcal{o}(n^2)$ の共役関係をそれぞれ負う。 また, 大規模共分散推定問題に対する数値実験により, 提案アルゴリズムの優れた実行時間と文毎の複雑性を実証した。

関連論文リスト

• Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees [6.422262171968397]
  ユークリッド距離幾何学問題を解くために2つのアルゴリズムが提案されている。 第一のアルゴリズムは真の解に線形に収束する。 第2のアルゴリズムは、合成データと実データの両方で強い数値性能を示す。
  論文  参考訳（メタデータ） (2024-10-08T21:19:22Z)
• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• Riemannian coordinate descent algorithms on matrix manifolds [12.05722932030768]
  行列多様体上で計算効率の良い座標降下(CD)アルゴリズムを開発するための一般的なフレームワークを提供する。 我々は、Stiefel, Grassmann, (Generalized) hyperbolic, symplectic, and symmetric positive (semi) definite などの多様体に対するCDアルゴリズムを提案する。 我々はそれらの収束と複雑性を分析し、いくつかのアプリケーションでその効果を実証的に説明する。
  論文  参考訳（メタデータ） (2024-06-04T11:37:11Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Reducing the Variance of Gaussian Process Hyperparameter Optimization with Preconditioning [54.01682318834995]
  プレコンディショニングは、行列ベクトル乗算を含む反復的な方法にとって非常に効果的なステップである。 プレコンディショニングには、これまで検討されていなかった付加的なメリットがあることを実証する。 基本的に無視可能なコストで、同時に分散を低減することができる。
  論文  参考訳（メタデータ） (2021-07-01T06:43:11Z)
• Automatic differentiation for Riemannian optimization on low-rank matrix and tensor-train manifolds [71.94111815357064]
  科学計算および機械学習アプリケーションでは、行列およびより一般的な多次元配列(テンソル)は、しばしば低ランク分解の助けを借りて近似することができる。 低ランク近似を見つけるための一般的なツールの1つはリーマン最適化を使うことである。
  論文  参考訳（メタデータ） (2021-03-27T19:56:00Z)
• Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifold [7.257751371276488]
  R-ProxSGDとR-ProxSPBは、近位SGDと近位SpiderBoostの一般化である。 R-ProxSPBアルゴリズムは、オンラインの場合で$O(epsilon-3)$ IFOs、有限サムの場合は$O(n+sqrtnepsilon-3)$ IFOsである。
  論文  参考訳（メタデータ） (2020-05-03T23:41:35Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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