Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2308.15720 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910779100364800 |
|---|---|
| author | Cho, Younghyun Demmel, James W. Dereziński, Michał Li, Haoyun Luo, Hengrui Mahoney, Michael W. Murray, Riley J. |
| author_facet | Cho, Younghyun Demmel, James W. Dereziński, Michał Li, Haoyun Luo, Hengrui Mahoney, Michael W. Murray, Riley J. |
| contents | 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 than 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 4x 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_15720 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Surrogate-based Autotuning for Randomized Sketching Algorithms in Regression Problems Cho, Younghyun Demmel, James W. Dereziński, Michał Li, Haoyun Luo, Hengrui Mahoney, Michael W. Murray, Riley J. Machine Learning Artificial Intelligence 68W20, 65F20, 65Y20 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 than 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 4x 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. |
| title | Surrogate-based Autotuning for Randomized Sketching Algorithms in Regression Problems |
| topic | Machine Learning Artificial Intelligence 68W20, 65F20, 65Y20 |
| url | https://arxiv.org/abs/2308.15720 |