Surrogate-based autotuning for randomized sketching algorithms in regression problems

DOI10.1137/23M1597526MaRDI QIDQ6987480zbMATH OpenFDO

Authors Young Hyun Cho, James Demmel, Michał Dereziński, Haoyun Li, Hengrui Luo, Michael W. Mahoney, Riley Murray

Publication date 6 May 2025

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

Full work available at URL https://escholarship.org/uc/item/85s5z8tj

zbMATH Keywords

least squares problemautotuningBayesian optimizationrandomized numerical linear algebrasketching algorithm

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Numerical solutions to overdetermined systems, pseudoinverses (65F20)

Cites work

• scientific article; zbMATH DE number 852536 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• 10.1162/153244303321897663
• A Distance-Preserving Matrix Sketch
• A fast randomized algorithm for overdetermined linear least-squares regression
• A set of level 3 basic linear algebra subprograms
• A sparse Johnson-Lindenstrauss transform
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• BLIS: a framework for rapidly instantiating BLAS functionality
• Blendenpik: Supercharging LAPACK's Least-Squares Solver
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Determinantal point processes in randomized numerical linear algebra
• Estimating Extremal Eigenvalues and Condition Numbers of Matrices
• Fast approximation of matrix coherence and statistical leverage
• Faster least squares approximation
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Global sensitivity indices for nonlinear mathematical models and their Monte Carlo estimates
• Hybrid Parameter Search and Dynamic Model Selection for Mixed-Variable Bayesian Optimization
• Hyperband: a novel bandit-based approach to hyperparameter optimization
• Improved matrix algorithms via the subsampled randomized Hadamard transform
• Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
• LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
• LSRN: A parallel iterative solver for strongly over- or underdetermined systems
• Latin hypercube sampling with multidimensional uniformity
• Lectures on randomized numerical linear algebra
• Low rank approximation and regression in input sparsity time
• Low-rank approximation and regression in input sparsity time
• Methods of conjugate gradients for solving linear systems
• Nearly tight oblivious subspace embeddings by trace inequalities
• Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
• OSNAP: faster numerical linear algebra algorithms via sparser subspace embeddings
• RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems
• Randomized Algorithms for Matrices and Data
• Randomized numerical linear algebra: Foundations and algorithms
• Sampling algorithms for l₂ regression and applications
• Sketching as a tool for numerical linear algebra
• Sobol' indices and Shapley value
• Variance based sensitivity analysis of model output. Design and estimator for the total sensitivity index

Cited in

(1)

• Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers

This page was built for publication: Surrogate-based autotuning for randomized sketching algorithms in regression problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6987480)