Using gradient descent: cost decreases, then increases 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?
 A: 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”.

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
