Stochastic rounding turns rounding errors into a residual: randomized Kaczmarz in low precision

Abstract Randomized Kaczmarz with iterates stored in a low-precision format stalls at an error floor. For round-to-nearest, the known bound on this floor grows like \(\:{\stackrel{\sim}{\kappa\:}}^{2}u\), where \(\:\stackrel{\sim}{\kappa\:}={‖A‖}_{F}‖{A}^{+}‖\) is the Demmel condition number and \(\:u\) the unit roundoff, and iterative refinement guarantees \(\:\stackrel{\sim}{\kappa\:}u\). With stochastic rounding, the rounding errors form a martingale difference sequence and act exactly like an additional inconsistency of the linear system: the long-run mean of \(\:{‖A({\widehat{x}}_{k}-{x}_{\star\:})‖}^{2}\) equals \(\:{‖{r}_{\star\:}‖}^{2}+{‖A‖}_{F}^{2}\eta\:\), where \(\:{r}_{\star\:}\) is the least-squares residual and \(\:\eta\:\) the mean squared rounding error per step. We call \(\:{‖A‖}_{F}\sqrt{\eta\:}\) the rounding residual. This identity yields a floor of order \(\:\stackrel{\sim}{\kappa\:}u\) without refinement, an exact trace formula for the stationary second moment, an additive split of the error into an exact-arithmetic part and a rounding part, a \(\:{T}^{-1/2}\) rate for tail averages, and a bias bound for stochastic rounding with few random bits; at most \(\:{\text{l}\text{o}\text{g}}_{2}\stackrel{\sim}{\kappa\:}+4\) bits were needed in our tests. For random singular vectors the trace formula is well approximated by the floor \(\:\left(\eta\:\right({\kappa\:}_{F}^{2}+{n}^{2})/(2n){)}^{1/2}\) in terms of the measured \(\:\eta\:\), with \(\:{\kappa\:}_{F}={‖A‖}_{F}{‖{A}^{+}‖}_{F}\). In experiments with binary16, bfloat16 and four singular value profiles, this prediction matches the median measured floor to within 4% in all 43 configurations, with \(\:n\) from 50 to 500 and \(\:\stackrel{\sim}{\kappa\:}\) from 10 to 640, and at \(\:\stackrel{\sim}{\kappa\:}=640\) in binary16 round-to-nearest is 12 times less accurate than stochastic rounding for the iterates and 37 times for their tail averages.

Authors

Institutions

Publication Details

Journal
Research Square
Published
2026-11-17
DOI
https://doi.org/10.21203/rs.3.rs-11576594/v1
Primary Topic
Matrix Theory and Algorithms
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Stochastic rounding turns rounding errors into a residual: randomized Kaczmarz in low precision

Liuwen Chang
2 links
Research Square
Matrix Theory and Algorithms
preprint

Stochastic rounding turns rounding errors into a residual: randomized Kaczmarz in low precision

Liuwen Chang
preprint en

Abstract

Abstract Randomized Kaczmarz with iterates stored in a low-precision format stalls at an error floor. For round-to-nearest, the known bound on this floor grows like \(\:{\stackrel{\sim}{\kappa\:}}^{2}u\), where \(\:\stackrel{\sim}{\kappa\:}={‖A‖}_{F}‖{A}^{+}‖\) is the Demmel condition number and \(\:u\) the unit roundoff, and iterative refinement guarantees \(\:\stackrel{\sim}{\kappa\:}u\). With stochastic rounding, the rounding errors form a martingale difference sequence and act exactly like an additional inconsistency of the linear system: the long-run mean of \(\:{‖A({\widehat{x}}_{k}-{x}_{\star\:})‖}^{2}\) equals \(\:{‖{r}_{\star\:}‖}^{2}+{‖A‖}_{F}^{2}\eta\:\), where \(\:{r}_{\star\:}\) is the least-squares residual and \(\:\eta\:\) the mean squared rounding error per step. We call \(\:{‖A‖}_{F}\sqrt{\eta\:}\) the rounding residual. This identity yields a floor of order \(\:\stackrel{\sim}{\kappa\:}u\) without refinement, an exact trace formula for the stationary second moment, an additive split of the error into an exact-arithmetic part and a rounding part, a \(\:{T}^{-1/2}\) rate for tail averages, and a bias bound for stochastic rounding with few random bits; at most \(\:{\text{l}\text{o}\text{g}}_{2}\stackrel{\sim}{\kappa\:}+4\) bits were needed in our tests. For random singular vectors the trace formula is well approximated by the floor \(\:\left(\eta\:\right({\kappa\:}_{F}^{2}+{n}^{2})/(2n){)}^{1/2}\) in terms of the measured \(\:\eta\:\), with \(\:{\kappa\:}_{F}={‖A‖}_{F}{‖{A}^{+}‖}_{F}\). In experiments with binary16, bfloat16 and four singular value profiles, this prediction matches the median measured floor to within 4% in all 43 configurations, with \(\:n\) from 50 to 500 and \(\:\stackrel{\sim}{\kappa\:}\) from 10 to 640, and at \(\:\stackrel{\sim}{\kappa\:}=640\) in binary16 round-to-nearest is 12 times less accurate than stochastic rounding for the iterates and 37 times for their tail averages.

Research Square
Xuchang University (CN)
Matrix Theory and Algorithms
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon