Efficient Online Multiclass Prediction on Graphs via Surrogate Losses
Abstract
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.
Cite
Text
Rakhlin and Sridharan. "Efficient Online Multiclass Prediction on Graphs via Surrogate Losses." International Conference on Artificial Intelligence and Statistics, 2017.Markdown
[Rakhlin and Sridharan. "Efficient Online Multiclass Prediction on Graphs via Surrogate Losses." International Conference on Artificial Intelligence and Statistics, 2017.](https://mlanthology.org/aistats/2017/rakhlin2017aistats-efficient/)BibTeX
@inproceedings{rakhlin2017aistats-efficient,
title = {{Efficient Online Multiclass Prediction on Graphs via Surrogate Losses}},
author = {Rakhlin, Alexander and Sridharan, Karthik},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2017},
pages = {1403-1411},
url = {https://mlanthology.org/aistats/2017/rakhlin2017aistats-efficient/}
}