Stochastic approximation on arvau

Wikipedia / Stochastic approximation

Stochastic approximation methods are a family of iterative methods typically used for root-finding problems or for optimization problems. The recursive update rules of stochastic approximation methods can be used, among other things, for solving linear systems when the collected data is corrupted by noise, or for approximating extreme values of functions which cannot be computed directly, but only estimated via noisy observations.

which is the expected value of a function depending on a random variable such as zeros or extrema.

Recently, stochastic approximations have found extensive applications in the fields of statistics and machine learning, especially in settings with big data. These applications range from stochastic optimization methods and algorithms, to online forms of the EM algorithm, reinforcement learning via temporal differences, and deep learning, and others. Stochastic approximation algorithms have also been used in the social sciences to describe collective dynamics: fictitious play in learning theory and consensus algorithms can be studied using their theory.

The earliest, and prototypical, algorithms of this kind are the Robbins–Monro and Kiefer–Wolfowitz algorithms introduced respectively in 1951 and 1952.

Robbins–Monro algorithm

The Robbins–Monro algorithm, introduced in 1951 by Herbert Robbins and Sutton Monro,. The structure of the algorithm is to then generate iterates of the form:

is a sequence of positive step sizes. Robbins and Monro proved, Theorem 2 converges, and Blum later proved the convergence is actually with probability one, provided that:

is uniformly bounded,
is nondecreasing,
exists and is positive, and
satisfies the following requirements:

, the above condition must be met.

Example

This is equivalent to stochastic gradient descent to exist in order to converge.

Complexity results

.
Conversely, in the general convex case, where we lack both the assumption of smoothness and strong convexity, Nemirovski and Yudin. They have also proven that this rate cannot be improved.

Subsequent developments and Polyak–Ruppert averaging

under the assumption of twice continuous differentiability and strong convexity, it can perform quite poorly upon implementation. This is primarily due to the fact that the algorithm is very sensitive to the choice of the step size sequence, and the supposed asymptotically optimal step size policy can be quite harmful in the beginning.

Chung (1954) and Fabian (1968)). Lai and Robbins has minimal asymptotic variance. However the application of such optimal methods requires much a priori information which is hard to obtain in most situations. To overcome this shortfall, Polyak (1991) and Ruppert (1988) independently developed a new optimal algorithm based on the idea of averaging the trajectories. Polyak and Juditsky decreases sufficiently slowly. That is

A1)

yet with a more robust step size policy. Prior to this, the idea of using longer steps and averaging the iterates had already been proposed by Nemirovski and Yudin.

A more general result is given in Chapter 11 of Kushner and Yin as

With assumption A1) and the following A2)

A2) is a standard Wiener process.

satisfied, and define . Then for each ,

The success of the averaging idea is because of the time scale separation of the original sequence and the averaged sequence , with the time scale of the former one being faster.

Application in stochastic optimization

is simulated from a conditional distribution defined by

is viewed as some "fundamental" underlying random process that is generated independently but not exactly equal to it.

, stochastic approximation can be applied to define a recursive solution for the minimum, analogous to the Robbins–Monro algorithm:

Convergence of the algorithm

for the algorithm to converge:

almost surely.

then

; it gives the search direction of the algorithm.

Example (where the stochastic gradient method is appropriate)

Kiefer–Wolfowitz algorithm

The Kiefer–Wolfowitz algorithm was introduced in 1952 by Jacob Wolfowitz and Jack Kiefer, and was motivated by the publication of the Robbins–Monro algorithm. However, the algorithm was presented as a method which would stochastically estimate the maximum of a function.

. The structure of the algorithm follows a gradient-like method, with the iterates being generated as

is approximated akin to a central difference method specifies a sequence of positive step sizes taken along that direction.

, and later Blum almost surely, provided that:

has a unique point of maximum (minimum) and is strong concave (convex)

which is known to include the optimal solution.

satisfies the regularity conditions as follows:

must be infinite sequences of positive numbers such that

Subsequent developments and important issues

is large, the Kiefer–Wolfowitz algorithm will require substantial computational effort per iteration, leading to slow convergence.

To address this problem, Spall proposed the use of simultaneous perturbations.
In the conditions required for convergence, the ability to specify a predetermined compact set that fulfills strong convexity (or concavity) and contains the unique solution can be difficult to find. With respect to real world applications, if the domain is quite large, these assumptions can be fairly restrictive and highly unrealistic.

Further developments

An extensive theoretical literature has grown up around these algorithms, concerning conditions for convergence, rates of convergence, multivariate and other generalizations, proper choice of step size, possible noise models, and so on. These methods are also applied in control theory should not converge to zero but should be chosen so as to track the function., 2nd ed., chapter 3

C. Johan Masreliez and R. Douglas Martin were the first to apply stochastic approximation to robust estimation.

The main tool for analyzing stochastic approximations algorithms (including the Robbins–Monro and the Kiefer–Wolfowitz algorithms) is a theorem by Aryeh Dvoretzky published in 1956.