論文の概要: Near-Optimal Nonconvex Matrix Completion

• arxiv url: http://arxiv.org/abs/2609.17048v1
• Date: Tue, 15 Sep 2026 11:57:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-16 14:56:08.48311
• Title: Near-Optimal Nonconvex Matrix Completion
• Title（参考訳）: 近接最適非凸行列補完
• Abstract要約: 本稿では,そのサブセットから低ランクスペクトル誤差を復元する問題について検討する。 この方法は問題に対する条件数法を収束させる。 2つの方法は、それぞれ$O(nlog nlog(n)$(nrlogr)$(nrlogr)$(nrlogr)$観測から高い確率で正確な回復を達成する。
• 参考スコア（独自算出の注目度）: 6.287662267319984
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study nonconvex methods for matrix completion, the problem of recovering a low-rank matrix from a subset of its entries. Convex methods achieve sample complexity linear in the matrix dimension and the rank, up to logarithmic factors, whereas global guarantees for commonly used nonconvex methods require a higher polynomial dependence on the rank. We close this gap by analyzing Riemannian gradient descent (RGD) and Riemannian Gauss--Newton (RGN) methods. For an $n\times n$ matrix of rank $r$ with incoherence parameter $μ$ and condition number $κ$, the two methods achieve exact recovery with high probability from $O(μnr\log n\log(nκ))$ and $O(μnr\log n\log(2μrκ))$ observations, respectively. The methods use a multiscale residual initialization, while the analysis simultaneously controls the spectral error and incoherence. The resulting RGD iterates converge linearly, whereas RGN eventually converges Q-quadratically.
• Abstract（参考訳）: 本稿では,行列補完のための非凸法について検討し,そのサブセットから低ランク行列を復元する問題について述べる。 凸法は、行列次元と階数において、対数係数まで線形なサンプル複雑性を実現するが、一般的な非凸法に対する大域的な保証は階数への多項式依存性を高くする必要がある。 リーマン勾配降下法(RGD)とリーマンガウス-ニュートン法(RGN)を解析することで、このギャップを埋める。 非コヒーレンスパラメータ$μ$と条件番号$κ$のランク$r$の$n\times n$行列に対して、この2つの方法は、それぞれ$O(μnr\log n\log(nκ))$と$O(μnr\log n\log(2μrκ))$観測から高い確率で正確な回復を達成する。 解析はスペクトル誤差と非コヒーレンスを同時に制御する一方、マルチスケールの残留初期化を用いる。 結果の RGD は線型収束するが、RGN は Q-四次収束する。

関連論文リスト

• Near-Optimal Regret in Adversarial Kernel Bandits [50.68324062892194]
  本稿では,各ラウンドにおける損失が任意の有界要素によって誘導される逆カーネルバンドイット問題について検討する。 我々の主な結果は、$widetildeObig(sqrtT, d_*(),log|X|big)$, ここでは$d_*()$は有効次元の広く解釈された概念である。
  論文  参考訳（メタデータ） (2026-05-26T06:10:24Z)
• Scaled Gradient Descent for Ill-Conditioned Low-Rank Matrix Recovery with Optimal Sampling Complexity [1.655804338897892]
  最適サンプリング設定を施した不条件サンプルに対して,スケールド・イテレーションが高速化されることを示す。 さらに, 最適サンプリング設定による不条件試料に対するスケールド収束が促進されることが示唆された。
  論文  参考訳（メタデータ） (2026-03-31T05:20:20Z)
• Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization [19.32160757444549]
  非特定行列分解の実例では、真の解体$のランクはしばしば未知であるため、モデルのランク子$は$r>rstar$として特異である。 本稿では,行列センサの非行列因数分解のための安価なサブプロセッサを提案し,非依存の場合においても収束係数を線形に復元する。 我々の数値実験により、PrecGD は他の変種非行列分解の収束を回復する上でも同様にうまく機能することがわかった。
  論文  参考訳（メタデータ） (2025-04-13T20:06:49Z)
• Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent [17.422662003404586]
  雑音行列検出問題に対する交互事前条件勾配降下法(APGD)を提案する。 APGDは、既存の代替法と比較して、最も早く収束し、最も低い計算時間を達成する。
  論文  参考訳（メタデータ） (2025-02-01T15:44:39Z)
• Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees [6.422262171968397]
  ユークリッド距離幾何学問題を解くために2つのアルゴリズムが提案されている。 第一のアルゴリズムは真の解に線形に収束する。 第2のアルゴリズムは、合成データと実データの両方で強い数値性能を示す。
  論文  参考訳（メタデータ） (2024-10-08T21:19:22Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogates [0.0]
  提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。 非テンション依存データ設定の下で, 各種手法の収束点を求める。
  論文  参考訳（メタデータ） (2022-01-05T15:17:35Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms [65.09383385484007]
  2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。 本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
  論文  参考訳（メタデータ） (2020-11-10T11:36:30Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。 我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-30T19:10:32Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)

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

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