Solving Ridge Regression using Sketched Preconditioned SVRG

We develop a novel preconditioning method for ridge regression, based on recent linear sketching methods. By equipping Stochastic Variance Reduced Gradient (SVRG) with this preconditioning process, we obtain a significant speed-up relative to fast stochastic methods such as SVRG, SDCA and SAG.

cs.LG Computer Science Mathematics

Paper

References (26)

01SDCA without Duality, Regularization, and Individual ConvexityS. Shalev-Shwartz2016 · International Conference on Machine Learning · 108 citations In Library

02Tightening the Sample Complexity of Empirical Risk Minimization via Preconditioned StabilityAlon Gonen, S. Shalev-Shwartz2016 · arXiv.org · 7 citations

03Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimizationRoy Frostig, Rong Ge, S. Kakade et al.2015 · International Conference on Machine Learning · 157 citations In Library

04A Universal Catalyst for First-Order OptimizationHongzhou Lin, J. Mairal, Z. Harchaoui2015 · Neural Information Processing Systems · 406 citations In Library

05Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value DecompositionCameron Musco, Christopher Musco2015 · Neural Information Processing Systems · 310 citations In Library

06Sketching as a Tool for Numerical Linear AlgebraDavid P. Woodruff2014 · Foundations and Trends® in Theoretical Computer Science · 1.4k citations

07On Data Preconditioning for Regularized Loss MinimizationTianbao Yang, Rong Jin, Shenghuo Zhu et al.2014 · Machine-mediated learning · 9 citations In Library

08Introductory Lectures on Convex Optimization - A Basic CourseY. Nesterov2014 · Applied Optimization · 6.5k citations

09A Proximal Stochastic Gradient Method with Progressive Variance ReductionLin Xiao, Tong Zhang2014 · SIAM Journal on Optimization · 778 citations In Library

10Accelerating Stochastic Gradient Descent using Predictive Variance ReductionRie Johnson, Tong Zhang2013 · Neural Information Processing Systems · 3.0k citations

11Accelerated proximal stochastic dual coordinate ascent for regularized loss minimizationS. Shalev-Shwartz, Tong Zhang2013 · Mathematical programming · 473 citations In Library

12Randomized Algorithms for Low-Rank Matrix Factorizations: Sharp Performance BoundsRafi Witten, E. Candès2013 · Algorithmica · 78 citations

Scroll for more · 14 remaining

Similar papers

Gradient preconditioned mini-batch SGD for ridge regressionZhuan Zhang, Shuisheng Zhou, Dong Li et al.2020 · Neurocomputing · 10 citations In Library

Sketching Algorithms and Lower Bounds for Ridge RegressionPraneeth Kacham, David P. Woodruff2022 · International Conference on Machine Learning · 6 citations In Library

Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model AveragingShusen Wang, Alex Gittens, Michael W. Mahoney2017 · International Conference on Machine Learning · 89 citations In Library

Large Scale Constrained Linear Regression Revisited: Faster Algorithms via PreconditioningDi Wang, Jinhui Xu2018 · AAAI Conference on Artificial Intelligence · 5 citations In Library

Ridge Regression: Structure, Cross-Validation, and SketchingSifan Liu, Edgar Dobriban2019 · International Conference on Learning Representations · 52 citations In Library

Localized sketching for matrix multiplication and ridge regressionRakshith Sharma Srinivasa, Mark A. Davenport, Justin Romberg2020 · arXiv (Cornell University) In Library

OKRidge: Scalable Optimal k-Sparse Ridge RegressionJiachang Liu, Sam Rosen, Chudi Zhong et al.2023 · Neural Information Processing Systems · 9 citations In Library

SketchySGD: Reliable Stochastic Optimization via Randomized Curvature EstimatesZachary Frangella, Pratik Rathore, Shipu Zhao et al.2022 · arXiv (Cornell University) In Library

Sketching for Convex and Nonconvex Regularized Least Squares with Sharp GuaranteesYingzhen Yang, Ping Li2023 · International Conference on Learning Representations · 0 citations In Library

PROMISE: Preconditioned Stochastic Optimization Methods by Incorporating Scalable Curvature EstimatesZachary Frangella, Pratik Rathore, Shipu Zhao et al.2023 · arXiv (Cornell University) In Library

Source of record

arXiv

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal