Surrogate-Based Autotuning for Randomized Sketching Algorithms in Regression Problems
SIAM Journal on Matrix Analysis and Applications · 30.06.2025 · 46 (2) · 1247-1279
DOI: 10.1137/23m1597526 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Matrix Analysis and Applications, online erschienen am 25.04.2025. Verfasst von Younghyun Cho und 6 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 79 Literaturangaben. Gefördert von: Amazon, Apple, Advanced Micro Devices.
Abstract (Originalsprache)
Algorithms from Randomized Numerical Linear Algebra (RandNLA) are known to be effective in handling high-dimensional computational problems, providing high-quality empirical performance as well as strong probabilistic guarantees. However, their practical application is complicated by the fact that the user needs to set various algorithm-specific tuning parameters which are different from those used in traditional NLA. This paper demonstrates how a surrogate-based autotuning approach can be used to address fundamental problems of parameter selection in RandNLA algorithms. In particular, we provide a detailed investigation of surrogate-based autotuning for sketch-and-precondition (SAP)–based randomized least squares methods, which have been one of the great success stories in modern RandNLA. Empirical results show that our surrogate-based autotuning approach can achieve near-optimal performance with much less tuning cost than a random search (up to about 7.6x fewer trials of different parameter configurations). Moreover, while our experiments focus on least squares, our results demonstrate a general-purpose autotuning pipeline applicable to any kind of RandNLA algorithm. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: code and data available”, as a recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://gptune.lbl.gov/ . [Formula: see text]
Förderung
- Amazon
- Apple
- Advanced Micro Devices
- National Nuclear Security Administration
- Natural Sciences and Engineering Research Council of Canada
- Intel Corporation
- National Science Foundation
Zitieren
APA
Cho, Y., Demmel, J., Dereziński, M., Li, H., Luo, H., Mahoney, M., & Murray, R. (2025). Surrogate-Based Autotuning for Randomized Sketching Algorithms in Regression Problems. SIAM Journal on Matrix Analysis and Applications, 46(2), 1247-1279. https://doi.org/10.1137/23m1597526
Vancouver
Cho Y, Demmel J, Dereziński M, Li H, Luo H, Mahoney M, et al. Surrogate-Based Autotuning for Randomized Sketching Algorithms in Regression Problems. SIAM Journal on Matrix Analysis and Applications. 2025;46(2):1247-1279. doi:10.1137/23m1597526
BibTeX
@article{Cho2025,
author = {Cho, Younghyun and Demmel, James and Dereziński, Michał and Li, Haoyun and Luo, Hengrui and Mahoney, Michael and Murray, Riley},
title = {Surrogate-Based Autotuning for Randomized Sketching Algorithms in Regression Problems},
journal = {SIAM Journal on Matrix Analysis and Applications},
year = {2025},
volume = {46},
number = {2},
pages = {1247--1279},
doi = {10.1137/23m1597526}
}
EUVIMED