  We propose a simple drop-in noise-tolerant replacement for the standard
finite difference procedure used ubiquitously in blackbox optimization. In our
approach, parameter perturbation directions are defined by a family of
structured orthogonal matrices. We show that at the small cost of computing a
Fast Walsh-Hadamard/Fourier Transform (FWHT/FFT), such structured finite
differences consistently give higher quality approximation of gradients and
Jacobians in comparison to vanilla approaches that use coordinate directions or
random Gaussian perturbations. We find that trajectory optimizers like
Iterative LQR and Differential Dynamic Programming require fewer iterations to
solve several classic continuous control tasks when our methods are used to
linearize noisy, blackbox dynamics instead of standard finite differences. By
embedding structured exploration in a quasi-Newton optimizer (LBFGS), we are
able to learn agile walking and turning policies for quadruped locomotion, that
successfully transfer from simulation to actual hardware.We theoretically
justify our methods via bounds on the quality of gradient reconstruction and
provide a basis for applying them also to nonsmooth problems.
