論文の概要: Sharp Analysis of Sketch-and-Project Methods via a Connection to
Randomized Singular Value Decomposition
- arxiv url: http://arxiv.org/abs/2208.09585v1
- Date: Sat, 20 Aug 2022 03:11:13 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-23 14:15:32.523806
- Title: Sharp Analysis of Sketch-and-Project Methods via a Connection to
Randomized Singular Value Decomposition
- Title（参考訳）: ランダム化特異値分解への接続によるスケッチ・アンド・プロジェクト法のシャープ解析
- Authors: Micha{\l} Derezi\'nski, Elizaveta Rebrova
- Abstract要約: 我々は、新しい厳密なスペクトル境界によってスケッチ・アンド・プロジェクト法の収束率の保証を得る。
我々の推定は、スケッチ・アンド・プロジェクト収束率と、他のよく知られた、一見無関係なアルゴリズムの近似誤差との関連性を明らかにする。
この接続により、スケッチ・アンド・プロジェクト・ソルバのパフォーマンスが、そのスケッチサイズに依存するかの定量化に近づきます。
- 参考スコア（独自算出の注目度）: 24.503413329757567
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Sketch-and-project is a framework which unifies many known iterative methods
for solving linear systems and their variants, as well as further extensions to
non-linear optimization problems. It includes popular methods such as
randomized Kaczmarz, coordinate descent, variants of the Newton method in
convex optimization, and others. In this paper, we obtain sharp guarantees for
the convergence rate of sketch-and-project methods via new tight spectral
bounds for the expected sketched projection matrix. Our estimates reveal a
connection between the sketch-and-project convergence rate and the
approximation error of another well-known but seemingly unrelated family of
algorithms, which use sketching to accelerate popular matrix factorizations
such as QR and SVD. This connection brings us closer to precisely quantifying
how the performance of sketch-and-project solvers depends on their sketch size.
Our analysis covers not only Gaussian and sub-gaussian sketching matrices, but
also a family of efficient sparse sketching methods known as LESS embeddings.
Our experiments back up the theory and demonstrate that even extremely sparse
sketches show the same convergence properties in practice.
- Abstract（参考訳）: sketch-and-project(スケッチ・アンド・プロジェクト)は、線形システムとその変種を解決する多くの既知の反復的手法と、非線形最適化問題のさらなる拡張を統合するフレームワークである。
ランダム化kaczmarz、座標降下、凸最適化におけるニュートン法の変種など、一般的な方法を含んでいる。
本稿では,期待される投影行列に対する新しい密接なスペクトル境界により,スケッチ・アンド・プロジェクション法の収束率を鋭く保証する。
我々の推定では、スケッチ・アンド・プロジェクト収束率と、QRやSVDなどの一般的な行列因数分解を高速化するためにスケッチを用いた他のよく知られた、一見無関係なアルゴリズムの近似誤差との関連性を明らかにする。
この接続により、スケッチ・アンド・プロジェクト・ソルバのパフォーマンスがそのスケッチサイズに依存するかを正確に定量化できます。
本解析はガウシアンおよびサブガウシアンのスケッチ行列だけでなく,less embeddeds として知られる効率的なスパーススケッチ手法のファミリーを網羅する。
我々の実験は理論を裏付け、非常にスパースなスケッチでさえ実際に同じ収束特性を示すことを示した。
関連論文リスト
- Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Distributed Sketching for Randomized Optimization: Exact
Characterization, Concentration and Lower Bounds [54.51566432934556]
我々はヘシアンの形成が困難である問題に対する分散最適化法を検討する。
ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
論文 参考訳（メタデータ） (2022-03-18T05:49:13Z) - Accumulations of Projections--A Unified Framework for Random Sketches in
Kernel Ridge Regression [12.258887270632869]
n-by-n 経験的カーネル行列のスケッチを構築することは、多くのカーネルメソッドの計算を加速するための一般的なアプローチである。
カーネルリッジ回帰におけるスケッチ手法を構築するための統一フレームワークを提案する。
論文 参考訳（メタデータ） (2021-03-06T05:02:17Z) - Delayed Projection Techniques for Linearly Constrained Problems:
Convergence Rates, Acceleration, and Applications [24.763531954075656]
線形制約問題(LCP)に対する新しいプロジェクションベースアルゴリズムのクラスについて検討する。
そこで本研究では,射影を一時的に呼び出す遅延射影手法を提案し,射影周波数を下げ,射影効率を向上させる。
強凸, 一般凸のどちらの場合においても, 投射効率を向上させることが可能であることを示す。
論文 参考訳（メタデータ） (2021-01-05T13:42:41Z) - Progressive Batching for Efficient Non-linear Least Squares [31.082253632197023]
ガウス・ニュートンの基本的な改良のほとんどは、基礎となる問題構造の空間性を保証するか、あるいは活用して計算速度を上げることである。
我々の研究は、機械学習と統計の両方からアイデアを借用し、収束を保証するとともに、必要な計算量を大幅に削減する非線形最小二乗に対するアプローチを提案する。
論文 参考訳（メタデータ） (2020-10-21T13:00:04Z) - Precise expressions for random projections: Low-rank approximation and
randomized Newton [63.68433510953756]
マトリックススケッチは、そのような次元削減を非常に効率的に行うための強力な技術として登場した。
本研究では,スケッチによって得られたランダムな投影行列の予測値に対して,確率的に正確な表現を提供する手法を開発した。
これらの表現は、様々な機械学習タスクにおける次元削減のパフォーマンスを特徴付けるのに使うことができる。
論文 参考訳（メタデータ） (2020-06-18T16:23:00Z) - 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) - Statistical Outlier Identification in Multi-robot Visual SLAM using
Expectation Maximization [18.259478519717426]
本稿では、同時局所化およびマッピング(SLAM)におけるマップ間ループ閉包外乱検出のための、新しい分散手法を提案する。
提案アルゴリズムは優れた初期化に頼らず、一度に2つ以上のマップを処理できる。
論文 参考訳（メタデータ） (2020-02-07T06:34:44Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳（メタデータ） (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。