Stochastic Approximation

Stochastic approximation methods are a family of iterative stochastic optimization algorithms that attempt to find zeroes or extrema of functions which cannot be computed directly, but only estimated via noisy observations.

Mathematically, this refers to solving:

where the objective is to find the parameter, which minimizes for some unknown random variable, . Denoting as the dimension of the parameter, we can assume that while the domain is known, the objective function, cannot be computed exactly, but instead approximated via simulation. This can be intuitively explained as follows. is the original function we want to minimize. However, due to noise, can not be evaluated exactly. This situation is modeled by the function, where represents the noise and is a random variable. Since is a random variable, so is the value of . The objective is then to minimize, but through evaluating . A reasonable way to do this is to minimize the expectancy of, i.e., .

The first, and prototypical, algorithms of this kind are the Robbins-Monro and Kiefer-Wolfowitz algorithms.