Does Stochastic Gradient Descent Converge on "some" Non-Convex Functions?

Question

I am interested in better understanding the theoretical behavior (i.e. strength of convergence) of Stochastic Gradient Descent on Non-Convex Functions.

We are constantly reminded that Stochastic Gradient Descent has the ability to converge for (deterministic, smooth, lipschitz continuous) Convex Functions - but usually, we also reminded that Stochastic Gradient Descent is not guaranteed to converge on Non-Convex Functions. Given that many applications in Machine Learning usually require optimizing a Non-Convex Function - several "variants" of the Stochastic Gradient Descent algorithm (e.g. ADAM, RMSprop) have been developed that literally "boost" the optimization algorithm out of the "Saddle Points" which often occur in Non-Convex Functions and result in suboptimal results.

However, I found some research papers online that suggest Stochastic Gradient Descent actually might be able to display "some convergence" on Non-Convex Functions - but my knowledge in this topic is far insufficient to fully understand the claims being made in these papers. I have listed summaries of these papers below:

1) "Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptions" (Lei et al., 2019)

In this paper, the authors comment that:

• Stochastic Gradient Descent is being heavily used on Non-Convex Functions, but the theoretical behavior of Stochastic Gradient Descent on Non-Convex Functions is not fully understood (currently only understood for Convex Functions).

• Currently, Stochastic Gradient Descent requires imposing a nontrivial assumption on the uniform boundedness of gradients.

• The authors establish a theoretical foundation for Stochastic Gradient Descent for Non-Convex Functions where the boundedness assumption can be removed without affecting convergence rates.

• The authors establish sufficient conditions for almost sure convergence as well as optimal convergence rates for Stochastic Gradient Descent applied to Non-Convex Functions.

2) "Stochastic Gradient Descent on Nonconvex Functions with General Noise Models" (Patel et al 2021)

In this paper, the authors comment that:

• Although recent advancements in Stochastic Gradient Descent have been noteworthy, these advancements have nonetheless imposed certain restrictions (e.g., Convexity, Global Lipschitz Continuity etc.) on the functions being optimized.

• The authors prove that for general class of Non-Convex Functions, Stochastic Gradient Descent iterates either diverge to infinity or converge to a stationary point with probability one.

• The authors make further restrictions and prove that regardless of whether the iterates diverge or remain finite — the norm of the gradient function evaluated at Stochastic Gradient Descent's iterates converges to zero with probability one and in expectation; thus broadening the scope of functions to which Stochastic Gradient Descent can be applied to while maintaining rigorous guarantees of its global behavior.

My Question: Based on some of these publications, have we truly been able to demonstrate that (Stochastic) Gradient Descent has the potential to display similar global convergence properties on Non-Convex Functions, to the same extent at which it had previously displayed only on Convex Functions?

Or have I completely misunderstood the results from this publications, and the conditions (and class of functions) in which the respective authors explored and demonstrated the convergence behavior of Stochastic Gradient Descent is far less "generous" compared to those pertaining to Convex Functions - and these conditions are also less likely to manifest themselves in real-world applications : And thus we still have reasons to believe that (Stochastic) Gradient Descent has more difficulties converging on Non-Convex Functions compared to Convex Functions?

Thanks!

References:

• https://arxiv.org/abs/1902.00908
• https://arxiv.org/pdf/2104.00423.pdf

Answer 1

The general thrust of the research in this area is to try to identify conditions on non-convex functions under which SGD will converge.

1. Since SGD isn't guaranteed to converge at all on general non-convex functions, it must be the case that it has more difficulties converging on non-convex functions compared to converging on convex functions, where it is indeed guaranteed to converge.

2. Note that "converge to a stationary point" doesn't mean "found a good solution". So be wary of assuming that convergence on non-convex functions is a panacea of some sort for non-convex optimization.

Editing in response to questions:

Stationary points can be saddle points as well as local minima. Under certain conditions on the saddlepoint, and with suitable modifications, SGD can escape a saddlepoint and find a local minimum. The second answer to Gradient descent on non-convex functions and the linked papers are well worth reading in this regard. But even if the SGD does converge to a local minimum, it might be a long way from optimal:

Sure, if we get a good starting point, we'll wind up at the minimum value of about -0.342, but, depending on the context, that might be a very long way indeed from the local minimum of 2.8 to the left of the actual minimum, or indeed from the local minimum of 1.23 to the right of the actual minimum.