Global Optimality in Matrix Factorization and Deep Learning

The past few years have seen a dramatic increase in the performance of recognition systems thanks to the introduction of deep networks for representation learning. However, the mathematical reasons for this success remain elusive. A key issue is that the neural network training problem is non-convex, hence optimization algorithms may not return a global minima. Building on ideas from convex relaxations of matrix factorizations, this work proposes a general framework which allows for the analysis of a wide range of non-convex factorization problems "“ including matrix factorization, tensor factorization, and deep neural network training. The talk will describe sufficient conditions under which a local minimum of the non-convex optimization problem is a global minimum and show that if the size of the factorized variables is large enough then from any initialization it is possible to find a global minimizer using a local descent algorithm. Joint work with Ben Haeffele.
Professor Vidal received his B.S. degree in Electrical Engineering (valedictorian) from the Pontificia Universidad Catolica de Chile in 1997 and his M.S. and Ph.D. degrees in Electrical Engineering and Computer Sciences from the University of California at Berkeley in 2000 and 2003, respectively. He was a research fellow at the National ICT Australia in 2003 and has been a faculty member in the Department of Biomedical Engineering and the Center for Imaging Science of The Johns Hopkins University since 2004. He has held several visiting faculty positions at Stanford, INRIA/ENS Paris, the Catholic University of Chile, Universite Henri Poincare, and the Australian National University. Dr. Vidal is co-author of the book "Generalized Principal Component Analysis" (2016), co-editor of the book "Dynamical Vision" and co-author of over 200 articles in machine learning, computer vision, biomedical image analysis, hybrid systems, robotics and signal processing. Dr. Vidal is or has been Associate Editor of Medical Image Analysis, the IEEE Transactions on Pattern Analysis and Machine Intelligence, the SIAM Journal on Imaging Sciences, Computer Vision and Image Understanding, and the Journal of Mathematical Imaging and Vision, and guest editor of the International Journal on Computer Vision and Signal Processing Magazine. He is or has been program chair for ICCV 2015, CVPR 2014, WMVC 2009 and PSIVT 2007. He was area chair for AAAI 2016, NIPS 2015, MICCAI 2013 and 2014, ICCV 2007, 2011, 2013 and 2017, and CVPR 2005, 2013 and 2017. Dr. Vidal is recipient of numerous awards for his work, including the 2012 J.K. Aggarwal Prize for "outstanding contributions to generalized principal component analysis (GPCA) and subspace clustering in computer vision and pattern recognition" , the 2012 Best Paper Award in Medical Robotics and Computer Assisted Interventions (with Benjamin Bejar and Luca Zappella), the 2011 Best Paper Award Finalist at the Conference on Decision and Control (with Roberto Tron and Bijan Afsari), the 2009 ONR Young Investigator Award, the 2009 Sloan Research Fellowship, the 2005 NFS CAREER Award and the 2004 Best Paper Award Honorable Mention (with Prof. Yi Ma) at the European Conference on Computer Vision. He also received the 2004 Sakrison Memorial Prize for "completing an exceptionally documented piece of research" , the 2003 Eli Jury award for "outstanding achievement in the area of Systems, Communications, Control, or Signal Processing" , the 2002 Student Continuation Award from NASA Ames, the 1998 Marcos Orrego Puelma Award from the Institute of Engineers of Chile, and the 1997 Award of the School of Engineering of the Pontificia Universidad Catolica de Chile to the best graduating student of the school. He is a fellow of the IEEE (2014), fellow of the IAPR (2016), and a member of the ACM and SIAM.