論文の概要: A Note on Randomized Kaczmarz Algorithm for Solving Doubly-Noisy Linear Systems
- arxiv url: http://arxiv.org/abs/2308.16904v2
- Date: Fri, 23 Aug 2024 11:15:29 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-26 20:18:44.253733
- Title: A Note on Randomized Kaczmarz Algorithm for Solving Doubly-Noisy Linear Systems
- Title（参考訳）: 二重雑音線形システムのランダム化Kaczmarzアルゴリズムに関する一考察
- Authors: El Houcine Bergou, Soumia Boucherouite, Aritra Dutta, Xin Li, Anna Ma,
- Abstract要約: 大規模線形システムである$Ax=b$は、実際にしばしば発生し、効果的な反復解法を必要とする。
本稿では,雑音系に対するランダム化Kaczmarzアルゴリズムの収束性について解析する。
- 参考スコア（独自算出の注目度）: 6.334599472563052
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Large-scale linear systems, $Ax=b$, frequently arise in practice and demand effective iterative solvers. Often, these systems are noisy due to operational errors or faulty data-collection processes. In the past decade, the randomized Kaczmarz (RK) algorithm has been studied extensively as an efficient iterative solver for such systems. However, the convergence study of RK in the noisy regime is limited and considers measurement noise in the right-hand side vector, $b$. Unfortunately, in practice, that is not always the case; the coefficient matrix $A$ can also be noisy. In this paper, we analyze the convergence of RK for {\textit{doubly-noisy} linear systems, i.e., when the coefficient matrix, $A$, has additive or multiplicative noise, and $b$ is also noisy}. In our analyses, the quantity $\tilde R=\| \tilde A^{\dagger} \|^2 \|\tilde A \|_F^2$ influences the convergence of RK, where $\tilde A$ represents a noisy version of $A$. We claim that our analysis is robust and realistically applicable, as we do not require information about the noiseless coefficient matrix, $A$, and considering different conditions on noise, we can control the convergence of RK. {We perform numerical experiments to substantiate our theoretical findings.}
- Abstract（参考訳）: 大規模線形システムである$Ax=b$は、実際にしばしば発生し、効果的な反復解法を必要とする。
多くの場合、これらのシステムは運用上のエラーや故障したデータ収集プロセスのためにうるさい。
過去10年間、ランダム化カッツマルツ(RK)アルゴリズムは、そのようなシステムに対する効率的な反復解法として広く研究されてきた。
しかし、雑音系におけるRKの収束の研究は限定的であり、右辺ベクトルの計測ノイズを$b$とみなす。
残念ながら、実際には必ずしもそうではない。係数行列 $A$ もうるさい。
本稿では, 係数行列 $A$ が加法的あるいは乗法的ノイズを持ち, $b$ もノイジーであるとき, 線形系に対する RK の収束を解析する。
我々の分析では、$\tilde R=\| \tilde A^{\dagger} \|^2 \|\tilde A \|_F^2$ が RK の収束に影響を与える。
我々は、ノイズレス係数行列($A$)に関する情報を必要とせず、ノイズの異なる条件を考慮してRKの収束を制御できるので、我々の分析は堅牢で現実的に適用可能であると主張する。
理論的知見を裏付ける数値実験を行う。
※
関連論文リスト
- Error-mitigated fermionic classical shadows on noisy quantum devices [0.3775283002059579]
古典的シャドウ (CS) アルゴリズムは、必要な量子状態コピー数を減らして解を提供する。
本稿では,ゲート独立性,時間定常性,マルコフ雑音(GTM)を仮定した誤り緩和型CSアルゴリズムを提案する。
提案アルゴリズムは,GTMノイズに対する$widetildemathcal O(knk)$状態コピーと$widetildemathcal O(sqrtn)$キャリブレーションによる$k$-RDMを効率的に推定する。
論文 参考訳（メタデータ） (2023-10-19T13:27:19Z) - 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) - Delayed Feedback in Kernel Bandits [16.11544965325835]
未知の機能のブラックボックス最適化は、機械学習、学術研究、工業生産においてユビキタスな問題である。
カーネルの帯域幅問題について検討し,$tildemathcalO(sqrtGamma_k(T)T+mathbbE[tau]Gamma_k(T))$を用いたアルゴリズムを提案する。
これは、 $tildemathcalO(Gamma_k(T)sqrtT のアート・リトリート境界に対する顕著な改善を示している。
論文 参考訳（メタデータ） (2023-02-01T12:03:19Z) - Higher degree sum-of-squares relaxations robust against oblivious
outliers [14.58610686291355]
我々は、$Y=X*+N$という形の推定モデルを考える。
本稿では,2乗推定アルゴリズムが存在するすべての推定問題において,軽度仮定の下で信号が$X*$に回復するアルゴリズム群を紹介する。
論文 参考訳（メタデータ） (2022-11-14T13:09:12Z) - Sample Complexity Bounds for Learning High-dimensional Simplices in
Noisy Regimes [5.526935605535376]
ノイズの多いサンプルから単純さを学習するために、サンプルの複雑さが結びついているのがわかります。
我々は、$mathrmSNRgeOmegaleft(K1/2right)$ である限り、ノイズのないシステムのサンプルの複雑さは、ノイズのないケースのそれと同じ順序であることを示す。
論文 参考訳（メタデータ） (2022-09-09T23:35:25Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳（メタデータ） (2022-05-23T17:59:18Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits [88.6139446295537]
一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
本稿では,FTRLに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-28T08:25:26Z) - Noise Regularizes Over-parameterized Rank One Matrix Recovery, Provably [42.427869499882206]
階数 1 の行列 $Y*$ by $XXtop$ をパラメータ化します。
次に,2乗損失関数を用いたランダムな摂動勾配降下法により得られた推定値の平均2乗誤差が$O(sigma2/d)$であることを示す。
対照的に、ランダムな摂動を伴わない勾配降下から得られる推定器は、平均2乗誤差が$O(sigma2)$となる。
論文 参考訳（メタデータ） (2022-02-07T21:53:51Z) - Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
我々は、$x_t+1=sigma(Thetastarx_t)+varepsilon_t$という形の非線形力学系を学ぶアルゴリズムを導入する。
最適なサンプル複雑性と線形ランニング時間を持つ単一軌道から重み行列$Thetastar$を復元するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-30T10:42:48Z) - Naive Exploration is Optimal for Online LQR [49.681825576239355]
最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。
我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
論文 参考訳（メタデータ） (2020-01-27T03:44:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。