RidgeSketch: A Fast Sketching Based Solver for Large Scale Ridge Regression

DOI10.1137/21M1422963MaRDI QIDQ5099418

Nidham Gazagnadou, Mark Ibrahim, Robert M. Gower

Publication date: 31 August 2022

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2105.05565

zbMATH Keywords

accelerationmomentumrandomized coordinate descentrandomized numerical linear algebrarandomized sketchingsketch-and-project methods

Mathematics Subject Classification ID

Ridge regression; shrinkage estimators (Lasso) (62J07) Large-scale problems in mathematical programming (90C06) Numerical optimization and variational techniques (65K10) Complexity and performance of numerical algorithms (65Y20) Probabilistic methods, stochastic differential equations (65C99)

Related Items (1)

Ridgesketch

Uses Software

• Unnamed Item
• SciPy
• NumPy
• Scikit
• Blendenpik
• Python

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Single projection Kaczmarz extended algorithms
• A fast randomized algorithm for the approximation of matrices
• A randomized Kaczmarz algorithm with exponential convergence
• Fast dimension reduction using Rademacher series on dual BCH codes
• Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
• Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
• Coordinate descent algorithms
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• Improved Matrix Algorithms via the Subsampled Randomized Hadamard Transform
• Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error
• Randomized Sketches of Convex Programs With Sharp Guarantees
• IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM
• Randomized Algorithms for Matrices and Data
• Blendenpik: Supercharging LAPACK's Least-Squares Solver
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• Low-Rank Approximation and Regression in Input Sparsity Time
• Extensions of Lipschitz mappings into a Hilbert space
• An accelerated randomized Kaczmarz algorithm
• Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods
• Randomized Iterative Methods for Linear Systems
• LAPACK Users' Guide
• Unified Matrix Treatment of the Fast Walsh-Hadamard Transform
• On Greedy Randomized Kaczmarz Method for Solving Large Sparse Linear Systems
• An improved data stream summary: the count-min sketch and its applications
• Tikhonov Regularization and Total Least Squares
• Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
• Sketched Newton--Raphson
• Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• Faster Randomized Block Kaczmarz Algorithms
• A New Theoretical Estimate for the Convergence Rate of the Maximal Weighted Residual Kaczmarz Algorithm
• Kernel Ridge Regression
• A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility
• Understanding Machine Learning
• Some methods of speeding up the convergence of iteration methods
• Methods of conjugate gradients for solving linear systems

This page was built for publication: RidgeSketch: A Fast Sketching Based Solver for Large Scale Ridge Regression