 Stochastic optimization

Stochastic optimization treats optimization involving uncertain quantities or algorithms driven by random observations. A basic model is ${\min }_{x}F(x)$ with $F(x)=\mathbb{E}[f(x,\xi )]$, where the decision $x$ must be chosen before the relevant realization of $\xi$ is known.

For $f(x,\xi )=\frac{1}{2}(x-\xi {)}^2$ and finite second moment, the minimizer is $x_{\ast }=\mathbb{E}\xi$. A fresh independent observation supplies $g(x,\xi )=x-\xi$, an unbiased estimate of the gradient $F^{\prime }(x)$. A stochastic gradient descent step uses that noisy information rather than evaluating the entire expectation. Averaging or suitable decreasing step sizes can control the accumulated noise; replacing an expectation with one random observation does not make its minimizer the population optimum.