Answers.Body: <p>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 <a href="https://ieeexplore.ieee.org/document/9812460" rel="nofollow noreferrer">this paper</a> (NeuroErgo: A Deep Neural Network Method to Improve Postural Optimization for Ergonomic Human-Robot Collaboration).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-23T16:18:06.487Z
Answers.Text: 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$.
Answers.UserDisplayName: Vladimir Zolotov
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-23T04:37:39.177Z
Answers.LastActivityDate: 2022-09-23T04:37:39.177Z
Answers.UserDisplayName: OmG
Answers.Body: <p>Yes, this is a standard approach.  An improvement is to do gradient descent on <span class="math-container">$F$</span> (not <span class="math-container">$F_1$</span>), but use the gradient of <span class="math-container">$F_1$</span> as your estimate for the gradient of <span class="math-container">$F$</span>.  In other words, when you calculate the function in the forward direction, you use <span class="math-container">$F$</span>, but when you backprop to get the gradient, you backprop through <span class="math-container">$F_1$</span>.</p>
  <p>Since the number of dimensions is so low in your case, an alternative is to use a <a href="https://en.wikipedia.org/wiki/Derivative-free_optimization" rel="nofollow noreferrer">gradient-free black-box optimization method</a>.  One approach is to use a zeroth-order optimization methods, where you use the method of <a href="https://en.wikipedia.org/wiki/Finite_difference" rel="nofollow noreferrer">finite differences</a> to estimate the gradient at a particular point.  You can estimate the gradient of <span class="math-container">$F$</span> at a point <span class="math-container">$x$</span> by evaluating <span class="math-container">$F$</span> at <span class="math-container">$n+1$</span> points, namely <span class="math-container">$F(x)$</span> and <span class="math-container">$F(x+\epsilon \cdot e_i)$</span> where <span class="math-container">$e_i$</span> is a vector of all-zeros except it has a 1 in the <span class="math-container">$i$</span>th coordinate.  This will be pretty efficient since in your setting, <span class="math-container">$n$</span> is small.  An improvement of that method is to use <a href="https://en.wikipedia.org/wiki/Natural_evolution_strategy" rel="nofollow noreferrer">NES</a>, where we estimate the gradient of <span class="math-container">$F$</span> as follows:</p>
  <p><span class="math-container">$$\nabla F(x) \approx {1 \over m} \sum_{i=1}^m F(z_i) \nabla \log p(z_i)$$</span></p>
  <p>where each <span class="math-container">$z_i$</span> is sampled iid from the normal distribution <span class="math-container">$\mathcal{N}(x,\sigma^2)$</span> and <span class="math-container">$p$</span> is the pdf of <span class="math-container">$\mathcal{N}(x,\sigma^2)$</span>.  There are many other candidate methods as well.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-23T16:52:44.007Z
Answers.Text: 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?
Answers.UserDisplayName: Vladimir Zolotov
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-23T17:05:02.790Z
Answers.Text: @VladimirZolotov, I don't know of a reference for it (sorry; it's a reasonable question).
Answers.UserDisplayName: D.W.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-23T16:43:16.823Z
Answers.LastActivityDate: 2022-09-23T16:43:16.823Z
Answers.UserDisplayName: D.W.
Body: <p>So I have this function let call her <span class="math-container">$F:[0,1]^n \rightarrow \mathbb{R}$</span> and say <span class="math-container">$10 \le n \le 100$</span>.  I want to find some <span class="math-container">$x_0 \in [0,1]^n$</span> such that <span class="math-container">$F(x_0)$</span> is as small as possible. I don't think there is any hope of getting the global minimum. I just want a reasonably good <span class="math-container">$x_0$</span>.</p>
  <p>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 <span class="math-container">$F$</span> are computed algorithmically and I don't have a way to compute gradients for <span class="math-container">$F$</span>.</p>
  <p>So I want to do something like this.</p>
  <p>(A) We create a neural network which takes an <span class="math-container">$n$</span>-dimensional vector as input and returns a real number as result. We want the NN to &quot;predict&quot; values of <span class="math-container">$F$</span> but at this point it is untrained.</p>
  <p>(B) We take bunch of random points in <span class="math-container">$[0,1]^n$</span>. We compute values of <span class="math-container">$F$</span> at those points. And we train NN using this data.</p>
  <p>(C1) Now the neural net provides us with a reasonably smooth function <span class="math-container">$F_1:[0,1]^n \rightarrow \mathbb{R}$</span> approximating <span class="math-container">$F$</span>. We run a gradient decent a bunch of times on <span class="math-container">$F_1$</span>. We take the final points of those decent and compute <span class="math-container">$F$</span> on them to see if we caught any small values. Then we take whole paths of those gradient decent, compute <span class="math-container">$F$</span> on them and use this as data to retrain our neural net.</p>
  <p>(C2) The retrained neural net provides us with a new function <span class="math-container">$F_2$</span> and we repeat the previous step</p>
  <p>(C3) ...</p>
  <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-09-23T16:28:42.837Z
Comments.Text: Cross-posted: https://ai.stackexchange.com/q/37166/1794, https://mathoverflow.net/q/431052/37212, https://cs.stackexchange.com/q/154308/755.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).
Comments.UserDisplayName: D.W.
Tags: <neural-networks><reference-request><gradient-descent><function-approximation>
Title: Can I minimize a mysterious function by running a gradient descent on her neural net approximations?
UserDisplayName: Vladimir Zolotov
ThreadText: # Can I minimize a mysterious function by running a gradient descent on her neural net approximations?
  
  (Asked by: username_0 on 2022-09-22)
  
  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?
  
  **Tags:** neural-networks, reference-request, gradient-descent, function-approximation
  > **Comments:**
  > **username_1**: Cross-posted: https://ai.stackexchange.com/q/37166/1794, https://mathoverflow.net/q/431052/37212, https://cs.stackexchange.com/q/154308/755.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2022-09-23. Score: 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](https://ieeexplore.ieee.org/document/9812460) (NeuroErgo: A Deep Neural Network Method to Improve Postural Optimization for Ergonomic Human-Robot Collaboration).
  
  > **Comments:**
  > **username_0**: 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$.  
  
  ---
  
  ### Answer by username_1 on 2022-09-23. Score: 1
  
  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](https://en.wikipedia.org/wiki/Derivative-free_optimization). One approach is to use a zeroth-order optimization methods, where you use the method of [finite differences](https://en.wikipedia.org/wiki/Finite_difference) 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](https://en.wikipedia.org/wiki/Natural_evolution_strategy), 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.
  
  > **Comments:**
  > **username_0**: 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?  
  > **username_1**: @VladimirZolotov, I don't know of a reference for it (sorry; it's a reasonable question).  
  
  ---
  
  