2
$\begingroup$

I'm looking for a proof of convergence of stochastic gradient descent applied to a non-convex smooth function. I'm generally interested in just asymptotic convergence, preferably to a critical point, but not necessary to a (local) minimizer.

I have found many relevant results but they all have some additional assumptions such as convexity.

Given that I also don't care much about speed of convergence how can I obtain the proof?

$\endgroup$

2 Answers 2

3
$\begingroup$

Check out Chapter 4 of: Harold Kushner and Dean Clark (1978). Stochastic Approximation Methods for Constrained and Unconstrained Problems. Springer-Verlag. This work proves asymptotic convergence to a stationary point in the non convex case. See Section 4.1 for their precise assumptions.

$\endgroup$
3
$\begingroup$

There is also a more recent literature on convergence of a randomized SGD for non-convex functions: http://arxiv.org/pdf/1309.5549v1.pdf

$\endgroup$
1
  • $\begingroup$ +1 that's a nice find $\endgroup$ Sep 6, 2016 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.