0
$\begingroup$

I have a function $f:\mathbb R^N\to \mathbb R$ and I would like to compute all the partial derivatives of $f$ w.r.t. the $N$ input. What is the computational complexity using the (ones-sided) finite difference method $\big(\text{derivative of f w.r.t. x}\sim\frac {f(x+\epsilon)-f(x)}{\epsilon}\big)$ using the $O( \ )$-notation? Could you also provide an explanation of that?

$\endgroup$
  • 4
    $\begingroup$ You are dividing by a vector, aren't you? $\endgroup$ – nicoguaro Apr 5 at 14:19
  • 2
    $\begingroup$ Also, what is the complexity of evaluating $f$? $\endgroup$ – nicoguaro Apr 5 at 14:19
  • $\begingroup$ @nicoguaro why dividing by a vector? the complexity of f is not known but I suppose that does not impact on the general order of the complexity. Let's say that the general order is n, if $f$ embed a sum, a multiplication and some other computation, the order will be always n.. it seems to me.. $\endgroup$ – Albert Apr 5 at 20:11
  • 1
    $\begingroup$ @nicoguaro is right here. You are confused here I think. If $f$ is a function that takes a vector $x$, you can't evaluate this expression $\frac{f(x+\epsilon)-f(x)}{\epsilon}$ cause it seems $\epsilon$ is also a vector. Unless, you are also confused and mixed up the notations here, which needs to be clarified. Also, you can't say I don't care about time-complexity of $f$ cause any finite difference method to approximate the derivatives needs to evaluate $f$ at some points in the space and final time-complexity depends on $f$ for sure. $\endgroup$ – Alone Programmer Apr 5 at 21:02
  • 1
    $\begingroup$ You meant to write $f(x+\epsilon e_i)$ where $e_i$ is the $i$th unit vector. $\endgroup$ – Wolfgang Bangerth Apr 6 at 17:35
5
$\begingroup$

As pointed out in the comments, the cost of evaluating $f$ is critical, and in most practical cases will be the dominant cost. Lets suppose it takes $C$ operations to evaluate $f$. For nontrivial functions, $C$ will be at least $\mathcal{O}(N)$ just from using the $N$ arguments.

Also pointed out in the comments, the finite difference formula you have does not make sense for a function that maps a vector to a scalar. If you are looking to approximate the entire gradient vector $\nabla f$ with finite differences, you can use the approximation

$$ \nabla f(x) = \begin{bmatrix} \frac{f(x + \epsilon e_1) - f(x)}{\epsilon} & \frac{f(x + \epsilon e_2) - f(x)}{\epsilon} & \cdots & \frac{f(x + \epsilon e_N) - f(x)}{\epsilon} \end{bmatrix} + \mathcal{O}(\epsilon^2) $$

where $e_i$ is the $i$-th canonical basis vector for $\mathbb{R}^N$. There are $N+1$ calls to $f$ here along with $N$ subtractions and divisions so the cost is $\mathcal{O}(C N)$.

In many cases a gradient is multiplied by a vector to get a directional derivative $\nabla f(x) \cdot v$. If this is the case, the following approximation is more efficient:

$$ \nabla f(x) \cdot v = \frac{f(x + \epsilon v) - f(x)}{\epsilon} + \mathcal{O}(\epsilon^2). $$

Now there are just two function evaluations and a cost of $\mathcal{O}(C)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.