2
$\begingroup$

I am minimizing a function using gradient descent. The learning rate is fixed. First, for few iterations, the cost decreases; after that, it starts increasing. What is the reason for this?

$\endgroup$
3
  • $\begingroup$ Problem-specific. Decreases and increases how? If the energy goes like 10, 1, 0, 0.01, 0.02, 0.03, 0.04, ... it's likely to be numerical error. If it goes like 10, 1, 0, 5, 10, 100, then you're not doing gradient descent on a good function. $\endgroup$
    – snar
    Oct 15, 2014 at 15:59
  • $\begingroup$ Try reducing the learning rate slowly, e.g. $\sim 1/\sqrt{k}$ or $\sim 1/\log k$. $\endgroup$ Oct 15, 2014 at 16:01
  • 1
    $\begingroup$ If learning rate = step size, then you should use a linesearch method to determine step size. $\endgroup$
    – daw
    Oct 15, 2014 at 17:58

1 Answer 1

2
$\begingroup$

One possible reason is due to Ill condtioning of Hessian matrix. Condition number of a matrix is the ratio of the largest singular value to the smallest singular value. A matrix is ill-conditioned if the condition number is very high, usually indicating that (i) the lowest singular value is orders of magnitude smaller than the highest one, and (ii) columns/rows of the matrix are heavily correlated with each other leading to redundancies and a matrix that is pretending to be of a higher rank than it truly is.

Hessian encodes the second derivatives of a function with respect to all pairs of variables. So, if there are n inputs to a function, the gradient is n-dimensional and the Hessian is nxn-dimensional. In machine learning, the inputs are usually the features and the function is usually a loss function we are trying to minimize. When the Hessian is ill-conditioned, it means the basis of the loss function have contours that are very long “ellipsoids” rather than being close to “circular”. enter image description here This causes problems for first-order optimization methods like gradient descent (w=w−η∇w) which need to follow a very zigzag path to the minimum. The first figure below shows the gradient directions at various points on a straight line through the parameter space. Notice how the directions away from the center are nearly orthogonal to the useful direction of descent. The second figure shows the zigzag path gradient descent has to take if the Hessian is ill-conditioned, the function contours are stretched out, and the gradients often point to directions that might not be the best way to descend to the minimum.

You would think that second-order optimization would solve this problem. It sort of does if the Hessian is not too ill-conditioned. I have inserted a screenshot from Chapter 8 of Deep learning book by Ian goodfellow et al. To read more about optimization problems in neural networks, you can look at this chapter: http://www.deeplearningbook.org/contents/optimization.html

Ill conditioning of Hessian matrix

$\endgroup$

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.