論文の概要: 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})$に改善される。

関連論文リスト

• Optimal High-probability Convergence of Nonlinear SGD under Heavy-tailed Noise via Symmetrization [50.49466204159458]
  雑音対称性に基づく2つの新しい推定器を提案する。 よりシャープな分析と改善されたレートを提供します。 モーメントと対称雑音を仮定する作業と比較して、よりシャープな解析と改善率を提供する。
  論文  参考訳（メタデータ） (2025-07-12T00:31:13Z)
• Near-Optimal Sample Complexity for Iterated CVaR Reinforcement Learning with a Generative Model [13.582475656749775]
  リスクに敏感な強化学習(RL)のサンプル複雑性問題を生成モデルを用いて検討する。 この問題のサンプル複雑性に基づいて,上界と下界にほぼ一致する境界を定めている。
  論文  参考訳（メタデータ） (2025-03-11T22:31:03Z)
• Sample Complexity of Linear Quadratic Regulator Without Initial Stability [11.98212766542468]
  ReINFORCEに触発されて、未知のパラメータを持つ線形二次レギュレータ(LQR)問題に対して、新しい回帰水平アルゴリズムを導入する。 従来の手法とは異なり、本アルゴリズムはサンプルの複雑さの順序を同じに保ちながら、2点勾配推定に依存することを回避している。
  論文  参考訳（メタデータ） (2025-02-20T02:44:25Z)
• From Gradient Clipping to Normalization for Heavy Tailed SGD [19.369399536643773]
  最近の実証的な証拠は、機械学習の応用が重尾ノイズを伴い、実際に有界分散の標準的な仮定に挑戦していることを示している。 本稿では, 勾配依存型雑音収束問題において, テール雑音下での厳密性を実現することができることを示す。
  論文  参考訳（メタデータ） (2024-10-17T17:59:01Z)
• Efficient Low-rank Identification via Accelerated Iteratively Reweighted Nuclear Norm Minimization [8.879403568685499]
  パラメータの平滑化に適応的な更新戦略を導入する。 この振る舞いは、アルゴリズムを数回繰り返した後に、効果的に問題を解決するものに変えます。 すべてのイテレーションが重要なものであることを保証し、グローバルに提案された実験を証明します。
  論文  参考訳（メタデータ） (2024-06-22T02:37:13Z)
• A Universal Class of Sharpness-Aware Minimization Algorithms [57.29207151446387]
  我々は、新しいシャープネス尺度を導入し、新しいシャープネス対応目標関数を導出する。 これらの測度がテキスト的に表現可能であることを証明し、トレーニング損失ヘッセン行列の任意の関数を適切なハイパーおよび行列式で表すことを可能にする。
  論文  参考訳（メタデータ） (2024-06-06T01:52:09Z)
• 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)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
  論文  参考訳（メタデータ） (2023-11-04T11:12:24Z)
• Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
  勾配に基づくアルゴリズムであるProspectは、スムーズな正規化損失に対する線形収束を享受していることを示す。 また、勾配法のようなベースラインよりも2～3$times$早く収束できることも示している。
  論文  参考訳（メタデータ） (2023-10-21T00:03:54Z)
• 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)
• Beyond the Edge of Stability via Two-step Gradient Updates [49.03389279816152]
  Gradient Descent(GD)は、現代の機械学習の強力な仕事場である。 GDが局所最小値を見つける能力は、リプシッツ勾配の損失に対してのみ保証される。 この研究は、2段階の勾配更新の分析を通じて、単純だが代表的でありながら、学習上の問題に焦点をあてる。
  論文  参考訳（メタデータ） (2022-06-08T21:32:50Z)
• Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization [4.7464518249313805]
  サブグラディエント法(Sub-gradient method, SubGM)は, 限られた測定値から低ランク行列を復元するために用いられる。 我々は、SubGMが任意の大きさの高密度ノイズ値の下でも、真の解に収束することを示す。
  論文  参考訳（メタデータ） (2022-02-17T17:50:04Z)
• 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)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。 我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
  論文  参考訳（メタデータ） (2021-11-01T15:43:36Z)
• 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)
• Support recovery and sup-norm convergence rates for sparse pivotal estimation [79.13844065776928]
  高次元スパース回帰では、ピボット推定器は最適な正規化パラメータがノイズレベルに依存しない推定器である。 非滑らかで滑らかな単一タスクとマルチタスク正方形ラッソ型推定器に対するミニマックス超ノルム収束率を示す。
  論文  参考訳（メタデータ） (2020-01-15T16:11:04Z)

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

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