6 citations · 9 across the 23 of their papers we have counts for
25 papers
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-stand…
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…
Well-Conditioned Oblivious Perturbations in Linear Space
Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong +1
Perturbing a deterministic -dimensional matrix with small Gaussian noise is a cornerstone of smoothed analysis of algorithms [Spielman and Teng, JACM 2004], as it reduces the co…
Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size
Michał Dereziński, Xiaoyu Dong
We study last-iterate convergence of SGD with greedy step size over smooth quadratics in the interpolation regime, a setting which captures the classical Randomized Kaczmarz algori…
Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop
Noah Amsel, Yves Baumann, Paul Beckman +33
This document presents a series of open questions arising in matrix computations, i.e., the numerical solution of linear algebra problems. It is a result of working groups at the w…
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…
Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors
Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong
We give a proof of the conjecture of Nelson and Nguyen [FOCS 2013] on the optimal dimension and sparsity of oblivious subspace embeddings, up to sub-polylogarithmic factors: For an…
Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method
Sachin Garg, Michał Dereziński
The Nyström method is a popular low-rank approximation technique for large matrices that arise in kernel methods and convex optimization. Yet, when the data exhibits heavy-tailed s…
Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure
Michał Dereziński, Aaron Sidford
We provide new high-accuracy randomized algorithms for solving linear systems and regression problems that are well-conditioned except for large singular values. For solving su…
Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project
Pratik Rathore, Zachary Frangella, Sachin Garg +3
Gaussian processes (GPs) play an essential role in biostatistics, scientific machine learning, and Bayesian optimization for their ability to provide probabilistic predictions and…
Randomized Kaczmarz Methods with Beyond-Krylov Convergence
Michał Dereziński, Deanna Needell, Elizaveta Rebrova +1
Randomized Kaczmarz methods form a family of linear system solvers which converge by repeatedly projecting their iterates onto randomly sampled equations. While effective in some c…
Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity
Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong
An oblivious subspace embedding is a random matrix such that, for any -dimensional subspace, with high probability preserves the norms of all vectors in that…
Have ASkotch: A Neat Solution for Large-scale Kernel Ridge Regression
Pratik Rathore, Zachary Frangella, Jiaming Yang +2
Kernel ridge regression (KRR) is a fundamental computational tool, appearing in problems that range from computational chemistry to health analytics, with a particular interest due…
Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning
Michał Dereziński, Michael W. Mahoney
Large matrices arise in many machine learning and data analysis applications, including as representations of datasets, graphs, model weights, and first and second-order derivative…
Stochastic Newton Proximal Extragradient Method
Ruichen Jiang, Michał Dereziński, Aryan Mokhtari
Stochastic second-order methods achieve fast local convergence in strongly convex optimization by using noisy Hessian estimates to precondition the gradient. However, these methods…
Distributed Least Squares in Small Space via Sketching and Bias Reduction
Sachin Garg, Kevin Tan, Michał Dereziński
Matrix sketching is a powerful tool for reducing the size of large data matrices. Yet there are fundamental limitations to this size reduction when we want to recover an accurate e…
Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning
Michał Dereziński, Christopher Musco, Jiaming Yang
We present a new class of preconditioned iterative methods for solving linear systems of the form . Our methods are based on constructing a low-rank Nyström approximation t…
Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems
Michał Dereziński, Daniel LeJeune, Deanna Needell +1
Despite being a key bottleneck in many machine learning tasks, the cost of solving large linear systems has proven challenging to quantify due to problem-dependent quantities such…
Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients
Sachin Garg, Albert S. Berahas, Michał Dereziński
We show that, for finite-sum minimization problems, incorporating partial second-order information of the objective function can dramatically improve the robustness to mini-batch s…
HERTA: A High-Efficiency and Rigorous Training Algorithm for Unfolded Graph Neural Networks
Yongyi Yang, Jiaming Yang, Wei Hu +1
As a variant of Graph Neural Networks (GNNs), Unfolded GNNs offer enhanced interpretability and flexibility over traditional designs. Nevertheless, they still suffer from scalabili…
Solving Dense Linear Systems Faster Than via Preconditioning
Michał Dereziński, Jiaming Yang
We give a stochastic optimization algorithm that solves a dense real-valued linear system , returning such that in time: $…