Cover Image

Near-Linear Runtime for a Classical Matrix Preconditioning Algorithm

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cai, Xufeng, Altschuler, Jason M., Diakonikolas, Jelena
Format:	Preprint
Published:	2025
Subjects:	Optimization and Control Data Structures and Algorithms Numerical Analysis
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

Optimized methods for composite optimization: a reduction perspective
by: Bok, Jinho, et al.
Published: (2025)

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

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

Accelerating Proximal Gradient Descent via Silver Stepsizes
by: Bok, Jinho, et al.
Published: (2024)

Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective
by: Diakonikolas, Jelena, et al.
Published: (2024)

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

Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule
by: Altschuler, Jason M., et al.
Published: (2023)

Stepsize Hedging: an Alternative Mechanism for Accelerating Gradient Descent
by: Altschuler, Jason M., et al.
Published: (2026)

Acceleration by Random Stepsizes: Hedging, Equalization, and the Arcsine Stepsize Schedule
by: Altschuler, Jason M., et al.
Published: (2024)

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

Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise
by: Li, Shuyao, et al.
Published: (2024)

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

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

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

Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing
by: Li, Shuyao, et al.
Published: (2024)

Randomized Kaczmarz Methods with Beyond-Krylov Convergence
by: Dereziński, Michał, et al.
Published: (2025)

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

Robust Learning of a Group DRO Neuron
by: Cao, Guyang, et al.
Published: (2026)

Robustly Learning Single-Index Models via Alignment Sharpness
by: Zarifis, Nikos, et al.
Published: (2024)

Negative Momentum for Convex-Concave Optimization
by: Shugart, Henry, et al.
Published: (2026)

Algorithmic warm starts for Hamiltonian Monte Carlo
by: Zhang, Matthew S., et al.
Published: (2026)

Shifted Composition III: Local Error Framework for KL Divergence
by: Altschuler, Jason M., et al.
Published: (2024)

Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
by: Spielman, Daniel A., et al.
Published: (2006)

(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs
by: Hunkenschröder, Christoph, et al.
Published: (2025)

Shifted Composition IV: Toward Ballistic Acceleration for Log-Concave Sampling
by: Altschuler, Jason M., et al.
Published: (2025)

Solving Linear Programs with Fast Online Learning Algorithms
by: Gao, Wenzhi, et al.
Published: (2021)

Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
by: Gu, Yuzhou, et al.
Published: (2023)

Approximating $q \rightarrow p$ Norms of Non-Negative Matrices in Nearly-Linear Time
by: Objois, Étienne, et al.
Published: (2025)

Scalable First-Order Interior Point Trust Region Algorithms for Linearly Constrained Optimization
by: Su, Yuexin, et al.
Published: (2026)

Stability of the Lanczos Method for Matrix Function Approximation
by: Musco, Cameron, et al.
Published: (2017)

Adaptive Matrix Sparsification and Applications to Empirical Risk Minimization
by: Liu, Yang P., et al.
Published: (2025)

Near-Optimal Sample Complexity for MDPs via Anchoring
by: Lee, Jongmin, et al.
Published: (2025)

Revisiting Approximate Leverage Score Sketching for Matrix Least Squares
by: Larsen, Brett W., et al.
Published: (2022)

Near-Optimal Dynamic Policies for Joint Replenishment in Continuous/Discrete Time
by: Segev, Danny
Published: (2025)

Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss
by: Wang, Hao, et al.
Published: (2024)

Near-optimal hierarchical matrix approximation from matrix-vector products
by: Chen, Tyler, et al.
Published: (2024)

Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop
by: Amsel, Noah, et al.
Published: (2026)