Surrogate-based Autotuning for Randomized Sketching Algorithms in
  Regression Problems
Younghyun Cho James W. Demmel Michał Dereziński Haoyun Li Hengrui Luo Michael W. Mahoney Riley J. Murray
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.