CatCMA : Stochastic Optimization for Mixed-Category Problems
- URL: http://arxiv.org/abs/2405.09962v1
- Date: Thu, 16 May 2024 10:11:18 GMT
- Title: CatCMA : Stochastic Optimization for Mixed-Category Problems
- Authors: Ryoki Hamano, Shota Saito, Masahiro Nomura, Kento Uchida, Shinichi Shirakawa,
- Abstract summary: Black-box optimization problems often require simultaneously optimizing different types of variables, such as continuous, integer, and categorical variables.
Several Bayesian optimization methods can deal with mixed-category black-box optimization (MC-BBO), but they suffer from a lack of scalability to high-dimensional problems and internal computational cost.
This paper proposes CatCMA, a new optimization method for MC-BBO problems.
- Score: 9.13074910982872
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Black-box optimization problems often require simultaneously optimizing different types of variables, such as continuous, integer, and categorical variables. Unlike integer variables, categorical variables do not necessarily have a meaningful order, and the discretization approach of continuous variables does not work well. Although several Bayesian optimization methods can deal with mixed-category black-box optimization (MC-BBO), they suffer from a lack of scalability to high-dimensional problems and internal computational cost. This paper proposes CatCMA, a stochastic optimization method for MC-BBO problems, which employs the joint probability distribution of multivariate Gaussian and categorical distributions as the search distribution. CatCMA updates the parameters of the joint probability distribution in the natural gradient direction. CatCMA also incorporates the acceleration techniques used in the covariance matrix adaptation evolution strategy (CMA-ES) and the stochastic natural gradient method, such as step-size adaptation and learning rate adaptation. In addition, we restrict the ranges of the categorical distribution parameters by margin to prevent premature convergence and analytically derive a promising margin setting. Numerical experiments show that the performance of CatCMA is superior and more robust to problem dimensions compared to state-of-the-art Bayesian optimization algorithms.
Related papers
- (1+1)-CMA-ES with Margin for Discrete and Mixed-Integer Problems [6.181926091202142]
This paper introduces the margin correction into (1+1)-CMA-ES, an elitist version of CMA-ES.
The (1+1)-CMA-ES is often advantageous for unimodal functions and can be computationally less expensive.
The numerical simulation using benchmark functions on mixed-integer, integer, and binary domains shows that (1+1)-CMA-ES with margin outperforms the CMA-ES with margin.
arXiv Detail & Related papers (2023-05-01T14:34:55Z) - Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
We focus on optimisation programming (SP), Optimal Control (SOC) and Decision Processes (MDP)
Recent progress in solving convex multistage Markov problems is based on cutting planes approximations of the cost-to-go functions of dynamic programming equations.
Cutting plane type methods can handle multistage problems with a large number of stages, but a relatively smaller number of state (decision) variables.
arXiv Detail & Related papers (2023-03-28T01:30:40Z) - Marginal Probability-Based Integer Handling for CMA-ES Tackling
Single-and Multi-Objective Mixed-Integer Black-Box Optimization [10.42820615166362]
We study the mixed-integer black-box optimization (MI-BBO) problem where continuous and integer variables should be optimized simultaneously.
We propose a simple integer handling for the CMA-ES based on lower-bounding the marginal probabilities associated with the generation of integer variables in the MGD.
arXiv Detail & Related papers (2022-12-19T06:08:20Z) - Optimization of Annealed Importance Sampling Hyperparameters [77.34726150561087]
Annealed Importance Sampling (AIS) is a popular algorithm used to estimates the intractable marginal likelihood of deep generative models.
We present a parameteric AIS process with flexible intermediary distributions and optimize the bridging distributions to use fewer number of steps for sampling.
We assess the performance of our optimized AIS for marginal likelihood estimation of deep generative models and compare it to other estimators.
arXiv Detail & Related papers (2022-09-27T07:58:25Z) - CMA-ES with Margin: Lower-Bounding Marginal Probability for
Mixed-Integer Black-Box Optimization [5.237999056930947]
This study targets the mixed-integer black-box optimization (MI-BBO) problem where continuous and integer variables should be optimized simultaneously.
We propose a simple modification of the CMA-ES based on lower-bounding the marginal probabilities associated with the generation of integer variables in the MGD.
arXiv Detail & Related papers (2022-05-26T16:47:56Z) - Bayesian Optimisation for Mixed-Variable Inputs using Value Proposals [10.40799693791025]
optimisation problems defined over both categorical and continuous variables.
We adopt a holistic view and aim to consolidate optimisation of the categorical and continuous sub-spaces.
We show that this unified approach significantly outperforms existing mixed-variable optimisation approaches.
arXiv Detail & Related papers (2022-02-10T04:42:48Z) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
In this paper, we demonstrate the power of a widely used estimator based on moving average (SEMA) problems.
For all these-the-art results, we also present the results for all these-the-art problems.
arXiv Detail & Related papers (2021-04-30T08:50:24Z) - Adaptive Local Bayesian Optimization Over Multiple Discrete Variables [9.860437640748113]
This paper describes the approach of team KAIST OSI in a step-wise manner, which outperforms the baseline algorithms by up to +20.39%.
In a similar vein, we combine the methodology of Bayesian and multi-armed bandit,(MAB) approach to select the values with the consideration of the variable types.
Empirical evaluations demonstrate that our method outperforms the existing methods across different tasks.
arXiv Detail & Related papers (2020-12-07T07:51:23Z) - Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
The predict+optimize problem combines machine learning ofproblem coefficients with a optimization prob-lem that uses the predicted coefficients.
We show how to directlyexpress the loss of the optimization problem in terms of thepredicted coefficients as a piece-wise linear function.
We propose a novel divide and algorithm to tackle optimization problems without this restriction and predict itscoefficients using the optimization loss.
arXiv Detail & Related papers (2020-12-04T00:26:56Z) - Robust, Accurate Stochastic Optimization for Variational Inference [68.83746081733464]
We show that common optimization methods lead to poor variational approximations if the problem is moderately large.
Motivated by these findings, we develop a more robust and accurate optimization framework by viewing the underlying algorithm as producing a Markov chain.
arXiv Detail & Related papers (2020-09-01T19:12:11Z) - Implicit differentiation of Lasso-type models for hyperparameter
optimization [82.73138686390514]
We introduce an efficient implicit differentiation algorithm, without matrix inversion, tailored for Lasso-type problems.
Our approach scales to high-dimensional data by leveraging the sparsity of the solutions.
arXiv Detail & Related papers (2020-02-20T18:43:42Z)
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.