×

On convergence rate of a convex relaxation of semisupervised support vector machines. (English) Zbl 1435.68283

Vapnick developed a machine learning technique essentially designed for binary classification and termed it as support vector machine (SVM). This concept was generalized to semi-supervised learning by Vapnick and Sterin and called semi-supervised support vector machine (S\(^{3}\)VM). S\(^{3}\)VM assumes a non-convex integer programming formulation that is hard to approximate. Recently, Bai and Yan proposed a conic programming reformulation of S\(^{3}\)VM. The conic relaxation is approximated by doubly non-negative matrices. In the paper under consideration, the dual of of the above-mentioned cone programming relaxation is constructed and results related to the approximation error are obtained. Moreover, the order of convergence is found. The cone programming relaxation is discretized and it is shown that the discretization method converges quadratically.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI