How AI settled the complexity of the oldest SGD algorithm

DOI10.48550/arXiv.2606.29593MaRDI QIDQ7270425arXivFDO

Authors Michał Dereziński, Xiaoyu Dong

Publication date 28 June 2026

Published in arXiv

Tldr We show that the Kaczmarz algorithm achieves a worst-case linear convergence rate with an optimal dependence on the condition number of the matrix and provide a tight bound for the first time.

Full work available at URL https://doi.org/10.48550/arXiv.2606.29593

arXiv classification

cs.LGstat.MLcs.AImath.NAmath.OC

This page was built for publication: How AI settled the complexity of the oldest SGD algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7270425)