Non-Convex Optimization: How Well Do We Understand It?

Question

As we know, there has been a lot of work and research done to demonstrate that the Gradient Descent Algorithm can converge on (deterministic) convex, differentiable and Lipschitz Continuous functions :

However, I am interested in learning about to what extent convergence of Gradient Descent Based Algorithms (e.g. Stochastic Gradient Descent) has been studied for (non-deterministic) Non-Convex Functions

I have been trying to read about this topic over the past few weeks, but the level of math required to understand some of these results goes far beyond my ability to understand. For instance, below are some of the publications that I consulted:

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?

References:

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

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

Answer 1

No we have not, and it doesn't.

Many decades of brilliant optimisation ideas have given us an extensive array of tools to use, but every tool is best suited for a certain job.

Mathematically speaking, there are very good reasons for which (stochastic) gradient descent does not have good convergence properties for non-convex problems. In fact, it is a very bad method to use on convex problems as well, assuming the problem is small enough to use better methods.

What makes it shine in machine learning is that, due to the size of the problem, it's one of the best methods that are usable in practice. In other words, it's a great tool for that job.

GD converges on convex problems because there's a guaranteed path for it to follow to get to the minimum. This is simply not guaranteed in the non-convex case, which is why the authors say it will either diverge or converge to a minimum. This makes perfect sense: if we happen to be very far from a basin of attraction, or if the non-convexity of the hypersurface is such that from most directions our algorithm will just slide past the basin of attraction, no amount of tricks will give us a guarantee of getting there if we must restrict ourselves to GD. With enough black magic, it can still of course work great a lot of the time, especially under assumptions.

The other aspect we must take into account here is the probability. There are many stochastic methods that have probability 1 to converge to a minimum, but what are the time assumptions? Is it after finite time, or infinite time?

A way we can think of the hierarchy of methods we want to be using, is how expensive/feasible it is to use a certain tool vs the potential payoff.

For instance, if a non-convex problem can be solved by a deterministic global optimisation solver, those methods guarantee global convergence in finite time and a finite number of iterations (which can still be a million years in practice).

If the problem is too large for a global optimiser, we would use local optimisation with second-order information.

If a problem is too large for second-order information, we would use first-order information (e.g. gradient descent).

If the problem is too large and/or too non-convex for the first-order method to perform well, we would use a stochastic method.

If the problem is still unsolvable, we either spend a few years/decades figuring it out, or wait until someone much smarter than us waltzes in and destroys it like it was nothing.