論文の概要: Towards Universal Convergence of Backward Error in Linear System Solvers

• arxiv url: http://arxiv.org/abs/2604.16075v1
• Date: Fri, 17 Apr 2026 14:00:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-20 22:00:19.94247
• Title: Towards Universal Convergence of Backward Error in Linear System Solvers
• Title（参考訳）: 線形系解における後方誤差の普遍収束に向けて
• Authors: Michał Dereziński, Yuji Nakatsukasa, Elizaveta Rebrova,
• Abstract要約: 古典的かつ単純なリチャードソンの反復は、任意の正半定値(PSD)線形系上での$k$の後に、少なくとも1/k$(相対的な)後方誤差を生じることを示す。 この普遍収束率は、PSD線形系を$$$逆誤差に解くための$O(n2/)$複雑性アルゴリズムを意味する。 本稿では,ベンチマーク問題に対するアルゴリズムの強い数値性能について報告する。
• 参考スコア（独自算出の注目度）: 0.5677105812643582
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The quest for an algorithm that solves an $n\times n$ linear system in $O(n^2)$ time complexity, or $O(n^2 \text{poly}(1/ε))$ when solving up to $ε$ relative error, is a long-standing open problem in numerical linear algebra and theoretical computer science. There are two predominant paradigms for measuring relative error: forward error (i.e., distance from the output to the optimum solution) and backward error (i.e., distance to the nearest problem solved by the output). In most prior studies, convergence of iterative linear system solvers is measured via various notions of forward error, and as a result, depends heavily on the conditioning of the input. Yet, the numerical analysis literature has long advocated for backward error as the more practically relevant notion of approximation. In this work, we show that -- surprisingly -- the classical and simple Richardson iteration incurs at most $1/k$ (relative) backward error after $k$ iterations on any positive semidefinite (PSD) linear system, irrespective of its condition number. This universal convergence rate implies an $O(n^2/ε)$ complexity algorithm for solving a PSD linear system to $ε$ backward error, and we establish similar or better complexity when using a variety of Krylov solvers beyond Richardson. Then, by directly minimizing backward error over a Krylov subspace, we attain an even faster $O(1/k^2)$ universal rate, and we turn this into an efficient algorithm, MINBERR, with complexity $O(n^2/\sqrtε)$. We extend this approach via normal equations to solving general linear systems, for which we empirically observe $O(1/k)$ convergence. We report strong numerical performance of our algorithms on benchmark problems.
• Abstract（参考訳）: O(n^2)$時間複雑性、または$O(n^2 \text{poly}(1/ε))$を$ε$相対誤差まで解くとき、$n\times n$線形系を解くアルゴリズムの探求は、数値線型代数と理論計算機科学における長年の未解決問題である。 相対誤差を測定するための主要なパラダイムは、前方誤差(すなわち、出力から最適解までの距離)と後方誤差(すなわち、出力によって解決された最も近い問題までの距離)である。 多くの先行研究において、反復線形系解法の収束は前方誤差の様々な概念を通じて測定され、その結果、入力の条件付けに大きく依存する。 しかし、数値解析の文献は、近似のより実践的な概念として、後方誤差を長年主張してきた。 この研究で、驚くことに、古典的で単純なリチャードソンの反復は、条件数に関係なく任意の正半定値(PSD)線型系上の$k$の反復の後、少なくとも1/k$(相対的)の後方誤差を生じる。 この普遍収束速度は、PSD線形系を$ε$後方誤差に解くための$O(n^2/ε)$複雑性アルゴリズムを意味し、リチャードソン以外の様々なクリロフ解を用いても同様またはより良い複雑性を確立する。 そして、クリロフ部分空間上の後方誤差を直接最小化することにより、より高速な$O(1/k^2)$ユニバーサルレートを得ることができ、これをより効率的なアルゴリズムであるMINBERRとし、複雑さを$O(n^2/\sqrtε)$とする。 我々はこのアプローチを正規方程式から一般線型系へ拡張し、そこでは経験的に$O(1/k)$収束を観察する。 本稿では,ベンチマーク問題に対するアルゴリズムの強い数値性能について報告する。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure [16.324043075920564]
  線形システムと回帰問題を解くための新しい高精度ランダム化アルゴリズムを提供する。 我々のアルゴリズムは、これらの問題に対する高密度な入力の下で、自然の複雑さの限界をほぼマッチングする。 特異値の$k$を除くすべての値が有界な一般化平均を持つというより弱い仮定の下でも、これらの実行時間を得る方法を示す。
  論文  参考訳（メタデータ） (2025-07-15T20:48:30Z)
• Quantum linear system algorithm with optimal queries to initial state preparation [0.0]
  線形システムの量子アルゴリズムは、2つのオラクルを問合せして解状態$A-1|brangle$を生成する。 本稿では,$mathbfThetaleft (1/sqrtpright)$クエリを$O_b$に変換する量子線形系アルゴリズムを提案する。 微分方程式の解法のような様々な応用において、ブロックプレコンディショニングスキームを用いて$p$への依存をさらに改善することができる。
  論文  参考訳（メタデータ） (2024-10-23T18:00:01Z)
• Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
  多くの機械学習タスクにおいて重要なボトルネックとなっているが、大規模な線形システムの解決コストは定量化が難しいことが証明されている。 低次元構造を示すアプリケーションによって動機づけられた線形システムの解法における複雑性の微妙な概念を考察する。 線形システム $Ax = b$, すなわち $|Abarx - b| le epsilon |b|$ であるような $barx$ を求める。
  論文  参考訳（メタデータ） (2024-05-09T14:56:49Z)
• 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)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Empirical Risk Minimization in the Non-interactive Local Model of Differential Privacy [26.69391745812235]
  本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。 これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
  論文  参考訳（メタデータ） (2020-11-11T17:48:00Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。 学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-16T16:12:10Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。