Analysis of the Performance of Algorithm Configurators for Search Heuristics with Global Mutation Operators

• URL: http://arxiv.org/abs/2004.04519v1
• Date: Thu, 9 Apr 2020 12:42:30 GMT
• Title: Analysis of the Performance of Algorithm Configurators for Search Heuristics with Global Mutation Operators
• Authors: George T. Hall, Pietro Simone Oliveto, Dirk Sudholt
• Abstract summary: ParamRLS can efficiently identify the optimal neighbourhood size to be used by local search. We show that the simple ParamRLS-F can identify the optimal mutation rates even when using cutoff times that are considerably smaller than the expected optimisation time of the best parameter value for both problem classes.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently it has been proved that a simple algorithm configurator called ParamRLS can efficiently identify the optimal neighbourhood size to be used by stochastic local search to optimise two standard benchmark problem classes. In this paper we analyse the performance of algorithm configurators for tuning the more sophisticated global mutation operator used in standard evolutionary algorithms, which flips each of the $n$ bits independently with probability $\chi/n$ and the best value for $\chi$ has to be identified. We compare the performance of configurators when the best-found fitness values within the cutoff time $\kappa$ are used to compare configurations against the actual optimisation time for two standard benchmark problem classes, Ridge and LeadingOnes. We rigorously prove that all algorithm configurators that use optimisation time as performance metric require cutoff times that are at least as large as the expected optimisation time to identify the optimal configuration. Matters are considerably different if the fitness metric is used. To show this we prove that the simple ParamRLS-F configurator can identify the optimal mutation rates even when using cutoff times that are considerably smaller than the expected optimisation time of the best parameter value for both problem classes.

Related papers

• Optimal Hyperparameter $\epsilon$ for Adaptive Stochastic Optimizers through Gradient Histograms [0.8702432681310399]
  We introduce a new framework based on gradient histograms to analyze and justify attributes adaptives. We propose a novel gradient histogram-based algorithm that automatically estimates a reduced and accurate search space for the safeguard factor $epsilon$.
  arXiv  Detail & Related papers  (2023-11-20T04:34:19Z)
• Efficient Convex Algorithms for Universal Kernel Learning [50.877957471649395]
  An ideal set of kernels should: admit a linear parameterization (for tractability); dense in the set of all kernels (for accuracy) Previous algorithms for optimization of kernels were limited to classification and relied on computationally complex Semidefinite Programming (SDP) algorithms. We propose a SVD-QCQPQP algorithm which dramatically reduces the computational complexity as compared with previous SDP-based approaches.
  arXiv  Detail & Related papers  (2023-04-15T04:57:37Z)
• Benchmarking optimality of time series classification methods in distinguishing diffusions [1.0775419935941009]
  This study proposes to benchmark the optimality of TSC algorithms in distinguishing diffusion processes by the likelihood ratio test (LRT) The LRT benchmarks are computationally efficient because the LRT does not need training, and the diffusion processes can be efficiently simulated and are flexible to reflect the specific features of real-world applications.
  arXiv  Detail & Related papers  (2023-01-30T17:49:12Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  We present the first efficient scalable and general framework that can directly search on the tasks of interest. Inspired by the innate tree structure of the underlying math expressions, we re-arrange the spaces into a super-tree. We adopt an adaptation of the Monte Carlo method to tree search, equipped with rejection sampling and equivalent- form detection.
  arXiv  Detail & Related papers  (2022-09-27T17:51:31Z)
• Evolving Pareto-Optimal Actor-Critic Algorithms for Generalizability and Stability [67.8426046908398]
  Generalizability and stability are two key objectives for operating reinforcement learning (RL) agents in the real world. This paper presents MetaPG, an evolutionary method for automated design of actor-critic loss functions.
  arXiv  Detail & Related papers  (2022-04-08T20:46:16Z)
• Automated Configuration of Genetic Algorithms by Tuning for Anytime Performance [4.33419118449588]
  We show that it might be preferable to use anytime performance measures for the configuration task. tuning for expected running time is much more sensitive with respect to the budget that is allocated to the target algorithms.
  arXiv  Detail & Related papers  (2021-06-11T10:44:51Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Optimizing Optimizers: Regret-optimal gradient descent algorithms [9.89901717499058]
  We study the existence, uniqueness and consistency of regret-optimal algorithms. By providing first-order optimality conditions for the control problem, we show that regret-optimal algorithms must satisfy a specific structure in their dynamics. We present fast numerical methods for approximating them, generating optimization algorithms which directly optimize their long-term regret.
  arXiv  Detail & Related papers  (2020-12-31T19:13:53Z)
• 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)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Stochastic batch size for adaptive regularization in deep network optimization [63.68104397173262]
  We propose a first-order optimization algorithm incorporating adaptive regularization applicable to machine learning problems in deep learning framework. We empirically demonstrate the effectiveness of our algorithm using an image classification task based on conventional network models applied to commonly used benchmark datasets.
  arXiv  Detail & Related papers  (2020-04-14T07:54:53Z)

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.