Skip to main content
43 votes

For convex problems, does gradient in Stochastic Gradient Descent (SGD) always point at the global extreme value?

They say an image is worth more than a thousand words. In the following example (courtesy of MS Paint, a handy tool for amateur and professional statisticians both) you can see a convex function ...
Jan Kukacka's user avatar
  • 11.5k
40 votes
Accepted

How could stochastic gradient descent save time compared to standard gradient descent?

Short answer: In many big data setting (say several million data points), calculating cost or gradient takes very long time, because we need to sum over all data points. We do NOT need to have exact ...
Haitao Du's user avatar
  • 37.1k
38 votes
Accepted

Who invented stochastic gradient descent?

Stochastic Gradient Descent is preceded by Stochastic Approximation as first described by Robbins and Monro in their paper, A Stochastic Approximation Method. Kiefer and Wolfowitz subsequently ...
David Kozak's user avatar
  • 1,842
33 votes

For convex problems, does gradient in Stochastic Gradient Descent (SGD) always point at the global extreme value?

Gradient descent methods use the slope of the surface. This will not necessarily (or even most likely not) point directly towards the extreme point. An intuitive view is to imagine a path of descent ...
Sextus Empiricus's user avatar
28 votes
Accepted

Why second order SGD convergence methods are unpopular for deep learning?

Should we go toward second order methods for deep learning? TL;DR: No, especially now when the pace of innovation is slowing down, and we're seeing less new architectural innovations, and more ways ...
DeltaIV's user avatar
  • 18.1k
22 votes

How can it be trapped in a saddle point?

Take a look at the image below from Off Convex. In a convex function (leftmost image), there is only one local minimum, which is also the global minimum. But in a non-convex function (rightmost image),...
Antimony's user avatar
  • 839
22 votes
Accepted

Mean or sum of gradients for weight updates in SGD

The following assumes a loss function $f$ that's expressed as a sum, not an average. Expressing the loss as an average means that the scaling $\frac{1}{n}$ is "baked in" and no further ...
Sycorax's user avatar
  • 92.3k
21 votes
Accepted

How does batch size affect convergence of SGD and why?

Sure one update with a big minibatch is "better" (in terms of accuracy) than one update with a small minibatch. This can be seen in the table you copied in your question (call $N$ the sample size): ...
Benoit Sanchez's user avatar
19 votes

For convex problems, does gradient in Stochastic Gradient Descent (SGD) always point at the global extreme value?

Steepest descent can be inefficient even if the objective function is strongly convex. Ordinary gradient descent I mean "inefficient" in the sense that steepest descent can take steps that oscillate ...
Sycorax's user avatar
  • 92.3k
17 votes

Batch gradient descent versus stochastic gradient descent

As other answer suggests, the main reason to use SGD is to reduce the computation cost of gradient while still largely maintaining the gradient direction when averaged over many mini-batches or ...
Xiao-Feng Li's user avatar
15 votes

How to choose between SGD with Nesterov momentum and Adam?

In general, there aren't definitive results on one learning algorithm being "better" than another. The common wisdom (which needs to be taken with a pound of salt) has been that Adam requires less ...
Austin Shin's user avatar
14 votes

Who invented stochastic gradient descent?

See Rosenblatt F. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological review. 1958 Nov;65(6):386. I am not sure if SGD was invented ...
Sam Weisenthal's user avatar
13 votes

How to set mini-batch size in SGD in keras

Yes you are right. In Keras batch_size refers to the batch size in Mini-batch Gradient Descent. If you want to run a Batch Gradient Descent, you need to set the <...
Ernest S Kirubakaran's user avatar
13 votes

For convex problems, does gradient in Stochastic Gradient Descent (SGD) always point at the global extreme value?

Local steepest direction is not the same with the global optimum direction. If it were, then your gradient direction wouldn't change; because if you go towards your optimum always, your direction ...
gunes's user avatar
  • 57.7k
12 votes

RMSProp and Adam vs SGD

After researching a few articles online and Keras documentation it is suggested that the RMSProp optimizer is recommended for recurrent neural networks.https://github.com/keras-team/keras/blob/master/...
Alejandro Trujillo's user avatar
11 votes

Why second order SGD convergence methods are unpopular for deep learning?

This is actually starting to change as recent work are showing the benefit of second order methods specially for NLP problems. Some examples are: "ADAHESSIAN: An Adaptive Second Order Optimizer ...
Amir Gholami's user avatar
10 votes
Accepted

Variance of gradient as e.g. in SGD

I gave this issue some more thoughts and came to the following conclusion: Most of the papers that deal with variance reduction for SGD (methods such as SVRG, SAGA, and SAG) actually mean the 1-norm ...
Jonasson's user avatar
  • 575
10 votes
Accepted

Does Keras SGD optimizer implement batch, mini-batch, or stochastic gradient descent?

It works just as you suggest. batch_size parameter does exactly what you would expect: it sets the size of the batch: batch_size: ...
Jan Kukacka's user avatar
  • 11.5k
9 votes
Accepted

Can small SGD batch size lead to faster overfitting?

Using "epoch" on the x-axis to compare "speed" of convergence while comparing different batch sizes makes no sense since the number of weight updates per epoch depends on the batch size. When using ...
Jan Kukacka's user avatar
  • 11.5k
8 votes

No change in accuracy using Adam Optimizer when SGD works fine

The benefits of Adam can be marginal, at best. The initial results were strong, but there is evidence that Adam converges to dramatically different minima compared to SGD (or SGD + momentum). "The ...
Sycorax's user avatar
  • 92.3k
8 votes
Accepted

What should we do when changing SGD optimizer to Adam optimizer?

In my experience, changing optimizers is not a simple matter of swapping one for the other. Instead, changing optimizers also interacts with several other configuration choices in the neural network. ...
Sycorax's user avatar
  • 92.3k
8 votes
Accepted

Why is gradient descent with momentum considered an exponentially weighted average?

Pick a gradient component, call it $g_a$. Let $g_{a,i}$ denote measured gradient on iteration i. Then we set $g_{a,1} = \beta g_{a,1} + (1-\beta)g_{a,1} = g_{a,1}$ $g_{a,2} = \beta g_{a,1} + (1-\...
Mark L. Stone's user avatar
8 votes

SGD for Gaussian Process estimation

This conference paper from NeurIPs 2020 may contain what you are looking for - it contains some theoretical guarantees on using mini-batch stochastic gradient descent in context of Gaussian processes.
microhaus's user avatar
  • 2,540
8 votes
Accepted

What is the meaning of "SGD scales the gradient uniformly in all directions"?

What it's getting at, is the step size you use should depend on the curvature , ie how the gradient changes in each direction. Imagine a narrow u-shaped sloping valley.in the direction of the U, you ...
seanv507's user avatar
  • 7,055
7 votes

How does batch size affect convergence of SGD and why?

To add to Curtis White's answer (and adding some more references): Yes SGD works as a type of regularization. This is important because otherwise, it's hard to explain why DNNs do not always overfit,...
dasWesen's user avatar
  • 201
7 votes
Accepted

Gradient Bandit Algorithm baseline

Your implementation is very close to being correct. The issue is in the definition of $\pi$ (which you have as $P$ in your code). From the notes: where here we have also introduced a useful new ...
combo's user avatar
  • 1,257
7 votes

When will gradient descent converge to a critical point or to a local/global minima) for non-convex functions?

In this answer I will explore two interesting and relevant papers that were brought up in the comments. Before doing so, I will attempt to formalize the problem and to shed some light on some of the ...
David Kozak's user avatar
  • 1,842
7 votes
Accepted

Is stochastic gradient descent biased?

For a typical loss function $L = E_{x_i \sim \text{D}}[f(x_i)]$ and true gradient $\nabla L = E[\nabla f(x_i)]$, the expectation of the SGD gradient is $E[\nabla f(x')]$ where $x'$ is the datapoint in ...
shimao's user avatar
  • 26.3k
6 votes
Accepted

For regression with time varying parameters, SGD or Kalman filter?

Both of these things can be used in an online manner, but they do this in different ways. So they are not competitors. The Kalman filter has two purposes. First, for a batch of data, it will yield ...
Taylor's user avatar
  • 20.9k
6 votes
Accepted

Parameter n_iter in scikit-learn's SGDClassifier

It must be the second. I always answer these questions by looking at the source code (which in sklearn is of very high quality, and is written extremely clearly). The function in question is here (I ...
Matthew Drury's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible