Error Bounds for Structured Convex Optimization Problems and Convergence Rate Analysis of First-Order Methods¶
Anthony Man-Cho So
Professor
Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong
Abstract: In recent years, we have witnessed a widespread use of first-order methods (FOMs) to solve large-scale structured convex optimization problems. One fundamental issue concerning FOMs is their convergence properties. Currently, linear convergence results for FOMs are typically established under strong convexity assumptions on the objective. However, such assumptions are not satisfied in most applications of interest. In this talk, we will present a framework for analyzing the convergence rates of FOMs. A key component of this framework is a so-called error bound condition, which provides a tractable bound on the distance from any candidate solution to the optimal solution set of the problem at hand. We will show that many structured convex optimization problems in machine learning satisfy the error bound condition. Consequently, we are able to show that many FOMs have a linear rate of convergence when applied to those problems.
Bio: Anthony Man-Cho So received his BSE degree in Computer Science from Princeton University in 2000 with minors in Applied and Computational Mathematics, Engineering and Management Systems, and German Language and Culture. He then received his MSc degree in Computer Science in 2002, and his PhD degree in Computer Science with a PhD minor in Mathematics in 2007, all from Stanford University. Dr. So joined The Chinese University of Hong Kong (CUHK) in 2007. He currently serves as Assistant Dean of the Faculty of Engineering and is an Associate Professor in the Department of Systems Engineering and Engineering Management. He also holds a courtesy appointment as Associate Professor in the CUHK-BGI Innovation Institute of Trans-omics. His recent research focuses on the interplay between optimization theory and various areas of algorithm design, such as computational geometry, signal processing, bioinformatics, stochastic optimization, combinatorial optimization, and algorithmic game theory.
At present, Dr. So serves on the editorial boards of Optimization Methods and Software, Mathematics of Operations Research, IEEE Transactions on Signal Processing, and Journal of Global Optimization. He received the 2010 Optimization Prize for Young Researchers from the Optimization Society of the Institute for Operations Research and the Management Sciences (INFORMS), and the 2010 Young Researcher Award from CUHK. He also received the 2008 Exemplary Teaching Award and the 2011 and 2013 Dean's Exemplary Teaching Award from the Faculty of Engineering at CUHK, and the 2013 Vice-Chancellor's Exemplary Teaching Award from CUHK.