How to calculate gradient in gradient descent?

Question

I am trying to optimize a function $f(x)$ of a vector of reals $x=<x_1, x_2, ...x_n>$. In my practical application, I have no expression for $f$ whatsoever, all I can do is given a vector $x$, calculate $f(x)$ via a deterministic experiment.

How do I go about calculating the gradient? What specific type of gradient descent would you suggest? Or do you suggest an alternative approach?

I was thinking, maybe try each $x_i$, shifting it up or down, see which way $f$ increases, and move in that direction. In other words, change only single $x_i$ at a time. Does this method have a name? Or is it flawed, and there is a better alternative? How do I approach this problem?

Answer 1

As you suggested, it's possible to approximate the gradient by repeatedly evaluating the objective function after perturbing the input by a small amount along each dimension (assuming it's differentiable). This is called numerical differentiation, or finite difference approximation. It's possible to use this for gradient-based optimization methods like vanilla gradient descent, BFGS, conjugate gradient method, etc. You can probably get away with it for small scale problems. But, it's not very efficient because the number of function evaluations needed to approximate the gradient scales with the number of variables. If your optimization problem has many variables, you'd probably be better off using a derivative-free optimization method. This class of methods doesn't require the gradient, and can be used in cases where the gradient is unavailable, or the objective function is non-differentiable. Derivative-free methods are typically less efficient than gradient based methods if an expression for the gradient is available. But, they can be more efficient than computing the gradient numerically.