Lower Complexity Bound of First-Order Methods for Affinely Constrained Composite Nonconvex Problems

信息管理与工程学院308室
上海财经大学（第三教学楼西侧）

上海市杨浦区武东路100号

Yangyang Xu is now an associate professor in the Department of Mathematical Sciences at Rensselaer Polytechnic Institute. He received his B.S. in Computational Mathematics from Nanjing University in 2007, M.S. in Operations Research from the Chinese Academy of Sciences in 2010, and Ph.D. from the Department of Computational and Applied Mathematics at Rice University in 2014. His research interests are on optimization theory and methods and their applications, such as machine learning, statistics, and signal processing. He developed optimization algorithms for compressed sensing, matrix completion, and tensor factorization and learning. His recent research focuses on first-order methods, stochastic optimization methods, and distributed optimization. His research has been supported by NSF, ONR, and IBM. He is now an associate editor of Mathematics of Operations Research.

Many recent studies on first-order methods (FOMs) focus on composite non-convex non-smooth optimization with linear and/or nonlinear function constraints. Upper (or worst-case) complexity bounds have been established for these methods. However, little can be claimed about their optimality as no lower bound is known, except for a few special smooth non-convex cases. In this talk, I will present lower complexity bounds of FOMs for solving a class of composite non-convex non-smooth optimization with linear constraints. Assuming two different first-order oracles, we establish lower complexity bounds of FOMs to produce a (near) $\epsilon$-stationary point of a problem (and its reformulation) in the considered problem class, for any given tolerance $\epsilon>0$. Our lower bounds indicate that the existence of a non-smooth convex regularizer can make the affinely constrained problem arbitrarily harder. In addition, we show that our bounds are tight, with a difference of up to a logarithmic factor from an upper complexity bound.