# Gradient of a computational graph Gradient descent optimization takes a differentiable function $`L_\theta` with parameters $`\theta_0 = \{ \theta_{i_0 d_p}: 1\leq p \leq P\}` and finds an approximation to $`\argmin_\theta L_\theta` by iteratively computing the gradient $`\nabla L_\theta` and updating $`\theta_{i+1} \larr \theta_i - \gamma \nabla L_\theta`. Computing the gradient is the most costly part of the process. The compute, memory, and latency cost of the gradient computation is as follows:

Algorithm	Compute	Memory	Latency	Variance
Backprop	2C	C+P	2D	0
Forward autodiff	2CP	W+P	2DP	0
Forward autodiff (parallel)	2CP	WP	2D	0
Finite difference stochastic approximation	2CP	W+P	2DP	0 as ε→0
Simultaneous perturbation stochastic approximation	2C	W+P	2D	P/S as ε→0
Forward autodiff in stochastic directions	2CS+P	W+P	2DS	P/S
Gradient approximation in stochastic directions	CS+P	(W+P)S	D	P/S as ε→0

where: - $`C`: number of nodes in the computational graph. - $`D`: depth of the computational graph. - $`W`: width of the computational graph. - $`P=|\theta|`: number of parameters in the computational graph, for which we want the loss gradient. - $`S`: number of samples (which is meaningful for some algorithms). We will detail the last two algorithms, which we present in this document. ## Forward autodiff in stochastic directions Choose $`S` orthogonal directional vectors in the space of parameters $`\theta`: ```latex V = \begin{bmatrix} v_1^\top\\ v_2^\top\\ \vdots\\ v_S^\top \end{bmatrix} \in\mathbb R^{S\times P} ``` Compute all corresponding directional derivatives $`d_k = D_{v_k}L_\theta = \nabla L_\theta^\top v_k`. Then: ```latex d = \begin{bmatrix} d_1\\ d_2\\ \vdots\\ d_S \end{bmatrix} = V \nabla L_\theta ``` Thus if $`S=P`, we have $`\boxed{\nabla L_\theta = V^{-1}d}`. If $`S