  Stochastic optimization (SO) considers the problem of optimizing an objective
function in the presence of noise. Most of the solution techniques in SO
estimate gradients from the noise corrupted observations of the objective and
adjust parameters of the objective along the direction of the estimated
gradients to obtain locally optimal solutions. Two prominent algorithms in SO
namely Random Direction Kiefer-Wolfowitz (RDKW) and Simultaneous Perturbation
Stochastic Approximation (SPSA) obtain noisy gradient estimate by randomly
perturbing all the parameters simultaneously. This forces the search direction
to be random in these algorithms and causes them to suffer additional noise on
top of the noise incurred from the samples of the objective. Owing to this
additional noise, the idea of using deterministic perturbations instead of
random perturbations for gradient estimation has also been studied. Two
specific constructions of the deterministic perturbation sequence using
lexicographical ordering and Hadamard matrices have been explored and
encouraging results have been reported in the literature. In this paper, we
characterize the class of deterministic perturbation sequences that can be
utilized in the RDKW algorithm. This class expands the set of known
deterministic perturbation sequences available in the literature. Using our
characterization we propose a construction of a deterministic perturbation
sequence that has the least possible cycle length among all deterministic
perturbations. Through simulations we illustrate the performance gain of the
proposed deterministic perturbation sequence in the RDKW algorithm over the
Hadamard and the random perturbation counterparts. We establish the convergence
of the RDKW algorithm for the generalized class of deterministic perturbations.
