論文の概要: Solving Dense Linear Systems Faster than via Preconditioning
- arxiv url: http://arxiv.org/abs/2312.08893v1
- Date: Thu, 14 Dec 2023 12:53:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-15 22:12:29.504612
- Title: Solving Dense Linear Systems Faster than via Preconditioning
- Title(参考訳): プレコンディショニングより高速な高密度線形システムの解法
- Authors: Micha{\l} Derezi\'nski and Jiaming Yang
- Abstract要約: 我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。
特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。
主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
- 参考スコア(独自算出の注目度): 15.781447266000159
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We give a stochastic optimization algorithm that solves a dense $n\times n$
real-valued linear system $Ax=b$, returning $\tilde x$ such that $\|A\tilde
x-b\|\leq \epsilon\|b\|$ in time: $$\tilde
O((n^2+nk^{\omega-1})\log1/\epsilon),$$ where $k$ is the number of singular
values of $A$ larger than $O(1)$ times its smallest positive singular value,
$\omega < 2.372$ is the matrix multiplication exponent, and $\tilde O$ hides a
poly-logarithmic in $n$ factor. When $k=O(n^{1-\theta})$ (namely, $A$ has a
flat-tailed spectrum, e.g., due to noisy data or regularization), this improves
on both the cost of solving the system directly, as well as on the cost of
preconditioning an iterative method such as conjugate gradient. In particular,
our algorithm has an $\tilde O(n^2)$ runtime when $k=O(n^{0.729})$. We further
adapt this result to sparse positive semidefinite matrices and least squares
regression.
Our main algorithm can be viewed as a randomized block coordinate descent
method, where the key challenge is simultaneously ensuring good convergence and
fast per-iteration time. In our analysis, we use theory of majorization for
elementary symmetric polynomials to establish a sharp convergence guarantee
when coordinate blocks are sampled using a determinantal point process. We then
use a Markov chain coupling argument to show that similar convergence can be
attained with a cheaper sampling scheme, and accelerate the block coordinate
descent update via matrix sketching.
- Abstract(参考訳): n\times n$ 実数値線形系 $ax=b$ を解く確率的最適化アルゴリズムを与え、$\tilde x$ を返すと、$\|a\tilde x-b\|\leq \epsilon\|b\|$ in time: $$\tilde o((n^2+nk^{\omega-1})\log1/\epsilon)$$k$ は$a$ の特異値の数である。
k=o(n^{1-\theta})$(すなわち、$a$は、ノイズデータや正規化のため、フラットテールのスペクトルを持つ)の場合、システムを直接解決するコストと、共役勾配のような反復的手法を事前に調整するコストの両方を改善する。
特に、我々のアルゴリズムは$k=O(n^{0.729})$のときに$\tilde O(n^2)$ランタイムを持つ。
さらに、この結果はスパース正半定行列と最小二乗回帰に適応する。
主アルゴリズムはランダムなブロック座標降下法とみなすことができ、そこで鍵となる課題は、良い収束と高速な解定時間を確保することである。
本解析では,基本対称多項式に対するメジャー化の理論を用いて,座標ブロックを行列点過程を用いてサンプリングした場合の鋭い収束保証を確立する。
次に、マルコフ連鎖結合論を用いて、より安価なサンプリング方式で類似の収束が達成できることを示し、行列スケッチによるブロック座標降下更新を高速化する。
関連論文リスト
- Hardness of Low Rank Approximation of Entrywise Transformed Matrix
Products [9.661328973620531]
自然言語処理における高速アルゴリズムにインスパイアされ、エントリ変換された設定における低階近似について研究する。
我々は、平坦なスパースベクトルのレバレッジスコアの低境界に依存するStrong Exponential Time hypothesis (SETH) から、新しい還元を与える。
我々の低階アルゴリズムは行列ベクトルに依存しているため、我々の下限は、小さな行列に対してさえも$f(UV)W$は$Omega(n2-o(1))$時間を必要とすることを示すために拡張される。
論文 参考訳(メタデータ) (2023-11-03T14:56:24Z) - Structured Semidefinite Programming for Recovering Structured
Preconditioners [41.28701750733703]
正定値$mathbfK を mathbbRd times d$ と $mathrmnnz(mathbfK)$ の 0 でないエントリで与えられるアルゴリズムは、時間内に$epsilon$-optimal diagonal preconditioner を計算する。
我々は、行列辞書近似SDPと呼ばれる半定値プログラムのクラスに対して、新しいアルゴリズムを用いて結果を得る。
論文 参考訳(メタデータ) (2023-10-27T16:54:29Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - Randomized and Deterministic Attention Sparsification Algorithms for
Over-parameterized Feature Dimension [18.57735939471469]
我々は注意問題のスパシフィケーションを考慮する。
超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
論文 参考訳(メタデータ) (2023-04-10T05:52:38Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳(メタデータ) (2022-06-17T17:55:43Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳(メタデータ) (2022-04-13T22:18:47Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳(メタデータ) (2022-02-10T16:10:41Z) - Escape saddle points by a simple gradient-descent based algorithm [6.7298812735467095]
非最適化において、サドルポイントのエスケープは中心的な研究トピックである。
滑らかな関数 $fcolonmathbbRntomathbbR$ に対して、$epsilonO(log n)2/epsilon4)$ を出力する。
技術的に、我々の主な貢献は勾配のみを用いたロバストなヘッセンパワー手法の実装である。
論文 参考訳(メタデータ) (2021-11-28T07:32:54Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳(メタデータ) (2020-11-21T01:33:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。