論文の概要: Efficient Alternating Minimization with Applications to Weighted Low
Rank Approximation
- arxiv url: http://arxiv.org/abs/2306.04169v2
- Date: Thu, 27 Jul 2023 16:20:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-28 19:41:17.568594
- Title: Efficient Alternating Minimization with Applications to Weighted Low
Rank Approximation
- Title（参考訳）: 効率的な交代最小化と軽量低ランク近似への応用
- Authors: Zhao Song, Mingquan Ye, Junze Yin, Lichen Zhang
- Abstract要約: 我々は、最小化の交互化のための効率的で堅牢なフレームワークを開発する。
重み付けされた低階近似の場合、 [LLR16] のランタイムを $n2 k2$ から $n2k$ に改善する。
- 参考スコア（独自算出の注目度）: 16.409210914237086
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Weighted low rank approximation is a fundamental problem in numerical linear
algebra, and it has many applications in machine learning. Given a matrix $M
\in \mathbb{R}^{n \times n}$, a weight matrix $W \in \mathbb{R}_{\geq 0}^{n
\times n}$, a parameter $k$, the goal is to output two matrices $U, V \in
\mathbb{R}^{n \times k}$ such that $\| W \circ (M - U V^\top) \|_F$ is
minimized, where $\circ$ denotes the Hadamard product. Such a problem is known
to be NP-hard and even hard to approximate assuming Exponential Time Hypothesis
[GG11, RSW16]. Meanwhile, alternating minimization is a good heuristic solution
for approximating weighted low rank approximation. The work [LLR16] shows that,
under mild assumptions, alternating minimization does provide provable
guarantees. In this work, we develop an efficient and robust framework for
alternating minimization. For weighted low rank approximation, this improves
the runtime of [LLR16] from $n^2 k^2$ to $n^2k$. At the heart of our work
framework is a high-accuracy multiple response regression solver together with
a robust analysis of alternating minimization.
- Abstract（参考訳）: 重み付き低階近似は数値線形代数の基本的な問題であり、機械学習に多くの応用がある。
行列 $m \in \mathbb{r}^{n \times n}$, 重み行列 $w \in \mathbb{r}_{\geq 0}^{n \times n}$, パラメータ $k$ が与えられたとき、目標は2つの行列 u, v \in \mathbb{r}^{n \times k}$ を$\| w \circ (m - u v^\top) \|_f$ として出力することであり、ここで $\circ$ はアダマール積を表す。
このような問題はNPハードであることが知られており、指数時間仮説 [GG11, RSW16] を仮定するのも難しい。
一方、交互最小化は重み付き低階近似を近似する優れたヒューリスティック解である。
作業[llr16]は、穏やかな仮定の下で、交互の最小化が証明可能な保証を提供することを示している。
本研究では、最小化を交互に行うための効率的で堅牢なフレームワークを開発する。
重み付き低階近似では、[LLR16] のランタイムを $n^2k^2$ から $n^2k$ に改善する。
作業フレームワークの核心は、反復最小化の堅牢な解析とともに、高精度な多重応答回帰解法である。
関連論文リスト
- How to Inverting the Leverage Score Distribution? [16.744561210470632]
ツールとして広く利用されているレバレッジスコアにもかかわらず、本論文では、新しい問題、すなわち反転レバレッジスコアについて検討する。
我々は、ニュートン法における大域収束率を確保するために反復縮小と帰納仮説を用いる。
この統計レバレッジの反転に関する重要な研究は、解釈、データリカバリ、セキュリティにおける多くの新しい応用を開放する。
論文 参考訳（メタデータ） (2024-04-21T21:36:42Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time [8.808780937701522]
我々は、より効率的でエラーの少ない最小化フレームワークに向けて、大きな一歩を踏み出します。
我々のアルゴリズムは時間$widetilde O(|Omega| k)$で実行され、解の検証にはほぼ線形である。
論文 参考訳（メタデータ） (2023-02-21T23:49:36Z) - Estimating the minimizer and the minimum value of a regression function
under passive design [72.85024381807466]
最小値 $boldsymbolx*$ と最小値 $f*$ を滑らかで凸な回帰関数 $f$ で推定する新しい手法を提案する。
2次リスクと$boldsymbolz_n$の最適化誤差、および$f*$を推定するリスクについて、漸近的でない上界を導出する。
論文 参考訳（メタデータ） (2022-11-29T18:38:40Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Hardness and Algorithms for Robust and Sparse Optimization [17.842787715567436]
スパース線形回帰やロバスト線形回帰といったスパース最適化問題に対するアルゴリズムと制限について検討する。
具体的には、スパース線型回帰問題は$k$-スパースベクトル$xinmathbbRd$を求め、$|Ax-b|$を最小化する。
頑健な線形回帰問題は、少なくとも$k$行を無視する集合$S$と、$|(Ax-b)_S|$を最小化するベクトル$x$を求める。
論文 参考訳（メタデータ） (2022-06-29T01:40:38Z) - Local Search Algorithms for Rank-Constrained Convex Optimization [7.736462653684946]
階数制約付き凸最適化のための欲望と局所探索アルゴリズムを提案する。
我々は、$R$のランク制限条件番号が$kappa$であれば、$A$のランク$O(r*cdot minkappa log fracR(mathbf0)-R(A*)epsilon、kappa2)$と$R(A)leq R(A*)+epsilon$のソリューションが回復できることを示しています。
論文 参考訳（メタデータ） (2021-01-15T18:52:02Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov
Decision Processes [91.38793800392108]
本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。
上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。
我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
論文 参考訳（メタデータ） (2020-12-15T18:56:46Z) - 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) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。