Efficient Online Multiclass Prediction on Graphs via Surrogate Losses


Alexander Rakhlin, Karthik Sridharan ;
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:1403-1411, 2017.


We develop computationally efficient algorithms for online multi-class prediction. Our construction is based on carefully-chosen data-dependent surrogate loss functions, and the new methods enjoy strong mistake bound guarantees. To illustrate the technique, we study the combinatorial problem of node classification and develop a prediction strategy that is linear-time per round. In contrast, the offline benchmark is NP-hard to compute in general. We demonstrate the empirical performance of the method on several datasets.

Related Material