Defeng Sun (National University of Singapore) – Tame Big Convex Optimization Problems Using Second Order Sparsity

Abstract

Big convex optimization models are ubiquitous in machine learning, statistics, finance, signal processing, imaging science, geophysics and many other areas. Concerned with the huge computational burdens of the interior point methods (IPMs) for solving big scale problems, many researchers and practitioners tend to believe that the first order methods such as the accelerated proximal gradient methods and the alternating direction methods of multipliers are the only option for the rescue. While these first order methods have enjoyed very successful stories for some interesting applications, they also encounter enormous numerical difficulties in dealing with many real data problems of big scales even only with a low or moderate solution quality. New ideas for solving these problems are highly sought both in practice and academic research. In this talk, we shall demonstrate how the second order sparsity property exhibited in big sparse optimization models can be intelligently explored to overcome the mentioned difficulties either in IPMs or in the first order methods. One critical discovery is that the second order sparsity allows one to solve sub-problems at costs even lower than many first order methods. For the purpose of illustration, we shall present highly efficient and robust semi-smooth Newton based augmented Lagrangian methods for solving various lasso and support vector machine models.

Speaker Bio

Born in a small village (where the story of Mo Yan’s award winning novel Red Sorghum took place) located at Gaomi County (高密县), Shandong Province, China, Professor Sun graduated with a BSc (1989) from Nanjing University, China, majoring in computational mathematics. He also achieved his MSc (1992) from Nanjing University, working on variational inequalities under the supervision of Professor Bingsheng He, and stochastic optimization under the supervision of Professor Jinde Wang. He studied for his PhD (1995) from Institute of Applied Mathematics, Chinese Academy of Sciences under the supervision of Professor Jiye Han focusing on non-smooth equations and optimization. Professor Sun is also a Visiting Fellow, Research Associate and then Australian Postdoctoral Fellow at the University of New South Wales, Australia (1995-2000), with key focus in the area of optimization. He has been with Department of Mathematics, National University of Singapore since December 2000 as Assistant Professor (December 2005), Associate Professor (January 2006) and Professor (July 2009 till now). He also worked for Risk Management Institute (RMI) as Deputy Director, Research (August 2009-August 2014) and acting Program Director to Masters of Financial Engineering (March –June, 2014).

For more information about the ESD Seminars Series, please contact Ying Xu at xu_ying@sutd.edu.sg.

170223 DSS Prof Sun Defeng eDM Final