2
$\begingroup$

Stochastic gradient descent is a useful approach to improving iteration time by giving up some rate of convergence. For a parameter $w$, learning rate $\eta$, and smooth objective function $Q$ the update rule is:

The term containing "stochastic" reminded me of stochastic processes and their role in SDEs and numerical algorithms like stochastic Runge-Kutta.

The idea of having an iterative algorithm which adds instances of a stochastic process seems like a possibility that someone would have explored by now for gradient descent. One could begin with modifying vanilla gradient descent by adding elements from a stochastic process to it:

$$W_{n+1} = W_n - \eta \nabla Q(w) + X_n$$

where $X_n$ is the $n$th element of a stochastic process.

Not all choices of stochastic process would result in the update rule having some form of convergence in the parameter random variable. Indeed, on the face of it including noise like this could seem like a horrible idea since you'll get inferior rate of convergence and makes the final parameter estimate noisier.

The main benefit I see is to allow jumps in the parameter coordinate to help avoid to getting stuck in local minima. Naturally, there are other approaches like adaptive learning rates to tackle this.

Maybe such alternatives are generally better, but for me this other "stochastic gradient descent" is an under-examined possibility. I imagine the approach isn't popular for the inefficiencies it introduces, but I can also imagine that for sufficiently gnarly parameters spaces (e.g. lots of local minima) that its ability to make jumps could be helpful.

Is this idea a dead end that was already explored in the literature? Or is it a fruitful niche that exists in the literature? Or is it still off people's radar?

$\endgroup$
6
  • 1
    $\begingroup$ SGD also has the benefit of allowing jumps (it is an effective way of adding noise), while requiring much less computations (which is one of the the main motivations of using it). Computing the full gradient and then adding noise seems a bit strange from that perspective $\endgroup$
    – J. Delaney
    Apr 23, 2023 at 18:28
  • 2
    $\begingroup$ @J.Delaney - it seems similar to "exploration vs. exploitation" thinking to me; I don't know that you would want to do it on every step, but... $\endgroup$
    – jbowman
    Apr 23, 2023 at 18:38
  • $\begingroup$ @jbowman The exploration vs exploitation tradeoff is what I was thinking about, but the term is often used in reinforcement learning. I thought the term might confuse the scope of the question. $\endgroup$
    – Galen
    Apr 23, 2023 at 18:40
  • 2
    $\begingroup$ optimization in the context of ML / neural networks (where SGD is most common) is a bit different from classical optimization in that trying "too hard" to find a lower local minimum is generally considered a bad idea, as it often leads to overfitting. $\endgroup$
    – J. Delaney
    Apr 23, 2023 at 18:56
  • $\begingroup$ @J.Delaney That's an excellent point. Thinking about various test functions led me to think about the benefit of hopping around more. But it is also true that the loss surface is subject to sampling error and measurement error. Some optima may be stable across samples, and others not. Definitely worth some more thought on my part. Of course in practice we have to test our models! $\endgroup$
    – Galen
    Apr 23, 2023 at 19:02

1 Answer 1

0
$\begingroup$

Within the deep learning and adjacent communities, the biggest advantage of SGD is that there is an implementation that is an order of complexity faster than per iteration than standard gradient descent.

The basic idea is that taking a sub-sample of data (potentially even 1 row!), you can show that in many cases, you have the expected gradient plus unbiased noise. This is a version of SGD, and it's also one in which the computational cost per iteration does not scale with the sample size of your data. For problems in which there are billions (or trillions!) of examples, clearly this is a make-or-break feature.

The fact that SGD may or may not dodge local minima is still of interest, but as an example, a version of SGD that required computation of exact gradient first with noise added on after would be a non-starter for most use cases, even if it were better at dodging local modes. However, there are methods like Adam that are no more expensive than "vanilla SGD" but tame the step sizes to help stabilize algorithm. In a sense, you could think of these methods as one in which we alter the form of the noise in order to have more desirable properties of the algorithm. Likewise, the general class of methods with momentum components are believed to help "blow past" local minimum.

$\endgroup$
3
  • $\begingroup$ Yes, I know all this and use Adam and similar methods on a regular basis. My question is about what happened to this other (possibly naive) idea of adding a stochastic process to the update rule. This 'could' be done with any of the common gradient-based methods, including Adam. I choice gradient descent as a simple example. Am I reading between the lines correctly that this other idea was a dead end in the literature? Or are you implying something else? $\endgroup$
    – Galen
    Apr 23, 2023 at 20:31
  • $\begingroup$ I'm merely implying that the main motivation for SGD is the speed. I think you could argue that momentum-based SGD is doing exactly what you are saying, i.e. altering the form of the noise to avoid local minimum. If you mean adding new noise explicitly (i.e. +rand(...)) rather than implicitly (sub-sampling the data), I'm guessing this isn't very much explored due to being a bit counter intuitive. If you could show that adding a noise term is better than a momentum based approach, I think you would surprise a lot of researchers. $\endgroup$
    – Cliff AB
    Apr 23, 2023 at 20:40
  • $\begingroup$ On the other hand, if you are talking about optimization for classes of problems in which the gradient is cheap but the optimization surface is not well behaved so we might want SGD specifically for mode dodging, that's an area of research that probably exists but doesn't get close to as much attention due to the popularity of DL. $\endgroup$
    – Cliff AB
    Apr 23, 2023 at 20:46

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.