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 ...
- 11.5k
39
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 ...
- 1,892
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 ...
- 86.5k
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 ...
- 18.4k
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),...
- 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 ...
- 94.1k
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):
...
- 8,757
19
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 ...
- 621
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 ...
- 94.1k
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 ...
- 371
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 ...
- 5,800
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 ...
- 58.2k
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/...
11
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 ...
- 595
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 ...
- 131
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: ...
- 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 ...
- 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 ...
- 94.1k
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.
...
- 94.1k
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-\...
- 13.5k
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.
- 2,630
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 ...
- 7,262
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,...
- 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 ...
- 1,277
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 ...
- 1,892
7
votes
Accepted
The actual role of second-order optimization as oppose to first-order optimizations
In other word, does it mean that if I know if the function is concave
then I can tell where the global minimum error is?
Yes, you got the gist of it. You get the first two derivatives of the ...
- 62.3k
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 ...
- 26.5k
7
votes
Accepted
Why increasing the batch size has the same effect as decaying the learning rate?
I think it may be a confusion about the different meanings of stability -- stable as in numerically stable / weights don't go to infinity, versus stable as in the loss steadily monotonically decreases ...
- 26.5k
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 ...
- 21.5k
Only top scored, non community-wiki answers of a minimum length are eligible