Black-Box Complexity of the Binary Value Function
The binary value function, or BinVal, has appeared in several studies in theory of evolutionary computation as one of the extreme examples of linear pseudo-Boolean functions. Its unbiased black-box complexity was previously shown to be at most $\lceil \log_2 n \rceil + 2$, where $n$ is the problem size. We augment it with an upper bound of $\log_2 n + 2.42141558 - o(1)$, which is more precise for many values of $n$. We also present a lower bound of $\log_2 n + 1.1186406 - o(1)$. Additionally, we prove that BinVal is an easiest function among all unimodal pseudo-Boolean functions at least for unbiased algorithms.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Continuous black-box optimization with quantum annealing and random subspace coding
A black-box optimization algorithm such as Bayesian optimization finds extremum of an unknown function by alternating inference of the underlying function and optimization of an acquisition function. In a high-dimensiona…
Bayesian OptimizationImproved Generalization Bounds for Adversarially Robust Learning
We consider a model of robust learning in an adversarial environment. The learner gets uncorrupted training data with access to possible corruptions that may be affected by the adversary during testing. The learner's goa…
Binary ClassificationGeneral ClassificationGeneralization BoundsMulti-class Classification+1The Geometry of Generalized Binary Search
This paper investigates the problem of determining a binary-valued function through a sequence of strategically selected queries. The focus is an algorithm called Generalized Binary Search (GBS). GBS is a well-known gree…
On the Complexity of Value Iteration
Value iteration is a fundamental algorithm for solving Markov Decision Processes (MDPs). It computes the maximal $n$-step payoff by iterating $n$ times a recurrence equation which is naturally associated to the MDP. At t…
Unbiased Black-Box Complexities of Jump Functions
We analyze the unbiased black-box complexity of jump functions with small, medium, and large sizes of the fitness plateau surrounding the optimal solution. Among other results, we show that when the jump size is $(1/2 …