論文の概要: Sharp Global Guarantees for Nonconvex Low-Rank Matrix Recovery in the Overparameterized Regime

• arxiv url: http://arxiv.org/abs/2104.10790v1
• Date: Wed, 21 Apr 2021 23:07:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2021-04-23 14:02:04.819466
• Title: Sharp Global Guarantees for Nonconvex Low-Rank Matrix Recovery in the Overparameterized Regime
• Title（参考訳）: 過パラメータ化レジームにおける非凸低ランクマトリックス回復のためのシャープグローバル保証
• Authors: Richard Y. Zhang
• Abstract要約: 我々は,非低位行列の回復が局所的な極小を含まないことを証明した。 RIP 定数 $delta1/2$ は、$rstarle r$ に対する明示的な制御がなければ、ランク-$r$基底真理の正確な回復に必要かつ十分である。
• 参考スコア（独自算出の注目度）: 16.422215672356167
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove that it is possible for nonconvex low-rank matrix recovery to contain no spurious local minima when the rank of the unknown ground truth $r^{\star}<r$ is strictly less than the search rank $r$, and yet for the claim to be false when $r^{\star}=r$. Under the restricted isometry property (RIP), we prove, for the general overparameterized regime with $r^{\star}\le r$, that an RIP constant of $\delta<1/(1+\sqrt{r^{\star}/r})$ is sufficient for the inexistence of spurious local minima, and that $\delta<1/(1+1/\sqrt{r+r^{\star}-1})$ is necessary due to existence of counterexamples. Without an explicit control over $r^{\star}\le r$, an RIP constant of $\delta<1/2$ is both necessary and sufficient for the exact recovery of a rank-$r$ ground truth. But if the ground truth is known a priori to have $r^{\star}=1$, then the sharp RIP threshold for exact recovery is improved to $\delta<1/(1+1/\sqrt{r})$.
• Abstract（参考訳）: 未知基底真理 $r^{\star}<r$ のランクがサーチランク $r$ よりも厳密に小さいとき、非凸な低ランク行列のリカバリが可能であり、しかも $r^{\star}=r$ のとき、クレームは偽であることを示す。 制限等方性 (RIP) の下では、r^{\star}\le r$ の一般的な過パラメータ化された状態に対して、$\delta<1/(1+\sqrt{r^{\star}/r})$ の RIP 定数は急激な局所ミニマの不存在に十分であり、$\delta<1/(1+1/\sqrt{r+r^{\star}-1})$ は反例の存在のために必要であることを示す。 r^{\star}\le r$ に対する明示的な制御がなければ、$\delta<1/2$ の RIP 定数は、階数-$r$基底真理の正確な回復に必要かつ十分である。 しかし、もし基底真理が$r^{\star}=1$を持つという事前条件が知られているなら、正確な回復のための鋭いRIP閾値は$\delta<1/(1+1/\sqrt{r})$に改善される。

関連論文リスト

• Near-Optimal Sample Complexity for Iterated CVaR Reinforcement Learning with a Generative Model [13.582475656749775]
  リスクに敏感な強化学習(RL)のサンプル複雑性問題を生成モデルを用いて検討する。 この問題のサンプル複雑性に基づいて,上界と下界にほぼ一致する境界を定めている。
  論文  参考訳（メタデータ） (2025-03-11T22:31:03Z)
• Low-rank Matrix Bandits with Heavy-tailed Rewards [55.03293214439741]
  アンダーライン重み付きアンダーラインリワード(LowHTR)を用いたアンダーラインローランク行列バンディットの問題点について検討する。 観測されたペイオフに対するトランケーションと動的探索を利用して,LOTUSと呼ばれる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-26T21:54:31Z)
• Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion [21.846732043706318]
  バニラ勾配降下は、明示的な正則化を必要とせず、必ず基底真理$rmXstar$に収束することを示す。 驚くべきことに、収束率も最終的な精度もオーバーパラメータ化された検索ランク$r'$に依存しておらず、それらは真のランク$r$によってのみ支配される。
  論文  参考訳（メタデータ） (2024-02-09T19:39:23Z)
• Implicit bias of SGD in $L_{2}$-regularized linear DNNs: One-way jumps from high to low rank [22.850359181621023]
  行列補完のようなタスクでは、トレーニングデータに適合する最小限のランクで局所最小値に収束することが目標である。 SGDでは、常に上位から下位にジャンプする確率があるが、後退する確率はゼロである。
  論文  参考訳（メタデータ） (2023-05-25T13:17:32Z)
• On the Optimality of Misspecified Kernel Ridge Regression [13.995944403996566]
  我々は、$mathcalH$がソボレフ RKHS であるとき、KRR が任意の$sin (0,1)$に対して最小値であることを示す。
  論文  参考訳（メタデータ） (2023-05-12T04:12:12Z)
• Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
  本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。 ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。 我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
  論文  参考訳（メタデータ） (2023-02-07T02:22:31Z)
• Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization [10.787390511207683]
  二つの微分可能な$L$-smooth, $mu$-strongly convex objective $phimph over a $ntimes n$frac14(L/mu-1)2rstar$を考える。 非局所性にもかかわらず、局所最適化は、任意の初期点から大域的最適点へグローバルに収束することが保証される。
  論文  参考訳（メタデータ） (2022-07-05T03:18:17Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。 我々はこの$d$への依存が対数的要因まで最適であることを示す。 また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
  論文  参考訳（メタデータ） (2021-11-09T00:20:01Z)
• Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
  我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。 規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
  論文  参考訳（メタデータ） (2021-05-31T16:10:49Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。 Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
  論文  参考訳（メタデータ） (2020-05-22T16:55:01Z)

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

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