Answers.Body: <p>The problem is not the input size but the model size.<br />
  Indeed, derivative-free/zero-order optimization methods usually tend to estimate a descent direction that correlates with some notion of local gradient (that might happen not to exist because the loss is not differentiable)</p>
  <p>Now, you can consider zero-order optimization as a &quot;practical&quot; finite difference method:
  <span class="math-container">$$
  f'(x) = lim_{\,h\,\rightarrow 0} \frac{f(x+h) - f(x)}{h}
  $$</span></p>
  <p>Thus, what they aim to do is to find a multidimensional direction <span class="math-container">$h$</span> that is a descent direction</p>
  <p>At this point, you can see that in order for such direction to have a span of the whole parameter space, you need <span class="math-container">$N$</span> function evaluation (in the general case), thus will be very computationally expensive to optimize the problem if your bi-lstm is very big in model size</p>
  <p>However, nothing stops you from taking a direction that might not span the whole space</p>
  <p>Clarified that the problem is the model size, you can consider any evolutionary strategy algorithm for such problem, something like Cross Entropy Methods (CE) or CMA-ES should work fine for your problem</p>
  <p>You can find improved versions in the citations of the paper of such methods, though they might lack an implementation in the programming language you are using</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-14T13:57:19.117Z
Answers.Text: Thanks, I will investigate more. Can I understand the formula you mentioned as follows: create an estimator of loss using maybe a neural network, and during the update, we both calculate the distance of the estimator and the real loss, and then update the model using estimator loss?
Answers.UserDisplayName: TWTom
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-14T17:21:21.083Z
Answers.Text: no, that was just an intro to CE and CMA-ES, which is "perturb your weights x by random quantity/direction h N times, and move toward the ones that worked the best"
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-14T11:44:48.063Z
Answers.LastActivityDate: 2024-01-14T11:44:48.063Z
Answers.UserDisplayName: Alberto
Body: <p>As titled, I want to ask what is the SOTA of derivative-free algorithm.</p>
  <p>I am not familiar with this thing at all, the only derivative-free optimization algorithm I am familiar with is GA, and others like Bayesian Optimization, I just know the name, but I don't even know what they do.</p>
  <p>The model I want to optimize is some bi-lstm models with about 3 layers, which has the input shape of (timesteps~=1024, features=512), and the output shape of (timesteps, 256).</p>
  <p>What I also know is that the model is a little big, but the loss calculation is not differentiable, and RL algorithms are not suitable for me, so it lead me down to this.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-01-16T07:13:07.227Z
Comments.Text: For some implementations you can look at [nevergrad](https://facebookresearch.github.io/nevergrad/optimizers_ref.html#optimizers) from facebook.
Comments.UserDisplayName: N. Kiefer
Tags: <optimization><state-of-the-art>
Title: The SOTA of derivative-free optimization
UserDisplayName: TWTom
ThreadText: # The SOTA of derivative-free optimization
  
  (Asked by: username_0 on 2024-01-14)
  
  As titled, I want to ask what is the SOTA of derivative-free algorithm.
  
  I am not familiar with this thing at all, the only derivative-free optimization algorithm I am familiar with is GA, and others like Bayesian Optimization, I just know the name, but I don't even know what they do.
  
  The model I want to optimize is some bi-lstm models with about 3 layers, which has the input shape of (timesteps~=1024, features=512), and the output shape of (timesteps, 256).
  
  What I also know is that the model is a little big, but the loss calculation is not differentiable, and RL algorithms are not suitable for me, so it lead me down to this.
  
  **Tags:** optimization, state-of-the-art
  > **Comments:**
  > **username_1**: For some implementations you can look at [nevergrad](https://facebookresearch.github.io/nevergrad/optimizers_ref.html#optimizers) from facebook.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2024-01-14. Score: 1 | Accepted answer
  
  The problem is not the input size but the model size.  
  Indeed, derivative-free/zero-order optimization methods usually tend to estimate a descent direction that correlates with some notion of local gradient (that might happen not to exist because the loss is not differentiable)
  
  Now, you can consider zero-order optimization as a "practical" finite difference method:
  $$
  f'(x) = lim\_{\,h\,\rightarrow 0} \frac{f(x+h) - f(x)}{h}
  $$
  
  Thus, what they aim to do is to find a multidimensional direction $h$ that is a descent direction
  
  At this point, you can see that in order for such direction to have a span of the whole parameter space, you need $N$ function evaluation (in the general case), thus will be very computationally expensive to optimize the problem if your bi-lstm is very big in model size
  
  However, nothing stops you from taking a direction that might not span the whole space
  
  Clarified that the problem is the model size, you can consider any evolutionary strategy algorithm for such problem, something like Cross Entropy Methods (CE) or CMA-ES should work fine for your problem
  
  You can find improved versions in the citations of the paper of such methods, though they might lack an implementation in the programming language you are using
  
  > **Comments:**
  > **username_0**: Thanks, I will investigate more. Can I understand the formula you mentioned as follows: create an estimator of loss using maybe a neural network, and during the update, we both calculate the distance of the estimator and the real loss, and then update the model using estimator loss?  
  > **username_2**: no, that was just an intro to CE and CMA-ES, which is "perturb your weights x by random quantity/direction h N times, and move toward the ones that worked the best"  
  
  ---
  
  