black-box optimization

Motivation

There are many problems backpropagation cannot be used for or has limitaitons, e.g. in RL the credit assignment problem makes gradient estimates difficult: rewards are often delayed, sparse, or noisy, and policies can get trapped in local optima.
In such settings, black-box optimization methods like genetic algorithms or evolution strategies provide a gradient-free alternative.

See also: Evolution Strategies as a Scalable Alternative to Reinforcement Learning

Link to original

Black-box optimization

You want to minimize an objective, but you don’t know its internal form.
You can only query a box: give it an input $x$ and it returns an output (e.g., a fitness/loss/…). The box may be expensive or noisy.

Problem. Minimize $f(x)$ over $x\in \mathcal{X}\subseteq {\mathbb{R}}^d$. The functions $f$ is unknown to the algorithm.
Oracle. On a query $x$, an oracle $\mathcal{O}$ returns a random output $Z_x\sim P_x$.
Typical cases include:
Value-only $\mathbb{E}[Z_x]=f(x)$,
Value+gradient $Z_x=(f(x),\nabla f(x))$, possibly noisy.

Algorithm. Choose $x_{t+1}$ adaptively from past data $\{(x_s,Z_{x_s}){\}}_{s=1}^t$, then output ${\hat{x}}_T$.

A common goal/criterion is: Find ${\hat{x}}_T$ with suboptimality $f({\hat{x}}_T)-f(x^{\star })\le \epsilon$ (where $x^{\star }=\arg \min f$) using as few oracle calls $T$ as possible (sample efficiency).

Is black-box optimization the same as zero order optimization

BBO is a modeling assumption about access to information, not a specific algorithm family.
The box might return just values, or values and gradients, but you can’t exploit an explicit formula.
BBO is about what you know (only queries), gradient-free optimization describes what you use.

Variants of black-box optimization

• stochastic optimization
  • random search
  • simulated annealing
  • evolutionary optimization
    • distribution-based
      • evolution strategies
      • …
    • population-based
      • genetic algorithm
      • particle swarm optimization
      • diffusion evolution
      • differential evolution
      • …
  • …
    • bayesian optimization
    • grid search
    • …