論文の概要: Can Learning Be Explained By Local Optimality In Low-rank Matrix Recovery?

• arxiv url: http://arxiv.org/abs/2302.10963v2
• Date: Sun, 10 Dec 2023 20:13:45 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-13 03:08:47.138263
• Title: Can Learning Be Explained By Local Optimality In Low-rank Matrix Recovery?
• Title（参考訳）: 学習は低位行列回復における局所的最適性によって説明できるか?
• Authors: Jianhao Ma, Salar Fattahi
• Abstract要約: 本研究では,低ランク行列回復,行列補完,行列センシングについて検討した。 真の解は、穏やかな条件下でのテキストリクトサドルポイントとして現れる。 行列の完備化において、わずかにランクの過大評価と穏やかなノイズがあったとしても、真の解は非臨界あるいは厳密なサドル点として現れる。
• 参考スコア（独自算出の注目度）: 21.846732043706318
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We explore the local landscape of low-rank matrix recovery, aiming to reconstruct a $d_1\times d_2$ matrix with rank $r$ from $m$ linear measurements, some potentially noisy. When the true rank is unknown, overestimation is common, yielding an over-parameterized model with rank $k\geq r$. Recent findings suggest that first-order methods with the robust $\ell_1$-loss can recover the true low-rank solution even when the rank is overestimated and measurements are noisy, implying that true solutions might emerge as local or global minima. Our paper challenges this notion, demonstrating that, under mild conditions, true solutions manifest as \textit{strict saddle points}. We study two categories of low-rank matrix recovery, matrix completion and matrix sensing, both with the robust $\ell_1$-loss. For matrix sensing, we uncover two critical transitions. With $m$ in the range of $\max\{d_1,d_2\}r\lesssim m\lesssim \max\{d_1,d_2\}k$, none of the true solutions are local or global minima, but some become strict saddle points. As $m$ surpasses $\max\{d_1,d_2\}k$, all true solutions become unequivocal global minima. In matrix completion, even with slight rank overestimation and mild noise, true solutions either emerge as non-critical or strict saddle points.
• Abstract（参考訳）: 低ランクマトリックスリカバリのローカルランドスケープを探求し、$m$線形測定値から$r$で$d_1\times d_2$マトリックスを再構築することを目的としている。 真のランクが不明な場合、過剰推定は一般的であり、ランク $k\geq r$ の過剰パラメータモデルが得られる。 近年の研究では、ロバストな$\ell_1$-lossを持つ一階法は、ランクが過大評価され、測定がうるさく、真の解が局所的あるいは大域的ミニマとして現れる可能性を示している。 本論文は, 穏やかな条件下では, 真の解が「textit{strict saddle points}」として現れることを示す。 我々は,ロバストな$\ell_1$-loss と低ランク行列回復,行列完成,行列センシングの2つのカテゴリについて検討した。 マトリックスセンシングでは、2つの臨界遷移を明らかにする。 m$ の範囲は $\max\{d_1,d_2\}r\lesssim m\lesssim \max\{d_1,d_2\}k$ の範囲であり、真の解はいずれも局所的あるいは大域的でない。 m$ が $\max\{d_1,d_2\}k$ を超えると、すべての真の解は無意味なグローバルミニマになる。 行列の完備化において、わずかなランクの過大評価と穏やかなノイズであっても、真の解は非臨界点または厳密な鞍点として現れる。

関連論文リスト

• 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)

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

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