論文の概要: Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regime
- arxiv url: http://arxiv.org/abs/2104.10790v3
- Date: Tue, 06 May 2025 17:29:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-07 18:50:10.81086
- Title: Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regime
- Title（参考訳）: 雑音過度レジームにおける非凸低ランク回復のためのシャープグローバル保証
- Authors: Richard Y. Zhang,
- Abstract要約: 本稿では,従来の競合する2つのアプローチを統一し,単純化し,強化する新しい証明手法を提案する。
近2次点が,より高価な凸法と同じミニマックス回復限界を達成することを示す。
- 参考スコア（独自算出の注目度）: 10.787390511207683
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent work established that rank overparameterization eliminates spurious local minima in nonconvex low-rank matrix recovery under the restricted isometry property (RIP). But this does not fully explain the practical success of overparameterization, because real algorithms can still become trapped at nonstrict saddle points (approximate second-order points with arbitrarily small negative curvature) even when all local minima are global. Moreover, the result does not accommodate for noisy measurements, but it is unclear whether such an extension is even possible, in view of the many discontinuous and unintuitive behaviors already known for the overparameterized regime. In this paper, we introduce a novel proof technique that unifies, simplifies, and strengthens two previously competing approaches -- one based on escape directions and the other based on the inexistence of counterexample -- to provide sharp global guarantees in the noisy overparameterized regime. We show, once local minima have been converted into global minima through slight overparameterization, that near-second-order points achieve the same minimax-optimal recovery bounds (up to small constant factors) as significantly more expensive convex approaches. Our results are sharp with respect to the noise level and the solution accuracy, and hold for both the symmetric parameterization $XX^{T}$, as well as the asymmetric parameterization $UV^{T}$ under a balancing regularizer; we demonstrate that the balancing regularizer is indeed necessary.
- Abstract（参考訳）: 近年の研究では,制限等尺性(RIP)下での非凸低ランク行列回復において,ランク過度化が急激な局所最小値を排除することが確認されている。
実アルゴリズムは、すべての局所ミニマが大域的である場合でも、非制限サドル点(任意に小さい負の曲率を持つ二階点)に閉じ込められることがあるからである。
さらに、この結果はノイズ測定には適していないが、既に過度にパラメータ化された状態で知られている多くの不連続かつ直観的な行動の観点から、そのような拡張が可能かどうかは不明である。
本稿では,2つの競合するアプローチを統一し,単純化し,強化する新しい証明手法を提案する。
局所最小値がわずかに過度なパラメータ化によって大域的最小値に変換されると、近2次点は同じミニマックス最適リカバリ境界(小さな定数要素まで)を、はるかに高価な凸アプローチとして達成できることが示される。
我々の結果はノイズレベルと解の精度に関して鋭く、対称パラメータ化$XX^{T}$と非対称パラメータ化$UV^{T}$の両方をバランス正則化の下で保持する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。