  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.
