Institute of Information Science, Academia Sinica

Due to the nature of the online learning setting, the online learning algorithms have been successfully applied to large scale classification tasks. This type of algorithms can be interpreted as a stochastic gradient descent method that try to find the solution of the underlying minimization problem with the objective function consisting the sum of training loss and regularization term. How to decide the learning rate becomes an important issue in this kind of learning algorithms. The passive and aggressive (PA) algorithm proposed an updating scheme to determine the new classifier. It suggests that the new classifier should not only classify the new arriving data correctly but also as close to current classifier as possible. A closed form of updating rule was derived that makes PA algorithm training extremely fast. However, a lack of memory for previous instances might hurt the learning efficiency. We propose a new updating rule that takes the accumulated variances and means information for different classes into account. Using these information, a good proximal classification model can be generated. We augment the proximal model into PA algorithm updating rule in a closed form. Thus, our proposed method has the same computational advantage as PA algorithm. The preliminary numerical results show that our proposed method is less sensitive to the input order of training data than PA algorithm. It will return a near optimal classifier in a single pass. Two consecutive classifiers generated by two training epochs are very close. These evidences show that our method is suitable for the learning task with extremely large dataset.