A Newton-Raphson Version of the Multivariate Robbins-Monro Procedure

Suppose that f is a function from Rᵏ to Rᵏ and for some θ, f(θ) = 0. Initially f is unknown, but for any x in Rᵏ we can observe a random vector $Y(x)$ with expectation $f(x)$. The unknown θ can be estimated recursively by Blum's (1954) multivariate version of the Robbins-Monro procedure. Blum's procedure requires the rather restrictive assumption that infimum of the inner product (x - θ)ᵗf(x) over any compact set not containing θ be positive. Thus at each $x, f(x)$ gives information about the direction towards θ. Blum's recursion is Xₙ₊₁ = Xₙ - aₙ Yₙ where the conditional expectation of Yₙ given X₁, ⋯, Xₙ is f(Xₙ) and aₙ > 0. Unlike Blum's method, the procedure introduced in this paper does not necessarily attempt to move in a direction that decreases \|Xₙ - θ\|, at least not during the initial stage of the procedure. Rather, except for random fluctuations it moves in a direction which decreases \|f\|², and it may follow a circuitous route to θ. Consequently, it does not require that (x - θ)ᵗf(x) have a constant signum. This new procedure is somewhat similar to the multivariate Kiefer-Wolfowitz procedure applied to \|f\|², but unlike the latter it converges to θ at rate n-1/2. Deterministic root finding methods are briefly discussed. The method of this paper is a stochastic analog of the Newton-Raphson and Gauss-Newton techniques.