論文の概要: Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods

• arxiv url: http://arxiv.org/abs/2110.10279v1
• Date: Tue, 19 Oct 2021 21:52:14 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-22 18:24:41.715769
• Title: Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods
• Title（参考訳）: 低複素行列完備問題に対する因子化アプローチ--スプリアス解の指数関数数と勾配法の故障
• Authors: Baturalp Yalcin, Haixiang Zhang, Javad Lavaei, Somayeh Sojoudi
• Abstract要約: Burer-Monteiro (B-M) 因数分解法は, RIP条件下での低ランク行列最適化問題を効率的に解けることが知られている。 情報理論の複雑さが低い低ランク行列最適化問題に対して、B-M分解に基づく手法が成功するかどうかを問うのは当然である。
• 参考スコア（独自算出の注目度）: 18.16094563534453
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It is well-known that the Burer-Monteiro (B-M) factorization approach can efficiently solve low-rank matrix optimization problems under the RIP condition. It is natural to ask whether B-M factorization-based methods can succeed on any low-rank matrix optimization problems with a low information-theoretic complexity, i.e., polynomial-time solvable problems that have a unique solution. In this work, we provide a negative answer to the above question. We investigate the landscape of B-M factorized polynomial-time solvable matrix completion (MC) problems, which are the most popular subclass of low-rank matrix optimization problems without the RIP condition. We construct an instance of polynomial-time solvable MC problems with exponentially many spurious local minima, which leads to the failure of most gradient-based methods. Based on those results, we define a new complexity metric that potentially measures the solvability of low-rank matrix optimization problems based on the B-M factorization approach. In addition, we show that more measurements of the ground truth matrix can deteriorate the landscape, which further reveals the unfavorable behavior of the B-M factorization on general low-rank matrix optimization problems.
• Abstract（参考訳）: burer-monteiro(b-m)因子分解アプローチがrip条件下での低ランク行列最適化問題を効率的に解決できることはよく知られている。 B-M分解に基づく手法が、情報理論の複雑さの低い低ランク行列最適化問題、すなわちユニークな解法を持つ多項式時間可解問題で成功するかどうかを問うのは当然である。 本稿では、上記の質問に対する否定的な回答を提供する。 RIP条件のない低ランク行列最適化問題の最も一般的なサブクラスであるB-M因子化多項式時間可解行列完備化問題(MC)の展望について検討する。 指数関数的に多くの局所最小値を持つ多項式時間可解MC問題の例を構築し、ほとんどの勾配法が失敗する。 これらの結果に基づいて,b-m因子分解法に基づく低ランク行列最適化問題の可解性を測定する新しい複雑性指標を定義する。 さらに,基底真理行列のさらなる測定が景観を悪化させる可能性を示し,一般の低ランク行列最適化問題に対するb-m因子分解の不利な挙動を明らかにした。

関連論文リスト

• Tailed Low-Rank Matrix Factorization for Similarity Matrix Completion [14.542166904874147]
  similarity Completion Matrixは多くの機械学習タスクの中核にある基本的なツールとして機能する。 この問題に対処するために、類似行列理論(SMC)法が提案されているが、それらは複雑である。 提案手法は,PSD特性を解析して推定プロセスを導出し,低ランク解を保証するために非低ランク正規化器を組み込む2つの新しい,スケーラブルで効果的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-29T04:27:23Z)
• An inexact LPA for DC composite optimization and application to matrix completions with outliers [5.746154410100363]
  本稿では,複合最適化問題のクラスについて述べる。 合成構造を利用することで、ポテンシャル関数が反復列において1/2$のKL特性を持つ条件を与える。
  論文  参考訳（メタデータ） (2023-03-29T16:15:34Z)
• On the Global Solution of Soft k-Means [159.23423824953412]
  本稿では,ソフトk-平均問題の解法を全世界で提案する。 ミニマルボリュームソフトkMeans (MVSkM) と呼ばれる新しいモデルを提案する。
  論文  参考訳（メタデータ） (2022-12-07T12:06:55Z)
• Unitary Approximate Message Passing for Matrix Factorization [90.84906091118084]
  行列分解 (MF) を一定の制約で考慮し, 様々な分野の応用を見いだす。 我々は,効率の良いメッセージパッシング実装であるUAMPMFを用いて,MFに対するベイズ的アプローチを開発する。 UAMPMFは、回復精度、ロバスト性、計算複雑性の観点から、最先端のアルゴリズムを著しく上回ることを示す。
  論文  参考訳（メタデータ） (2022-07-31T12:09:32Z)
• Large-scale matrix optimization based multi microgrid topology design with a constrained differential evolution algorithm [30.792124441010447]
  非線形問題を解くために二項行列に基づく微分進化アルゴリズムを提案する。 制約に対処するため,環境選択戦略を改良した実現可能性ルールを提案する。
  論文  参考訳（メタデータ） (2022-07-18T00:35:29Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  我々は弱い教師付き回帰問題を解く。 weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。 数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
  論文  参考訳（メタデータ） (2021-04-13T23:21:01Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。 この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。 我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
  論文  参考訳（メタデータ） (2021-02-16T06:04:27Z)
• Meta-learning based Alternating Minimization Algorithm for Non-convex Optimization [9.774392581946108]
  複数変数の非プロブレムに挑戦する新しい解を提案する。 提案手法では,他の手法が一般的に失敗するケースに対して,効果的なイテレーションを実現することができる。
  論文  参考訳（メタデータ） (2020-09-09T10:45:00Z)
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method [47.80060761046752]
  ロバスト低ランク行列補完(RMC)は、コンピュータビジョン、信号処理、機械学習アプリケーションのために広く研究されている。 この問題は、部分的に観察された行列を低ランク行列とスパース行列の重ね合わせに分解することを目的とした。 RMCに取り組むために広く用いられるアプローチは、低ランク行列の核ノルム(低ランク性を促進するために)とスパース行列のl1ノルム(空間性を促進するために)を最小化する凸定式化を考えることである。 本稿では、近年のローワークの動機付けについて述べる。
  論文  参考訳（メタデータ） (2020-08-18T04:46:22Z)
• Follow the bisector: a simple method for multi-objective optimization [65.83318707752385]
  複数の異なる損失を最小化しなければならない最適化問題を考える。 提案手法は、各イテレーションにおける降下方向を計算し、目的関数の相対的減少を等しく保証する。
  論文  参考訳（メタデータ） (2020-07-14T09:50:33Z)

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

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