# Optimization of a noisy function with binary output

What frameworks exist to optimize the following problem:

$\theta^\ast = \operatorname*{argmin}\limits_{\theta \in \Theta} f(\theta)$

with the characteristic that $f$ is noisy and has a binary output (so it follows the Bernoulli distribution with unknown $p_\theta$):

$f(\theta) \sim Bern(p_{\theta})$.

So the optimization problem is better defined as follows:

$\theta^\ast = \operatorname*{argmin}\limits_{\theta \in \Theta} E[f\left(\theta\right)]$.

Another problem is that the domain only contains binary choices, so we could write it as $\Theta = (0,1)^k$.

Genetic algorithms could be a solution but what selection process to use? Also Racing came to my mind but are there implementations for binary $y$?

EDIT: How data about $f$ can be collected:

$f$ can be evaluated for any arbitrary $\theta \in \Theta$ and will return $0$ or $1$. As the function is not deterministic for the same $\theta$ the results will vary. Therefore multiple evaluations of $f(\theta)$ will be necessary to determine $p_\theta$.

• There's nothing that can be done without data, so please edit your post to describe how you have collected data about $f.$ – whuber Aug 22 '18 at 14:14
• @whuber I am a bit confused, because the "data collecting" procedure is part of the optimization algorithm right? It will collect data just by evaluating $f$. I can generate any initial design and I am totally free as to how to collect the data. – jakob-r Aug 23 '18 at 7:16
• Just to clear up the notation: Actually, every $f(\theta)$ is a bernoulli distributed random variable, lets say $f(\theta) \sim B(p_\theta)$ as you wrote above. Then $E[f(\theta)]$ is nothing else but $p_\theta$. So actually we are not talking about the function $\theta \mapsto f(\theta)$ but rather you want to know something about the function $\theta \mapsto p(\theta)=p_\theta$. So the question is: How can any algorithm know anything about this function if we have no information about it? So far it is just a general function $p : \{0,1\}^k \mapsto [0,1]$ and you want to minimize that. – Fabian Werner Aug 23 '18 at 8:42
• If you are truly that free to evaluate the function, then the answer is to evaluate it at every possible value of its arguments and to do so multiple times independently. This obviously is impractical, thereby highlighting the importance of explaining what it costs to evaluate $f.$ – whuber Aug 23 '18 at 12:55