論文の概要: Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems
- arxiv url: http://arxiv.org/abs/2405.05818v1
- Date: Thu, 9 May 2024 14:56:49 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-10 13:02:50.698511
- Title: Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems
- Title（参考訳）: 線形系反復解法のためのきめ細かい解析と高速アルゴリズム
- Authors: Michał Dereziński, Daniel LeJeune, Deanna Needell, Elizaveta Rebrova,
- Abstract要約: 我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。
結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
- 参考スコア（独自算出の注目度）: 9.30306458153248
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: While effective in practice, iterative methods for solving large systems of linear equations can be significantly affected by problem-dependent condition number quantities. This makes characterizing their time complexity challenging, particularly when we wish to make comparisons between deterministic and stochastic methods, that may or may not rely on preconditioning and/or fast matrix multiplication. In this work, we consider a fine-grained notion of complexity for iterative linear solvers which we call the spectral tail condition number, $\kappa_\ell$, defined as the ratio between the $\ell$th largest and the smallest singular value of the matrix representing the system. Concretely, we prove the following main algorithmic result: Given an $n\times n$ matrix $A$ and a vector $b$, we can find $\tilde{x}$ such that $\|A\tilde{x}-b\|\leq\epsilon\|b\|$ in time $\tilde{O}(\kappa_\ell\cdot n^2\log 1/\epsilon)$ for any $\ell = O(n^{\frac1{\omega-1}})=O(n^{0.729})$, where $\omega \approx 2.372$ is the current fast matrix multiplication exponent. This guarantee is achieved by Sketch-and-Project with Nesterov's acceleration. Some of the implications of our result, and of the use of $\kappa_\ell$, include direct improvement over a fine-grained analysis of the Conjugate Gradient method, suggesting a stronger separation between deterministic and stochastic iterative solvers; and relating the complexity of iterative solvers to the ongoing algorithmic advances in fast matrix multiplication, since the bound on $\ell$ improves with $\omega$. Our main technical contributions are new sharp characterizations for the first and second moments of the random projection matrix that commonly arises in sketching algorithms, building on a combination of techniques from combinatorial sampling via determinantal point processes and Gaussian universality results from random matrix theory.
- Abstract（参考訳）: 実効性はあるものの、線形方程式の大規模系を解く反復法は問題依存条件数量に大きく影響される。
これにより、特に決定論的手法と確率論的手法の比較をしたい場合、特に事前条件や高速行列乗法に頼らない場合、時間の複雑さを特徴付けるのが難しくなる。
そこで本研究では,スペクトルテール条件数である$\kappa_\ell$を,システムを表す行列の最小特異値と$\ell$2の比として定義する。
具体的には、$n\times n$ matrix $A$とベクトル$b$が与えられたとき、$\tilde{x}-b\|\leq\epsilon\|b\|$ in time $\tilde{O}(\kappa_\ell\cdot n^2\log 1/\epsilon)$ for any $\ell = O(n^{\frac1{\omega-1}})=O(n^{0.729})$,$\omega \approx 2.372$は現在の高速行列乗法である。
この保証はNesterovの加速度を持つSketch-and-Projectによって達成される。
結果と$\kappa_\ell$の使用のいくつかの意味は、共役勾配法におけるきめ細かい解析の直接的な改善、決定論的および確率的反復解法の間のより強い分離の示唆、および、反復解法の複雑さと高速行列乗法におけるアルゴリズム的進歩の関係である。
我々の主な技術的貢献は、スケッチアルゴリズムで一般的に発生するランダム射影行列の第1および第2モーメントに対する新しい鋭い特徴付けであり、決定点過程による組合せ的サンプリングと確率行列理論によるガウス的普遍性から得られる技術の組み合わせの上に構築されている。
関連論文リスト
- Combinatorial optimization of the coefficient of determination [0.0]
決定係数が最も高い平面上の$n$点の$k$-部分集合を選択するための効率的なアルゴリズムを開発する。
誤差のない$n=30$までの試行で,提案手法の最適性を実験的に実証した。
論文 参考訳（メタデータ） (2024-10-12T00:53:25Z) - Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers [29.212403229351253]
我々は、このマルコフ連鎖のほぼ最適な実装を示し、ステップごとの複雑さは、約$A$のゼロでないエントリの数であるのに対して、マルコフ連鎖のステップの数は同じである。
1) このダイキンウォークで生じる行列はゆっくりと変化すること,2) この遅い変化を利用した効率的な線形解法を展開し, 以前のステップで計算した情報を用いて行列の逆転を高速化すること,3) ランダム化されたテイラー級数に基づく推定器を用いてメトロポリスフィルタステップにおける行列項の計算を高速化すること,である。
論文 参考訳（メタデータ） (2024-09-06T14:49:43Z) - Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。
特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。
主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
論文 参考訳（メタデータ） (2023-12-14T12:53:34Z) - Fast Minimization of Expected Logarithmic Loss via Stochastic Dual
Averaging [8.990961435218544]
本稿では,対数障壁を用いたB$-sample双対平均化法を提案する。
Poisson逆問題に対して、我々のアルゴリズムは$smashtildeO(d3/varepsilon2)$ timeで$varepsilon$解を得る。
量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは $smashtildeO(d3/varepsilon2)$ time で $varepsilon$-optimal Solution を得る。
論文 参考訳（メタデータ） (2023-11-05T03:33:44Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳（メタデータ） (2023-07-13T08:46:19Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z) - Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
我々は、$x_t+1=sigma(Thetastarx_t)+varepsilon_t$という形の非線形力学系を学ぶアルゴリズムを導入する。
最適なサンプル複雑性と線形ランニング時間を持つ単一軌道から重み行列$Thetastar$を復元するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-30T10:42:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。