In mathematical optimization, oracle complexity is a standard theoretical framework to study the computational requirements for solving classes of optimization problems. It is suitable for analyzing iterative algorithms which proceed by computing local information about the objective function at various points (such as the function's value, gradient, Hessian etc.). The framework has been used to provide tight worst-case guarantees on the number of required iterations, for several important classes of optimization problems.
Formal description Consider the problem of minimizing some objective function f : X → R {\displaystyle f:{\mathcal {X}}\rightarrow \mathbb {R} } (over some domain X {\displaystyle {\mathcal {X}}} ), where f {\displaystyle f} is known to belong to some family of functions F {\displaystyle {\mathcal {F}}} . Rather than direct access to f {\displaystyle {\mathcal {f}}} , it is assumed that the algorithm can obtain information about f {\displaystyle f} via an oracle O {\displaystyle {\mathcal {O}}} , which given a point x {\displaystyle \mathbf {x} } in X {\displaystyle {\mathcal {X}}} , returns some local information about f {\displaystyle f} in the neighborhood of x {\displaystyle \mathbf {x} } . The algorithm begins at some initialization point x 1 {\displaystyle \mathbf {x} _{1}} , uses the information provided by the oracle to choose the next point x 2 {\displaystyle \mathbf {x} _{2}} , uses the additional information to choose the following point x 3 {\displaystyle \mathbf {x} _{3}} , and so on. To give a concrete example, suppose that X = R d {\displaystyle {\mathcal {X}}=\mathbb {R} ^{d}} (the d {\displaystyle d} -dimensional Euclidean space), and consider the gradient descent algorithm, which initializes at some point x 1 {\displaystyle \mathbf {x} _{1}} and proceeds via the recursive equation
… excerpt ends here. Continue reading the full article.
