A Note on Randomized Kaczmarz Algorithm for Solving Doubly-Noisy Linear Systems

• URL: http://arxiv.org/abs/2308.16904v2
• Date: Fri, 23 Aug 2024 11:15:29 GMT
• Title: A Note on Randomized Kaczmarz Algorithm for Solving Doubly-Noisy Linear Systems
• Authors: El Houcine Bergou, Soumia Boucherouite, Aritra Dutta, Xin Li, Anna Ma,
• Abstract summary: Large-scale linear systems, $Ax=b$, frequently arise in practice and demand effective iterative solvers. In this paper, we analyze the convergence of the randomized Kaczmarz algorithm for noisy systems.
• Score: 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.}

Related papers

• Error-mitigated fermionic classical shadows on noisy quantum devices [0.3775283002059579]
  Classical shadow (CS) algorithms offer a solution by reducing the number of quantum state copies needed. We propose an error-mitigated CS algorithm assuming gate-independent, time-stationary, and Markovian (GTM) noise. Our algorithm efficiently estimates $k$-RDMs with $widetildemathcal O(knk)$ state copies and $widetildemathcal O(sqrtn)$ calibration measurements for GTM noise.
  arXiv  Detail & Related papers  (2023-10-19T13:27:19Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Delayed Feedback in Kernel Bandits [16.11544965325835]
  Black box optimisation of an unknown function is a ubiquitous problem in machine learning, academic research and industrial production. We consider a kernel bandit problem underally delayed feedback, and propose an algorithm with $tildemathcalO(sqrtGamma_k(T)T+mathbbE[tau]Gamma_k(T))$ This represents a significant improvement over the state of the art regret bound of $tildemathcalO(Gamma_k(T)sqrtT
  arXiv  Detail & Related papers  (2023-02-01T12:03:19Z)
• Higher degree sum-of-squares relaxations robust against oblivious outliers [14.58610686291355]
  We consider estimation models of the form $Y=X*+N$, where $X*$ is some $m$-dimensional signal we wish to recover. We introduce a family of algorithms that under mild assumptions recover the signal $X*$ in all estimation problems for which there exists a sum-of-squares algorithm.
  arXiv  Detail & Related papers  (2022-11-14T13:09:12Z)
• Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimes [5.526935605535376]
  We find a sample complexity bound for learning a simplex from noisy samples. We show that as long as $mathrmSNRgeOmegaleft(K1/2right)$, the sample complexity of the noisy regime has the same order to that of the noiseless case.
  arXiv  Detail & Related papers  (2022-09-09T23:35:25Z)
• Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs [111.75736569611159]
  We propose the first computationally efficient horizon-free algorithm for linear mixture MDPs. Our algorithm adapts a weighted least square estimator for the unknown transitional dynamic. This also improves upon the best-known algorithms in this setting when $sigma_k2$'s are known.
  arXiv  Detail & Related papers  (2022-05-23T17:59:18Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  We study the problem of estimating the value of a known smooth function $f$ at an unknown point $boldsymbolmu in mathbbRn$, where each component $mu_i$ can be sampled via a noisy oracle. We design an instance-adaptive algorithm that learns to sample according to the importance of each coordinate, and with probability at least $1-delta$ returns an $epsilon$ accurate estimate of $f(boldsymbolmu)$.
  arXiv  Detail & Related papers  (2022-03-18T18:50:52Z)
• Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits [88.6139446295537]
  We study the problem of online generalized linear regression in the setting of a generalized linear model with possibly unbounded additive noise. We provide a sharp analysis of the classical follow-the-regularized-leader (FTRL) algorithm to cope with the label noise. We propose an algorithm based on FTRL to achieve the first variance-aware regret bound.
  arXiv  Detail & Related papers  (2022-02-28T08:25:26Z)
• Noise Regularizes Over-parameterized Rank One Matrix Recovery, Provably [42.427869499882206]
  We parameterize the rank one matrix $Y*$ by $XXtop$, where $Xin Rdtimes d$. We then show that under mild conditions, the estimator, obtained by the randomly perturbed gradient descent algorithm using the square loss function, attains a mean square error of $O(sigma2/d)$. In contrast, the estimator obtained by gradient descent without random perturbation only attains a mean square error of $O(sigma2)$.
  arXiv  Detail & Related papers  (2022-02-07T21:53:51Z)
• Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
  We introduce algorithms for learning nonlinear dynamical systems of the form $x_t+1=sigma(Thetastarx_t)+varepsilon_t$. We give an algorithm that recovers the weight matrix $Thetastar$ from a single trajectory with optimal sample complexity and linear running time.
  arXiv  Detail & Related papers  (2020-04-30T10:42:48Z)
• Naive Exploration is Optimal for Online LQR [49.681825576239355]
  We show that the optimal regret scales as $widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$, where $T$ is the number of time steps, $d_mathbfu$ is the dimension of the input space, and $d_mathbfx$ is the dimension of the system state. Our lower bounds rule out the possibility of a $mathrmpoly(logT)$-regret algorithm, which had been
  arXiv  Detail & Related papers  (2020-01-27T03:44:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.