In steepest descent methods of minimizing a function $f(x), x \in \mathbb{R}^d$, zig-zag descent path from Wikipedia

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 ?

  • $\begingroup$ Add a fraction of the gradient approximation from the previous iteration, and look up Nesterov smoothing. $\endgroup$ – Emre Nov 7 '14 at 8:31
  • $\begingroup$ @Emre, do you know of any connection between Nesterov (smoothing | momentum) and filter theory ? $\endgroup$ – denis Nov 10 '14 at 16:45
  • $\begingroup$ No, why? As it stands, the question concerns optimization theory. $\endgroup$ – Emre Nov 10 '14 at 18:13
  • $\begingroup$ @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.) $\endgroup$ – denis 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:


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.