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

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?

• – D.W.
Sep 23, 2022 at 16:28

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).

• Thank you. This is useful but I think it's a bit different. If I understood correctly it of just does steps (A), (B) and (C1). So we learn a single approximation $F_1$ and then search for minimums of $F_1$. Sep 23, 2022 at 16:18

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.

• Thank you! Do you have any name or reference for the method from the first paragraph or a reference for an example of its application? Sep 23, 2022 at 16:52
• @VladimirZolotov, I don't know of a reference for it (sorry; it's a reasonable question).
– D.W.
Sep 23, 2022 at 17:05