6 papers
Debiasing Random Oblique Projections for Subsampled OLS and Fast CUR in High Dimensions
Chengmei Niu, Sachin Garg, Michał Dereziński +1
Random sampling is a fundamental tool in modern machine learning and numerical linear algebra for reducing the computational cost of large-scale matrix problems. Existing analyses,…
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,…
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…
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…
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…
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…