論文の概要: Fast Projected Newton-like Method for Precision Matrix Estimation under
Total Positivity
- arxiv url: http://arxiv.org/abs/2112.01939v4
- Date: Mon, 23 Oct 2023 02:55:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-25 15:27:41.825334
- Title: Fast Projected Newton-like Method for Precision Matrix Estimation under
Total Positivity
- Title(参考訳): 全正負の精度行列推定のための高速射影ニュートン様法
- Authors: Jian-Feng Cai, Jos\'e Vin\'icius de M. Cardoso, Daniel P. Palomar,
Jiaxi Ying
- Abstract要約: 現在のアルゴリズムはブロック座標降下法や近点アルゴリズムを用いて設計されている。
本稿では,2次元投影法に基づく新しいアルゴリズムを提案し,慎重に設計された探索方向と変数分割方式を取り入れた。
合成および実世界のデータセットに対する実験結果から,提案アルゴリズムは最先端の手法と比較して計算効率を著しく向上させることを示した。
- 参考スコア(独自算出の注目度): 15.023842222803058
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of estimating precision matrices in Gaussian
distributions that are multivariate totally positive of order two
($\mathrm{MTP}_2$). The precision matrix in such a distribution is an M-matrix.
This problem can be formulated as a sign-constrained log-determinant program.
Current algorithms are designed using the block coordinate descent method or
the proximal point algorithm, which becomes computationally challenging in
high-dimensional cases due to the requirement to solve numerous nonnegative
quadratic programs or large-scale linear systems. To address this issue, we
propose a novel algorithm based on the two-metric projection method,
incorporating a carefully designed search direction and variable partitioning
scheme. Our algorithm substantially reduces computational complexity, and its
theoretical convergence is established. Experimental results on synthetic and
real-world datasets demonstrate that our proposed algorithm provides a
significant improvement in computational efficiency compared to the
state-of-the-art methods.
- Abstract(参考訳): 次数 2 (\mathrm{mtp}_2$) の完全正の多変量ガウス分布における精度行列の推定問題について検討する。
そのような分布における精度行列はm行列である。
この問題は、符号制約付きログ決定プログラムとして定式化することができる。
現在のアルゴリズムはブロック座標降下法や近点アルゴリズムを用いて設計されており、多くの非負の二次プログラムや大規模線形系を解く必要があるため、高次元の場合では計算が困難になる。
そこで本研究では, 注意深く設計した探索方向と可変分割スキームを組み込んだ2次元投影法に基づく新しいアルゴリズムを提案する。
本アルゴリズムは計算複雑性を大幅に低減し,その理論的収束を確立する。
合成および実世界のデータセットにおける実験結果から,提案手法は最先端手法に比べて計算効率が著しく向上することが示された。
関連論文リスト
- Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization [26.36906884097317]
我々は,リプシッツ,凸関数を次数次オラクルで最小化するための新しい並列アルゴリズムを開発した。
その結果,最もよく知られた問合せ深度と並列アルゴリズムの最もよく知られた計算深度とのギャップを埋めることができた。
論文 参考訳(メタデータ) (2024-06-11T15:41:48Z) - Randomized Algorithms for Symmetric Nonnegative Matrix Factorization [2.1753766244387402]
対称非負行列因子化(SymNMF)は、データ解析と機械学習における技術である。
計算のためのランダム化アルゴリズムを2つ開発した。
提案手法は, 解法の品質を概ね維持し, 大規模疎水化問題と大規模疎水化問題の両方に対して, 大幅な高速化を実現する。
論文 参考訳(メタデータ) (2024-02-13T00:02:05Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳(メタデータ) (2023-07-17T20:11:56Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳(メタデータ) (2023-01-30T15:46:39Z) - Matrix Reordering for Noisy Disordered Matrices: Optimality and
Computationally Efficient Algorithms [9.245687221460654]
単細胞生物学とメダゲノミクスの応用により,ノイズモノトンToeplitz行列モデルに基づく行列化の問題を考察した。
我々は、決定理論の枠組みでこの問題の基本的な統計的限界を確立し、制約付き最小二乗率を示す。
そこで本研究では,性能向上を保証した新しい時間適応ソートアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-01-17T14:53:52Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳(メタデータ) (2020-06-10T15:00:09Z) - SONIA: A Symmetric Blockwise Truncated Optimization Algorithm [2.9923891863939938]
本研究は, 経験的リスクに対する新しいアルゴリズムを提案する。
このアルゴリズムは、一部分空間における二階探索型更新を計算し、1階探索法と2階探索法の間のギャップを埋める。
論文 参考訳(メタデータ) (2020-06-06T19:28:14Z) - Estimating Multiple Precision Matrices with Cluster Fusion
Regularization [0.90238471756546]
異なるクラスから複数の精度行列を推定するペナライズされた可能性を提案する。
既存の手法の多くは、精度行列間の関係に関する情報を含まないか、あるいはこの情報を先入観として要求する。
論文 参考訳(メタデータ) (2020-03-01T01:03:22Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳(メタデータ) (2020-02-21T17:45:32Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳(メタデータ) (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。