Questions tagged [gradient-descent]

Gradient descent is a first-order iterative optimization algorithm. To find a local minimum of a function using gradient descent, one takes steps proportional to the negative of the gradient (or of the approximate gradient) of the function at the current point. For stochastic gradient descent there is also the [sgd] tag.

Filter by
Sorted by
Tagged with
59
votes
7answers
10k views

Optimization when Cost Function Slow to Evaluate

Gradient descent and many other methods are useful for finding local minima in cost functions. They can be efficient when the cost function can be evaluated quickly at each point, whether numerically ...
33
votes
2answers
9k views

Do we need gradient descent to find the coefficients of a linear regression model?

I was trying to learn machine learning using the Coursera material. In this lecture, Andrew Ng uses gradient descent algorithm to find the coefficients of the linear regression model that will ...
3
votes
1answer
451 views

How can change in cost function be positive?

In chapter 1 of Nielsen's Neural Networks and Deep Learning it says To make gradient descent work correctly, we need to choose the learning rate η to be small enough that Equation (9) is a good ...
144
votes
8answers
63k views

Why is Newton's method not widely used in machine learning?

This is something that has been bugging me for a while, and I couldn't find any satisfactory answers online, so here goes: After reviewing a set of lectures on convex optimization, Newton's method ...
81
votes
7answers
43k views

Why use gradient descent for linear regression, when a closed-form math solution is available?

I am taking the Machine Learning courses online and learnt about Gradient Descent for calculating the optimal values in the hypothesis. h(x) = B0 + B1X why we ...
17
votes
1answer
10k views

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

Standard Gradient Descent would compute gradient for the entire training dataset. ...
107
votes
3answers
103k views

Batch gradient descent versus stochastic gradient descent

Suppose we have some training set $(x_{(i)}, y_{(i)})$ for $i = 1, \dots, m$. Also suppose we run some type of supervised learning algorithm on the training set. Hypotheses are represented as $h_{\...
25
votes
6answers
5k views

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

Given a convex cost function, using SGD for optimization, we will have a gradient (vector) at a certain point during the optimization process. My question is, given the point on the convex, does the ...
74
votes
2answers
47k views

Solving for regression parameters in closed-form vs gradient descent

In Andrew Ng's machine learning course, he introduces linear regression and logistic regression, and shows how to fit the model parameters using gradient descent and Newton's method. I know gradient ...
46
votes
1answer
29k views

How does the Adam method of stochastic gradient descent work?

I'm familiar with basic gradient descent algorithms for training neural networks. I've read the paper proposing Adam: ADAM: A METHOD FOR STOCHASTIC OPTIMIZATION. While I've definitely got some ...
24
votes
3answers
8k views

Why use gradient descent with neural networks?

When training a neural network using the back-propagation algorithm, the gradient descent method is used to determine the weight updates. My question is: Rather than using gradient descent method to ...
41
votes
4answers
32k views

How does rectilinear activation function solve the vanishing gradient problem in neural networks?

I found rectified linear unit (ReLU) praised at several places as a solution to the vanishing gradient problem for neural networks. That is, one uses max(0,x) as activation function. When the ...
28
votes
2answers
10k views

What is the difference between EM and Gradient Ascent?

What is the difference between the algorithms EM (Expectation Maximization) and Gradient Ascent (or descent)? Is there any condition under which they are equivalent?
18
votes
2answers
2k views

What causes sudden drops in training/test errors when training a neural network?

I've seen plots of test/training error suddenly dropping at certain epoch(s) a few times during the neural network training, and I wonder what causes these performance jumps: This image is taken from ...
55
votes
4answers
56k views

What's the difference between momentum based gradient descent and Nesterov's accelerated gradient descent?

So momentum based gradient descent works as follows: $v=self.momentum*m-lr*g$ where $m$ is the previous weight update, and $g$ is the current gradient with respect to the parameters $p$, $lr$ is the ...
32
votes
4answers
37k views

How is the cost function from Logistic Regression derivated

I am doing the Machine Learning Stanford course on Coursera. In the chapter on Logistic Regression, the cost function is this: Then, it is derivated here: I tried getting the derivative of the cost ...
71
votes
3answers
12k views

Why do neural network researchers care about epochs?

An epoch in stochastic gradient descent is defined as a single pass through the data. For each SGD minibatch, $k$ samples are drawn, the gradient computed and parameters are updated. In the epoch ...
17
votes
2answers
12k views

What is the difference between Maximum Likelihood Estimation & Gradient Descent?

What are the pro & cons of both the methods?
10
votes
1answer
2k views

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

It seems that, especially for deep learning, there are dominating very simple methods for optimizing SGD convergence like ADAM - nice overview: http://ruder.io/optimizing-gradient-descent/ They trace ...
21
votes
3answers
6k views

Is Gradient Descent possible for kernelized SVMs (if so, why do people use Quadratic Programming)?

Why do people use Quadratic Programming techniques (such as SMO) when dealing with kernelized SVMs? What is wrong with Gradient Descent? Is it impossible to use with kernels or is it just too slow (...
29
votes
6answers
3k views

Why not use the third derivative for numerical optimization?

If Hessians are so good for optimization (see e.g. Newton's method), why stop there? Let's use the third, fourth, fifth, and sixth derivatives? Why not?
9
votes
3answers
12k views

Linear regression and non-invertibility

In linear regression there are two approaches for minimizing the cost function: The first one is using gradient descent. The second one is setting the derivative of the cost function to zero and ...
2
votes
2answers
1k views

Stochastic gradient descent Vs Mini-batch size 1

Is stochastic gradient descent basically the name given to mini-batch training where batch size = 1 and selecting random training rows? i.e. it is the same as 'normal' gradient descent, it's just the ...
49
votes
1answer
71k views

How large should the batch size be for stochastic gradient descent?

I understand that stochastic gradient descent may be used to optimize a neural network using backpropagation by updating each iteration with a different sample of the training dataset. How large ...
25
votes
2answers
11k views

Gradient backpropagation through ResNet skip connections

I'm curious about how gradients are back-propagated through a neural network using ResNet modules/skip connections. I've seen a couple of questions about ResNet (e.g. Neural network with skip-layer ...
17
votes
5answers
24k views

Why doesn't k-means give the global minimum?

I read that the k-means algorithm only converges to a local minimum and not to a global minimum. Why is this? I can logically think of how initialization could affect the final clustering and there is ...
20
votes
2answers
3k views

In neural nets, why use gradient methods rather than other metaheuristics?

In training deep and shallow neural networks, why are gradient methods (e.g. gradient descent, Nesterov, Newton-Raphson) commonly used, as opposed to other metaheuristics? By metaheuristics I mean ...
9
votes
1answer
1k views

How is gradient boosting like gradient descent?

I am reading the useful Wikipedia entry on gradient boosting (https://en.wikipedia.org/wiki/Gradient_boosting), and try to understand how / why we can approximate the residuals by the steepest descent ...
12
votes
2answers
2k views

Gradient descent doesn't find solution to ordinary least squares on this dataset?

I have been studying linear regression and tried it on below set {(x,y)}, where x specified the area of house in square-feet, and y specified the price in dollars. This is the first example in Andrew ...
14
votes
2answers
6k views

Gradient descent vs lm() function in R?

I'm going through the videos in Andrew Ng's free online machine learning course at Stanford. He discusses Gradient Descent as an algorithm to solve linear regression and writing functions in Octave ...
5
votes
1answer
2k views

Why one epoch for stochastic gradient descent (SGD) is much better than one iteration for gradient decent (GD)?

Calculating gradient needs to sum over all the data points. So, SGD can be viewed as "using one data point to weakly approximate the gradient" to save time. Intuitively, I would think One epoch for ...
3
votes
1answer
495 views

How to compute gradient of partial log-likelihood function in Cox proportional hazards model?

The partial log-likelihood function in Cox proportional hazards is given with such formula $${}_{p}\ell(\beta) = \sum\limits_{i=1}^{K}X_i'\beta - \sum\limits_{i=1}^{K}\log\Big(\sum\limits_{l\in \...
6
votes
1answer
3k views

When the data set size is not a multiple of the mini-batch size, should the last mini-batch be smaller, or contain samples from other batches?

When training a artificial neural network using stochastic gradient descent with mini-batches, if the data set size is not a multiple of mini-batches, should the last mini-batch contains fewer samples?...
3
votes
1answer
150 views

What optimization (maximization/minimization) methods exist contours with lots of kinks?

I am wondering what methods exist out there for optimization on problems where your contour has lots of small sharp kinks. For example, suppose we have a contour where there are lots of lots of spiky, ...
1
vote
0answers
62 views

Proving that an SVM problem with a complex loss function is convex

The end goal, along with proving that the problem is convex, is to be able to get the problem into a form that can be coded in CVX. I have m positively labeled data points $x_i$ $\in$ $\mathbb{R}^n, ...
2
votes
1answer
799 views

Most common method for deciding when to stop training a neural net on a batch

I have created my own neural net which is using batch gradient descent. In other words, it trains on batches of examples all at once. My issue is trying to figure out when to stop the training of the ...
1
vote
0answers
42 views

Momentum updates average of g, Adagrad also of g^2 - any other interesting updated averages for SGD convergence?

Updating exponential moving average is a basic tool of SGD methods, starting with of gradient $g$ in momentum method to extract local linear trend from the statistics. Then e.g. Adagrad, ADAM family ...
1
vote
1answer
101 views

Can we apply analyticity of a neural network to improve upon gradient descent? [duplicate]

Gradient descent uses the first order derivative information of the objective function as a function of the parameters. Gradient descent therefore uses only “local” information about the objective ...
26
votes
1answer
29k views

How to define the termination condition for gradient descent?

Actually, I wanted to ask you how can I define the terminating condition for gradient descent. Can I stop it based upon the number of iterations, i.e. considering parameter values for, say, 100 ...
21
votes
3answers
27k views

How does batch size affect convergence of SGD and why?

I've seen similar conclusion from many discussions, that as the minibatch size gets larger the convergence of SGD actually gets harder/worse, for example this paper and this answer. Also I've heard of ...
20
votes
3answers
34k views

How can stochastic gradient descent avoid the problem of a local minimum?

I know that stochastic gradient descent has random behavior, but I don't know why. Is there any explanation about this?
21
votes
3answers
13k views

From the Perceptron rule to Gradient Descent: How are Perceptrons with a sigmoid activation function different from Logistic Regression?

Essentially, my question is that in multilayer Perceptrons, perceptrons are used with a sigmoid activation function. So that in the update rule $\hat{y}$ is calculated as $$\hat{y} = \frac{1}{1+\exp(...
15
votes
1answer
14k views

Sum or average of gradients in (mini) batch gradient decent? [duplicate]

When I implemented mini batch gradient decent, I just averaged the gradients of all examples in the training batch. However, I noticed that now the optimal learning rate is much higher than for online ...
23
votes
4answers
8k views

When are genetic algorithms a good choice for optimization?

Genetic algorithms are one form of optimization method. Often stochastic gradient descent and its derivatives are the best choice for function optimization, but genetic algorithms are still sometimes ...
9
votes
3answers
3k views

Gradient descent on non-convex functions

What situations do we know of where gradient descent can be shown to converge (either to a critical point or to a local/global minima) for non-convex functions? For SGD on non-convex functions, one ...
15
votes
1answer
16k views

How do CNN's avoid the vanishing gradient problem

I have been reading a lot about convoloutional neural networks and was wondering how they avoid the vanishing gradient problem. I know deep belief networks stack single level auto-encoders or other ...
14
votes
4answers
9k views

How can it be trapped in a saddle point?

I am currently a bit puzzled by how mini-batch gradient descent can be trapped in a saddle point. The solution might be too trivial that I don't get it. You get an new sample every epoch, and it ...
6
votes
2answers
12k views

Gradient for hinge loss multiclass

I am a little confused when trying to find the gradient for the multiclass hinge loss: $$l(y) = \max( 0, 1 + \underset{r \neq y_i}{ \max } W_r \cdot x_i - W_{y_i} \cdot x_i)$$ Where $W^{k \times n}$...
3
votes
2answers
8k views

Derivative of softmax and squared error

I'm trying to understand the derivatives w.r.t. the softmax arguments when used in conjunction with a squared loss (for example as the last layer of a neural network). I am using the following ...
9
votes
2answers
1k views

Why are my steps getting smaller when using fixed step size in gradient descent?

Suppose we are doing a toy example on gradient decent, minimizing a quadratic function $x^TAx$, using fixed step size $\alpha=0.03$. ($A=[10, 2; 2, 3]$) If we plot the trace of $x$ in each iteration, ...