論文の概要: Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
- arxiv url: http://arxiv.org/abs/2302.11068v3
- Date: Mon, 1 Apr 2024 22:17:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-04 14:01:34.975294
- Title: Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
- Title（参考訳）: ほぼ線形時間におけるロバスト交代最小化による低ランク行列補完
- Authors: Yuzhou Gu, Zhao Song, Junze Yin, Lichen Zhang,
- Abstract要約: 我々は、より効率的でエラーの少ない最小化フレームワークに向けて、大きな一歩を踏み出します。
我々のアルゴリズムは時間$widetilde O(|Omega| k)$で実行され、解の検証にはほぼ線形である。
- 参考スコア（独自算出の注目度）: 8.808780937701522
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a matrix $M\in \mathbb{R}^{m\times n}$, the low rank matrix completion problem asks us to find a rank-$k$ approximation of $M$ as $UV^\top$ for $U\in \mathbb{R}^{m\times k}$ and $V\in \mathbb{R}^{n\times k}$ by only observing a few entries specified by a set of entries $\Omega\subseteq [m]\times [n]$. In particular, we examine an approach that is widely used in practice -- the alternating minimization framework. Jain, Netrapalli, and Sanghavi [JNS13] showed that if $M$ has incoherent rows and columns, then alternating minimization provably recovers the matrix $M$ by observing a nearly linear in $n$ number of entries. While the sample complexity has been subsequently improved [GLZ17], alternating minimization steps are required to be computed exactly. This hinders the development of more efficient algorithms and fails to depict the practical implementation of alternating minimization, where the updates are usually performed approximately in favor of efficiency. In this paper, we take a major step towards a more efficient and error-robust alternating minimization framework. To this end, we develop an analytical framework for alternating minimization that can tolerate a moderate amount of errors caused by approximate updates. Moreover, our algorithm runs in time $\widetilde O(|\Omega| k)$, which is nearly linear in the time to verify the solution while preserving the sample complexity. This improves upon all prior known alternating minimization approaches which require $\widetilde O(|\Omega| k^2)$ time.
- Abstract（参考訳）: 行列 $M\in \mathbb{R}^{m\times n}$ が与えられたとき、低階行列完備問題によりランク-k$$$M$ as $UV^\top$ for $U\in \mathbb{R}^{m\times k}$ と $V\in \mathbb{R}^{n\times k}$ を求めることができる。
特に、交代最小化フレームワークである、実際に広く使われているアプローチについて検討する。
Jain, Netrapalli, Sanghavi [JNS13] は、$M$ が不整列と列を持つなら、最小化の交互化は、$n$ のエントリのほとんど線形を観察することによって、行列 $M$ を確実に回復させることを示した。
サンプルの複雑さはその後改善された [GLZ17] が、最小化ステップの交互化は正確に計算する必要がある。
これにより、より効率的なアルゴリズムの開発が妨げられ、更新がほぼ効率を優先して実行される交代最小化の実践的な実装を表現できない。
本稿では,より効率的で誤りの少ない最小化フレームワークの実現に向けて大きな一歩を踏み出した。
そこで本研究では,近似更新による誤りの程度を許容できる最小化を交互に行う解析フレームワークを開発した。
さらに、我々のアルゴリズムは時間$\widetilde O(|\Omega| k)$で実行され、これはサンプルの複雑さを保ちながら解を検証するのにほぼ線形である。
これは、$\widetilde O(|\Omega| k^2)$ time を必要とするすべての既知の交互最小化アプローチを改善する。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning [10.690769339903941]
我々は、$Ax = b$という形式の線形系を解くための、新しい条件付き反復法のクラスを示す。
提案手法は,低ランクなNystr"om近似をスパースランダムスケッチを用いて$A$に構築することに基づいている。
我々は、我々の手法の収束が自然平均条件数$A$に依存することを証明し、Nystr"om近似のランクとして改善する。
論文 参考訳（メタデータ） (2024-05-09T15:53:43Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Efficient Alternating Minimization with Applications to Weighted Low
Rank Approximation [16.409210914237086]
我々は、最小化の交互化のための効率的で堅牢なフレームワークを開発する。
重み付けされた低階近似の場合、 [LLR16] のランタイムを $n2 k2$ から $n2k$ に改善する。
論文 参考訳（メタデータ） (2023-06-07T05:38:55Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Improved No-Regret Algorithms for Stochastic Shortest Path with Linear
MDP [31.62899359543925]
線形MDPを用いた最短経路問題(SSP)に対する2つの新しい非回帰アルゴリズムを提案する。
我々の最初のアルゴリズムは計算効率が高く、後悔すべき$widetildeOleft(sqrtd3B_star2T_star Kright)$を達成している。
第2のアルゴリズムは計算的に非効率であるが、$T_starに依存しない$widetildeO(d3.5B_starsqrtK)$の最初の「水平な」後悔を実現する。
論文 参考訳（メタデータ） (2021-12-18T06:47:31Z) - Nonparametric Matrix Estimation with One-Sided Covariates [5.457150493905064]
mathbbRntimes m$ のデータセット $X をスパシティ $p$ で観測する行列推定のタスクを考える。
我々は,行数が小さすぎる場合に,各行を別々に推定することで,アルゴリズムの精度が向上することを示すアルゴリズムと解析を提供する。
論文 参考訳（メタデータ） (2021-10-26T19:11:45Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。