Estimation-of-Distribution Algorithms for Multi-Valued Decision Variables

• URL: http://arxiv.org/abs/2302.14420v2
• Date: Mon, 1 Jan 2024 10:15:27 GMT
• Title: Estimation-of-Distribution Algorithms for Multi-Valued Decision Variables
• Authors: Firas Ben Jedidia, Benjamin Doerr, Martin S. Krejca
• Abstract summary: We extend the known quantitative analysis of genetic drift to estimation-of-distribution algorithms for multi-valued variables. Our work shows that our good understanding of binary EDAs naturally extends to the multi-valued setting.
• Score: 10.165640083594573
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The majority of research on estimation-of-distribution algorithms (EDAs) concentrates on pseudo-Boolean optimization and permutation problems, leaving the domain of EDAs for problems in which the decision variables can take more than two values, but which are not permutation problems, mostly unexplored. To render this domain more accessible, we propose a natural way to extend the known univariate EDAs to this setting. Different from a naive reduction to the binary case, our approach avoids additional constraints. Since understanding genetic drift is crucial for an optimal parameter choice, we extend the known quantitative analysis of genetic drift to EDAs for multi-valued variables. Roughly speaking, when the variables take $r$ different values, the time for genetic drift to become significant is $r$ times shorter than in the binary case. Consequently, the update strength of the probabilistic model has to be chosen $r$ times lower now. To investigate how desired model updates take place in this framework, we undertake a mathematical runtime analysis on the $r$-valued \leadingones problem. We prove that with the right parameters, the multi-valued UMDA solves this problem efficiently in $O(r\ln(r)^2 n^2 \ln(n))$ function evaluations. This bound is nearly tight as our lower bound $\Omega(r\ln(r) n^2 \ln(n))$ shows. Overall, our work shows that our good understanding of binary EDAs naturally extends to the multi-valued setting, and it gives advice on how to set the main parameters of multi-values EDAs.

Related papers

• Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Generalized OneMax [2.07180164747172]
  We provide a first runtime analysis of a generalized OneMax function. We show that the r-cGA solves this r-valued OneMax problem efficiently. At the end of experiments, we state one conjecture related to the expected runtime of another variant of multi-valued OneMax function.
  arXiv  Detail & Related papers  (2024-04-17T10:40:12Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  This paper studies the problem of contextual dueling bandits, where the binary comparison of dueling arms is generated from a generalized linear model (GLM) We propose a new SupLinUCB-type algorithm that enjoys computational efficiency and a variance-aware regret bound $tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$. Our regret bound naturally aligns with the intuitive expectation in scenarios where the comparison is deterministic, the algorithm only suffers from an $tilde O(d)$ regret.
  arXiv  Detail & Related papers  (2023-10-02T08:15:52Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  We present the first computationally efficient algorithm for linear bandits with heteroscedastic noise. Our algorithm is adaptive to the unknown variance of noise and achieves an $tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regret. We also propose a variance-adaptive algorithm for linear mixture Markov decision processes (MDPs) in reinforcement learning.
  arXiv  Detail & Related papers  (2023-02-21T00:17:24Z)
• Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments [48.96971760679639]
  We study variance-dependent regret bounds for Markov decision processes (MDPs) We propose two new environment norms to characterize the fine-grained variance properties of the environment. For model-based methods, we design a variant of the MVP algorithm. In particular, this bound is simultaneously minimax optimal for both and deterministic MDPs.
  arXiv  Detail & Related papers  (2023-01-31T06:54:06Z)
• Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds [34.37963000493442]
  This paper considers the multi-armed bandit (MAB) problem and provides a new best-of-both-worlds (BOBW) algorithm that works nearly optimally in both adversarial settings.
  arXiv  Detail & Related papers  (2022-06-14T12:58:46Z)
• An Application of a Multivariate Estimation of Distribution Algorithm to Cancer Chemotherapy [59.40521061783166]
  Chemotherapy treatment for cancer is a complex optimisation problem with a large number of interacting variables and constraints. We show that the more sophisticated algorithm would yield better performance on a complex problem like this. We hypothesise that this is caused by the more sophisticated algorithm being impeded by the large number of interactions in the problem.
  arXiv  Detail & Related papers  (2022-05-17T15:28:46Z)
• Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environments [55.24895403089543]
  Domain generalization aims at performing well on unseen test environments with data from a limited number of training environments. We present a new algorithm based on performing iterative feature matching that is guaranteed with high probability to yield a predictor that generalizes after seeing only $O(logd_s)$ environments.
  arXiv  Detail & Related papers  (2021-06-18T04:39:19Z)
• Distributionally Robust Optimization with Markovian Data [8.126833795693699]
  We study a program where the probability distribution of the uncertain problem parameters is unknown. We propose a data-driven distributionally to estimate the problem's objective function and optimal solution.
  arXiv  Detail & Related papers  (2021-06-12T10:59:02Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  We develop a new algorithm for non-critical optimization that finds an $O(epsilon)$epsilon point in the optimal product. We validate our results on a variety of large-scale deep learning benchmarks and architectures.
  arXiv  Detail & Related papers  (2021-03-04T19:01:20Z)
• Alternating Direction Method of Multipliers for Quantization [15.62692130672419]
  We study the performance of the Alternating Direction Method of Multipliers for Quantization ($texttADMM-Q$) algorithm. We develop a few variants of $texttADMM-Q$ that can handle inexact update rules. We empirically evaluate the efficacy of our proposed approaches.
  arXiv  Detail & Related papers  (2020-09-08T01:58:02Z)
• The Univariate Marginal Distribution Algorithm Copes Well With Deception and Epistasis [9.853329403413701]
  We show that the negative finding is caused by an unfortunate choice of the parameters of the UMDA. Our result shows that the UMDA can cope better with local optima than evolutionary algorithms.
  arXiv  Detail & Related papers  (2020-07-16T12:07:09Z)

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.