AISTATS 2017poster8 citations
Efficient Online Multiclass Prediction on Graphs via Surrogate Losses
Alexander Rakhlin, Karthik Sridharan
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.
BibTeX
@InProceedings{pmlr-v54-rakhlin17a,
title = {{Efficient Online Multiclass Prediction on Graphs via Surrogate Losses}},
author = {Rakhlin, Alexander and Sridharan, Karthik},
booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics},
pages = {1403--1411},
year = {2017},
editor = {Singh, Aarti and Zhu, Jerry},
volume = {54},
series = {Proceedings of Machine Learning Research},
month = {20--22 Apr},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v54/rakhlin17a/rakhlin17a.pdf},
url = {https://proceedings.mlr.press/v54/rakhlin17a.html},
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. }
}