3
$\begingroup$

Problem statement: Assume that I have an objective function $f(x)$ which takes as input a $D$-dimensional vector $x\in\mathbb{R}^D$, and that $f(x)$ is sufficiently smooth. Assume further that I have a set of $N$ samples $\{x_1,x_2,...,x_N\}$ for which I know the output of the objective functions $\{f(x_1),f(x_2),...,f(x_N)\}$. It is my task to minimize the objective function $f(x)$ by moving the samples towards its minimum.

Complication: Now assume that I cannot evaluate the partial derivatives of the objective function $\nabla f(x)$ analytically, and that evaluations of $f(x)$ are very expensive and $D$ is very large, so that obtaining $\nabla f(x)$ through local finite differences is not an option. Assume further that the points are distributed arbitrarily.

Question: I am looking for methods which would permit me to approximate the partial derivatives of the objective function $\{\nabla_{x_1}f(x_1),\nabla_{x_2}f(x_2),...,\nabla_{x_N}f(x_N)\}$ at each sample point $x_i, i=1,...,N$, using only the evaluations of the objective function at the sample points. Do you know of any methods which could be used towards this end?

Improve this question
$\endgroup$
9
  • $\begingroup$ Have you considered to use Bayesian methods for optimization? or in another word gradient free methods? You don't need to know the gradient at all! See here: github.com/hyperopt/hyperopt $\endgroup$
    – Mithridates the Great
    Dec 6 '19 at 20:49
  • $\begingroup$ Also look here for some method that could give you the derivative at each point without using finite differences: blogs.mathworks.com/cleve/2013/10/14/… $\endgroup$
    – Mithridates the Great
    Dec 6 '19 at 20:53
  • $\begingroup$ Thank you for the comments! I actually intend to use this gradient estimation problem for Bayesian inference, using a technique called Stein Variational Gradient Descent. I am aware of gradient-free BAyesian optimization (e.g. via particle filters or MCMC), but in this case I really need to approximate the derivatives (for reasons too complicated to elaborate them here). The complex step differentiation algorithm sounds very interesting, but requires additional evaluations of $f(x)$, which I would like to avoid (that's also the main motivation to avoid finite differences). $\endgroup$
    – J.Galt
    Dec 7 '19 at 10:01
  • 1
    $\begingroup$ Idea: You take the smallest N evaluations (you want to minimize), you calculate a plane which cuts through these values, you efficiently calculate the gradient of your plane. You descend the gradient. $\endgroup$
    – MPIchael
    Dec 11 '19 at 12:40
  • 1
    $\begingroup$ By following MPIchael idea, what if you create a regression based model by using your $\{x_{1},x_{2},...,x_{N}\}$ and $\{f(x_{1}),f(x_{2}),...,f(x_{N})\}$ and a regression model such as SVM or Gradient Boosting and then when you have this regression based model you can use finite difference to calculate derivatives since these regression models might be much faster to evaluate at certain points. $\endgroup$
    – Mithridates the Great
    Dec 12 '19 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.