Online Classification Using a Voted RDA Method
This work addresses online classification efficiency for NLP applications, but it is incremental as it builds on existing RDA methods.
The authors tackled online classification by proposing a voted dual averaging method that updates only on misclassified examples, deriving bounds on training mistakes and generalization error. They achieved state-of-the-art performance with sparse models on a large-scale NLP task.
We propose a voted dual averaging method for online classification problems with explicit regularization. This method employs the update rule of the regularized dual averaging (RDA) method, but only on the subsequence of training examples where a classification error is made. We derive a bound on the number of mistakes made by this method on the training set, as well as its generalization error rate. We also introduce the concept of relative strength of regularization, and show how it affects the mistake bound and generalization performance. We experimented with the method using $\ell_1$ regularization on a large-scale natural language processing task, and obtained state-of-the-art classification performance with fairly sparse models.