論文の概要: Sharp Analysis of Sketch-and-Project Methods via a Connection to
Randomized Singular Value Decomposition
- arxiv url: http://arxiv.org/abs/2208.09585v2
- Date: Mon, 18 Sep 2023 20:19:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-20 20:43:21.391931
- 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要約: 本研究では,スケッチ・アンド・プロジェクト手法の収束率の急激な保証を得るための理論的枠組みを開発する。
収束速度はスケッチサイズとともに少なくとも直線的に改善され、データ行列が特定のスペクトル崩壊を示すとさらに高速になることを示す。
我々の実験は、この理論を支持し、非常にスパースなスケッチでさえ、我々のフレームワークによって予測される収束特性を示すことを示した。
- 参考スコア（独自算出の注目度）: 14.453949553412821
- 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 develop a theoretical
framework for obtaining sharp guarantees on the convergence rate of
sketch-and-project methods. Our approach is the first to: (1) show that the
convergence rate improves at least linearly with the sketch size, and even
faster when the data matrix exhibits certain spectral decays; and (2) allow for
sparse sketching matrices, which are more efficient than dense sketches and
more robust than sub-sampling methods. In particular, our results explain an
observed phenomenon that a radical sparsification of the sketching matrix does
not affect the per iteration convergence rate of sketch-and-project. To obtain
our results, we develop new non-asymptotic spectral bounds for the expected
sketched projection matrix, which are of independent interest; and we establish
a connection between the convergence rates of iterative sketch-and-project
solvers and the approximation error of randomized singular value decomposition,
which is a widely used one-shot sketching algorithm for low-rank approximation.
Our experiments support the theory and demonstrate that even extremely sparse
sketches exhibit the convergence properties predicted by our framework.
- Abstract（参考訳）: sketch-and-project(スケッチ・アンド・プロジェクト)は、線形システムとその変種を解決する多くの既知の反復的手法と、非線形最適化問題のさらなる拡張を統合するフレームワークである。
ランダム化kaczmarz、座標降下、凸最適化におけるニュートン法の変種など、一般的な方法を含んでいる。
本稿では,sketch-and-project法の収束率に関するシャープな保証を得るための理論的枠組みを提案する。
提案手法は,(1)コンバージェンスレートがスケッチサイズで少なくとも線形に改善され,かつ,あるスペクトル減衰を示すとさらに速くなることを示すこと,(2)密度の高いスケッチよりも効率的で,サブサンプリング法よりも頑健な疎スケッチ行列を可能にすること,の1つである。
特に,スケッチ行列のラジカルスパーシフィケーションは,スケッチ・アンド・プロジェクト毎のイテレーション収束率に影響を与えないという観測現象を説明する。
この結果を得るために, 予測された投影行列に対する非漸近的スペクトル境界を独立に開発し, 反復的スケッチ・アンド・プロジェクトソルバの収束率と, 低ランク近似のための一眼レフティングアルゴリズムであるランダム化特異値分解の近似誤差との関係を明らかにした。
我々の実験は理論を支持し、非常にスパースなスケッチでさえ我々のフレームワークによって予測される収束特性を示すことを示した。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。