論文の概要: Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decomposition

• arxiv url: http://arxiv.org/abs/2204.14067v3
• Date: Tue, 17 Dec 2024 07:39:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-18 13:54:25.171237
• Title: Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decomposition
• Title（参考訳）: Burer-Monteiro分解による加速核ノルム正規化低ランク行列最適化
• Authors: Ching-pei Lee, Ling Liang, Tianyun Tang, Kim-Chuan Toh,
• Abstract要約: 凸正規化および低ランク行列問題に対する高速BM-Globalを提案する。 BM-Globalは、原子力ノーミライザを含む低ランク問題に対する最先端のアルゴリズムよりも高速である。
• 参考スコア（独自算出の注目度）: 11.829012707752696
• License:
• Abstract: This work proposes a rapid algorithm, BM-Global, for nuclear-norm-regularized convex and low-rank matrix optimization problems. BM-Global efficiently decreases the objective value via low-cost steps leveraging the nonconvex but smooth Burer-Monteiro (BM) decomposition, while effectively escapes saddle points and spurious local minima ubiquitous in the BM form to obtain guarantees of fast convergence rates to the global optima of the original nuclear-norm-regularized problem through aperiodic inexact proximal gradient steps on it. The proposed approach adaptively adjusts the rank for the BM decomposition and can provably identify an optimal rank for the BM decomposition problem automatically in the course of optimization through tools of manifold identification. BM-Global hence also spends significantly less time on parameter tuning than existing matrix-factorization methods, which require an exhaustive search for finding this optimal rank. Extensive experiments on real-world large-scale problems of recommendation systems, regularized kernel estimation, and molecular conformation confirm that BM-Global can indeed effectively escapes spurious local minima at which existing BM approaches are stuck, and is a magnitude faster than state-of-the-art algorithms for low-rank matrix optimization problems involving a nuclear-norm regularizer. Based on this research, we have released an open-source package of the proposed BM-Global at https://www.github.com/leepei/BM-Global/.
• Abstract（参考訳）: 本研究は,核ノルム正規化凸問題と低ランク行列最適化問題に対する高速アルゴリズムBM-Globalを提案する。 BM-Global は非凸だが滑らかなBurer-Monteiro (BM) 分解を利用した低コストのステップで目的値を効率よく減少させると同時に、BM 形式のサドル点や急激な局所ミニマを効果的に回避し、その上の周期的不規則な近位勾配ステップを通じて原核-ノルム-正則化問題の大域的最適値への高速収束率の保証を得る。 提案手法は、BM分解のランクを適応的に調整し、多様体識別のツールを用いて最適化の過程でBM分解問題の最適ランクを自動同定することができる。 したがって、BM-Globalは既存の行列分解法よりもパラメータチューニングに要する時間をはるかに少なくし、この最適ランクを見つけるには徹底的な探索が必要である。 推奨システムの大規模問題、正規化カーネル推定、分子配座に関する大規模な実験により、BM-Globalは既存のBMアプローチが停滞している局所最小値から効果的に逃れることができ、核ノルム正規化器を含む低ランク行列最適化問題に対する最先端のアルゴリズムよりも格段に高速であることを確認した。 本研究に基づき,提案されているBM-Globalのオープンソースパッケージをhttps://www.github.com/leepei/BM-Global/で公開した。

関連論文リスト

• A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning [74.80956524812714]
  我々は,現代のディープラーニングにおいて広く普及している一般的なメタ学習問題に対処する。 これらの問題は、しばしばBi-Level Optimizations (BLO)として定式化される。 我々は,与えられたBLO問題を,内部損失関数が滑らかな分布となり,外損失が内部分布に対する期待損失となるようなii最適化に変換することにより,新たな視点を導入する。
  論文  参考訳（メタデータ） (2024-10-14T12:10:06Z)
• Tailed Low-Rank Matrix Factorization for Similarity Matrix Completion [14.542166904874147]
  similarity Completion Matrixは多くの機械学習タスクの中核にある基本的なツールとして機能する。 この問題に対処するために、類似行列理論(SMC)法が提案されているが、それらは複雑である。 提案手法は,PSD特性を解析して推定プロセスを導出し,低ランク解を保証するために非低ランク正規化器を組み込む2つの新しい,スケーラブルで効果的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-29T04:27:23Z)
• Block Majorization Minimization with Extrapolation and Application to $\beta$-NMF [17.97403029273243]
  マルチ最適化問題のクラスを解くために,外挿法 (BMMe) を用いたブロック行列化最小化法を提案する。 本稿では,Bregman分散を適応的に更新することにより,BMMeのブロック偏極パラメータをブロックミラー法として再構成可能であることを示す。 広範囲な実験を通じて,$beta$NMF に対する有意な加速 BM を実証的に説明する。
  論文  参考訳（メタデータ） (2024-01-12T15:52:02Z)
• On the Global Solution of Soft k-Means [159.23423824953412]
  本稿では,ソフトk-平均問題の解法を全世界で提案する。 ミニマルボリュームソフトkMeans (MVSkM) と呼ばれる新しいモデルを提案する。
  論文  参考訳（メタデータ） (2022-12-07T12:06:55Z)
• Optimization of Annealed Importance Sampling Hyperparameters [77.34726150561087]
  Annealed Importance Smpling (AIS) は、深層生成モデルの難易度を推定するために使われる一般的なアルゴリズムである。 本稿では、フレキシブルな中間分布を持つパラメータAISプロセスを提案し、サンプリングに少ないステップを使用するようにブリッジング分布を最適化する。 我々は, 最適化AISの性能評価を行い, 深部生成モデルの限界推定を行い, 他の推定値と比較した。
  論文  参考訳（メタデータ） (2022-09-27T07:58:25Z)
• Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods [18.16094563534453]
  Burer-Monteiro (B-M) 因数分解法は, RIP条件下での低ランク行列最適化問題を効率的に解けることが知られている。 情報理論の複雑さが低い低ランク行列最適化問題に対して、B-M分解に基づく手法が成功するかどうかを問うのは当然である。
  論文  参考訳（メタデータ） (2021-10-19T21:52:14Z)
• Fast Batch Nuclear-norm Maximization and Minimization for Robust Domain Adaptation [154.2195491708548]
  ランダムに選択されたデータバッチの分類出力行列の構造について検討し,予測可能性と多様性について検討した。 本稿では,目標出力行列上で核ノルムを行い,目標予測能力を向上するBatch Nuclear-norm Maximization and Minimizationを提案する。 実験により,本手法は3つの典型的なドメイン適応シナリオにおいて適応精度とロバスト性を高めることができることが示された。
  論文  参考訳（メタデータ） (2021-07-13T15:08:32Z)
• Rotation Coordinate Descent for Fast Globally Optimal Rotation Averaging [47.3713707521106]
  回転座標降下 (RCD) と呼ばれる世界最適性を実現する高速アルゴリズムを提案する。 半定値行列を行ごと更新することでSDPを解くブロック座標降下(BCD)とは異なり、RCDは繰り返しを通して全ての有効な回転を直接維持・更新する。 我々は数学的にアルゴリズムの収束を証明し、最先端のグローバル手法よりも優れた効率を示す。
  論文  参考訳（メタデータ） (2021-03-15T11:31:34Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。 提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
  論文  参考訳（メタデータ） (2020-12-04T15:46:30Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Low-Rank Factorization for Rank Minimization with Nonconvex Regularizers [0.0]
  核ノルムへの凸緩和を最小化することは、推奨システムと堅牢な主成分分析に重要である。 本研究では, ブイロとルクシロによる核プログラムのランク因数分解のための効率的なアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-06-13T19:04:37Z)

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

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