18 papers
The matrix-vector complexity of
MichaÅ DereziÅski, Ethan N. Epperly, Raphael A. Meyer
Matrix--vector algorithms, particularly Krylov subspace methods, are widely viewed as the most effective algorithms for solving large systems of linear equations. This paper establ…
How AI settled the complexity of the oldest SGD algorithm
MichaÅ DereziÅski, Xiaoyu Dong
In 1937, Stefan Kaczmarz proposed a simple algorithm for solving systems of linear equations. This algorithm turned out to be the earliest known example of stochastic gradient desc…
Towards Universal Convergence of Backward Error in Linear System Solvers
MichaÅ DereziÅski, Yuji Nakatsukasa, Elizaveta Rebrova
The quest for an algorithm that solves an linear system in time complexity, or when solving up to relative error, is a long-sta…
Perfect Parallelization in Mini-Batch SGD with Classical Momentum Acceleration
Sachin Garg, MichaÅ DereziÅski
Accelerating stochastic gradient methods with classical momentum schemes, such as Polyak's heavy ball, has proven highly successful in training large-scale machine learning models,…
Numerical Instabilities in the Kaczmarz Method and Stabilization by Iterative Refinement
MichaÅ DereziÅski, Ethan N. Epperly, Deanna Needell +1
The randomized Kaczmarz method and its accelerated variants are a powerful class of iterative methods for solving large-scale linear systems, offering guaranteed convergence with l…
Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation
Shabarish Chenakkod, MichaÅ DereziÅski
The power method is one of the most fundamental tools for extracting top principal components from data through low-rank matrix approximation. Yet, when the target rank is large, t…