Edward
Cheung,
PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
In this seminar, we provide efficient optimization algorithms for some semi-supervised learning (SSL) tasks in machine learning. For many machine learning tasks, training a classifier requires a large amount of labeled data; however, providing labels typically requires costly manual annotation. Fortunately, there is typically an abundance of unlabeled data that can be easily collected for many domains. We focus on problems where an underlying structure allows us to leverage the large amounts of unlabeled data, while only requiring small amounts of labeled data. In particular, we consider low-rank matrix completion problems with applications to recommender systems, and semi-supervised support vector machines (S3VM) to solve binary classification problems, such as digit recognition or disease classification.
For the low-rank matrix completion problems, we explore Frank-Wolfe methods solve the convex trace norm constrained problem. We introduce the idea of "rank-drop steps" to ensure that the iterates are always low-rank, leading to much more scalable algorithms. We then extend the Frank-Wolfe analysis to accommodate nonsmooth objectives for separable objectives using "uniform affine approximations." Finally, we propose a variant of self-training for the semi-supervised binary classification problem by leveraging ideas from S3VM to address common issues associated with self-training, such as error propagation and label imbalances.