3
$\begingroup$

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 ?

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

1 Answer 1

1
$\begingroup$

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:

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – denis
    Jul 11, 2018 at 9:22
  • $\begingroup$ 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/…. $\endgroup$
    – Royi
    Jul 11, 2018 at 9:53
  • $\begingroup$ Also a nice read about ADAM is fast.ai/2018/07/02/adam-weight-decay. $\endgroup$
    – Royi
    Jul 11, 2018 at 9:55
  • $\begingroup$ I asked specifically about a "signal-processing point of view", in the hope of some insight / visualization. Do any of the papers you cite consider that ? (Feel free to improve the title / the question.) $\endgroup$
    – denis
    Nov 11, 2021 at 16:36
  • $\begingroup$ I gave the point of view of those methods, you may think of it as variance reducing by weighted sum of gradients. $\endgroup$
    – Royi
    Nov 11, 2021 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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