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 '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
4
$\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 '18 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 '18 at 9:53
  • $\begingroup$ Also a nice read about ADAM is fast.ai/2018/07/02/adam-weight-decay. $\endgroup$
    – Royi
    Jul 11 '18 at 9:55
  • $\begingroup$ @denis, Could you please mark my answer? $\endgroup$
    – Royi
    Nov 11 '21 at 3:41
  • $\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 '21 at 16:36

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.