Pith. sign in

REVIEW 1 cited by

Randomized Kaczmarz with tail averaging

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2411.19877 v3 pith:RTMB24YL submitted 2024-11-29 math.NA cs.NA

Ethan N. Epperly , Gil Goldshlager , Robert J. Webber This is my paper · ORCID
classification math.NAcs.NA
keywords least-squareskaczmarzproblemsrandomizedconsistentinconsistentlinearmethod
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

The randomized Kaczmarz (RK) method is a well-known approach for solving linear least-squares problems with a large number of rows. RK accesses and processes just one row at a time, leading to exponentially fast convergence for consistent linear systems. However, RK fails to converge to the least-squares solution for inconsistent systems. This work presents a simple fix: average the RK iterates produced in the tail part of the algorithm. The proposed tail-averaged randomized Kaczmarz (TARK) converges for both consistent and inconsistent least-squares problems at a polynomial rate, which is known to be optimal for any row-access method. An extension of TARK also leads to efficient solutions for ridge-regularized least-squares problems.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A Sketch-and-Project Analysis of Subsampled Natural Gradient Algorithms

    cs.LG 2025-08 conditional novelty 6.0 of 10

    For linear least squares, SNGD and SPRING are proved equivalent to accelerated regularized Kaczmarz methods, yielding the first fast rates and first SPRING guarantee; the general quadratic analysis holds under strong ...

Pith tools