Surrogate-based Autotuning for Randomized Sketching Algorithms in Regression Problems

• URL: http://arxiv.org/abs/2308.15720v1
• Date: Wed, 30 Aug 2023 02:50:54 GMT
• Title: Surrogate-based Autotuning for Randomized Sketching Algorithms in Regression Problems
• Authors: Younghyun Cho, James W. Demmel, Micha{\l} Derezi\'nski, Haoyun Li, Hengrui Luo, Michael W. Mahoney, Riley J. Murray
• Abstract summary: We show how a surrogate-based autotuning approach can be used to address fundamental problems of parameter selection in RandNLA algorithms. Our results show that our surrogate-based autotuning approach can achieve near-optimal performance with much less tuning cost than a random search.
• Score: 44.54726768134471
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
  This paper reveals a unified game-theoretic connection between iterative BOND and self-play alignment. We establish a novel framework, WIN rate Dominance (WIND), with a series of efficient algorithms for regularized win rate dominance optimization.
  arXiv  Detail & Related papers  (2024-10-28T04:47:39Z)
• On the Effectiveness of Parameter-Efficient Fine-Tuning [79.6302606855302]
  Currently, many research works propose to only fine-tune a small portion of the parameters while keeping most of the parameters shared across different tasks. We show that all of the methods are actually sparse fine-tuned models and conduct a novel theoretical analysis of them. Despite the effectiveness of sparsity grounded by our theory, it still remains an open problem of how to choose the tunable parameters.
  arXiv  Detail & Related papers  (2022-11-28T17:41:48Z)
• Fast Feature Selection with Fairness Constraints [49.142308856826396]
  We study the fundamental problem of selecting optimal features for model construction. This problem is computationally challenging on large datasets, even with the use of greedy algorithm variants. We extend the adaptive query model, recently proposed for the greedy forward selection for submodular functions, to the faster paradigm of Orthogonal Matching Pursuit for non-submodular functions. The proposed algorithm achieves exponentially fast parallel run time in the adaptive query model, scaling much better than prior work.
  arXiv  Detail & Related papers  (2022-02-28T12:26:47Z)
• TFPnP: Tuning-free Plug-and-Play Proximal Algorithm with Applications to Inverse Imaging Problems [22.239477171296056]
  Plug-and-Play (MM) is a non- optimization framework that combines numerical algorithms, for example, with advanced denoising priors. We discuss several practical considerations of more denoisers, which together with our learned strategies are state-of-the-art results.
  arXiv  Detail & Related papers  (2020-11-18T14:19:30Z)
• Data-driven Algorithm Design [21.39493074700162]
  Data driven algorithm design is an important aspect of modern data science and algorithm design. A small tweak to the parameters can cause a cascade of changes in the algorithm's behavior. We provide strong computational and statistical performance guarantees for batch and online scenarios.
  arXiv  Detail & Related papers  (2020-11-14T00:51:57Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Fast Perturbative Algorithm Configurators [0.0]
  We prove a linear lower bound on the expected time to optimise any parameter problem for ParamRLS and ParamILS. We propose a harmonic mutation operator for perturbative algorithms in polylogarithmic time for unimodal and approximately unimodal. An experimental analysis confirms the superiority of the approach in practice for a number of configuration scenarios.
  arXiv  Detail & Related papers  (2020-07-07T10:48:32Z)
• Determinantal Point Processes in Randomized Numerical Linear Algebra [80.27102478796613]
  Numerical Linear Algebra (RandNLA) uses randomness to develop improved algorithms for matrix problems that arise in scientific computing, data science, machine learning, etc. Recent work has uncovered deep and fruitful connections between DPPs and RandNLA which lead to new guarantees and improved algorithms.
  arXiv  Detail & Related papers  (2020-05-07T00:39:52Z)
• MATE: A Model-based Algorithm Tuning Engine [2.4693304175649304]
  We introduce a Model-based Algorithm Turning Engine, namely MATE, where the parameters of an algorithm are represented as expressions of the features of a target optimisation problem. We formulate the problem of finding the relationships between the parameters and the problem features as a symbolic regression problem and we use genetic programming to extract these expressions. For the evaluation, we apply our approach to configuration of the (1+1) EA and RLS algorithms for the OneMax, LeadingOnes, BinValue and Jump optimisation problems.
  arXiv  Detail & Related papers  (2020-04-27T12:50:48Z)
• Online Hyperparameter Search Interleaved with Proximal Parameter Updates [9.543667840503739]
  We develop a method that relies on the structure of proximal gradient methods and does not require a smooth cost function. Such a method is applied to Leave-one-out (LOO)-validated Lasso and Group Lasso. Numerical experiments corroborate the convergence of the proposed method to a local optimum of the LOO validation error curve.
  arXiv  Detail & Related papers  (2020-04-06T15:54:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.