Tengyu Ma will present his FPO, "Non-convex Optimization for Machine Learning: Design, Analysis, and Understanding" on Thursday, 10/12/2017 at 3pm, in CS 402.
The members of his committee are: Sanjeev Arora (adviser); Readers: Rong GE (Duke), Sanjeev Arora, and David Steurer (ETH Zurich); Nonreaders: Sanjeev Arora, Elad Hazan, and Mark Braverman.
A copy of his thesis, is available in Room 310. Everyone is invited to attend his talk. The talk abstract follows below:
Non-convex optimization is ubiquitous in modern machine learning: recent breakthroughs
in deep learning require optimizing non-convex training objective functions;
problems that admit accurate convex relaxation can often be solved more efficiently
with non-convex formulations. However, the theoretical understanding of optimizing
non-convex functions remained rather limited to the intractability result of optimizing
worst case non-convex functions. Can we extend the algorithmic frontier by effi-
ciently optimizing a family of interesting non-convex functions? Can we successfully
apply non-convex optimization to machine learning problems with provable guarantees?
How do we interpret the complicated models in machine learning that demand
non-convex optimizers?
Towards addressing these questions, in this thesis, we theoretically studied various
machine learning models including sparse coding, topic models, and matrix completion,
linear dynamical systems, and word embeddings.
We first consider how to find a coarse solution to serve as a good starting point
for local improvement algorithms such as stochastic gradient descent. We propose ef-
ficient methods for sparse coding and topic inference with better provable guarantees.
Second, we propose a framework for analyzing local improvement algorithms with
a good starting point. We apply it successfully to the sparse coding problem and
demonstrate its advantage over other related frameworks.
Then, we consider minimizing a family of non-convex functions that local improvement
algorithms can succeed efficiently from random or arbitrary initialization
— the family of functions of which all local minima are also global. The challenge, in
turn, becomes proving the objective function belongs to this class. We establish such
type of results for the natural learning objectives for matrix completion and learning
linear dynamical systems.
iii
Finally, we make steps towards interpreting the non-linear models that require
non-convex training algorithms. We reflect on the principles of word embeddings in
natural language processing. We give a generative model for the texts, using which
we explain why different non-convex formulations such as word2vec and GloVe can
learn similar word embeddings with the surprising performance — analogous words
have embeddings with similar differences.
