論文の概要: Escaping Spurious Local Minima of Low-Rank Matrix Factorization Through
Convex Lifting
- arxiv url: http://arxiv.org/abs/2204.14067v1
- Date: Fri, 29 Apr 2022 13:04:36 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-02 22:36:06.471077
- Title: Escaping Spurious Local Minima of Low-Rank Matrix Factorization Through
Convex Lifting
- Title(参考訳): 凸浮揚による低ランク行列因子分解のスプリアス局所最小化
- Authors: Ching-pei Lee, Ling Liang, Tianyun Tang, Kim-Chuan Toh
- Abstract要約: 本研究は,MF-Global と呼ばれる非低ランク行列分解(MF)問題に対する大域的高速解法を提案する。
コンベックスのステップを通じて,実世界のノイズの多いデータの中で,サドルやスプリケートな局所ミニマを効率的に回避する。
我々は,MF-Globalが既存のMFアプローチが定着している局所解を効果的に回避できることを示す。
- 参考スコア(独自算出の注目度): 10.76492224896965
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This work proposes a rapid global solver for nonconvex low-rank matrix
factorization (MF) problems that we name MF-Global. Through convex lifting
steps, our method efficiently escapes saddle points and spurious local minima
ubiquitous in noisy real-world data, and is guaranteed to always converge to
the global optima. Moreover, the proposed approach adaptively adjusts the rank
for the factorization and provably identifies the optimal rank for MF
automatically in the course of optimization through tools of manifold
identification, and thus it also spends significantly less time on parameter
tuning than existing MF methods, which require an exhaustive search for this
optimal rank. On the other hand, when compared to methods for solving the
lifted convex form only, MF-Global leads to significantly faster convergence
and much shorter running time. Experiments on real-world large-scale
recommendation system problems confirm that MF-Global can indeed effectively
escapes spurious local solutions at which existing MF approaches stuck, and is
magnitudes faster than state-of-the-art algorithms for the lifted convex form.
- Abstract(参考訳): 本研究は,MF-Global と呼ばれる非凸低ランク行列分解(MF)問題に対する高速大域的解法を提案する。
対流昇降ステップにより,ノイズの多い実世界データにおいて,サドルポイントとスプリアス局所ミニマを効率的に回避し,常にグローバルオプティマに収束することが保証される。
さらに,提案手法は因子化のランクを適応的に調整し,多様体識別ツールによる最適化の過程でMFの最適ランクを自動的に同定し,パラメータチューニングに要する時間を既存のMF法よりも大幅に短縮する。
一方、持ち上げられた凸形式のみを解く方法と比較すると、mf-globalは収束を大幅に高速化し、実行時間が大幅に短縮される。
実世界の大規模レコメンデーションシステム問題に関する実験では、MF-Globalが既存のMFアプローチが定着している急激な局所解を効果的に回避できることを確認した。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。