Monte Carlo gradient estimation in high dimensions

A Monte Carlo procedure to estimate efficiently the gradient of a generic function in high dimensions is presented. It is shown that, adopting an orthogonal linear transformation, it is possible to identify a new coordinate system where a relatively small subset of the variables causes most of the variation of the gradient. This property is exploited further in gradient‐based algorithms to reduce the computational effort for the gradient evaluation in higher dimensions. Working in this transformed space, only few function evaluations, i.e. considerably less than the dimensionality of the problem, are required. The procedure is simple and can be applied by any gradient‐based method. A number of different examples are presented to show the accuracy and the efficiency of the proposed approach and the applicability of this procedure for the optimization problem using well‐known gradient‐based optimization algorithms such as the descent gradient, quasi‐Newton methods and Sequential Quadratic Programming. Copyright © 2009 John Wiley & Sons, Ltd.