题目： Pinning Down the Lojasiewicz Exponent: Towards Understanding the Convergence Behavior of First-Order Methods for Structured Non-Convex Optimization Problems
报告人： 苏文藻 教授 香港中文大学
摘要： The convergence behavior of optimization algorithms has long been a topic of fundamental interest in numerical analysis. Over the past decade or so, various researchers have proposed to use the powerful Lojasiewicz inequality to study the convergence rates of first-order methods (FOMs). In this approach, an exponent in the Lojasiewicz inequality, which we shall call the Lojasiewicz exponent, plays a key role. The Lojasiewicz exponent is an analytic feature of the optimization problem at hand and is independent of the algorithm used. However, if an FOM for solving the problem satisfies certain rather mild conditions, then the value of the Lojasiewicz exponent will determine the convergence rate of that particular FOM. The Lojasiewicz inequality based convergence analysis approach is extremely powerful, as it applies to a wide range of convex and non convex optimization problems. Unfortunately, it suffers from a serious limitation; namely, even for very simple problems, the Lojasiewicz exponent is either not known, or the existing bounds are too weak to lead to any meaningful convergence rate guarantees. As such, there is a strong motivation to determine the Lojasiewicz exponents associated with some concrete optimization problems.

In this talk, we will first briefly review the Lojasiewicz inequality based convergence analysis framework. Then, we will present our recent result, which gives a sharp estimate on the Lojasiewicz exponent associated with a class of orthogonality-constrained quadratic optimization problems. Lastly, we will discuss some directions for future study.