Beyond Expectation: Concentration Inequalities for Randomized Iterative Methods
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918218278371328 |
|---|---|
| author | Anderson, Toby Collins, Max Haddock, Jamie Lok, Jackie Rebrova, Elizaveta |
| author_facet | Anderson, Toby Collins, Max Haddock, Jamie Lok, Jackie Rebrova, Elizaveta |
| contents | Stochastic iterative methods are useful in a variety of large-scale numerical linear algebraic, machine learning, and statistical problems, in part due to their low-memory footprint. They are frequently used in a variety of applications, and thus it is imperative to have a thorough theoretical understanding of their behavior. Most theoretical convergence results for stochastic iterative methods provide bounds on the expected error of the iterates, and yield a type of average case analysis. However, understanding the behavior of these methods in the near-worst-case is desirable. For stochastic methods, this motivates providing bounds on the variance and concentration of their error, which can be used to generate confidence intervals around the bounds on their expected error.
Here, we provide upper bounds for the concentration and variance of the error of a general class of linear stochastic iterative methods, including the randomized Kaczmarz method and the randomized Gauss--Seidel method, and a more general class of nonlinear stochastic iterative methods, including the randomized Kaczmarz method for systems of linear inequalities. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_20877 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Beyond Expectation: Concentration Inequalities for Randomized Iterative Methods Anderson, Toby Collins, Max Haddock, Jamie Lok, Jackie Rebrova, Elizaveta Numerical Analysis Optimization and Control Probability 60F10, 65F10, 68W20, 60G42, 90C25 Stochastic iterative methods are useful in a variety of large-scale numerical linear algebraic, machine learning, and statistical problems, in part due to their low-memory footprint. They are frequently used in a variety of applications, and thus it is imperative to have a thorough theoretical understanding of their behavior. Most theoretical convergence results for stochastic iterative methods provide bounds on the expected error of the iterates, and yield a type of average case analysis. However, understanding the behavior of these methods in the near-worst-case is desirable. For stochastic methods, this motivates providing bounds on the variance and concentration of their error, which can be used to generate confidence intervals around the bounds on their expected error. Here, we provide upper bounds for the concentration and variance of the error of a general class of linear stochastic iterative methods, including the randomized Kaczmarz method and the randomized Gauss--Seidel method, and a more general class of nonlinear stochastic iterative methods, including the randomized Kaczmarz method for systems of linear inequalities. |
| title | Beyond Expectation: Concentration Inequalities for Randomized Iterative Methods |
| topic | Numerical Analysis Optimization and Control Probability 60F10, 65F10, 68W20, 60G42, 90C25 |
| url | https://arxiv.org/abs/2511.20877 |