# How to Smooth Gradient Estimates for Steepest Descent Optimization

In steepest descent methods of minimizing a function $f(x), x \in \mathbb{R}^d$,

it's common to approximate the gradient by finite differences: $\qquad\qquad \nabla f(x) \approx gradest( x; h ) \equiv { {f( x + h I ) \ - \ f(x)} \over h }$
then minimize along those directions:
$\qquad\qquad x_{k+1} \ \text{from min} \ f( x_k + \lambda \ gradest( x_k ) )$

Can a signal-processing point of view suggest ways of smoothing $gradest()$ in this context ?
For example, one could view the "zig-zags" in the picture above as high frequencies in $gradest()$, to be smoothed out over the last few ${x_k}$. But that may be naive: can one model, then smooth, zig-zags through non-uniformaly spaced points in 5d or 10d ?

• Add a fraction of the gradient approximation from the previous iteration, and look up Nesterov smoothing.
– Emre
Nov 7 '14 at 8:31
• @Emre, do you know of any connection between Nesterov (smoothing | momentum) and filter theory ? Nov 10 '14 at 16:45
• No, why? As it stands, the question concerns optimization theory.
– Emre
Nov 10 '14 at 18:13
• @Emre, afaik (correct me), Nesterov is used to accelerate big gradient descent / SGD problems, and is very sensitive to learning rates. Has anyone used it on e.g. Rosenbrock ? (I've tried -- terrible.) Dec 2 '14 at 17:01

In the Probabilistic settings we have many methods applied to the Stochastic Gradient Descent in order to decrease the variance of the Gradient Estimation (ADAM / RMS Prop / AdaDelta, etc...).

The nice thing is to utilize them in deterministic settings.
So for instance you can use Momentum which to Signal Processing guy will look just like applying IIR / AR filter on the Gradient.

There are also methods derived from the Convex Optimization world settings.
There is nothing prevents us using them in any setting besides there are no guarantees.
For instance you can use FISTA Method or Nesterov Accelerated Gradient Descent.

More References:

• That's quite a grab bag of methods, mostly for high-dimensional stochastic problems. Have you run any of them on a 2d problem like the one in the plot, or know of such on the web ? Thanks. Jul 11 '18 at 9:22
• Why would they not work on 2D? They indeed work beautifully on 2D as 2D is the limit of what can be shown. Have a look at denizyuret.com/2015/03/alec-radfords-animations-for.html, ruder.io/optimizing-gradient-descent and shaoanlu.wordpress.com/2017/05/29/….
– Royi
Jul 11 '18 at 9:53