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.

该论文展示了如何使用基于代理模型的自动调整方法来解决 RandNLA 算法中参数选择的基本问题，并详细研究了基于代理模型的自动调整方法在基于随机预处理的最小二乘法中的应用。实验结果表明，我们的基于代理模型的自动调整方法可以以较少的调整成本实现接近最优的性能，同时适用于任何类型的 RandNLA 算法。