Solving Stochastic Root-Finding with adaptive d-ary search

Abstract

The most fundamental problem encountered in the field of stochastic optimization, is the Stochastic Root Finding (SRF) problem where the task is to locate an unknown point x

for which g ( x

)=0 for a given function g that can only be observed in the presence of noise [13]. The vast majority of the state-of-the-art solutions to the SRF problem involve the theory of stochastic approximation. The premise of the latter family of algorithms is to operate by means of so-called “small- step” processes that explore the search space in a conservative manner. Using this paradigm, the point investigated at any time instant is in the proximity of the point investigated at the previous time instant, rendering the convergence towards the optimal point, x

, to be sluggish. The unfortunate thing about such a search paradigm is that although g () contains information using which large sections of the search space can be eliminated, this information is unutilized. This paper provides a pioneering and novel scheme to discover and utilize this information. Our solution recursively shrinks the search space by, at least, a factor of 2 d 3 at each epoch, where d

2 is a user-defined parameter of the algorithm. This enhances the convergence significantly. Conceptually, this is achieved through a subtle re-formulation of SRF problem in terms of a continuous-space generalization of the Stochastic Point Location (SPL) problem originally proposed by Oommen in [8]. Our scheme is based, in part, on the Continuous Point Location with Adaptive d -ary Search (CPL–A d S), originally presented in [12]. The solution to the CPL–A d S [12], however, is not applicable in our particular domain because of the inherent asymmetry of the SRF problem. Our solution invokes a CPL– A d S-like solution to partition the search interval into d sub- intervals, evaluates the location of the unknown root x

with respect to these sub-intervals using learning automata, and prunes the search space in each iteration by eliminating at least one partition. Our scheme, the CPL–A d S algorithm for SRF, denoted as SRF–A d S, is shown to converge to the unknown root x

with an arbitrary large degree of accuracy, i.e., with a probability as close to unity as desired. Unlike the classical formulation of the SPL problem proposed by Oommen etal [8], [12], in our setting, the probability, p , of the “environment” suggesting an accurate response is non-constant. In fact, the latter probability depends of the point x being examined and the region that is a candidate to be pruned. The fact that p is not constant renders the analysis much more involved than in [12]. The decision rules for pruning are also different from those encountered when p is constant [12].