Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

Speaker:	Professor Anthony Man-Cho So, Department of Systems Engineering and Engineering Management The Chinese University of Hong Kong
Inviter:	Associate Professor Yafeng Liu
Title:	On the Complexity of Approximate Stationarity Concepts in Non-Smooth Optimization
Language:	Chinese
Time & Venue:	2023.08.01 16:00-17:00 Z311
Abstract:	Non-smooth non-convex optimization problems pose many challenges to the definition and computation of stationarity concepts. Although the field of variational analysis has over the years developed various stationarity concepts for Lipschitz functions and provided many beautiful theoretical tools for studying them, the computational complexity of these concepts remains largely open. In this talk, we discuss the complexity of finding (approximate) stationary points of certain sub-classes of Lipschitz functions. On the negative side, we show that under a standard first-order oracle framework, no algorithm that can find a near-approximate stationary (NAS) point of any Clarke regular function has dimension-free finite-time complexity. On the positive side, we show that with a standard first-order oracle, there is an algorithm with dimension-free finite-time complexity for computing a Goldstein approximate stationary point of a Lipschitz function. If time permits, we also discuss how such an algorithm can be used to compute NAS points of certain Clarke irregular Lipschitz functions that arise in machine learning applications. Joint work with Lai Tian and Kaiwen Zhou.