  Despite the recent development in machine learning, most learning systems are
still under the concept of "black box", where the performance cannot be
understood and derived. With the rise of safety and privacy concerns in public,
designing an explainable learning system has become a new trend in machine
learning. In general, many machine learning problems are formulated as
minimizing (or maximizing) some loss function. Since real data are most likely
generated from non-linear models, the loss function is non-convex in general.
Unlike the convex optimization problem, gradient descent algorithms will be
trapped in spurious local minima in solving non-convex optimization. Therefore,
it is challenging to provide explainable algorithms when studying non-convex
optimization problems. In this thesis, two popular non-convex problems are
studied: (1) low-rank matrix completion and (2) neural network learning.
