Oracle in optimization

Question

Oracle in optimization

Blade

2020年6月22日 07:11

I have encountered the word oracle in the following context:

Given an $\alpha$-approximate oracle for stochastic optimization we show how to implement an $\alpha$-approximate solution for robust optimization under a necessary extension, and illustrate its effectiveness in applications.

I saw this question, but it doesn't seem to have the same meaning. I was wondering what does oracle mean in this context.

Edits:

I found the following definition in this paper:

A $\rho$-approximate Bayesian optimization oracle is a function $\mathcal{O}_{\rho}:(\Theta \rightarrow \mathbb{R}) \rightarrow \Theta$ for which: $$ f\left(\mathcal{O}_{\rho}(f)\right) \leq \inf _{\theta^{*} \in \Theta} f\left(\theta^{*}\right)+\rho $$ for any $f: \Theta \rightarrow \mathbb{R}$ that can be written as a nonnegative linear combination of the objective and constraint functions $g_0, g_1, \dots, g_m$.

I would appreciate if someone can shed some light on it.

Topic self-study optimization

Category Data Science

Siong Thye Goh · Accepted Answer · 2020年6月22日 07:10

The definition of $\alpha$-Approximate Stochastic oracle has been given in the paper that you provide on Page $3$.

Given a distribution $D$ over $\mathcal{L}$, an $\alpha$-approximate stochastic oracle $M(D)$ computes $x^*$ such that such that $$\mathbb{E}_{L \sim D}[L(x^*)] \le \alpha \min_{x \in \mathcal{X}} \mathbb{E}_{L \sim D}[L(x)]$$

You need not know the details of $M$, but if you provide it with a distribution $D$, then it returns you an $x^*$ such that if you evaluate the expected loss it is an most $\alpha$ times the objective value of the minimum of the expected loss.

Notice that different papers use different definitions and you should find the definition in the paper itself, as you can see, the first paper uses a multiplicative definition but the second paper uses an additive definition.

Oracle in optimization

About