Surrogate-based Autotuning for Randomized Sketching Algorithms in Regression Problems

Younghyun Cho, James Weldon Demmel, Michal Derezinski, Haoyun Li, Hengrui Luo, Michael W. Mahoney, Riley J. Murray

TL;DR

This paper introduces a novel autotuning framework for Randomized Numerical Linear Algebra (RandNLA) algorithms, specifically focusing on sketch-and-precondition (SAP) methods for least squares problems. By employing Bayesian optimization and transfer learning, their approach significantly reduces the computational cost of finding near-optimal algorithm parameters, achieving performance comparable to expensive grid searches with far fewer evaluations.

What Problem Does This Paper Address?

Randomized Numerical Linear Algebra (RandNLA) algorithms offer powerful tools for tackling large-scale computational problems, often outperforming traditional methods. However, their practical application is hindered by a multitude of algorithm-specific tuning parameters that significantly impact performance. Unlike traditional methods where parameters are often well-understood, RandNLA parameters can be complex and their optimal settings highly dependent on the specific problem instance. Manually tuning these parameters is time-consuming and often leads to suboptimal results. Existing recommendations are often overly conservative, and exhaustive grid searches are computationally prohibitive. This paper addresses the critical need for an efficient and effective method to automatically tune RandNLA algorithms, making them more accessible and performant for a wider range of users and problems.

Methods

The core of this work is a surrogate-based autotuning framework built upon Bayesian optimization. This framework treats the RandNLA algorithm as a black-box function, where performance (e.g., wall-clock time and accuracy) is measured for different parameter configurations. A Gaussian Process (GP) regression model is used to build a surrogate model of this performance landscape, allowing the tuner to intelligently select the next parameter configurations to evaluate, minimizing the number of expensive function evaluations.

A key innovation is the incorporation of transfer learning. Recognizing that optimal parameters vary across problem instances, the framework leverages previously collected tuning data from similar problems ("source tasks") to accelerate tuning on new problems ("target tasks"). This is achieved by combining GP models from source and target tasks, effectively providing a "warm start" for the optimization process.

The authors also introduce a tuning opportunity trichotomy for SAP-based least squares:

  • TO1: Sketching Matrix Construction: How to create the sketching matrix (e.g., SJLT, LessUniform).
  • TO2: Preconditioner Generation: How to derive a preconditioner from the sketched matrix.
  • TO3: Iterative Method Selection: Which iterative solver to use for the preconditioned problem.

Their framework tunes these parameters, along with others like sampling factor and non-zero counts, to optimize a combined objective function of wall-clock time and residual error.

Datasets

The paper uses a combination of synthetic and real-world datasets for evaluation:

  • Synthetic Datasets: Generated matrices with varying properties (e.g., coherence) based on multivariate normal and t-distributions. These include matrices labeled GA, T5, T3, and T1.
  • Real-World Datasets:
    • Musk: A dataset for classification (m=6,598, n=166).
  • CIFAR-10: An image classification dataset, adapted for regression (m=32,768, n=512).
  • Localization: A regression dataset for CT image location (m=53,500, n=385).

The authors also mention using a smaller matrix B (m=10,000, n=1,000) for pre-collecting transfer learning data.

Key Insights and Ideas

  • RandNLA parameter tuning is crucial and complex: The performance of RandNLA algorithms is highly sensitive to parameter choices, and "safe" default settings can lead to orders of magnitude worse performance than optimally tuned configurations.
  • Bayesian optimization is well-suited for RandNLA tuning: Its ability to model uncertain and noisy performance landscapes makes it effective for optimizing expensive, stochastic black-box functions.
  • Transfer learning dramatically boosts efficiency: Leveraging prior tuning data significantly reduces the number of function evaluations needed to achieve near-optimal performance, especially for smaller or similar problems.
  • "LessUniform" sketching operators often outperform "SJLT" for SAP: This is attributed to their inherent sparsity and better cache efficiency in typical implementations.
  • QR-LSQR is generally faster and more robust than SVD-based methods: Especially for high-coherence matrices, QR-LSQR shows fewer ARFE failures.
  • Sensitivity analysis reveals key parameters: SAP_alg and sampling_factor are identified as the most influential parameters, guiding efforts for more efficient tuning.

Key Results

  • The proposed autotuning approach (GPTune and TLA) achieves near-optimal performance with significantly fewer function evaluations compared to random search (LHSMDU) and even Tree-structured Parzen Estimator (TPE).
  • Specifically, for the T1 matrix, TLA achieved near-optimal performance with 7.6x fewer evaluations than random search.
  • The framework can achieve performance comparable to expensive grid searches but with a drastically reduced computational budget. For example, on the GA matrix, GPTune achieved optimal performance with 1.63x fewer evaluations than LHSMDU.
  • The autotuning pipeline demonstrated effectiveness across both synthetic and real-world datasets, showcasing its generality.
  • Sensitivity analysis confirmed that parameters like SAP_alg and sampling_factor are highly sensitive, justifying their inclusion in the autotuning process.

Limitations and Future Work

  • Failure Handling: The current scheme for handling low-accuracy samples (high ARFE) is simple and can be less effective in transfer learning, especially for strongly constrained settings with many failures. More sophisticated error handling methods are needed.
  • Tuning Space: The authors suggest exploring larger and higher-dimensional tuning spaces, including more sketching operators and preconditioner options, to enhance usability.
  • Sensitivity Analysis for Parameter Reduction: Developing more sophisticated sensitivity analysis techniques could further reduce the tuning space effectively.
  • Practical Use Case: Investigating the practical application of tuning on smaller, down-sampled data matrices and then applying those parameters to solve larger problems is a promising future direction.
  • Computational Overhead: The paper acknowledges that the computational overhead of the surrogate modeling and search itself is not considered, as the focus is on reducing function evaluation costs. For very small problems, this overhead might be significant.

Summary updated

Abstract

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.
BibTeX
@article{cho2023surrogate,
  author = {Younghyun Cho and James Weldon Demmel and Michal Derezinski and Haoyun Li and Hengrui Luo and Michael W. Mahoney and Riley J. Murray},
  title = {{Surrogate-based Autotuning for Randomized Sketching Algorithms in Regression Problems}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2023},
  doi = {10.1137/23m1597526},
}
Figure