Improved Algorithms for Online Classification with Surrogate Losses

We study online multiclass classification with surrogate losses. We identify and exploit a structural property of margin-based classifiers: on many rounds predictions are stable in the sense that after an update of the parameters the algorithms do not change the predicted label on the current example. By exploiting this stability we improve upon the state of the art in several ways. We provide an improved surrogate regret bound for the perceptron, develop a parameter-free version of $\texttt{GAPTRON}$, develop improved results for the delayed feedback setting, and extend our results to the batch setting. These results are complimented by empirical evaluations.