1
$\begingroup$

For example due to symmetry of parameters, functions optimized in machine learning usually have huge number of local minima and saddles - growing exponentially with dimension.

I am trying to understand second order SGD convergence methods (slides), and it seems like they often attract to a saddle, like natural gradient wanting to take us to a close point with zero gradient.

There are many approaches trying to escape non-convexity by approximating Hessian with some positive definite matrix, for example:

While such approximation tries to pretend that minimized function is locally convex, in fact it isn't - we can be near a saddle in this moment.

How do such positive Hessian approximations handle saddles?

For example, naively, covariance matrix of recent gradients should be similar near minimum and near saddle (ignores sign of curvature) - why using it doesn't attract to saddles?

$\endgroup$
  • $\begingroup$ One of the features/quirks of SGD is that, done right, the update is, in a sense, rank deficient. It updates in a subset of the operating directions toward the local optimal. This acts like a cousin of stochastic annealing, where noise is injected to the convergence process to keep the optimization from being stuck in a local optimum. The basketball can roll around the rim before going through the basket. $\endgroup$ – EngrStudent Mar 12 at 15:45
  • $\begingroup$ While first order methods also have problem with saddles (stochasticity can help with), my question concerns second order methods - they usually uncritically approximate Hessian with a positive defined matrix, often not even mentioning the elephant in the room: saddles. Why can we ignore them? $\endgroup$ – Jarek Duda Mar 12 at 16:09
  • $\begingroup$ Reddit discussion: reddit.com/r/MachineLearning/comments/b0i9tz/… $\endgroup$ – Jarek Duda Mar 13 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.