Can I minimize a mysterious function by running a gradient descent on her neural net approximations?

Question

So I have this function let call her $F:[0,1]^n \rightarrow \mathbb{R}$ and say $10 \le n \le 100$. I want to find some $x_0 \in [0,1]^n$ such that $F(x_0)$ is as small as possible. I don't think there is any hope of getting the global minimum. I just want a reasonably good $x_0$.

AFAIK the standard approach is to run an (accelerated) gradient descent a bunch of times and take the best result. But in my case values of $F$ are computed algorithmically and I don't have a way to compute gradients for $F$.

So I want to do something like this.

(A) We create a neural network which takes an $n$-dimensional vector as input and returns a real number as result. We want the NN to "predict" values of $F$ but at this point it is untrained.

(B) We take bunch of random points in $[0,1]^n$. We compute values of $F$ at those points. And we train NN using this data.

(C1) Now the neural net provides us with a reasonably smooth function $F_1:[0,1]^n \rightarrow \mathbb{R}$ approximating $F$. We run a gradient decent a bunch of times on $F_1$. We take the final points of those decent and compute $F$ on them to see if we caught any small values. Then we take whole paths of those gradient decent, compute $F$ on them and use this as data to retrain our neural net.

(C2) The retrained neural net provides us with a new function $F_2$ and we repeat the previous step

(C3) ...

Does this approach have a name? Is it used somewhere? Should I indeed use neural nets or there are better ways of constructing smooth approximations for my needs?

Answer 1

I do not know any specific name for this method, but it is a common approach for approximating and optimizing complex functions. You can find an industrial use-case of this approach in this paper (NeuroErgo: A Deep Neural Network Method to Improve Postural Optimization for Ergonomic Human-Robot Collaboration).

Answer 2

Yes, this is a standard approach. An improvement is to do gradient descent on $F$ (not $F_1$), but use the gradient of $F_1$ as your estimate for the gradient of $F$. In other words, when you calculate the function in the forward direction, you use $F$, but when you backprop to get the gradient, you backprop through $F_1$.

Since the number of dimensions is so low in your case, an alternative is to use a gradient-free black-box optimization method. One approach is to use a zeroth-order optimization methods, where you use the method of finite differences to estimate the gradient at a particular point. You can estimate the gradient of $F$ at a point $x$ by evaluating $F$ at $n+1$ points, namely $F(x)$ and $F(x+\epsilon \cdot e_i)$ where $e_i$ is a vector of all-zeros except it has a 1 in the $i$th coordinate. This will be pretty efficient since in your setting, $n$ is small. An improvement of that method is to use NES, where we estimate the gradient of $F$ as follows:

$$\nabla F(x) \approx {1 \over m} \sum_{i=1}^m F(z_i) \nabla \log p(z_i)$$

where each $z_i$ is sampled iid from the normal distribution $\mathcal{N}(x,\sigma^2)$ and $p$ is the pdf of $\mathcal{N}(x,\sigma^2)$. There are many other candidate methods as well.