A Dynamic Stochastic Approximation Method

Abstract

This investigation has been inspired by a paper of V. Fabian [3], where inter alia the applicability of stochastic approximation methods for progressive improvement of production processes is discussed; his non-formal discussion includes the case where the optimum of the production process moves during the optimization process. In the present paper, the last case is treated in a formal way. A modified approximation scheme is suggested, which turns out to be an adequate tool, when the position of the optimum is a linear (or nearly linear) function of time. The domain of effectiveness of the unmodified approximation scheme is also investigated. In this context, the incorrectness of a theorem of T. Kitagawa is pointed out. The considerations are performed for the Robbins-Monro case in detail; they can all be repeated for the Kiefer-Wolfowitz case and for the multidimensional case, as indicated in Section 4. Among the properties of the method, only the mean convergence and the order of magnitude of $E\lbrack (x_n - \theta_n)^2\rbrack$ are investigated; (here $x_n$ denotes the estimated and $\theta_n$ the true position of the optimum at time $n$.) A lemma, due to K. L. Chung [1] is used repeatedly: LEMMA. Let $b_n, n = 1, 2, \cdots$, be real numbers such that for $n \geqq n_0$, \begin{equation*}\tag{1}b_{n + 1} \leqq (1 - c/n^s)b_n + c'/n^t,\end{equation*} where $0 < s < 1, c > 0, c' > 0, t$ real. Then \begin{equation*}\tag{2}\lim \sup_{n \rightarrow \infty} n^{t - s}b_n \leqq c'/c.\end{equation*} The lemma remains true, if the inequalities (1) and (2) are reversed and, simultaneously, $\lim \sup_{n \rightarrow \infty}$ is changed into $\lim \inf_{n \rightarrow \infty}$. (In Chung's paper, a further assumption $t > s$ is made, but it is easily seen, that both versions of the lemma hold true also when $t \leqq s$; this fact is used in Section 3.) Throughout the paper, $K_0, K_1, K_2, \cdots$ denote positive constants, numbered in order of appearance.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 88 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.