## Author(s)

## Publication date

2017-07

## Series/Report no

Information Sciences;Volume 393

## Publisher

Elsevier

## Document type

## Abstract

The most fundamental problem encountered in the ﬁeld 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 [15]. 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 oper
ate by means of so-called “small-step”processesthat explorethe 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, renderingthe 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 2d 3 at each epoch, where d ≥ 2 is a user-deﬁned parameter of the algorithm. This enhances the convergence signiﬁcantly.
Conceptually, this is achieved through a subtle re-formulationof SRF problem in terms of a continuous-space gen
eralization of the Stochastic Point Location (SPL) problem originally proposed by Oommen in [9]. Our scheme
is based, in part, on the Continuous Point Location with Adaptive d-ary Search (CPL–AdS), originally presented
in [13]. The solution to the CPL–AdS [13], however, is not applicable in our particular domain because of the inher
ent asymmetry of the SRF problem. Our solution invokes a CPL–AdS-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 learn
ing automata, and prunes the search space in each iteration by eliminating at least one partition. Our scheme, the CPL–AdS algorithm for SRF, denoted as SRF–AdS, 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 et al [9,13], 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 [13]. The decision rules for pruning are also different from those encountered when p is constant [13].

## Version

acceptedVersion

## Permanent URL (for citation purposes)

- https://hdl.handle.net/10642/5991