Cover Image

Randomized Kaczmarz Methods with Beyond-Krylov Convergence

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dereziński, Michał, Needell, Deanna, Rebrova, Elizaveta, Yang, Jiaming
Format:	Preprint
Published:	2025
Subjects:	Numerical Analysis Data Structures and Algorithms Machine Learning Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems
by: Dereziński, Michał, et al.
Published: (2024)

Towards Universal Convergence of Backward Error in Linear System Solvers
by: Dereziński, Michał, et al.
Published: (2026)

Solving Dense Linear Systems Faster Than via Preconditioning
by: Dereziński, Michał, et al.
Published: (2023)

Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning
by: Dereziński, Michał, et al.
Published: (2024)

Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure
by: Dereziński, Michał, et al.
Published: (2025)

The matrix-vector complexity of $Ax=b$
by: Dereziński, Michał, et al.
Published: (2026)

Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size
by: Dereziński, Michał, et al.
Published: (2026)

Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation
by: Chenakkod, Shabarish, et al.
Published: (2026)

Iterative Refinement for $\ell_p$-norm Regression
by: Adil, Deeksha, et al.
Published: (2019)

Distributed Least Squares in Small Space via Sketching and Bias Reduction
by: Garg, Sachin, et al.
Published: (2024)

Block Matrix and Tensor Randomized Kaczmarz Methods for Linear Feasibility Problems
by: Zhang, Minxin, et al.
Published: (2024)

Optimal Embedding Dimension for Sparse Subspace Embeddings
by: Chenakkod, Shabarish, et al.
Published: (2023)

Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors
by: Chenakkod, Shabarish, et al.
Published: (2025)

Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity
by: Chenakkod, Shabarish, et al.
Published: (2024)

Well-Conditioned Oblivious Perturbations in Linear Space
by: Chenakkod, Shabarish, et al.
Published: (2026)

Near-Linear Runtime for a Classical Matrix Preconditioning Algorithm
by: Cai, Xufeng, et al.
Published: (2025)

On Smale's 17th problem over the reals
by: Montanari, Andrea, et al.
Published: (2024)

Randomized Kaczmarz in Adversarial Distributed Setting
by: Huang, Longxiu, et al.
Published: (2023)

Oracle-based Uniform Sampling from Convex Bodies
by: Dang, Thanh, et al.
Published: (2025)

Constrained and Composite Sampling via Proximal Sampler
by: Dang, Thanh, et al.
Published: (2026)

Negative Stepsizes Make Gradient-Descent-Ascent Converge
by: Shugart, Henry, et al.
Published: (2025)

Convergence analysis of wide shallow neural operators within the framework of Neural Tangent Kernel
by: Xu, Xianliang, et al.
Published: (2024)

Combinatorial Sparse PCA Beyond the Spiked Identity Model
by: Kumar, Syamantak, et al.
Published: (2026)

Lower bounds for trace estimation via Block Krylov and other methods
by: Yu, Shi Jie
Published: (2025)

Gradient-Free Method for Heavily Constrained Nonconvex Optimization
by: Shi, Wanli, et al.
Published: (2024)

Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling
by: Kook, Yunbum, et al.
Published: (2023)

Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods
by: Tarzanagh, Davoud Ataee, et al.
Published: (2022)

Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method
by: Garg, Sachin, et al.
Published: (2025)

Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion
by: Cai, Yang, et al.
Published: (2022)

Omnipredicting Single-Index Models with Multi-Index Models
by: Hu, Lunjia, et al.
Published: (2024)

Beyond Non-Degeneracy: Revisiting Certainty Equivalent Heuristic for Online Linear Programming
by: Chen, Yilun, et al.
Published: (2025)

Stochastic gradient descent for streaming linear and rectified linear systems with adversarial corruptions
by: Jeong, Halyun, et al.
Published: (2024)

Convergence Analysis of Two-Layer Neural Networks under Gaussian Input Masking
by: Kolomvaki, Afroditi, et al.
Published: (2026)

Worth Their Weight: Randomized and Regularized Block Kaczmarz Algorithms without Preprocessing
by: Goldshlager, Gil, et al.
Published: (2025)

Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
by: Bach, Eleon, et al.
Published: (2025)

Optimal Bounds for Adversarial Constrained Online Convex Optimization
by: Ferreira, Ricardo N., et al.
Published: (2025)

Min-Max Optimization Is Strictly Easier Than Variational Inequalities
by: Shugart, Henry, et al.
Published: (2025)

Online Convex Optimization with Switching Cost with Only One Single Gradient Evaluation
by: Shah, Harsh, et al.
Published: (2025)

Distributionally Robust Optimization with Adversarial Data Contamination
by: Li, Shuyao, et al.
Published: (2025)

Discrete and Continuous Difference of Submodular Minimization
by: Orfanides, George, et al.
Published: (2025)