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.


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.


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.

  • 1
    $\begingroup$ Is it possible to articulate a concise definition of what the term oracle generally means in this sort of context? $\endgroup$
    – Ryan Volpi
    Jun 22 '20 at 20:06
  • 2
    $\begingroup$ oracle is just a function that let you perform queries, they typically promise certain property such as in your context, they ensure that a solution that is not too bad. usually, such papers do not promise that they know how to construct such oracles, but they tell you if you have such a function, what can we conclude. $\endgroup$ Jun 23 '20 at 1:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.