Title : Algorithms and Analysis for Non-convex Problems in Machine Learning

Bo Xie

School of Computational Science and Engineering

College of Computing

Georgia Institute of Technology

Date : Friday, December 02, 2016

Time : 10:30 AM to 12:30 PM EST

Location : KACB 1315

Committee

-------------

Dr. Le Song (Advisor), School of Computational Science and Engineering

Dr. Santosh Vempala, School of Computer Science

Dr. Hongyuan Zha, School of Computational Science and Engineering

Abstract

-------------

Non-convex problems are ubiquitous in machine learning, ranging from hidden variable models in graphical model estimation, to matrix factorization in recommender systems, and to recently hugely successful deep learning models. Compared with convex problems which have provably efficient algorithms, non-convex problems are in general much harder to solve and most existing algorithms do not have theoretical guarantees on their performance.

In this thesis, we propose efficient algorithms and provide novel analysis for many of the important non-convex problems in machine learning. For hidden variable models, we leverage the special tensor structure and design a nonlinear spectral algorithm that avoids the intractability of non-convex optimization. To scale up such nonlinear spectral decomposition, we have also proposed a doubly stochastic gradient algorithm as well as a distributed algorithm that can efficiently run on millions of data points. Moreover, we provide formal analysis on the optimization landscape of one-hidden-layer neural network where any critical point implies a global minimum when the neural weights are diverse enough.