Convex Optimization for Active Learning with Large Margins

In this paper we show how large margin assump-tions make it possible to use ideas and algorithms from convex optimization for active learning. This provides an alternative and complementary approach to standard algorithms for active learning. These algorithms appear to be robust and provide approx-imately correct hypotheses with probability one, as opposed to the standard PAC learning results. In particular we consider the problem of finding global convergence bounds for active learning with halfspaces. We show that a large margin assump-tion allows the reduction of active learning prob-lem to that of convex optimization from which one can construct efficient algorithms. This work gen-eralizes and clarifies previous results in this area and provides new insights