Minover revisited for incremental support-vector-classification

Abstract. The well-known and very simple MinOver algorithm is reformulated for incremental support vector classification with and without kernels. A modified proof for its O(t −1/2) convergence is presented, with t as the number of training steps. Based on this modified proof it is shown that even a convergence of at least O(t −1) is given. This new convergence bound for MinOver is confirmed by computer experiments on artificial data sets. The computational effort per training step scales as O(N) with the number N of training patterns.