Anthony Man-Cho So, Professor, Department of Systems Engineering and Engineering Management The Chinese University of Hong Kong

Yafeng Liu, Associate Professor

On the Complexity of Approximate Stationarity Concepts in Non-Smooth Optimization

16:00-17:00, August 1 (Tuesday), Z311

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.

报告人简介: 苏文藻教授现为香港中文大学研究生院院长、晨兴书院副院长及系统工程与工程管理学系教授，主要研究方向为数学优化理论及其在计算几何、机器学习、信号处理和统计等领域的应用。他于2019年被任命为香港中文大学工程学院杰出学人，2023年当选IEEE（电机电子工程师学会）会士。他曾获得多个研究和教学奖项，包括2018年IEEE信号处理分会最佳论文奖、2015年IEEE信号处理分会《IEEE Signal Processing Magazine》最佳论文奖、2014年IEEE通信分会亚太杰出论文奖、2010年INFORMS（运筹学与管理学研究协会）优化学会青年奖、香港大学教育资助委员会2022年杰出教学奖、香港中文大学2022年博文教学奖、香港中文大学2013年校长模范教学奖等。他的学生也曾获得国内与国外的研究奖项。他现担任数学优化领域国际期刊《Journal of Global Optimization》、《Mathematical Programming》、《Mathematics of Operations Research》、《Optimization Methods and Software》和《SIAM Journal on Optimization》的编辑，并曾担任信号处理领域国际期刊《IEEE Transactions on Signal Processing》的编辑和信号处理领域国际期刊《IEEE Signal Processing Magazine》中Special Issue on Non-Convex Optimization for Signal Processing and Machine Learning的客座主编。他现为中国运筹学会数学规划分会副理事长和常务理事。