## Author(s)

## Publication date

2015

## Publisher

IEEE

## Document type

## 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].

## Version

publishedVersion

## Permanent URL (for citation purposes)

- http://hdl.handle.net/10642/4632