Bandit Online Learning on Graphs via Adaptive Optimization

Peng Yang, Peilin Zhao, Xin Gao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


Traditional online learning on graphs adapts graph Laplacian into ridge regression, which may not guarantee reasonable accuracy when the data are adversarially generated. To solve this issue, we exploit an adaptive optimization framework for online classification on graphs. The derived model can achieve a min-max regret under an adversarial mechanism of data generation. To take advantage of the informative labels, we propose an adaptive large-margin update rule, which enjoys a lower regret than the algorithms using error-driven update rules. However, this algorithm assumes that the full information label is provided for each node, which is violated in many practical applications where labeling is expensive and the oracle may only tell whether the prediction is correct or not. To address this issue, we propose a bandit online algorithm on graphs. It derives per-instance confidence region of the prediction, from which the model can be learned adaptively to minimize the online regret. Experiments on benchmark graph datasets show that the proposed bandit algorithm outperforms state-of-the-art competitors, even sometimes beats the algorithms using full information label feedback.
Original languageEnglish (US)
Title of host publicationProceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
PublisherInternational Joint Conferences on Artificial Intelligence
Number of pages7
ISBN (Print)9780999241127
StatePublished - Jul 5 2018


Dive into the research topics of 'Bandit Online Learning on Graphs via Adaptive Optimization'. Together they form a unique fingerprint.

Cite this