1
$\begingroup$

A cross post from on AI StackExchange.

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 decent 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?

$\endgroup$
5
  • 2
    $\begingroup$ This is not the appropriate venue for this question, but I believe what you're looking for is just a gradient-free optimization method? Many numerical libraries implement one or more such methods (e.g. scipy has a Nelder-Mead routine). Maybe start here: en.wikipedia.org/wiki/Derivative-free_optimization $\endgroup$ Sep 23, 2022 at 1:58
  • $\begingroup$ @YoavKallus Thanks for the link. The thing I'm looking for is definitely a gradient-free optimization method. But the thing is that if you plug a tricky function in one of methods from wiki it will probably just never find anything. I mean I assume that ppl from machine learning are using neural nets for a reason another that they are unaware of Nelder-Mead routine. $\endgroup$ Sep 23, 2022 at 2:48
  • 1
  • 1
    $\begingroup$ Hi Vladimir, I just wanted to comment that the proof will be in the pudding. It's a pretty cheap thing to try, and you should just try to do it! I have tried this on several problems where it did horribly, and presumably it does well on others. The most crucial thing will be trying to have some understanding of whether the neural net will be a reasonable approximation of your function. This depends a lot on what kind of function you are trying to optimize. $\endgroup$ Sep 27, 2022 at 15:45
  • $\begingroup$ The problem is that if $d$ is a descent direction for NN, it may be an ascent direction for $F$. $\endgroup$
    – Red shoes
    Jan 23, 2023 at 18:11

0