= Stochastic optimization
{wiki}
<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)=\tfrac12(x-\xi)^2$ and finite second moment, the minimizer is $x_* =\mathbb E\xi$. A fresh <independent> observation supplies $g(x,\xi)=x-\xi$, an unbiased estimate of the <gradient> $F'(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.
Back to article page
