論文の概要: 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$ に改善する。
作業フレームワークの核心は、反復最小化の堅牢な解析とともに、高精度な多重応答回帰解法である。
関連論文リスト
- Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39:42Z) - 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) - 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) - Unique sparse decomposition of low rank matrices [17.037882881652617]
低階行列Yin mathbbRrtimes n$ のユニークな分解が見つかる。
我々は、ある$Yin MathRrtimes n$が$Xin mathbbRrtimes n$のスパースワイズ分解であることを示す。
論文 参考訳（メタデータ） (2021-06-14T20:05:59Z) - Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。
実験ではハッチンソン法を著しく上回る結果を得た。
論文 参考訳（メタデータ） (2020-10-19T16:45:37Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - Rank $2r$ iterative least squares: efficient recovery of ill-conditioned
low rank matrices from few entries [4.230158563771147]
低階行列補完のための新しい,単純で,計算効率のよい反復法を提案する。
我々のアルゴリズムは、R2RILS(R2RILS for rank $2r$peterative least squares)と呼ばれ、メモリ要件が低い。
論文 参考訳（メタデータ） (2020-02-05T16:20:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。