Convex optimization methods for robust classification

The support vector machine (SVM) is a supervised learning algorithm used for robust classification. The SVM training problem can be formulated as a dense quadratic programming problem (QP). In practice, this QP is usually solved in batch mode, using general-purpose interior-point solvers. Although such methods are quite efficient, they are not well suited when the training set is very large as the SVM QP scales with the training set size rather than the input dimension. Such methods are also not well suited in situations where the training vectors are made available sequentially. In both these cases, iterative implementations are desirable.; We examine three possible classes of iterative methods to solve the SVM training problem, namely row-action, sequential analytic centering, and sequential self-dual embedding methods. While row-action methods suffer from slow convergence, these algorithms may be our only choice for very large scale problems as they operate on only one row of the data matrix at a time. They are also extremely easy to implement. Sequential analytic centering based methods, on the other hand, are not quite as simple to implement but have superior convergence properties. Sequential self-dual embedding methods have similar computational properties to sequential analytic centering methods but have the added advantage of producing a series of optimal SVM solutions as opposed to the suboptimal ones produced by the analytic centering method.; We also examine a large scale algorithm for the L1 norm SVM. This common reformulation of the standard SVM is of interest because the resulting classifier is known to be sparse, which allows for simultaneous classification and relevant feature selection. We apply a coordinate descent based algorithm to a smooth approximation of the L1 norm problem and show that a sparse classifier with good generalizability can be produced. In addition, we show this algorithm to be of comparable complexity to the row action algorithm applied to the L2 norm problem.; Finally, we address a basic problem in probability with applications to classification. We find a sharp lower bound on the probability of a set defined by quadratic inequalities, given the first two moments of the distribution. We give a constructive proof based on the solution of two semidefinite programming formulations. The probability of correct classification can often be expressed as the probability that a random variable lies in a set defined by linear or quadratic inequalities. Therefore, these techniques can be used to find lower bounds on the probability of correct classification, or equivalently upper bounds on the probability of error.