論文の概要: On the Optimization Landscape of Burer-Monteiro Factorization: When do Global Solutions Correspond to Ground Truth?

• arxiv url: http://arxiv.org/abs/2302.10963v1
• Date: Tue, 21 Feb 2023 19:47:31 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-23 17:22:32.224355
• Title: On the Optimization Landscape of Burer-Monteiro Factorization: When do Global Solutions Correspond to Ground Truth?
• Title（参考訳）: burer-monteiro因子分解の最適化の展望について--グローバルソリューションはいつ基底的真理に対応するのか?
• Authors: Jianhao Ma, Salar Fattahi
• Abstract要約: 低ランク行列のリカバリでは、リニアでノイズの多い測定値が限られているため、低ランク行列のリカバリが目的である。 ノイズ測定では,過大推定BMの解が真の解ともはや一致しないことが示される。
• 参考スコア（独自算出の注目度）: 4.7464518249313805
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In low-rank matrix recovery, the goal is to recover a low-rank matrix, given a limited number of linear and possibly noisy measurements. Low-rank matrix recovery is typically solved via a nonconvex method called Burer-Monteiro factorization (BM). If the rank of the ground truth is known, BM is free of sub-optimal local solutions, and its true solutions coincide with the global solutions -- that is, the true solutions are identifiable. When the rank of the ground truth is unknown, it must be over-estimated, giving rise to an over-parameterized BM. In the noiseless regime, it is recently shown that over-estimation of the rank leads to progressively fewer sub-optimal local solutions while preserving the identifiability of the true solutions. In this work, we show that with noisy measurements, the global solutions of the over-parameterized BM no longer correspond to the true solutions, essentially transmuting over-parameterization from blessing to curse. In particular, we study two classes of low-rank matrix recovery, namely matrix completion and matrix sensing. For matrix completion, we show that even if the rank is only slightly over-estimated and with very mild assumptions on the noise, none of the true solutions are local or global solutions. For matrix sensing, we show that to guarantee the correspondence between global and true solutions, it is necessary and sufficient for the number of samples to scale linearly with the over-estimated rank, which can be drastically larger than its optimal sample complexity that only scales with the true rank.
• Abstract（参考訳）: 低ランクマトリックスのリカバリでは、リニアでうるさい測定値が限られているため、低ランクマトリックスのリカバリが目標である。 低ランク行列回復は通常、Burer-Monteiro factorization (BM)と呼ばれる非凸法によって解決される。 基底真理の階数が知られているならば、bm は準最適局所解を含まず、その真の解は大域的解(すなわち真の解は識別可能である)と一致する。 地上の真実のランクが不明な場合、過度に推定され、過度にパラメータ化されたBMが発生する。 無雑音環境において、最近、ランクの過大評価は、真の解の識別可能性を維持しつつ、漸進的に最適でない局所解を減少させることが示された。 本研究では, 過度パラメータ化BMの大域的解法は, 雑音測定によりもはや真の解と一致せず, 本質的には過度パラメータ化を祝福から呪いへと変化させることを示す。 特に,低位行列回復の2つのクラス,すなわち行列完成と行列センシングについて検討した。 行列の完備化について、ランクがわずかに過大評価され、ノイズに非常に穏やかな仮定があるとしても、真の解は局所解でも大域解でもないことを示す。 行列センシングでは,大域的解と真の解との対応を保証するためには,過大評価された階数と線形にスケールするサンプルの数が必要であり,真の階数にしか対応しない最適な試料複雑性よりも大幅に大きいことを示す。

関連論文リスト

• Low-rank Matrix Bandits with Heavy-tailed Rewards [55.03293214439741]
  アンダーライン重み付きアンダーラインリワード(LowHTR)を用いたアンダーラインローランク行列バンディットの問題点について検討する。 観測されたペイオフに対するトランケーションと動的探索を利用して,LOTUSと呼ばれる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-26T21:54:31Z)
• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
  論文  参考訳（メタデータ） (2024-02-24T06:36:08Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。 合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
  論文  参考訳（メタデータ） (2023-06-06T22:35:16Z)
• A General Algorithm for Solving Rank-one Matrix Sensing [15.543065204102714]
  マトリックスセンシングの目標は、一連の測定に基づいて、mathbbRn×n$の行列$A_starを復元することである。 本稿では、このランク-$kの仮定を緩和し、より一般的な行列センシング問題を解く。
  論文  参考訳（メタデータ） (2023-03-22T04:07:26Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Low-rank Matrix Recovery With Unknown Correspondence [62.634051913953485]
  我々は、M$の回復のために証明不可能な非漸近誤差を伴い、M$の適切な低ランク条件下で核ノルム最小化問題を解くことで、M$を回復可能であることを示す。 シミュレーションデータの実験、MovieLens 100KデータセットとYale Bデータベースは、$textM3textOがいくつかのベースラインで最先端のパフォーマンスを達成し、高精度な地上真実対応を回復できることを示した。
  論文  参考訳（メタデータ） (2021-10-15T09:27:50Z)
• Unique sparse decomposition of low rank matrices [17.037882881652617]
  低階行列Yin mathbbRrtimes n$ のユニークな分解が見つかる。 我々は、ある$Yin MathRrtimes n$が$Xin mathbbRrtimes n$のスパースワイズ分解であることを示す。
  論文  参考訳（メタデータ） (2021-06-14T20:05:59Z)
• Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries [4.230158563771147]
  低階行列補完のための新しい,単純で,計算効率のよい反復法を提案する。 我々のアルゴリズムは、R2RILS(R2RILS for rank $2r$peterative least squares)と呼ばれ、メモリ要件が低い。
  論文  参考訳（メタデータ） (2020-02-05T16:20:58Z)

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

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