論文の概要: Recursive Importance Sketching for Rank Constrained Least Squares:
Algorithms and High-order Convergence
- arxiv url: http://arxiv.org/abs/2011.08360v3
- Date: Fri, 29 Jul 2022 14:02:13 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-24 16:28:38.653082
- Title: Recursive Importance Sketching for Rank Constrained Least Squares:
Algorithms and High-order Convergence
- Title（参考訳）: ランク制約付き最小二乗に対する再帰的重要度スケッチ:アルゴリズムと高次収束
- Authors: Yuetian Luo, Wen Huang, Xudong Li, Anru R. Zhang
- Abstract要約: RISROは次元還元最小二乗問題を解くアルゴリズムである。
RISROは実装が容易で計算効率が良く,各イテレーションのコアプロシージャは次元還元最小二乗問題の解法であることを示す。
- 参考スコア（独自算出の注目度）: 6.757692422527145
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose {\it \underline{R}ecursive} {\it
\underline{I}mportance} {\it \underline{S}ketching} algorithm for {\it
\underline{R}ank} constrained least squares {\it \underline{O}ptimization}
(RISRO). The key step of RISRO is recursive importance sketching, a new
sketching framework based on deterministically designed recursive projections,
which significantly differs from the randomized sketching in the literature
\citep{mahoney2011randomized,woodruff2014sketching}. Several existing
algorithms in the literature can be reinterpreted under this new sketching
framework and RISRO offers clear advantages over them. RISRO is easy to
implement and computationally efficient, where the core procedure in each
iteration is to solve a dimension-reduced least squares problem. We establish
the local quadratic-linear and quadratic rate of convergence for RISRO under
some mild conditions. We also discover a deep connection of RISRO to the
Riemannian Gauss-Newton algorithm on fixed rank matrices. The effectiveness of
RISRO is demonstrated in two applications in machine learning and statistics:
low-rank matrix trace regression and phase retrieval. Simulation studies
demonstrate the superior numerical performance of RISRO.
- Abstract（参考訳）: 本稿では, {\it \underline{r}ecursive} {\it \underline{i}mportance} {\it \underline{s}ketching} algorithm for {\it \underline{r}ank}stricted least squares {\it \underline{o}ptimization} (risro)を提案する。
RISROの重要なステップは再帰的重要スケッチ(recursive importance sketching)である。これは決定論的に設計された再帰的投影に基づく新しいスケッチフレームワークであり、文献 \citep{mahoney 2011randomized,woodruff2014sketching} のランダム化されたスケッチとは大きく異なる。
文献にあるいくつかの既存のアルゴリズムは、この新しいスケッチフレームワークの下で再解釈することができ、RISROはそれらに対して明確な利点を提供する。
RISROは実装が容易で計算的に効率的であり、各イテレーションのコアプロシージャは次元還元最小二乗問題の解法である。
軽度条件下でRISROの局所2次線形および2次収束速度を確立する。
また、固定階数行列上のリーマンガウスニュートンアルゴリズムとRISROの深い関係も発見する。
risroの有効性は、機械学習と統計学の2つの応用(低ランク行列のトレース回帰と位相検索)で実証されている。
シミュレーション研究はRISROの優れた数値性能を示す。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Online and Offline Robust Multivariate Linear Regression [0.3277163122167433]
提案手法は,オンライン勾配降下アルゴリズムと平均化バージョン,オフライン固定点アルゴリズムの2つである。
ノイズの分散行列は一般に未知であるため、マハラノビスに基づく勾配勾配アルゴリズムに頑健な推定をプラグインすることを提案する。
論文 参考訳（メタデータ） (2024-04-30T12:30:48Z) - Sketching for Convex and Nonconvex Regularized Least Squares with Sharp
Guarantees [23.614074988517864]
本稿では,非正規化関数によって正規化あるいは凸化される最小二乗問題に対する高速近似を提案する。
スケッチされた凸や非近似問題を解くことにより、推定のための最小値率を初めて示す。
論文 参考訳（メタデータ） (2023-11-03T09:35:01Z) - Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement
Learning [53.445068584013896]
低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。
低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。
簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
論文 参考訳（メタデータ） (2023-10-10T17:06:41Z) - Deep Unrolling for Nonconvex Robust Principal Component Analysis [75.32013242448151]
我々はロバスト成分分析のためのアルゴリズムを設計する(A)
行列を低主行列とスパース主行列の和に分解する。
論文 参考訳（メタデータ） (2023-07-12T03:48:26Z) - Recovering Simultaneously Structured Data via Non-Convex Iteratively
Reweighted Least Squares [0.8702432681310401]
線形観測から多種多様低次元構造に固執するデータを復元する新しいアルゴリズムを提案する。
IRLS法は,低/複合状態の計測に好適であることを示す。
論文 参考訳（メタデータ） (2023-06-08T06:35:47Z) - Lifelong Learning with Sketched Structural Regularization [36.86222424065129]
構造正規化 (SR) は、ネットワークを「臨界パラメータ」を変更することで破滅的な忘れを緩和するアルゴリズムのファミリーを指す。
ほとんどのSR法は、その対角線による重要性行列を粗く近似する。
提案手法は,合成実験とベンチマーク連続学習の両方において,様々なSRアルゴリズムの性能を継続的に向上することを示す。
論文 参考訳（メタデータ） (2021-04-17T18:07:23Z) - Low-Rank Sinkhorn Factorization [45.87981728307819]
本稿では,テキストサブカップリング係数の積として,低位結合の明示的な因子化を導入する。
このアルゴリズムの非漸近定常収束を証明し、その効率をベンチマーク実験で示す。
論文 参考訳（メタデータ） (2021-03-08T13:18:45Z) - Learning the Positions in CountSketch [51.15935547615698]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習アルゴリズムを提案する。
このアルゴリズムは, 従来よりも低階近似の精度を向上し, 初めて$k$-meansクラスタリングのような他の問題に適用できることを示す。
論文 参考訳（メタデータ） (2020-07-20T05:06:29Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。