A randomized algorithm for exact transduction

Random sampling is an efficient method dealing with constrained optimization problems. In computational geometry, it has been applied, through Clarkson's algorithm [10], to solve a general class of problems called violator spaces. In machine learning, TSVM is a learning method used when only a small fraction of labeled data is available, which implies solving a non convex optimization problem. Several approximation methods have been proposed to solve it, but they usually find suboptimal solutions. Global optimal solution may be obtained using exact techniques, costing an exponential time complexity with respect to the number of instances. In this paper, an interpretation of TSVM in terms of violator space is given. Hence, a randomized method is presented extending the use of exact methods now reducing the time complexity to sub-exponential in particular exponential w.r.t. the number of support vectors of the optimal solution instead of exponential w.r.t. the number of instances.