6 citations · 9 across the 23 of their papers we have counts for
9 papers · 1 filter
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…