Scalable Semi-Supervised SVM via Triply Stochastic Gradients
  Semi-supervised learning (SSL) plays an increasingly important role in the
big data era because a large number of unlabeled samples can be used
effectively to improve the performance of the classifier. Semi-supervised
support vector machine (S$^3$VM) is one of the most appealing methods for SSL,
but scaling up S$^3$VM for kernel learning is still an open problem. Recently,
a doubly stochastic gradient (DSG) algorithm has been proposed to achieve
efficient and scalable training for kernel methods. However, the algorithm and
theoretical analysis of DSG are developed based on the convexity assumption
which makes them incompetent for non-convex problems such as S$^3$VM. To
address this problem, in this paper, we propose a triply stochastic gradient
algorithm for S$^3$VM, called TSGS$^3$VM. Specifically, to handle two types of
data instances involved in S$^3$VM, TSGS$^3$VM samples a labeled instance and
an unlabeled instance as well with the random features in each iteration to
compute a triply stochastic gradient. We use the approximated gradient to
update the solution. More importantly, we establish new theoretic analysis for
TSGS$^3$VM which guarantees that TSGS$^3$VM can converge to a stationary point.
Extensive experimental results on a variety of datasets demonstrate that
TSGS$^3$VM is much more efficient and scalable than existing S$^3$VM
algorithms.
