We introduce deterministic perturbation schemes for the recently proposed\nrandom directions stochastic approximation (RDSA) [17], and propose new\nfirst-order and second-order algorithms. In the latter case, these are the\nfirst second-order algorithms to incorporate deterministic perturbations. We\nshow that the gradient and/or Hessian estimates in the resulting algorithms\nwith deterministic perturbations are asymptotically unbiased, so that the\nalgorithms are provably convergent. Furthermore, we derive conver…